The problem we’re trying to solve is to get a game object from the starting point to a goal. Pathfinding addresses the problem of finding a good path from the starting point to the goal―avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.). Movement addresses the problem of taking a path and moving along it. It’s possible to spend your efforts on only one of these. At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm would find a path when the object begins to move and the object would follow that path, oblivious to everything else. At the other extreme, a movement-only system would not look ahead to find a path (instead, the initial “path” would be a straight line), but instead take one step at a time, considering the local environment at every point. Best results are achieved by using both pathfinding and movement algorithms.

Pathfinding

  1. Introduction to A*
    1. Algorithms
    2. Dijkstra’s Algorithm and Best-First-Search
    3. The A* Algorithm
  2. Heuristics
    1. A*’s Use of the Heuristic
    2. Speed or accuracy?
    3. Scale
    4. Exact heuristics
      1. Precomputed exact heuristic
      2. Linear exact heuristic
    5. Heuristics for grid maps
      1. Manhattan distance
      2. Diagonal distance
      3. Euclidean distance
      4. Euclidean distance, squared
      5. Multiple goals
      6. Breaking ties
  3. Implementation notes
    1. Sketch
      1. Connectivity
    2. Source code and demos
      1. Demos
      2. Code
    3. Set representation
      1. Unsorted arrays or linked lists
      2. Sorted arrays
      3. Sorted linked lists
      4. Sorted skip lists
      5. Indexed arrays
      6. Hash tables
      7. Binary heaps
      8. Splay trees
      9. HOT queues
      10. Data Structure Comparison
      11. Hybrid representations
    4. Interaction with the game loop
      1. Early exit
      2. Interruptible algorithm
      3. Group movement
      4. Refinement
  4. Variants of A*
    1. Beam search
    2. Iterative deepening
    3. Dynamic weighting
    4. Bandwidth search
    5. Bidirectional search
    6. Dynamic A* and Lifelong Planning A*
    7. Jump Point Search
    8. Theta*
  5. Dealing with moving obstacles
    1. Recalculating paths
    2. Path splicing
    3. Watching for map changes
    4. Predicting obstacle movement
  6. Space used by precalculated paths
    1. Locations vs. directions
    2. Path compression
      1. Location storage
      2. Direction storage
    3. Computed waypoints
    4. Limited path length
    5. Summary

Other topics

There are many other topics related to pathfinding.

  1. Map representations
    1. Grids
      1. Tile movement
      2. Edge movement
      3. Vertex movement
    2. Polygonal maps
      1. Managing complexity
    3. Navigation Meshes
      1. Polygon movement
      2. Polygon edge movement
      3. Polygon vertex movement
      4. Hybrid movement
      5. Path smoothing
    4. Hierarchical
    5. Wraparound maps
    6. Connected Components
    7. Road maps
    8. Skip links
    9. Waypoints
    10. Graph Format Recommendations
  2. Long and short term goals
    1. Unit movement
    2. Behavior flags or stacks
    3. Waiting for movement
    4. Coordinated movement
  3. Movement costs for pathfinders
    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
  4. User experience with shortest paths
    1. Dumb movement
    2. Smart movement
    3. Multithreading
    4. Multiple units
    5. Multiple waypoints
  5. Applications
    1. Exploration
    2. Spying
    3. Road building
    4. Terrain analysis
    5. City building
  6. AI techniques
    1. Neural Networks
    2. Genetic Algorithms
    3. Reinforcement Learning
  7. References
Next: