Repository files navigation

Maze generation code, inspired by working throughMazes forProgrammers.Because the book leans on Object Oriented design (coded in Ruby), much of thisis a re-thinking of the approaches in a Clojure style.

Each maze generation algorithm is in its own namespace.

Except where otherwise noted, all algorithms produce "perfect" mazes. Perfectmazes have exactly one path between any two cells in the maze. This also meansthat you designate any two cells as the start and end and guarantee that thereis a solution.

|Usage|Algorithms|Solutions|Utilities|Presentation

Project is pretty much complete and does not have functions exposed forexternal use (such as through a command-line executable JAR file). All theexamples below assume that you are importing into a REPL for execution.

There are several ways to display a maze. The primary data structure used hereto store a maze is a vector of vectors, where each cell indicates whichdirections you can navigate out of the cell to. Each of these cells isposition-aware, with cells accessed by[row column].

Here is a 5x5 maze:

(defmaze [[[:east] [:south:west:east] [:west:east] [:west:south] [:south]] [[:east:south] [:east:north:west] [:south:west] [:north:east] [:west:north]] [[:north:east] [:west] [:south:north:east] [:west] [:south]] [[:south] [:south] [:south:north:east] [:west:east] [:west:north:south]] [[:east:north] [:north:west:east] [:west:north] [:east] [:north:west]]])

The easiest way to visualize a maze at the REPL is to generate an ASCIIversion:

