Finding a way to make this 2D loop faster?

Question

So I'm creating a unity3D game with infinite terrain and it's going great! However, I'm struggling with a specific but important part of the 'infinite' terrain. Make the terrain actually infinite. I got it working but it's very slow and I've looked through the code and at the profiler that unity has built in and came to the conclusion that it's my 2D for-loop that's slowing down the game. (VERY small freezes)

Let me explain... so I have a total of 3 lists keeping track of all the chunk gameobjects in the scene for that player. One for the active chunks, one for the inactive chunks, and one for all the chunks in the scene. In the beginning I spawn the chunks around the player in a circle around the player (size defined by a radius variable) and then all those chunks get added to the active and all chunks lists. Then I check if the player has moved one chunk of distance every frame (which isn't really slow at all) and if the player has moved one chunk of distance in any direction it calls a infinite terrain method that does this:

It loops through the ALL chunks list and checks their distance if they are farther then the radius variable. If it is then it adds it to the unloaded chunk list queue. THEN: It's a 2D for-loop (nested for loops) that loop through a square area around the players current position. It then checks if that position in that point in the loop has a chunk by looking finding if the loaded chunks list (it's a dictionary) has that current position in it. If it doesn't then that means that positions needs a chunk.. it dequeues a chunk from the unloaded chunks queue and loads it in that position and then adds it to the loaded chunks list.

private List<GameObject> allChunks = new List<GameObject>();
private Dictionary<GameObject, Vector2> loadedChunks = new Dictionary<GameObject, Vector2>();
private Queue<GameObject> unloadedChunks = new Queue<GameObject>();

private void InfiniteWorld()
{
    // Check for unloaded chunks and unload them
    for (int i = 0; i < allChunks.Count; i++)
    {
        if (loadedChunks.ContainsKey(allChunks[i]))
        {
            float distFromCenter = Vector2.Distance(new Vector2(Mathf.FloorToInt(allChunks[i].transform.position.x / chunkSize), Mathf.FloorToInt(allChunks[i].transform.position.z / chunkSize)), new Vector2(Mathf.FloorToInt(transform.position.x / chunkSize), Mathf.FloorToInt(transform.position.z / chunkSize))); //Mathf.Sqrt(Mathf.Pow(Mathf.Abs(Mathf.FloorToInt(allChunks[i].transform.position.x / chunkSize) - Mathf.FloorToInt(transform.position.x / chunkSize)), 2) + Mathf.Pow(Mathf.Abs(Mathf.FloorToInt(allChunks[i].transform.position.z / chunkSize) - Mathf.FloorToInt(transform.position.z / chunkSize)), 2));
            if (distFromCenter >= worldRadius)
            {
                // If there is a chunk farther then our render distance unload it.
                loadedChunks.Remove(allChunks[i]);
                unloadedChunks.Enqueue(allChunks[i]);
                allChunks[i].GetComponent<Chunk>().Unload();
            }
        }
    }

    // Check for positions that chunks need to be loaded in to
    for (int x = -worldRadius; x < worldRadius; x++)
    {
        for (int y = -worldRadius; y < worldRadius; y++)
        {
            Vector2 chunkGridPosition = new Vector2(x + Mathf.FloorToInt(transform.position.x / chunkSize), y + Mathf.FloorToInt(transform.position.z / chunkSize));
            if (!loadedChunks.ContainsValue(chunkGridPosition))
            {
                float distFromCenter = Vector2.Distance(chunkGridPosition, new Vector2(Mathf.FloorToInt(transform.position.x / chunkSize), Mathf.FloorToInt(transform.position.z / chunkSize)));//Mathf.Sqrt(Mathf.Pow(Mathf.Abs(chunkGridPosition.x - Mathf.FloorToInt(transform.position.x / chunkSize)), 2) + Mathf.Pow(Mathf.Abs(chunkGridPosition.y - Mathf.FloorToInt(transform.position.z / chunkSize)), 2));
                if (distFromCenter < worldRadius)
                {
                    // If a chunk isn't in a position in our render distance then load one from the unloaded list
                    GameObject chunk = unloadedChunks.Dequeue();
                    chunk.transform.position = new Vector3(chunkGridPosition.x * chunkSize, 0, chunkGridPosition.y * chunkSize);
                    chunk.GetComponent<Chunk>().Load();

                    loadedChunks.Add(chunk, chunkGridPosition);
                }
            }

        }
    }
}

