Directed mazes

[econrad003]

I think the following algorithms can be used for two pass creation of directed mazes:

1. Binary Tree (the version as given by Jamis Buck).

Pass 1: N/E binary tree directing edges N and E. The NE corner is easily reachable from every vertex. Pass 2: N/E binary tree directing edges S and W. Now the every vertex is easily reachable from the NE corner.

Given vertices (i.e. cells) u and v, to find a directed path from u to v, let P be the pass 1 directed path from u to the NE corner, and let Q be the pass 2 directed path from the NE corner to v. Then P+Q is a directed path from u to v.

2. Sidewinder

Generally the same idea as in Binary Tree. When closing a run in pass 1, E/W arcs are directed towards the escape to the N. When closing a run in pass 2, E/W arcs are directed away from the southward feed from the N.

3. Recursive Backtracker (DFS)

Again two passes, both with the same start node. In the first pass we direct arcs backward from child to parent in the DFS search tree. In the second pass, we direct arcs from parent to child.

The result is that from any vertex v there are directed paths both to and from the start vertex s. So start vertex s is like the NE corner in Binary Tree.

Other growing tree algorithms should work in the same fashion.

4. First-entry Aldous/Broder

Pass 1: when entering a cell the first time, direct an arc from the cell into the visited area Pass 2: same start vertex, but when entering a cell for the first time, direct an arc into the cell from the visited area.

5. Hybrids

Pass 1: use pass 1 in any algorithm above Pass 2: using the same start vertex (this will be the NE corner if Binary Tree or Sidewinder was used for pass 1, and must be the NE corner if this pass is Binary Tree or Sidewinder), apply pass 2 from any algorithm above.

[econrad003]

In addition, the following tools may be useful in creating directed mazes:

1. a tool to change undirected edges into directed arcs by coin flips - two steps per edge: a. heads - modify the edge; tails - leave it alone b. heads - direct it forward; tails - direct it backward

Caution here: we don't want to run this twice on an edge.

2. A tool to form relative meets, joins and complements

Not sure how useful these would be in practice... But note that the above algorithms suggest that joins have a practical use.

[econrad003]

I am currently working on this in the context of rectangular grids. At the moment, I have:

1. a layout class for directed rectangular mazes that works quite well;
2. a N/E binary tree algorithm which creates directed passages; and
3. a demonstration script.

The layout class doesn't handle one-way tunnels yet, so it is not yet suitable for use with weave mazes. The binary tree algorithm is complete. The demonstration script is in line with what I've done so far. Some samples follow.

1. a 3 by 5 directed binary tree maze: (The links in the NE corner were turned into two-way links for demonstration purposes. The algorithm only produces one-way links. Note that coloring is supported.)

2. Another 3x5 demo, with inset walls and passages. In this case we have two directed binary trees superimposed on one another, one leading towards the root in the NE corner, and the other leading away from the root cell:

3. A larger demo, also inset, also two superimposed directed binary tree mazes, one directed towards the NE corner, the other away.

Before I release the code, I'd like to (1) handle one-way tunnels in weave mazes and (2) one-way stairwells ("escalators"?) in multilevel mazes; (3) more algorithms and, of course, (4) a reasonable complement of demonstrations.

[econrad003]

Sidewinder is now complete -- at least it works correctly with forward east and up north. I've replaced the thick lines with thinner lines in the layout. (It's one extra line of code in the demo, but I think it looks better on the dense image.) Note the characteristic top row. This is actually two passes of E/N sidewinder, one with arcs directed towards the NE corner, and the other directed away. Each cell should have a minimum of two arcs, one directed into the cell, and the other directed out. If a passage has no arrow, it indicates that it is bidirectional, i.e. both an in-passage and an out-passage. Note also that the top row is connected by bidirectional passages. A typical puzzle might be: start in the SW corner, work your way through the maze to a cell in the top row where some object has been place and find your way to the exit in the SE corner. There is also the Theseus puzzle: start in the SW corner, find your way to the Minotaur somewhere in the north row, slay the Minotaur, and trace your way back to the SW corner to Ariadne (who is later abandoned on a deserted island somewhere in the Mediterranean, but that's another story.)

[econrad003]

Oops! I see that there are no arrows into the north row, Well still some work to do...

A second look finds that there is indeed one arrow into the top row from the row below. It is about eight columns of the way across (or about one fourth of the way) from the left.. But there is still a bug. Note that the maze is disconnected even if we ignore the arrows. Also, there are some interesting artifacts of the bug (or bugs) in the second row,

[econrad003]

The bug turned out to be quite simple. When closing out the runs, I failed to reset the list of cells in the run to the empty list. The result was that some of the links that were created were to cells that weren't actually in the run. In all but the top row, the more cells that were processed, the more likely that northward links were not valid. The correction was one line of code:

In method close_out_run(self), replace the line

return None with the line self.fwdrun = [] Of course finding the error was harder than fixing it.

Here is a 5 by 5 directed sidewinder maze with arrows directed towards terminus:

And here is a full-sized one with arrows directed away:

[econrad003]

Recursive Backtracker (or depth-first seach) is now complete. During the course of debugging, I investigated weave mazes. There are some complications related to tunnelling, specifically in (but not limited to) the can_tunnel methods. So I've decided not deal with weave mazes for the time being. Perhaps they will be a later enhancement. In any case, here is a recursive backtracker run. The terminus is displayed in orange. The maze is produced with two runs, the first with arrows leading to the terminus (treating it as the sink) and the second with arrows leading away from the terminus (now treating it as the source). There should be at least one directed path between any pair of vertices. There are directed circuits in the maze, and there may be more than one simple directed path between some pairs of vertices. (These are features, not bugs.)

[econrad003]

With the implementation of directed Aldous/Broder, this issue is now closed, See the README (or CHANGELOG) for information on the September 29 update.