You are previewing Mazes for Programmers.
O'Reilly logo
Mazes for Programmers

Book Description

Unlock the secrets to creating random mazes! Whether you're a game developer, an algorithm connoisseur, or simply in search of a new puzzle, you're about to level up. Learn algorithms to randomly generate mazes in a variety of shapes, sizes, and dimensions. Bend them into Moebius strips, fold them into cubes, and wrap them around spheres. Stretch them into other dimensions, squeeze them into arbitrary outlines, and tile them in a dizzying variety of ways. From twelve little algorithms, you'll discover a vast reservoir of ideas and inspiration.

Table of Contents

  1. Mazes for Programmers
    1. For the Best Reading Experience...
    2. Table of Contents
    3. Early praise for Mazes for Programmers
    4. Acknowledgments
    5. Introduction
      1. About This Book
      2. Online Resources
    6. Part 1: The Basics
      1. Chapter 1: Your First Random Mazes
        1. Preparing the Grid
        2. The Binary Tree Algorithm
        3. The Sidewinder Algorithm
        4. Your Turn
      2. Chapter 2: Automating and Displaying Your Mazes
        1. Introducing Our Basic Grid
        2. Implementing the Binary Tree Algorithm
        3. Displaying a Maze on a Terminal
        4. Implementing the Sidewinder Algorithm
        5. Rendering a Maze as an Image
        6. Your Turn
      3. Chapter 3: Finding Solutions
        1. Dijkstra’s Algorithm
        2. Implementing Dijkstra’s
        3. Finding the Shortest Path
        4. Making Challenging Mazes
        5. Coloring Your Mazes
        6. Your Turn
      4. Chapter 4: Avoiding Bias with Random Walks
        1. Understanding Biases
        2. The Aldous-Broder Algorithm
        3. Implementing Aldous-Broder
        4. Wilson’s Algorithm
        5. Implementing Wilson’s Algorithm
        6. Your Turn
      5. Chapter 5: Adding Constraints to Random Walks
        1. The Hunt-and-Kill Algorithm
        2. Implementing Hunt-and-Kill
        3. Counting Dead Ends
        4. The Recursive Backtracker Algorithm
        5. Implementing the Recursive Backtracker
        6. Your Turn
    7. Part 2: Next Steps
      1. Chapter 6: Fitting Mazes to Shapes
        1. Introducing Masking
        2. Implementing a Mask
        3. ASCII Masks
        4. Image Masks
        5. Your Turn
      2. Chapter 7: Going in Circles
        1. Understanding Polar Grids
        2. Drawing Polar Grids
        3. Adaptively Subdividing the Grid
        4. Implementing a Polar Grid
        5. Your Turn
      3. Chapter 8: Exploring Other Grids
        1. Implementing a Hex Grid
        2. Displaying a Hex Grid
        3. Making Hexagon (Sigma) Mazes
        4. Implementing a Triangle Grid
        5. Displaying a Triangle Grid
        6. Making Triangle (Delta) Mazes
        7. Your Turn
      4. Chapter 9: Braiding and Weaving Your Mazes
        1. Braiding Mazes
        2. Cost versus Distance
        3. Implementing a Cost-Aware Dikstra’s Algorithm
        4. Introducing Weaves and Insets
        5. Generating Weave Mazes
        6. Your Turn
    8. Part 3: More Algorithms
      1. Chapter 10: Improving Your Weaving
        1. Kruskal’s Algorithm
        2. Implementing Randomized Kruskal’s Algorithm
        3. Better Weaving with Kruskal
        4. Implementing Better Weaving
        5. Your Turn
      2. Chapter 11: Growing With Prim’s
        1. Introducing Prim’s Algorithm
        2. Simplified Prim’s Algorithm
        3. True Prim’s Algorithm
        4. The Growing Tree Algorithm
        5. Your Turn
      3. Chapter 12: Combining, Dividing
        1. Eller’s Algorithm
        2. Implementing Eller’s Algorithm
        3. Recursive Division
        4. Implementing Recursive Division
        5. Your Turn
    9. Part 4: Shapes and Surfaces
      1. Chapter 13: Extending Mazes into Higher Dimensions
        1. Understanding Dimensions
        2. Introducing 3D Mazes
        3. Adding a Third Dimension
        4. Displaying a 3D Maze
        5. Representing Four Dimensions
        6. Your Turn
      2. Chapter 14: Bending and Folding Your Mazes
        1. Cylinder Mazes
        2. Möbius Mazes
        3. Cube Mazes
        4. Sphere Mazes
        5. Your Turn
    10. Appendix 1: Summary of Maze Algorithms
      1. Aldous-Broder
      2. Binary Tree
      3. Eller’s
      4. Growing Tree
      5. Hunt-and-Kill
      6. Kruskal’s (Randomized)
      7. Prim’s (Simplified)
      8. Prim’s (True)
      9. Recursive Backtracker
      10. Recursive Division
      11. Sidewinder
      12. Wilson’s
    11. Appendix 2: Comparison of Maze Algorithms
      1. Dead Ends
      2. Longest Path
      3. Twistiness
      4. Directness
      5. Intersections
      6. Your Turn
      7. You May Be Interested In…