StackOverflowException - Flood fill

Hello,

Actually, I have a problem with an algorithm which consist to fill a surface. In order to do this, I have an 2D array which each case represents a case in my array. Besides, each case of my array are also represented by a state.
And I want to say that if there is a form (like a square or a triangle) on the map when the player walk and create a geometric shape.
About the state, if the player walk once on the square (array*[j]) the state is 1.1, twice : 1.2 and >= 3 the state is 1.3. And then if he walks three times in order to draw a square then inside the square it can be a state between 1.1 and 1.3 but my algorithm must say “ok then here there is a square”.*
I know it’s not obvious to understand but maybe with the algorithm you will see better.
Then my algorithm is :
```

  •   void check(ref IsoCollision iso_collision, float i, float j, ref int z) // check if array[i][j] is inside a geometric shape
     {
         if ((i == 0 || j == 0 || i == 3 || j == 3) &&
             get_state(i,j) != 1.3f) // if we are on the extremity and the state is not maximum then we are no inside a geometric shape, thus we quit
         {
             z = 0;
             return;
         }
         if (get_state(i, j) < 1.3f)
         {
             GameObject Case = GameObject.Find ("Floor_" + i + "x" + j);
             if ( Case.GetComponent<IsoObject> ().position.x == i && Case.GetComponent<IsoObject> ().position.y == j)
                 Case.GetComponent<IsoBoxCollider> ().state *= -1; // in order to remember what this algorithm change case
             z++;
             // And then reccursif call
             check(ref iso_collision, i+1, j, ref z);
             check(ref iso_collision, i-1, j, ref z);
             check(ref iso_collision, i, j+1, ref z);
             check(ref iso_collision, i, j-1, ref z);
    
         }
     }*
    

* *And when I do :* *check(ref iso_collision, 0, 0);* *no error, but i want to browe my array thus I do :* *
*for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
check(ref iso_collision, i, j);
for (int x = 0; x < 10; x++)
for (int y = 0; y < 10; y++)
if (get_state(y, k) < 0)
Case.GetComponent().state = -1; / in order to reset all the state /
if (z != 0)
{ /
Do something, that is to say there is a shape /
}
}

* *And with this I had "StackOverFlow Exception". (Then in C++ it's works perfectly with a simple array of std::string and the state 1.3 represent the "X";* *
*----------
| XXXXXXX|
| X X|
|X X|
|XXXXX X|
| X X|
| XXX X|
| XX|
| |

Output : 1 : 2*
```
Indeed, array[1][2] is inside a shape :wink:
Thank you !

Don’t use equality when checking for floating point numbers, e.g. 1.3f. This is because computers are base 2 and floating point numbers in our world are base 10, and thus there is not always a 1-1 mapping, and the equality check will fail. It is called floating point error if you want to google more.

Instead use integers, such as 11 or 12 or 13. Integers may be correctly compared for equality.

If you absolutely MUST use floating point, then use the Mathf.Approximately function, but I don’t recommend this approach for what you are doing.

According to you, because I’m using 1.3f there is a StackOverFlow Exception? Okaip, thus I wil try tonight!

Nevertheless the prototype of my function get_state is :

float get_state(float i, float j);

Anyway or it’s important that I precise this ?

Update, I change all my float by a Int and I have again a StackOverflow i don’t know why …

Actually I did something similar back last year when I was looking to build an old 80’s game, but I couldn’t get my head around a flood fill algorithm, now first it’s coded in VB.net using winforms but if you have a version of Visual studio not Coder, you should be able to convert it to c# or take the concept and adapt it, for your needs, it fully works, one day I’ll make the remake of the game.

I hope this helps

3073773–231161–FloodFill.zip (151 KB)

  1. When writing a recursive function, double check the stopping condition(s) and make sure that it will happen.
  2. If you are definitely sure your algorithm is correct, and your recursion need to go extremely deeply, you may run into a stack overflow (the stack is limited). If that the case, note that any recursive algorithm can be rewritten using a stack (System.collection.generic.stack) or a queue (System.collection.generic.queue), so you avoid growing the call stack too much.
1 Like

Indeed. In fact, to understand recursion, you must first understand recursion.

Floodfills of large pixel arrays (I know the OP’s array looks fairly small) are usually done by a non-naive algorithm, something along the lines of going left/right first and watching for “breaking out” into new sub-areas that need to fill, and marking only that “breakout pixel” and continuing to fill until you break out again.

This was how older computers (i.e., the Commodore VIC-20 running a 2mhz 6502 CPU) would fill, and it was fairly efficient in memory and CPU. You could watch it happen.

Wikipedia identifies a few ways, and the way I mention above is specifically covered. https://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations