使用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的迷宫一代

回答

相关问题