Flexible Maze Generator
Originally based on Growing Tree algorithm, but with added features.
In essence this variant uses a mix of backtracking and random selection to fill a proportion of the grid (1.0 = all).
Complexity is the probability of using backtracking (vs. random pick) each iteration — high complexity tends to produce less branchy mazes. (The reason I called it complexity is that a complex maze is more likely to have blind alleys that aren't apparent from an intersection.)
Completeness is the number of cells the generator will "carve out".
Max isolation limits how isolated a cell can end up, where isolation is defined as the distance to the nearest junction. Algorithm only "de-isolates" 50% of eligible cells per pass, and will exit if no cells were carved during a pass. (Prevents deadlocks where setting is < 2.)
Ideas to make generated maps more "interesting" or less "random"
- Support templates.
- Allow "precarved" cells to be carved into (e.g. they might have the fifth ("16") bit set. These cells would not be added to the path, but not count as carved until the maze carve algorithm reaches them.
- Similarly, allocate sixth bit ("32") to "poison" cells (they cannot be carved).
- Add a weight to prefer carving in the same direction (kinkiness!).
- Add a mechanism for placing "points of interest" (targets and obstacles).
- Add a mechanism for adding path-finding nodes (complete with links). Note that this dovetails with "kinkiness" since you need to add a node when you change direction. (It may be simpler and easier to generate nodes post-hoc, especially since you need to handle templates.)
- Allow rings and toruses.
- Consider something like Voronoi partitioning. Start with a set of perturbed blobs (each individual paths) then grow each one in turn until it can no longer grow or has made some number of connections (e.g. 1 to 3) with other blobs. Again, more randomness could result if the blobs have a chance of missing a turn, or growth "turns" are assigned randomly. The blobs could themselves be templates or prefabs.