Forums

Spent the evening getting smooth scrolling in all four directions, but I realized I'm making some early optimizations on how I'm storing my map, since I'm only moving the BG tiles at this point. I'd like to get some input on how to best layout a map file, considering the following:

* It seems smart to put the BG map in a nice, linear fashion for faster lookup when filling in offscreen tiles. Obviously this eats up the ROM like nobody's business, especially when a tile might have to be represented by two bytes (either for tile index > 255, or for meta data such as horizontal/vertical flipping)
* Collision would also be nice to embed into a map. One alternative there is to tie collision to each tile index, which forces re-use of tiles (or at least some level of lookup indirection). Given that a collision map would normally utilize a lot of repeating data, it seems ripe for RLE, but that isn't always practical for runtime lookup of arbitrary position.
* Speaking of collision, what methods are people using for this? Primitives (0 = none, 1 = 8x8 square, 2 = sloping triangle, etc.) are one option, as are flags on top/bottom/left/right
* Finally, there's actor placement and management. How to embed those into the map data? A separate segment seems wise here.

I'd like to hear some suggestions for the above. I'm figuring I could probably use a small buffer of RAM to hold the current map "chunk", but that also feels a little wasteful.

I'm simply tinkering with this to learn the hardware, but ultimately I think I'd like to do an action/platformer, so keep that in mind.

Most games use a "metatile" system, whereby you pick a block size (e.g. 16x16, 32x32), then define your map in terms of these. You then have lookup tables that determine the tile data, and collision data, for these metatiles.

The level data itself is typically stored compressed (if only RLE) due to the cost of ROM. Sonic 1, for example, decompresses its levels into the first 4KB of RAM. Some later SMS games included 8KB of on-cart RAM for this purpose.

SavagePencil wrote

* Speaking of collision, what methods are people using for this? Primitives (0 = none, 1 = 8x8 square, 2 = sloping triangle, etc.) are one option, as are flags on top/bottom/left/right

Most 8-bit era games just used rectangles. Depending on the context, you can do something more clever; for example, for my "ono" game I implemented circle collision detection with lookup tables for squaring integers; for "RC Grand Prix" there were half-res "bitmaps" in ROM.

SavagePencil wrote

* Finally, there's actor placement and management. How to embed those into the map data? A separate segment seems wise here.

I'd guess that's the way to go. It's going to be very sparse compared to the map data. If the whole map is in RAM, you can even have them active when off-screen. An alternative is to reserve some map bits for the actors.

Quote

* It seems smart to put the BG map in a nice, linear fashion for faster lookup when filling in offscreen tiles. Obviously this eats up the ROM like nobody's business, especially when a tile might have to be represented by two bytes (either for tile index > 255, or for meta data such as horizontal/vertical flipping)

I'll explain what the arcade version of Shinobi does because it is a pretty nice method for encoding very large backgrounds.

The background is defined in 4x4 tile units. This could be any size, 2x2 might be better for the SMS. Each unit is represented by a byte, so the map is a linear array of bytes like you mentioned.

The byte is an index into a table which stores information for the 4x4 unit:

- Palette number
- Priority value
- Another index byte
- Padding (to simplify calculating the offset in the list)

The second index byte looks up a list of raw tile numbers that define each 4x4 tile group, and they include the flip-flags.

Now the advantage is that two unit entries can point to the same 4x4 tile group, but have different palette or priority values. So you could re-use an object like a wooden box, but make one a different color or appear in front of the sprites. You could expand this to move the flip flags as a global attribute, though in arcade games you usually have tons of tiles so storing flipped copies is no big deal.

In the end the maps were quite compact, an entire 512x256 screen is just 128 bytes, a level map needs 1K to define the 4x4 tile unit attributes and 8K to define the tile numbers themselves. Both of these tables fit in ROM and the 8K list was big enough to store tile definitions for the entire game (!).

If you need less tile units, you can go down from 256 to 128, etc. And these tables can be changed at runtime as new elements are brought in, in case you are running up against any limits.

What Zillion does is to RLE encode vertical columns of background data that are wide (I think 4x24 or 8x24?) and decompress those to RAM, then copy strips of the column to VRAM as the screen scrolls. It keeps the current and previous columns in memory so a worst-case scenario of moving between two areas doesn't force a copy-and-decompress each time.

Quote

* Collision would also be nice to embed into a map. One alternative there is to tie collision to each tile index, which forces re-use of tiles (or at least some level of lookup indirection). Given that a collision map would normally utilize a lot of repeating data, it seems ripe for RLE, but that isn't always practical for runtime lookup of arbitrary position.

This is probably not ideal, but Wonder Boy in Monster Land uses the spare 3 bits per tile to encode collision data, and then reads from VRAM to check collisions with adjacent tiles.

Oh duh, that's a brilliant optimization. At 2x2 or 4x4 that's a huge optimization by chunking it together, with each chunk having relevant metadata associated with it.

