Mazes For Programmers Python Sources

Introduction

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.

Implemented algorithms

AldousBroder
BinaryTree
HuntAndKill
RecursiveBacktracker
Sidewinder
Wilson

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

Implemented exporters

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)

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

Wolfenstein 3D Exporter

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):

Implemented pathfinding algorithms

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.

Setup

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

Execute

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

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

Testing

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

make test

Roadmap & TODOs

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, etc.
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)

hanok2/mazes-for-programmers-python-src