How To Simplify CPU Intensive For Loop C#

Question

So, I'm making a procedurally generated world in C#, Visual Studio on Windows 10 in Unity. I was having a problem figuring out why my map couldn't handle big dimensions until I stumbled upon this set of loops in my code.

    for (int index = 0; index < terrainCoords.Count; index++)
        {
            if (index == terrainCoords.Count)
            {
                break;
            }

            touchCount = 0;

            for (int posAdd = 0; posAdd < neighbors.Count; posAdd++)
            {
                newPos = new Vector3Int(terrainCoords[index].x + neighbors[posAdd].Item1, terrainCoords[index].y + neighbors[posAdd].Item2, 0);
                touchCount += terrainCoords.Contains(newPos) ? 1 : 0;
            }

            if (touchCount < 2)
            {
                terrainCoords.Remove(terrainCoords[index]);
            }

        }

    for (int j = 0; j < caveSmoothness; j++)
    {
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                if (!terrainCoords.Contains(new Vector3Int(x, y, 0)))
                {
                    touchCount = 0;

                    for (int posAdd = 0; posAdd < neighbors.Count; posAdd++)
                    {
                        newPos = new Vector3Int(x + neighbors[posAdd].Item1, y + neighbors[posAdd].Item2, 0);
                        touchCount += terrainCoords.Contains(newPos) ? 1 : -1;
                    }

                    if (touchCount > 1)
                    {
                            terrainCoords.Add(new Vector3Int(x, y, 0));
                    }

                }

            }

        }
    }

Now, for reference, terrainCoords is a list of Vector3Int's which i have pre-generated to make a map, although the resulting map is messy, so these for loops clean them up by iterating through a list of tuples called 'neighbors' which is a set of numbers that when added to the coordinates of a block give all the coordinates of the blocks directly touching them. The purpose of the first loop is to remove free floating solid blocks that aren't touching enough solid blocks to constitute any important structure. The second loop is to fill in random pockets that may appear, by adding blocks in the position of empty blocks who aren't touching enough empty blocks. And when caveSmoothness is increased, it can also fill in small, narrow-trailing tunnels. Yet, if I were to have a map with, say, a 100*100 size and a 'caveSmoothness' of 2, it would have to iterate over itself 100,000,000 times, which is far too much. This is a critical process though do to not having it resulting in awkward maps. To pre-generate the terrain, I am using Accidental Noise's minecraft world example with these settings:

terraintree=
{
    {name="ground_gradient",               type="gradient",         x1=0, x2=0, y1=0, y2=1},

    {name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=0.25},
    {name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
    {name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.125, offset=-0.45},
    {name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
    {name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},

    {name="highland_shape_fractal",        type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=2},
    {name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=-1, high=1},
    {name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.25, offset=0},
    {name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
    {name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

    {name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=8, frequency=1},
    {name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=-1, high=1},
    {name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.45, offset=0.15},
    {name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.25},
    {name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

    {name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.125},
    {name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
    {name="terrain_type_y_scale",          type="scaledomain",      source="terrain_autocorrect", scaley=0},
    {name="terrain_type_cache",            type="cache",            source="terrain_type_y_scale"},
    {name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.2},
    {name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
    {name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
    {name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},

    {name="cave_shape",                    type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
    {name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
    {name="cave_shape_attenuate",          type="combiner",          operation=anl.MULT, source_0="cave_shape", source_1="cave_attenuate_bias"},
    {name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
    {name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
    {name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
    {name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},

    {name="ground_cave_multiply",          type="combiner",          operation=anl.MULT, source_0="cave_select", source_1="ground_select"}
}

And despite my efforts to find a noise reduction/fractal smoothness setting in their docs and tweaking with the settings, I cant seem to generate the same results as I can with the Ruth-Goldberg machine that my for loops are. If you can simplify my for loops, find a more efficient way to achieve these results, or can tweak the fractal settings in a way that I hadn't noticed, your input would be very much appreciated. Thank You! =)

Answer 1

It seems to me too complicated. It is a 2D array, so why not start with simple 2D array?

Random rnd = new Random(1);
int xSize = 10000;
int ySize = 1000;
byte[,] terrainCoords = new byte[ySize + 2, xSize + 2];

for (int y = 1; y <= ySize; ++y)
{
    for (int x = 1; x <= xSize; ++x)
    {
        if (rnd.Next(100) < 40) //40% fill ratio
        {
            terrainCoords[y, x] = 1;
        }
    }
}

var st = new System.Diagnostics.Stopwatch();
st.Start();

for (int y = 1; y <= ySize; ++y)
{
    for (int x = 1; x <= xSize; ++x)
    {
        int touchCount =
              terrainCoords[y - 1, x - 1]
            + terrainCoords[y - 1, x]
            + terrainCoords[y - 1, x + 1]
            + terrainCoords[y, x - 1]
            + terrainCoords[y, x + 1]
            + terrainCoords[y + 1, x - 1]
            + terrainCoords[y + 1, x]
            + terrainCoords[y + 1, x + 1];

        if (touchCount < 2)
        {
            terrainCoords[y, x] = 0;
        }
    }
}           

int caveSmoothness = 5;
for (int j = 0; j < caveSmoothness; j++)
{
    for (int y = 1; y <= ySize; ++y)
    {
        for (int x = 1; x <= xSize; ++x)
        {
            int touchCount =
               terrainCoords[y - 1, x - 1]
             + terrainCoords[y - 1, x]
             + terrainCoords[y - 1, x + 1]
             + terrainCoords[y, x - 1]
             + terrainCoords[y, x + 1]
             + terrainCoords[y + 1, x - 1]
             + terrainCoords[y + 1, x]
             + terrainCoords[y + 1, x + 1];

            if (touchCount > 4)
            {
                terrainCoords[y, x] = 1;
            }
        }
    }
}

st.Stop();
Console.WriteLine(st.ElapsedMilliseconds.ToString()); //800ms

I think it is a good start point. If you need more performance, you can optimize it further, but it has to be done on real data.

Answer 2

One optimization that stands out is to short circuit the loop for removing terrainCoords elements. You don't care about the true count, only that it's < 2. so the moment touchCount fails that test, bail from the rest of the loop.

for (int posAdd = 0; posAdd < neighbors.Count && touchCount < 2; posAdd++)
{
    newPos = new Vector3Int(terrainCoords[index].x + neighbors[posAdd].Item1, terrainCoords[index].y + neighbors[posAdd].Item2, 0);
    touchCount += terrainCoords.Contains(newPos) ? 1 : 0;
}

if (touchCount < 2)
{
    terrainCoords.Remove(terrainCoords[index]);
}

You can apply a similar short circuit to the inner most loop for cave smoothness.