small medium large xlarge

05 Feb 2015, 12:04
Leen Torenvliet (1 post)

Is it perhaps possible to give more teasing excerpts from the book. I’m amazed (pun not intended) that you could write a whole book on this subject. After all, what more is a maze than a (possibly directed, possibly cycle free, possibly planar) graph, for which wikipedia has plenty algorithms? The contents does not make it more attractive. If Prim and Kruskal (min cost spanning tree) and Dijkstra (shortest paths) is as deep as it goes, then algorithmically it isn’t very challenging. There could be very deep and interesting visualization problems in the book, that make it worth spending $25 on it (rather a steep prize by comparison for an ebook), but I’d like to be convinced a bit more before drawing the credit card.

05 Feb 2015, 13:07
Jamis Buck (30 posts)

I’m glad you asked! It’s apparent from your post that you’re well-versed in graph theory—the ideas and vocabulary that underpin mazes are no news to you. That’s fantastic!

You mentioned Prim’s and Kruskal’s, and yes, the book goes into those. (The corresponding chapters aren’t yet in the beta, but will be in the next update or two.) I actually discuss Prim’s as two separate (but closely related) algorithms: “simplified” (as it is usually presented online in relation to maze generation) and “true” (which uses random weights to give a much more interesting texture).

There are quite a few more than just those two, though. The book includes descriptions, demonstrations, and implementations for all of these:

  • Binary Tree
  • Sidewinder
  • Aldous-Broder
  • Wilson’s
  • Hunt-and-Kill
  • Recursive Backtracker (aka depth-first search)
  • Kruskal’s
  • Prim’s (simplified and true)
  • Growing Tree
  • Recursive Division
  • Eller’s

Even then, you’d be right that if the book only talked about those algorithms, it wouldn’t be nearly as compelling. Information about all of those can be found online (though some of them you might have to dig harder than for others). What this book does is bring them all togther in one place, using a common framework to discuss and compare them, pointing out their pros and cons and biases—and then it takes you through applications of those algorithms.

These include using Dijkstra’s algorithm to not only find a shortest path, but to find a longest path, or to color mazes to find hidden textures in them. The book covers “masking” (where you constrain the maze to certain areas of the grid), different grid tesselations and systems (polar, hex, and triangle), weaving (making “pseudo-3D” mazes by making passages weave over and under one-another), braiding (adding loops, or cycles, to mazes), higher dimensional mazes (3D and 4D, etc.), and mazes on non-planar surfaces (like spheres and Moebius strips). And every chapter ends with a section called “Your Turn”, with a handful (or more, sometimes) of ideas to try related to the chapter’s topic.

Now, maybe you’re still shrugging your shoulders, and that’s okay. If you’ve already done all these things, or if they don’t sound interesting to you, then the book may simply not be for you. But from my own experience blogging about mazes and maze algorithms, it is apparent to me that there are plenty of people who are interested in these things, and who haven’t had very much prior experience with mazes and grids and graph theory.

Which I hope gets back to your original question: “why this book?” Why? Because I think it can make people better programmers. I’ve found mazes to be hugely inspirational, and I believe others will, too. It’s a topic that hearks back to the feeling of discovery I used to have, back when I was first learning to write software.

Also, it’s a lot of fun. :)

I hope that helps, and no hard feelings if you still aren’t convinced. :) I tried!

You must be logged in to comment