Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Please have a look at this link:

http://en.wikipedia.org/wiki/Maze_generation#Depth-first_search

Here, the theoretical algorithm given is:

Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell.

But I don't think the animation on it's right uses the same algorithm to generate the maze, though it's not incorrect.

I feel the animation uses this algorithm:

  1. Start with any unvisited cell, make it a part of the maze and mark it visited.
  2. Add the unvisited neighbours of that cell to the set of cells that can be considered next
  3. Choose any one of cells from the set and mark it visited.
  4. Check if that cell does not have any neighbours that are visited except ONE (the one which caused this cell to be added to the set in the first place). Else go to 3.
  5. Continue till all cells are visited.

Am I wrong?

share|improve this question
1  
Wikipedia has a discussion tab for every question. In addition, the bar for editing is fairly low, although be prepared for your edits to be challenged. –  Robert Harvey Apr 23 '12 at 21:41

1 Answer 1

up vote 2 down vote accepted

The animation uses the algorithm that the article describes. Their stack consists of the cells that have been visited. When they reach a dead end, they backtrack by popping cells off the stack until they come across one that has an unvisited neighbor and then start exploring a path beginning at that cell (by pushing that cell onto the stack).

They are not keeping a set of unvisited cells and randomly choosing another one to visit. If you look closely, they always choose to explore starting at a cell closest to the red square.

If we label the cells so that the bottom left cell is (1, 1) and the top right cell is (30, 20) you notice that its first 'decision' at time 0:03 when it hits a dead-end at (1, 5). It backtracks to the last cell with an unvisited neighbor (1, 7) and is forced to explore (1, 8) next. If I understand the algorithm you describe, you would be randomly choosing a any cell which touched part of the path that was generated already.

share|improve this answer
    
It hits a dead end at (1,5)? Are we both looking at the right video? link The maze has progressed far beyond (1,5) by time 0:03.. And from the image that I gave the link to, it appears as if the first decision is taken when the red square reaches (7,3) and the traversal path is: (1,1) (1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (5,1) (6,1) (7,1) (8,1) (9,1) (9,2) (9,3) (9,4) (9,5) (8,5) (7,5) (6,5) (5,5) (5,4) (5,3) (6,3) (7,3) –  Programming Noob Apr 24 '12 at 23:42
    
I understand what you say about backtracking to the last cell with an unvisited neighbor, so after reaching (7,3) it must back track to (6,3) and (6,3) still has unvisited neighbors - which are (6,4) and (6,2) right? So why is the next cell chosen after (7,3), (4,5)? Sorry if this is confusing lol. Tell me if you didn't get anything.. –  Programming Noob Apr 24 '12 at 23:42
    
Ok I think I got it. The animation there assumes the cells adjacent to the cell under consideration as it's 'walls'. I thought a 'wall' was the common edge between two adjacent cells... –  Programming Noob Apr 24 '12 at 23:47
    
Actually the place I described was the 2nd backtrack. I couldn't see the first one because the video bar was in the way. the first time it backtracked was when it went from (4, 2) and backtracked 2 spaces to go back to space (3, 3) where it randomly chose to start going left to (2, 3). The 2nd time it backtracks is when it hits the dead-end at (1, 5) –  WuHoUnited Apr 25 '12 at 2:46
    
I think you're also counting the squares incorrectly. The maze starts at (1, 1) and then goes to (1, 2) and then turns right to (2, 2). –  WuHoUnited Apr 25 '12 at 2:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.