# More Efficient Data Structure for Large Layered Tile Map

It seems like the popular method is to break the map up into regions and load them as needed, my problem is that in my game there are many AI entities other than the player out performing actions in virtually all the regions of the map. Let's just say I have a 5000x5000 map, when I use a 2D array of byte's to render it my game uses around 17 MB of memory, as soon as I change that data structure to a my own defined MapCell class (which only contains a single field: byte terrain) my game's memory consumption rockets up to 400+ MB. I plan on adding layering, so an array of byte's won't cut it and I figure I'd need to add a List of some sort to the MapCell class to provide objects in the layers. I'm only rendering tiles that are on screen, but I need the rest of the map to be represented in memory since it is constantly used in Update.

So my question is, how can I reduce the memory consumption of my map while still maintaining the above requirements? Thank you for your time!

Here's a few snippets my C# code in XNA4:

public static void LoadMapData()
{
// Test map generations
int xSize = 5000;
int ySize = 5000;
MapCell[,] map = new MapCell[xSize,ySize];
//byte[,] map = new byte[xSize, ySize];

Terrain[] terrains = new Terrain[4];
terrains[0] = grass;
terrains[1] = dirt;
terrains[2] = rock;
terrains[3] = water;

Random random = new Random();

for(int x = 0; x < xSize; x++)
{
for(int y = 0; y < ySize; y++)
{
//map[x,y] = new MapCell(terrains[random.Next(4)]);
map[x,y] = new MapCell((byte)random.Next(4));
//map[x, y] = (byte)random.Next(4);
}
}

testMap = new TileMap(map, xSize, ySize);
// End test map setup

currentMap = testMap;
}

public class MapCell
{
//public TerrainType terrain;
public byte terrain;

public MapCell(byte itsTerrain)
{
terrain = itsTerrain;
}

// the type of terrain this cell is treated as
/*public Terrain terrain { get; set; }

public MapCell(Terrain itsTerrain)
{
terrain = itsTerrain;
}*/
}

• I plan on adding layering, so an array of byte's won't cut it Why not? – Cypher Nov 7 '12 at 18:16
• I'm sorry for my poor wording. I need to be able to have a re sizable list of objects at each cell (which may be empty for the majority of cells), so it would seem a simple byte array wouldn't work, but perhaps there is a hybrid implementation that I'm not seeing? What did you have in mind? – Stupac Nov 7 '12 at 18:30
• 5000x5000? All visible at the same time? If no, why are you loading it that way? Split it up into small, screen-sized chunks and stream/decompress those as necessary. – snake5 Nov 7 '12 at 18:56
• If you requirement is to simulate the whole world all the time, then you will need to load the whole world into memory. You can't avoid this. If you don't mind simulating your world with a degree of error, you can interpolate AI actions and only load the area around the player. For example, make the AI simpler in a further region and don't simulate each tick, just simulate entire regions for several ticks all at once. This way you can load a region, simulate up to the current game tick, and then compress back to disk to save memory. – kurtzbot Nov 7 '12 at 19:11
• Don't forget that just because it is cool to have giant seamless worlds right now, that doesn't mean there aren't other and potentially better ways to manage the problem. Look to history. Sim Ant was able to, on very limited hardware, simulate an entire backyard, which on ant scales is continent sized, including depth. Did it with 3 phases: The backyard is broken into about 64 easy to simulate nodes that the player can only inhabit one of, the surface is a tiny set of tiles with holes that are linked lists to the underground's surface, which itself is a 2D plane. Great depth, small space. – DampeS8N Nov 8 '12 at 15:14

Don't use a class for MapCell.

Classes are allocate on the heap. Every MapCell hence has overhead associate with memory management (bookkeeping of the allocations, padding, etc.). There's also the overhead of all the internal data that every object instance has like the "vtable" handle (which isn't much but it adds up) and you don't need the featurs those provide.

Use a struct. It allows you to store any custom fields you want, has no additional object space overhead, and is allocated in-place in the List's memory buffer so it has no additional memory manager overhead.

Additionally, your code will be a fair bit faster, since iterating over the List will be much quicker as you're no longer suffering indirection overhead and poor cache utilization you get when you allocate 5000x5000 individual objects spread all over memory.

Note that the other suggestions you received to spatially subdivide your world and perform logic level-of-detail filtering are also good, and you should do that in addition to converting MapCell to a struct.

You can also look into using a sparse cell approach with a hierarchy of cells.

• Quantitatively, a 2D array of objects replaces a byte in the original map with a pointer to an object, plus a byte of data, plus slack for alignment to 4 or 8 bytes, plus (probably) a hidden pointer in each object. 20 times the memory, no added functionality. – Lorenzo Gatti Sep 5 '16 at 13:25

This is a difficult problem because you have a large world which you want to update and have AI running around, regardless of where the player is. Since you need to lower memory while keeping the above true you will have to either raise your memory requirement, or cut some corners. I will explain how to cut those corners.

For simplicity, I assume a 100x100 grid. Assume the player can reasonably see an area of 10x10. Since this area easily fits into memory we will fully simulate this region, which I will call the player region.

Now, for all area outside of the player region will be called non-visible space. Since the player can't see this area, updates don't need to be instant, but as per the requirements, we do need to keep updating this region. Since we can't fit all of it into memory, the usual trick is to break it up into chunks and load what you need. So we break the rest of the 90x90 region into equal sized chunks for convenient loading. These chunks are then rotated into a single (or multiple if you have mutliple threads) buffer. The trick here is to now fully/partially simulate this region up to the current game tick so as to keep the region relevant to changing AI/physics. Once the region is simulated, just write (compress as needed) the region back to disk.

