# Amit's A* Pages

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

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. Breaking ties
6. Searching for an area

3. Implementation notes

1. Sketch
2. Source 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. Comparison
11. Hybrid representations

4. Interaction with the game loop

1. Early exit
2. Interruptible algorithm
3. Group movement
4. Refinement

4. Variations of A*

1. Beam search
2. Iterative deepening
3. Dynamic weighting
4. Bandwidth search
5. Bidirectional search
6. Dynamic A* and Lifelong Planning A*

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. Grid
2. Polygonal maps
3. Flat
4. Hierarchical
5. Wraparound maps
6. Road maps
7. Duals
8. Skip links
9. Waypoints

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