defndaines / meiro
- понедельник, 19 июня 2017 г. в 03:12:58
https://github.com/defndaines/meiro
Clojure
Maze generation code, inspired by Mazes for Programmers.
Meiro 迷路
Maze generation code, inspired by working through Mazes for Programmers. Because the book leans on Object Oriented design (coded in Ruby), much of this is a re-thinking of the approaches in a Clojure style.
Each maze generation algorithm is in its own namespace.
Usage Algorithms Solutions Utilities
Usage
Project is currently under development and does not have functions exposed for external use.
Displaying Mazes
There are several ways to display a maze. The data structure used to store a maze is a vector of vectors, where each cell indicates which directions you can navigate out of the cell to.
Here is a 5x5 maze:
[[[: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 ASCII version:
user=> (require '[meiro.ascii :as ascii])
nil
user=> (print (ascii/render maze))
+---+---+---+---+---+
| | |
+---+ +---+ + +
| | |
+ +---+ +---+---+
| | | |
+---+---+ +---+ +
| | | |
+ + + +---+ +
| | |
+---+---+---+---+---+
nilAnd if you want to print or share a maze, it can be output as a PNG:
(require '[meiro.png :as png])
(png/render (sw/create (m/init 15 20)) "sample-maze.png")Which creates a PNG file like:
To print a maze with masked cells:
(def grid (ascii/read-grid "template.txt"))
(png/render-masked (b/create grid))
To print a circular (polar) maze:
(png/render-polar
(b/create (polar/init 10) [0 0] polar/neighbors polar/direction))
To print a sigma (hex) maze:
(png/render-hex
(b/create (m/init 15 20) [7 9] hex/neighbors hex/direction))
To print a delta (triangle) maze:
(def grid (ascii/read-grid "test/meiro/triangle.txt"))
(png/render-delta
(b/create grid [0 12] triangle/neighbors m/direction))
Algorithms
There are a number of different algorithms for generating mazes.
Binary Tree
Binary Tree produces mazes with a bias toward paths which flow down and to the right. They will always have a single corridor along both the southern and eastern edges.
If you wish to generate and print a random binary-tree maze, you can start up a REPL and try to following:
(require '[meiro.core :as m])
(require '[meiro.ascii :as ascii])
(require '[meiro.binary-tree :as bt])
(print (ascii/render (bt/create (m/init 8 25))))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | | |
+ +---+---+ + +---+ +---+---+ + +---+ + +---+---+---+ +---+ + +---+---+---+ +
| | | | | | | | | | | | | | | | | |
+ +---+---+---+ +---+ + +---+ + + + +---+---+ + + + + + + + +---+ +
| | | | | | | | | | |
+---+---+ +---+---+---+ +---+---+ + +---+---+---+ +---+ +---+---+---+---+ + + + +
| | | | | | | | | | | | | |
+---+ + +---+---+---+ + + +---+---+ + + + + +---+---+ + +---+---+---+---+ +
| | | | | | | | | | | | | |
+ + +---+---+ + +---+ +---+---+ + + +---+---+---+ +---+ + +---+---+---+ + +
| | | | | | | | | | | | |
+ +---+ +---+---+---+ +---+---+---+---+ +---+ + +---+---+ + + + +---+ +---+ +
| | | | | | | | | | | | | |
+---+ +---+---+---+ + + +---+ + +---+ +---+---+---+---+ +---+ + + + +---+ +
| |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Sidewinder
Sidewinder is based upon Binary Tree, but when it navigates south, it chooses a random cell from the current horizontal corridor and generates the link from there. The mazes will still flow vertically, but not to the right as with Binary Tree. All mazes with have a single horizontal corridor along the southern edge.
To generate a maze using the sidewinder algorithm:
(require '[meiro.sidewinder :as sw])
(print (ascii/render (sw/create (m/init 8 25))))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | | |
+ +---+---+ +---+---+---+---+ +---+ + + +---+ + +---+ + +---+---+---+ + +---+
| | | | | | | | | | | | | | | | |
+---+ + + + +---+ + +---+ +---+ + +---+---+ +---+ +---+ +---+ + + + +
| | | | | | | | | | | | | |
+ + +---+---+---+ +---+---+---+ +---+ +---+ + + +---+ + +---+---+ +---+ + +
| | | | | | | | | | |
+---+ +---+---+---+ + +---+---+ +---+---+---+---+ +---+ + + + +---+ +---+---+---+
| | | | | | | | | | | | | | | |
+---+ + +---+---+ +---+ +---+ +---+ + + +---+ + + +---+ + +---+ + +---+
| | | | | | | | | | | | | | |
+ +---+---+---+---+ + + +---+ + +---+---+ +---+ +---+ + + +---+ + +---+ +
| | | | | | | | | | | | |
+---+---+---+ +---+ + +---+---+---+---+ + + +---+---+---+ +---+ + +---+ + + +
| |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Aldous-Broder
To generate a random-walk maze using Aldous-Broder:
(require '[meiro.aldous-broder :as ab])
(print (ascii/render (ab/create (m/init 8 25))))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+ + + +---+---+ + +---+---+ +---+---+ +---+---+---+ + + + +---+---+ + +
| | | | | | | | | | | | | |
+ +---+ + +---+ +---+ +---+ + +---+---+ +---+ +---+ + + + +---+ +---+ +
| | | | | | | | | | | | | | |
+ +---+---+---+---+---+ +---+---+ + + +---+---+---+ +---+---+ + +---+ + +---+ +
| | | | | | | | | | | |
+---+---+---+ + + + + + +---+ +---+ + + + +---+ +---+ + + +---+ +---+
| | | | | | | | | | | | | | | | | |
+ +---+ +---+ +---+ + +---+ + +---+---+---+ +---+ + + + +---+ +---+ +---+
| | | | | | | | | | | | | | | |
+ +---+ +---+ + + + + + +---+---+ + + +---+---+ + +---+ +---+ + +---+
| | | | | | | | | | | | | |
+---+ + + +---+---+ + +---+---+ + + + +---+---+---+ + +---+ + + +---+ +
| | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Wilson's
To generate a loop-erasing, random-walk maze using Wilson's:
(require '[meiro.wilson :as w])
(print (ascii/render (w/create (m/init 8 25))))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | |
+ + + +---+ +---+---+ +---+ + + +---+ + +---+---+ +---+ + +---+ +---+ +
| | | | | | | | | | | | | | | |
+---+---+---+---+ +---+ +---+ +---+ + +---+---+ +---+---+ +---+---+---+---+---+ + +
| | | | | | | | | | | | |
+---+ + +---+---+ + + +---+---+ +---+ +---+---+ +---+ +---+---+ + + + + +
| | | | | | | | | | | | | | | |
+---+ + +---+---+---+---+ +---+---+ +---+---+ + +---+ + + +---+---+ + +---+ +
| | | | | | | | | | |
+---+ +---+ +---+ +---+ +---+ +---+ +---+---+ +---+---+ + + +---+---+ + + +
| | | | | | | | | | | | |
+ + +---+---+ +---+ +---+ +---+---+---+ +---+ + + +---+---+ + +---+ +---+---+
| | | | | | | | | |
+---+ +---+---+ + +---+ + +---+---+ + +---+ + +---+---+---+---+ +---+ +---+ +
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Hunt and Kill
To generate a random-walk maze biased to first visited cell using Hunt and Kill:
(require '[meiro.hunt-and-kill :as hk])
(print (ascii/render (hk/create (m/init 8 25))))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | |
+ + + + + +---+---+ +---+---+ + +---+ +---+---+---+ +---+---+ + +---+---+ +
| | | | | | | | | | | | |
+ +---+---+---+ +---+---+---+ + +---+ + +---+ + + +---+---+ + +---+---+ + +
| | | | | | | | | | | | |
+ +---+ + +---+---+ + +---+---+---+---+---+---+---+ +---+ + +---+ +---+---+---+ +
| | | | | | | | | | |
+---+---+---+---+ + +---+---+---+---+ + + +---+---+---+ +---+---+ +---+ +---+---+---+
| | | | | | | | | | | | |
+ + + + +---+ + + +---+---+ + + +---+---+---+---+ +---+---+ +---+ + + +
| | | | | | | | | | | | | |
+ +---+---+---+---+---+ +---+---+---+---+ +---+---+ +---+ +---+ + + + +---+ + +
| | | | | | | | | | | |
+---+---+---+ + +---+---+ + +---+---+---+ + +---+---+---+---+---+---+---+ + + + +
| | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Recursive Backtracker
To generate a random-walk maze biased to last unvisited cell on the path using the Recursive Backtracker:
(require '[meiro.backtracker :as b])
(print (ascii/render (b/create (m/init 8 25))))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | |
+ +---+---+ + +---+---+---+ + + + +---+ + +---+ + +---+---+ +---+ + + +
| | | | | | | | | | | | | | | | | | | |
+ + + + +---+ +---+ + + + +---+ + + + + +---+ + + + + +---+ +
| | | | | | | | | | | | | | | |
+ +---+ +---+ + + +---+ + +---+ +---+---+---+ +---+---+---+---+---+---+ + +---+
| | | | | | | | | | | | |
+ + +---+ + + +---+ + +---+---+---+ +---+---+---+---+---+ + +---+ +---+ + +
| | | | | | | | | | | | |
+---+---+ + + +---+ + +---+---+---+ +---+---+ + +---+---+---+ + +---+---+---+---+
| | | | | | | | | | | | |
+ + +---+---+ + +---+ + +---+ +---+---+---+---+ +---+ +---+---+---+ + + + +
| | | | | | | | | | | |
+ +---+ +---+---+---+---+---+---+---+---+ +---+ + +---+ +---+ +---+ +---+---+ + +
| | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Solutions
To calculate the distance from the north-east cell to each cell using Dijkstra's algorithm:
(require '[meiro.dijkstra :as d])
(def maze (sw/create (m/init 8 8)))
(def dist (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:
(def maze (b/create (m/init 8 25)))
(def sol (d/solution maze [0 0] [0 24]))
(print (ascii/render maze (ascii/show-solution sol)))Which will produce a maze like:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| * | | * * | * * | * * * * * * | * * | * * |
+ + + + +---+ + + + +---+---+---+ + +---+ +---+---+ +---+---+ + + + +
| * | | | * * | * * | * * | | * | | | | * | * * | * | * * | |
+ +---+---+---+ +---+---+---+---+ +---+---+---+ + + + + + + + + +---+---+ +
| * * | * * | * | * * | | * | * * * * | | | | | * * | * * | | |
+---+ + + + + + + + + + +---+---+---+ + + + +---+---+---+---+ + +---+
| * * | * | * | * * | * * | | * | * | | | | | | |
+ +---+ + +---+---+---+ +---+ + +---+---+ + +---+---+ + +---+---+ + +---+ +
| * * * | * | * * * | * * | * | * * | | | | | | | |
+---+---+---+ + + +---+---+ + + + + +---+---+ + +---+---+ + +---+---+ + +
| * * * * | | * * | * | | * | * | * * * | | | | |
+ +---+---+ +---+---+ +---+ + + + +---+---+ +---+---+---+---+ +---+---+ + +---+
| * * * | | * * | * | * * | | * * | * * | * * * * * * * | | | | |
+ +---+ +---+ + + + +---+---+---+---+ + +---+---+---+---+---+---+ + + + + +
| | * * * | * * | * * * * * * | * * * * * * * * | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Utilities
There are a few additional utilities besides deriving solutions.
Longest Path
TBD
Braid
By default, the algorithms produce "perfect" mazes, i.e., every position in the grid has one path to any other position in the grid. This inevitably produces dead ends. "Braiding" is the act of removing dead ends from a maze by linking them with neighbors.
To enumerate the dead ends in a maze:
(def maze (b/create (m/init 8 22)))
(m/dead-ends maze)
([0 10] [0 16] [1 1] [1 21] [2 5] [2 13] [3 0] [3 7] [4 2] [4 13] [4 15] [5 3]
[5 10] [6 1] [6 15] [6 19] [7 11] [7 21])You can remove all dead ends with the braid function.
(m/braid maze)If you don't want to remove all dead ends, you can pass in a rate which will determine what percentage of the dead ends should be removed (randomly).
(def braided (m/braid maze 0.4))
(ascii/render braided)
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | |
+ +---+---+---+---+ +---+ + +---+---+ + + + + +---+---+---+---+ + +
| | | | | | | | | | | |
+ +---+ +---+ +---+ + +---+---+ + +---+---+ +---+ + +---+---+---+---+
| | | | | | | | | | | | |
+---+ + + + + + +---+ + +---+ + +---+---+ + +---+---+---+---+ +
| | | | | | | | | | | | |
+ + + + +---+ + +---+---+---+ +---+ + + +---+---+---+---+ + + +
| | | | | | | | | | | | |
+ + +---+ + + +---+---+---+---+---+ +---+---+ +---+---+ +---+---+ + +
| | | | | | | | | | | |
+ +---+ +---+ +---+---+---+ + +---+---+---+ + +---+ + + +---+ + +
| | | | | | | | | | | | |
+ +---+---+ +---+ + +---+---+---+ +---+ + +---+---+ + +---+---+ + +
| | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+License
Copyright © 2017 Michael S. Daines
Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.