CODEWITHSUNDEEP
c#linqunity-game-engine
Utku
Utku

Reputation: 1

Checking distance between items of list taking too much time. Is there a way to make it faster?

I'm following Sebastian Lague's Procedural Landmass Generation tutorial . He is generating landmass' color by height value. But I want to separate landmass to a array or list as areas by their color. Because the way Sebastian use generates too many water or mountain areas so I want to make them less. I tried to edit the code of him but the code I made tooks 2-3 minutes to separate. Does anyone have idea to make it faster?

The class I use to seperate regions and the areas in every region:

public class Positions
{
    public int regionID;
    public int areaID;
    public int x;
    public float y;
    public int z;
}

List<Positions> positions = new List<Positions>();

The code I try to find and list them:

    for (int y = 0; y<mapChunkSize; y++)
    {
        for (int x = 0; x<mapChunkSize; x++)
        {
            float currentHeight = noiseMap[x, y];
            for (int i = 0; i<regions.Length; i++)
            {
                if (currentHeight <= regions[i].height)
                {
                    int areaID = 0;
                    if(positions.Where(x => x.regionID == i).Count() != 0)
                    {
                        areaID = getNeighourIndex(i, x, y);
                    }
                    Positions p = new Positions { regionID = i, areaID = areaID, x = x, y = noiseMap[x, y], z = y };
                    positions.Add(p);
                    break;
                }
            }
        }
    }


    int getNeighourIndex(int regionID, int x, int y)
    {
        List<Positions> pos = positions.Where(x => x.regionID == regionID).ToList();
        if (pos.Where(q => Vector2Int.Distance(new Vector2Int(q.x, q.z), new Vector2Int(x, y)) <= 1).Count() > 0)
            return pos.Find(q => Vector2Int.Distance(new Vector2Int(q.x, q.z), new Vector2Int(x, y)) <= 1).areaID;

        return (pos.Select(q => q.areaID).OrderBy(x => x).LastOrDefault()) + 1;
    }

Upvotes: 0

Views: 119

Answers (1)

JonasH
JonasH

Reputation: 36541

As always when doing optimizing, the first step should be to measure, ideally with a profiler since this can hint at what it is that takes most time.

But I would guess that the majority of the time is spent in positions.Where(x => x.regionID == regionID). To solve this you could use a multi value dictionary, i.e. a dictionary where each key can map to multiple values. It is fairly easy to make your own wrapper around a Dictionary<TKey, List<TValue>>, or you could use one from Microsoft.Experimental.Collections.

You could also consider using a hierarchical search structure for the points, like a kd-tree, quad-tree or similar.

Also, if performance is of high importance, using LINQ is likely not the best option. LINQ is convenient, but the abstraction adds some overhead. In most cases this overhead is irrelevant, but in tight loops like this it may very well be a significant factor.

Upvotes: 2

Related Questions