Question by z3nth10n · Nov 14, 2018 at 07:18 PM · c#optimization algorithm flood

Flood filling algorithm doesn't work as expected - it creates gaps between pixels

Well, I can't be so expressive in the title, so I will try to explain it here.

Basically my flood filling algorithm is doing this:

The different colors means the following:

Blue pixels are the points from the polygon
Red pixels are what Flood Fill has already filled
Magenta is the combination of both colors
Yellow pixels should never appear (that means that the algorithm that iterates the shape has already been iterated)
Everything else is the source texture

This is my current method:

     /// <summary>
     /// Floods the fill.
     /// </summary>
     /// <typeparam name="T"></typeparam>
     /// <param name="source">The source.</param>
     /// <param name="x">The x.</param>
     /// <param name="y">The y.</param>
     /// <param name="width">The width.</param>
     /// <param name="height">The height.</param>
     /// <param name="target">The target.</param>
     /// <param name="replacement">The replacement.</param>
     public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement)
         where T : IEquatable<T>
     {
         int i;

         source.FloodFill(x, y, width, height, target, replacement, out i);
     }

     /// <summary>
     /// Floods the array following Flood Fill algorithm
     /// </summary>
     /// <typeparam name="T"></typeparam>
     /// <param name="source">The source.</param>
     /// <param name="x">The x.</param>
     /// <param name="y">The y.</param>
     /// <param name="width">The width.</param>
     /// <param name="height">The height.</param>
     /// <param name="target">The target to replace.</param>
     /// <param name="replacement">The replacement.</param>
     /// <param name="i">The i.</param>
     // This was generic
     public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement, out int i)
         where T : IEquatable<T>
     {
         i = 0;
         HashSet<int> queue = new HashSet<int>();

         queue.Add(P(x, y, width, height));

         while (queue.Count > 0)
         {
             int _i = queue.First(),
                 _x = _i % width,
                 _y = _i / width;

             queue.Remove(_i);

             if (source[_i].Equals(target))
                 source[_i] = replacement;

             for (int offsetX = -1; offsetX < 2; offsetX++)
                 for (int offsetY = -1; offsetY < 2; offsetY++)
                 {
                     // do not check origin or diagonal neighbours
                     if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
                         continue;

                     int targetIndex = Pn(_x + offsetX, _y + offsetY, width); // This is already inverted that's why we don't use F.P(...)
                     int _tx = targetIndex % width,
                         _ty = targetIndex / width;

                     // skip out of bounds point
                     if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
                         continue;

                     if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
                     {
                         queue.Add(targetIndex);

                         if (Monitor.IsEntered(i))
                             ++i;
                         else
                             Interlocked.Increment(ref i);
                     }
                 }

             if (i > 100000)
                 break;
         }
     }

I can't show the other code, but I can try to explain it.

Basically, we have this texture (https://themindheist.files.wordpress.com/2015/03/gta_usa_map3.png) (It's too big to be here).

We iterate it pixel by pixel.
If we found any allowed pixel (Grass, Rock, Ice, Snow or whatever) then...
We start looking for the shape of the current biome
Then before continuing iterating we call Flood Fill algorithm.
With this call we ensure that we will never pass over any pixel that form part of any of the map's polygons.

But as you can see, I have problems.

Watching at my implementation I suppose that when enqueued pixels looks for neighbors they are trapped and they don't return any neighbor pixel.

Or maybe, this is the way my flood fill algorithm executes (under special conditions I don't know).

What could you suggest/recommend me to do?

Add comment