# Chunk Generation Performance in C#

I'm working on a game in C#, this game generate new chunk (infinite) when you move around. If I have > 1000 chunks in my list then it become laggy even though I only load the necessary chunks on my screen. Tried all things to improve the code but it did not improve.

Stopwatch ChunkDetect = new Stopwatch();
List<Chunks> allChunks = new List<Chunks>();
public readonly int sizeChunk = 800;

{
ChunkDetect.Restart();
ChunkDetect.Start();
int CamXCh = Convert.ToInt32(Math.Ceiling(-Convert.ToDouble(CameraX) / sizeChunk)),
CamYCh = Convert.ToInt32(Math.Ceiling(-Convert.ToDouble(CameraY) / sizeChunk));

int sizeX = Convert.ToInt32(Math.Ceiling(Convert.ToDouble(gameBox.Width) / sizeChunk)) + 4,
sizeY = Convert.ToInt32(Math.Ceiling(Convert.ToDouble(gameBox.Height) / sizeChunk)) + 4;

Random generation = new Random();
for (int chunkX = 0; chunkX < sizeX; chunkX++)
{
for (int chunkY = 0; chunkY < sizeY; chunkY++)
{
int xChunk = chunkX + CamXCh - 2,
yChunk = chunkY + CamYCh - 2;

Chunks currentChunk = allChunks.Where(i => i.positionX == xChunk && i.positionY == yChunk).FirstOrDefault();

if (chunkX == 0 || chunkX == (sizeX - 1) || chunkY == 0 || chunkY == (sizeY - 1))

if (currentChunk == null)
{
Color ColorBiome = Color.FromArgb(64, 233, 56);
string BiomeName = "Grass";
}
else
{
}
}
}
ChunkDetect.Stop();
}

class Chunks
{
public Color biomeType;
public Guid uid;
public int positionX, positionY, Size;
public string biomeName;
public List<CeldsChunk> MapChunk;

public Chunks(int x, int y, int size, Color biome, string BiomeName, bool loaded, int sizeCeld)
{

this.uid = new Guid();

// Posición y tamaño
this.positionX = x;         // Position
this.positionY = y;         // Position
int cSize = this.Size = size;         // Size

// Bioma
this.biomeType = biome;      // Biome Color
this.biomeName = BiomeName;  // Name of Biome

int sizeChunkInCeld = (cSize / sizeCeld);

List<CeldsChunk> celdsToChunk = new List<CeldsChunk>();

Random rd = new Random();
for (int CeldX = 0; CeldX < sizeChunkInCeld; CeldX++)
{
for (int CeldY = 0; CeldY < sizeChunkInCeld; CeldY++)
{
celdsToChunk.Add(new CeldsChunk(new Point(CeldX, CeldY, sizeCeld), this.biomeType));
}
}

this.MapChunk = celdsToChunk;
}

{
}

}

-
Welcome to Code Review! Can you please add the declaration of allChunks to your code? Can you also explain a bit about the purpose of your gameBox variable? –  Simon André Forsberg Jun 23 at 13:40
gameBox is only a control picture box. –  Lukas Häring Jun 23 at 14:27
Ok, I added the class Chunks and the list allChunks –  Lukas Häring Jun 23 at 14:28

Your allChunks is a List. The Linq query to get the chunk with the right coordinates is going to scan the entire list, and check each chunk. This is a linear process, and the performance depends on the number of chunks in the list. As the list grows, the performance decreases.

The solution is to index the chunks in a way that makes the lookup performance a constant-time operation (not dependant on the number of chunks).

The logical data structure for this is to use a Dictionary, and key the Dictionary on a value that is the coordinate. Thus, given a coordinate, you can easily find the Chunk.

Your chunks are indexed using int values for the X and Y coordinate. I would recommend using a long-value as the key, and to simply shift the X and Y coordinates in to the Dictionary... for example:

Dictionary<long, Chunks> indexChunks = ....

// merge both coordinates in to one unique key
// the y-coordinate is in the high-32-bits, the x-coord in the low 32 bits.
// this should probably be in a function.
long key = xChunk + ((long)yChunk << 32);

if (!indexChunks.containsKey(key)) {
}

Chunks currentChunk = indexChunks[key];


The Dictionary will convert the lookup process to a faster, scalable mechanism.

If you want to, you can create a more complicated key mechanism, but I would recommend that you keep the key as simple as possible.

-
Give me a hug :') thx :D –  Lukas Häring Jun 23 at 15:17
I would think that's obvious? the x,y values are 4 bytes each, this method preserves both bytes in 1 long value. Curious how @rolfl would handle a 3D array of chunks though ... thats a lot of bits!!! –  Wardy Jun 23 at 15:45
@bazola If the key was a short, then your x or y coordinates would be limited to 8 bits, which is 0 to 255 unsigned. That's not very big for an 'infinite' grid. With 64 bits you get the full range of 32-bit integers, which isn't infinite, but most players probably won't reach any limits. Example of combining them: Say X = 11111111 and Y = 00000000 your short key = 0000000011111111 –  Ryan Jun 23 at 15:50
@bazola - the core of my advice is to use a Dictionary with a useful key. In this case, two 32-bit coordinates fit nicely in single long, which makes it convenient, and keeps the same limitations as before (with the int-based x/y coords). For more complicated indexing, a more complicated key would be appropriate (as I suggested was an option). What the key would be, would depend on the circumstances, and the key would have to have all the right methods implemented, which long does already. –  rolfl Jun 23 at 15:51
I'd strongly recommend Sytem.Tuple as a dictionary key as long as there is no noticable drop in performance. Scales easily to 3D. Or use a custom struct like IntVector2D/IntVector3D as key. –  Sebastian Jun 23 at 18:15