Amit's Thoughts on Path-Finding

In the first few months of 1996, I read about many approaches to unit movement and path calculation. At the time path-finding did not seem to be widely used in games, but as CPU cycles have increased and as game players have demanded better movement of units, path-finding algorithms have become more popular. I eventually decided to implement path-finding for my game with the A* algorithm. My game has a grid/tile map (as opposed to a continuous coordinate map), and I wanted to tell military units to walk from one spot to another. How could I find a good path? I want my units to take roads when possible, and avoid mountains and hills. (This is similar to the path-finding goals in the once-popular game, "Civilization".) I have been writing up some of my thoughts and findings in these pages.

Find a path or Take a step?

When trying to write movement for game units, the biggest choice is probably between the path-finding and step-taking approaches. Path-Finders look at the map and find a path for your unit to take. After that, your unit takes each step prescribed by the path-finder. Step-takers look only for the next step and leave the remainder of the path to the goal for later. There are advantages and disadvantages to each approach, as you might expect. When two things are in widespread use, you should expect that neither is always better than the other.

  1. Introduction
    1. The A* Algorithm
    2. The Heuristic
    3. Speed or Accuracy?
      1. Computer speed
      2. Number of units
      3. Implementation ideas
  2. Implementation Notes
    1. Sketch
    2. Source code
    3. Performance tips
      1. Bad heuristic
      2. Slow priority queue
    4. Variations of A*
      1. Beam search
      2. Iterative deepening
      3. Dynamic weighting
      4. Bandwidth search
      5. Bidirectional search
      6. Hierarchical A*
      7. Dynamic A*
  3. Dealing with moving obstacles
    1. Recalculating paths
    2. Path splicing
    3. Watching for map changes
    4. Dealing with clashes
    5. Predicting obstacle movement
    6. Waiting for movement
    7. Coordinated movement
  4. Speed of precalculated paths vs. step-taking
    1. Predictable behavior vs. potential speed
      1. Load spikes
      2. Waypoints
    2. Path recalculation
      1. Idle-time recalculation
    3. Redundancy in path-finding
      1. Networked games
      2. Multiple units
    4. Summary
  5. Space used by precalculated paths
    1. Locations vs. directions
    2. Path compression
      1. Location storage
      2. Direction storage
    3. Beacons
    4. Limited path length
    5. Summary
  6. Walking traps in steppers
    1. Predetermined places to avoid
    2. Learning to avoid traps
  7. AI Techniques
    1. Neural Networks
    2. Genetic Algorithms
  8. References

Other topics

There are many other topics related to path-finding.

  1. Map representations
    1. Flat
    2. Hierarchal
    3. Static maps
    4. Beacons
    5. Precalculated shortest paths
    6. Non-grid path-finding
      1. Polygonal maps
      2. Road maps
  2. Long and short term goals
    1. Unit Movement
    2. Behavior flags or stacks
  3. Heuristics
    1. Manhattan distance
    2. Diagonal distance
    3. Straight line distance
    4. Guessing path quality
    5. Breaking ties
    6. Searching for an area
  4. Movement costs for path-finders
    1. Altitude
      1. Moving uphill
      2. Moving up- or downhill
    2. Terrain
      1. Forests, mountains, and hills
      2. Roads
      3. Walls or other barriers
      4. Sloped Land
    3. Enemies and friendly units
    4. Marked beacons
    5. Fuel Consumption
  5. User experience with shortest paths
    1. Dumb Movement
    2. Smart Movement
    3. Multithreading
    4. Multiple Units
  6. Applications
    1. Exploration
    2. Spying
    3. Road Building
    4. City Building

Last modified: Sun Nov 18 11:32:17 2001
From Amit's Game Programming Site
Copyright (C) 2000, Amit J. Patel