https://media.pragprog.com/covers/jbmaze.jpg

Description

From video games to movies, mazes are ubiquitous. Explore a dozen algorithms for generating these puzzles randomly, from Binary Tree to Eller’s, each copiously illustrated and accompanied by working implementations in Ruby. You’ll learn their pros and cons, and how to choose the right one for the job.

You’ll start by learning six maze algorithms and transition from making mazes on paper to writing programs that generate and draw them. You’ll be introduced to Dijkstra’s algorithm and see how it can help solve, analyze, and visualize mazes. Part 2 shows you how to constrain your mazes to different shapes and outlines, such as text, circles, hex and triangle grids, and more. You’ll learn techniques for culling dead-ends, and for making your passages weave over and under each other. Part 3 looks at six more algorithms, taking it all to the next level. You’ll learn how to build your mazes in multiple dimensions, and even on curved surfaces.

Through it all, you’ll discover yourself brimming with ideas, the best medicine for programmer’s block, burn-out, and the grayest of days. By the time you’re done, you’ll be energized and full of maze-related possibilities!

Q&A with Jamis Buck, author of Mazes for Programmers

It has to be asked: Why mazes?

You know, I came to programming because it fascinated me. There was something magical and wonderful about it—this idea that I could write a few commands in some cryptic syntax and make something happen. It was powerful! I don’t think I’m unique that way. I think a lot of us come to programming like that.

But somewhere along the line we generally lose that sense of the magical. Maybe it gets drowned in the mundane tasks we typically use these amazing tools for, I don’t know. But when the magic goes away, so does the wonder. So does the fun.

For me, mazes take me back to those days when programming was fun, when I’d sit down and start coding simply to see what might happen! Every random maze is unique, and the algorithms lend themselves well to variation and experimentation. It becomes this iterative game of “what if,” for me. What if I make this condition more or less likely? What if I disallow this set of cells in the grid? What if I use color to visualize this or that aspect of the maze?

So, why mazes? Because they bring the wonder and the fun back into programming.

How did you come to write this book?

Would you believe there aren’t any other books solely about maze algorithms? I couldn’t. There are lots of great resources online about them, but if you want to learn how to generate a maze in more than just one or two ways, you wind up having to do a fair bit of research. You glean a bit of information here, a bit more there, you tinker and experiment until you get something working, and then you do it all over again for the next algorithm.

Some years ago I wrote a series of blog articles summarizing my own explorations in just this vein, and they were pretty well-received. Some readers suggested I write a book…and I’m embarrassed to admit that it took me a few years to take them seriously. But I did, and here I am!

Why are there so many algorithms for generating mazes?

You can’t write software for very long before realizing that there are lots of different ways to solve problems in code. There are at least a dozen different ways to sort information, for instance, and each one has different strengths and weaknesses. Just so with maze algorithms, too. Depending on your need for memory efficiency, speed, and esthetics, the variety of maze algorithms let you choose one that will best fit your needs.

Besides, life would be a bit less wonderful if there were only one way to generate mazes. I like to celebrate the fact that there are that many more things to explore!

What’s your favorite maze algorithm?

I don’t know that I could pick just one… I love the novelty of the Recursive Division algorithm, and how it works so well to add “rooms” to the mazes. One of my favorite projects recently was implementing a variation on Recursive Division that split each space into “blobs,” instead of rectangular spaces, and that gave some really nice results.

I’ve always loved the Recursive Backtracker algorithm, though. The esthetics of the long, winding passages that it produces really appeals to me, and the algorithm itself can be used to solve as well as create mazes!

What do you hope readers take away from the book?

More than anything, I want them to come away with a new sense of wonder for computer programming. I hope they find themselves remembering their own first steps into the world of software development, and rediscovering that joy of learning and exploring.

