I need a container that can reference 70 million+ texture2d/vector2 object sets

Question

I'm trying to find a method of storing references to roughly 70 million texture2d/vector2 sets. To clarify a bit, I need to be able to use 100 or so texture2d's and then assign them a vector2 XY value for a tile map that would have around 70 million tiles. I just need a refernce of which texture2d goes with which vector2. I will be dynamically/procedurally generating the tile/co-ordinate sets I just need a method of storing all of them now that won't blow up my ram. I tried to use a dictionary with the vector2 as the key and the texture2d as the value but that killed over on me with an OutOfMemoryException. So I then tried Wintellect Power Collections and used their MultiDictionary. But even if i assigned a texture2d as the only key and used the vector2 as the 70 million values to that key it still killed over with the same exception.

So I'm at a loss as to how I should proceed now. I just need to store the references for later access. I'm not trying to draw them to the screen or anything like that so I can't figure out why it takes 700mb of ram just for the dictionary. As an after thought I just realized that I've been letting these dictionaries resize themselves. Could that be the issue ?

I hope this was specific enough I've been up all night so I won't bother cleaning up and posting any code right now. If you think my code is the culprit and not my methods though, let me know and I'll post it for you. Looking forward to your answers.

EDIT: Ok here's the code I'm working with right now. I cleaned it up a bit but I know its not the greatest looking code. If you see any obvious problems or even inefficiencies I'd be happy to hear about them. Just don't bash me to badly since this is the first time I've worked with c# :)

The 70 million tiles come into play when WorldWidth & WorldHeight are set to 8400 each.

class MapMaker
{
    SpriteSheet spriteSheetMap;
    SpriteSheet spriteSheet1;
    SpriteSheet spriteSheet2;
    SpriteSheet spriteSheet3;
    SpriteSheet spriteSheet4;
    SpriteSheet spriteSheet5;
    SpriteSheet spriteSheet6;
    SpriteSheet spriteSheet7;
    SpriteSheet spriteSheet8;
    SpriteSheet spriteSheet9;
    SpriteSheet spriteSheet10;
    SpriteSheet spriteSheet11;
    SpriteSheet spriteSheet12;
    SpriteSheet spriteSheet13;
    SpriteSheet spriteSheet14;
    SpriteSheet spriteSheet15;
    SpriteSheet spriteSheet16;
    SpriteSheet spriteSheet17;
    SpriteSheet spriteSheet18;
    SpriteSheet spriteSheet19;
    SpriteSheet spriteSheet20;
    SpriteSheet spriteSheet21;
    SpriteSheet spriteSheet22;
    SpriteSheet spriteSheet23;

    Random rnd = new Random();

