Techniques for large world maps

How does one implement a large world map ala Final Fantasy, Dragon Quest or Chaos World? All I can think of is a primary array that chunks of static map get copied to when the player reaches a certain limit. That technique sounds like it'd take so much time you'd notice it when scrolling. Am I on the right track though?

Metatiles, metablocks. With ROM large enough you can in fact make a really huge world as a single map. There is, however, problem of graphics diversity, as tileset only has 256 tiles, and they have to be swapped when you need to change setting. That's why there are 'doors' in games of this kind, to hide the graphics switch.

I've heard these terms used but never saw a good source for what and how they work. Any good examples?

It is very simple concept that doesn't really require any docs.

A normal tile is usually encoded with a single byte, 0-255 - 256 different tiles. A map 128*128 tiles will take exactly that much space - 128*128 bytes.

A metatile is a group of normal tiles, say 4x4 tiles. You have a meta tileset that encodes these blocks, it'll take 4*4*256 bytes in this case, and map now contains metatile numbers instead of tile numbers. So 128*128 tiles map will be 32*32 metatiles and will take 32*32 bytes.

Metablock is just a higher level group, the same difference as between a tile and a metatile.

You can see 2x2 and 4x4 metatiles all over NES games, they also affect the level design a lot, so usually you can easily see them. Super Mario Bros. and Megaman are examples for 2x2 and 4x4 respectively.

Slobu also asked the question on SpritesMind, where I replied with this:

Well, I imagine you already know the general gist of the idea, so here's a quick run through of the simplest case.


Meta-blocks, one way to see it, is a form of basic data compression, storing maps of patterns of tiles instead of individual tiles.

Let's say you have a 32 x 2 map, where the data looks like this, stored in an array of 16 bit values:



If the map is large, like 512x512, it would take 524288 bytes. This is obviously a lot. The example would take 128 bytes of storage.

But there's something peculiar about the data. As you probably noticed, there are 2x2 patterns of blocks that are repeated. Because of the patterns, you could represent the data differently by not storing individual tile, but patterns of tiles.



Because the map is now represented as a series of patterns and not individual tiles, you start seeing some savings in rom storage. Here, the patterns would take 32 bytes and the map data would take 32 bytes for a total of 64.

If you had that 512x512 map with the same pattern of data, that map would take 131072 bytes. Plus the 32 bytes for the patterns. So with patterns, you could save a fair bit of rom space.

Of course, my example is pretty contrived and artificial but it does give you an idea of how it works.


*************

Another way of see it, from the point of view of a game designer, is not as a compression scheme but as a way to build maps. You create a set of patterns use them as building blocks to build a map. Because you're working with sets of 2x2 patterns, it's faster to build maps than placing individual tiles. Of course what you gain in speed you lose in flexibility. You have to make sure that the patterns go together well and that they can repeat. If you have lots of specific patterns, you start losing the memory savings.






*************

That's the theory. Of course the storage savings aren't free. There are two practical problems, one of storing the data and one of retrieving the data.

1. Storing the data.

There are two cases, a) you're using a pre-built editor like Mappy or Tiled or b) you have your own editor.

a) pre-built editor like Mappy or Tiled.

To save the map into meta-blocks, the programmer will have to write an exporter. The exporter will have to analyze the map data, looking for 2x2 patterns (or whatever size you choose). The exporter analyzes the map in 2x2 tile chunks. It also keeps a list of 2x2 tile patterns in memory while analyzing the map. There will also be a new map, the meta-block map, which will be a quarter of the size of the map where every item is an index into the pattern set.

When analyzing the map chunck by chunk, if the 2x2 tile chunk its looking at doesn't exist in the pattern set, it creates a new pattern and adds it to the pattern set. If the pattern already exists, then no new pattern is needed. In either case, the index of the pattern is saved into the meta-block map. When it has finished going through the whole map, where will be a pattern set and a meta-block map.

It's extra work to do the map analysis, but you save work because you're working with pre-made tools. Also, the complexity of the map affects the size of the data. If there are too many individual patterns in the map, meaning that there are very few repeated 2x2 patterns, then you start losing on the storage savings. It's a trade off between unique patterns and storage size. Your game designer will always have to be aware of this when building maps.

b) custom editor

A programmer builds an editor specially made to create maps with 2x2 patterns. The game designer creates the patterns manually and creates a map with them. There's no need for a programmer to analyze the data but it requires writing a custom editor. The game designer is aware at all times that their map is made out of patterns and is most likely more conscious of reusing them efficiently.

2. Retrieving data

Once you have your map data stored in your rom, there needs to be a way to build your map on screen. Because the data is stored as a bunch of patterns instead of a big array, it's trickier to do.

Simplest case:

You know your map on screen is supposed to be 512 x 512 and that every pattern is 2x2 and that your meta-block array is 256x256. To draw an individual tile from your 512x512 map, you need to go from the 512x512 map to the 256x256 meta-block map by dividing by 2 (or whatever the width of your pattern is). Once you know which item of the 256x256 map you're using, you can get the index of the pattern it uses.

Once you have the pattern, you can use modulo to figure out which tile of the pattern you're using.


An example of doing the look up:


Of course you're drawing one tile at a time. It may be more efficient to use the meta-block map intstead and draw 2x2 patterns on screen directly. I'll leave that as an exercise to the reader


This is just one technique. I'm sure others have better ones.

And I'm sure I've made a mistake or two. Corrections welcome!

A custom editor also allows structuring the map as a list of objects, such as "house 2 centered at X,Y", or "wall starting at X,Y and L tiles long". At least Super Mario 1, 3, and World store their maps this way. Updating the map as the camera moves involves traversing the list of objects and finding which objects intersect the area to be updated. To get a feel for this, try Lunar Magic for a while.

The way Dragon Quest worked was to use an RLE compressed overworld map. (I wrote the Dragon Warrior editor a long time ago, I know these things...)
There are also row pointers that point to each row, so it can instantly seek to the start of the row, and seek through the RLE runs to a particular X coordinate. Updating a bunch of rows and columns isn't very hard to do.
Dragon Quest 4 needed more CPU time, so they split the rows down the middle as well.

I was fascinated by how Ultima 6 did the overworld map: 8x8 chunks of 16x16 tiles, plus an object layer.

Was your info on Ultima 6 somewhere on the Interwebs or did you reverse engineer it Dwedit?