Recursive Backtracker Maze Algorithm:
- Go in random unvisited direction and backtrack when each direction is visited until everything is visited
Jamis Buck Maze Algorithm:
- Similar to Recursive Backtracker
- Addition of some parameters that control bias of turning
Recursive Backtracker (left) versus Jamis Buck (right)
- Change the state of a grid cell (whether it can be walked on or not) based on neighboring states
- If (parameter_above = 5) or more of neighbors are "walkable" then this cell is walkable.
- If (parameter_under = 2) or less of neighbors are NOT "walkable" this this cell is non-walkable.
- Run the above to "erode" the dungeon
- No guarantee of connectedness without further work
Examples of Cellular Automata:
BSP Tree (Binary Space Partion):
- Split the component in half either vertically or horizontally at some position
- Recurse into each half and repeat until the components are "small enough"
- Add rooms to each resulting component after tree is generated
- Connect rooms (by connecting each component to its sibling)
- Connectedness *is* guaranteed as a property of the BSP Tree
Examples of BSP Tree Dungeons: