Overview
Lazy Theta* is a pathfinding method that searches a graph, grid, or configuration space using costs, heuristics, or incremental updates. It is useful when route quality, replanning cost, or search speed matters more than a naive traversal.
CoreSource checked
Lazy Theta*
Lazy Theta* guides route search with a heuristic score.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Pathfinding
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
state spacepath costsearch frontierfrontiercost estimatepath reconstruction
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E)
Average
O(E log V)
Worst
O(E log V)
Space
O(V)
When to Use
- Use Lazy Theta* when the map, costs, and movement rules match its search assumptions.
- Use it when route quality and search budget must be balanced explicitly.
When Not to Use
- Avoid when the heuristic or cost model does not match the real movement constraints.
- Avoid when dynamic updates make a simpler replanning strategy easier to validate.
What It Does
- Searches a state space for routes
- Uses costs, heuristics, or incremental updates
- Returns a route or reachable region
Use Cases
- Game navigation
- Robotics planning
- Route planning
Inputs
- Graph, grid, or map
- Start and goal
- Costs or heuristic
Outputs
- Path
- Distance estimate
- Search tree
Key Formulas (1)
Any-angle shortcut test
if lineof sight(parent(current), neighbor), relax through parent(current)
if line_of_sight(parent(current), neighbor), relax through parent(current)Uses visibility checks to skip unnecessary grid corners.
Pseudocode
- 1.Initialize start state, goal state, and search records
- 2.Select the next frontier node using cost, heuristic, or sampling rule
- 3.Expand reachable neighbors or samples
- 4.Update path costs and parent links
- 5.Return the reconstructed path or failure result
Canonical Example
- Input
- grid with start S and goal G
- Output
- route from S to G or no path
- Explanation
- Lazy Theta* expands candidate states and reconstructs a path when the goal is reached.
Implementation Notes
- Keep cost, heuristic, and parent-link updates in separate steps.
- Test blocked, unreachable, and changing-cost maps.
Common Pitfalls
- Using an inadmissible heuristic while expecting optimal paths gives incorrect guarantees.
- Forgetting to update parent links makes path reconstruction fail.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the frontier expanding through the map and the final path being reconstructed.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Initialize start state, goal state, and search records
pathfindingNotes
Lazy Theta* operates in O(E log V) time and O(V) space within the Pathfinding family. Key governing relation: if line_of_sight(parent(current), neighbor), relax through parent(current). Often compared with Theta* and A* Search.
Sources (1)
What each reference supports for this entry.
Lazy Theta*
PaperReference for Lazy Theta* any-angle pathfinding with deferred line-of-sight checks.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toTheta*
Lazy Theta* is a route-search alternative to Theta* with different heuristic or replanning behavior.
Variant ofA* Search
Lazy Theta* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Alternative toWeighted A*
Lazy Theta* is an alternative to Weighted A* within the Pathfinding family.
Related Algorithms
Tags
PathfindingGraph