Mazes for Programmers: Dijkstra's algorithm

Related post: mazes for programmers: binary tree and sidewinder

In mazes for programmers: binary tree and sidewinder we explored several techniques for generating mazes by interconnecting the cells of a grid and then treating those interconnections as paths between the cells.

Round 2 of Mazes for Programmers has us implementing Dijkstra’s algorithm to solve a maze by finding the shortest path between two points using the notion of cost.¹

As a side-effect, one also gets pretty good at typing “Dijkstra”.

The algorithm in a nutshell:

1. Determine the starting point of the grid (commonly the northwestern-most cell).
2. Record the cost of reaching that cell: 0.
3. Find that cell’s navigable neighbors.
4. For each neighbor, record the cost of reaching the neighbor: 1.
5. For each neighbor, repeat steps 3-5, taking care not to revisit already-visited cells.

When complete, we’ll have a record of the cost of reaching each cell iteratively from the starting point. This data tells us how far each cell is from the root, and you can imagine this being perfectly useful in its own right.

If we now traverse that body of data with cost information in reverse, starting from the desired endpoint and stepping through cells that bear a cost less than the cost of the current cell, we’ll eventually reach the root cell via the shortest path possible.

Because our maze generator currently outputs only perfect mazes, with exactly one path between any two points, the shortest path from start to end is also the only path from start to end, but you can imagine more complicated mazes with multiple ways to reach the goal cell.

You can also imagine a more realistic terrain where costs differ depending on the realities of any given point; perhaps climbing a mountain pass or traversing a forest is time-consuming, or takes the traveller too far away from water sources. Finding the shortest (or least-expensive, or safest, or etc.) path between any two cells is easily obtained via the same algorithm by having additional information for each cell informing that cell’s cost; the steps above describe a cost of 1 for simplicity’s sake alone.

Ruby Dijkstra

The Ruby implementation was a short-lived stop on my way to Clojure side of things; after studying the book’s implementation for a bit, I folded it in, preserving my own local variances for seeding and debugging and quickly moved on.

Clojure Dijkstra

The Clojure implementation is where things get interesting. Thus far we’ve established some patterns around maze generation and display, and we’ll be able to use those again here (and having used this boilerplate three times with minimal tweaks, it’s due to be factored out into a shared implementation).

However, actually solving a maze means new kinds of work need to be accomplished:

1. We’ll need to actually walk the maze in order to solve it, which means…
2. Cells will need two-way links so that we can walk paths in reverse.
3. We’ll have to find the shortest path, which means….
4. We’ll have to determine cell costs.

In previous maze generation work, I concentrated on keeping the grid structure as minimal as possible, using one-way links to determine paths, but in finding the shortest path back from the goal cell, we’ll now have to walk the cells backwards, and this is more easily done if links are reciprocal.

For generation I had also avoided making much use of embedding coordinates in the cells themselves, relying mostly on the nested list-of-lists shape to drive display, but given the data structure I chose to use for solving, relying on those coordinates more made downstream processing simpler.

Spoiler alert: looking back, it’s clear that my instinctive choice to use a single data structure by overloading it with information for completing all these tasks was less than ideal; the code would have been much simpler by using several smaller, task-focused data structures to attack the various sub-problems piecemeal.

Warning signs include: having to do too much work to re-shape the data structure for ephemeral tasks, a mix of helper functions that work with coordinates and ones that work with shape, and too much damn code.

I’d like to take another pass and tighten it up, but for now…

It does the thing. Which is nice.

There are other ways to make this more interesting – path priority using the A* algorithm to avoid exploring non-goal paths, using non-perfect mazes with multiple ways to reach the goal, but the thing I’d really like to do here is lift this into some kind of UI with a stepper control so the maze can be solved (and un-solved) incrementally.

Until next time!