// the find
mikepound/mazesolving
A variety of algorithms to solve mazes from an input image
Companion code to a Computerphile YouTube video, implementing BFS, DFS, Dijkstra, A*, and wall-following algorithms to solve bitmap mazes loaded from PNG images. It's primarily educational — the kind of thing you read alongside the video, not something you'd drop into production. The author is explicit that active development stopped.
Each algorithm is in its own file with no cross-contamination, making it genuinely easy to read one in isolation. The image-to-graph conversion in mazes.py is the most interesting piece — it converts pixel paths to a sparse graph of junctions rather than treating every pixel as a node, which meaningfully reduces memory on large mazes. A custom Fibonacci heap implementation is included for Dijkstra, which is a nice touch for an educational repo. Large example mazes (up to 15k×15k) are bundled so you can actually stress-test the algorithms without hunting for inputs.
Abandoned since 2022 with no packaging, no requirements.txt, and no entry point beyond running solve.py directly — you're on your own figuring out dependencies. The README warns that large mazes need 16 GB of RAM, which is partly an algorithm problem: the junction-graph approach helps but the BFS and DFS implementations still keep too much in memory. No maze generation code — only solving, so you're dependent on the bundled examples or third-party tools to make your own inputs. The wall-follower (leftturn.py) only works on simply connected mazes and there's no check or warning for when it silently fails on braided ones.