nesdev.org

I want to rewrite my map scrolling code, so I have been thinking about what kind of data format to use for the maps. The old format I used was sort of lazy: 16x16 pixel metatiles in a flat table. This time I'd like to go for something better. If any of you have any thoughts on the topic, please share them.

Some design goals/constraints:

- Should be generic rather than limited. I don't mind losing a little bit in efficiency (in space and time) due to this. No object based formats like used in SMB1.
- Should work with multi-directional scrolling.
- Shouldn't needlessly limit artistic freedom (no "64 metatiles should be enough for everybody").
- Should be able to store a variety of extra info for tiles, such as 1) color attribute 2) slope type 3) collision flags
- Should not depend on extra cartridge RAM (but should be able to work with maps decompressed to WRAM).

There are so many options available I'm having hard time coming up with anything concrete, because I don't have a good grasp on the benefits/drawbacks of things such as:

- Metatile size (32x32 pixels? 16x16 pixels? Metatiles of metatiles?)
- Divide the map to screens of e.g. 256x256 pixels? (This seems like a good idea, so that sparse maps can be supported efficiently by having a map of screens. I guess "screen" here is really nothing but another name for a big metatile of metatiles.)
- Should attribute data be stored in metatiles, or should there be a separate map for them? Same goes for collision data. (Many, many options here. E.g. if we use 32x32 pixel metatiles which consist of 16x16 pixel metatiles, we could store attributes in the either metatile, or separated so that the same metatile could be used in two places with a different palette, for example).
- Maximum number of metatiles? 256 is a natural limitation to use here, but how likely are artists to run out of metatiles, say at the 16x16 pixel metatile level?

Existing solutions in games:

- Blaster Master apparently uses 256x256 pixel metatiles (screens), consisting of 64x64 pixel metatiles, consisting of 32x32 pixel metatiles, consisting of 16x16 pixel metatiles. I may have been misinterpreting the document I found, but it's something similar. The color attribute is associated with the 16x16 metatile.
- Gimmick uses 16x16 pixel metatiles. The whole map is stored more or less as is. The map is divided to screens, but the screens are not used to reduce redundancy. See my earlier post for some more info.
- Kirby uses 16x16 pixel metatiles and 256x192 pixel screens. Maps are stored compressed in ROM and decompressed to WRAM.
- <add your favorite game here>

Thoughts?

EDIT: Added an extra constraint about not requiring WRAM.

I once made an engine that did 8x8 blocks (quarter screen) of 16x16 tiles, and a big 16x16 map of those 8x8 blocks. I did sort-of RLE compression (either run lengths, or run lengths taken from one row above) on the 16x16 big map. This limits you to levels 2048x2048 pixels large.

Definitely divide into something large like screens. I divide into screens, but while typing up this post, I actually think 128x128 metatiles would be super cool.*

