Metatiles, and memory vs. complexity

[UncleSporky]

Hi guys, I've been thinking about the reasoning behind different systems of organizing your backgrounds/level data and I'm looking for a simple method I can use for a platformer. As such I have a lot of random questions so please forgive the length.

I'm kind of going off of this topic which has excellent info but I thought the subject was different enough to start a new one.

The basic 2x2 metatiles have obvious memory-saving advantages. There aren't many NES games that don't have 16x16 pixel blocks repeated all over the place. It would be easy to stuff a lot of those together, RLE it and call it a day, though that wouldn't be efficient at all. (Or would that be sufficient for a 4 to 8 level demo/game?)

Anyway I'm having a hard time figuring out how I'd put larger metatiles to good use without sacrificing a lot graphically. 32x32 blocks would probably still have a lot of repetitions, but the larger you get the less I see the point. Isn't the main point of metatiles to use repeatable data more than once? How often am I going to repeat 64x64 or 128x128? I understand reused screens the way Mario does it for each flagpole for example, but simply using big blocks while also trying to keep the level layout unique seems needlessly difficult for only mediocre savings.

When people say they have metatiles of metatiles of metatiles, what do they mean? I guess the first thing I picture is this:



Which is clearly wrong and not the way most games appear to do it. We need the flexibility to place graphics wherever we need them and in a typically complex screen there is no repeated data on the largest metatile size. On closer inspection I see this:



But this introduces even more complexity. Now we have 64x64 blocks mixing with 32x32 blocks, so we have to keep track of additional size/coordinate data rather than letting the sequential data be enough, much like an object based system. Again, are the savings worth the effort?

I understand that this example is probably flawed since CV3 is a complicated game made late in the NES's life, but it's representative of what I'm trying to understand: the memory savings vs. map decoding complexity.

What about priority systems for background graphics - was it ever common to overlay metatiles on top of each other? For example, writing in a metatile of a statue and overwriting the bottom of it with plant growth a few lines later. The thought occured to me seeing the two small windows near Trevor with one mostly covered.

I have seen from a lot of topics here that you don't usually store every tile of every screen; it makes sense for a level to have a default screen that is then modified. You can seen this when you jump over the flagpole in Mario and you can keep walking forever. Or like this screen of Kirby:

repeats

That doesn't seem too hard to implement.

Do games use "vector" methods to store backgrounds? For example in that Kirby screen, does the code detect the top of one of those thin poles and extrapolate it to the ground? Or in this Mario screen,



Is the slant defined by its height, and the top becomes the new "ground level" with a grass fill below it?

Finally, would it be worthwhile to keep a copy of the current screen decoded into RAM on a 16x16 level? (Meaning, with status bar taken into account, probably 192 bytes.) It would essentially be for checking collisions or recording changes that need to be made during VBLANK.

[tepples]

When people say they have metatiles of metatiles of metatiles, what do they mean?

Mega Man series (32x32px, made of 16x16px). Blaster Master (64x64px, made of 32x32px, made of 16x16px). Sonic 2 for Genesis (128x128px, made of 16x16px). Tokumaru's Sonic clone (256x256px, made of 128x128px, made of 64x64px, made of 32x32px, made of 16x16px).

What about priority systems for background graphics - was it ever common to overlay metatiles on top of each other?

Super Mario Bros. Super Mario Bros. 3, Super Mario World, and the engine that I've been working on use a sort of object-based storage for area data as (x, y, contents, size) tuples, and objects overwrite objects.

repeats

SMB1 has three layers of repeating stuff behind the "area data", which doppelganger's disassembly called "background scenery", "foreground scenery", and "terrain".

Background scenery consists of clouds, hills, bushes, fences, etc. There are 16 16x48px metametatiles, which are used in three different 48-metatile-wide repeating patterns. Notice how there's never a cloud over a hill, or a cloud over a cloud, or a cloud over a Green Cloud That You Can't Unsee.

Foreground scenery is one of three repeating columns of tiles very similar to the one you plucked out of Kirby:

• Full-screen water in 2-2, 7-2, and 8-4.
• The water at the bottom of x-4 and 3-1.
• The wall at the back of 8-3.

Terrain is various repeating columns of tiles used for long horizontal stretches. Terrain patterns are bitfields of solid and hollow, where the block type is set by the locale (e.g. bricks and cracked-blocks for most levels, or cloud blocks for coin heaven, or castle blocks for x-4, or wet cracked-blocks for underwater levels other than 8-4).

