Tile Maps: How to Represent a World

After the last post, which covered an awful lot of code, this will mostly be theory again, mostly because I'd like to go in with a plan, and I do not yet have one.

With a good tile set, you hardly notice the grid.

I want you to think of classical console RPGs. Final Fantasy VI (pictured on left), Chrono Trigger, Secret of Mana and the like. While their art styles differ somewhat, they have one thing in common: They share an angled top-down view of their game worlds, projected orthogonally, i.e. without perspective. Levels are made up of 16 by 16 pixel square tiles.
Pokémon, Golden Sun and most RPG Maker games use the very same world view. Yet, with all of these games, there are some technical differences in how they do their rendering; they all use different data structures to represent their levels, so they all have slightly different 'max-specs' in terms of level design.

Layers

Seiken Densetsu 3, showing the ocean
and the sky beyond the cliffs.

Some SNES games opted to use one of their precious two background layers for a parallax background.

Especially popular with the RPG Maker crowd, but also used in Chrono's room in Chrono Trigger, you could use additive blending for lighting effects.

You could use subtractive blending for shadow effects in murkier environments, alpha blending for translucent overlays, e.g. for weather effects or transparent objects in the game world.

By sacrificing layers for visual effects like these, however, you limit how many layers you can effectively use for maps. For instance, Pokémon Ruby and Sapphire had bridges you could go both under and over, solely because the GBA had more background layers, making a multi-layered environment possible.
Considering you also need to render UI elements somehow, you run out of layers fast. In my post on technical limitations, I said I'd use around eight layers. Let's see where that gets us, assuming we want all of the above:

1. Parallax Background
2. Map (Underneath objects)
3. Map (Above objects)
4. Light Map (Additive Blending)
5. Shadow Map (Subtractive Blending)
6. Parallax Overlays (Arbitrary Blending)
7. UI Background (Blending)
8. UI Text

That's not very far. We could do objects crossing bridges over and under, but there could be no elements in the map that cover these bridges, so that's already pretty limiting. With both the light and shadow map above the map layers, you couldn't have light sources or shadows that only cover the lower level of the map.

We'll have to bend our minds somewhat to justify more layers.
The obvious target would be UI; Assuming the background doesn't blend, you could render it into a single layer. You could also use sprites for text and other non-transparent objects. Either way, that's one layer we get back.
You might argue that few maps would use both light and shadow maps, and that having both go in front of all map layers is almost certainly a waste of either. Reordering the layers so that you get one transparent layer with arbitrary blending in front of both map layers would be more useful.
Finally, you might say that having both an overlay and a parallax background would look weird, since some layers in the middle would be the only scrolling ones. If you allow either, but not both at the same time, you get the same fundamental feature set, and an additional layer back. However, I've never seen both effects used at the same time and thus would like to withhold judgement in this case.

Still, our layer reservations now look like this:

1. Parallax Background
2. Map (Underneath objects)
3. Light Map (Arbitrary Blending)
4. Map (Above objects)
5. Light Map (Arbitrary Blending)
6. Map (Above everything)
7. Parallax Overlays (Arbitrary Blending)
8. UI

I might want to reshuffle layers 2 through 6 later on, or even provide facilities to determine their order on a per-map basis, but that's basically what I'll be going for. And I'm quite happy with it. We have three Map Layers, which should be enough. We might even get a fourth, depending on my judgement on the background+overlay issue.
All that said, it should be clear that there can really only be two layers of map objects, which will be a major factor in how you can layout a dungeon, for example.

Tile Sets

These are the deciding factor in what can actually go inside a map. I barely touched on these in my post on technical constraints, so it's time to talk about them now.
A tile set is essentially a texture you use to construct maps. A map is a multidimensional array of indices into an array of tiles. Tiles are regularly sized pieces of the tile set.
As mentioned above, most RPGs from the era in question had a 16x16 pixel grid, but both the SNES and GBA had hardware support for maps with a 8x8 pixel grid. Generally, you would find tile set meta data, that provides the 8x8 tile set to the hardware, as well as block data, which would combine four small tiles into one 16x16 block, possibly with some gameplay data attached. This gives you a block set, from which the actual maps are constructed.

Since there's no hardware or even library support for tile maps, I don't have to add this complication, using a tile set with a 16x16 grid from the outset.
However, that begs the question how large our tile sets should be. Depending on the graphics mode, the SNES supported up to 1024 8x8 tiles in a set. Each can be displayed in one of eight palettes, giving us 8192 possible tiles, four of which are combined into one block, giving us upwards of 4.5 quadrillion possible blocks, more than we could index with a 32 bit integer.
Usually, only a handful of tiles would be used with different palettes, and even then, rarely more than two palettes. Assuming all tiles could be reused that way, this gets us down to about 17.6 trillion. If none are to be reused, that puts us to just below 1.1 trillion, still more than fits into an integer.