My favorite thing about writing this book has been the times that readers have contacted me to show me something wonderful that they’ve created as a result of what they’ve learned. One man used the masking chapter to write a program that generated mazes in the shape of his child’s name, which apparently earned him “dad-of-the-year” in their house! I love that stuff so much.

What’s your favorite part of the book?

Since I suppose you won’t be happy if I simply answer “all of it,” I’ll say that I really enjoyed writing the last chapter, the one about mazes on non-planar surfaces. I got very side-tracked on that one and as part of my “research” wrote an OpenGL program that built a maze on a sphere, and then allowed the player to navigate through it!

That kind of thing happened throughout the process of writing the book, though. Every algorithm suggested curious little projects to me, and I had to stop for a bit and explore sometimes. I hope the readers find themselves similarly distracted!

Contents and Extracts

• The Basics
  • Your First Random Mazes excerpt
    • Preparing the Grid
    • The Binary Tree Algorithm
    • The Sidewinder Algorithm
    • Your Turn
  • Automating and Displaying Your Mazes
    • Introducing Our Basic Grid
    • Implementing the Binary Tree Algorithm
    • Displaying a Maze on a Terminal
    • Implementing the Sidewinder Algorithm
    • Rendering a Maze as an Image
    • Your Turn
  • Finding Solutions
    • Dijkstra’s Algorithm
    • Implementing Dijkstra’s
    • Finding the Shortest Path
    • Making Challenging Mazes
    • Coloring Your Mazes
    • Your Turn
  • Avoiding Bias with Random Walks excerpt
    • Understanding Biases
    • The Aldous-Broder Algorithm
    • Implementing Aldous-Broder
    • Wilson’s Algorithm
    • Implementing Wilson’s Algorithm
    • Your Turn
  • Adding Constraints to Random Walks
    • The Hunt-and-Kill Algorithm
    • Implementing Hunt-and-Kill
    • Counting Dead-Ends
    • The Recursive Backtracker Algorithm
    • Implementing the Recursive Backtracker
    • Your Turn
• Next Steps
  • Fitting Mazes to Shapes
    • Introducing Masking
    • Implementing a Mask
    • ASCII Masks
    • Image Masks
    • Your Turn
  • Going in Circles
    • Understanding Polar Grids
    • Drawing Polar Grids
    • Adaptively Subdividing the Grid
    • Implementing a Polar Grid
    • Your Turn
  • Exploring Other Grids excerpt
    • Implementing a Hex Grid
    • Displaying a Hex Grid
    • Making Hexagon (Sigma) Mazes
    • Implementing a Triangle Grid
    • Displaying a Triangle Grid
    • Making Triangle (Delta) Mazes
    • Your Turn
  • Braiding and Weaving Your Mazes
    • Braiding Mazes
    • Cost versus Distance
    • Implementing a Cost-Aware Dikstra’s Algorithm
    • Introducing Weaves and Insets
    • Generating Weave Mazes
    • Your Turn
• More Algorithms
  • Improving Your Weaving
    • Kruskal’s Algorithm
    • Implementing Randomized Kruskal’s Algorithm
    • Better Weaving With Kruskal
    • Implementing Better Weaving
    • Your Turn
  • Growing With Prim’s
    • Introducing Prim’s Algorithm
    • Simplified Prim’s Algorithm
    • True Prim’s Algorithm
    • The Growing Tree Algorithm
    • Your Turn
  • Combining, Dividing
    • Eller’s Algorithm
    • Implementing Eller’s Algorithm
    • Recursive Division
    • Implementing Recursive Division
    • Your Turn
• Shapes and Surfaces
  • Extending Mazes into Higher Dimensions
    • Understanding Dimensions
    • Introducing 3D Mazes
    • Adding a Third Dimension
    • Displaying a 3D Maze
    • Representing Four Dimensions
    • Your Turn
  • Bending and Folding Your Mazes
    • Cylinder Mazes
    • Möbius Mazes
    • Cube Mazes
    • Sphere Mazes
    • Your Turn