Running into stack overflow exception when running flood fill algorithm multiple times

Question

I have a list of objects arranged on a grid. I want to remove any which don't don't have a path back to the top of the grid, either directly or through their neighbours.

I thought a good way to do this would be to first make everything on the grid deletable, then make anything on the top row not deletable. Then, I wanted to do a flood fill from any objects in the top row, to make the objects connected to them not deletable.

I can't think of a way (that works) to optimize it. Is there a simpler way to go about what I'm trying to do?

I may have shot myself in the foot by using a list, rather than a 2d array. It's introducing a lot of extra foreach loops.

    internal void DetectHangingObjects(int X)
    {
        //Set all objects to deletable
        for (int i = 0; i < planets.Count; i++)
            planets[i].deletable = true;

        //Set first row to not deletable
        for (int i = 0; i < planets.Count; i++)
        {
            Debug.WriteLine(planets[i].X + " " + X);

            if (planets[i].X == X) //X=0
            {
                planets[i].deletable = false;
                try
                {
                    DetectHangingNeighbours(planets[i]);
                }

                catch (Exception ee)
                { Debug.WriteLine(ee.Message); }
            }
        }          
    }

    internal void DetectHangingNeighbours(Planet planet)
    {
        if (planet == null || planet.deletable==true)
            return;

        planet.deletable = false;

        DetectHangingNeighbours(GetTopLeftNode2(planet));
        DetectHangingNeighbours(GetTopRightNode2(planet));
        DetectHangingNeighbours(GetLeftNode2(planet));
        DetectHangingNeighbours(GetRightNode2(planet));
        DetectHangingNeighbours(GetBottomLeftNode2(planet));
        DetectHangingNeighbours(GetBottomRightNode2(planet));
    }

    //The following methods check the six adjacent objects and returns them to the caller if they match
    internal Planet GetTopLeftNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X - planetSize && gridPlanet.Y == planet.Y - yOffset)
                return gridPlanet;

        return null;
    }

    internal Planet GetTopRightNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X - planetSize && gridPlanet.Y == planet.Y + yOffset)
                return gridPlanet;

        return null;
    }

    internal Planet GetLeftNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X && gridPlanet.Y == planet.Y - planetSize)
                return gridPlanet;

        return null;
    }

    internal Planet GetRightNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X && gridPlanet.Y == planet.Y + planetSize)
                return gridPlanet;

        return null;
    }

    internal Planet GetBottomLeftNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X + planetSize && gridPlanet.Y == planet.Y - yOffset)
                return gridPlanet;

        return null;
    }

    internal Planet GetBottomRightNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X + planetSize && gridPlanet.Y == planet.Y + yOffset)
                return gridPlanet;

        return null;
    }

Answer 1

Unravel recursion

One answer is to unravel your recursion. You're getting a stack overflow because there is too many levels of recursion which requires memory allocation before it can finalize and return, thus "stack overflow".

Limit recursion

I have created an editor for an XNA game in the past where I've required a flood fill algorithm, what I did there was to put an upper limit on the number of times it'll recurse before exiting. Effectively this means that I may have to re apply a large flood fill to the remaining portions that wasn't filled, however it wouldn't cause a stack overflow.

Flood Fill Algorithms

• http://www.codeproject.com/KB/GDI-plus/floodfillincsharp.aspx
• http://www.codeproject.com/KB/GDI-plus/queuelinearfloodfill.aspx

This uses regular looping to avoid stack overflow errors.

Answer 2

Avoid recursion (DetectHangingNeighbours calling itself). Use instead a stack approach:

push your starting node into the stack

while there are elements in stack...
  pop element from stack

  if the element is not visited
    visit the element
    push its neighbours into the stack
  end if
end while

Good luck.