使用DFS的迷宮一代

我試圖在Objective-C中生成一個迷宮。我已經構建了一個圖並連接了所有的邊（我認爲）。但是，當我試圖製造實際的迷宮時，我陷入了困境。使用DFS的迷宮一代

下面是我使用的代碼：

- (void)visitFromCurrentPoint:(GridPoint *)point fromPreviousVertex:(Vertex *)prev { 

if ([grid allVerticiesVisited]) { 
    NSLog(@"done!"); 
    return; 
} 
Vertex *cur = [grid vertexAtPoint:point]; 
[grid setVertextVisited:cur]; 
NSArray *borderingVerticies = [grid verticiesBorderingPoint:point]; 
Vertex *randomVertex; 
int random = arc4random()%[borderingVerticies count]; 
randomVertex = [borderingVerticies objectAtIndex:random]; 
if (![randomVertex visited]) { 
    [cur.edgeList removeObject:prev]; 
    [prev.edgeList removeObject:cur]; 
    [self visitFromCurrentPoint:[randomVertex point] fromPreviousVertex:cur]; 
} 
else { 
    [self visitFromCurrentPoint:point fromPreviousVertex:cur]; 
} 
}

然而，這並不工作，我得到一個堆棧溢出。你能看到我做錯了什麼嗎？

在此先感謝！

來源

2012-08-03 strange quark

那麼這裏有什麼問題？ – 2012-08-03 19:11:55

@ BlueRaja-DannyPflughoeft哎呀，甚至忘了問。我得到一個堆棧溢出。我已經編輯了這個問題，現在就包括這個。抱歉! – 2012-08-03 19:14:35

遞歸太多了 – nielsbot 2012-08-03 19:29:55

這是由遞歸太多造成的。嘗試一種迭代解決方案。

澄清：每個函數調用使用一些棧空間來傳遞參數和/或保存將在被調用函數範圍內更改的CPU寄存器的狀態。如果你正在進行非常深的遞歸，那麼最終可能會使用所有的堆棧空間，因此會導致崩潰。

迭代解決方案通過用動態大小的數組或隊列替換系統堆棧來避免此問題。這使用系統內存而不是堆棧空間。

（基本上是一個遞歸解決方案，您使用隊列或數組中的功能將不能自動記賬的，你通過遞歸函數調用得到的地方）第一

另一種選擇可能是廣度優先遞歸與深度。

來源

2012-08-03 19:30:16 nielsbot

使用DFS的迷宮一代

回答

相關問題