Level data storage

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Level data storage

Post by DRW »

Since I'm not sure whether the way I intend to store the level data for my next game is efficient enough, I wanted to ask whether there is any known information of specific games and the way they store their levels.

Since my game will be a top-down, screen-by-screen-scrolling game, "The Legend of Zelda" seems to be the most straightforward example for comparison:

How is, for example, the overworld stored in ROM? Do they save two bytes (x/y and meta tile) for each and every 16 x 16 tile on the screen or do they have other ways of doing this?

I assume they don't save 16 x 11 bytes for every screen to store every 16 x 16 area uncompressed.

Also, the color values: Do they save the whole palette indices for each screen separately (i.e. in case the programmer changes the position of an object, he also has to remember to change the palette data)? Or do they actually generate the colors from the meta tiles (like in: At position 7,4 there is a tree, so we write the palette index for a tree into the memory location that corresponds with the location of the tree tiles.)
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Level data storage

Post by tepples »

If a game has been hacked, RomHacking.net may have a document describing its map storage format. See The Legend of Zelda on Data Crystal and List of The Legend of Zelda hacking docs.

I seem to remember The Legend of Zelda using a metatile scheme involving repeating entire 16-pixel-wide vertical strips of the map.

I know Super Mario Bros. generates attribute data from the metatiles.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Level data storage

Post by Drag »

Link's Awakening starts with one of several templates (such as a closed room, a room open on one side, a grassy field, etc), and then uses a string of commands to define the contents of the rooms. IIRC, you lay down rectangular regions of objects in sequence (bushes, water, grass, walls, etc), or you stamp down individual objects like chests and switches.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Level data storage

Post by tokumaru »

I would take a look at whatever it is Alp is doing here. Those are some impressive compression ratios!
Revenant
Posts: 462
Joined: Sat Apr 25, 2015 1:47 pm
Location: FL

Re: Level data storage

Post by Revenant »

tokumaru wrote:I would take a look at whatever it is Alp is doing here. Those are some impressive compression ratios!
This came to mind for me, as well. That post is a great example of how to represent Zelda-esque map data in an efficient way.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Level data storage

Post by DRW »

Thanks for the tips. With your help, I found a hacking tutorial which referred to the tool "Zelda Improvement". With this and the tutorial's description, I understood what tepples said:
tepples wrote:I seem to remember The Legend of Zelda using a metatile scheme involving repeating entire 16-pixel-wide vertical strips of the map.
Yeah, it's true: "Zelda" has a bit less than 256 meta sprites which are all 16 pixels wide and 176 pixels high, i.e. the whole height of the playfield. So, each screen takes exactly 16 bytes.


I'm asking myself whether this is a better compression method than simply putting meta sprites on arbitrary sections of the screen. (The latter seems to be the way that Drag mentioned in relation to "Link's Awakening".)

I.e. each meta sprite on the screen consists of an x/y position in one byte and the meta sprite index in the next byte.

The meta sprite definition itself would then be an array containing the width and every single tile. (And maybe color information.)

This might not be so efficient if I try to put every tree and every rock on the screen individually. But it's possible to use some larger meta sprites. For example, six trees in a rectangle of 3 x 2 could be their own meta sprite.

But in this case, I need to consider whether I declare a group of trees in the same way as a tree itself:

Code: Select all

meta sprite Tree:
width = 2
tiles =
    TreeUpperLeft, TreeUpperRight,
    TreeLowerLeft, TreeLowerRight

meta sprite TreeGroup:
width = 6
tiles =
    TreeUpperLeft, TreeUpperRight, TreeUpperLeft, TreeUpperRight, TreeUpperLeft, TreeUpperRight,
    TreeLowerLeft, TreeLowerRight, TreeLowerLeft, TreeLowerRight, TreeLowerLeft, TreeLowerRight
    TreeUpperLeft, TreeUpperRight, TreeUpperLeft, TreeUpperRight, TreeUpperLeft, TreeUpperRight,
    TreeLowerLeft, TreeLowerRight, TreeLowerLeft, TreeLowerRight, TreeLowerLeft, TreeLowerRight
Or whether I use another level for groups of meta tiles:

Code: Select all

meta sprite Tree:
width = 2
tiles =
    TreeUpperLeft, TreeUpperRight,
    TreeLowerLeft, TreeLowerRight

meta sprite group TreeGroup:
width = 3
meta sprites =
    Tree, Tree, Tree,
    Tree, Tree, Tree
What's your opinion about all this?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
MottZilla
Posts: 2837
Joined: Wed Dec 06, 2006 8:18 pm

Re: Level data storage

Post by MottZilla »

Memory is cheap now so unless you are exceeding what your mapper supports then I wouldn't worry about being extremely efficient. If you can guess how many screens worth of data the game will use then you can get an idea of how much memory you need. As you saw Zelda uses predefined vertical strips of tiles to make up the overworld and save memory. And the underworld uses predefined room types. However when BS-Zelda was developed for the Super Famicom, the map data actually is stored as a grid of 16x16 pixel tiles and not compressed. Why compress the data or use tricks if you have the memory to fit it? So I'd suggest only going so far that it's comfortable and you can do what you want but it still fits into your memory budget.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Level data storage

Post by DRW »

MottZilla wrote:Memory is cheap now
Now, but not at the time of the NES. And I don't plan to use a custom mapper.
Even though I will get the cartridges produced from scratch, I will create a game that could go on a common donor cartridge, so that people can reproduce it if it becomes freeware.

