It is currently Tue Oct 24, 2017 12:57 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 15 posts ] 
Author Message
PostPosted: Fri Mar 11, 2016 5:02 pm 
Offline
User avatar

Joined: Fri Sep 11, 2015 10:39 am
Posts: 106
I suspect that this one is not going to have many specific answers, as it probably just comes down to the individual game and how it was programmed.

But even so, I'm wondering what limitations influenced the sizes of maps that games used.
Okay, I know some were influenced by the name table and things like status bars, which is why Mario 3 had most maps about two screens tall, and a lot of games were just one screen tall so they only had to scroll horizontally.
But then there are games like Castlevania II which had both vertical and horizontal scrolling, but the game was still divided into map sections. Most of the time this was because there would be different tiles and monsters in the different areas, but then they also had such divisions in the middle of the mansions, where those things did not change. This suggests that they may have had a logical limit of how large of a map the game could handle.
And yet there are also RPGs with world maps that are frikkin 4096x4096 (in pixels.) So, it looks to me that map sizes were largely arbitrary, and set up more for convenience and game logic rather than hardware limitations. (Well, to a point. obviously.)

Even so, I wonder if there were common restrictions or perhaps particular aspects to map sizes that most games faced. I am about to set up camera limits in my game, and logically the camera limits are the map sizes. So I'm curious what kind of restrictions I should conform myself to. (And in case there is anyone new here, I'm making a game with a modern engine, but trying to emulate the NES's restrictions 100%.)

I would venture a guess that perhaps a map's size ought to be limited by powers of two, or at least to multiples of a power of two. On top of that, a game could easily add an arbitrary "wall" that the camera can't scroll past at any point, so even if a map was technically 512 pixels long, the player might only see 400 of that. But knowing those limitations would influence how a map was designed; like if maps were stored in powers of two, then making a map that is 528 wide would result in a big chunk of data being wasted on empty space. That's the kind of stuff I need to be aware of.

For the sake of argument, we'll say the mapper is MMC3, since that is probably going to influence things. Though I'm also curious about the MMC1.

And on the subject of maps, I am also curious about the limitations for the number of maps a game could have overall. I was thinking I would set an arbitrary limit of 256 different maps, since that seems like a reasonable technical limit that probably no game on the NES ever hit. But I suspect one would hit limits in the PRG data first. This limit is probably more important to me; I have a tendency to go overboard and put in more and more in the games I design, and I want to establish a barrier to make sure that I don't make the game too big. So figured I would have a limit of 256 individual maps, including ones for the title and menu and such. That's a pretty outrageous limit though, so I wonder if there is a smaller one I should be more conscious of.

And on the final subject of maps, I want to confirm that they work the way I imagine.
Commonly they would store the data in blocks of 16x16 pixels, (though I understand some might use 32x32 or perhaps other amounts.) which would mean each address on the map contains data for four tiles, a palette, and a collision type. And from what I have seen of games from before my time, these are probably commonly stored as a set list of instructions, rather than a whole list for each block. So for a block at the location of 14 x 10, the map would store a single byte, say, the number 12. And then the game checks to see that a block of twelve uses the tiles 44, 45, 32, and 33, uses palette 2, and does not collide with the player.
And since these are set up arbitrarily, a game could put in whatever data it finds pertinent for itself in that data, and the blocks could be any size it wants. (Although the way the hardware renders things probably influences what kind of data they want to use.)
So if I'm right about that, maps would also have a logical limitation of 256 different types of blocks, which limitation no one came close to breaking, and would probably hit cost limits to store the PRG data first.
...Am I right about that?


Last edited by Marscaleb on Fri Mar 11, 2016 5:44 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 5:37 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1021
Here is a large test level from my game. It is 3840x2304: http://i.imgur.com/J3N5SB1.png

Here are all the levels I'm fitting in less than 16KB: https://www.youtube.com/watch?v=2bJW64G_tHY (A lot are a single screen, though.) The first one shown is the one above.

