small medium large xlarge

### Posts by Jamis Buck

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!

Joe, I’m not sure why the print book isn’t listed at the main book page. I’ll ask and post here again when I know more about that.

In the meantime, you can order both the print edition and the ebook by going here:

My bad, apparently the omission is on purpose, due to headaches caused by preordering print versions during the beta process. I’ve been told though, that anyone who orders the beta version will get a special coupon to order the print edition when the print edition becomes available, so you’ll still be eligible for the discounted pricing.

Thanks, and sorry for the confusion!

Jamis

Hello Xavier! Thank you for your comment. You’re absolutely right that the second way (using Array#compact) is better Ruby code. I originally had it implemented that way, but I worried that the Array#compact idiom would require more explanation for non-Rubyists. The first version is more verbose, but I think it explains the intention better, and is more easily portable to other languages.

Ultimately, this means that there will be more idiomatic ways to implement many of these methods in Ruby, but it’s a trade-off.

I’ll consider this some more, but ultimately I don’t want non-Rubyists to be discouraged from reading this book—the algorithms are really at the core of it.

Thanks again! I really appreciate your feedback on this issue. It’s been a tricky one for me to find a balance here.

It should work either way, north or south, as long as you are consistently choosing from the same set of directions. If you always choose between north and east at each cell, you’ll get a north-easterly textured maze with solid corridors on the north and east sides. Choosing between south and east would give you a south-easterly textured maze, with corridors on the south and east instead.

I’m curious what you mean when you say that choosing north causes the maze to “look bad”. I wonder if it might suggest that the code which is configuring the adjacent cells (Grid#configure_cells in the Ruby implementation) is misconfiguring the northern neighbor somehow? If you don’t mind sharing your Grid implementation, I could take a look. It might also help to see what one of the resulting mazes looks like.

Thanks for the feedback, Wari! That’s very helpful to hear that you prefer the first version. Also, I’m excited to hear that you’re porting the Ruby implementation from the Book, to Go! I look forward to seeing how it comes together for you.

Wonderful! I’m glad you figured it out. I’ve spent more time than I care to admit troubleshooting issues like this in my own maze code. :)

I’m excited to see how this progresses! Swift has been on my bucket list for a while.

Hello, Alex!

The constants there represent bits to set within a bitfield—e.g. N is the first bit (2^0==1), S is the second, E is the third, and W is the fourth. (2^3 == 8). DX indicates the direction in X that a given compass direction takes you–DX[E] == 1, DX[W] == -1, and N and S don’t go any distance in X. DY is the same, but for Y. (I hope that makes sense!)

The code in the book is much more intuitive and object-oriented. Instead of using bitfields to represent cells, I’m using actual classes and objects with named accessors. It’s not as memory-efficient as the bitfields, but it’s a lot easier to understand and work with!

Locking a maze to a random seed happens as a side-effect of how pseudo-random number generators (PRNG) work. It’ll work this way in any language, and not just Ruby. If you give a PRNG the same starting seed, it will always produce the same sequence of “random” numbers. Because the maze algorithm itself simply consumes these random numbers, you’ll always get the same maze if you give it the same sequence of random values. This means that (as long as you don’t change the algorithm at all) you can represent an entire maze with just the dimensions of the grid, and the random seed used to generate it.

Pretty cool! It’s really, REALLY handy for debugging these programs. Just print the seed you’re using, and when you see a maze that isn’t being generated or displayed correctly, you lock the seed to the one that was used, and then track down the bug.

And for licensing: the code I used on those blog posts is all in the public domain—you can use it for whatever you want, however you want, without attribution (though attribution would be appreciated).

The code from the book, though, is a bit more restrictive. Each file includes the following header:

``````#---
# Excerpted from "Mazes for Programmers",
# Copyrights apply to this code. It may not be used to create training material,
# courses, books, articles, and the like. Contact us if you are in doubt.
# We make no guarantees that this code is fit for any purpose.
# Visit http://www.pragmaticprogrammer.com/titles/jbmaze for more book information.
#---
``````

Aside from the restrictions mentioned there, though, you may use the code however you like, as long as it retains that copyright notice.

• Jamis

Mark, thanks for picking up the book! I absolutely agree that this topic could be hugely successful in teaching kids the different concepts of programming. In fact, my 13yo son has been my primary “alpha reader” through this process, and has really enjoyed following the code examples. I’d love to talk more about how to use mazes to introduce programming (though it’ll probably have to wait until May, as I need to finish this book in the next few weeks, and then prep for a presentation I’m giving at RailsConf in April).

• Jamis

I love it! What a great exploration, very inspirational. Thanks for sharing!

Very cool! I love the little “mice” that come out at the end – very mesmerizing.

Thanks for the suggestion, Herbert. I can’t make any promises, but we’re looking into it!

It sounds like the ChunkyPNG library isn’t installed. Were you able to `gem install chunky_png`, as indicated near the bottom of page 29 (print/PDF version)? If you type `gem list` at a command line, does `chunky_png` show up there?

Oh, are you using the code downloaded from here? Rather than keying in the examples yourself? You’re right, that the grid.rb in the source code is the complete grid.rb, with all the bells and whistles, and it assumes you’ve already hit those bits about rendering an image. I’m sorry about that!

I’ll put on my thinking cap and see what I can do for that. You really ought to be able to run those early examples without stumbling over `chunky_png`.

Excellent suggestion. Thank you!

The book does contain a section at the beginning (in the introduction) listing some additional online resources, but I’ll be honest: it’s a bit sparse. There really are no other books that I’m aware of which discuss maze generation algorithms (but if anyone knows of any, please do share).

For websites, Walter Pullen’s excellent Think Labyrinth site is a must read, with information about the algorithms and the psychology of mazes. (He’s a bit light on implementation details, though, so while you can learn the algorithms from his pages, it requires a bit of trial and error).

Mike Bostock has done some beautiful work on algorithm visualization with his D3 library, here. Sprinkled among the visualizations are a few related to mazes. Again, they’re light on implementation details, although you can read the (Javascript) code for pointers.

Also, I wrote a series of articles about each of the maze algorithms several years ago, summarized here. These include walk-throughs of the algorithms and sample implementations, but I’ll be honest: I’ve learned a lot since writing those posts, and the book presents them much better. :)