user=> (require '[meiro.ascii:as ascii])niluser=> (print (ascii/render maze))+---+---+---+---+---+|               |   |+---+   +---+   +   +|           |       |+   +---+   +---+---+|       |       |   |+---+---+   +---+   +|   |   |           |+   +   +   +---+   +|           |       |+---+---+---+---+---+nil

And if you want to print or share a maze, it can be output as a PNG:

(require '[meiro.png:as png])(require '[meiro.core:as m])(require '[meiro.sidewinder:as sw])(png/render (sw/create (m/init1520))"sample-maze.png")

Which creates a PNG file like:

To print a maze with masked cells:

(defgrid (ascii/read-grid"test/meiro/template.txt"))(require '[meiro.backtracker:as b])(png/render-masked (b/create grid))

To print a circular (polar) maze:

(require '[meiro.polar:as polar])(png/render-polar  (b/create (polar/init10) [00] polar/neighbors polar/link))

To print a sigma (hex) maze:

(require '[meiro.hex:as hex])(png/render-hex  (b/create (m/init1520) [79] hex/neighbors hex/link))

To print a delta (triangle) maze:

(require '[meiro.triangle:as triangle])(defgrid (ascii/read-grid"test/meiro/triangle.txt"))(png/render-delta  (b/create grid [012] triangle/neighbors m/link))

To print a maze with an inset:

(png/render-inset (b/create (m/init825))3)

To print a maze composed of edges, the image must be bored out of a backgroundimage. Use the following:

(require '[meiro.prim:as prim])(defforest (prim/create258))(png/render-forest forest)

If you want to print an ASCII maze as if it were a series of corridors inNetHack:

(require '[meiro.nethack:as nethack])(print (nethack/render-corridor maze))####### # ####### ####### ####### ##     # # # #   # #     # #     # #### # # ### ### # ### ##### # ### #  # # #       # #   #       # #   #### # ### ### # ### ####### ### ####   #   # # # #   #       # #     ## # ### # # ### # ### ##### ##### ## # #   # #     #   # #         # ## # # ### ### ##### # ### ##### # ## # # #     # #   # #   # # #   # #### ######### ### ####### # #######

If you want to print an ASCII maze as if it were a situated in aNetHack room (corners could use some work):

(print (nethack/render-room maze))-------------------------------------|.......|.|.......|.......|.......|.||.-----.|.|.-.---.|.-----.|.-----.|.||...|.|.|...|...|.|...|.....|.|...|.||--.|.|.|------.|.|--.|------.|.---.||...|.|...|...|.|...|.......|...|...||.---.|--.|.-.|.|--.|------.|.-----.||.|.|...|.|.|...|.|...|.....|.....|.||.|.|.---.|.|----.|--.|.---------.|.||.|.|.|...|...|.....|.|...|.....|.|.||.|.|.|.-----.|.---.|.|--.|.-.---.|.||...|.........|...|.......|.|.......||------------------------------------

There are a number of different algorithms for generating mazes.

Binary Tree produces mazes by visiting each cell in a grid and opening apassage either south or east. This causes a bias toward paths which flow downand to the right. They will always have a single corridor along both thesouthern and eastern edges.

If you wish to generate and print a random binary-tree maze, you can start up aREPL and try to following:

(require '[meiro.core:as m])(require '[meiro.ascii:as ascii])(require '[meiro.binary-tree:as bt])(png/render (bt/create (m/init825)))

Which will produce a maze like:

Sidewinder is based upon Binary Tree, but when it navigates south, it chooses arandom cell from the current horizontal corridor and generates the link fromthere. The mazes will still flow vertically, but not to the right as with BinaryTree. All mazes will have a single horizontal corridor along the southern edge.

To generate a maze using the sidewinder algorithm:

(require '[meiro.sidewinder:as sw])(png/render (sw/create (m/init825)))

Which will produce a maze like:

Because Sidewinder creates a maze one row at a time, it is possible to createinfinite mazes. The mazes won't be perfect mazes unless completed, though.These mazes only link south or east, so you'll only be able to use certainrender functions, likeascii/render andpng/render, which are alreadyoptimized to only render the east and south walls per cell. Optional weights canbe passed to the function.

(definfini-maze (sw/create-lazy25 {:south2:east5}))(defmaze (conj (vec (take7 infini-maze)) (sw/last-row25)))(png/render maze)

Which will produce a maze like:

Aldous-Broder picks a random cell in the grid and the moves randomly. If itvisits a cell which has not been visited before, it links it to the previouscell. The algorithm ends when all cells have been visited.

Because movement is random, it can take a long time for this algorithm tofinish. Because movement is completely random, the generated maze has no bias.

To generate a random-walk maze using Aldous-Broder:

(require '[meiro.aldous-broder:as ab])(png/render (ab/create (m/init825)))

Which will produce a maze like:

Wilson's starts at a random cell and then does a random walk. When it introducesa loop by coming back to a visited cell, it erases the loop then continues therandom walk from that point. The algorithm starts slowly, but produces acompletely unbiased maze.

To generate a loop-erasing, random-walk maze:

(require '[meiro.wilson:as w])(png/render (w/create (m/init825)))

Which will produce a maze like:

Hunt-and-Kill performs a random walk, but avoids visiting cells which arealready linked. When it reaches a dead end but there are still cells to visit,it will look for an unvisited cell neighboring a visited cell and begin walkingagain from there.

Hunt-and-kill mazes tend to have long, twisty passages with fewer dead ends thanmost of the algorithms here. It can be slower because it can visit cells manytimes.

To generate a random-walk maze biased to the first visited cell usingHunt-and-Kill:

(require '[meiro.hunt-and-kill:as hk])(png/render (hk/create (m/init825)))

Which will produce a maze like:

Recursive Backtracker uses a random-walk algorithm. When it encounters a deadend, it backtracks to the last unvisited cell and resumes the random walk fromthat position. It completes when it backtracks to the starting cell. Resultingmazes have long, twisty passages and fewer dead ends. It should be faster thanhunt-and-kill, but has to maintain the stack of all visited cells.

To generate a random-walk maze biased to the last unvisited cell on the pathusing Recursive Backtracker:

(require '[meiro.backtracker:as b])(png/render (b/create (m/init825)))

Which will produce a maze like:

Kruskal's algorithm is focused on generating a minimum spanning tree. I decidedto use a more graph-centric approach, so thecreate function returns a"forest", a map which includes the nodes and edges. It usesx, y coordinates,so is "backward" from the other algorithms to this point.

The algorithm assigns every cell to a distinct forest, and then merges forestsone at a time until there is only one forest remaining.

Thepng/render-forest function will render a forest directly, or the resultscan be converted to the standard, grid-style maze usinggraph/forest-to-mazebefore passing to otherpng functions.

(require '[meiro.kruskal:as k])(require '[meiro.graph:as graph])(defforest (k/create258))(defmaze (graph/forest-to-maze forest))(png/render maze)

Which will produce a maze like:

Prim's algorithm generates a minimum spanning tree by starting with a positionand adding the "cheapest" edge available. Weights are assigned randomly toensure a less biased maze. Like Kruskal's, the approach is graph-centric andcreate returns a collection of edges. The implementation here is a "TruePrim's" approach, using weighted edges. (There are other versions possible, likeSimplified Prim's, which produce more biased mazes.)

(require '[meiro.prim:as prim])(require '[meiro.graph:as graph])(defforest (prim/create258))(defmaze (graph/forest-to-maze forest))(png/render maze)

Which will produce a maze like:

The Growing Tree algorithm is an abstraction over the approach in Prim'salgorithm.It needs to be passed aqueue which holds the active edges of the growing tree(forest), apoll-fn which removes an edge from thequeue, and ashift-fnwhich transfers the edges of a newly added node from the set of remaining,unexplored edges to thequeue.

The bias of this algorithm will depend on how edges are added to and removedfrom the queue

To implement Prim's algorithm using Growing Tree:

(require '[meiro.growing-tree:as grow])(require '[meiro.prim:as prim])(defforest (grow/create258                         (java.util.PriorityQueue.)                         prim/poll                         prim/to-active!))(defmaze (graph/forest-to-maze forest))(png/render maze)

Which will produce a maze like:

But, Growing Tree can also be used to implement Recursive Backtracker.Note: If you do not shuffle the new edges, the resulting "maze" will mostly be aseries of connected corridors.

(require '[meiro.growing-tree:as grow])(defnback-poll  [q]  [(first q) (rest q)])(defnback-shift  [new-edges queue remaining-edges]  (reduce    (fn [[q es] e]      (let [remaining (disj es e)]        (if (= es remaining)          [q es]          [(conj q e)           remaining])))    [queue remaining-edges]    (shuffle new-edges)))(defforest (grow/create258 '() back-poll back-shift))(defmaze (graph/forest-to-maze forest))(png/render maze)

Which will produce a maze like:

Eller's algorithm processes a row at a time, creating forests as it goes. Italso behaves like Sidewinder, in that it will connect to the next row from onerandom position in a horizontal corridor. When a forest is orphaned, because itdoes not have a link to the next row, then it is merged with an adjacent forest.When the last row is reached, all forests are merged. Note that when forests aremerged, they can be linked at any two adjacent nodes (i.e., not necessarily thesouthernmost cell).

To create a maze using Eller's:

(require '[meiro.eller:as eller])(defforest (eller/create258))(png/render (graph/forest-to-maze forest))

Which will produce a maze like:

The Recursive Division algorithm generates fractal mazes and is distinct amongall the algorithms here in that is adds walls instead of carving passages.

To create a maze using Recursive Division:

(require '[meiro.division:as division])(defmaze (division/create (m/init825)))(png/render maze)

Which will produce a maze like:

Recursive Division also enables the creation of rooms inside the maze. Do thisby passing a maximum room size and a creation rate (a percentage of the timewhen the subdivision will stop when height and width are below the size).

(defmaze (division/create (m/init825)40.4))(png/render maze)

Which will produce a maze like:

To calculate the distance from the north-east cell to each cell using Dijkstra'salgorithm:

(require '[meiro.dijkstra:as d])(defmaze (sw/create (m/init88)))(defdist (d/distances maze))(print (ascii/render maze (ascii/show-distance dist)))

Which will produce a maze like:

+---+---+---+---+---+---+---+---+| 0   1 | 4 | n | q   p | o   n |+   +---+   +   +---+   +---+   +| 1   2   3 | m   l | o   n | m |+   +---+---+---+   +---+   +   +| 2   3 | m   l | k   l | m | l |+---+   +---+   +   +---+   +   +| 5   4 | l   k   j   k | l | k |+   +---+---+---+   +---+   +   +| 6 | 9 | k   j   i | h | k   j |+   +   +---+---+   +   +---+   +| 7   8   9   a | h   g | j | i |+---+---+   +---+---+   +   +   +| g   f | a   b | g   f | i   h |+---+   +---+   +---+   +---+   +| f   e   d   c   d   e   f   g |+---+---+---+---+---+---+---+---+

To calculate and show a solution:

(defmaze (b/create (m/init825)))(defsol (d/solution maze [00] [024]))(print (ascii/render maze (ascii/show-solution sol)))

Which will produce a maze like:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+| *     |           | *   * | *   *                 | *   *   *   *   *   * |         *   * | *   * |+   +   +   +   +---+   +   +   +   +---+---+---+   +   +---+   +---+---+   +---+---+   +   +   +   +| * |       |   | *   * | *   * | *   * |           | * |   |   |       | * | *   * | * | *   * |   |+   +---+---+---+   +---+---+---+---+   +---+---+---+   +   +   +   +   +   +   +   +   +---+---+   +| *   * | *   * | * | *   * |       | * | *   *   *   * |   |   |   |   | *   * | *   * |   |       |+---+   +   +   +   +   +   +   +   +   +   +---+---+---+   +   +   +   +---+---+---+---+   +   +---+| *   * | * | * | *   * | *   * |   | * | * |               |       |   |               |   |       |+   +---+   +   +---+---+---+   +---+   +   +---+---+   +   +---+---+   +   +---+---+   +   +---+   +| *   *   * | *     | *   *   * | *   * | * | *   * |   |           |       |   |       |       |   |+---+---+---+   +   +   +---+---+   +   +   +   +   +---+---+   +   +---+---+   +   +---+---+   +   +| *   *   *   * |   | *   *     | * |   | * | * | *   *   * |   |               |           |       |+   +---+---+   +---+---+   +---+   +   +   +   +---+---+   +---+---+---+---+   +---+---+   +   +---+| *   *   * |   | *   * | * | *   * |   | *   * | *   * | *   *   *   *   *   *   * |   |   |   |   |+   +---+   +---+   +   +   +   +---+---+---+---+   +   +---+---+---+---+---+---+   +   +   +   +   +|       | *   *   * | *   * | *   *   *   *   *   * | *   *   *   *   *   *   *   * |       |       |+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

There are a few additional utilities besides deriving solutions.

Dijkstra's distances calculation can be used to find the position furthest froma given start point. If none is provided, it will assume the upper left-handcorner position.

(d/farthest-pos maze)[220]

By running this algorithm twice, the second time with the output of the firstrun, you can determine the longest path in a maze. This can be useful if you arelooking to determine start and end points. This function returns a path withall the positions.

(d/longest-path maze)([620] [619] [719] [720] [721] [621] [521] [520] [519] [518] [618] [718] [717] [617] [616] [716] [715] [615] [614] [714] [713] [613] [513] [514] [515] [415] [416] [316] [216] [116] [115] [215] [214] [213] [313] [314] [414] [413] [412] [411] [511] [512] [612] [712] [711] [611] [610] [710] [79] [69] [68] [78] [77] [76] [75] [74] [73] [72] [71] [70] [60] [50] [40] [30] [20] [21] [11] [10] [00] [01] [02] [12] [13] [14] [15] [16] [17] [07] [08] [18] [19] [29] [28] [27] [26] [36] [46] [45] [44] [54] [53] [43] [33] [32] [31] [41] [51] [61] [62] [63] [64] [65] [55] [56] [57] [47] [48] [49] [59] [510] [410] [310] [311] [312] [212] [112] [113] [013] [014] [015][016] [017] [018] [118] [218] [219] [319] [320] [420] [421] [321] [221] [121] [021] [020] [019] [119] [120] [220])

By default, the algorithms produce "perfect" mazes, i.e., every position in thegrid has one path to any other position in the grid. This inevitably producesdead ends. "Braiding" is the act of removing dead ends from a maze by linkingthem with neighbors.

To enumerate the dead ends in a maze:

(defmaze (b/create (m/init822)))(m/dead-ends maze)([010] [016] [11] [121] [25] [213] [30] [37] [42] [413] [415] [53] [510] [61] [615] [619] [711] [721])

You can remove all dead ends with thebraid function.

(m/braid maze)

If you don't want to remove all dead ends, you can pass in a rate which willdetermine what percentage of the dead ends should be removed (randomly).

(defbraided (m/braid maze0.4))(png/render braided)

Whereas braiding eliminates dead ends by connecting them to neighbors, it isalso possible tocull dead ends, creating a sparse maze. A maze can be culledmultiple times to remove more ends. Culled cells will be marked as masked, soyou will need to use a rendering function which handles this sensibly.Culled mazes will remain perfect mazes.

(require '[meiro.hunt-and-kill:as hk])(defmaze (hk/create (m/init822)))(png/render-inset (m/cull (m/cull maze0.6)0.6)3)

A weave maze can connect to non-adjacent cells provided certain conditions aremet.

• Passages cannot dead end while underneath another cell.
• Passages must be perpendicular, one north-south, one east-west.
• Passages cannot change direction while traveling under other passages.

A weave maze will need to be rendered using "inset", otherwise it won't bepossible to visually identify the under passages.

(require '[meiro.weave:as weave])(defmaze (b/create (m/init825) [00] weave/neighbors weave/link))(png/render-inset maze2)

Kruskal's is set up to allow weave to be injected into a maze. This is done bypre-seeding the algorithm with cells already combined, and then letting the mazebuild around it. In order to render a weave maze, it has to be converted to thestandard grid format.

(require '[meiro.kruskal:as k])(require '[meiro.graph:as graph])(defforests (graph/init-forests258))(defseeded (reduce k/weave forests  (for [x (range1252) y (range182)] [x y])))(defforest (k/create258 seeded))(defmaze (graph/forest-to-maze forest))(png/render-inset maze2)

Thegrid-3d namespace can be used to generate three-dimensional mazes.The example below takes advantage of the controls which can be passed to thecreate function to favor spreading out on a level before ascending ordescending.

(require '[meiro.grid-3d:as grid-3d])(defgrid (grid-3d/init345))(deflink-3d (m/link-with grid-3d/direction))(defnselect-fn"Favor selecting neighbors on the same level."  [neighbors]  (let [n (count neighbors)]    (if (and (<2 n) (<0.1 (rand)))      (rand-nth (take (- n2) (rest (sort neighbors))))      (rand-nth neighbors))))(defmaze (b/create grid                    (grid-3d/random-pos grid)                    grid-3d/neighbors link-3d select-fn))(png/render-3d maze)

Sometimes you may want to have maze wrap around, meaning if you step off theleft edge of the maze, it re-enters on the right edge. You could use this tocreate a maze on a cylinder. You could use this approach to create a Pac-Manstyle maze as well.

This will only wrap along the vertical walls:

(require '[meiro.wrap:as wrap])(defmaze (b/create (m/init825) [313]                    wrap/neighbors-horizontal                    wrap/link))(png/render-inset maze2)

To wrap off any direction:

(defmaze (b/create (m/init825) [313] wrap/neighbors wrap/link))(png/render-inset maze2)

I did a presentation on this code at Pivotal in January 2018. It is availableon YouTube here:Maze Generation Algorithms in Clojure – Michael Daines

Copyright © 2017–2020 Michael S. Daines

Distributed under the Eclipse Public License either version 1.0 or (atyour option) any later version.