Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

}
share|improve this question
3  
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
add comment

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
1  
Give me a hug :') thx :D –  Lukas Häring Jun 23 at 15:17
2  
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
1  
@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
3  
@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
4  
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
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.