Maze Generation: Recursive Backtracker

This article is inspired by Jamis Buck’s presentation(Algorithm is not a 4-letter word). I’ve talked before about Maze Generation and its importance in acmASCIS blog, it’s great and interesting topic. In this post we’ll talk about a technique of generating a perfect maze, it’s Recursive Backtracking . Recursive backtracking is an algorithm for solving and generating perfect mazes. This algorithm is fast, easy to understand and straightforward to implement, but the maze is still biased(check Jamis Buck’s Presentation about Biased Maze Concept). Recursive backtracker performs a drunkard’s walk from the starting point by randomizing the visited child node at each level, but with some modifications on the drunkard’s walk ,as  it pushes each visited node onto a stack and when it reached a dead-end it pops the nodes off the stack until it finds one that it can continue walking from instead of doing O(n) Search. Algorithm Steps from Jamis Buck’s Blog:

  1. Choose a starting point in the field.
  2. Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
  3. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
  4. The algorithm ends when the process has backed all the way up to the starting point.

    you can check the animation introduced by Jamis Buck (here).

Implementation:

Here’s my Implementation in C#.

  1. publicoverridevoid GenerateMaze()
  2.         {
  3.             while (NumOfVisitedCells < TotalCells)
  4.             {
  5.                 ArrayList adjcentCells = this.GetNeighborsWithWalls(currentCell);
  6.                 if (adjcentCells.Count > 0)
  7.                 {
  8.                     int randomCell = Cell.theRandom.Next(0, adjcentCells.Count);
  9.                     Cell aCell = ((Cell)adjcentCells[randomCell]);
  10.                     currentCell.KnockDownWall(aCell);
  11.                     cellStack.Push(currentCell);
  12.                     currentCell = aCell;
  13.                     numOfVisitesCells++;
  14.                 }
  15.                 else
  16.                 {
  17.                     currentCell = (Cell)cellStack.Pop();
  18.                 }
  19.             }
  20.         }

you can try simple .exe file Maze Generation.exe.

Advertisements

2 thoughts on “Maze Generation: Recursive Backtracker

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s