Skip to content
Algorithm Atlas
PathfindingAll categories
SpecializedSource checked

Theta*

Finds smoother grid paths by allowing line-of-sight shortcuts during A* search.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Pathfinding
Difficulty
Advanced
Family
Any-Angle Pathfinding
Tier
Specialized
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
4
Code example
Ready
Visualization
Ready

Overview

Theta* extends A* by checking whether a node can connect directly to an ancestor, reducing grid-like stair-stepping.

Core Concepts

heuristic scoreline of sightparent shortcutany-angle path

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E log V)

Average

O(E log V)

Worst

O(E log V)

Space

O(V)

When to Use

  • Use when grid paths should be smoother than standard A* without full continuous planning.
  • Use when any-angle grid pathfinding is a central requirement.

When Not to Use

  • Avoid when movement must stay strictly on grid edges.
  • Avoid when edge costs or movement rules do not match the algorithm's assumptions.

What It Does

  • Runs heuristic graph search
  • Tests line of sight to ancestors
  • Updates parents to create shortcuts

Use Cases

  • Any-angle grid pathfinding
  • Game navigation
  • Robot planning on grids

Inputs

  • Grid map
  • Start and goal cells
  • Line-of-sight test

Outputs

  • Any-angle path

Key Formulas (1)

Shortcut relaxation

cost(parent[current], neighbor) < cost(current, neighbor) path if lineof sight(parent[current], neighbor)
cost(parent[current], neighbor) < cost(current, neighbor) path if line_of_sight(parent[current], neighbor)

Uses an ancestor as the predecessor when it gives a shorter visible segment.

Pseudocode

  1. 1.Run A* with an open set
  2. 2.For each neighbor, test line of sight from the current node's parent
  3. 3.If visible, relax through the parent instead of the current node
  4. 4.Otherwise relax normally
  5. 5.Reconstruct the parent chain at the goal

Canonical Example

Input
blocked cells = none, start = (0, 0), goal = (3, 3)
Output
path = [(0, 0), (3, 3)]
Explanation
Theta* can connect start directly to goal when line of sight is clear.

Implementation Notes

  • Use the same collision rules for line-of-sight checks that agents use for movement.
  • Store predecessor links so paths can be reconstructed after distances are computed.
  • Keep a tiny example with expected output beside the implementation.

Common Pitfalls

  • A permissive line-of-sight test can cut through blocked corners.
  • Mixing heuristic, movement cost, and tie-breaking rules can produce surprising routes.
  • Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show A* grid expansion with direct shortcut edges replacing staircase parent links.

S
#
#
#
#
#
#
#
G
Step 1 of 5: Run A* with an open set
pathfinding

Notes

The quality and cost depend on the line-of-sight implementation.

Sources (1)

What each reference supports for this entry.

Theta*

Paper

Reference for any-angle grid path planning with line-of-sight relaxation.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Variant ofA* Search

Pathfinding · Core

Theta* modifies A* to allow any-angle paths.

Compare with this
AlternativesLazy Theta*

Pathfinding · Core

Lazy Theta* is a route-search alternative to Theta* with different heuristic or replanning behavior.

Compare with this
Alternative toJump Point Search

Pathfinding · Extended

Both improve grid pathfinding in different ways.

Compare with this

Relationships

View full relationship page
Variant ofA* Search

Theta* modifies A* to allow any-angle paths.

Alternative toJump Point Search

Both improve grid pathfinding in different ways.

Related Algorithms

A* SearchJump Point Search

Tags

PathfindingHeuristic SearchGrid SearchVisibility