Maze Generation Algorithms

Maze algorithms are used to generate mazes. They are given a grid of cell separated by walls, and they output a maze by systematically breaking down a set of walls. Due to the method of generation, it is assured that there is only one path between two points on the maze. There are several maze generation algorithms, each with their own pros and cons in terms of length of passages, frequency and length of dead ends, and computational resources demanded.


Choose a maze generation algorithm

Description

1) Iterated Depth First Search: Maintains a stack of cells whose neighbours haven't been explored yet

  1. A random cell is chosen, marked as visited and pushed to the stack
  2. While the stack is not empty, the following steps are carried out:
    1. The last cell from the stack is obtained and designated as the current cell
    2. If it has any neighbouring cell(s) that have not been visited yet, then the current cell is again added to the stack. An unvisited neighbour is chosen at random, marked as visited and designated as the chosen cell. The wall between the current cell and the chosen cell is removed. The chosen cell is pushed to the stack
    3. If it does not have any neighbouring unvisited cell, then it's exploraton potential has been fully utilised

The current cell is painted yellow. Cells that are suspected of having unexplored neighbours are red while those that surely don't have any unexplored neighbours are blue.


2) Randomized Kruskal: Requires a randomized list of all walls and a list of sets, each containing only one cell at the beginning

For each wall in the list of walls, if the cells divided by the wall lie in disjoint sets, then the wall is removed and the sets are merged.

Cells whose parent sets have been merged atleast once are colored blue. The current wall is stroked yellow.


3) Randomized Prim: Requires a stack of walls which surround the currently visited cells.

  1. A random cell is chosen, marked as visited. It's surrounding walls are pushed to the stack
  2. While the wall stack is not empty, the following steps are repeated:
    1. A random wall is selected from the stack. If either cell separated by the wall is unvisited, then the unvisited cell is marked as visited, and it's surrounding walls are added to the stack
    2. The aforementioned wall is removed from the stack as well as the maze.

Visited cells are marked with blue and the wall under consideration is stroked with yellow.


Analysis of Algorithms

  1. Iterated Depth First Search: Has a bias for generating long corridors, due to its very method of operation. Considerably difficult for humans to solve. Moderate space and time complexity
  2. Randomized Kruskal: Generates lot of small dead-ends. Simple for humans to solve. High space complexity and moderate time complexity
  3. Randomized Prim: Generates more dead-ends than Kruskal. Extremely simple for humans to solve. Moderate space and time complexity. Considerable resources wasted on redundant tasks

Note:
  1. If the simulation freezes at any point then please refresh the page.
  2. Related: Sorting Algorithms.

Developed by ChanRT | Fork me at GitHub