Alternative to 2D array in a tiled-map structure

Question

After searching for a long time, I'm surprised this question was not asked yet. In a 2D, tiled-map game, how do you handle the map ? I'd be glad to have your point of view in any languages, though I'm more interested in C++ implementations.

A 2D array, a 2D vector, a class handling a linked-list with ad hoc computing to handle coordinates, a boost::matrix... ? What solution do you use and why ?

Answer 1

One thing I've done for an RPG style map - that is, houses you can enter, dungeons, etc is have 4 main structures: a Map, an Area, a Zone, and a Tile.

A Tile is obviously a tile.
A Zone, or a chunk, or whatever, is an area of X by Y tiles. This has a 2D array.
An Area is a collection of Zones. Each Area can have different Zone sizes - the overworld may use a 32x32 Zone, whereas a house may have one 10x20 Zone. These are stored in dictionaries (so I can have Zone (-3, -2)).
A Map is a collection of Areas, all of which are linked to each other.

I felt this allowed me greater flexibility rather than having one huge map.

Answer 2

I'll explain what I do for a specific case of tiled maps: this is for effectively infinite maps, ones where the world is generated on demand but you need to save modifications to it:

I define some cell size "N" and split the world up into squares/cubes "NxN" or "NxNxN"

A cell will have a unique key. I generate mine by hashing or using directly the formatted string:"%i,%i,%i",x,y,z (where x,y,z are the world coordinates of the start of the cell divided by N)

Storing the tiles indices in arrays is straightforward as you know you have NxN tiles or NxNxN tiles. You also know how many bits your tile type takes up. Just use a linear array. It makes loading and saving/releasing the cells simpler to handle too.

Any accessor merely needs to generate the key for the cell (to make sure it's loaded/generated, then get the pointer to it), then use a sub index to look inside that cell. to find the tile value at that specific point.

Extracting the cell by its key, I currently use a map/dictionary as generally I process whole cells at once (wouldn't want to know how bad a hit it would be to do a dictionary lookup per tile, eek).

Another point, I don't keep mobs / players in the cell data. The actively dynamic stuff needs its own system.

Answer 3

The question probably wasn't asked because you don't need an alternative. For me, it's:

Tile tiles[MAP_HEIGHT][MAP_WIDTH]; if the size is fixed.

std::vector<Tile> tiles(MAP_HEIGHT*MAP_WIDTH); otherwise.

Answer 4

It would depend on the style of game and map honestly. For a relatively small rectangular tile map, I'd probably just stick with a 2d array. If the map was very irregularly shaped (lots of empty gaps), a wrapper around linked lists that provides O(1) indexing would probably be my choice.

An integer indexed array gives you a 2147483647^2 2d array. That's pretty big, but exceeds what you'd what to load into memory. If the map was to be large scale, another thing to look at is dividing the map into chunks. Each chunk is fixed size and contains a sub-array of tiles that could be loaded/unloaded as needed to keep memory lower.

Answer 5

I am toying with a 3D engine where the world is a mesh.

I am importing some 2D maps+tilesets that have previously been made.

And when I do, I convert it to a 3D mesh and put all the tiles into a single texture.

This draws substantially faster.

I would perhaps keep the map around in a 1D array of w*h if I had to keep it's tile concept, but my answer is that its liberating to move beyond the 2Dness.

And, if you have performance problems whilst using GPU drawing, keeping the graphical representation as a single texture - with a mesh if its got variable heights - can really speed it up compared to drawing each tile individually.