Definitely store attribute data with metatiles. (I don't think you'll have many metatiles that are identical except for their palette. Having a separate map would mean storing LOTS of redundant data whenever that's not true which is certainly the more common case.)
Definitely store collision info with metatiles. (Same as above. Is storing it separately likely to save you more space than having two of the same metatile with different collision info sometimes? Unless you mean define an arbitrary slope outside the metatiles so that multiple tiles can use it. In which case, yes, do that.)

As far as which metatile size gets this data, I'd say always the smallest one possible. You're likely to have larger (say... 32x32) metatiles that have very slightly different arrangements of smaller (say... 16x16 metatiles) metatiles. You only save space if each small metatile is used fewer than 4 times in the large ones.

- Maximum number of metatiles? 256 is a natural limitation to use here, but how likely are artists to run out of metatiles, say at the 16x16 pixel metatile level?

The artists should be willing to meet you halfway, here. I would not go out of my way to support more than 256 of anything. (Err... but to actually answer your question, pretty likely if they don't know a lot. They're even likely to run of regular 8x8 tiles, which I see a lot a lot a lot.)

I chose 32x32 metatiles as my second largest size, because you can fit 4 screens of them in a page of RAM. Having 512x512 pixels covered in RAM is super nice for a multidirectional scroller. I really, really recommend 32x32 tiles specifically, with some larger size to make it easy to seek through the level. (Screens or whatever)

*So... I'm currently using 256x256 screens made of 32x32 metatiles made of 16x16 metatiles. I did it so I could fit 4 screens in RAM as mentioned above. However I have a problem now dealing with objects/enemies moving offscreen. Because it's possible the screen boundary is one pixel away from loading two new screens. If an object is then thrown offscreen to the right, it will either A: Interact with collision data from the left two loaded screens which could result in weird behavior, or B: Immediately be destroyed.

I want some persistence off screen, but as it is now... it's very inconsistent persistence. You could throw an object a pixel off screen, and it might vanish. Or... it might stay there while you walk like 64 pixels away from it and come back.

128x128 metatiles allows you to never have that situation come up. And of course still keeping all the benefits 32x32 metatiles provide. (512x512 pixels covered in RAM.) I'm now seriously considering changing to this, but man... there's a lot of things I'd have to update everywhere... (But I guess it also limits my level size without keeping 256x256 metatiles as well. Currently I can do any level dimensions that don't exceed 256. 64x4 screens, 128x2, 256x1 85x3 1x256... or anything less).

I could post about how I store slopes or whatever if you want, but I'm not sure it helps with point 1. Generic. The thing to realize is that with metatiles everything is easily extendible. My 16x16 metatiles are 4 arrays of top left, top right etc. Need slope type? Add an array and a fifth byte. Need more info? Add it to the fifth byte. Out of space in the fifth byte? Add a sixth.

