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.