Chunk Generation Performance in C#

Question

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;
private void loadChunks()
{
 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();
 // Load Chunks or Create
 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();
 bool isLoad = true;
 if (chunkX == 0 || chunkX == (sizeX - 1) || chunkY == 0 || chunkY == (sizeY - 1))
 isLoad = false;
 if (currentChunk == null)
 {
 Color ColorBiome = Color.FromArgb(64, 233, 56);
 string BiomeName = "Grass";
 allChunks.Add(new Chunks(xChunk, yChunk, sizeChunk, ColorBiome, BiomeName, isLoad, 40));
 }
 else
 {
 bool isCurrentLoaded = currentChunk.isLoaded;
 if (!isLoad)
 currentChunk.isLoaded = false;
 else if (!isCurrentLoaded)
 currentChunk.isLoaded = true;
 }
 }
 }
 ChunkDetect.Stop();
}
class Chunks
{
 public Color biomeType;
 public Guid uid;
 public bool isLoaded;
 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)
 {
 // Identificador
 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
 // Propiedades
 this.isLoaded = loaded; // If chunk is loaded
 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;
 }
 public void changeLoaded(bool g)
 {
 this.isLoaded = g;
 }
}

• Simon Forsberg: 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?
• Lukas Häring: gameBox is only a control picture box.
• Lukas Häring: Ok, I added the class Chunks and the list allChunks

Answer 1

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)) {
 indexChunks.Add(key, new Chunks(.....));
}
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.

• Lukas Häring: Give me a hug :') thx :D
• War: 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!!!
• Shaz: @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
• rolfl: @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.
• Sebastian Graf: 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.