small medium large xlarge

01 Mar 2015, 19:46
Alex K (2 posts)

Hi Jamis,

I’m planning on buying your book once it comes out of beta. It looks really cool! I’ve been thinking of building a game based on mazes and your book might make it possible.

If this isn’t an appropriate place for this question, please let me know where I should best ask.

I was reading your Recursive Backtracing post and was confused by some of the code, specifically the constants you used.

# --------------------------------------------------------------------
# 2. Set up constants to aid with describing the passage directions
# --------------------------------------------------------------------

N, S, E, W = 1, 2, 4, 8
DX         = { E => 1, W => -1, N =>  0, S => 0 }
DY         = { E => 0, W =>  0, N => -1, S => 1 }
OPPOSITE   = { E => W, W =>  E, N =>  S, S => N }

Why are N, S, E, W, DX, DY set to those values?

Also, and this is probably because I don’t know ruby as well as I’d like: you generate a seed, how does the code lock that maze to that randomly generated number?

Lastly, do you have a license you’re using for the code on your website, gist, and in your book?

Thanks! Alex

02 Mar 2015, 15:24
Jamis Buck (30 posts)

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",
# published by The Pragmatic Bookshelf.
# 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 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
07 Mar 2015, 23:32
Alex K (2 posts)

Hi Jamis,

That is incredibly helpful, thank you.

Looking forward to the final book release.

Best, Alex

You must be logged in to comment