0

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?

Note: The texture was get when I manually exited the method. So, my fill algorithm is filling the texture by "layers" that's why there are so many yellow pixels.

z3nth10n
  • 2,341
  • 2
  • 25
  • 49
  • You are missing marking pixels as visited. At the moment you can visit a node multiple times – juvian Nov 14 '18 at 20:12
  • I mark pixels as visited outside of the Flood Fill algorithm, and I suppose I do the same when I check `!queue.Contains(targetIndex)`. In this case, what do you mean? – z3nth10n Nov 14 '18 at 20:18
  • 1
    You start with source. On the first step you remove it from the queue add its neighbour's to the queue. Now you remove first neighbor added from the queue and you will add source again to the queue because it is not in it anymore – juvian Nov 14 '18 at 20:22
  • So, it's better to do this `queue.Remove(_i)` at the end or what do you suggest me? – z3nth10n Nov 14 '18 at 20:40
  • I created another forked fiddle: https://dotnetfiddle.net/jIhRSU and I see no differences, so I will check this. Also, I'm testing if I really need to check for Interloecked. – z3nth10n Nov 14 '18 at 20:41
  • No, you need 2 structures, a stack or queue for doing the flood fill and a hashset or array to mark positions already visited. Check [some implementations](https://stackoverflow.com/questions/21865922/non-recursive-implementation-of-flood-fill-algorithm) – juvian Nov 14 '18 at 21:04
  • Actually, if you see my code, I'm modifying the color on the array, so, any iterations done later will check if the current color is the same as target. If not this pixel will be already marked as visited. @juvian – z3nth10n Nov 14 '18 at 21:07
  • Your FloodFill is fine yes, should be working if targetColor != replacementColor. Still, would be better to color pixels when you add them to the stack, if not a pixel can be added to the stack by all its neighbours – juvian Nov 14 '18 at 21:12
  • So the problem is you do targetColor = source[P(x, y, width, height)] at the start, which makes targetColor and replacementColor be the same, which makes adding nodes infinite times as I mentioned before – juvian Nov 14 '18 at 21:26

0 Answers0