This works great so long as the player doesn't move to those regions. What if he does? A hierarchical approach may be needed. Instead, we want to update non-visible regions close to the player more often than those which are further away. You may have to play with this a bit, but maybe we choose to update a close non-visible region two or three times for every further away non-visible region. This way if the player moves into a previously non-visible region, little extra work is needed to bring that region up to sync.

Keep in mind that AI/effects that happen on a boundary between regions. You may need to save those updates as a "resolve all boundary" update loop. Since you want each region to interact with another you will have to play around with the most appropriate way to propagate effects from one region to another.

You could also watch the player behavior. If they are moving close to an edge region, maybe you will alter now often those other regions get updated to avoid having the player wait while the game simulates up to the current tick.

However, this approach is only necessary because you have a very computationally difficult requirement of a large area that always needs to be updated with potentially complex AI/effects. I would look into how important that requirement is for core-gameplay and reevaluate what a more realistic requirement would be. As this approach opens a lots of cans of worms.

• +1 for "I would look into how important that requirement is for core-gameplay and reevaluate what a more realistic requirement" – Luke B. Nov 7 '12 at 23:33

map[x,y] = new MapCell((byte)random.Next(4));


Each of those calls generates a new object, even if that object is identical to a million others already in the game.

What you can use to alleviate the problem is called the "Flyweight Pattern." In this case, your MapCell instances become immutable (similar to, for example, String instances), so you'll have to store the changeable state - like entities - in some other data structure. Similarly, if you want to define some behaviour in your MapCell instances, only the behaviour which is common to all of them can be defined as its class methods.

An example using a static Factory and a private constructor; this makes your MapCell class essentially sealed, aside from hard-coded exceptions.

using System.Collections.Generic;

public class MapCell
{
private static readonly Dictionary<byte, MapCell> terrainCells
= new Dictionary<byte, MapCell>();

public static MapCell ForTerrain(byte cellTerrain)
{
MapCell result = null;
if( terrainCells.ContainsKey(cellTerrain) )
{
result = terrainCells[cellTerrain];
}
else
{
// Possibly add a switch-case here
// for hardcoding special terrain subclasses
result = new MapCell(cellTerrain);
}
return result;
}

private MapCell(byte itsTerrain)
{
terrain = itsTerrain;
}
}


Instead of the call above, you now use ...

map[x,y] = MapCell.ForTerrain((byte)random.Next(4));


An alternative, which allows for extending the MapCell class with your own and creating new terrain types at runtime (for example from configuration files) would have them register themselves in their constructor. You use them essentially the same way as above, though MapCell.ForTerrain(...) can now return null, which you have to deal with somehow (assuming that tile is empty, creating a new tile terrain type on the fly and so on).

using System.Collections.Generic;

public class MapCell
{
private static readonly Dictionary<byte, MapCell> terrainCells
= new Dictionary<byte, MapCell>();

// Pre-defined MapCell types
public static readonly MapCell TYPE0 = new MapCell((byte)0);
public static readonly MapCell TYPE1 = new MapCell((byte)1);
public static readonly MapCell TYPE2 = new MapCell((byte)2);
public static readonly MapCell TYPE3 = new MapCell((byte)3);

public static MapCell ForTerrain(byte cellTerrain)
{
MapCell result = null;
if( terrainCells.ContainsKey(cellTerrain) )
{
result = terrainCells[cellTerrain];
}
else
{
result = null;
}
return result;
}

protected MapCell(byte itsTerrain)
{
terrain = itsTerrain;
// Register ourselves
// You should probably throw a RTE
// if there's already a terrain registered here
}
}


(Note: Code untested, aside from looking if Unity throws any fits when compiling it.)

as soon as I change that data structure to a my own defined MapCell class (which only contains a single field: byte terrain) my game's memory consumption rockets up to 400+ MB.

Objects in managed languages have lots of extra overhead, so when you have very large collections of them, you will notice that overhead.

I plan on adding layering, so an array of byte's won't cut it and I figure I'd need to add a List of some sort to the MapCell class to provide objects in the layers.

I would argue that the most efficient data structure for your tile rendering would be an array of byte, provided that you do not have more than 256 different types of tiles (although these days, an array of short or int isn't going to kill you either).

You state that you cannot use an array of bytes because you want to implement layering, but I disagree. You could store each layer as a separate array, and simply render them in order.

I would also advise against trying to store your game entities within your tiles. If for some reason your game entities need to know which tile they are standing over, simply keep the tile's coordinates stored in your entity.

You may also want to consider using jagged arrays (byte[][]), instead of multidimensional arrays (byte[,]). For such a large collection of tiles that you will have to iterate over each frame, the additional performance benefits of using jagged arrays may prove to be worthwhile.

• That makes since, that was kinda what my gut was telling me, but I thought I might be missing some other way of doing things. I can work with this though, thanks a bunch! – Stupac Nov 7 '12 at 19:31

Store the tilemap with byte arrays. If byte is not enough for you, use more byte arrays or short/int arrays. Each object has such a big memory overhead in C# (and Java) that you should use primitive arrays for large sizes. Store the objects in other data structures, not per tile.