Do games use "vector" methods to store backgrounds? For example in that Kirby screen, does the code detect the top of one of those thin poles and extrapolate it to the ground?

I'm not sure, but my engine has a pass called "Markov" or "MLBB" (most likely block below) that sees, for example, a top-of-thin-pole metatile and extends it downward through empty metatiles until it hits a non-empty metatile.

Or in this Mario screen,



Is the slant defined by its height, and the top becomes the new "ground level" with a grass fill below it?

The Super Mario Bros. games are all vector-fests. Go download Lunar Magic or one of the Mario Improvement editors to see how.

Finally, would it be worthwhile to keep a copy of the current screen decoded into RAM on a 16x16 level? (Meaning, with status bar taken into account, probably 192 bytes.)

SMB1 keeps two such screens side-by-side. But if you're scrolling in more than one direction with a destructible environment (such as ? blocks that can be activated or bricks that can be broken), you'll need some more compact storage to determine what tiles have already been activated/destroyed whenever you redecode part of the level where the player has already been.

[UncleSporky]

Thanks for the info, I'm glad to learn that the above methods are all used. I guess I should've been more specific - knowing that all the above is possible, how do I figure out what combination of features is going to be efficient for a starter engine?

When people say they have metatiles of metatiles of metatiles, what do they mean?

Mega Man series (32x32px, made of 16x16px). Blaster Master (64x64px, made of 32x32px, made of 16x16px). Sonic 2 for Genesis (128x128px, made of 16x16px). Tokumaru's Sonic clone (256x256px, made of 128x128px, made of 64x64px, made of 32x32px, made of 16x16px).

I meant, how is this system of metatiles utilized. What sort of matrix are we looking at, how many bits per entry?

I'm not very good at elaborating on this. Why would you have a 256x256 metatile? What am I looking at to determine the most optimal size for my largest metatile?

Do games use "vector" methods to store backgrounds? For example in that Kirby screen, does the code detect the top of one of those thin poles and extrapolate it to the ground?

I'm not sure, but my engine has a pass called "Markov" or "MLBB" (most likely block below) that sees, for example, a top-of-thin-pole metatile and extends it downward through empty metatiles until it hits a non-empty metatile.

Is this efficient enough to use often, considering it requires a little more checking than tossing down a square of tiles?

[tokumaru]

I meant, how is this system of metatiles utilized. What sort of matrix are we looking at, how many bits per entry?

The easiest way to handle them is when the sizes of the metatiles are powers of 2, so that specific bits from a full coordinate can be used to identify all the metatiles. Take my metatile format as an example:

