# Alternative to 2D array in a tiled-map structure

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 ?

-

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.

-
Yay, 3000 rep. :) –  The Communist Duck Mar 11 '11 at 15:52
I don't feel that this necessarily answers OP's question. That is the way you store it, but is it in an array? Vector? –  Kenny Worden Feb 7 '13 at 20:45

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.

-

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.

-
With C++ TR1 one can use std::array for fixed size with "no" performance penalty and get potentially nicer iterator semantics. –  user744 Mar 2 '11 at 22:45
Another reason to use 2d arrays (using C arrays or std::vector or std::array, or the equivalent in other languages) is that they're rather compact. The percentage of space used to store game data (out of the total size of the data structure) is close to 100% with 2d arrays, but often much lower with sparse arrays, linked lists, hash tables, arrays of pointers, or other structures. This matters less in PC games but many platforms are memory limited, and compact representations help with load times and the cpu cache. –  amitp Mar 5 '11 at 6:07

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.

-
There's no advantage to using a quad-tree for this rather than simply chunking the map at fixed sizes, and lots of gained complexity. –  user744 Mar 2 '11 at 16:12
Ah, didn't explain that one well - chunked sections works better. –  Leniency Mar 2 '11 at 18:02

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.

-