Map data and compression for scrollable map?

[CrashTest]

Just curious, what are you doing to store your in game level maps?
Do you have separate collision detection data and character data?
Do you have special data to tell where enemies spawn from?
Did you make your own map editing tools?

For me I'm just using a tileset of up to 4x4 tiles, with one attribute byte per tile set. The map is just a 2d array of tile indices so a map that is 8x9 screens is about 4k for the map, and 4.25k for the tiles+att if I define all 256 of them

Different ranges of my character set define their usage e.g. solid, platform, wall, empty, ladder, etc.

For collision detection I'm debating mirroring the nametable in 1k of work ram (MMC3) as a quick lookup table, since I'll need to test against object against background quite a bit. I can copying into this temporary ram buffer, outside of vblank also.

Also, since I can copy from this buffer to the name table more efficiently, it will take less time in the vblank.

[Celius]

For my game, which contains one giant map like Metroid and the non-stage based Castlevania games, I will hold a map that points to rooms, and those rooms will point to screens. There are 1024 different possible screens, and each screen is made up of 16 8x8 tiles. Each screen is 256x256 pixels. Each 8x8 tile is made up of 4 4x4 tiles, which are made up of 4 2x2 tiles, which are made up of 4 1x1 tiles. There are 256 different 8x8, 4x4, 2x2, and 1x1 tiles. I can swap different stacks of tile definitions to make more interesting/different areas.

I plan to have different ranges in my 2x2 metatile defs to represent different tile types, like solids or solid diagonals, etc.

I haven't quite figured out the exact format of the whole map, but I know there is a 16k bank full of the different metatile definitions, 16k for the screen definitions, and I'm sure a bank or so for the room definitions.

For collision detection, I plan to have a copy of the screen in RAM that's 16x16 metatiles big, and it'll be easy to do detection here. But this is something that has always concerned me, as there are objects off screen that sometimes I want to remain active, and they can't act properly if they don't collide with anything.

To spawn enemies, I load all of them as I enter a room. They all have 16-bit X/Y coordinates, and they are always somewhat active. When they are killed, they are removed from existence so there are no annoying respawns.

I plan to make my own map editor in Visual Basic, but I haven't gotten around to it yet. I need to make this as typing in levels is a nightmare.

[Banshaku]

That's a good question. I'm searching on the subject at the moment. Since my project is still not that far, I put that part on hold until I figure out other things about the nes.

I'm planning to write my own map editor in c# since there is no generic one that I can easily use. I'm already able to load the CHR-DATA but now I need to create the editor itself. After that the format of the data, which I'm in the same situation as you (i.e. I don't know how to approach it yet).

Once I find the right format and can make my editor, it will be quite useful. I would love to be able to make a generic one so other people could benefit from it.

[tokumaru]

please think of Sonic games while you read this.

Just curious, what are you doing to store your in game level maps?

The basic building blocks are the metatiles (256 of them per zone), they have 2x2 tiles, a palette index (0 to 3), a type (solid, empty, platform, water, etc), a height map (the height of each pixel column) and an angle.

Then the crazy compression starts: The 16x16-pixel blocks can't be directly placed in the level. They are used to form 256 32x32-pixel blocks. Those are combined to form 256 64x64-pixel blocks. Those are combined to form 256 128x128-pixel blocks. Those are combined to form 256 256x256-pixel blocks, which can be directly placed in the level map.

This is so compact that the levels can be really huge, with up to 1536 256x256-pixel blocks (such as 128x12 blocks, or 32768x3072 pixels), although there must be a decent level of block reuse for it to work well (not hard in a platformer, would suck for RPG). Looks complicated, but the code that decompresses blocks is very efficient, so it's possible to read any 16x16-pixel block from the level without having to decompress anything to RAM.

Do you have separate collision detection data and character data?

These are both attributes of the 16x16-pixel blocks.

Do you have special data to tell where enemies spawn from?