    int WorldWidth = 250;
    int WorldHeight = 250;
    List<int> sprites = new List<int>();
    int[][] TheGrid = new int[10][];
    int posX = 0, posY = 0, gridX = 0, gridY = 0;
    Dictionary<int, Texture2D> TileStorage = new Dictionary<int, Texture2D>();
    Dictionary<Vector2, Texture2D> SineSaver = new Dictionary<Vector2, Texture2D>();
    public void loadTiles(ContentManager Content)
    {
        spriteSheetMap = new SpriteSheet();

        spriteSheet1 = new SpriteSheet();
        spriteSheet2 = new SpriteSheet();
        spriteSheet3 = new SpriteSheet();
        spriteSheet4 = new SpriteSheet();
        spriteSheet5 = new SpriteSheet();
        spriteSheet6 = new SpriteSheet();
        spriteSheet7 = new SpriteSheet();
        spriteSheet8 = new SpriteSheet();
        spriteSheet9 = new SpriteSheet();
        spriteSheet10 = new SpriteSheet();
        spriteSheet11 = new SpriteSheet();
        spriteSheet12 = new SpriteSheet();
        spriteSheet13 = new SpriteSheet();
        spriteSheet14 = new SpriteSheet();
        spriteSheet15 = new SpriteSheet();
        spriteSheet16 = new SpriteSheet();
        spriteSheet17 = new SpriteSheet();
        spriteSheet18 = new SpriteSheet();
        spriteSheet19 = new SpriteSheet();
        spriteSheet20 = new SpriteSheet();
        spriteSheet21 = new SpriteSheet();
        spriteSheet22 = new SpriteSheet();
        spriteSheet23 = new SpriteSheet();

        spriteSheetMap.Map = Content.Load<Dictionary<string, Rectangle>>("Tiles/Map");
        TileStorage.Add(0, spriteSheet1.Sheet = Content.Load<Texture2D>("test2"));
        TileStorage.Add(1, spriteSheet1.Sheet = Content.Load<Texture2D>("Tiles/Amethyst"));
        TileStorage.Add(2, spriteSheet2.Sheet = Content.Load<Texture2D>("Tiles/Amethyst_N"));
        TileStorage.Add(3, spriteSheet3.Sheet = Content.Load<Texture2D>("Tiles/Aquamarine"));
        TileStorage.Add(4, spriteSheet4.Sheet = Content.Load<Texture2D>("Tiles/Aquamarine_N"));
        TileStorage.Add(5, spriteSheet5.Sheet = Content.Load<Texture2D>("Tiles/Citrine"));
        TileStorage.Add(6, spriteSheet6.Sheet = Content.Load<Texture2D>("Tiles/Citrine_N"));
        TileStorage.Add(7, spriteSheet7.Sheet = Content.Load<Texture2D>("Tiles/Diamond"));
        TileStorage.Add(8, spriteSheet8.Sheet = Content.Load<Texture2D>("Tiles/Diamond_N"));
        TileStorage.Add(9, spriteSheet9.Sheet = Content.Load<Texture2D>("Tiles/Dirt1"));
        TileStorage.Add(10, spriteSheet10.Sheet = Content.Load<Texture2D>("Tiles/Dirt2"));
        TileStorage.Add(11, spriteSheet11.Sheet = Content.Load<Texture2D>("Tiles/Emerald"));
        TileStorage.Add(12, spriteSheet12.Sheet = Content.Load<Texture2D>("Tiles/Emerald_N"));
        TileStorage.Add(13, spriteSheet13.Sheet = Content.Load<Texture2D>("Tiles/Peridot"));
        TileStorage.Add(14, spriteSheet14.Sheet = Content.Load<Texture2D>("Tiles/Peridot_N"));
        TileStorage.Add(15, spriteSheet15.Sheet = Content.Load<Texture2D>("Tiles/Ruby"));
        TileStorage.Add(16, spriteSheet16.Sheet = Content.Load<Texture2D>("Tiles/Ruby_N"));
        TileStorage.Add(17, spriteSheet17.Sheet = Content.Load<Texture2D>("Tiles/Sand"));
        TileStorage.Add(18, spriteSheet18.Sheet = Content.Load<Texture2D>("Tiles/Sapphire"));
        TileStorage.Add(19, spriteSheet19.Sheet = Content.Load<Texture2D>("Tiles/Stone1"));
        TileStorage.Add(20, spriteSheet20.Sheet = Content.Load<Texture2D>("Tiles/Stone2"));
        TileStorage.Add(21, spriteSheet21.Sheet = Content.Load<Texture2D>("Tiles/Stone3"));
        TileStorage.Add(22, spriteSheet22.Sheet = Content.Load<Texture2D>("Tiles/Topaz"));
        TileStorage.Add(23, spriteSheet23.Sheet = Content.Load<Texture2D>("Tiles/Topaz_N"));

        CreateMapKey();
    }

