You are previewing Mathematics and Physics for Programmers, Second Edition.
O'Reilly logo
Mathematics and Physics for Programmers, Second Edition

Book Description

The casual game market continues to expand, and with the use of Flash growing and the increased popularity of the iPhone and other mobile gaming devices, developers have an exciting new route to market. But many of these budding game programmers find that they're missing the core math and physics skills they need to develop even simple games. MATHEMATICS AND PHYSICS FOR PROGRAMMERS, SECOND EDITION teaches beginning game programmers they skills they need to develop causal games. Beginning with the basic aspects of mathematics and physics that are relevant to games, and moving on to more complex topics, the book combines theory and practice and the reader develops a number of games throughout the course of the book. With the concepts and techniques presented in the book, readers should be able to program a number of standard casual game types, including Mario-style platformers, driving simulations, puzzle games, and a simple first-person shooter. They will also gain a basic understanding of 2D and 3D geometry.

Table of Contents

  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
        1. Integers, Rationals, and Irrationals
        2. Irrational and Real Numbers
        3. The Number as a String of Digits
        4. Decimal, Binary, and Hexadecimal
      4. How Computers Represent Numbers
        1. Representing Integers
        2. Representing Rational and Irrational Numbers
        3. Standards and Computed Numbers
          1. The value 10.5
          2. The value –1 e35
          3. Considerations
        4. Common Functions
          1. Absolute Values
          2. Floats to Integers
        5. Rounding Errors and Performance
        6. Big Integers
      5. Exercises
        1. Exercise 1.1
        2. Exercise 1.2
      6. Summary
      7. You Should Now Know
    2. 2. Arithmetic
      1. In This Chapter
      2. Overview
      3. Fractions
        1. Calculating Fractions
          1. Multiply Two Fractions
          2. Divide Fractions
          3. Addition and Subtraction of Fractions
        2. Factors and Factorization
          1. Generating Prime Numbers
          2. GCD and Euclid’s Algorithm
          3. Lowest Common Multiple
        3. Modulo Arithmetic
        4. Cycling Through Data
      4. Proportions, Ratios, and Percentages
        1. Mapping Between Ranges of Values
          1. Paper
          2. The Golden Ratio
          3. Fibonacci Sequence
        2. Making a Slider
        3. Calculating Percentages
          1. Compound Interest
          2. Debts and Interest
      5. Exponentials
        1. Calculating with Powers
        2. The Number e and the exp( ) Function
        3. Exponential Functions in Real Life and Physics
      6. Logarithms
        1. Calculating with Logarithms
        2. Using Logarithms to Simplify Calculations
        3. Using Logarithms to Deal with Large Numbers
      7. Exercises
        1. Exercise 2.1
        2. Exercise 2.2
        3. Exercise 2.3
      8. Summary
      9. You Should Now Know
    3. 3. Algebra
      1. In This Chapter
      2. Overview
      3. Basic Algebra
        1. Variables, Parameters, and Constants
        2. Expressions and Terms
        3. Functions
        4. Representations
        5. One-to-One, Inverse, and Multivalued
        6. Polynomials
        7. Equations, Formulas, and Inequalities
      4. Working with Equations
        1. Balancing Equations
        2. Simplification
        3. Negatives and Substitution
        4. Solving the Original Problem
      5. Factoring and Solving Quadratic Equations
        1. Examples of Factoring
        2. Factors and Quadratics
        3. The Quadratic Formula and the Difference of Two Squares
        4. Solving Cubic Equations
        5. Solving Simultaneous Equations
          1. Simultaneous Solutions by Substitution
          2. Simultaneous Solutions by Elimination
          3. A Function for Solving Systems of Equations
      6. Functions and Graphs
        1. What Is a Graph?
        2. Plotting and Examining Functions on a Graph
        3. What Graphs Tell You
          1. About Horizontal Functions
          2. About Diagonal Functions
          3. About Parabolic Functions
          4. About Asymptotic Functions
        4. Parametric Curves and Functions
      7. Exercises
        1. Exercise 3.1
        2. Exercise 3.2
        3. Exercise 3.3
      8. Summary
      9. You Should Now Know
    4. 4. Geometry and Trigonometry
      1. In This Chapter
      2. Overview
      3. Angles
        1. Angles and Degrees
        2. Area and the Number π
        3. Radians
      4. Triangles
        1. The Types of Triangle
          1. General Types of Triangles
          2. Right Triangles
        2. The Pythagorean Theorem
          1. Triples
          2. Extending the Pythagorean Theorem
        3. The Trigonometric Functions
        4. Trigonometric Identities
        5. The Inverse Trigonometric Functions
      5. Calculations with Triangles
        1. The Sine and Cosine Rules
        2. Similar Triangles
        3. The Area of a Triangle
      6. Rotations and Reflections
        1. Transformations
        2. Rotating an Object by an Angle
        3. Around a Center
        4. Quick Rotations by Special Angles
        5. Reflections
        6. sin(), cos() and Circular Motion
      7. Exercises
        1. Exercise 4.1
        2. Exercise 4.2
      8. Summary
      9. You Should Now Know
    5. 5. Vectors
      1. In This Chapter
      2. Overview
      3. Getting from Here to There
        1. The Vector as an Instruction
        2. Vector Arithmetic
          1. Scalar Multiplication and Addition
          2. Differences
          3. Vector Programs
        3. The Normal Vector
        4. Vectors and Scalars in Real Life
      4. Vector Motion
        1. Describing Shapes with Vectors
          1. Parallel Lines
          2. A Square
          3. An Equilateral Triangle
          4. Other Shapes and a Function
        2. Moving from P to Q
        3. More Complicated Vector Paths
          1. A Function for a Path
          2. Wacky Paths
      5. Vector Calculations
        1. Separating Vectors into Components
        2. The Scalar (Dot) Product
        3. Vector Equations
          1. Explore Vectors with Code
          2. Returning the Value of t
          3. Intersecting Lines
          4. Final Notes
      6. Matrices
        1. Matrix Fundamentals
        2. The Determinant
        3. Matrix Arithmetic
        4. The Matrix as a Transformation
      7. Exercises
        1. Exercise 5.1
        2. Exercise 5.2
      8. Summary
      9. You Should Now Know
    6. 6. Calculus
      1. In This Chapter
      2. Overview
      3. Differentiation and Integration
        1. The Gradient of a Function
        2. Differentiating
          1. A Few Applications
          2. Things Derivatives Can Tell You
        3. Differentiating Logarithms and Exponentials
        4. Differentiating Trigonometric Functions
        5. Parametric Equations and Partial Derivatives
        6. Integration
      4. Differential Equations
        1. Characteristics of Ordinary Differential Equations
        2. Solving Linear ODEs
      5. Approximation Methods
        1. Bracketing Methods
        2. Gradient Methods
      6. Exercises
        1. Exercise 6.1
        2. Exercise 6.2
      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
        1. Acceleration and Deceleration
        2. The Equations of Motion Under Constant Acceleration
        3. Acceleration Due to Gravity
        4. The Motion of a Cannonball
      4. Mass and Momentum
        1. Mass and Inertia
        2. Calculating Momentum
      5. Energy
        1. Kinds of Energy
        2. Conservation of Energy
        3. Using Conservation of Energy to Solve Ballistics Problems
      6. Exercises
        1. Exercise 7.1
        2. Exercise 7.2
        3. Exercise 7.3
      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
        1. Circles
        2. A Moving Circle and a Wall
        3. A Stationary Circle and a Moving Point
        4. Two Moving Circles on a Straight Line
        5. Two Circles Moving at an Angle
        6. One Circle Inside Another
        7. The Point of Contact
      5. When Squares Collide
        1. Rectangles and Squares
        2. A Stationary Rectangle and a Moving Point
        3. Two Rectangles at the Same Angle
        4. Two Rectangles at Different Angles
        5. The Point of Contact
      6. When Ellipses Collide
        1. Ellipses
        2. Describing an Ellipse Using Coordinates
        3. Translation
        4. A Stationary Ellipse and a Moving Point
        5. Two Ellipses
        6. The Point of Contact
      7. When Things Collide
        1. Collisions Between Circles and Rectangles
        2. The Point of Contact
      8. Exercises
        1. Exercise 8.1
        2. Exercise 8.2
      9. Summary
      10. You Should Now Know
    3. 9. Collision Resolution
      1. In This Chapter
      2. Overview
      3. Resolving a Single Collision
        1. A Ball Hitting a Wall
        2. A Ball Hitting a Movable Ball
        3. Two Moving Balls Colliding
        4. Inelastic Collisions
      4. Multiple Collisions
        1. Collision Is a Recursive Function
        2. Simultaneous Collisions
      5. Exercises
        1. Exercise 9.1
        2. Exercise 9.2
      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
        1. Bitmaps and Vector Shapes
        2. Defining a Complex Shape
          1. A Collision Map Function
          2. Parametric Functions
        3. Bezier Curves and Splines
          1. Catmull-Rom Curves
          2. Movable Splines
        4. Convex and Concave
        5. Determining If a Point Is Inside a Shape
      4. Some Reasonable Problems
        1. Finding the Leading Edge of a Complex Shape
        2. Using a Collision Map
        3. Finding Bounding Shapes
      5. Built-In Solutions
      6. Exercises
        1. Exercise 10.1
        2. Exercise 10.2
      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
        1. Defining the Table
        2. Defining the Balls
        3. Defining the Physical Parameters
      4. Taking a Shot
        1. Creating the Cue
        2. The Main Game Loop
        3. Basic Culling
        4. Game Logic
      5. Exercises
        1. Exercise 11.1
        2. Exercise 11.2
      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
        1. The First Law
        2. The Second Law
        3. The Third Law
        4. Impulse
      4. Gravity
        1. The Law of Gravitation
        2. The Motion of a Planet Under Gravity
        3. Stable Orbits
        4. Centrifugal and Centripetal Force
      5. Rockets and Satellites
        1. Geo-Stationary Orbit
        2. A Really Fast Cannonball
      6. Exercise
        1. Exercise 12.1
      7. Summary
      8. You Should Now Know
    2. 13. Angular Motion
      1. In This Chapter
      2. Overview
      3. The Physics of a Lever
        1. Torque
        2. Moments of Inertia
        3. Inertial and Laminar Objects
      4. Spin
        1. Ballet Dancers and Spinning Tops
        2. Rotational Kinetic Energy
      5. Spinning Collisions
        1. Detecting Collisions Between a Rotating Line and a Circle
        2. A Circle and a Moving Line
        3. Detecting Collisions Between Lines
        4. Two Rotating Lines
        5. Resolving Angular Collisions
      6. Spin Applied to the Pool Game
      7. Exercises
        1. Exercise 13.1
        2. Exercise 13.2
      8. Summary
      9. You Should Now Know
    3. 14. Friction
      1. In This Chapter
      2. Overview
      3. How Friction Works
        1. The Coefficient of Friction
        2. Friction and Energy
        3. Air Resistance and Terminal Velocity
      4. Friction and Angular Motion
        1. Wheels and Grip
        2. Friction and Slipping
      5. Exercise
        1. Exercise 14.1
      6. Summary
      7. You Should Now Know
    4. 15. Strings, Pulleys, and Conveyor Belts
      1. In This Chapter
      2. Overview
      3. Pulling Things Around
        1. The Inextensible String
        2. Strings on Tables
        3. Strings and Circular Motion
        4. Pulleys
      4. Continuous Momentum
        1. Conveyor Belts
        2. Rocket Fuel
      5. Exercise
        1. Exercise 15.1
      6. Summary
      7. You Should Now Know
    5. 16. Oscillations
      1. In This Chapter
      2. Overview
      3. Springs
        1. The Force in a Stretched Spring
        2. Using Springs to Measure Weight
      4. Simple Harmonic Motion
        1. The Equation of SHM
        2. Other Examples of SHM
        3. Calculating the Parameters
      5. Damped Harmonic Motion
        1. The Equation of DHM
        2. Damping in Practice
      6. Complications of Springs
        1. Resonance: Pushing the Swing
        2. Coupling: Linked Motion
      7. Calculating Spring Motion
        1. Force Due to a Spring
        2. Undamped and Uncoupled Springs
        3. Pure DHM Oscilllation
      8. Waves
        1. Wave Motion
        2. Types of Wave
        3. Wave Addition and Subtraction
        4. Wave Behavior
      9. Exercise
        1. Exercise 16.1
      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
        1. Adding the Third Dimension
        2. The Vector (Cross) Product
        3. Using the Cross Product
        4. Homogeneous Coordinates
      4. Rendering
        1. The Projection Plane
        2. Perspective
        3. Orthographic Projections
      5. Casting a Ray
        1. Using a 3-D Engine to Find Objects Along a Path
        2. Picking, Dragging, and Dropping
      6. Exercise
        1. Exercise 17.1
      7. Summary
      8. You Should Now Know
    2. 18. Transforms
      1. In This Chapter
      2. Overview
      3. Describing Locations in Space
        1. Position, Rotation, and Scale
        2. The Transformation Matrix
      4. Applying Transforms
        1. Creating Motion with Transforms
        2. Interpolation
        3. Quaternions
        4. Parents and Children
      5. Exercise
        1. Exercise 18.1
      6. Summary
      7. You Should Now Know
    3. 19. 3-D Collision Detection
      1. In This Chapter
      2. Overview
      3. Colliding Worlds
        1. Spheres
        2. A Moving Sphere and a Wall
        3. A Sphere and a Moving Point or Two Spheres
        4. The Point of Contact
      4. Colliding Footballs
        1. Ellipsoids
        2. An Ellipsoid and a Moving Point or Plane
        3. Two Ellipsoids
      5. Colliding Boxes
        1. Boxes
        2. A Box and a Moving Point
        3. Two Boxes
        4. A Box and a Sphere
      6. Colliding Cans
        1. Cylinders
        2. A Cylinder and a Point or Sphere
        3. A Cone and a Sphere or Particle
        4. Two Cylinders
      7. Varieties of Collisions
        1. Bounding Spheres,Ellipsoids,and Boxes
        2. Collisions with an Arbitrary Mesh
      8. Resolving Collisions in Three Dimensions
      9. Exercise
        1. Exercise 19.1
      10. Summary
      11. You Should Now Know
    4. 20. Lighting and Textures
      1. In This Chapter
      2. Overview
      3. Light
        1. Real Lights
        2. Fake Lights
      4. Materials
        1. The Color Elements of a Surface
        2. Image Maps and Textures
        3. Fitting a Map to a Shape
        4. Mip-Maps
      5. Shading
        1. Gouraud and Phong Shading
        2. The Normal at a Vertex
      6. Exercise
        1. Exercise 20.1
      7. Summary
      8. You Should Now Know
    5. 21. Modeling Techniques
      1. In This Chapter
      2. Overview
      3. Mathematical 3-D Modeling
        1. Surfaces of Rotation
        2. Splines in 3-D
          1. NURBS
        3. Surfaces Generated with Sine and Cosine Functions
        4. Tessellation
      4. Animated Surfaces
        1. Cloth and Hair
        2. Water
      5. Bone Animations
        1. Working with Bones
        2. Inverse Kinematics
      6. Exercises
        1. Exercise 21.1
        2. Exercise 21.2
      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
        1. Computational Complexity
        2. Using Look-Up Tables
        3. Integer Calculations
      4. Pseudo-Physics
        1. Simplifying Collisions
        2. Simplifying Motion
      5. Culling
        1. Segregating Space
        2. Quadtrees and Octrees
        3. Binary-Space Partitioning
        4. Bounding Volume Hierarchies
      6. Exercises
        1. Exercise 22.1
        2. Exercise 22.2
      7. Summary
      8. You Should Now Know
    2. 23. Tile-Based Games
      1. In This Chapter
      2. Overview
      3. Generating a Game from Bits
        1. Creating a Tile-Based World
        2. Basic Movement and Camera Control
        3. Basic Collisions
        4. Complex Tiles
      4. Advanced Tiling
        1. The Isometric View
        2. Platform Games in 3-D
        3. Spline-Based Tiles
      5. Exercise
        1. Exercise 23.1
      6. Summary
      7. You Should Now Know
    3. 24. Mazes
      1. In This Chapter
      2. Overview
      3. Classifying Mazes
        1. Graphs and Connectivity
        2. Twists and Turns
      4. Creating Mazes
        1. Handling Maze Data
        2. Automatically Generating a Maze
        3. Multiply-Connected Mazes
        4. More Complex Mazes
      5. Navigating Within Mazes
        1. Collision Detection and Camera Control
        2. Line of Sight
        3. Maze-Threading
        4. Pathfinding and the A *Algorithm
      6. Exercise
        1. Exercise 24.1
      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
        1. Zero-Sum Games
        2. Solving a Game
        3. A Game Theory Approach to Tic-Tac-Toe
        4. Applying a Search to Tic-Tac-Toe
        5. Limitations
      4. Tactical AI
        1. How Chess Programs Work
        2. Training a Program
        3. A Tactical AI Approach to Tic-Tac-Toe
      5. Top-Down AI
        1. Goals and Subgoals
        2. When to Change the Goal
        3. A Top-Down AI Approach to Tic-Tac-Toe
      6. Bottom-Up AI
        1. Neural Networks
        2. Training a Neural Network
        3. Actors and Emergence
        4. A Bottom-Up AI Approach to Tic-Tac-Toe
      7. Exercises
        1. Exercise 25.1
        2. Exercise 25.2
      8. Summary
      9. You Should Now Know
    5. 26. Search Techniques
      1. In This Chapter
      2. Overview
      3. Problem Solving
        1. Representing a Problem
        2. Searching for Answers
        3. Interaction
      4. Case Study
        1. Preparing the Ground
        2. Creating the Search Function
      5. Genetic Algorithms
        1. Natural Selection
        2. The Genetic Algorithm
        3. Tweaking
      6. Exercise
        1. Exercise 26.1
      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