Maze generation using DFS

Question

I'm trying to generate a maze in Objective-C. I've constructed a graph and connected all the edges (I think). However, I'm getting stuck when trying to make the actual maze.

Here's the code I'm using:

- (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];
}
}

However, this doesn't work and I get a stack overflow. Can you see what I'm doing wrong?

Thanks in advance!

@BlueRaja-DannyPflughoeft Oops, forgot to even ask. I'm getting a stack overflow. I've edited the question to include that now. Sorry! — strange quark

nielsbot nielsbot · Accepted Answer · 2012-08-03T19:30:16

This is caused by too much recursion. Try an iterative solution.

To clarify: each function call uses a bit of stack space to pass arguments and/or save the state of CPU registers that will be altered during the scope of the called function. If you are doing really deep recursion, you can end up using all your stack space, hence the crash.

An iterative solution avoids the problem by replacing the system stack with a dynamically sized array or queue. This uses system memory instead of stack space.

(basically a recursive solution where you use a queue or array in your function to take the place of the automatic bookkeeping you get via recursive function calls)

Another option might be breadth-first recursion vs. depth first.

Maze generation using DFS

1 Answers