# 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? – Kenneth 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
• What do you mean by "you don't need an alternative?" Sometimes a linked list is better, sometimes a 1D array, sometimes a 2D array, etc. Are you suggesting there's only one way to do something in a topic as vast and complex as game programming? 😳 – jdk1.0 Dec 27 '19 at 20:16
• @jdk1.0 I can't think of any time you'd want a linked list for a 2D structure. And the difference between a 2D array and 1D one in C++ is mostly irrelevant since you're gonna get 1 lump of contiguous memory either way. The reason this question doesn't get asked much is because the simple and obvious answer is almost always the best one. – Kylotan Jan 20 at 16:17

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

If it's just a simple tiled game on a grid like a turn-based strategy game, then something like this:

struct Tile
{
// Stores the first entity (enemy, NPC, item, etc) on the tile.
int first_entity;
...
};

struct Entity
{
// Stores the next entity on the same tile or
// the next free entity index to reclaim if
// this entity has been freed/removed.
int next;
...
};

struct Row
{
// Stores all the tiles on the row.
vector<Tile> tiles;

// Stores all the entities on the row.
vector<Entity> entities;

// Points to the first free entity index
// to reclaim on insertion.
int first_free;
};

struct Map
{
// Stores all the rows in the map.
vector<Row> rows;
};


Some people might wonder why I choose to store separate vectors for each map row. It's to improve spatial locality as we traverse the entities standing on a given tile. When we store a separate vector per row, then all the entities for that row might fit in L1 or L2, whereas they might not even fit in L3 if we stored one entity container for all entities in the entire map. That still tends to be quite cheap compared to, say, storing a separate vector per tile.

To get, say, the tile at (102, 72), we do this:

Row& row = map.rows[72];
Tile& tile = row.tiles[102];


To traverse the entities on the tile we do:

int entity = tile.first_entity;
while (entity != -1)
{
// Do something with the entity on the tile.
...

// Advance to the next entity on the tile.
entity = row.entities[entity].next;
}


Naturally for "separate container per row" type implementation to benefit most, your tile access patterns should try to process all the columns of interest for a row before you move to the next, not so much zig-zagging back and forth from one row to the next and back again.

Insertion of an entity to a tile would be like this:

int Map::insert_entity(Entity ent, int col_idx, int row_idx)
{
Row& row = rows[row_idx];

int ent_idx = row.first_free;
if (ent_idx != -1)
{
row.first_free = row.entities[ent_idx].next;
row.entities[ent_idx] = ent;
}
else
{
ent_idx = static_cast<int>(row.entities.size());
row.entities.push_back(ent);
}

Tile& tile = row.tiles[col_idx];
row.entities[ent_idx].next = tile.first_entity;
tile.first_entity = ent_idx;
return ent_idx;
}


... and removal:

void Map::remove_entity(int ent_idx, int col_idx, int row_idx)
{
Row& row = rows[row_idx];
Tile& tile = row.tiles[col_idx];
if (tile.first_entity = ent_idx)
tile.first_entity = row.entities[ent_idx].next;

row.entities[ent_idx].next = row.first_free;
row.first_free = ent_idx;
}


Main reason I like this solution is that we avoid storing too many vectors (ex: one vector per tile: too many for big maps), but not so few that iterating through the entities on a given tile leads to epic strides across the memory address space and lotsa cache misses. One entity vector per row strikes a nice balance there.

This is assuming that you have things like buildings and enemies and items and treasure chests and players standing on the tiles and that a lot of the time spent in the game logic is accessing the entities standing on those tiles as well as checking what entities are on a given tile. Otherwise I'd use a 1D array approach with a single vector for all tiles as that would be the most efficient for just accessing tiles. You can then get a tile using: tiles[row*num_cols+col] Use a one-dimensional array if in doubt since it will let you traverse things in a straightforward sequential order without nested loops and only require one heap allocation to allocate the entire thing.

Just in general the separate dynamic array per row is something I've found to reduce cache misses a lot in cases in cases where your grid is storing elements inside of it. Of course if it doesn't and your grid is just like an image containing pixels, then it makes no sense to use a separate dynamic array per row. As a recent benchmark where I optimized something grid-like this way (before it was just using one giant array for everything; I optimized it to store a separate dynamic array per row after seeing lots of cache misses in vtune):

Before:

--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {1.799000 secs}
mem use after 'insert': 479,508,224 bytes

8560 cells, 1000000 rects
finished test_grid: {1.919000 secs}


After:

--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {0.310000 secs}
mem use after 'insert': 410,546,720 bytes

8560 cells, 1000000 rects
finished test_grid: {0.361000 secs}


And I used the same kind of strategy described above. As a bonus you can also see it reduced memory usage because the vectors storing the entities tend to make a tighter fit if you store one per row instead of one for the entire map.

Note that the above test to insert a million entities to the grid might seem like it's taking a long time and lotsa memory even after the optimization. That's because each entity I'm inserting takes many tiles, averaging about 100 tiles per entity (10x10 average size). So I'm inserting each of the million entities to an average of 100 grid tiles which makes it more like inserting 100 million entities than a measly 1 million entities. It's stress testing a pathological case. If I'm just inserting a million entities that occupy 1 tile each, I can do it in milliseconds and just using about 16 megabytes of memory.

In my case I often even have to make pathological cases efficient since I work in VFX instead of gaming. I can't tell artists, "Make your content this way for this engine," since the whole point of VFX is to let the artists create the content however they want. They then optimize it before they export to their favorite engine, but I have to deal with the unoptimized stuff which means I do often have to efficiently handle the pathological cases, like an octree having to efficiently deal with massive triangles that span the entire scene since the artists create such content and frequently (far more often than one might expect). So anyway, that above test is testing something that should never happen and that's why it takes almost a third of a second to insert a million entities, but in my case those "should never happen" things happen all the time. So the pathological case isn't a rare case for me, though the row-based optimization described above equally optimizes both the common-common case and the common-pathological case.

As a side bonus, this also allows you to insert and remove entities for multiple rows simultaneously in parallel using multithreading without locking, since you can now safely do it given that each row has a separate entity container provided that two threads aren't trying to insert/remove stuff to/from the same row simultaneously.

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.