---
title: "Grid pathfinding: A*, JPS, Theta* and HPA*"
url: https://recursiveai.org/onepath/cookbook/grid-pathfinding/
description: "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."
version: "1.1.0"
---

# Grid pathfinding: A*, JPS, Theta* and HPA*

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:

```csharp
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](https://recursiveai.org/onepath/docs/grids/).