Mazes for Programmers: Binary tree and Sidewinder

Related post: mazes for programmers intro

Mazes for Programmers starts off with an intro to maze generation, discussing the Binary Tree and Sidewinder algorithms, their implementations and idiosyncracies.¹

Chapter 2 is where we dive into actually implementing the algorithms. Grid and Cell class implementations are provided by the book, and the exercises cleanly differentiate themselves by applying their particular algorithm to those classes.

Ruby Binary Tree

Algorithm:

For each cell, toss a coin to choose whether to carve a passage north or east. Rinse and repeat until every cell has been visited.

For Binary Tree, I stayed faithful to the book’s Ruby implementation to get the feel of things, departing only to add a debug facility in order to print intermediate states of the grid during generation, and a seeding facility that allows a deterministic sequence of “randomized” choices to drive generation, producing identical mazes across multiple runs.

Ruby Sidewinder

Algorithm:

As with Binary Tree, toss a coin to determine whether we carve a passage north or east, considering the eastward-connected series of cells connecting to the current cell a ‘run’. If the toss dictates north, then randomly choose one cell from among the run and carve a passageway north from that cell. Repeat until every cell has been visited.

I implemented Sidewinder without first studying the book’s version, and despite not having used Ruby in earnest for some time I ended up with something fairly clean. Having the underlying Cell class do the state bookkeeping for links between cells definitely made this easier, though since these are actual object references with bi-directional links between them, printing out this data structure for inspection was a startling experience. I’m used to everything being just data!

Chapter 2 concludes with wiring up the chunky_png library to write generated mazes to a PNG file, so you get one of these at the end like a little treat…

Clojure code librarianship

For the Clojure side of this jam, I wanted to leave my options open as far as visualizing output; for sure, I want a fast feedback loop when developing maze generation code, which in Clojure land typically means developing at a REPL – which is, by default, what you’d do, and certainly where I spend the vast majority of my Clojure development time.

But I also thought it’d be neat to wire this work up to a web app later on so I could pursue fancy visualizations like this one, which implies ClojureScript. With a bit more effort, I can achieve that at the same time via cljc, which makes a single codebase usable from both Clojure and ClojureScript compilation paths.

So my Clojure/Script code will be housed in files bearing a .cljc file extension, and will use reader conditionals to differentiate CLJ and CLJS codepaths for those bits that differ between JVM and JS hosts, like so…

That’s it – that’s all you have to do to make a Clojure/Script codebase portable between Clojure and ClojureScript hosts.

To top it off, cljc is also usable directly from NodeJS engines like Lumo, so this choice also accommodates good old-fashioned fast² command-line access to these programs, which is the mode I got into while developing the Ruby implementations.

Clojure Binary Tree

My binary-tree implementation used a two-dimensional array of maps as cells, each with a one-way link to either the north or east.

This didn’t surface any surprises in terms of translating between OO-style and FP-style, with the exception that the debug pattern I established in the Ruby code of printing intermediate grid states while generating the maze demanded a much different shape to the code than I was happy with. In order to facilitate access to those intermediate states, the pattern of generating the maze with no external state via nested for calls to build a 2D array would probably need to flatten out into a single looping construct, such that the inner body has access to the entire data structure in-flight so it can be printed out.

In particular I’d like to avoid the minor but infectious consequence that cells track their own coordinates so that downstream code knows which row they occupy – in the current shape, we avoid having to deal with that by simply iterating over the discrete cell arrays. I’d like to figure out a more elegant way of facilitating debug printing while keeping things clean; I may drive out an alternate implementation. ³

Clojure Sidewinder

sidewinder was more entertaining: Sidewinder’s mechanism for carving out a north passageway in a random selection from among the east-linked cells of the current run was a fun constraint in keeping things as stateless as possible. Again, our cells are generated in a doubly-nested loop, each containing a set of zero or more one-way links to northern and/or eastern neighbors. Using state here would have been “easier” – tracking cell coordinates and linkages in each cell would have been an obvious choice in OO land, but that would defeat the purpose here, wouldn’t it?

For the Clojure implementations, I skipped outputting to an image; I’ve got more ambitious things in mind for visualization.

I’d like to see other functional implementions of Sidewinder, and was surprised to not find much in this space. I found two, both code work-throughs of the Mazes for Programmers book:

• A Clojure implementation. This is a very complete exploration, and I have to keep myself from peeking at his approaches to algorithms I haven’t yet implemented.
• An F# implementation in a GitHub gist that will bear some study. This was linked in a blogpost much like this one discussing a C# implementation.

Looking over that Clojure version, it has a more elegant means of handling the interesting bit of Sidewinder – mine strove (perhaps a bit too much) to avoid dealing with positional indexes when inserting north links into runs.

Next

Next up: solving mazes with Dijkstra’s Algorithm and others I explore on the side. This should be fun – not least because once we have maze solving, we can have sweet CLJS visualizations of same.