More Efficient Data Structure for Large Layered Tile Map

Question

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;
    }*/
}

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.