xrspatial.pathfinding.a_star_search

xrspatial.pathfinding.a_star_search(surface: xarray.core.dataarray.DataArray, start: Union[tuple, list, numpy.array], goal: Union[tuple, list, numpy.array], barriers: list = [], x: Optional[str] = 'x', y: Optional[str] = 'y', connectivity: int = 8, snap_start: bool = False, snap_goal: bool = False) → xarray.core.dataarray.DataArray

Calculate distance from a starting point to a goal through a surface graph. Starting location and goal location should be within the graph.

A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination. Dijkstra’s Algorithm can find paths to all locations; A* finds paths to one location, or the closest of several locations. It prioritizes paths that seem to be leading closer to a goal.

The output is an equal sized Xarray.DataArray with NaNs for non-path pixels, and the value of the path pixels being the current cost up to that point.

surface: xarray.DataArray

2D array of values to bin

start: array like object (tuple, list, array, …) of 2 numeric elements

(x, y) or (lon, lat) coordinates of the starting point

goal: array like object (tuple, list, array, …) of 2 numeric elements

(x, y) or (lon, lat) coordinates of the goal location

barriers: array like object (default = [])

list of values inside the surface which are barriers (cannot cross)

x: str (default = ‘x)

name of the x coordinate in input surface raster

y: str (default = ‘x’)

name of the y coordinate in input surface raster

connectivity: int (default = 8) 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

path_agg: Xarray.DataArray

2D array, of the same type as the input surface raster. All other input attributes are preserved.

Algorithm References: - Patel, A, Red Blob Games, Implementation of A*, https://www.redblobgames.com/pathfinding/a-star/implementation.html, Accessed Apr. 21, 2021. # noqa - Swift, N, Medium, Easy A* (star) Pathfinding, https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2, Accessed Apr. 21, 2021. # noqa

Imports >>> import numpy as np >>> import xarray as xr >>> from xrspatial import pathfinding as pf

Create Surface Data Array >>> agg = xr.DataArray(np.array([[0, 0, 0, 0, 0], >>> [0, 0, 0, 0, 0], >>> [0, 0, 0, 0, 0], >>> [0, 0, 0, 0, 0], >>> [0, 0, 0, 0, 0]]), >>> dims = [“lat”, “lon”]) >>> height, width = agg.shape >>> _lon = np.linspace(0, width - 1, width) >>> _lat = np.linspace(0, height - 1, height) >>> agg[“lon”] = _lon >>> agg[“lat”] = _lat

Create Path Data Array >>> print(pf.a_star_search(agg, (0,0), (4,4), x = ‘lon’, y = ‘lat’)) <xarray.DataArray (lat: 5, lon: 5)> array([[0. , nan, nan, nan, nan],

[nan, 1.41421356, nan, nan, nan], [nan, nan, 2.82842712, nan, nan], [nan, nan, nan, 4.24264069, nan], [nan, nan, nan, nan, 5.65685425]])

Coordinates:

• lon (lon) float64 0.0 1.0 2.0 3.0 4.0

• lat (lat) float64 0.0 1.0 2.0 3.0 4.0

Pathfinding Proximity