Algorithms

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