My object definitions are completely separated from the level map, so that the blocks can be reused across different levels. Each object in the list has the following information: type, coordinates and an extra parameter (which each type of object uses differently). Having the objects separate from the map even allows for some layering effects, because the objects can draw tiles on top of the level map, making the basic blocks more unique, and not so obvious they are reused so much.

Did you make your own map editing tools?

It would be next to impossible to encode my maps like that by hand, so I made a command line utility that creates all the intermediary blocks based on images of the level I want to create and an image that contains all 16x16-pixel blocks. It builds a dictionary of blocks based on that image and then tries to recognize the blocks in the other images, creating all the intermediate blocks in the process. When finished, it reports back how many of each type of block was used, so that I know when I need to start repeating stuff more often.

[clueless]

I have not changed my game rendering code yet, but I have decided upon a map compression scheme. As with everything else, it is subject to change at any time.

I'm still writing the 'C' utility that will convert PNG files into compressed map data. Documentation on the map format are here [1] and the source code to the compressor program is here [2].

In the end, I suspect that each of us will implement whatever is the most efficient for our game engine to decompress and display based on our game's requirements.

I plan to decompress map to metatiles in SRAM while the PPU is drawing the screen and then convert metatiles into PPU tiles during VBLANK. If that does not work, I'll fully decompress the map section into PPU tiles during PPU rendering and blit the required columns and rows into the PPU during VBLANK. I haven't gotten that far yet.

[1] https://www.ecoligames.com/svn/nes-game/trunk/NOTES.txt

[2] https://www.ecoligames.com/svn/nes-game ... map-maker/

[doynax]

In my current 6502 game project, a single-directionally scrolling shoot'em up, I've tried to make things as simple as possible for the artist. That is I've got a tool which takes one big bitmap and spits out individual tile indices and attributes, and packs them using general-purpose LZ compression. Furthermore the tileset isn't fixed but is refilled automatically as the level scrolls (though that feature is still buggy.)
The idea here is that my potential level designer shouldn't have to deal with funky tilemap editors, meta-tiles or budgeting tilesets. That's not to say that you can ever forget about tiles and palettes, but I'm hoping that minimizing the amount of arbitrary limitations and being able to use standard tools will pay off in the end.
Oh, and since it's a vertical shoot'em up the background is purely decorative.

On the other hand the actual level script, that is a time-line primarily controlling how the enemies are spawned, is very simple. There are no reused formations, or run-time scripting, or even an editor. Just a bunch of commands of the form 'spawn enemy of class A at point B', 'wait C ticks' or 'start effect D', as generated by macros through the normal assembler (thus giving you access to the assemblers somewhat clunky preprocessor facilities for compile-time scripting.) The one nice thing about it is that it's all embedded into the same LZ-compressed stream as the backgrounds, so you don't have to pay much attention to the size of the script.

Frankly I've been looking to co-opt some sort of visual editor for laying out the enemies. Any ideas? All I really need is to be able to place enemies (represented by some bitmap for each class) over the level bitmap and set the attributes controlling their behavior, plus a margin or something for miscellaneous commands. Being able to test play the current section of the level at the press of a button would be nice too.

[Bregalad]

I like having 32x32 pixels "blocks", themselves made by 4 16x16 pixels "metatiles", themselves made of 4 tiles plus color/collision information.