    private void CreateMapKey()
    {
        TheGrid[0] = new int[] { 0, 3, 14, 25, 36, 47, 58, 69, 80, 91 };
        TheGrid[1] = new int[] { 12, 4, 15, 26, 37, 48, 59, 70, 81, 92 };
        TheGrid[2] = new int[] { 23, 5, 16, 27, 38, 49, 60, 71, 82, 93 };
        TheGrid[3] = new int[] { 34, 6, 17, 28, 39, 50, 61, 72, 83, 94 };
        TheGrid[4] = new int[] { 45, 7, 18, 29, 40, 51, 62, 73, 84, 95 };
        TheGrid[5] = new int[] { 56, 8, 19, 30, 41, 52, 63, 74, 85, 96 };
        TheGrid[6] = new int[] { 67, 9, 20, 31, 42, 53, 64, 75, 86, 97 };
        TheGrid[7] = new int[] { 78, 10, 21, 32, 43, 54, 65, 76, 87, 98 };
        TheGrid[8] = new int[] { 89, 11, 22, 33, 44, 55, 66, 77, 88, 99 };
        TheGrid[9] = new int[] { 1, 13, 24, 35, 46, 57, 68, 79, 90, 2 };

        BaseTileset();
    }

    private void BaseTileset()
    {
        int hillLocation = 300, hillWidth = 120, hillHeight = 10;
        for (int i = 0; i < WorldHeight * WorldWidth; i++)
        {
            if (i % WorldHeight * 5 == 0)
            {
                hillLocation += rnd.Next(-40, 40);
                hillWidth += rnd.Next(-10, 10);
                if (hillWidth == 0) { hillWidth = 1; }
                hillHeight += rnd.Next(-5, 5);
            }
            Vector2 position = new Vector2(posX, posY);
            Texture2D tile = TileStorage[9];
            double sine = hillLocation + Math.Sin(posX / hillWidth) * hillHeight;
            double cosine = hillLocation + Math.Cos(posX / hillWidth) * hillHeight / 2;
            if (posY <= sine || posY < cosine)
            {
                tile = null;
            }
            if (tile != null)
            {
                SineSaver.Add(position, tile);
                sprites.Add(TheGrid[gridY][gridX]);

            }

            posY += 20;
            if (posY > (WorldHeight - 1) * 20) { posY = 0; posX += 20; }
            gridX = posX / 20 % 10;
            gridY = posY / 20 % 10;
        }

    }

    public void DrawLevel(SpriteBatch spriteBatch, GraphicsDeviceManager graphics)
    {
        spriteBatch.Begin();
        int i = 0;
        foreach (KeyValuePair<Vector2, Texture2D> entry in SineSaver)
        {
            spriteBatch.Draw(entry.Value, entry.Key, spriteSheetMap[sprites[i]], Color.White);
            i++;
        }
        spriteBatch.End();
    }
}

Answer 1

I'd recommend looking into the flyweight pattern (http://en.wikipedia.org/wiki/Flyweight_pattern)

If you know the width and height of each tile, you can calculate the Vector2 position of each tile - it's deterministic based on an index so it doesn't need to be stored. The only data that's needed for each tile is one int for the index, and a 'type' identifier which could be as small as a single byte.

70 million * (4 + 1 )bytes = 333.786011 megabytes

EDIT 1: Elaborating slightly..

Lets say we have a 3x3 grid of tiles - we know there are 9 tiles in total, so we assign each tile an index 0-8..

Tile[] tiles = new Tile[9]

for (int i = 0; i < 9; i++)
    tiles[i].Index = i;

Knowing that each grid row is 3 tiles across, and each column 3 tiles down, we can use the modulo and division operators to get the row & column for any tile index...

Tile tile = getSomeTile();

int column = tile.Index % 3; // = column 1
int row = tile.Index \ 3; // = row 1 - tile 4 is in the middle :)

knowing the width and height of each tile (lets say 10 pixels) we can now calculate the exact position of tile 4:

Vector2 position = new Vector2
{
    X = 10f * column,
    Y = 10f * row
};

EDIT 2: In response to comment...

Your Tile object would need to contain a type identifier like so:

struct Tile
{
    int Index; // The tiles index in the map [0 - 70 million].
    byte TileTypeId; // An identifier for a tile type.
}

class TileType // This is the flyweight object..
{
    Texture2D Texture; // Gets the texture reference for the tile type...

    // any other information about the tile ie. is it collidable? is it water? etc..
}

Then when it comes to drawing tiles...

