xrspatial.pathfinding.a_star_search

xrspatial.pathfinding.a_star_search(surface: DataArray, start: tuple | list | ndarray, goal: tuple | list | ndarray, barriers: list | None = None, x: str = 'x', y: str = 'y', connectivity: int = 8, snap_start: bool = False, snap_goal: bool = False, friction: DataArray | None = None, search_radius: int | None = None) → DataArray

Calculate the least-cost path from a starting point to a goal through a surface graph, optionally weighted by a friction surface.

A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination. It prioritizes paths that seem to be leading closer to a goal using an admissible heuristic.

When a friction surface is provided, edge costs are geometric_distance * mean_friction_of_endpoints, matching the cost model used by cost_distance(). The heuristic is scaled by the minimum friction value to remain admissible.

The output is an equal-sized xr.DataArray with NaN for non-path pixels and the accumulated cost at each path pixel.

NaN cells in surface are always impassable, whether or not they appear in barriers.

Backend support

Backend	Strategy
NumPy	Numba-jitted kernel (fast, in-memory)
Dask	Sparse Python A* with LRU chunk cache — loads chunks on demand so the full grid never needs to fit in RAM
CuPy	CPU fallback (transfers to numpy, runs numba kernel, transfers back)
Dask + CuPy	Same sparse A* as Dask, with cupy→numpy chunk conversion

Memory safety

Before allocating arrays, the numpy and cupy backends check whether the grid would exceed 80 % of available RAM. If so, a MemoryError is raised suggesting search_radius or dask. When search_radius=None and the grid would exceed 50 % of RAM, an automatic radius is computed. For very long paths (manhattan distance > 1000 pixels) with auto-radius, hierarchical pathfinding (HPA*) is used: the grid is coarsened, a global route is found, then refined segment by segment.

snap_start and snap_goal are not supported with Dask-backed arrays (raises ValueError).

Parameters:

• surface (xr.DataArray or xr.Dataset) – 2D array of the surface to find a path across. A Dataset routes each data variable independently and returns a Dataset of the per-variable results.

• start (array-like object of 2 numeric elements) – (y, x) or (lat, lon) coordinates of the starting point. The point is mapped to the pixel whose cell center is nearest. A point outside the raster bounds raises a ValueError.

• goal (array like object of 2 numeric elements) – (y, x) or (lat, lon) coordinates of the goal location. Mapped to the nearest cell center; a point outside the raster bounds raises a ValueError.

• barriers (array like object, optional) – List of values inside the surface which are barriers (cannot cross). Default is no barriers. Must be a 1-D sequence of numeric values; anything else raises before the search runs. Cells whose value is NaN are always impassable, regardless of this list.

• x (str, default='x') – Name of the x coordinate in input surface raster.

• y (str, default='y') – Name of the y coordinate in input surface raster.

• connectivity (int, default=8) – Use 4 or 8 pixel connectivity to define neighboring cells.

• snap_start (bool, default=False) – Snap the start location to the nearest valid value before beginning pathfinding.

• snap_goal (bool, default=False) – Snap the goal location to the nearest valid value before beginning pathfinding.

• friction (xr.DataArray, optional) – 2-D friction (cost) surface. Must have the same shape as surface. Values must be positive and finite for passable cells; NaN or <= 0 marks impassable barriers. When provided, edge costs become geometric_distance * mean_friction_of_endpoints.

• search_radius (int, optional) – Limit the A* search to a bounding box of ±search_radius pixels around the start and goal. Must be a non-negative integer (or None). Dramatically reduces memory for large grids when start and goal are relatively close. If None (default) and the full grid would exceed 50 % of available RAM, an automatic radius is computed. Ignored for dask-backed arrays (already memory-safe).

Returns:

path_agg – 2D array of pathfinding values. All other input attributes are preserved. A Dataset input returns a Dataset of per-variable results.

Return type:

xr.DataArray of the same type as surface.

References

• Red Blob Games: https://www.redblobgames.com/pathfinding/a-star/implementation.html # noqa

• Nicholas Swift: https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2 # noqa

Examples

>>> import numpy as np
>>> import xarray as xr
>>> from xrspatial import a_star_search
>>> agg = xr.DataArray(np.array([
...     [0, 1, 0, 0],
...     [1, 1, 0, 0],
...     [0, 1, 2, 2],
...     [1, 0, 2, 0],
...     [0, 2, 2, 2]
... ]), dims=['lat', 'lon'])
>>> height, width = agg.shape
>>> _lon = np.linspace(0, width - 1, width)
>>> _lat = np.linspace(height - 1, 0, height)
>>> agg['lon'] = _lon
>>> agg['lat'] = _lat

>>> barriers = [0]  # set pixels with value 0 as barriers
>>> start = (3, 0)
>>> goal = (0, 1)
>>> path_agg = a_star_search(agg, start, goal, barriers, 'lon', 'lat')