Grid pathfinding: A*, JPS, Theta* and HPA* · onepath cookbook

Find paths on a square grid with OnePath, compare the search algorithms on one map, size the path for a larger agent, and add area costs.

The map is 64 × 64 with a wall down the middle that leaves a gap two cells wide at the bottom:

using RecursiveAI.OnePath;
 
// A 64 x 64 map with a long wall that leaves a two-cell gap at the bottom.
var map = new Grid(64, 64);
map.SetRect(32, 0, 1, 62, AreaCosts.Wall);
 
Cell start = new(2, 2), goal = new(60, 4);
foreach (var algorithm in new[] { GridAlgorithm.AStar, GridAlgorithm.Jps, GridAlgorithm.JpsPlus, GridAlgorithm.ThetaStar, GridAlgorithm.Hpa })
{
    GridPath p = map.FindPath(start, goal, new GridOptions { Algorithm = algorithm });
    Console.WriteLine($"{algorithm,-10} ran {p.Algorithm,-10} cost {p.Cost,9:F4}  cells {p.Cells.Length,3}  expanded {p.ExpandedCount,5}");
}
 
// A 3 x 3 agent doesn't fit through the gap.
GridPath fat = map.FindPath(start, goal, GridOptions.ForAgentSize(3));
Console.WriteLine($"3x3 agent: {fat.Status}");
 
// Area costs: a swamp (area 2) that costs three times as much to cross. JPS needs one cost
// everywhere, so this query falls back to A*, and GridPath.Algorithm says so.
map.SetRect(10, 50, 22, 12, 2);
map.Areas[2] = 3.0;
GridPath around = map.FindPath(start, goal, new GridOptions { Algorithm = GridAlgorithm.Jps });
Console.WriteLine($"with swamp: ran {around.Algorithm}, cost {around.Cost:F4}");

Text

AStar      ran AStar      cost  143.1960  cells 121  expanded  2072
Jps        ran Jps        cost  143.1960  cells 121  expanded     5
JpsPlus    ran JpsPlus    cost  143.1960  cells 121  expanded     6
ThetaStar  ran ThetaStar  cost  132.6174  cells   4  expanded  2118
Hpa        ran Hpa        cost  143.1960  cells 121  expanded    47
3x3 agent: NoPath
with swamp: ran AStar, cost 155.4975

Reading the results

A*, JPS and JPS+ find the same optimal eight-connected path (cost 143.196). Jump point search prunes the symmetric alternatives, so it expands 5 nodes instead of 2,072; JPS+ precomputes jump distances once per grid.
Theta* checks line of sight and returns an any-angle path: 4 corner points and a shorter true length. Lazy Theta* does the same with fewer line-of-sight checks.
HPA* searches an abstract graph of grid chunks: very few expansions on large maps, and a path that is near optimal but not guaranteed optimal.
GridOptions.ForAgentSize(3) plans for a 3 × 3 agent from each cell’s clearance; it can’t fit through a 2-cell gap, so the status is NoPath.
Area costs multiply the cost of crossing a cell. JPS needs one cost everywhere, so with the swamp it falls back to A*, and GridPath.Algorithm tells you which search ran.

Other options

GridOptions also sets four- or eight-connected moves and the corner rule, the heuristic and its weight, StepCost and Blocked delegates, and IterationBudget with IterationsPerSlice for spreading a search over frames. HexGrid and VoxelGrid take the same calls. All of it is in grids.