If inside a 256x256 metatile (meaning I'm limiting values to 8 bits) I have coordinates %10010010 (x) and %00100110 (y). Ignore the lower 4 bits because those represent pixels inside the smallest metatile, so we have: %1001 and %0010. We're already inside a 256x256 metatile, which is composed by 4 128x128 metatiles. But in which of those 4 are those coordinates? Easy, the highest bit of the x coordinate will indicate if it's the left one or the right one. Similarly, the highest bit of the y coordinate will indicate if it's the top one or the bottom one. OK, my bits are %1 and %0 so we want the 128x128 metatile at the top right corner. Just go to the place where the 256x256 metatiles are stored and get that one.

Now, inside the 128x128 metatile the process continues. The next bits are %0 and %0, so we want the 64x64 metatile at the top left corner. This goes on until the 16x16 metatile is reached, at which point you can do anything with it (draw it, collide with it, and so on).

This is the process to find the smallest metatile at specific coordinates, but there are cases when we want to read more, such as when drawing a column or a row of metatiles while scrolling. The process is not much complicated. If rendering a column, for example, use the x coordinate of the column to select between the left or right sides of each type metatile, and once the smallest one is found, just read the top and bottom elements of all the metatiles all the way down until the column is complete.

In the ROM each type of metatile is encoded individually. Each 256x256 metatiles points to 4 128x128 metatiles. Each of those point to 4 64x64 metatiles, and so on.

Why would you have a 256x256 metatile?

You could ask the programmers of games like Sonic 1 or Mega Man X for their reasons, but the reason I use them is so that I can have huge levels that don't take so much memory.

I don't expect to reuse many 256x256 metatiles, except for those that are pure sky or pure ground. Some sections of flat ground can be reused fairly often as well, and you can use tricks like placing decorative objects such as rocks and vegetation over the background so that it looks like a different area.

What am I looking at to determine the most optimal size for my largest metatile?

The amount o redundancy you are willing to tolerate. Some games don't work well with large metatiles, such as RPGs, because their maps don't have many repeated areas. They have areas where specific blocks are reused a lot, so some RLE or LZ-based compression scheme might work better. Platforms in a platformer on the other hand are very similar, and you'll often see large blocks used over and over again.

[UncleSporky]

I meant, how is this system of metatiles utilized. What sort of matrix are we looking at, how many bits per entry?

The easiest way to handle them is when the sizes of the metatiles are powers of 2, so that specific bits from a full coordinate can be used to identify all the metatiles. Take my metatile format as an example:

etc.

This is a really nice system. So as the upper four bits handle 128/64/32/16 location, do the lower four go down to 8/4/2/1, or are they flags for something else? Do you have reason to look up exact pixels in your engine?

Also, that is a lot of decoding! Do you keep track of the screen somewhere temporarily, or is it fast enough to find each tile and push it into the nametable?

This is part of Faxanadu's map, let's say for the sake of example that it scrolls like a Sonic game and each screen is a 256x256 metatile. Your level data would look like this?

Code: Select all

.db 4, 2     ;size of map
.db %00000001, %00000001, etc. etc.

It seems really simple but I want to make sure I understand. Everything is ultimately part of a 256x256 block, even when only used once?

[tokumaru]

You got it all!

do the lower four go down to 8/4/2/1, or are they flags for something else? Do you have reason to look up exact pixels in your engine?

I use them to tell how far into the metatile the coordinates are. This is useful when the ground is not perfectly straight, for example. If each column of the metatile has a different height (as is the case with slopes or irregular surfaces), I have to use the lower bits of the y coordinate in order to tell if a character is touching the ground or not.

Also, that is a lot of decoding! Do you keep track of the screen somewhere temporarily, or is it fast enough to find each tile and push it into the nametable?

I have unrolled loops for decoding rows and columns (for drawing), and those are pretty fast, because I first use the bits of the coordinates to set up a few pointers (one for each type of metatile) and then it's just a bunch of "lda (pointer), y", "tay", "lda (pointer), y", "tay"... because the value you read from a type of metatile is used to read the next type.

Reading individual metatiles (for collision detection and such) is also done on the fly, because it also takes just a few "lda", "tay" instructions.

Your level data would look like this?

Exactly!

I have some tables with the addresses of each row of the level map, so that I don't have to do any multiplications in order to find a particular 256x256 metatile.

Everything is ultimately part of a 256x256 block, even when only used once?

It's easier to do it like this than treat them differently. I don't see any problems with using a few metatiles only once.

[UncleSporky]

do the lower four go down to 8/4/2/1, or are they flags for something else? Do you have reason to look up exact pixels in your engine?

I use them to tell how far into the metatile the coordinates are. This is useful when the ground is not perfectly straight, for example. If each column of the metatile has a different height (as is the case with slopes or irregular surfaces), I have to use the lower bits of the y coordinate in order to tell if a character is touching the ground or not.

Oh, that makes sense, awesome.

Of course your method is most suitable for scrolling in all directions with large levels, whereas a game like Mario or Kirby might just have a basic template modified by objects. I think I understand it a lot better.

I've been thinking about a non-scrolling game with the format of Zelda or Sivak's platformer, so in that case I would probably want to encode each screen individually with 64x64 or 32x32 tiles (also similar to Mega Man which has many individual rooms).

[tokumaru]

I've been thinking about a non-scrolling game with the format of Zelda or Sivak's platformer, so in that case I would probably want to encode each screen individually with 64x64 or 32x32 tiles (also similar to Mega Man which has many individual rooms).

Oh yeah, if you only show one screen at a time the best thing to do is encode them individually. I don't think you need more than one layer of metatiles, and 32x32 is a very good size to use because it makes handling attributes much easier. You should also use some conventional compression such as RLE or LZ on each screen.

This would work well even if you want to have basic scrolling like Zelda, where scrolling is just an animation from one screen to the other and the player has no power over it. All you have to do is decode the new screen to the name table that isn't visible, and when it's done scroll to show it. Of course that if you have hardwired mirroring, vertical for example, you'd have to copy the data a row at a time from the other name table into the visible one as it scrolls up or down. The Mega Man games with hardwired mirroring do this when scrolling vertically.