This week I learned Theta* pathfinding algorithms for all-angle movement through square grids. These evolved from the classic A*, which keeps its search directed towards a goal and 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 alternate awkwardly between directions.

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 about 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.

The procedure:

1. Have a priority Queue that dispenses squares in order of increasing EPC.
2. Put Start in Queue and set its cost to 0.
3. Until Queue is empty, take the next Square off Queue and:
   1. If Square is the Goal, follow previous squares from Goal back to Start to build the Path and return it.
   2. If not, go through its Neighbors that are passable and have not been queued:
      1. Calculate Neighbor’s cost from Square.
      2. If it is Neighbor’s best cost so far:
         1. Set it as Neighbor’s cost, then calculate Neighbor’s EPC from it.
         2. Set Square as Neighbor’s previous.
         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 previous. If not blocked, continue processing the Neighbor against Square’s previous, not Square itself.

Converting from A* to Lazy Theta*

In 3.2: Process each Neighbor against Square’s previous, not Square itself.

Before 3.1: Check line of sight from Square to its previous. If blocked, find the lowest-cost neighbor of Square that has been queued, then make it Square’s new previous and recalculate Square’s cost.

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 the first line 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

github.com/zehuilu/Lazy-Theta-with-optimization-any-angle-pathfinding