need resize-able datatype for xy coordinate system

Question

I am coding a program to modify select chunks of a simple 3d game map (minecraft). The map can be theoretically very large so loading the entire map is out of the question. I want to only load each 16x16 sized chunk once and have those chunks in memory should I need to modify it again. I need a data structure to store these portions in memory in an (x,y) coordinate fashion while being able to resize this data structure as needed and keep it orderly so I can find specific chunks. I am at a loss on what data structure I could use to meet my requirements. I am hoping someone could make some suggestions. I am coding in c#.

Answer 1

I recommend a top level Map data structure that has an indexer based on a Coordinate. Next add a Chunk data structure which is like a miniature map. In the accessors for the Map indexer, check whether the chunk that contains the coordinate is loaded and if not load it. Then delegate the Map indexer to the Chunk indexer. The Map can keep track of which chunks are loaded using a Dictionary. Finally, you need to unload chunks based on a strategy, e.g. least recently used.

With this infrastructure in place you can then use the Map as a virtual infinite plane.

Here's some (untested) pseudo-code to get you started:

public struct Coordinate : IEquatable<Coordinate>
{
    public int X { get; set; }
    public int Y { get; set; }

    public bool Equals(Coordinate other)
    {
        return X == other.X && Y == other.Y;
    }

    public override int GetHashCode()
    {
        return X ^ Y;
    }
}

public class Data
{
    // Map data goes here.
}

public class Chunk
{
    public Coordinate Origin { get; set; }
    public Data[,] Data { get; set; }

    public Data this[Coordinate coord]
    {
        get { return Data[coord.X - Origin.X, coord.Y - Origin.Y]; }
        set { Data[coord.X - Origin.X, coord.Y - Origin.Y] = value; }
    }
}

public class Map
{
    private Dictionary<Coordinate, Chunk> map = new Dictionary<Coordinate,Chunk>();

    public Data this[Coordinate coord]
    {
        get
        {
            Chunk chunk = LoadChunk(coord);
            return chunk[coord];
        }
        set
        {
            Chunk chunk = LoadChunk(coord);
            chunk[coord] = value;
        }
    }

    private Chunk LoadChunk(Coordinate coord)
    {
        Coordinate origin = GetChunkOrigin(coord);
        if (map.ContainsKey(origin))
        {
            return map[origin];
        }
        CheckUnloadChunks();
        Chunk chunk = new Chunk { Origin = origin, Data = new Data[16, 16] };
        map.Add(origin, chunk);
        return chunk;
    }

    private void CheckUnloadChunks()
    {
        // Unload old chunks.
    }

    private Coordinate GetChunkOrigin(Coordinate coord)
    {
        return new Coordinate { X = coord.X / 16 * 16, Y = coord.Y / 16 * 16 };
    }
}