"Yet another maze implementation" by Eric Conrad.
This is a collection of maze algorithms and scripts that were implemented primarily in Python 3. Most of these programs are based on suggestions and ideas found in an wonderful little book by Jamis Buck called Mazes for Programmers. See the references at the end for more information. (My recommendation: buy this book. In addition to learning about mazes, you will pick up some graph theory and ruby language programming.) I've made some departures from Buck's approaches, so my programs are not simply translations from ruby into python.
The scripts entab.py and detab.py are respectively a script to replace spaces by tabs and a script to replace tabs by spaces. They have nothing to do with mazes. I use them because the text editor that I use (Gnome's TextEditor) cannot be configured to use spaces for Python and tabs for some other language. The space/tab configuration is all or nothing. Nor can it be configured correctly to do entabbing or detabbing.
The list of older changes, going back to 14 July 2020, has been moved to file CHANGELOG.md. A short list of recent changes will continue to appear here before being archived in CHANGELOG.md.
Directed mazes -- Four directed maze generation algorithms have been implemented. These are binary tree (first version), sidewinder, recursive backtracker, and Aldous/Broder (both first entrance and last exit). A layout new program using matplotlib supports directed rectangular mazes. See the demonstration script directed_maze_demo.py for some examples and some details.
The python implementations of the directed maze generation algorithms are described briefly at the end of Section 3.1 below. They are: di_aldous_broder.py, di_binary_tree.py, di_recursive_backtracker.py, and di_sidewinder.py.
This closes issue #12 (Directed mazes).
Inform 7 code -- The first steps in generating Inform 7 code from a maze on a 3-dimensional grid are complete. This is done in two steps. First, the maze is "saved" as an editable INI configuration file which contains grid and maze information. Then the configuration file is used to generate Inform 7 statements. Section 5.2 of the README.md file has more information.
At the moment the implementations in grid3d.py (to generate the INI file) and inform7.py (to generate the Inform 7 code) are both crude and preliminary, but they should at least be functional.
The Floyd-Warshall algorithm -- The Floyd-Warshall algorithm (known by a number of names, including, more simply, Floyd's algorithm) is an algorithm for finding all minimum weight paths in a directed graph, or, in our case, in a directed maze. (At the moment, we don't have directed maze generation algorithms, though several implemented algorithms, including Binary Tree (au Jamis Buck), Sidewinder, Aldous-Broder and Recursive Backtracker (DFS) can easily be adapted for that purpose, or so I hope.) It produces a state matrix with running time that is cubic in the number of vertices. It is implemented in floyds.py and there is a simple demonstration in floyds_demo.py.
It has a number of uses, including detecting negative weight cycles (in linear time), finding minimum weight paths (in linear time), and checking reachability (in linear time), and determining whether one given vertex is reachable from another given vertex (in constant time).
N.B. The adaptations of the four above-mentioned maze generation algorithms will (I hope!) be included in the next update. The demonstration program floyds_demo.py will probably be extended to include one or more of these algorithm implementations.
In the descriptions, the terms spanning tree and perfect maze are used interchangeably. They do really mean exactly the same thing. They only differ in the underlying context.
aldous_broder.py - implementations of the first-entrance random walk algorithm (Aldous/Broder) and the last-exit random walk algorithm (reverse Aldous/Broder, see [6]) for generating (theoretically) uniformly random spanning trees on a connected simple graph, or equivalently, uniformly random perfect mazes on a connected grid. (The first-entrance algorithm is described in Buck (2015).) The algorithm tends to start quickly and end slowly, unlike Wilson's algorithm which tends to start slowly and end quickly.
binary_tree.py - implementation of a simple binary spanning tree algorithm for rectangular mazes. This is the binary tree algorithm described in Buck (2015).
binary_tree2.py - implementation of a binary tree algorithm that works most of the time for generating perfect mazes on arbitrary grids. When it fails, the result is a binary spanning forest. When used on rectangular grids, the result is typically a binary spanning tree which cannot be produced by Jamis Buck's binary tree algorithm.
boruvkas.py - Borůvka's algorithm [8] (and see also [7]) is an algorithm to create minimum-weight spanning trees from connected edge-weighted graphs, provided the weight function is injective. (If the weight function is not one-to-one, the result is a connected spanning subgraph which could contain circuits. [N.B.: This is either a bug or a feature of the algorithm, depending on one's point of view.]) Python program boruvkas.py is an implementation of Borůvka's algorithm for creating mazes. To insure that weights are unique, the default weight function is a random one-to-one map from the grid edges into range [1,e], where e is the number of grid edges. As with Kruskal's algorithm, edge costs need to be known a priori, so the algorithm does not create weave mazes in a natural way, but like Kruskal's algorithm, the algorithm can be used to extend forests to spanning trees, and thus it is well-suited to mazes with prewoven crossings.
binary_tree_polar.py - an adaptation of the simple binary tree algorithm from Buck (2015) for theta (polar) mazes.
complete_maze.py - this program, intended primarily for testing purposes, generates a complete maze on a grid, i.e. a maze in which every grid connection is linked. In graph-theoretic terms, viewing the grid as a given graph and a maze as isomorphic to a subgraph of the grid, then this generates a maze which is isomorphic to the grid.
edgewise_growing_tree.py - a family of algorithms for creating spanning trees (perfect mazes) on edge-weighted connected graphs (grids) that are similar in form to Prim's algorithm.
hunt_and_kill.py - an implementation of the Hunt and Kill algorithm described in Chapter 5 of Buck (2015).
ellers.py - an implementation of Eller's algorithm as described in Chapter 12 of the Jamis Buck book [1]. The algorithm is suitable as implemented for rectangular grids using "north" and "east" row and column grid connections. In polar_ellers.py, there is an adaptation of the state matrix that uses the "inward" and "ccw" grid connections -- this variant make the Eller's algorithm implementation work with polar maze.
high_card_wins.py - a generalization of the binary tree algorithm described in Chapter 1 of Buck [1]. This also includes the ternary tree algorithm described in Chapter 12 as another special case. (Note: It is called the 'Trinary Tree' algorithm on page 219.) The basic idea of the algorithm is that players, representing grid directions, go from cell to cell. At each cell any players who won't create a circuit are dealt a card. The player who has the high card makes the maze connection. The game continues until the maze is connected.
inwinder.py - an adaptation of the sidewinder algorithm for theta (polar) mazes.
kruskals.py - an implementation of Kruskal's minimum weight spanning tree algorithm tocreate perfect mazes. The implementation includes some special handling for Preweave mazes to allow for random tunneling and for the creation of long tunnels. (This implementation closely follows the approaches used in the Jamis Buck book. See chapters 9 and 10 in [1].)
multilevel_mst.py - state classes for prewoven multilevel mazes, to be used with Kruskal's algorithm and with Borůvka's algorithm. (A state class for use with Prim's algorithm should be available in the near future.)
prims.py - an implementation of Prim's minimum weight spanning tree algorithm to create perfect mazes. This is the algorithm described in the beginning of Chapter 11 of [1], with implementation left as an exercise ("Truest Prim").
recursive_backtracker.py - the unfortunately misnamed depth-first search algorithm for producing perfect mazes in a connected grid. The implementation is stack-based to avoid explicit recursion. (See also: tree_search.py.)
recursive_division.py - a maze generation algorithm (recursive division) which recursively partitions a grid (in the manner of quicksort) until minimal partitions are obtained. In [1], the algorithm is implemented as a wall adder. Here it is implemented as a passage carver using a State object as in the implementations of Kruskal's algorithm, Prim's algorithm, vertex-Prim's, and Borůvka's algorithm. The partitions are created in pairs, with a door to connect paired partitions. Minimal partitions are carved using some other maze algorithm. The default settings are to create rectangular partitions on a rectangular grid, with minimal partitions being those which are either one cell in width or one cell in height, and to use Sidewinder to carve mazes in the minimal partitions. The defaults can be reconfigured by creating subclasses of the State object and supplying any necessary methods. The supplied State classes allow some simple reconfiguration.
sidewinder.py - a modification of Buck's binary spanning tree algorithm which eliminates one bias in that algorithm. It only works on rectangular grids or (more generally) on grids which can be traversed in two orthogonal directions. The resulting spanning trees can be binary, but usually are not.
vertexwise_growing_tree.py - a family of algorithms for creating spanning trees (perfect mazes) on vertex-weighted connected graphs (grids) that are superficially similar to Prim's algorithm. These are all built on an algorithm that, for lack of a better name, I call vertex Prim. These algorithms are similar to the algorithms "Simple Prim" and "True Prim", and two of the growing tree algorithms that were implemented in Chapter 11 of [1].
tree_search.py - included are alternative spanning tree search algorithms using a queue (breadth-first search) or a priority-queue (best-first search). These complement the stack-based depth-first search algorithm used in recursive_backtracker.py.
wilson.py - Wilson's algorithm, a theoretically unbiased spanning tree algorithm that uses a loop-erased random walk of the grid. In addition, the program includes a hybrid Aldous/Broder/Wilson algorithm that starts the random walk using the first-entrance algorithm of Aldous and Broder and finishes using the loop-erased random walk due to Wilson. Wilson's algorithm tends to start slowly and end quickly. The hybrid algorithm tends to start and end quickly, slowing down as it approaches the middle using Aldous/Broder, then speeding up after Wilson's algorithm takes control. I don't know whether the hybrid algorithm is biased.
Directed algorithms - directed versions of some of the algorithms have also been implemented. These produce one-way links instead of two-way links:
The demonstration script konigsberg_demo.py produces a maze based on the Königsberg bridges problem (Leonhard Euler, 1736). It uses the recursive backtracker algorithm followed by one pass of simple braiding to insure that bridges are passable. Cell removal and cell coloring are governed by a template file input/königsberg.txt and sample output is in demos/königsberg.png. For background, see references [2] through [5].
The programs grid.py and cell.py describe the basic grid and cell classes that underly all mazes and the grids that they span.
The function of the various cell programs should be mostly self-explanatory. Much of the actual work is done in the grid programs and in the layout programs. ASCII and unicode layout are handled in rectangular_grid.py.
Several types of layouts are supported. ASCII and unicode layouts are supported on rectangular grids and on some grids derived from rectangular grids (for example, cylinder grids). All grids support GraphViz/dot layout, though the results usually leave a lot to be desired.
Most derived grids support plot layouts using MatPlotLib, though in most cases, support will require some direct use of MatPlotLib methods. See the scripts for examples.
These typically require a substantial amount of tweaking.
Inform 7 is a declarative language used primarily to produce interactive fiction (aka text adventures). A classic example of interactive fiction is the game Cave (aka Adventure) from the early 1980s. Modern versions of Cave can be found on the Interactive Fiction Archive at https://ifarchive.org under the names Adventure and Colossal Cave. Cave also inspired a commercial game called Zork. Information about Inform 7 can be found on the Inform 7 web site at http://inform7.com/.
Inform 7 code can be generated in two or three steps from a supported grid to represent a maze in Inform. Supported grids are 3-D grids (defined in *grid3d.py) and their subclasses. (Rectangular grids and weave grids may be backfitted with support sometime in the future.) The required steps are:
For help generating the INI file or with generating the maze from the INI file, see the examples in inform7_demo.py.
The generator handles both one-way and two-way links. Typical generated code looks something like this:
[definitions needed for one-way links]
The verb to be eastward from means the reversed mapping east relation.
Cell1 is a room. The description is "There are exits east and northeast.".
[defining a one-way link]
Cell2 is a room. It is a room eastward from Cell1.
The description is "There is an exit north.".
[defining two two-way links]
Cell3 is a room. It is northeast from Cell1. It is north from Cell2.
The description is "There are exits south and southwest."Buck (2015) - Jamis Buck. Mazes for Programmers. Pragmatic Bookshelf, 2015. ISBN-13 978-1-68050-055-4.
Leonhard Euler (1736). "Solutio problematis ad geometriam situs pertinentis". Comment Acad Sci U Petrop 8, 128–40.
Carl Hierholzer (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen, 6 (1): 30–32, doi:10.1007/BF01442866.
"Eulerian path". Wikipedia, 5 Aug. 2020. Web, accessed 8 Aug. 2020. Wikipedia: https://en.wikipedia.org/wiki/Eulerian_path
"Seven bridges of Königsberg". Wikipedia, 6 Jun. 2020. Web, accessed 8 Aug. 2020. Wikipedia: https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
Yiping Hu, Russell Lyons and Pengfei Tang. "A reverse Aldous/Broder algorithm". Preprint. Web: arXiv.org. 24 Jul 2019. Arxiv.org: http://arxiv.org/abs/1907.10196v1
Bernard Chazelle. "A minimum spanning tree algorithm with inverse-Ackermann type complexity". J ACM 47 (2000), 1028-1047. Preprint: https://www.cs.princeton.edu/~chazelle/pubs/mst.pdf
"Borůvka's algorithm". Wikipedia. 10 Jun. 2020. Web, accessed 12 Aug. 2020. Wikipedia: https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm