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