koobas.hobune.stream
Stack overflow with recursive floodfill method.
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
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 ;) 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.
You introduced even more method calls, therefore the performance will be even worse. Also that use of "Any()" will produce tons of garbage for no reasons. Why not simply checking Count? If you think method calls aren't that bad, have a look at my answer over here. Yes in most cases you don't care about method calls. However when iterating over the pixels of an image you quickly go into several million calls where it does have a huge effect. Especially it can stall the pipeline of the cpu.
Properties are actually methods.
Properties can be used as if they are public data members, but they are actually special methods called accessors.
so whether it is faster/slower depends on the implementation of Count/Any(). So you might be right about it being faster as I honestly haven't tested it. But that is not a general thing you can assume, it depends on the actual implementation of the method/property in question... (EDIT, now I did test it, And in this case you are totally right, didn't know Any created garbage :p, good call)
Also, although there are more methods in this answer, I do not increase the number of methods called. There is an equal number of methods called in both solutions. And the ones I do call are not called recursivly meaning the call stack doesn't grow beyond a fixed number.
Now I'm sure you can find ways to further optimize this by inlining the fill like you said and by reducing the number of checks (if we check x+1 we don't need to check wether x > 0, y > 0 or y < height, because we already know it is based on how we got there). But that is extra optimizing steps that i thought would be out of scope for this answer as I focussed on the converting recursion to iteration part...
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
How would i utilize this with a 2D array ins$$anonymous$$d of a single array?
