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

本文关键字:遇到 堆栈 栈溢出 异常 算法 运行 泛洪 填充 | 更新日期: 2023-09-27 18:04:14

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

我认为这样做的一个好方法是首先使网格上的所有内容可删除,然后使顶部行的任何内容不可删除。然后,我想做一个洪水填充从任何对象在顶部的行,使对象连接到他们不可删除。

我想不出一个方法来优化它。有更简单的方法来做我想做的事吗?

我可能是搬起石头砸了自己的脚,因为我使用了一个列表,而不是一个2d数组。它引入了很多额外的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;
    }

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

解开递归

一个答案是解开递归。你会得到一个堆栈溢出,因为有太多层次的递归,需要内存分配之前,它可以完成和返回,因此"堆栈溢出"。

限制递归

我曾经为一款XNA游戏创建了一个编辑器,在那里我需要一个洪水填充算法,我所做的就是在退出之前设置一个递归次数的上限。实际上,这意味着我可能不得不对未被填充的剩余部分重新应用大量的溢出填充,但是它不会导致堆栈溢出。

洪水填充算法

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

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

避免递归(detecthangingneighbors调用自己)。请使用堆栈方法:

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

好运。