I had already thought of listing the map data horizontally or vertically (depending on what would be done more for the level), but this helps a lot.

Dumb question: do the sprite collision flags tell you when the *rectangle* collided, or when a non-clear bit overlapped? I've seen it done both ways by other hardware.

Thanks, both of you!

The sprite collision flag is for the opaque pixels, but it is generally unhelpful because it is for any two sprites, so for example overlapping enemies or the player collecting a powerup would trigger it.

Yeah, I can totally see the limitations of that.

As the creator of the game aren't you also in control of the cartridge design and thus how much ROM/RAM it can use? I wouldn't be afraid to use up plenty of either because the CPU is relatively slow but storage is cheap. The more you can offload the better the gameplay can be. ;)

In theory, yes; although you might choose to limit yourself to configurations supported by emulators and existing flashcarts, i.e. Sega mapper, max 32K RAM, max 1MB ROM. In practice, while I don't worry too much about it, I prefer to use compression rather than ship bloated ROMs. A single full-screen graphic can be ~12KB, which (combined with the need to pack into 16KB slots) uses the space up very quickly.

SavagePencil wrote

Oh duh, that's a brilliant optimization. At 2x2 or 4x4 that's a huge optimization by chunking it together, with each chunk having relevant metadata associated with it.

I think it should be common behavior to use several levels of indexed dictionnaries like that. Psycho Fox has 6 levels of indirection for compression. You can add metadata at any level to create data variations and still reuse bits.
In Psycho Fox: 1 level is a list of screen, each screen refers to 2 half-screens, each half-screen refers to 2 quarter-screens, each quarter-screen refers to 8 vertical strips of 16x16 metatiles, each metatiles refers to 4 tiles. Makes the whole thing well packed.
( http://smspower.org/forums/viewtopic.php?t=11300 )

Author	Message
SavagePencil Joined: 23 Aug 2009 Posts: 213 Location: Seattle, WA	Formatting levels (BG, actors, metadata, and collision)... Posted: Thu Sep 03, 2009 3:45 pm
	Spent the evening getting smooth scrolling in all four directions, but I realized I'm making some early optimizations on how I'm storing my map, since I'm only moving the BG tiles at this point. I'd like to get some input on how to best layout a map file, considering the following: * It seems smart to put the BG map in a nice, linear fashion for faster lookup when filling in offscreen tiles. Obviously this eats up the ROM like nobody's business, especially when a tile might have to be represented by two bytes (either for tile index > 255, or for meta data such as horizontal/vertical flipping) * Collision would also be nice to embed into a map. One alternative there is to tie collision to each tile index, which forces re-use of tiles (or at least some level of lookup indirection). Given that a collision map would normally utilize a lot of repeating data, it seems ripe for RLE, but that isn't always practical for runtime lookup of arbitrary position. * Speaking of collision, what methods are people using for this? Primitives (0 = none, 1 = 8x8 square, 2 = sloping triangle, etc.) are one option, as are flags on top/bottom/left/right * Finally, there's actor placement and management. How to embed those into the map data? A separate segment seems wise here. I'd like to hear some suggestions for the above. I'm figuring I could probably use a small buffer of RAM to hold the current map "chunk", but that also feels a little wasteful. I'm simply tinkering with this to learn the hardware, but ultimately I think I'd like to do an action/platformer, so keep that in mind.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14759 Location: London	Posted: Thu Sep 03, 2009 4:16 pm
	Most games use a "metatile" system, whereby you pick a block size (e.g. 16x16, 32x32), then define your map in terms of these. You then have lookup tables that determine the tile data, and collision data, for these metatiles. The level data itself is typically stored compressed (if only RLE) due to the cost of ROM. Sonic 1, for example, decompresses its levels into the first 4KB of RAM. Some later SMS games included 8KB of on-cart RAM for this purpose. SavagePencil wrote * Speaking of collision, what methods are people using for this? Primitives (0 = none, 1 = 8x8 square, 2 = sloping triangle, etc.) are one option, as are flags on top/bottom/left/right Most 8-bit era games just used rectangles. Depending on the context, you can do something more clever; for example, for my "ono" game I implemented circle collision detection with lookup tables for squaring integers; for "RC Grand Prix" there were half-res "bitmaps" in ROM. SavagePencil wrote * Finally, there's actor placement and management. How to embed those into the map data? A separate segment seems wise here. I'd guess that's the way to go. It's going to be very sparse compared to the map data. If the whole map is in RAM, you can even have them active when off-screen. An alternative is to reserve some map bits for the actors.

Charles MacDonald Joined: 28 Sep 1999 Posts: 1197	Posted: Thu Sep 03, 2009 4:34 pm
Charles MacDonald Joined: 28 Sep 1999 Posts: 1197	Quote * It seems smart to put the BG map in a nice, linear fashion for faster lookup when filling in offscreen tiles. Obviously this eats up the ROM like nobody's business, especially when a tile might have to be represented by two bytes (either for tile index > 255, or for meta data such as horizontal/vertical flipping) I'll explain what the arcade version of Shinobi does because it is a pretty nice method for encoding very large backgrounds. The background is defined in 4x4 tile units. This could be any size, 2x2 might be better for the SMS. Each unit is represented by a byte, so the map is a linear array of bytes like you mentioned. The byte is an index into a table which stores information for the 4x4 unit: - Palette number - Priority value - Another index byte - Padding (to simplify calculating the offset in the list) The second index byte looks up a list of raw tile numbers that define each 4x4 tile group, and they include the flip-flags. Now the advantage is that two unit entries can point to the same 4x4 tile group, but have different palette or priority values. So you could re-use an object like a wooden box, but make one a different color or appear in front of the sprites. You could expand this to move the flip flags as a global attribute, though in arcade games you usually have tons of tiles so storing flipped copies is no big deal. In the end the maps were quite compact, an entire 512x256 screen is just 128 bytes, a level map needs 1K to define the 4x4 tile unit attributes and 8K to define the tile numbers themselves. Both of these tables fit in ROM and the 8K list was big enough to store tile definitions for the entire game (!). If you need less tile units, you can go down from 256 to 128, etc. And these tables can be changed at runtime as new elements are brought in, in case you are running up against any limits. What Zillion does is to RLE encode vertical columns of background data that are wide (I think 4x24 or 8x24?) and decompress those to RAM, then copy strips of the column to VRAM as the screen scrolls. It keeps the current and previous columns in memory so a worst-case scenario of moving between two areas doesn't force a copy-and-decompress each time. Quote * Collision would also be nice to embed into a map. One alternative there is to tie collision to each tile index, which forces re-use of tiles (or at least some level of lookup indirection). Given that a collision map would normally utilize a lot of repeating data, it seems ripe for RLE, but that isn't always practical for runtime lookup of arbitrary position. This is probably not ideal, but Wonder Boy in Monster Land uses the spare 3 bits per tile to encode collision data, and then reads from VRAM to check collisions with adjacent tiles.

SavagePencil Joined: 23 Aug 2009 Posts: 213 Location: Seattle, WA	Posted: Thu Sep 03, 2009 4:44 pm
	Oh duh, that's a brilliant optimization. At 2x2 or 4x4 that's a huge optimization by chunking it together, with each chunk having relevant metadata associated with it. I had already thought of listing the map data horizontally or vertically (depending on what would be done more for the level), but this helps a lot. Dumb question: do the sprite collision flags tell you when the rectangle collided, or when a non-clear bit overlapped? I've seen it done both ways by other hardware. Thanks, both of you!

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14759 Location: London	Posted: Thu Sep 03, 2009 4:54 pm
	The sprite collision flag is for the opaque pixels, but it is generally unhelpful because it is for any two sprites, so for example overlapping enemies or the player collecting a powerup would trigger it.

SavagePencil Joined: 23 Aug 2009 Posts: 213 Location: Seattle, WA	Posted: Thu Sep 03, 2009 6:06 pm
	Yeah, I can totally see the limitations of that.

PoorAussie Joined: 26 Aug 2008 Posts: 292 Location: Australia	Posted: Fri Sep 04, 2009 12:03 am
	As the creator of the game aren't you also in control of the cartridge design and thus how much ROM/RAM it can use? I wouldn't be afraid to use up plenty of either because the CPU is relatively slow but storage is cheap. The more you can offload the better the gameplay can be. ;)

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14759 Location: London	Posted: Fri Sep 04, 2009 6:48 am
	In theory, yes; although you might choose to limit yourself to configurations supported by emulators and existing flashcarts, i.e. Sega mapper, max 32K RAM, max 1MB ROM. In practice, while I don't worry too much about it, I prefer to use compression rather than ship bloated ROMs. A single full-screen graphic can be ~12KB, which (combined with the need to pack into 16KB slots) uses the space up very quickly.

Bock Site Admin Joined: 08 Jul 2001 Posts: 8663 Location: Paris, France	Posted: Fri Sep 04, 2009 11:42 am
	SavagePencil wrote Oh duh, that's a brilliant optimization. At 2x2 or 4x4 that's a huge optimization by chunking it together, with each chunk having relevant metadata associated with it. I think it should be common behavior to use several levels of indexed dictionnaries like that. Psycho Fox has 6 levels of indirection for compression. You can add metadata at any level to create data variations and still reuse bits. In Psycho Fox: 1 level is a list of screen, each screen refers to 2 half-screens, each half-screen refers to 2 quarter-screens, each quarter-screen refers to 8 vertical strips of 16x16 metatiles, each metatiles refers to 4 tiles. Makes the whole thing well packed. ( http://smspower.org/forums/viewtopic.php?t=11300 )

Forums

View topic - Formatting levels (BG, actors, metadata, and collision)...