You are previewing Mathematics and Physics for Programmers, Second Edition.

Mathematics and Physics for Programmers, Second Edition

Cover of Mathematics and Physics for Programmers, Second Edition by John Patrick Flynt... Published by Course Technology PTR
  1. Copyright
    1. Dedication
  2. Acknowledgments
    1. The First Edition
    2. The Second Edition
  3. About the Authors
  4. Introduction
    1. Who Is This Book For?
    2. What Is This Book About?
    3. How Should I Use This Book?
    4. About the Pseudocode
    5. How to Locate the Code Samples
    6. Errors, Omissions, and Comments
    7. Companion Website Downloads
  5. I. Essential Topics in Mathematics
    1. 1. Numbers
      1. In This Chapter
      2. Overview
      3. Numbers as Written
      4. How Computers Represent Numbers
      5. Exercises
      6. Summary
      7. You Should Now Know
    2. 2. Arithmetic
      1. In This Chapter
      2. Overview
      3. Fractions
      4. Proportions, Ratios, and Percentages
      5. Exponentials
      6. Logarithms
      7. Exercises
      8. Summary
      9. You Should Now Know
    3. 3. Algebra
      1. In This Chapter
      2. Overview
      3. Basic Algebra
      4. Working with Equations
      5. Factoring and Solving Quadratic Equations
      6. Functions and Graphs
      7. Exercises
      8. Summary
      9. You Should Now Know
    4. 4. Geometry and Trigonometry
      1. In This Chapter
      2. Overview
      3. Angles
      4. Triangles
      5. Calculations with Triangles
      6. Rotations and Reflections
      7. Exercises
      8. Summary
      9. You Should Now Know
    5. 5. Vectors
      1. In This Chapter
      2. Overview
      3. Getting from Here to There
      4. Vector Motion
      5. Vector Calculations
      6. Matrices
      7. Exercises
      8. Summary
      9. You Should Now Know
    6. 6. Calculus
      1. In This Chapter
      2. Overview
      3. Differentiation and Integration
      4. Differential Equations
      5. Approximation Methods
      6. Exercises
      7. Summary
      8. You Should Now Know
  6. II. Essential Topics in Physics
    1. 7. Acceleration, Mass, and Energy
      1. In This Chapter
      2. Overview
      3. Ballistics
      4. Mass and Momentum
      5. Energy
      6. Exercises
      7. Summary
      8. You Should Now Know
    2. 8. Detecting Collisions Between Simple Shapes
      1. In This Chapter
      2. Overview
      3. Ground Rules
      4. When Circles Collide
      5. When Squares Collide
      6. When Ellipses Collide
      7. When Things Collide
      8. Exercises
      9. Summary
      10. You Should Now Know
    3. 9. Collision Resolution
      1. In This Chapter
      2. Overview
      3. Resolving a Single Collision
      4. Multiple Collisions
      5. Exercises
      6. Summary
      7. You Should Now Know
    4. 10. Detecting Collisions Between Complex Shapes
      1. In This Chapter
      2. Overview
      3. Problems with Complex Shapes
      4. Some Reasonable Problems
      5. Built-In Solutions
      6. Exercises
      7. Summary
      8. You Should Now Know
    5. 11. A Simple Pool Game
      1. In This Chapter
      2. Overview
      3. Primary Elements of a Simulation
      4. Taking a Shot
      5. Exercises
      6. Summary
      7. You Should Now Know
  7. III. Complex Motion
    1. 12. Force and Newton’s Laws
      1. In This Chapter
      2. Overview
      3. Force
      4. Gravity
      5. Rockets and Satellites
      6. Exercise
      7. Summary
      8. You Should Now Know
    2. 13. Angular Motion
      1. In This Chapter
      2. Overview
      3. The Physics of a Lever
      4. Spin
      5. Spinning Collisions
      6. Spin Applied to the Pool Game
      7. Exercises
      8. Summary
      9. You Should Now Know
    3. 14. Friction
      1. In This Chapter
      2. Overview
      3. How Friction Works
      4. Friction and Angular Motion
      5. Exercise
      6. Summary
      7. You Should Now Know
    4. 15. Strings, Pulleys, and Conveyor Belts
      1. In This Chapter
      2. Overview
      3. Pulling Things Around
      4. Continuous Momentum
      5. Exercise
      6. Summary
      7. You Should Now Know
    5. 16. Oscillations
      1. In This Chapter
      2. Overview
      3. Springs
      4. Simple Harmonic Motion
      5. Damped Harmonic Motion
      6. Complications of Springs
      7. Calculating Spring Motion
      8. Waves
      9. Exercise
      10. Summary
      11. You Should Now Know
  8. IV. 3-D Mathematics
    1. 17. 3-D Geometry
      1. In This Chapter
      2. Overview
      3. 3-D Vectors
      4. Rendering
      5. Casting a Ray
      6. Exercise
      7. Summary
      8. You Should Now Know
    2. 18. Transforms
      1. In This Chapter
      2. Overview
      3. Describing Locations in Space
      4. Applying Transforms
      5. Exercise
      6. Summary
      7. You Should Now Know
    3. 19. 3-D Collision Detection
      1. In This Chapter
      2. Overview
      3. Colliding Worlds
      4. Colliding Footballs
      5. Colliding Boxes
      6. Colliding Cans
      7. Varieties of Collisions
      8. Resolving Collisions in Three Dimensions
      9. Exercise
      10. Summary
      11. You Should Now Know
    4. 20. Lighting and Textures
      1. In This Chapter
      2. Overview
      3. Light
      4. Materials
      5. Shading
      6. Exercise
      7. Summary
      8. You Should Now Know
    5. 21. Modeling Techniques
      1. In This Chapter
      2. Overview
      3. Mathematical 3-D Modeling
      4. Animated Surfaces
      5. Bone Animations
      6. Exercises
      7. Summary
      8. You Should Now Know
  9. V. Game Algorithms
    1. 22. Speeding Things Up
      1. In This Chapter
      2. Overview
      3. Cheap and Expensive Calculations
      4. Pseudo-Physics
      5. Culling
      6. Exercises
      7. Summary
      8. You Should Now Know
    2. 23. Tile-Based Games
      1. In This Chapter
      2. Overview
      3. Generating a Game from Bits
      4. Advanced Tiling
      5. Exercise
      6. Summary
      7. You Should Now Know
    3. 24. Mazes
      1. In This Chapter
      2. Overview
      3. Classifying Mazes
      4. Creating Mazes
      5. Navigating Within Mazes
      6. Exercise
      7. Summary
      8. You Should Now Know
    4. 25. Game Theory and Artificial Intelligence
      1. In This Chapter
      2. Overview
      3. Introduction to Game Theory
      4. Tactical AI
      5. Top-Down AI
      6. Bottom-Up AI
      7. Exercises
      8. Summary
      9. You Should Now Know
    5. 26. Search Techniques
      1. In This Chapter
      2. Overview
      3. Problem Solving
      4. Case Study
      5. Genetic Algorithms
      6. Exercise
      7. Summary
      8. You Should Now Know
  10. A. Glossary of Mathematical Terms
  11. B. Code References
    1. Data Types
    2. Variables
    3. Operators
  12. C. The Greek Alphabet
  13. D. Learning Resources
    1. General Mathematics
    2. Specialized Resources
      1. Collision Detection
      2. 3-D Engines and Geometry
      3. Game Physics
      4. Mazes, Searches, and AI
  14. E. Answers to Exercises
O'Reilly logo

Chapter 24. Mazes

Overview

A particularly common type of game world can be loosely described as a maze. The variety of games that fit into this category in one way or another is large. Consider such games as the classical Pac-Man, which conspicuously uses a maze, to sophisticated driving games that unfold within a vast city grid. Even tile-based games and exploratory 3-D platform games make use of mazes. In this chapter, you’ll look at how to create, work with, and navigate through mazes. You will also explore how to create simple artificial intelligence (AI) routines that search through the maze for a quarry.

Classifying Mazes

Before you look at how to work with mazes, ...

The best content for your career. Discover unlimited learning on demand for around $1/day.