多次運行洪泛填充算法時遇到堆棧溢出異常

我有一個排列在網格上的對象列表。我想刪除任何沒有路徑回到網格頂部的路徑，直接或通過它們的鄰居。多次運行洪泛填充算法時遇到堆棧溢出異常

我認爲這樣做的一個好方法是首先將網格上的所有內容都刪除，然後使頂部行上的任何內容都不可刪除。然後，我想從頂行的任何對象中進行填充，以使連接到它們的對象不可刪除。

我想不出一種方法（工程）來優化它。有沒有一種更簡單的方法可以解決我想要做的事情？

我可能通過使用列表而不是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; 
    }

來源

2011-08-03 David

總共有多少顆行星？ – dfb

@spinning_plate 0到90之間的任何地方。 – David

這不應該是應該吹捧堆棧的東西，除非在洪水填充中有一個錯誤。我沒有立即看到任何東西，但我會在第一個if語句之後的'DetectHangingNeighbours'中放置一些打印語句，以查看是否兩次擊中同一個行星。 – dfb

避免遞歸（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

祝你好運。

來源

2011-08-03 11:18:58

解開遞歸

一個答案是解開你的遞歸。你得到一個堆棧溢出，因爲遞歸的級別太多，需要內存分配才能完成並返回，從而導致「堆棧溢出」。

我已經創造了在過去的XNA遊戲，我需要的洪水填充算法的編輯限制遞歸，我就是這樣做有把上限的次數就在退出之前會遞減。實際上，這意味着我可能不得不重新對其餘未填充的部分應用大量填充，但不會導致堆棧溢出。

顏色填充算法

這使用常規的循環，以避免堆棧溢出錯誤。

來源

2011-08-03 02:24:51

多次運行洪泛填充算法時遇到堆棧溢出異常

回答

相關問題