Size:
Probability of random:
A* heuristic greed factor:
Attempts to place rooms:
Boundaries to break at once (higher = more connected maze):

Regenerate on settings change
Pathfind on settings change
Dungeon Mode
Show stats (lowers performance)




Target updates per second:



Mazes are generated by the Growing Tree algorithm, which works as follows:
  1. Pick a random cell to start at. Add it to the list of selected cells.
  2. Pick a cell from the list of selected cells.
  3. If the chosen cell has no unvisited neighbours, remove it from the list of selected cells.
  4. If the chosen cell has unvisited neighbours, pick an unvisited neighbour at random, remove the wall between the two cells, and add the neighbour to the list of selected cells.
  5. Repeat steps 2-4 until the list of selected cells is empty.
The key to the Growing Tree algorithm is the method by which we pick a cell in step 2. If we pick the most recently added cell, the algorithm behaves identically to a randomised depth-first search or recursive backtracker algorithm. If a cell is chosen at random, the algorithm behaves identically to Prim's algorithm.

By deciding at random whether to pick the most recent cell or a random cell, we achieve a middle ground between the long and winding corridoors of a recursive backtracker and the chaotic branching of Prim's algorithm. You can change the probability of choosing a cell at random as opposed to the most recent cell with the slider above.

When generating bit-by-bit, grey cells are unvisited, pink cells are on the list of selected cells, white cells are visited and not on the list, and the red cell is the most recently modified cell.

Pathfinding is done via the A* algorithm, using the Manhattan heuristic multiplied by the greed factor above. Greed factors less than or equal to 1 are guaranteed to find the shortest path, but tend to be slower, as they cause A* to behave more like a breadth-first search - in fact, at a greed factor of 0, the algorithm is identical to a breadth-first search. Greed factors higher than 1 tend to be faster, but can find paths that are not the shortest possible, as the algorithm starts to perform more like a greedy best-first search.

Tips: Pure mazes tend to look nicer with lower [probability of random], as it results in more winding corridors. Dungeon mode tends to look nicer with higher [probability of random] as it means the paths between rooms are less convoluted.