Stack overflow with recursive floodfill method.

Questions & Answers
1

I’ve tried to implement an array floodfill method and i found this online:

public void FloodFill(int x, int y, int fill, int old)
{
    if ((x < 0) || (x >= width)) return;
    if ((x < 0) || (x >= width)) return;
    if (map[x, y] == old)
    {
        map[x, y] = fill;
        FloodFill(x+1, y, fill, old);
        FloodFill(x, y+1, fill, old);
        FloodFill(x-1, y, fill, old);
        FloodFill(x, y-1, fill, old);
    }

}

This works fine, However my stack overflows at the scale i need this to work.
Is there any other non recursive approach to this that works just as fast or faster than this?

Regards,
J-F

2

First thing, might be because you retyped here, but I would change this second line: if ((x < 0) || (x >= width)) return; to if ((y < 0) || (y >= height)) return; for this to work properly…

You could implement your own stack/queue. and then use a loop instead of recursion. If implemented correctly this should prevent any stack overflows. Below is an example implementation I did out of my head, so there might be silly errors in it, but the idea should be clear. Note that I enqueue the ones I already altered, not the ones that I actually want to check. as this makes sure we don’t enqueue the same item more then once.

	public void FloodFill(Vector2Int pos, int fill)
	{
		Queue<Vector2Int> queue = new Queue<Vector2Int>();

		Fill(pos, fill, queue);

		while (queue.Any())
		{
			Vector2Int toCheck = queue.Dequeue();

			Fill(toCheck + new Vector2Int(-1, 0), fill, queue);
			Fill(toCheck + new Vector2Int(0, 1), fill, queue);
			Fill(toCheck + new Vector2Int(1, 0), fill, queue);
			Fill(toCheck + new Vector2Int(0, -1), fill, queue);
		}
	}

	private void Fill(Vector2Int pos, int fill, Queue<Vector2Int> queue)
	{
        if ((pos.x < 0) || (pos.x >= width)) return;
        if ((pos.y < 0) || (pos.y >= height)) return;
		if (map[pos.x, pos.y] != fill)
		{
			map[pos.x, pos.y] = fill;
			queue.Enqueue(pos);
		}
	}

In my example I ignored old for simplicity, but you can of course implement that back in :wink: Also note that this example uses Linq, so you’ll need to add using System.Linq;to the top for this exact example to work…

Edit:
Based on @Bunny83 comment. Figured I might aswell include a further optimized method. My original post was about converting it from recursive to iteration, below I inlined the Fill method and removed some redundant bound checks.

	public void FloodFill(Vector2Int pos, int old, int fill)
	{
		if (fill == old) return;
		if (pos.x < 0 || pos.x >= width) return;
		if (pos.y < 0 || pos.y >= height) return;
		if (map[pos.x, pos.y] != old) return;

		Queue<Vector2Int> queue = new Queue<Vector2Int>(/*map.Length*/);

		map[pos.x, pos.y] = fill;
		queue.Enqueue(pos);

		while (queue.Count > 0)
		{
			Vector2Int filled = queue.Dequeue();

			// Left
			Vector2Int check = new Vector2Int(filled.x - 1, filled.y);
			if (check.x >= 0 && map[check.x, check.y] == old)
			{
				map[check.x, check.y] = fill;
				queue.Enqueue(check);
			}

			// Right
			check = new Vector2Int(filled.x + 1, filled.y);
			if (check.x < width && map[check.x, check.y] == old)
			{
				map[check.x, check.y] = fill;
				queue.Enqueue(check);
			}

			// Top
			check = new Vector2Int(filled.x, filled.y + 1);
			if (check.y < height && map[check.x, check.y] == old)
			{
				map[check.x, check.y] = fill;
				queue.Enqueue(check);
			}

			// Bot
			check = new Vector2Int(filled.x, filled.y - 1);
			if (check.y >= 0 && map[check.x, check.y] == old)
			{
				map[check.x, check.y] = fill;
				queue.Enqueue(check);
			}
		}
	}

By uncommenting the /*map.Length*/ in the queue constructor you can further optimize it, note however that setting the capacity might set it to more then is actually needed, trading memory for speed. So setting the initial capacity and growth factor to something that makes sense for your application can be a good idea to reduce the number of times the queue needs to resize to fit added elements which can be a costly operation.

3

Just have a look at my texture flood fill extensions. The most important thing for any recursive algorithms is the exit / break condition. Any two dimensional operating algorithm has to be extra careful to avoid reaching the same already visited points again. One way is to move in a way so it’s impossible to reach the same point twice. However that would limit the fill to certain shapes as it makes it impossible to fill shapes that requires to go backwards.

My “FloodFillArea” method simply fills an area as long as the new points have the same color as the reference color. This is essentially how the bucket tool in MS paint works. All connected area with the same color will be filled.

The method “FloodFillBorder” has an additional boolean array to remember which locations has been visited already. This method will fill over any color except a certain border color where it is supposed to stop.

For tight loops I would highly recommend to avoid unnecessary method calls. Method calls are slow and depending on the complexity the compiler most likely can not optimise it for you. You may want to have a look at the flood fill wikipedia page