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