SpritesMind.Net

I'd like a seamless world like most Final Fantasy games. I guess The Faery Tale Adventure is one other example. What are the choices when planning for large world maps?

The SonicRetro forums mention "meta-blocks" but I've yet to find a good tutorial on such things.

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!

Thanks for the detailed explanation djcouchycouch!

Er, I'm still processing all of this, but.. aren't we assuming this is all in one static array? What happens when we have multiple map sections?

I'd assume with that you'd have to store the current area as an array and feed it portions of the static map areas on the fly. How would that be done without slowdown at map boundaries?

slobu wrote:Er, I'm still processing all of this, but.. aren't we assuming this is all in one static array? What happens when we have multiple map

The explanation would only work for one section. If you had multiple sections, like many floors in a dungeon, you'd have to store each section individually and then store data about the doors between them.

That's what I thought. When I think The Faery Tale Adventure I think VERY BIG maps. There must be a good way to traverse map sections stitching together a complete world.

They must be using some very big meta tiles but how to they transition new map data seamlessly without doors?

I can imagine a hierarchy of maps such as world map -> local map data but to stitch them together seamlessly without pause is troubling me.

slobu wrote:That's what I thought. When I think The Faery Tale Adventure I think VERY BIG maps. There must be a good way to traverse map sections stitching together a complete world.

They must be using some very big meta tiles but how to they transition new map data seamlessly without doors?

Oh, I see what you mean. I wasn't familiar with that game.

If it's one giant-scrolling map then you could still use the same technique.

You can break down the map into smaller sections.

Say it's a 10,000 x 10,000 world map. You can break it down into screen sized sections of 100x100. Wherever your player is, you load the nine sections around the player. Whenever the player reaches the edges of a section, you unload the farthest away one and load the closest one.

Say the player is in screen 8. you'd only need to load the sections around the player (2, 3, 4, 7, 8 ,9, 12, 13,14). If the player moves right to section 9, then you drop 2, 7, 12 and load 5, 10, 15.

The idea is that you only load the sections you require.

That was a pretty decent Account of Meta-Tiles, djcouchycouch - thanks.

Very good reading all this.

As a matter of fact, I'm planning to do a research in seamless world generation for a world map. I didn't know the term, actually, I always referred to "world map view".

Many RPG games work around this by using world map view and town/dungeon view, however, games like Faery Tale Adventure and Ultima VII (for PC) use only one world map view.

I am also planning to use the Open-Ended concept, which is very interesting.

Faery Tale Adventure is a huge acomplishment still today. For the year it was designed, ca. 1987, allegedly had more than 17.000 screens!

I read on the Internet that the key for this was to use loading screens during adventuring. The technique is described by djcouchycouch: you load the main player screen and its boundaries. When the player reach one boundary, the game unloads all screens not boundary anymore, then load the other boundaries not loaded yet.

The challenge is to do this while the game runs. One sugestion maybe: using a separate loading process that uses all intervals available during screen redraws. <phew>

I tend to have 4x4 screenfuls loaded at a time. These are loaded in the background by a separate thread when the main game thread is not running. The loading routine reads object data and clips each object to the current screen, meaning that screen boundaries are not a concern when designing maps. Previously, I would define each screen separately, but the level designer found this awkward to work with.