In my case, I will probably use UNROM.
ROM memory: I'll have to check how much the most common UNROM games had.

For the overworld map, I thought we'll create maybe something like "Final Fantasy Adventure":
www.finalfantasykingdom.net/ffa/map.png
(I'm talking about an absolute pixel size, not about having 16 x 16 NES screens.)
Maybe a bit smaller.

Dungeons: Maybe so that we have the same size as the overworld, but I probably won't implement a separate rendering method for dungeons, like "Zelda" does with its walls and doors. Dungeons in my game will use the same storing method as the overworld, only that they refer to different meta sprites and the graphics tiles are of course different ones than in the overworld.

The game will be a bit story-heavy. So, apart from the level data, there will be a lot of space needed for dialogs. Because I want to create an ongoing storyline (like in "Final Fantasy Adventure", only on a smaller scale), not the static world of "The Legend of Zelda".
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Level data storage

Post by tokumaru »

DRW wrote:I'll have to check how much the most common UNROM games had.
UNROM is 128KB, UOROM (which works the exact same way and has the same mapper number) is 256KB. There's a 512KB extension that has been used for homebrew before. You can fit a lot of screens in 512KB even if you don't use the most optimal compression ever.

Personally, I wouldn't worry about compression so early in development... It's better to start with something straightforward and focus on the engine, IMO.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Level data storage

Post by tepples »

UNROM is 65536 or 131072 bytes; UOROM is 262144 bytes. But because the stock UNROM board doesn't support WRAM, you have to pack the entire mutable state into roughly 1536 bytes (assuming stack, VRAM transfer buffer, and OAM transfer buffer are 512 bytes). You also have to either make your game one sitting long or squeeze the entire campaign's state into 48 bits or less for a practical password save. Two possible extensions to UNROM are adding WRAM using a circuit like that in Family BASIC or making it self-flashable to treat the first few sectors as a log-structured file system.

MMC1 SNROM is 32768, 65536, 131072, or 262144 bytes, and includes 8192 bytes of WRAM. But bankswitching is slow because it uses a serial protocol to save three input pins. The smaller your level format, the less often you have to bankswitch.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Level data storage

Post by DRW »

Yeah, the mapper details are something that I take care of later. In the moment, I'm in the middle of experimenting with the scrolling and screen loading stuff. When this is finished and I can also show a dialog box with text, then I'll take care of learning about the mapper.
tokumaru wrote:Personally, I wouldn't worry about compression so early in development... It's better to start with something straightforward and focus on the engine, IMO.
The reason why I care about compression now is because that's directly related to loading the screen: When the next screen is put into memory before the scrolling starts, I need to load data from ROM, extract it and see how long this takes. That's why I need to take care of the compression now.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Level data storage

Post by tokumaru »

DRW wrote:The reason why I care about compression now is because that's directly related to loading the screen: When the next screen is put into memory before the scrolling starts, I need to load data from ROM, extract it and see how long this takes. That's why I need to take care of the compression now.
Normally you'd abstract these layers... If you already know the basic unit that composes your map (16x16-pixel metatiles?) then you can already test how much memory you can use to buffer those and how long it'll take for you to blast them to VRAM. That's part of the video system, and this system shouldn't really care where the metatiles are coming from, as long as they're put in the buffers.

Similarly, the map/scrolling system should only care about filling the buffers with data. Early in development, you can easily use uncompressed maps and fill the buffers just by copying data, and once you have some of the game working, you can try different encoding methods and finish up the map/scrolling system.

This way you'll not only have a working prototype sooner, but you'll also not regret any encoding decisions you make now in case you decide to change something after testing the gameplay. This is just a suggestion, from someone who's used to overthinking details like this and taking forever to get to the good stuff, you're free to ignore it of course, this is your project after all.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Level data storage

Post by DRW »

tokumaru wrote:Normally you'd abstract these layers... If you already know the basic unit that composes your map (16x16-pixel metatiles?) then you can already test how much memory you can use to buffer those and how long it'll take for you to blast them to VRAM. That's part of the video system, and this system shouldn't really care where the metatiles are coming from, as long as they're put in the buffers.
Sure, my function that writes everything to the PPU in vblank doesn't care. It gets only raw data from an array.
But the preparation function that fills the array during game logic is different: If I do lines like in "Zelda", I have a constant rate of PPU updates. If I do two-dimensional meta sprites of variable size, the update size can vary and I have to include status variables to check whether the next meta sprite can still be included into the PPU update buffer array. And if not, the corrent position of the extraction needs to be saved until the next frame, so that the correct next meta tile gets read when the next frame appears.

In the moment, I'm only experimenting with separate features anyway. I'm not doing anything of the game itself yet, like character movement etc. My current program is only a tech demo to try out all the stuff that will be necessary for the game.
The actual game development will probably not start before the second half of 2017.

So, don't worry. I know what I'm doing and I know what I want.

I implemented filling the complete off-screen name table with a single tile.
Now it's compressing sample data and filling the PPU from the compressed ROM data.
Then it's horizontal scrolling.
Then vertical scrolling with updating the currently visible screen piece by piece.
Then adding color attributes to all the previous stuff.
Then some consideration how to hide the artifacts during vertical scrolling.
Then comes drawing and disabling a dialog box to the other name table on demand.
Then I implement the raster effect that when a dialog box is active, that the name table with the dialog box is rendered and afterwards, we switch back to the regular name table that holds the currently active screen.
And then comes the mapper stuff.

That's my plan.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Post Reply