HPA* searches crossings between grid chunks, then returns a route of adjacent cells.
dotnet add package RecursiveAI.OnePathRequires .NET 10 (net10.0); .NET 9 and earlier aren’t supported.
using RecursiveAI.OnePath; var grid = new Grid(24, 8); grid.SetRect(11, 0, 1, 5, AreaCosts.Wall); var path = grid.FindPath( new Cell(1, 1), new Cell(21, 5), new GridOptions { Algorithm = GridAlgorithm.Hpa, HpaChunkSize = 4 }); Console.WriteLine(path.Status); Console.WriteLine(path.Algorithm);
Prints:
Found Hpa
Unzip the example, then dotnet run.
The full program
The full program uses the same wall as the snippet at the top: column 11 is blocked in rows 0–4. A two-cell-square agent uses four-connected moves around the wall’s bottom end. The program checks both endpoints, each footprint and every move before printing.
using RecursiveAI.OnePath; var grid = new Grid(24, 8); grid.SetRect(11, 0, 1, 5, AreaCosts.Wall); var start = new Cell(1, 1); var goal = new Cell(21, 5); var options = new GridOptions { Algorithm = GridAlgorithm.Hpa, HpaChunkSize = 4, Connectivity = Connectivity.Four, AgentSize = 2 }; var path = grid.FindPath(start, goal, options); if (!path.Found) throw new InvalidOperationException(path.Status.ToString()); if (path.Cells[0] != start || path.Cells[^1] != goal) throw new InvalidOperationException("Wrong endpoints"); for (int i = 0; i < path.Cells.Length; i++) { var cell = path.Cells[i]; for (int y = cell.Y; y < cell.Y + options.AgentSize; y++) for (int x = cell.X; x < cell.X + options.AgentSize; x++) if (!grid.Contains(x, y) || !grid.IsWalkable(x, y)) throw new InvalidOperationException("Blocked footprint"); if (i > 0) { var previous = path.Cells[i - 1]; if (Math.Abs(cell.X - previous.X) + Math.Abs(cell.Y - previous.Y) != 1) throw new InvalidOperationException("Not a face move"); } } Console.WriteLine($"{path.Algorithm}: {path.Status}"); Console.WriteLine($"{path.Cells.Length} cells, agent size {options.AgentSize}"); Console.WriteLine(string.Join(" -> ", path.Cells.ToArray() .Select(cell => $"({cell.X},{cell.Y})")));
dotnet run prints:
Hpa: Found 25 cells, agent size 2 (1,1) -> (2,1) -> (3,1) -> (4,1) -> (5,1) -> (6,1) -> (7,1) -> (8,1) -> (8,2) -> (8,3) -> (8,4) -> (9,4) -> (9,5) -> (10,5) -> (11,5) -> (12,5) -> (13,5) -> (14,5) -> (15,5) -> (16,5) -> (17,5) -> (18,5) -> (19,5) -> (20,5) -> (21,5)
An unreachable goal returns NoPath; a blocked or out-of-range endpoint returns StartInvalid or GoalInvalid.
Variations
Use eight-cell chunks and turn off smoothing. This is a complete replacement for Program.cs.
using RecursiveAI.OnePath; var grid = new Grid(24, 8); grid.SetRect(11, 0, 1, 5, AreaCosts.Wall); var path = grid.FindPath( new Cell(1, 1), new Cell(21, 5), new GridOptions { Algorithm = GridAlgorithm.Hpa, HpaChunkSize = 8, HpaSmoothing = false }); Console.WriteLine(path.Status); Console.WriteLine(path.Algorithm);
Found Hpa
Related recipes
The short answer
For hierarchical pathfinding in C#, select GridAlgorithm.Hpa in a GridOptions passed to Grid.FindPath. Set HpaChunkSize to the chunk side in cells. OnePath builds a graph of crossings between chunks, searches that graph, then expands the result into legal grid moves. Read the returned Algorithm because unsupported configurations fall back to A*.
Use this when your map is a square grid and you want a chunk-based route abstraction. This implementation has one hierarchy level. It does not create a hierarchy over hex grids, voxel volumes or navigation meshes. The complete program crosses several four-cell chunks while preserving a two-cell-square footprint.
How does HPA* pathfinding work?
The map is divided into square chunks. Along a shared border, a consecutive run of open crossing positions is an entrance. OnePath chooses representative transitions from each entrance and makes their endpoint cells abstract nodes. Edges between those nodes describe crossing a border or traveling inside one chunk.
Before queries can use the abstract graph, chunk-local Dijkstra searches price the routes between portal nodes. A query connects its start and goal to their chunk’s nodes, then runs abstract A*. Finally it repeats chunk-local searches to reconstruct the cell route. The result is not just a list of distant portals for your application to connect itself.
Preprocessing therefore has real work and storage: it computes intra-chunk connections and stores pairwise costs. Chunk size changes both the number of chunks and the size of their local searches. Choose it for your map and query pattern rather than treating the example’s value as a universal setting. The default side is 16 cells. See the grid documentation for the exact entrance and preprocessing rules.
Is hierarchical pathfinding near optimal?
OnePath documents that HPA* finds a path exactly when A* finds one, and every returned step is legal. It does not promise an optimal route. Representative entrances restrict the abstract search, so the result can cost more than the optimum, but never less.
Smoothing is enabled by default. It searches along allowed grid directions for cheaper shortcuts to later cells of the refined route. It does not turn the result into arbitrary-angle segments: the final list remains a sequence of grid moves, and Cost is computed from those final moves. The variation disables smoothing so you can use the refined route without that pass.
HPA* ignores the heuristic selection and weight in GridOptions. Use ordinary A* when exact optimal cost is the deciding requirement; changing HPA*’s heuristic weight is not a way to request an optimal hierarchical result.
How does clearance-based pathfinding work with HPA*?
AgentSize is a square footprint in cells. Its position is the top-left cell, and the square extends toward positive x and y. The full program uses size two, so each returned position must have an open two-by-two block. It uses four-connected moves to make the footprint transitions explicit.
The hierarchy is built for one agent size and movement rule. Tier one caches hierarchies by chunk size, agent size, connectivity and diagonal rule. Both NoCornerCutting and NoSqueezing are supported; eight-connected AllowAll and custom cost or blocking callbacks trigger A* fallback.
Edits through Grid mark affected chunks for rebuilding. Every query refreshes the hierarchy before searching; changing area costs invalidates the whole hierarchy. You can keep the grid and issue another query after edits instead of constructing your own portal graph. Do not assume a previously returned route remains safe after you block one of its cells.