Users browsing this thread: 1 Guest(s)
Faster compression & Imperial Camp boxes

#1
Posts: 18
Threads: 3
Thanks Received: 0
Thanks Given: 0
Joined: Nov 2019
Reputation: 0
Status
None
The Imperial Camp has a box which can be walked on but not walked off causing a softlock. This seems due to the player changing layers to walk under a nearby wall but one of the boxes being at the transition point makes returning impossible. The way I fixed this bug required working with compressed data.

A perl script is available on the compression page; however, while experimenting I found that it did not meet my needs. I want to keep WC executing in under 1 second under any configuration but discovered that larger chunks of data could take significantly longer to compress. The Imperial Camp bug does not require compressing much data but I want something flexible for future changes.

Attached are compression and decompression functions in Python which seem to significantly improve upon current methods.
Also attached are benchmarks of various sizes between the perl script, functions in BC, and my method. Benchmarks use Perl 5.30.0 and Python 3.8.5 on my development machine.

The benchmarks decompress then recompress data at:
0x2fe49b (1048 bytes), wob_minimap
0x2f114f (8449 bytes), wob_graphics
0x02686c (8692 bytes), title_intro_fc_world
0x2ed434 (15643 bytes), wob_map
0x18f000 (24178 bytes), title_intro

Additionally, 3 tests were run by compressing and then decompressing the beginning of a ROM.
0x0, (20000 bytes), rom_start_20k
0x0, (50000 bytes), rom_start_50k
0x0, (65535 bytes), rom_start

As a sidenote, none of the BC tests decompressed to the exact original data. I am not certain whether this was an error in the compression, decompression or my testing. I used the decompress/recompress functions and default simple/complicated arguments.

My new methods were able to compress each test in under 1.5 seconds.
The biggest improvement came from the wob_map test at 0x2ed434. The perl script took 5 minutes and 58 seconds, BC produced an error, and this approach was able to successfully compress it in 1.404 seconds.
Another notable example was title_intro at 0x18f000 taking 43.692 seconds in the perl script, 6.564 seconds in BC, and 1.210 seconds with this approach.
The improvement also seems consistent with smaller data. wob_minimap is only 1048 bytes and completed in 0.567 seconds with the perl script, 0.249 seconds in BC, but only 0.048 seconds with this approach.

The perl decompression time can sometimes run slightly faster but is overall negligable.
There was no significant difference in compressed sizes between the perl script and this approach. BC compression typically produced larger sizes except in the case of wob_minimap.

Overall, this new approach seems to be much faster without any loss in compression.
There are still possible optimizations; however, I am satsified with the improvement in time complexity for now. Hopefully it can be used to significantly speed up other projects as well and may also be helpful in other games such as Chrono Trigger.

As for the Imperial Camp box bug, my solution was to change those boxes to use impassable box tiles from the same map.
The boxes are on layer 1, the data for which is at index 0x1c. The pointer leads to address 0xda6970, which is 1582 bytes
The coordinates for the boxes to change are (19, 13), (15, 14), (18, 14)

Code:
address = 0xda6970
size = 1582

tilemap = load(address, size)
decompressed = decompress(tilemap)

map_width = 64
impassable_box_tile = 62 # box tile that cannot be entered
coordinates = [(19, 13), (15, 14), (18, 14)] # coordinates of boxes to change
for coordinate in coordinates:
    decompressed[coordinate[0] + coordinate[1] * map_width] = impassable_box_tile

compressed = compress(decompressed)
write(address, compressed)

This will not allow character sprites to get close enough to appear "behind" those boxes anymore but will fix appearing inside them, only displaying half the sprite, and the softlock.


Attached Files Thumbnail(s)
   
.txt  compression.txt (3.92 KB, 13 downloads)
  Find
Quote  
[-] The following 5 users say Thank You to AtmaTek for this post:
  • Everything (03-07-2021), Gi Nattak (03-08-2021), madsiur (03-07-2021), snaphat (05-14-2021), SSJ Rick (03-13-2021)

#2
Posts: 2,548
Threads: 98
Thanks Received: 147
Thanks Given: 156
Joined: Aug 2009
Reputation: 52
Status
Nattak\'d
Interesting stuff! I'm not too sure what all the new compression routine would entail exactly (just waking up here), but if it's better, that's great! Was handling the box in question via the level editor not an option? Or perhaps I'm not grasping the full intention of the new compression - would it speed up map-loading or something along those lines? After re-reading a few times, I'm going to assume yes lol.

So about the Imperial Camp box, which box is it? I'm not seeing a pic here. EDIT: Ah I see you put the coordinates.
And it's a vanilla issue? I'm a bit shocked to have had no knowledge of this one.
MORE EDIT: Ah that's right, event triggers normally prevent the player from going up to those boxes... Or is there some way to bypass those triggers?


We are born, live, die and then do the same thing over again.
Quote  

#3
Posts: 178
Threads: 2
Thanks Received: 23
Thanks Given: 4
Joined: Apr 2015
Reputation: 18
Status
None
Nice catch. I didn't know stepping on those boxes caused a soft lock. Actually, I never even knew you could get to that Barrier Ring chest. I think the coordinates you listed might be reversed though? It looks like you have them listed as (y,x) instead of (x,y).
  Find
