CircleCI

I'm reading the Mazes for Programmers book, but source code comes in Ruby and I like Python, so I decided to rewrite them as I read. And along the way add tests, both to make sure the conversion is ok and to see a more continuous way than having to write all basic stuff and an "ASCII renderer" before being able to see anything.

A small remark: Code is not a 1:1 copy of the book's. For example I built exporters instead of adding to_s and to_png methods, pathfinding is also a module that works over traversable grids (those with distances calculated), and a few other changes and extras.

• AldousBroder
• BinaryTree
• HuntAndKill
• RecursiveBacktracker
• Sidewinder
• Wilson

Note: This list will grow as I progress with the book.

• ASCIIExporter: outputs to console

+---+---+---+---+---+---+
| |
+ + + +---+---+ +
| | | | |
+---+ +---+---+ + +
| | | |
+---+---+---+---+ + +
| | |
+ +---+ + +---+ +
| | | | |
+ + + + +---+ +
| | | | | |
+---+---+---+---+---+---+

• PNGExporter: outputs to a PNG file on the project root folder (filename will be current datetime)

Depending on the pathfinding and coloring flags combination can draw the colored solution path or a "distance-colored map" from the center.

• UnicodeExporter: outputs to console (prettier than raw ASCII)

┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃ ┃
┃ ┏━━━━━━━ ┃
┃ ┃ ┃ ┃ ┃
┣━━━┛ ┣━━━┻━━━ ┃
┃ ┃ ┃ ┃
┣━━━━━━━┻━━━━━━━ ┃ ┃
┃ ┃ ┃
┃ ┏━━━ ┏━━━┛ ┃
┃ ┃ ┃ ┃ ┃
┃ ┃ ┃ ┣━━━ ┃
┃ ┃ ┃ ┃ ┃ ┃
┗━━━┻━━━┻━━━┻━━━┻━━━━━━━┛

Special section for my small hack that I'm fond of, a "different" exporter:

• Wolf3DExporter: outputs to a LEV file, to be used from NMAP tool to import as a Wolfenstein 3D map. Level exit is at the pathfinding end (most distant cell from starting position), and on each dead-end there is an enemy soldier (when you attack one all will start to move around the map). Also outputs a PNG file with the maze solution. To be used with game_map_demo.py demo runner.

Sample small map playthrough (start at blue, end at red, enemy on deadend at white zone):

hint map Wolfenstein3D playthrough

• Dijkstra: Uses cell distances to calculate maze solution. The actual "core" logic lives at Distances base class.
• LongestPath: Calculates "a longest path" of the maze. There can be many as it selects a cell as starting point and could be other longer ones.

You just need to have installed make, docker and docker-compose.

Easiest way is to run the corresponding demo-xxxx make command, e.g.:

make demo-terminal rows=<value> cols=<value> algorithm=<value>
# example
make demo-terminal rows=10 cols=10 algorithm=AldousBroder
# examples of how to send optional params through make
make demo-terminal rows=15 cols=15 algorithm=AldousBroder pathfinding=-p=true
make demo-image rows=25 cols=25 algorithm=AldousBroder pathfinding=-p=true coloring=-c=true

Run without arguments to see all available options

Available make commands that run algorithms:

• demo-terminal
• demo-image
• demo-game-map
• run-stats

An alternative is to open a shell into the container and then run from the inside any demo:

# start and enter into container
make shell
# then run desired demo
python3 demos/<filename>

Available demo runners:

• terminal_demo.py
• game_map_demo.py
• image_demo.py
• stats_demo.py

And read the instructions of required and optional parameters (run without arguments and it will explain usage).

Usually you have to choose a desired grid size (in number of rows and columns) and the algorithm to use. Optionally you can select a few other parameters.

Stats demo runs all available algorithms a certain number of times and gathers statistics and metrics, careful with launching it with big mazes as might take a while. Sample output:

PYTHONPATH=. python3 demos/stats_demo.py 25 25 --pathfinding
Rows: 25
columns: 25
Total cells: 625
Runs per algorithm: 100
Pathfinding: True
> running AldousBroder
> running BinaryTree
> running HuntAndKill
> running RecursiveBacktracker
> running Sidewinder
> running Wilson
Average dead-ends (deadends/total-cells, sorted by % desc):
 AldousBroder: 182/625 (29.12%)
 Wilson: 181/625 (28.93%)
 Sidewinder: 171/625 (27.29%)
 BinaryTree: 156/625 (24.97%)
 RecursiveBacktracker: 065/625 (10.47%)
 HuntAndKill: 061/625 (9.73%)
Generation speed benchmark (seconds, sorted by average desc):
 Wilson: avg: 0.641611 min: 0.235594 max: 2.173624
 HuntAndKill: avg: 0.078919 min: 0.059095 max: 0.101278
 AldousBroder: avg: 0.038898 min: 0.015946 max: 0.180922
 RecursiveBacktracker: avg: 0.005492 min: 0.005383 max: 0.006105
 BinaryTree: avg: 0.002130 min: 0.002074 max: 0.002359
 Sidewinder: avg: 0.002105 min: 0.002039 max: 0.002320
Pathfinding speed benchmark (seconds, sorted by average desc):
 AldousBroder: avg: 0.014295 min: 0.011494 max: 0.035487
 RecursiveBacktracker: avg: 0.012775 min: 0.012238 max: 0.014378
 HuntAndKill: avg: 0.012100 min: 0.011589 max: 0.013740
 Wilson: avg: 0.011712 min: 0.011262 max: 0.013362
 Sidewinder: avg: 0.011641 min: 0.011314 max: 0.013308
 BinaryTree: avg: 0.011561 min: 0.011267 max: 0.013016

Note: Runs also linter tests, to conform with both mypy and flake8.

make test

• Of course finish the book and implement all main code and algorithms
• Check in depth mypy doc to see why all the issues with Union, probably I'm doing something wrong and doesn't detects properly hierarchies and the like.
• Check to improve Wolf3DExporter drawing of tiles so I can have bigger maps (each cell now uses 2x2 map tiles)
• Implement more pathfinders? e.g. recursive backtracking as a maze solving algorithm

• Visual A* Pathfinding and Maze Generation in Python: Great visualization system, advanced maze generation algorithms (15 different ones!), and great details and metrics in the A* implementation used for the path finding.