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 [source]#
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.
- Parameters
surface (xr.DataArray) – 2D array of values to bin.
start (array-like object of 2 numeric elements) – (y, x) or (lat, lon) coordinates of the starting point.
goal (array like object of 2 numeric elements) – (y, x) or (lat, lon) 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.
- Returns
path_agg – 2D array of pathfinding values. All other input attributes are preserved.
- 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
… sourcecode:: python
>>> 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') >>> print(path_agg) <xarray.DataArray (lat: 5, lon: 4)> array([[ nan, nan, nan, nan], [0. , nan, nan, nan], [ nan, 1.41421356, nan, nan], [ nan, nan, 2.82842712, nan], [ nan, 4.24264069, nan, nan]]) Coordinates: * lon (lon) float64 0.0 1.0 2.0 3.0 * lat (lat) float64 4.0 3.0 2.0 1.0 0.0