Tile tile = tiles[someIndex];

TileType type = tileTypes[tile.TileTypeId];  // tileTypes could be a dictionary...

Vector2 position = this.CalculateTilePosition(tile.Index); // Calculate the position as above...

spriteBatch.Draw(type.Texture, position);

EDIT 3: In response to serialization comment...

Serializing the tile grid should be quite easy, it's just a looong sequence of bytes. Assuming the tiles are stored in order, we already know the tiles index number, so that doesn't need to be stored in the file.

Back to the 3x3 grid example:

Example binary data file:
0xF4 0x15 0x5A 0xB5 0x00 0x61 0xEE 0xA3 0x39

BinaryReader reader = OpenSomeBinaryFile();

for (int i = 0; i < (3 * 3); i++)
    tiles[i] = new Tile { Index = i, TileTypeId= reader.ReadByte() };

// easy to optimize by reading bigger binary chunks (say an Int64) and bit shifting to get the individual bytes...

// If you happen to have reasonbly large series of tiles with the same type id (byte), the file will be quite well suited to compression on disk, which is a bonus :)

Answer 2

In order to avoid the enourmous memory issues (70 million tiles even at 1 byte per tile is 70Mb) you may want to consider some sort of streaming implementation. At its most basic something like a WorldChunk that contains NxN tiles, and a link to another WorldChunk (either a direct link, or just an ID or String to identify it). Each of these chunks could have an OnEnterFrame and OnExitFrame method.

In the OnEnterFrame method you could invoke a load from file on all linked chunks that would populate them with data from your game files, and OnExit you would destroy them. In this sort of case you would only keep a small set of chunks around, a subset of your 8400x8400 world. 3x3 or 5x5 are good choices. Ideally these chunks would fill the screen or slightly more than the screen.

Pseudocode concept follows:

class WorldChunk
{
    String MyName;
    String[8] LinkedWorldChunkFileNames; 
    Tile[32,32] Tiles;
    void OnEnterFrame()
    {
        LoadWorldChunkFromName(MyName);
        foreach(name in LinkedWorldChunkFileNames)
        {
            LoadWorldChunkFromName(name);
        }
    }

    void LoadWorldChunkFromName(string name)
    {
        string fileData = LoadFromFile(name); //this should probably be done earlier, 
                                              //when a neighbor loads it should load
                                              // offscreen nieghbors
                                              //files then parse them on its own enter                                        
                                              //frame
        Tiles = ParseToTiles(fileData); //your own file parsing here
    }

    void OnExitFrame()
    {
        Tiles.Clear();
    }
}

I have not implemented anything like this yet, but it is something i am starting to give thought too since i need to do something very similar in 3d.

Answer 3

So I dunno if your spritesheets have multiple tiles within them or whatnot... but you could do something like:

class GameTile 
{
    private Vector2D _vec;
    //These integers should be sized to fit your needs
    //int8 = up to 256 tilesets
    //int16 = up to 65536 tiles in a set
    private int8 _tileSet;
    private int16 _tileIndex;

    //This is the tiles position in the world
    public Vector2D Position { get { return _vec; } }
    //This is the index of the tileset in the array of all tilesets
    public int8 CurrentTileset { get { return _tileSet; } }
    //This is the flattened index (row * width + column) 
    //of the tile in the tileset
    public int16 CurrentTile { get { return _tileIndex; } }        
}

Answer 4

Why don't you just make a class that extends Vector2, but takes an extra variable in the constructor that says which Texture2D belongs to it? This way everything would be stored in the objects itself, which is quite efficient. So you probably don't need any other data structure!

Edit: Or even just make an array of all possible textures, and just give an index to your custom object. This way you don't have to copy the whole Texture2D object every time!

Edit2: As (as I should have known and has been pointed out to me) you cannot extend to a Vector2, I would do something like this:

 public class TextureVector2D
 {
     public Vector2D vector;
     public int textureIndex;

     public TextureVector2D( Vector2D v, int tI )
     {
          vector = v;
          textureIndex = tI;
      }
 }