# How to store “chunks” of tiles or How to make my implementation work

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

-

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.

-
I found two errors in your code but fixed them in the x for loop make the x >= rootPos.X to X <= rootPos.X, and it gives out a world position not a chunk position. It is currently lagging my came but i think I know a fix. – ceriosNerd Mar 7 '12 at 0:33
Oops, it is always outputting the same world coordinates somehow? – ceriosNerd Mar 7 '12 at 0:38
Sorry, I wasn't sure how your ChunkPosition was defined. I assumed chunk positions were root positions for the chunk. For example for chunks 32 blocks big, if a chunk had a ChunkPosition of (0,0), the chunk in the X Plus direction would have a ChunkPosition of (32,0) – Byte56 Mar 7 '12 at 0:44
And the other error was me bitshifting the wrong direction.... – ceriosNerd Mar 7 '12 at 0:48
OK, let me know if that works for generating a valid list. – Byte56 Mar 7 '12 at 1:06

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 }
``````

The AdjacencyArray for chunk 2 should be

``````AdjacencyArray = { null, null, null, null, null, null, Chunk3, Chunk1 }
``````

The AdjacencyArray for chunk 3 should be

``````AdjacencyArray = { null, Chunk1, Chunk2, null, null, null, null, null }
``````

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][ ]
[ ][ ][ ][ ]    [ ][ ][ ][ ]
``````
-
Your AdjacencyArray has 8 neighbors but you are only representing the 4 neighbors in your AdjacencyArray for chunk2 and chunk3. chunk1 looks fine though :) – Luis Estrada Mar 6 '12 at 22:37
Thanks fixed it :) – ClassicThunder Mar 6 '12 at 22:41