Interactive demo
Theta*
Grid paths zigzag: even the cheapest one only turns in steps of 45°. Theta*, by Alex Nash, Kenny Daniel, Sven Koenig and Ariel Felner (2007), checks the line of sight while searching and finds paths that run straight at any angle.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. The white lines link every cell to its parent, often far away. Theta* only takes shortcuts across open ground; around and through mud it falls back to steps from cell to cell.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Theta* always estimates with the straight-line distance.
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Expanded right now
- Path
Properties
Optimal
No
Usually shorter than the best grid path, but not guaranteed to be the shortest path at any angle.
Weighted cells
Conditionally
Shortcuts only cross open ground; through mud it moves from cell to cell.
Heuristic
Yes
The straight-line distance, the only safe estimate for paths at any angle.
Any angle
Yes
The path can turn at any angle, wherever the line of sight is free.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* this page | No | Shortcuts over open ground only | Yes | Yes |
1. Two candidates
When A* reaches a neighbor from a cell, that cell becomes the neighbor's parent. Theta* also tries the cell's own parent: if the straight line from there to the neighbor is free, the neighbor links to it directly, and its cost is the length of that line.
2. Line of sight
The line is checked cell by cell, as if it were drawn on the grid. Every cell it touches must be open. Where it passes exactly through a corner, both cells beside the corner must be open too, so the path never slips between two walls.
3. Nearly optimal
Theta* paths are usually shorter than any grid path and look natural without smoothing them afterwards. They are not guaranteed to be the shortest paths at any angle, because shortcuts only lead to the parent's parent.
Credits
- Alex Nash, Kenny Daniel, Sven Koenig and Ariel Felner: Theta*: Any-Angle Path Planning on Grids (AAAI 2007).
- The line of sight walks the grid like the supercover lines in Line drawing on a grid by Amit Patel (Red Blob Games).