Why is this flood fill method causing a stack overflow when coordinates are subtracted?

Question

I am trying to create a paint bucket-style flood fill for a tile system, in order to create an editor.

However, basing it on the four way flood fill algorithm is causing problems. x + 1 and y + 1 work just fine, however the moment they are paired with x - 1 and y - 1, it causes a stack overflow. In addition, my comparative point is the color of the tile. There are instances where it will just ignore if colors do match, and overwrite them anyway, when it ought to exit instead.

Following the example algorithms here, this code feels like it -ought- to work:

Flood Fill Algorithm Example

However, as described above, my own implementation in C# just isn't working properly in all directions:

public void FloodFill(int x, int y, Color fillColor, Color oldColor)
{
    if (x < 0 || x >= boardSize) return;
    if (y < 0 || y >= boardSize) return;
    Tile tile = world.GetTileAt(x, y);

    if (tile.currentColor.Equals(fillColor))
    {
        return;
    }

    if (tile.currentColor.Equals(oldColor))
    {
        UpdateTile(tile.currentTile, fillColor);

        FloodFill(x - 1, y, fillColor, oldColor);
        FloodFill(x + 1, y, fillColor, oldColor);
        FloodFill(x, y - 1, fillColor, oldColor);
        FloodFill(x, y + 1, fillColor, oldColor);
    }

        return;
}

My best guess is that metaphorically, it's tripping over itself, but that should not be occurring with the comparisons and returns to prevent execution. This conclusion comes from the log - it keeps hopping tiles when dealing with both positive and negative numbers.

Here's the log thus far:

MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:134)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:136)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:138)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:136)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:138)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:136)
MasterController.FloodFill (System.Int32 x, System.Int32 y, UnityEngine.Color fillColor, UnityEngine.Color oldColor) (at Assets/Game Assets/Scripts/Gameplay/MasterController.cs:138)

This is the code for UpdateTile and GetTileAt:

public void UpdateTile(Transform tile, Color color)
{
    Mesh mesh = tile.GetComponent<MeshFilter>().mesh;

    Color32[] nextColor = new Color32[mesh.vertices.Length];

    for (int i = 0; i < nextColor.Length; i++)
    {
        nextColor[i] = color;
    }

    mesh.colors32 = nextColor;
}

public Tile GetTileAt(int x, int y)
{
    if (x > size || x < 0 || y > size || y < 0)
    {
        return null;
    }

    return tiles[x, y];
}