Maybe looking at actual technical limitations is in order. XNA runs on DirectX 9. That's so 2010. Anyway, DX9 supported textures up to 4096x4096 pixels, though not all DX9 GPUs actually implemented that. The most commonly recommended maximum texture size I remember from these days is 1024x1024 pixels.
Now, I'm not sure how MonoGame fares compared to that, but a texture of that size gives us 64x64 (=4096) tiles. In comparison, that's nothing, but it's a much more reasonable size for a block set. You can index that with a 16 bit integer and have 4 bits left over, e.g. for flipping blocks along either axis (one bit per axis) or rotating by a multiple of 90 degrees (four rotations fit into two bits).

As for colors, because of the way blocks are constructed from four tiles, each of which might use one of eight palettes of 15 colors, one block might contain up to 60 different colors, but only 15 colors per quarter block. That's not only confusing, but also somewhat limiting.
You can't really enforce it from a software perspective either, so I just decided to go with up to 128 colors per tileset, and try to avoid scenarios with many palettes on a block. If breaking this rule makes for a prettier tileset, though, I won't think twice about it.

Animation

Whether it's a waterfall crashing into a riverbed, the mill wheel rotating downstream or just the grass beside it swaying in the wind, if it's in your game world, you'll want to see it moving. Since the tiles themselves can't really move, and that would make for a horrible 'animation' to boot, we have to figure out another method.
Generally, you animate pixel art with old-school, hand drawn frames that get swapped according to some carefully chosen timing.

Ideally, the tile ID we read from the map should be translated directly into coordinates in the tile set texture, so this leaves us in a bit of a predicament.
On the SNES, you'd have a set of animation definitions, process them, and hot-swap the animated tiles in the tile set for other graphics. We could use SetData on the tile set texture, though I'm not sure how feasible it is to do that mid-frame.
If we want to stick to the ideal tile ID to texture coordinate translation, the only real option is to modify the map data instead of the tile set data. That's naive and counter intuitive at the same time; the map refers to an animated block, why does the animation change the map? It would also take varying amounts of time, depending on map size.
The most viable solution I can see, would be an additional step in translating the tile ID to a texture coordinate. Have a dictionary of tile IDs, which is updated by the animation code, and switch tiles as they're rendered.

Meta Data

With that, we could go in and write a renderer for this specific tile map system, but there are some questions left to make it into a game. These questions primarily concern meta data:
Which tiles can you actually walk on? Do these tiles have any special behaviour attached? How should NPCs and other event data be stored?

Starting with collision data, I want you to think of two games in particular: The Legend of Zelda - A Link to the Past, and Tales of Phantasia. In both games, you move your character with no respect for the grid, unlike Pokémon, where your character is always aligned with it.
In Tales of, a block's collision data was essentially four boolean values, creating a smaller 8x8 grid of colliders. In A Link to the Past, in addition to full-block colliders, there were diagonal walls, that, when walked against, had you slide along them.
The point is, there's many ways to relate collision data to the tile map, and you have to decide on one concept.

Logical layers also tie into this. Consider bridges again. While you're on top, you collide with their edges, but can walk over just fine. When you're below, the inverse is true.
The Pokémon games handled this strangely. They have one byte of movement data attached to each block. Two bits of that are dedicated to the basic collision behaviour (walkable, impassable, walkable*, surfable), with some of the rest representing various layers.
You can cross from walkable blocks to walkable blocks of the same layer, but not of a different layer. The walkable* behaviour allows you to cross layers.
Certain values of the movement byte are reserved for horizontal and vertical bridges, as well as some others with unknown behaviour. If you are on a walkable block above a certain layer, you can enter horizontal bridge tiles from the sides, though you can walk freely between them. At the same time, you could only enter vertical bridge tiles from the top and bottom. If you are below that layer, the inverse is true.

I really like this approach, because you only need one collision map. The Pokémon developers only ever used, like, two of the dozens of available layers, confirming again that that should be enough, while also freeing up some space in the collision data structure.
Let's say we use three bits to determine the basic collider shape. There's passable (0), impassable (1), four variations of diagonal walls (4-7), and two undefined values. When used on the lower layer, these may just be impassible, but on the upper layer, they might represent bridges. Add one bit to indicate the layer, and we have four bits per collider.
We could easily use four of these per block, which would make for a total of 16 bits of collision data.

Block behaviour is a whole other issue. These should be hard-coded event handlers for entering, exiting or clicking on a block with the given behaviour. Seeing that they're hard coded, you could use a simple list of behaviours and index that with a byte, but I think you could parametrize behaviours opcode style.

NPCs and Objects should probably get their own post, especially with the recent buzz around Entity-Component-System designs. For the time being, I think the most important bits are already covered.

Anyway, we won't need most of that meta data for quite a while. We will first focus on getting tile maps to render in the first place, then we can worry about map objects, collision detection, the character controller, and all the other good stuff.
Personally, I'm excited this is finally packing some steam and look forward to continue work on this! Until then!