This week I learned Theta* pathfinding algorithms for all-angle movement through square grids. These evolved from the classic A*, which builds a path in the form of one-way links from square to square.
A* grid paths are limited to orthogonal and/or diagonal lines depending on the game. This is fine if the environment is mostly tight corridors along those lines, or the actor has fixed goals arranged along those lines. But with dynamic and arbitrary goals in open spaces the path can awkwardly alternate between the lines.
Theta* addresses that problem. It allows walking straight from any square to any other square if there is an unblocked line of sight. Lazy Theta* is an optimized variant that assumes line of sight first and corrects it later.
Review of A*
Keep the following information for each square:
Passable: Depends on the game. At its simplest, the whole square is either Passable or Impassable.
Previous: Which square would be the previous one in the path.
Cost: Cost to reach this square from Start. Equals cost of its previous + distance to its previous. If square is passable but harmful or otherwise not desirable, factor that in too.
Estimated Path Cost (EPC): square’s cost + distance to Goal.
Been Queued: one of three states - No, In Queue, or Yes.
Procedure:
1. Have a priority Queue that sorts squares by increasing (cost + distance to Goal).
2. Put Start in Queue and set its cost to 0.
3. Until Queue is empty, take the next Square off Queue and:
3.1. If Square is the Goal, follow links from Goal back to Start to build the Path and return it.
3.2. If not, go through its Neighbors that have never been in Queue:
3.2.1. Calculate Neighbor’s cost from Square.
3.2.2. If it is Neighbor’s best cost so far:
3.2.2.1. Set it as Neighbor’s cost.
3.2.2.2. Link Neighbor to Square.
3.2.2.3. Add Neighbor to Queue or update its position in Queue.
Converting from A* to Theta*
This can be fine if your grid is not too big.
Before 3.2.1: Check line of sight from Neighbor to Square’s linked square. If not blocked, continue processing the Neighbor against Square’s linked square, not Square itself.
Converting from A* to Lazy Theta*
In 3.2: Process each Neighbor against Square’s linked square, not Square itself.
Before 3.1: Check line of sight from Square to its linked square. If blocked, link Square to its lowest-cost neighbor that has been in Queue, and recalculate Square’s cost from that neighbor.
Line of Sight
The classic line-on-grid algorithm is Bresenham. Note this implementation is meant for undirected lines. It requires modification if you need it to start at a specific point.
If you want a fatter line of sight to avoid squeezing between diagonal blocks, you might try a second and even third line of sight offset by one square, or consider adapting Wu’s anti-aliased line algorithm.
Extra: Approach an Unreachable Goal
Keep track of a Best Goal, that is the closest known square to the Goal. This should be combined with a limit on the number of squares searched, or you will end up searching every reachable square.
Before 3: Set the Best Goal to Start.
After 3.1: If Square is a better goal than Best Goal, set Best Goal to Square.
After 3: Build the Path as in 3.1 but start at Best Goal instead of Goal.
Sources
Wikipedia Theta*
Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D