ExtendedSource checked

Hierarchical Pathfinding

Speeds pathfinding by planning through coarse regions before refining locally.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: Hierarchical Planning
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 2
Code example: Not ready
Visualization: Ready
Aliases: HPA*

Overview

Hierarchical Pathfinding groups a map into higher-level regions so long paths can be planned with fewer detailed nodes.

Core Concepts

path costabstraction layerheuristic scoringhierarchical planningroute costfrontier expansionpath 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 + V')

When to Use

Use Hierarchical Pathfinding when you need to build an abstract map from local regions.
Use it for large game maps with inputs like grid or navigation map.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the Hierarchical Planning tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Do not treat the O(E' log V') average case as a guarantee; check the O(E log V) worst case.
Avoid it when the required output is not approximate or refined path.

What It Does

Builds an abstract map from local regions
Plans coarsely before refining detailed segments

Use Cases

Large game maps
Real-time navigation
Pathfinding over repeated queries

Inputs

Grid or navigation map
Region abstraction

Outputs

Approximate or refined path

Pseudocode

1.Partition the map into regions
2.Connect entrances between regions
3.Search the abstract region graph
4.Refine each abstract step locally
5.Return the combined path

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Hierarchical Pathfinding: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Grid or navigation map; Region abstraction.
Use this step as the implementation spine: Partition the map into regions.
Then preserve the next state change: Connect entrances between regions.
Store predecessor links if the final path is needed, not just the final distance.

Common Pitfalls

Hierarchical planning trades exactness and preprocessing for faster long-distance queries.
Treating a visited node as final before its best known cost is actually settled.
Returning approximate or refined path without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show a coarse route over regions with local paths filled in.

Step 1 of 5: Partition the map into regions

abstract-path

Notes

Hierarchical Pathfinding operates in O(E' log V') time and O(V + V') space within the Hierarchical Planning family. Often compared with A* Search and Jump Point Search.