Kasumi wrote:Definitely store attribute data with metatiles. (I don't think you'll have many metatiles that are identical except for their palette. Having a separate map would mean storing LOTS of redundant data whenever that's not true which is certainly the more common case.)

Yeah I agree. This was actually my plan all along and what I've done in the past. I also haven't yet found a game which didn't do this. The reason I asked about it is that I talked with somebody (an artist) who disagreed, but he probably hadn't put much thought into it, or at least the technical ramifications of it. It probably wouldn't be terribly difficult to change the code to later on support this kind of scheme, if really needed (drop the data from the metatile data, load from a separate per-screen 2bpp bitmap).

Definitely store collision info with metatiles. (Same as above. Is storing it separately likely to save you more space than having two of the same metatile with different collision info sometimes? Unless you mean define an arbitrary slope outside the metatiles so that multiple tiles can use it. In which case, yes, do that.)

I guess the only counter-argument for that again is: do we want to save space, or to have as many graphically unique metatiles as possible? But yeah it's probably best stored in the metatile for a generic solution.

As far as which metatile size gets this data, I'd say always the smallest one possible. You're likely to have larger (say... 32x32) metatiles that have very slightly different arrangements of smaller (say... 16x16 metatiles) metatiles. You only save space if each small metatile is used fewer than 4 times in the large ones.

Yeah. As far as space savings go, it of course depends a lot on the data. I don't really have an intuition on which way would be better from that angle, but shoving all of it in the smallest metatiles seems like an easy way to go. I guess it shouldn't be that hard to change this later on, either.

Might be interesting to throw "raw" 16x16 pixel metatile data from some games into an utility that tries different combinations of metatile sizes to see which yield the best compression, and see how much variation there is.

- Maximum number of metatiles? 256 is a natural limitation to use here, but how likely are artists to run out of metatiles, say at the 16x16 pixel metatile level?

The artists should be willing to meet you halfway, here. I would not go out of my way to support more than 256 of anything. (Err... but to actually answer your question, pretty likely if they don't know a lot. They're even likely to run of regular 8x8 tiles, which I see a lot a lot a lot.)

Yeah, I guess. The 8x8 tile limit is easier, because no need to make a choice there (other than whether to use MMC5 or not.) And I wouldn't want to work with an artist who wasn't willing to make him or herself aware of that limitation.

I chose 32x32 metatiles as my second largest size, because you can fit 4 screens of them in a page of RAM. Having 512x512 pixels covered in RAM is super nice for a multidirectional scroller. I really, really recommend 32x32 tiles specifically, with some larger size to make it easy to seek through the level. (Screens or whatever)

Why do you have the map in RAM? Do you decompress it there, or load it dynamically, or something? What do you mean when you say you "load new screens"? Personally I was planning to keep the map data in ROM (or at least allow an option of doing so.)

I'm now seriously considering changing to this, but man... there's a lot of things I'd have to update everywhere...

This is what I'm afraid of, so I want to make at least somewhat informed decisions.

Thanks for the reply, I was afraid I was going to have to do a monologue on this one. Looks like most of what you say align with what I've been thinking. And in the end, many of the differences between different methods are fairly small, so might as well just pick one and run with it.

thefox wrote:Metatiles of metatiles?

Always my first choice!

I guess "screen" here is really nothing but another name for a big metatile of metatiles.

Exactly. I have metatiles all the way from 16x16 to 256x256 (going through 32x32, 64x64 and 128x128), which are the ones that are actually used in the level map. Sound crazy, but is really compact. I even considered sharing the structures across all metatiles, since they're all just arrays of 2x2 bytes no matter their size, to save even more data. That would have made the encoder insanely complex, so I never got to try this.

To decompress the map, I first locate the specific 256x256 block I'll read from, and from there I use a set of pointers that I modify in ZP. Depending on the corner of the metatile I'm reading (which is specified by bits from the coordinates), I modify the pointers to point to the specific corner, and then it's just a matter of loading an index and moving on to the next pointer, until I reach the smallest block. Sounds slow, but it's not too bad. If you had lots of RAM you could decompress larger sections progressively instead of doing it the crazy way.

Should attribute data be stored in metatiles, or should there be a separate map for them? Same goes for collision data.

I prefer to store attributes (and I really mean all attributes, not only the palette bits that the NES calls attributes) in the smallest metatile (16x16), but the collision maps are in a separate table, and are indexed in the metatiles. I have 2 sets of collision data per metatile, in order to simulate two layers in my level maps. Triggers cause the objects to switch layers.

256 is a natural limitation to use here, but how likely are artists to run out of metatiles, say at the 16x16 pixel metatile level?

I usually go with 256 because it's much simpler/faster to work with bytes. If you need more than that, the best option would probably be to store them in RAM and replace them progressively as the level is played.

Why do you have the map in RAM? Do you decompress it there, or load it dynamically, or something? What do you mean when you say you "load new screens"?

I have the map partially in RAM mainly because the screens are compressed in a way that doesn't allow random access, yeah. (Not sure if that means they're no longer considered metatiles. If so, my bad for calling them that.) I'd have to decompress for every collision if I didn't keep them in RAM somehow. They're also compressed in a way that's limited (against point 1.), so I didn't mention it.

A map in RAM is also cool if you have some destructibility. You only have to change the state of a tile once when you load it, rather than check if it's solid every single time an object needs to collide with it.

Basically when high byte of the scroll changes, I decompress the two screens that have just appeared to the 128 bytes that just moved offscreen. See GIF:

To change to 128x128 metatiles, I'd need to change what updates this RAM. (And how objects are created when scrolled onto the screen.) Tile drawing and collision detection both read from this RAM to get the 32x32 metatile numbers, so the first change would fix those for free. (This is also why offscreen objects may collide with the wrong things, which wouldn't be a problem with an only ROM approach.) I mainly worry about updating the tool I use to create the maps. That's where I'd have to change things everywhere.

Personally I was planning to keep the map data in ROM (or at least allow an option of doing so.)

There's nothing wrong with this at all. I thought there were more benefits to the map in RAM, but now that I think about it...

