Theta*: Any-Angle Path Planning on Grids

Kenny Daniel, Alex Nash, Sven Koenig, Ariel Felner

Abstract

Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are artificially constrained. We present two new correct and complete any-angle path-planning algorithms that avoid this shortcoming. Basic Theta and Angle-Propagation Theta are both variants of A that propagate information along grid edges without constraining paths to grid edges. Basic Theta is simple to understand and implement, fast and finds short paths. However, it is not guaranteed to find true shortest paths. Angle-Propagation Theta achieves a better worst-case complexity per vertex expansion than Basic Theta by propagating angle ranges when it expands vertices, but is more complex, not as fast and finds slightly longer paths. We refer to Basic Theta and Angle-Propagation Theta collectively as Theta. Theta has unique properties, which we analyze in detail. We show experimentally that it finds shorter paths than both A with post-smoothed paths and Field D (the only other version of A we know of that propagates information along grid edges without constraining paths to grid edges) with a runtime comparable to that of A on grids. Finally, we extend Theta to grids that contain unblocked cells with non-uniform traversal costs and introduce variants of Theta which provide different tradeoffs between path length and runtime.

Introduction

Grid-based path planning is ubiquitous in robotics and video games due to its simplicity and efficiency. However, standard A* search on these grids typically restricts movement to a small set of headings (usually 8 directions), resulting in "octile paths" that zig-zag unnecessarily. These paths are often significantly longer than the true shortest path in continuous space.

The Problem with Grid Constraints

Traditional grid paths are constrained to edges, leading to sub-optimal trajectories. While post-processing techniques like path smoothing can straighten these paths, they often fail to find the global any-angle optimum because the initial search was already biased by the grid structure. The discrepancy between a grid-constrained path and the true shortest path is a fundamental limitation of standard grid search.

Comparison between a grid path (a) and the true shortest path (b) in a simple environment.

Proposed Methods: Theta*

The authors propose Theta, a variant of A that considers any-angle paths during the search process rather than as a post-processing step. Two versions are introduced:

  1. Basic Theta*: This algorithm modifies the standard A UpdateVertex procedure. When considering a neighbor $s'$ of vertex $s$, it checks for a line-of-sight between the parent* of $s$ and $s'$. If a clear path exists, it sets the parent of $s'$ to be the parent of $s$, effectively shortcutting the path. This greedy application of the triangle inequality allows the path to ignore grid edges.
  2. Angle-Propagation Theta*: To improve worst-case complexity per vertex expansion, this version propagates angle ranges (fields of view) between vertices. While theoretically more efficient in its expansion complexity, it is more complex to implement and often yields slightly longer paths in practice than the Basic version.

Experimental Results

The algorithms were evaluated on random grids and game maps from Baldur’s Gate II. The results demonstrate that Basic Theta finds paths within ~0.3% of the true shortest path length while maintaining a runtime comparable to standard A.

Runtime vs. Path Length ratio for various algorithms. Theta* provides a superior balance of speed and path quality compared to A* PS and Field D*.

As shown in the figure above, Theta (specifically Basic Theta) occupies a highly desirable position: it is significantly faster than Visibility Graphs (which find the absolute shortest path) and produces much shorter paths than standard A or A with post-smoothing (A PS). It also outperforms Field D in both path quality and runtime efficiency.

Conclusion

Theta* represents a significant advancement in any-angle path planning. By interleaving shortcutting logic directly into the search process, it achieves near-optimal path quality with minimal computational overhead. It is simple to implement and provides a practical solution for applications requiring natural-looking, efficient paths on grid-based maps.

Summary updated

Abstract

Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are artificially constrained. We present two new correct and complete any-angle path-planning algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation Theta* are both variants of A* that propagate information along grid edges without constraining paths to grid edges. Basic Theta* is simple to understand and implement, fast and finds short paths. However, it is not guaranteed to find true shortest paths. Angle-Propagation Theta* achieves a better worst-case complexity per vertex expansion than Basic Theta* by propagating angle ranges when it expands vertices, but is more complex, not as fast and finds slightly longer paths. We refer to Basic Theta* and Angle-Propagation Theta* collectively as Theta*. Theta* has unique properties, which we analyze in detail. We show experimentally that it finds shorter paths than both A* with post-smoothed paths and Field D* (the only other version of A* we know of that propagates information along grid edges without constraining paths to grid edges) with a runtime comparable to that of A* on grids. Finally, we extend Theta* to grids that contain unblocked cells with non-uniform traversal costs and introduce variants of Theta* which provide different tradeoffs between path length and runtime.
BibTeX
@inproceedings{daniel2007theta,
  author = {Kenny Daniel and Alex Nash and Sven Koenig and Ariel Felner},
  title = {{Theta*: Any-Angle Path Planning on Grids}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=hqHgKxW-x-z},
}
Figure