Archived

This topic is now archived and is closed to further replies.

can't understand this maze generating algorithm

This topic is 5587 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In one of my books ("Computer Graphics using Open GL by F. S. Hill, JR.) He lists a maze generating algorithm that can be used to generate a maze. I think i could code it and it would work, but thinking about it i can''t exactly figure out exactly how... here is what he says: "Generating a Maze Start with all walls intact, so that the maze is a simple grid of horizontal and vertical lines. The program draws this grid. An invisible "mouse" whose job is to "eat" through walls to connect adjacent cells is initially placed in some arbitrarily chosen cell. The mouse checks the four neighbor cells (above, below, left, and right) and, for each neighbor, asks wether it has all four walls intact. If not the cell has previously been visited and so is already on some path. The mouse may detect several candidate cells that haven''t been visited: It chooses one randomly and eats through the connecting wall, saving the locations of the other candidates on a stack. The wall that is eaten is erased, and the mouse repeates the process. When it becomes trapped at a dead end--surrounded by visited cells--it pops an unvisited cell and continues. When the stack is empty, all cells in the maze have been visited. A "start" and "end" cell is then chosen randomly, most likely along some edge of the maze." First off i guess i should say that the text is a little vague to me and i''m assuming that first you only chose a wall to eat that conects a cell that hasn''t been visited (it doesn''t quite say that literally) and 2nd that after you eat a wall you move into the cell you just opened a conection to and repeat... maybe i''m wrong with those? Ok i get the first part, but it seems that will just give each cell 2 openings, one way in and one way out. A maze is based around having to make a choice about where to go next, ie a cell with one inlet , and 2 or more outlets. I don''t see how this algorithm generates them. It seems to me that it would just create several ''paths'' that are straight begining to end that are completly isolated from eachother. But it seems to generate one where each cell can be reached from any other. The only place i see the conections between the path being made are if you push a cell on the stack, then visit it, then pop it off the stack. But that seems like a rare case that wouldn''t make all the conections. Anyone know why this works?

Share this post


Link to post
Share on other sites
In their attempt to present the algorithm is a cutesy mouse metaphor, I think the writers lost/neglected some important details. I have implemented this algorithm numerous times so I think I can explain it:

You have a stack as the description suggests. In the process of generating the maze, you only empty the stack once, and when this occurs the maze is done (there are no unexplored cells left). Rather than checking the neighboring cell''s walls, simply check to see if the neighboring cell has been hollowed out. If it has not, you can tunnel to it. Also, you should be picking which neighboring cell to look at first using a random number generator. This allows the maze to be "mazy" instead of a simple straight line. Eventually the tip of the passage will run itself into a place where you can''t continue: there will be hollowed out cells on all 4 sides. When this happens you backtrack one step in the stack to an earlier location and look again. If you are still trapped, you will backtrack another step, etc. This results in a kind of depth-first search attempting to "flood-fill" the area with maze tendrils. Eventually there will be no empty cells left and you will backtrack to the bottom of the stack (empty) and then you know the maze is done. It appears the description you quoted left out the important element of randomness.

What I have noticed in my experimentation with this algorithm is that you can get better mazes by using a queue instead of a stack. That''s because when you use a stack, related passages tend to end up right next to each other and many of them end up quite short. But if you use a queue, "backtracking" one step will take you to a very different location than your current dead end. I''ve also noticed you can set a "maximum passage length" and still almost always get a full maze. For instance, if you have gone 30 steps without backtracking you can force a backtrack (works best with a queue rather than a stack). This results in a maze with more even passage lengths instead of some very long passages with a few very short and obvious dead ends along the way. Enforcing a maximum passage length results in a higher branching factor, and some cells being ignored. But since cells are checked many times in the process of generating the maze, it is highly unlikely that a cell will be permanently missed. Cells don''t tend to be missed until your maximum passage length gets down to the 5-step range (where you ignore the next options every 5 steps you take, and force a backtrack). hope this helps you understand the algorithm. If you''d like to see it in action (with modifications to allow diagonal passages and wide passages and walls) you can see it implemented in teh maze generator in the Scrolling Game Development Kit at http://gamedev.sf.net/. (It''s open source so you can see the source code too.)

"All you need to do to learn circular logic is learn circular logic"

Share this post


Link to post
Share on other sites