This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

level data: RLE type compression vs fixed length

level data: RLE type compression vs fixed length
by on (#40801)
I am at the stage in my game where i am designing the various data formats and what not. the levels in my game will be for a grid of 14x10 tiles. (there is actually a frame around this grid so it is really 16x12, but the frame is tile type 0 so when i clear the buffer it will take care of this).... anyways, i am trying to decided on storing 16x10 tiles in the format of :

Code:
76543210
XXXXYYYY
      XXXX # of times tile repeats
      YYYY # tile number to repeat

with this format, the smallest level size (with the other level information) would be around 12 bytes (not that this would happen as the level would be boring as hell) and no bigger than 100 bytes

although, if i store just two tiles per a byte... and have the stored level data be just the 14x10... then i can store each level in ~74 bytes.


what methods does everyone typically use? i am leaning towards having each level be the 74 bytes as it should average out.

by on (#40803)
Well for this type of thing (a one-screen level, I'm assuming), methods I've used have been a bit more extreme (only 2 tile types for a maze) where I had 32 byte levels (each bit represented the absence/presence of a tile). But for your case, I'd probably stick with a system where in one byte there are 2 tiles. This is good because you have a fixed size for a level, and you won't end up wasting bytes or anything like that.

But a better system might be an objects system. Define rectangular objects in ROM and place them on the level using coordinates. For example you could have an 8 tile wide horizontal bar of metatiles, and this can be made of any metatiles. Then you do this:

.db XPosition, YPosition, ObjectNumber

Which would use 3 bytes to place a large object. You could also implement a layering system with this where metatile #0 in each of these blocks represents invisibility, so you can put an object below it which will show up through the "invisible" metatiles. But if that's too complex, I'd stick with the two tiles per byte. How much space are you working with for how many levels?

EDIT: Another advantage of the objects system is it works 2 dimensionally, where RLE and stuff works 1-dimensionally. Though these objects might be defined 1 dimensionally....

by on (#40804)
i have about 16kb worth of space for levels, so optimizations is not really that big of a deal i guess. I have used use the object method before though in this the odds of reusing a block of tiles is very slim. in previous versions that had less tile types, i used the RLE method and got rather small levels.... though with the new tiles i think the 2 tiles per a byte will work better :)

by on (#40805)
I used to be a big fan of object-based encodings, as seen in Super Mario Bros. and Super Mario World. But as I did basic research on what would go into a social sim game similar to Animal Crossing or Harvest Moon, I came up with the outline of a proof that an object-based encoding is equivalent to run-length encoding.

Assume that an object-based encoding can be converted into an equivalent object-based encoding where the coordinates are strictly increasing through a level. (Without loss of generality, assume row-major decompressed storage; for side-scrollers that use column-major storage, exchange X and Y.) For objects A and B, if A.Y < B.Y then A comes before B, and if A.Y == B.Y and A.X < B.X, then A comes before B. So the coordinates X and Y of each object can be replaced with a number XY = Y * width + X, which is also strictly increasing. Now, if you subtract two adjacent objects' XY values, you get 1 + the length of the run between the objects.

WhoaMan: How many levels do you plan to have? And can you draw one for us with ASCII art inside the [code] tag?

by on (#40806)
tepples wrote:
Assume that an object-based encoding can be converted into an equivalent object-based encoding where the coordinates are strictly increasing through a level. (Without loss of generality, assume row-major decompressed storage; for side-scrollers that use column-major storage, exchange X and Y.) For objects A and B, if A.Y < B.Y then A comes before B, and if A.Y == B.Y and A.X < B.X, then A comes before B. So the coordinates X and Y of each object can be replaced with a number XY = Y * width + X, which is also strictly increasing. Now, if you subtract two adjacent objects' XY values, you get 1 + the length of the run between the objects.
I fail to see how you account for the the vector "objects" in a game like Mario being two-dimensional. That is to say filling a rectangle from four edge coordinates shouldn't fill everything between the first and last points in your single-dimensional XY-space, merely the interior portion of each individual column/row. Obviously there will always be scenes for which RLE is superior, but I fail to see how the schemes are equivalent (relative to some appropriate constant factor.)

Besides, the sheer awesomeness of the SMB3/SMW approach is damn near impossible to beat :)

edit: I suppose you could tweak the RLE routine such that only the "interior" points are filled, and subdivide the rectangles in such a way as to make consecutive rectangles share edges (plus some horizontal wrapping logic), let the points be strictly increasing, and avoid overdraw. Which ought to make it relatively straightforward to write an automatic encoder if nothing else.
Uh, or... something.

by on (#40808)
tepples wrote:
I came up with the outline of a proof that an object-based encoding is equivalent to run-length encoding.


What do you mean by equivalent? I fail to see how under all conditions, they would be "equivalent".

by on (#40810)
Dragon Warrior and Zelda 2 use that exact format described in the first post, only Zelda 2 uses a nibble-swapped version of Dragon Warrior's. Hacking those games taught me RLE.

But you may want to look into LZ compression. If done right, it is no worse than RLE, and can possibly be better.

by on (#40811)
doynax wrote:
tepples wrote:
Assume that an object-based encoding can be converted into an equivalent object-based encoding where the coordinates are strictly increasing through a level. [etc]

I fail to see how you account for the the vector "objects" in a game like Mario being two-dimensional. That is to say filling a rectangle from four edge coordinates shouldn't fill everything between the first and last points in your single-dimensional XY-space

Decoding an object-based level can be separated into two passes: placing markers representing an object's upper-left corner into an array, then expanding them rectangularly. The first step is what's equivalent to RLE; after the first step, there's still a buttload of empty space in the array.

Dwedit wrote:
But you may want to look into LZ compression. If done right, it is no worse than RLE, and can possibly be better.

In fact, RLE can be seen as the special case of LZ77-family algorithms with match distances of 1 byte.

by on (#40813)
I think tepples' point of equivalence only applies when the object-based format's objects are all of like size, placed on a grid with a spacing the same as the object size. If object sizes vary, then decoding wouldn't be able to follow a strict top-to-bottom, left-to-right tile order.

by on (#40814)
blargg wrote:
I think tepples' point of equivalence only applies when the object-based formats objects are all of like size, placed on a grid with a spacing the same as the object size.


Like large metatiles?

When I refer to an object based system, I refer to placing variable sized objects over a "cleared" background. I seem to recall a title screen compression discussion created by SecretServiceDude where I suggested he used an object based system like I just described, and it saved him a good deal of space.

Imagine an empty background with 3 identical, large, complicated rectangular objects. Place them slightly layered on top of each other like so:

Code:
11
122
 233
  33


Say that one of these objects compressed with RLE takes up 33 bytes. It's going to take more than that to define the whole background with RLE (including the blank spaces around that). However, it's going to take 42 bytes to define that whole background with an object based system.

The object itself is 33 bytes, and pointing to/placing the object takes 3 bytes. So 3 objects times 3 bytes = 9 + 33 = 42. With just RLE and no layering system, this would take a lot more, depending on the object.

by on (#40820)
Then there's always huge meta-meta tiles, like Ultima 6 for the PC.
There was the "Map", made up of big 8x8 tile sheets (up to 1024 different ones), and the "chunks", which defined the contents of each 8x8 tile sheet, using up to 256 different tiles. I think the main map was 128x128 sheets. Total size of a U6 world map: 84KiB exactly.

by on (#40827)
In my game (ChateauLevania, pretty much a ripoff of Castlevania: SOTN but based off of a book I'm writing titled "The Curse of Chateau LeVeaux"), the map is made of rooms, which are collections of screens, which are each 4x4 collections of 8x8 tile metatiles (so they're 256x256 pixels big, but it makes it easier to handle if they're not 256x240).

These metatiles are made of 2x2 4x4 tile metatiles, which are made of 2x2 2x2 tile metatiles, which are made of 2x2 single tiles. There are 256 possible different tiles to choose from with 8x8, 4x4, 2x2 and of course 1x1. You can swap these stacks of metatile definitions to have more unique level design.

All screens are defined in one bank (16 bytes each, so 16k/16 =1024 unique screens), all rooms are defined in one bank (all are variable size), and all metatiles are defined in one bank (~4k for each stack, so 4 different ones minimum, but they'll be layed out so you can use more than that). That makes my castle map 48k just for the background part, but maybe I'll squeeze the object map into the room part, making the entire map 48k, which I think is decent when I have 512k to work with. If not, then it'll be 64k, which I still think is pretty okay.