It is currently Sat Dec 16, 2017 9:31 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: Level data storage
PostPosted: Mon Jan 16, 2017 7:16 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
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.)

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 10:24 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19353
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 10:53 am 
Offline

Joined: Mon Sep 27, 2004 2:57 pm
Posts: 1248
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 11:02 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10166
Location: Rio de Janeiro - Brazil
I would take a look at whatever it is Alp is doing here. Those are some impressive compression ratios!


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 11:19 am 
Offline

Joined: Sat Apr 25, 2015 1:47 pm
Posts: 337
Location: FL
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 2:13 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
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:
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:
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?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 2:40 pm 
Offline
User avatar

Joined: Wed Dec 06, 2006 8:18 pm
Posts: 2806
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 2:58 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
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".

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 3:53 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10166
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 4:23 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19353
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 4:39 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
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.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 4:51 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10166
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
 Post subject: Re: Level data storage
PostPosted: Mon Jan 16, 2017 5:40 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1516
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.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: Bing [Bot] and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group