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.