The only limitation I have (that would matter for what you're asking) is that no level may have more than 256 unique screens. I can have a level that is 256x1 screens. For reasons that I'd rather not get into, I can't exactly have a level that's 1x256 screens. But I could have like... 1x200. And anything in between. 2x128, 128x2, 64x1, 64x2, 64x3, 64x4. Etc. It doesn't have to be a power of two. I can have maps that are 12x5 or whatever. So long as X*Y is not > 256.

Quote:
So if I'm right about that, maps would also have a logical limitation of 256 different types of blocks, which limitation no one came close to breaking,

Well... there's nothing that would really stop me from having more than 256 screens in a level (I actually do have one data type that I support more than 256 of) if I wanted to, it's just that it would make data size bigger and take a little longer to read. I'd say that if you're not actually making an NES game you should just consider yourself unrestricted for levels.

Edit:
Quote:
then making a map that is 528 wide would result in a big chunk of data being wasted on empty space. That's the kind of stuff I need to be aware of.

Make a map with a large part of it "unused" doesn't really take any extra space. Because (in my case), that just means it's storing the same screen in all the "unused" space which takes up 1 byte per screen. Not really a big hit. I could have a 16x16 screen level that has a flow diagonally downward. Sure the player can't reach the top right or the bottom left, so the top rightish piece of it would be filled with a "sky" screen and the bottom left would be filled with a "solid" screen. And I only have to define the screen once. Then references to it take a byte.

Edit2: There's also absolutely nothing stopping you (or me) from having more than 256 levels. The reason stuff is often limited to 256 is space concerns, or speed concerns. But since you just... load a level, the extra time it'll take to access more than 256 doesn't matter. (You've faded to black to load the level. You have a lot of time to do it, it doesn't need to happen during gameplay. But loading a new "section" of the level does, which is why I am limited to 256 screens.) The extra space needed to define more than 256 levels is similarly not that much of a burden, especially for what it gets you.

Edit3: I can't hold all these edits.

Quote:
Commonly they would store the data in blocks of 16x16 pixels, (though I understand some might use 32x32 or perhaps other amounts.) which would mean each address on the map contains data for four tiles, a palette, and a collision type. And from what I have seen of games from before my time, these are probably commonly stored as a set list of instructions, rather than a whole list for each block. So for a block at the location of 14 x 10, the map would store a single byte, say, the number 12. And then the game checks to see that a block of twelve uses the tiles 44, 45, 32, and 33, uses palette 2, and does not collide with the player.
And since these are set up arbitrarily, a game could put in whatever data it finds pertinent for itself in that data, and the blocks could be any size it wants. (Although the way the hardware renders things probably influences what kind of data they want to use.)
So if I'm right about that, maps would also have a logical limitation of 256 different types of blocks, which limitation no one came close to breaking, and would probably hit cost limits to store the PRG data first.
...Am I right about that?

Basically levels are made of references to other data. There can be a bunch of layers of references, or just one, or none. (But that's rare)

For a small game, you might have levels that reference the screens that make them up. The Screens reference the 16x16 regions that make them up. The 16x16 regions are stored as the 4 tiles that make them up, their palette, and their collision info.

So... every unique 16x16 region needs five bytes. 4 bytes for tile references, one byte for other stuff. (Palette is two bits, 6 bits free for collision stuff.)
Each screen needs 240 bytes. A screen is 256x240, which means it it made of 16x15 16x16 regions. It uses a single byte to reference which 16x16 tile to read from at a given location in the screen. If there were more than 256 unique 16x16 regions that a level needed, it would need two bytes per, effectively doubling level size. (Screens need 480 bytes now instead of 240bytes, or else they become much harder to decode if not byte aligned.)

Then each level needs however many screens long the level is of bytes. If there are more than 256 screens, once again the size of this is effectively doubled. (Which isn't really all that bad. An 8 screen long level is now 16 bytes instead of 8.)

The reason for the layers of references is because any time you reused something, you save big. If you use a screen you've used before, you use literally one byte to use it again. Instead of storing the same set of 240 bytes of 16x16 tiles. If you didn't have a layer of references for screens, you couldn't do that.

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 6:11 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5736
Location: Canada
Once you're into all-ways scrolling territory there's no real maximum map size. The real problem is just how much space the map data takes up in your ROM; if you have some sort of simple repetitive rubber-stamp room system you might get very large indeed.

You might want to poke around at VGMaps: http://vgmaps.com/Atlas/index.htm#NES


Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 6:21 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1021
Edit time is over, new post time:

The reason for the layers of references is because any time you reused something, you save big. If you use a screen you've used before, you use literally one byte to use it again. Without the layer of abstraction, you'd have to store an identical 240 bytes to what could be another screen. Basically make a layer of references for the largest part you think you'll be able to reuse.

But there's another piece to that: I usually don't count on being able to reuse screens, but I have a layer for them because it makes random access in my level easier. Assume you have a level 128 screens wide. You're only storing 16x16 regions as bytes. To access each row, you have to multiply the width to get what you want, and it's higher than 256.

If you had screens, you get what screen you're in, access that. And then find out where you are in the screen by bitwise ANDing your positions.

My data is stacked with references, so I can reuse "large small parts" and save big on what makes them up. I've also got other kinds of compression, so that (for example) a screen of 16x16 tiles still would usually take less than 240 bytes. (I don't do it exactly that way, but you get what I mean.)

I've got levels->256x256 regions->128x128 regions (This is what I can have more than 256 of)->32x32 regions ->16x16 regions.

I could make an entirely new level using 128x128 regions from other levels and save big on space because there's basically no new definitions. I'd save bigger making a level using screens from other levels too, but it'd be easier for the player to see X piece is from some other level.

I tend to build my levels reusing 32x32 regions, meaning 128x128 regions and 256x256 are mostly unique per level. But things like sky from other levels can totally be reused. I can actually even reuse whole levels and change just the enemies in them, if I wanted.

Another way to build data is tell a the game "There are two drawing instructions: draw a solid 10x12 rectangle here, draw a 5x2 rectangle here." And that may be smaller than storing a byte for each part of those rectangles, plus a byte for each piece of the non solid parts.

But really, like I said in my post, and what rainwarrior mirrored. Just consider yourself unrestricted as far as map size. I think it'd be a waste of time to define the regions you think you'll use, then write software to check that. Just... make levels.

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
PostPosted: Fri Mar 11, 2016 7:47 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10068
Location: Rio de Janeiro - Brazil
The hardware has very little influence over map sizes, since the name tables can be rewritten as much as you like. It's really all just a matter of having where to pull new level data from. If you have the space to store it, you can display it, and interact with it. As for the mapper, its role is limited to providing more space for level data.

Having more than 256 items of any particular kind of item is not impossible by any means, the only drawback is that indexing said items will require twice the space, making their use less compact than it would be otherwise, and accessing that data will be slightly slower, since each reference is twice the size, and you might need to use pointers to access the items themselves rather than indexed tables. In most cases the difference shouldn't cause any noticeable performance issues.

The one thing that greatly impacts how large your levels can be and how many of them there are is the format in which you encode them, because that defines how well you use the ROM space that's available for maps. No level format suits all types of games, so you should find the format that's able to retain the dimensions and level of detail you need in the space you have. If you can't find that format, you'll have to compromise somewhere.

In my current project, I use several layers of indirection: Levels are built from 256x256-pixel blocks, which are built from 128x128-pixel blocks, which are built from 64x64-pixel blocks, which are built from 32x32-pixel blocks, which are built from 16x16-pixel blocks, which contain collision and palette information. I can have 256 of any of these structures, and that costs very little memory, but the levels need to have many repeating structures for this to work well, which might be undesirable in many types of games. Levels themselves can have any configuration of 256x256-pixel blocks, with a limit of 128 per axis. Even 128x128 (32768x32768 pixels) is possible, but not very practical because this map alone would consume half of a PRG-ROM bank.


Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 8:21 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19122
Location: NE Indiana, USA (NTSC)
One significant limit on level size is destructibility. Unless your game scrolls only one way, as Super Mario Bros. does, you need to remember which parts of the map the player broke, collected, or otherwise changed in some way in case the player returns to that area. With only 2K of RAM available to most games (or 10K if an extra 8K RAM is included inside the cart at extra cost), this information can pile up. Section breaks act as a barrier to let the game forget destroyed objects in the previous section. See "Programming M.C. Kids".

This destruction can be stored at various levels of detail: 1 byte per lowest-level metatile (e.g. 16x16) to decompress the whole level first, 1 bit per lowest-level metatile to store just primary/alternate forms for each block, 1 bit per larger metatile if you're fine with storing destruction at a coarser resolution, or perhaps 1 bit per object ID if only a few objects in the level can be destroyed. In a game that scrolls only in one direction, you may be able to get away with storing one destruction bit per column (e.g. 16x192 pixels) of the level.


Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 9:47 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10068
Location: Rio de Janeiro - Brazil
I'm generally against storing destructible levels in RAM (in my own projects, I'm fine with other people doing it if it suits their games), mainly because even with an extra 8KB of RAM, the level sizes you can get without multiple layers of indirection are nothing to write home about. 128x64 blocks will get you only 8x4 "screens", or 16x8 (or 32x4, etc.) if you go with 32x32-pixel metatiles. That's perfectly acceptable for many types of games, especially considering that even with 32x32-pixel metatiles, the destruction could still appear to happen at the 16x16-pixel level if there were few (ideally 1!) destructible types and there were 16 32x32-pixel blocks containing all possible combinations of intact/destroyed for the 4 sub-blocks.

As I see it, levels with huge destructible sections aren't that common anyway, and the typical amount of destructible obstacles can normally be implemented with objects instead. In my engine I have 192 bytes or so that objects can use to keep track of their intact/destroyed status for the duration of the level, and at 1 bit per block that could mean 1536 destructible blocks in a level (there will never be that many though, since those bits must also be used for items, enemies and such). I'm very comfortable with that limitation.

Sure there are other disadvantages of having destructible scenery implemented as objects, such as the need for extra logic in order to have level objects collide with it. In many cases though, only the player really ever touches these blocks, so I don't consider that to be a big problem for the particular type of level I'm designing.


Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 1:43 pm 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 183
Marscaleb wrote:
And on the subject of maps, I am also curious about the limitations for the number of maps a game could have overall. I was thinking I would set an arbitrary limit of 256 different maps, since that seems like a reasonable technical limit that probably no game on the NES ever hit. But I suspect one would hit limits in the PRG data first.


The PRG limit is only a problem, if the formatting isn't sufficiently optimized.
My cancelled NES game, had more than 300 unique(!) rooms, because the data size was trivial.

Here are some figures, with the byte count labelled.
Image

Each screen was compressed with multi-directional RLE, and parsed by the game engine in RAM, using a dictionary-based "auto-tiler" system. A .GIF rendering the process is shown below.
Image

Theoretically, this exact format could be modified to support full-range scrolling, with very little compression loss. But I honestly can't be bothered.


Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 1:53 pm 
Offline

Joined: Thu Aug 12, 2010 3:43 am
Posts: 1589
That already looks more advanced than the filtering PNG applies before deflate compression =P


Top
 Profile  
 
PostPosted: Sat Mar 12, 2016 4:57 pm 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 183
Sik wrote:
That already looks more advanced than the filtering PNG applies before deflate compression =P

I'm a software engineer, and this was made for an NROM game, so I can't complain! :P
The unpacking process is actually quite fast.


Top
 Profile  
 
PostPosted: Thu Mar 17, 2016 10:29 pm 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 284
Alp wrote:
Each screen was compressed with multi-directional RLE, and parsed by the game engine in RAM, using a dictionary-based "auto-tiler" system. A .GIF rendering the process is shown below.

What do you mean by "multi-directional RLE"? The animation looks like it's following a series of line-drawing instructions, but I can't figure out how you'd fit them all in just 12 bytes.


Top
 Profile  
 
PostPosted: Fri Mar 18, 2016 6:10 am 
Offline
User avatar

Joined: Mon Oct 06, 2014 12:37 am
Posts: 183
Rahsennor wrote:
What do you mean by "multi-directional RLE"? The animation looks like it's following a series of line-drawing instructions, but I can't figure out how you'd fit them all in just 12 bytes.


Do you see that block of 16x16 tiles at the beginning of the .GIF that fades out, before the building process starts? That's exactly how the map is stored in ROM, using the RLE method described.

That demonstration room is only 12 bytes, for the raw tile data. It's expanded to 192 bytes in-game. That "line-drawing" you see, is actually an "auto-tiler" routine, parsing the data.

The screen is built directly in a RAM buffer, using a series of instructions, that simply check for certain lengths of tiles, and replace them with the correct tiles, as needed.

1.) Walls bottom-to-top (1x2), checking for corners, and changing the "write mode", as needed.
2.) Floor, left-to-right (1x1), checking for index 00, and creating pits, if found.
3.) Ceiling, checking the remaining 00 tiles, and creating a wall fringe around the room, if possible.

