多次运行洪水填充算法时遇到堆栈溢出异常

Question

我有一个排列在网格上的对象列表。我想删除任何没有返回网格顶部的路径的东西，无论是直接的还是通过邻居的。

我认为执行此操作的一个好方法是首先使网格上的所有内容都可删除，然后使顶行上的所有内容不可删除。然后，我想对顶行中的任何对象进行洪水填充，以使连接到它们的对象不可删除。

我想不出一种（有效的）方法来优化它。有没有更简单的方法来完成我想做的事情？

使用列表而不是二维数组可能会搬起石头砸自己的脚。它引入了许多额外的 foreach 循环。

    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

解开递归

一个答案是解开你的递归。您会遇到堆栈溢出，因为递归级别太多，需要内存分配才能完成并返回，因此“堆栈溢出”。

限制递归

我过去为 XNA 游戏创建了一个编辑器，其中需要洪水填充算法，我所做的是对其递归次数设置上限退出前。实际上，这意味着我可能必须对未填充的剩余部分重新应用大的洪水填充，但这不会导致堆栈溢出。

洪水填充算法

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

这使用常规循环来避免堆栈溢出错误。

Answer 2

避免递归（DetectHangingNeighbours 调用自身）。使用堆栈方法：

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

祝你好运。