Quote  

#4
Posts: 2,548
Threads: 98
Thanks Received: 147
Thanks Given: 156
Joined: Aug 2009
Reputation: 52
Status
Nattak\'d
Well unless I've mistaken, there's no way to ever get the chance to step on those particular boxes though, even by way of going to the secret Barrier Ring chest... so I'm a bit baffled how it could happen. I mean of course those boxes would cause the character to become stuck if the character walked on them, due to the tile's properties, but if there's no way to have it happen without hacking then it's not an issue, right? Jumping over to the Barrier Ring tent has the character on autopilot, back and forth, never getting the chance to touch the boxes. Then when escaping the camp, the event triggers prevent it. Is there another way?


We are born, live, die and then do the same thing over again.
Quote  

#5
Posts: 18
Threads: 3
Thanks Received: 0
Thanks Given: 0
Joined: Nov 2019
Reputation: 0
Status
None
(03-07-2021, 02:49 PM)Everything Wrote: Nice catch. I didn't know stepping on those boxes caused a soft lock. Actually, I never even knew you could get to that Barrier Ring chest. I think the coordinates you listed might be reversed though? It looks like you have them listed as (y,x) instead of (x,y).
Thanks. I must have accidentally switched them while posting.

(03-07-2021, 03:32 PM)Gi Nattak Wrote: Well unless I've mistaken, there's no way to ever get the chance to step on those particular boxes though, even by way of going to the secret Barrier Ring chest... so I'm a bit baffled how it could happen.

Yes, you are correct. The bug should not be encountered in a vanilla playthrough. I only posted the Imperial Camp fix for context and in case anyone else wanted to open that map up for exploration.

However, the main reason for posting was to share my compression algorithm rather than the Imperial Camp fix.
Unless an error in my algorithm or testing is found (or someone would like to share a better approach), I believe my method using two additional hash maps can speed up compression in every existing tool and project by an order of magnitude. This potentially also applies to tools and projects for other games using Square's LZSS compression such as Chrono Trigger and FFV (does FFIV use this anywhere?).

I am not very familiar with C#, but I quickly converted the code from FF6LE I found in the source on the wiki to python for the purposes of another benchmark. Attached is the converted code if anyone is interested in checking if the translation can be improved for the benchmark.

I ran the 3 rom start compression tests:
20k compressed in 5.173 seconds by FF6LE compared to my 0.126 seconds
50k compressed in 12.900 seconds by FF6LE compared to my 0.333 seconds
65535 compressed in 18.093 seconds by FF6LE compared to my 0.536 seconds
The resulting compressed file sizes all matched my script exactly and decompressed correctly.

I also believe I discovered a bug in FF6LE while benchmarking. This line in LCDecomp.cs:
Code:
                   while ((run < 31 + 3) &&
                       (buf[bpos - (ulong)x + run] == buf[bpos + run]) &&
                       (bpos + run < fsize))
                   {

Should have the bpos + run < fsize check come before the buf array access to prevent out of bounds access (this occurred during the 50k test):
Code:
while ((run < 31 + 3) &&
   (bpos + run < fsize) &&
   (buf[bpos - (ulong)x + run] == buf[bpos + run]))
{


Attached Files
.txt  ff6le.txt (1.71 KB, 2 downloads)
  Find
Quote  
[-] The following 1 user says Thank You to AtmaTek for this post:
  • madsiur (03-08-2021)

#6
Posts: 200
Threads: 1
Thanks Received: 10
Thanks Given: 0
Joined: Oct 2015
Reputation: 18
Status
None
what are BC and WC? Tongue

Quote:The Imperial Camp has a box which can be walked on but not walked off causing a softlock. This seems due to the player changing layers to walk under a nearby wall but one of the boxes being at the transition point makes returning impossible.
huh, that kind of reminds me of NPCs like Ice Drgn getting trapped one-way:
http://mnrogar.slickproductions.org/phpB...6845#p6845
http://mnrogar.slickproductions.org/phpB...?f=2&t=325
http://mnrogar.slickproductions.org/phpB...4750#p4750  (yeah, a repeat, but it did get discussed further here.)
Quote  

#7
Posts: 2,548
Threads: 98
Thanks Received: 147
Thanks Given: 156
Joined: Aug 2009
Reputation: 52
Status
Nattak\'d
(03-08-2021, 08:38 AM)assassin Wrote: what are BC and WC? Tongue
That would be Beyond Chaos and Worlds Collide, the two most popular randomizers in all the land, BC being the most insane (in a good way) of the two, with tons of randomized sprites, songs, skills, and pretty much everything at this point, while WC is more vanilla-feeling-experience, but is an "open worlds" type format, so the treasures and bosses are all randomized, which makes for an excellent race setting. I think WC is now also doing the tons of randomized sprites as an option - there's lots of options for both to customize the randomness to your liking etc.


We are born, live, die and then do the same thing over again.
Quote  
[-] The following 1 user says Thank You to Gi Nattak for this post:
  • assassin (04-07-2021)



Forum Jump:

Users browsing this thread: 1 Guest(s)


Theme by Madsiur2017Custom Graphics by JamesWhite