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.

- Introduction to A*
- Heuristics
- Implementation notes
- Sketch
- Performance
- Source code and demos
- Set representation
- Unsorted arrays or linked lists
- Sorted arrays
- Sorted linked lists
- Binary heaps
- Sorted skip lists
- Indexed arrays
- Hash tables
- Splay trees
- HOT queues
- Pairing heaps
- Data Structure Comparison
- Hybrid representations
- Interaction with the game loop
- Variants of A*
- Beam search
- Iterative deepening
- Dynamic weighting
- Bandwidth search
- Bidirectional search
- Dynamic A* and Lifelong Planning A*
- Jump Point Search
- Theta*
- Dealing with moving obstacles
- Space used by precalculated paths

There are many other topics related to pathfinding.

- Map representations
- Grids
- Polygonal maps
- Navigation Meshes
- Hierarchical
- Wraparound maps
- Connected Components
- Road maps
- Skip links
- Waypoints
- Graph Format Recommendations
- Long and short term goals
- Movement costs for pathfinders
- User experience with shortest paths
- Applications
- AI techniques
- References

Next: Introduction to A*→