How big is the area being flooded? Have you checked through the call stack or debugged line by line what it’s doing? — Sami Kuhmonen, Jun 07 '20 at 21:05
You may want to [compare](https://stackoverflow.com/questions/45290317/how-can-i-fill-part-of-image-with-color/45299760#45299760) with my working implementation.. — TaW, Jun 07 '20 at 21:06
When you say ‘Tile.currentColor’ here, do you really mean ‘tile.currentColor’? — 500 - Internal Server Error, Jun 07 '20 at 22:01
Whoops - thanks. That's a spellcheck auto-correct, I didn't even notice it. It's not in the original code, just here - fixing. — Merlin, Jun 07 '20 at 22:04
@SamiKuhmonen It's happening on any size area, even as small as 3x3. I did check the stack trace - it keeps hopping back between itself when dealing with x - 1 and y - 1 in conjunction with positive numbers. — Merlin, Jun 07 '20 at 22:10
Taking a closer look, it -seems- to get stuck bouncing between two points, repeatedly. It has no way of telling which point has been visited or not. — Merlin, Jun 08 '20 at 00:41
I think I need to determine a different way to do this kind of fill more suited to tiles then pixels. — Merlin, Jun 08 '20 at 00:46

Gavin S. · Answer 1 · 2023-02-07T16:21:06.623

Large image solution. Working on a project of my own I have optimized a solution based on several others I have found. First, this solution avoids recursion by using a while loop with a stack of Points. Second, it avoids overlapping itself by checking the state of the current pixel from the stack against the target. It only adds the surrounding items IFF current pixel is the target color. In this way, the function avoids looking at a pixel again, by quickly exiting when the pixel pointed at is already filled. This avoids having to use a different data structure to store your already visited locations, as suggested by Flater above. This solution does have its own weakness when trying to fill a large portion of large images, discussed below.

    System.Drawing.Image _image;// defined & populated elsewhere in my class.
    public void FloodFill(Point pt, Color replacementColor)
    {
        Color TargetColor = ((Bitmap)_image).GetPixel(pt.X, pt.Y);
        if (TargetColor == replacementColor)
        {             
            return;//Avoids overlap
        }
        Int32 overfill_counter = 0;
        Int32 overfill_max = 2400000;//Max pixels to traverse.
        
        Stack<Point> pixels = new Stack<Point>();
        pixels.Push(pt);
        while (pixels.Count > 0)
        {
            Point a = pixels.Pop();
            if(overfill_counter < overfill_max)
            {
                Color a_Color = ((Bitmap)_image).GetPixel(a.X, a.Y);
                
                if(a_Color == TargetColor)
                {
                    overfill_counter++; 
                    ((Bitmap)_image).SetPixel(a.X, a.Y, replacementColor);
                    if (a.X > 0) { pixels.Push(new Point(a.X - 1, a.Y)); }
                    if (a.X < _image.Width - 1) { pixels.Push(new Point(a.X + 1, a.Y)); }
                    if (a.Y > 0) { pixels.Push(new Point(a.X, a.Y - 1)); }
                    if (a.Y < _image.Height - 1) { pixels.Push(new Point(a.X, a.Y + 1));}
                }
            }
        }
        this.Invalidate();
        return;
    }//FloodFill()

Other Optimizations I had found other solutions using a Bitmap directly and in creating my project I used those by converted my System.Drawing.Image to a bitmap at the start of each FloodFill() call. Later, I found that this conversion eats up a large amount of memory, because the BMP representation of the large image objects I am working with became unwieldly. Instead, casting the System.Drawing.Image as a Bitmap and using the necessary GetPixel() and SetPixel() functions avoids the large memory utilization. This makes it very friendly to editing/flooding parts of large images.

Weakness This algorithm uses a Stack, that can get quite large very quickly when working with large images. For my project, it is acceptable to limit the size of the flood-fill region, which I have done with the usage of the overfill_counter in the code above.

score 0 · Accepted Answer · answered Jun 08 '20 at 12:40

After a number of hours of attempts, I finally found an answer to why things weren't working properly. There were a few more steps that needed to be confirmed, before moving onto the flood fill step-through.

(Note: activeColor is a public variable outside the method)

private void RevisedFloodFill(int x, int y, Color targetColor)
{
    if (isValid(x, y))
    {
        Tile node = world.GetTileAt(x, y);
        if (node.hasActiveTile)
        {
            if (node.currentColor != activeColor)
            {
                string target = ColorUtility.ToHtmlStringRGB(targetColor);
                string compare = ColorUtility.ToHtmlStringRGB(node.currentColor);

                if (string.Equals(target.Trim(), compare.Trim()))
                {
                    node.currentColor = activeColor;
                    UpdateTile(node.currentTile, activeColor);

                    RevisedFloodFill(x + 1, y, targetColor);
                    RevisedFloodFill(x - 1, y, targetColor);
                    RevisedFloodFill(x, y + 1, targetColor);
                    RevisedFloodFill(x, y - 1, targetColor);
                }
            }

        }


    }
}

private bool isValid(int x, int y)
{
    if (x >= 0 && x < boardSize && y >= 0 && y < boardSize)
    {
        return true;
    }

    return false;
}

However, while this works without crashing, it's not perfect. There are instances where it tends to ignore the next color and fill the entire board with the wrong color, so my comparison still needs work.

As an aside, `if( bla) ) { return true; } else { return false; }` can **always** be reduced to `return bla;` (where `bla` is your evaluation logic) — Flater, Jun 08 '20 at 12:53
True, though I just figured out why it wasn't working correctly. In my coloring method, while I was setting the tile color - it wasn't being stored! That's what working overnight will do sometimes, I guess. — Merlin, Jun 08 '20 at 12:56

Flater · Answer 3 · 2020-06-08T13:14:55.500

The problem

You're running into a recursive problem. It helps to look at the pseudocode:

function ColorThisTile()

    if needed set tile color

    check tile on the left
    check tile on the right
    check tile on the top
    check tile on the bottom

Let's use a chess board for reference in the example I'm going to use:

Say we start from B4. This means that the method will perform these steps for B4:

    if needed set B4 color

    check A4
    check C4
    check B5
    check B3

So what does check A4 entail? That's another instance of this method, and for A4 it does the following

    if needed set A4 color

    check ?4  // This does nothing since there's no tile to the left
    check B4  // The problem is here!
    check A5
    check A3

Your initial B4 check entailed checking A4. The subsequent A4 check then leads to checking B4 again. This new B4 check is going to check A4 again. That A4 check is going to check B4 again. And this repeats infinitely.

The solution

To prevent the problem, you're going to have to write your logic so you avoid checking the same cell over and over.
This can be done in several ways, but the simplest approach is to keep track of every cell you've visited, and if you run a check on a cell that was already visited, immediately return from the function.

Something along the lines of:

public void FloodFill(Cell cell, Color fillColor, List<Cell> visitedCells)
{
    if(visitedCells.Any(visitedCell => visitedCell.X = cell.X && visitedCell.Y = cell.Y)
        return;

    visitedCells.Add(cell);

    // the rest of the code

    FloodFill(cell.GetLeft(),  fillColor, visitedCells);
    FloodFill(cell.GetRight(), fillColor, visitedCells);
    FloodFill(cell.GetUp(),    fillColor, visitedCells);
    FloodFill(cell.GetDown(),  fillColor, visitedCells);
}

public class Cell
{
    public int X { get; set; }
    public int Y { get; set; }

    public Cell GetLeft()
    {
        return new Cell() { X = this.X-1, Y = this.Y };
    }

    public Cell GetRight()
    {
        return new Cell() { X = this.X+1, Y = this.Y };
    }

    public Cell GetUp()
    {
        return new Cell() { X = this.X, Y = this.Y-1 };
    }

    public Cell GetDown()
    {
        return new Cell() { X = this.X, Y = this.Y+1 };
    }
}

This ensures that you don't run into the issues of two neighbors constantly checking each other.

I added the Cell class to avoid juggling the coordinate variables at every turn - be sure to check if your environment doesn't already have an existing class/struct to represent a 2D point.

A good tip

You would've stumbled on this issue if you had logged which cells were being checked. With logging along the lines of:

public void FloodFill(Cell cell, Color fillColor, List<Cell> visitedCells)
{
    _log.Info($"Checking cell ({cell.X},{cell.Y})");

    // ...
}

You would've seen that it would repeatedly check the same two cells over and over.

I did. It's in the log posted above - where it hops between two of the floodfills repeatedly: 138 - 136 - 138 - 136, so on and so forth. Part of the problem also turned out to be my "coloring" method - it wasn't setting the variable even though it was coloring the tile. — Merlin, Jun 08 '20 at 13:27
@Merlin: What you have there is a stacktrace on an exception, and it's giving you a line reference. You have no idea _which cell_ is being checked in any of those line references. It's much better to create your own custom log messages which can reveal the values of your variables instead of just the code lines in the stack trace (which leaves you guessing as to which values were being used at the time). — Flater, Jun 08 '20 at 13:32

Why is this flood fill method causing a stack overflow when coordinates are subtracted?

3 Answers3

The problem

The solution

A good tip