There's a few smaller, less-significant rules, but I won't list them here. (Blocks, Spikes, Water)


Top
 Profile  
 
PostPosted: Fri Mar 18, 2016 6:46 pm 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 284
Ah, I think I get it now. Thank you for explaining.

You didn't actually describe what you meant by "multi-directional RLE" though. :|

Sorry for sounding like a broken record; your "auto-tiler" approach is way cool, but my maps are nowhere near fancy enough to benefit, so whatever you're doing to get those byte counts is actually more interesting to me. The best RLE I can come up with would take 25 bytes for the 'raw' version of the demonstration room, which is a lot better than the 48 my current format would use, but still nowhere near 12.


Top
 Profile  
 
PostPosted: Fri Mar 18, 2016 9:31 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1021
It's not his specific thing, but I've made a similar compact format. You can define a starting position in a byte like XXXXYYYY. You can define a structure and type in another byte like XXXXXXYY. You can define properties of the structure in a third byte.

My format also auto tiled and had the types vertical line, horizontal line, rectangle, and filled rectangle. So to define a room like his, I'd use three bytes for the floor. Starting position (top left corner of) a filled rectangle is one byte, the structure (which autotile set to use), type (filled rectangle), and height and width in the third byte. The walls would then be a non filled rectangle around that, so another three bytes. Since his top wall is taller, I might then have to draw a horizontal line above that. 3 more bytes for 9 total.

Before everything I think have a byte that is how many instructions are in the room/how many enemies in this format XXXXYYYY, but it might just be a byte for each. So three instructions (the two rectangles and the straight line), and zero enemies.

Ten bytes total for a similar room. (Edit: Looking again at his image, I might have to draw the walls as a filled rectangle and then draw the floor as a filled rectangle on top of that to not use a fourth structure.) His format definitely better handles other cases, but I'm sure you can start to see how to get very small room sizes. That said, the structures (how things auto tile) do need to be defined, so it's not really ten bytes when you think about it.

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
PostPosted: Fri Mar 18, 2016 9:43 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19122
Location: NE Indiana, USA (NTSC)
In other words, it's like the object-based format of Super Mario Bros. series.


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

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 7 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