CODEWITHSUNDEEP
algorithmmaze
Babak Fakhriloo
Babak Fakhriloo

Reputation: 2126

maze problem and Recursive backtracker algorithm

i want to implement the Recursive backtracker algorithm to solve maze problem, but i cant understand 2.3 Command ("remove the wall between the current cell and the chosen cell") would any help me ?

  1. Mark the current cell as 'Visited'
  2. If the current cell has any neighbours which have not been visited
    1. Choose randomly one of the unvisited neighbours
    2. add the current cell to the stack
    3. remove the wall between the current cell and the chosen cell
    4. Make the chosen cell the current cell
    5. Recursively call this function
  3. else
    1. remove the last current cell from the stack
    2. Backtrack to the previous execution of this function

Edit In fact I want an algorithm to solve maze problem by using stack.

Upvotes: 2

Views: 4834

Answers (3)

ruslik
ruslik

Reputation: 14870

Your algorithm is for god mode. Normally you should do

  1. If the current cell is the exit, then finished
  2. If the current cell has any neighbours which have not been visited that are not walls
    1. Choose randomly one of the unvisited non-wall neighbours
    2. add the current cell to the stack
    3. nothing
    4. Make the chosen cell the current cell
    5. Recursively call this function
  3. else
    1. remove the last current cell from the stack
    2. Backtrack to the previous execution of this function

Upvotes: 1

Niki Yoshiuchi
Niki Yoshiuchi

Reputation: 17541

That algorithm is a maze generator not a maze solver. The idea is that you want to create a random maze. You also want all points in the maze to be reachable from all other points.

If you just randomly remove walls it is likely that your maze will not be connected. The recursive backtracking algorithm takes care of this by creating a random walk and removing the walls along that random walk. The recursive backtracking part allows you to walk to every cell in the maze, even when you reach a dead end.

Upvotes: 4

El Ronnoco
El Ronnoco

Reputation: 11922

Removing the wall simply means removing the wall! You start with a grid of cells, each of which is totally surrounded by 4 walls. As you move randomly around (2.1) you remove the wall joining the cells.

Upvotes: 0

Related Questions