How to store "chunks" of tiles or How to make my implementation work

Question

I asked a previous question about the loading and unload of chunk data and people noted that my way of storing chunks is weird and I was wondering how I would go about doing it properly. @Byte56 suggested using a linked list or adjacency list but i have no clue how to do those even after searching google/stackoverflow. Any advice to a person new to xna programming?

Source

Previous Question

Answer 1

I think ClassicThunder is heading in the right direction, but he/she may be at the wrong level. Keeping an adjacency list at the Chunk level is fine, but it's not really the solution you're looking for to manage the loaded chunks at the World level.

If you're keeping the actual data for your chunks in the dictionary structure, all you really need is an array of keys, in your case chunk positions. This is actually fairly simple after I've thought about it more. For knowing which chunks should be loaded, all you really need is the root position of the chunk the camera is currently over. Now, you know what size each chunk is and you can figure out how many chunks you need to be visible at a time. So once you have the root position, it's really just a few loops to give you the positions of all the other chunks needed.

So for example, say you decide that having 9 chunks loaded at a time works well enough. This means the chunk the camera is currently over, plus all chunks that touch it horizontally and diagonally. That would mean the view area is no larger than a single chunk.

int range = 1; //This is the number of chunks from the center chunk to load
ChunkPosition rootPos = GetChunkRootAt(Camera.Position.X, Camera.Position.Y);
ChunkPosition[] Positions = new ChunkPosition[9];
int i = 0;
for(int y = rootPos.Y + (ChunkSize.Y * range); y >= rootPos.Y - (ChunkSize.Y * range); y -= ChunkSize.Y){
    for(int x = rootPos.X - (ChunkSize.X * range); x <= rootPos.X + (ChunkSize.X * range); x += ChunkSize.X){
        Positions[i++] = new ChunkPosition(x,y);
    }
}

I'm just running this in my head so I'm probably off by one or something, but I believe the above will fill the array with this configuration:

[0][1][2]
[3][4][5]
[6][7][8]

Now you have a list of chunks that should be loaded. Use that list to update your dictionary.

Answer 2

What we were recommending was treating each chunk as a node in an graph. The modification to your chunk data structure necessary to do this adjacency list. Note the list part doesn't dictate a List necessarily, I suggest a array for performance reasons and their simplicity.

The data structure should contain at least the two below fields.

public class Chunk {
    private Point position
    private Tile Tiles[]
    private Chunk AdjacencyArray = new Chunk[8]
}

This allow for the below. '@' is the current chunk. 0 is the chunk to the top left of the current chunk. 1 is the chunk above the current chunk. So on and so forth all indexes of the above AdjacencyArray field.

[0][1][2]
[7][@][3]
[6][5][4]

Now assuming we have multiple chunks 1, 2, and 3 in a grid

[ ][ ][ ][ ]
[ ][1][2][ ]
[ ][3][ ][ ]
[ ][ ][ ][ ]

The AdjacencyArray for chunk 1 should be

AdjacencyArray = { null, null, null, Chunk2, null, Chunk3, null, null }
AdjacencyArray[3] = Chunk2
AdjacencyArray[5] = Chunk3

The AdjacencyArray for chunk 2 should be

AdjacencyArray = { null, null, null, null, null, null, Chunk3, Chunk1 }
AdjacencyArray[6] = Chunk3
AdjacencyArray[7] = Chunk1

The AdjacencyArray for chunk 3 should be

AdjacencyArray = { null, Chunk1, Chunk2, null, null, null, null, null }
AdjacencyArray[1] = Chunk1
AdjacencyArray[2] = Chunk2

I'm hoping that illustrates that an adjacency array merely stores a reference to the chunk. And the index of that reference describes where referenced chunk is located related compared to the current chunk.

Now lets say the camera is in chunk 2 and moves down. We now have to add 4. We then have to update all old chunks (O) so they and the new chunks (N) point towards each other. There are various ways to do this none of them particularly elegant. In fact I kind of like you idea of the dictionary with the location as a hash. It would allow the linking to happen in what is basically O(8).

[ ][ ][ ][ ]    [ ][ ][ ][ ]
[ ][1][2][ ]    [ ][O][O][ ]
[ ][3][4][ ]    [ ][O][N][ ]
[ ][ ][ ][ ]    [ ][ ][ ][ ]