Overview
HPA* 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
HPA*
HPA* finds routes through graphs, grids, or motion-planning spaces.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Pathfinding
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- 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 HPA* 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
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
- HPA* 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
HPA* operates in O(E log V) time and O(V) space within the Pathfinding family. Often compared with Hierarchical Pathfinding and A* Search.
Sources (2)
What each reference supports for this entry.
Near Optimal Hierarchical Path-Finding
PaperReference for HPA* abstraction over grid clusters and near-optimal hierarchical pathfinding.
Open sourceGame AI Pro
BookGame AI reference supporting HPA* grid navigation, abstraction, many-agent movement, or real-time pathfinding tradeoffs.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Variant ofA* Search
Pathfinding · Core
HPA* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Compare with thisRelationships
View full relationship pageAlternative toHierarchical Pathfinding
HPA* is a route-search alternative to Hierarchical Pathfinding with different heuristic or replanning behavior.
Variant ofA* Search
HPA* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Alternative toSubgoal Graph Pathfinding
HPA* is an alternative to Subgoal Graph Pathfinding within the Pathfinding family.
Related Algorithms
Tags
PathfindingGraph