The Generation Algorithms

In order to generate mazes with a variety of styles, four different algorithms were implemented for both 2D and 3D with one having further custimation for more variation. Each algorithm creates a different style of maze.


Recusive Backtrack


Pattern:

  • Pleasing, random appearance
  • Relatively long sections before a branch

Algorithm:

  • Works by randomly selecting a path until there are no more valid moves (there are no unvisited adjacent cells)
  • Next moves back until another move is possible
  • Continues until the whole maze has been visited

Recusive Division


Pattern:

  • Lots of intersections between paths
  • Long straight lines of walls

Algorithm:

  • Randomly places a wall dividing the maze in two and picks a random opening
  • Then does that same division with the two new sections

Prim's Algorithm


Pattern:

  • Lots of intersections between paths
  • Shorter and more random wall segments

Pattern:

  • Picks a random starting point
  • Continuously picks a random cell from the unvisited neighbors of the current visited cells

Growing Tree Algorithm


Pattern:

  • Can look like Prim’s, Recursive Back-tracker, both and more
  • It depends on the parameters

Pattern:

  • Pick a random cell and store it in a list
  • Randomly pick more cells until no longer possible
  • Once a dead-end is hit, use some condition to pick the next cell to iterate from

Parameters:

  • New: Picks the newest cell to be added to the list to continue from; works exactly like recursive backtrack)
  • Old: Picks the oldest cell still in the list to continue from; causes lots of straight paths originating from random starting point
  • Random: Picks a random cell from the list to continue from; works and looks similar to Prim's Algorithm