Thanks for the reply, I was afraid I was going to have to do a monologue on this one.

Any time. Not like my game will ever come out anyway, may as well share the thoughts.

You might need 'Tile Destroyed' flags, such as for collecting coins, already hit question blocks, blowing up walls, etc.
One way I've thought of doing it is to use a big map that corresponds directly to 8x8 areas of the map. It would have numbers in it, such as FF for nothing destroyable, otherwise it would have a unique number for each area containing destructible tiles, think of them as 'cell numbers'. This does not necessarily need to be in RAM, it could be in ROM.
Then you have the tiles destroyed bits, 8 bytes total per 'cell number', this is just the 64 bits of flags for whether tiles are destroyed or not.
Use a table to map a metatile to a 'destroyed' metatile.

thefox wrote:- Should be generic rather than limited. I don't mind losing a little bit in efficiency (in space and time) due to this. No object based formats like used in SMB1.

What's wrong in general with an object-based format?

Kasumi wrote:A map in RAM is also cool if you have some destructibility. You only have to change the state of a tile once when you load it, rather than check if it's solid every single time an object needs to collide with it.

In a 2-way scroller like SMB2, if you're not going to have destructible objects above destructible objects, you could always use a single destruction bit per column.

Kasumi wrote:I have the map partially in RAM mainly because the screens are compressed in a way that doesn't allow random access, yeah. (Not sure if that means they're no longer considered metatiles. If so, my bad for calling them that.)

Understood. I think they should still be called metatiles, this method just caught me by surprise since I haven't heard of it before. The first thing that most people would probably think would be that decompressing entire screens while the game was running would be too slow, or at least make for an uneven processing load per frame.

A map in RAM is also cool if you have some destructibility. You only have to change the state of a tile once when you load it, rather than check if it's solid every single time an object needs to collide with it.

Definitely. I hadn't even thought of the option of storing only a partial view of the map in RAM (when using a big map), although I probably won't do it because it seems complicated.