If anyone else has any maze-related resources to share, please do!

Hello Rob,

I’m sorry this is proving so tricky! If you don’t mind posting your code somewhere, I could take a look and see if I can spot what’s going on there. Otherwise, I think the two key points in the book are the illustration at the top of page 140 (showing the locations of x1-x4 and y1-y4), and then the code snippet on the bottom of page 150 and the top of page 151.

Essentially, OverCells are always drawn just as before, but UnderCells draw only the small walls on the corresponding insets (north/south for vertical passages, east/west for horizontal).

I don’t know how much help that is. Please let me know how it goes!

• Jamis

Thank you for sharing this! I’ve been curious about how these algorithms would come together in Swift.

• Jamis

I’m glad you figured it out! if there was anything I could have made clearer in the book, which might have saved you some headache, please let me know. Maybe a future edition could help other readers!

• Jamis

Hello Brandon! I’m sorry for the confusion, there. That `each_cell` call that you’re seeing is actually a custom iterator, implemented as a method on the `Grid` class. In that method, you’ll see a call to `yield` – what this does is invoke the block of code that was attached when the `each_cell` method was called.

(If you look at `each_cell`, you’ll see that it actually calls another custom iterator: `each_row`, which in turn calls the standard `each` method on the underlying grid array itself.)

I hope that clarifies things a bit. It’s a pretty standard Ruby idiom, but if you’re not used to Ruby’s way of doing things, these iterators can certainly be a bit confusing!

Very odd! I’ll take a look at what you’ve got and see if I can spot anything.

(edit: I originally asked to see the code – but missed that you’d liked to it already)

That is really cool! Thank you for sharing; I love seeing what people come up with, like this. :)

I cloned your repo and tried running the `dijkstra.rb` script, and I got an error (but not the one you indicated). I had to change this line:

https://github.com/brian-davis/mazes/blob/master/distances.rb#L5

So that it was

``````@cells[@root] = 0 # instead of @cell[@root]...
``````

After that, the `dijkstra.rb` script worked fine. Was it a different script you were trying to run? If you’re still having the error, let me know and I’ll take another look.

30 posts