The day I'm making a RPG or sRPG I'll probably directly code my maps with 16x16 metatiles tough for more flexibility (until I'd come with really large characters and all).

[Memblers]

Here's my level editor, it's not finished because I haven't needed it yet. It would save to WRAM and/or controller port (XMODEM). It should be able to save now, but it doesn't load.

http://www.parodius.com/~memblers/nes/editron/

[Dwedit]

Having a lot of experience in Romhacking made me immediately implement map compression on my first real ASM program. I used 4-bit RLE just like Dragon Warrior.

[doynax]

Having a lot of experience in Romhacking made me immediately implement map compression on my first real ASM program. I used 4-bit RLE just like Dragon Warrior.

I'm not familiar with how Dragon Warrior handles this. How do you scroll around within a compressed map efficiently?

[tepples]

I'd imagine that these RPGs that use RLE maps decode a row of tiles at a time and keep them in a buffer.

[Dwedit]

Dragon Warrior in addition to the RLE compressed map data also stored a lookup table which maps between rows and the start address of each row.
So you have random access to rows, and sequential access within a row.

Dragon Warrior 4 took it one step further, and split the map vertically down the middle, so there is random access to either the first or second half of a row, presumably because DW4 needed more CPU time in the overworld than the other games.

Only DW1 had RLE runs extending beyond the boundaries of a row, that was so they could have water on the right side of a map, and save a byte by using longer water on the left side of the next row.


DW1's map format:

Code: Select all

xxxx.... = tile number
....xxxx = length

Zelda 2 almost uses the exact same format for the overworld, just with the nibbles swapped.

[doynax]

That seems rather inefficient though. Scrolling involves decompressing up to N screens of data (where N width of the level) and storing the start pointers eats up precious bytes, especially considering the generally meager RLE savings.
I suppose it could be sped up with various techniques. For instance the pointer table could be generated at runtime when first entering a region. A buffer of a couple of columns could be stored on the sides of the screen, shifted horizontally relative to each other, such that you only need to decode a subset of the rows when scrolling.

But to be honest I don't see why they didn't just unpack the whole thing into memory using better compression schemes, kind of like SMB3 except with Exomizer or something instead of that funky 'vector' format. Or at least store the entire columns as tepples suggests. After all a few save games couldn't use up much of the SRAM, right?

DW1's map format:

Code: Select all

xxxx.... = tile number
....xxxx = length

Zelda 2 almost uses the exact same format for the overworld, just with the nibbles swapped.

Wait, you mean there's only 16 tiles in a map?

[Bregalad]

I guess it's 16 metatiles. The overworld is very simple graphically in Dragon Warrior games, altough very large.
I also use a similar format for my game, but can allow up to 32 metatiles (using 5 bits) and only runs up to 8 of the same metatile (using 3 bits).
I have random acess because I place everything in RAM (I only have 1 screen loaded at a time). I guess RPGs uses SRAM to do this, but definitely not Dragon Warrior 1&2, because they originally were without SRAM in Japan.

[clueless]

https://www.ecoligames.com/svn/FariaEdi ... rWorld.cpp

Faria uses RLE, but with three different types of runs:

1) The three most common runs of metatiles (water, grass, forest) can have runs of 2 to 17 metatiles. Bit pattern is 0x11mmcccc (m = metatile index into lookup array and c = count - 2)

2) Then there are 8 lesser types (generally horizontal boundaries between grass and other terrain types). These runs can be from 2 to 9 in count. Bit pattern is 0x10mmmccc.

3) Other metatiles don't have repeat count. This is also how one would represent a single water tile. Bit pattern is %0mmmmmmm.

The overworld is 128x128 metatiles, and compresses down to 7443 bytes in size. Uncompressed it would be 16K. There are a possible 128 metatiles, but only about 120 are actually used.

The skyworld and cave world are not RLE compressed. There are only 4 possible map tiles in each, so those maps are just stored as 4 metatiles per byte.

And I disagree that RLE compression doesn't compress enough. It is enough to fit the entire overworld into a single MMC1 or MMC3 PROG-ROM bank. That makes decompression significantly easier (and faster) to implement. Typical MMC1 bank switching (LSR, STA 5 times) requires 2*(2+4) + jsr + rts = (too lazy to add it up) many CPU cycles.

Not shown in the ROM editor is another fact, Faria does decompress the visible portion of the overworld into temp space. It will decompress rows as needed as you scroll north and south. I don't remember if it buffers a off-screen few tiles in the east/west direction or not. If it doesn't, it would need to decompress 15 rows each time you move east or west.