This works perfectly except it has a VERY slight spike and it's barely noticeable but it's there. (only really noticeable with high radius values) but I need a decently high radius value so the player can actually see the terrain around it. So I need your help to make this faster or just make a new infinite terrain system because I can see myself that this isn't really a good way of doing things especially with 3 lists constantly being modified EVEN if they are the correct list types for that job.

Yes I have thought of threading this code but the issue is since this is unity its hard to keep track of things in a list and then access it to do something for example: chunk.LoadChunk(position); And I got it working but not completely and it was overall more messy because of unity's limitations and my poor threading skills. Not that this is any better but I definitely understand it more.

Any help guys? Thanks!

Answer 1

The problem here might be that you are actualy searching all the world.

If you model the world as a graph, where each node carries a GameObject and edges connect adjacent chunks, you can traverse chunks from player position outwards until you get out of range.

Btw, you should use foreach instead of this:

for (int i = 0; i < allChunks.Count; i++) allChunks[i];

Answer 2

Firstly, unless there is something you are not showing depending on the 'allChunks' list, I think that you could just remove it. Chunks appear to be either loaded or unloaded and all you will be doing is moving chunks between these two collections.

The following line, jumps out at me as a possible slow operation:

    loadedChunks.ContainsValue(chunkGridPosition)

Checking if a value is stored in a dictionary can be a slow operation, since dictionaries are optimized for checking for keys and accessing the stored values by keys. My main suggestion would be to update your dictionary to have the position as the key and gameobject as the value.

This would change your logic from 'is this object loaded' to 'is there an object loaded at this coord'. This small change might help stop some of the extra work you were doing.

I have another suggestion that might not help with performance, but could help with readability and reducing repeating code. Create a simple struct that stores coordinates of chunks and handles all related conversions. This will put all code in a single place to handle jumping between world positions and chunk coordinates. This would help reduce the amount of times you might have to use 'Mathf.FloorToInt()'. A simple implementation could look like the following:

public struct ChunkCoord {
    public const int ChunkSize = 10;
    public int X, Y;

    public ChunkCoord(int x, int y) {
        this.X = x; this.Y = y; 
    }

    public static ChunkCoord FromWorld(Vector2 position) {
        return new ChunkCoord(
            (int)Math.Floor(position.X / ChunkSize),
            (int)Math.Floor(position.Y / ChunkSize)
        );
    }

    public Vector2 ToWorld() {
        return new Vector2(
            (float)(this.X * ChunkSize),
            (float)(this.Y * ChunkSize)
        );
    }

    public float DistToWorldPoint(Vector2 position) {
        return Vector2.Distance(position, this.ToWorld());  
    }
}

By updating your collections and adding the ChunkCoords you could update your code to something similar to the following:

public class World {
    Queue<Chunk> availableChunks;
    Dictionary<ChunkCoord, Chunk> loadedChunks;

    public void UpdateWorld(Vector2 position, float radius) {
        // Loop through all available keys in the loaded chunks
        // and check if they are still in the visible radius
        foreach(var coord in this.loadedChunks.Keys) {
            if(coord.DistToWorldPoint(position) >= radius) {
                var chunk = this.loadedChunks[coord];

                chunk.Unload();
                loadedChunks.Remove(coord);
                availableChunks.Enqueue(chunk);
            }
        }

        // Get the min and max values for visible coords.
        ChunkCoord minCoord = ChunkCoord.FromWorld(
            new Vector2(position.X - radius, position.Y - radius));
        ChunkCoord maxCoord = ChunkCoord.FromWorld(
            new Vector2(position.X + radius, position.Y + radius));

        // Loop through all visible coords and 
        // load any chunks that need to be loaded.
        for(int x = minCoord.X; x <= maxCoord.X; x++) {
            for(int y = minCoord.Y; y <= maxCoord.Y; y++) {
                var coord = new ChunkCoord(x, y);
                // Check if the point is in the visable radius
                if (coord.DistToWorldPoint(position) >= radius)
                    continue;

                // Check if there is a chunk already loaded
                if (this.loadedChunks.ContainsKey(coord))
                    continue;

                // Coord is visible and no chunk is loaded, load it.
                var chunk = this.GetAvailableChunk();
                chunk.Load(coord);
                this.loadedChunks[coord] = chunk;
            }
        }
    }

    public Chunk GetAvailableChunk() {
        if(this.availableChunks.Count > 0) {
            return this.availableChunks.Dequeue();
        } else {
            // Handle creating a new chunk and return it here
        }
    }
}