Pathfinding

A* Pathfinding

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

Examples

… sourcecode:: python

>>> 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