Overview
Block A* 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
Block A*
Block A* 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
- 3
- Formulas
- 0
- Relationships
- 2
- 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 Block A* 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
- Block A* 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
Block A* operates in O(E log V) time and O(V) space within the Pathfinding family. Often compared with Dijkstra's Algorithm and A* Search.
Sources (3)
What each reference supports for this entry.
Game AI Pro
BookGame AI reference for block-level grid pathfinding and local-distance preprocessing tradeoffs.
Artificial Intelligence: A Modern Approach
BookAI search reference for A* heuristics and graph-search correctness used by Block A* variants.
Open sourceBlock A*
PaperOriginal Block A* reference for local distance databases and block-level grid pathfinding.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toDijkstra's Algorithm
Block A* is a route-search alternative to Dijkstra's Algorithm with different heuristic or replanning behavior.
Variant ofA* Search
Block A* is a pathfinding variant of A* Search with a different search or heuristic tradeoff.
Related Algorithms
Tags
PathfindingGraph