Tile drawing and collision detection both read from this RAM to get the 32x32 metatile numbers, so the first change would fix those for free. (This is also why offscreen objects may collide with the wrong things, which wouldn't be a problem with an only ROM approach.)

Yeah, I had this same problem in STREEMERZ initially. I stored only the visible portion of the map in RAM, until I realized that the player should be able to interact with the walls of the upper/lower room during transitions. Since I wanted to make it behave the same way as the original, I had no option but to modify the code to load an additional couple of tile rows at the top and the bottom of the room. Of course this is not an option with a big map.

Thanks for the reply, I was afraid I was going to have to do a monologue on this one.

Any time. Not like my game will ever come out anyway, may as well share the thoughts.

I guess many of us here are in the same boat. I have actually realized I like working on engines more than I like working on games, so I'm not going to stress about getting anything complete out of this.

Dwedit wrote:One way I've thought of doing it is to use a big map that corresponds directly to 8x8 areas of the map.

I want to go on a record to say that it can be really confusing when people talk about "8x8 areas" and don't specify what unit they use (pixels? metatiles? megatiles? inches?). I assume you meant metatiles here. This is why I used pixels all over the place in the original post in case anybody was wondering. Still, thanks for the thought on destroyable terrain!

tepples wrote:

thefox wrote:- Should be generic rather than limited. I don't mind losing a little bit in efficiency (in space and time) due to this. No object based formats like used in SMB1.

What's wrong in general with an object-based format?

I didn't say anything was wrong with it. I said it's not a generic format, at least I think most people would feel limited by it.

Dwedit wrote:You might need 'Tile Destroyed' flags, such as for collecting coins, already hit question blocks, blowing up walls, etc.

I like to implement all of those as actual objects, not part of the level map. Whenever the camera scrolls, the background objects check for overlaps between themselves and new rows/columns, and "patch" the row/column with their own tiles. This allows breakable/removable blocks to have actual graphics behind them, as apposed to just blank space. Plus, I like that the level map is just the static part, and everything you can interact with is an object.

Objects might have permanent state bits assigned to them, so level deformation is possible, as long as the number of removable blocks isn't insanely high to the point where the CPU will have trouble dealing with so many objects or there won't be enough RAM to remember all the states.

Disclaimer: rambling.

thefox wrote:- Should be generic rather than limited.

Unfortunately, the preferred structure of data owes a good deal to its nature. I found reading about the MIDI format (and the superclass it owes its structure to, Interchange File Formats) to be fascinating; it seems relevant. Of course, 4 bytes for chunk-identification is likely going to be massive overkill for storing level data, but there are benefits to conforming to standards: (partial) compatibility, even if you don't understand every chunk, is feasible as the sizeof field allows you to simply discard unknowns. The non-mandatory nature of chunks suggests to me, one might have 'default' collision data for a metatile, and on occasion have a chunk added to a metatile saying "no, use this collision instead". Similarly, one might have a "this metatile relies on this memory data"; if one is not making a geomod-fanatic game, this is going to be present in relatively fewer tiles...except for the obvious case of collectibles. A simliar (possibly the same, possibly different, depending on implementation) would be one depending on saved (password/SRAM/etc.) data.

Variable-length quantities, like how MIDI does for time-deltas (summary: sign bit of a byte is "is there another byte to this number") are a simple way of providing extreme extensibility (and, if incautious, buffer overflows) to fields.

The problem with this is that often, map-proximate tiles are going to be source-proximate, so you'll have a lot of data redundancy if you do this on a per-tile basis. One could instead specify the first (meta)tile as absolute, and for other (meta)tiles within the (meta)tile, only specify the relative address or lower byte(s), in similar fashion, using VLQs for the subsequent ones.

On the crazy side, there will never be a time when you need more than 18 bytes to select a graphical 8px*8px tile on the NES. (16 bytes for the tile, 2 bytes for "ridiculous-mapper" per-8x1-sliver attribute).

Attributes should probably be per-32*32px metatile under normal circumstances; this makes it easy to copy into the PPU attribute tables.

Collision being stored separately to graphics, and at which level? There are two obvious NES-like cases where you want them disparate (illusionary/invisible walls/structures) as well as for "foreground".

A truly-universal object would just be a function pointer "run this when this scrolls in", leaving further determination in said code. Obvious extensions are a "dead" or status flag to say when (/not) to run it again. One could store palette changes in this fashion, with a batch at the start of the level to initialize them.

If you are doing a "net-of-screens(~256*256px(240?) metatiles)" approach, then one thought is that one might wish to is that one might wish to be able to change the direction of the coordinate system of said 'screen's, so as to more easily be able to extend the level forward. The one UR-scrolling level in SMB3 would have +y be up rather than down, in this thought...but you're likely to not have any need for this sort of affair if you are creating your own tools to produce the data.

Sources: the MIDI Technical Fanatic's Brainwashing Center (mirror)

Myask wrote:Disclaimer: rambling.

Now, something like this is too generic for my purposes. And it would destroy performance.

Myask wrote:Attributes should probably be per-32*32px metatile under normal circumstances; this makes it easy to copy into the PPU attribute tables.

Unless you scroll vertically, in which case blocks in every other screen are misaligned to the attribute grid, and will require you to do some bit shuffling in order to form the attribute bytes. Another factor is that if you're using 8 or 4-way scrolling without extra name table RAM on the cartridge, one of the axes will not have 32 continuous pixels you can modify at once without causing glitches on the opposite side of the screen, so you will have to break up the bits anyway.

True...unless one is using nametable-size "screens" so the cuts on the half-metatiles are already in-place.

Myask wrote:unless one is using nametable-size "screens" so the cuts on the half-metatiles are already in-place.

True for the misalignment, but the 4/8-way scrolling and the lack of space to put the scrolling seam still applies.

Still, I kinda like the idea of assigning attributes to the 32x32-pixel blocks, even if some bit shifting is necessary.