Pathfinding#

Xarray-spatial’s Pathfinding provides a comprehensive tool for finding the shortest path from one point to another in a raster that can contain any level of complex boundaries or obstacles amidst an interconnected set of traversable path segments.

Importing Packages#

[1]:
import numpy as np
import pandas as pd

import datashader as ds
from datashader.transfer_functions import shade
from datashader.transfer_functions import stack
from datashader.transfer_functions import dynspread
from datashader.transfer_functions import set_background
from datashader.colors import Elevation

import xrspatial

To download the examples data, run the command xrspatial examples in your terminal. All the data will be stored in your current directory inside a folder named xrspatial-examples.

A*#

A* is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (min distance travelled, shortest time, …).

The xrspatial.a_star_search function calculates the shortest path in pixel space from a start location to a goal location through a given aggregate surface graph. The graph should be a line raster which contains crossable and non-crossable (a.k.a walls or barrieres) values. Note that both start and goal are in (lon, lat), or (x, y) coordinate space and must be within the graph. xrspatial.a_star_search provides 2 separate options, snap_start and snap_goal, which can be set to true to snap locations to the nearest valid value before beginning pathfinding. It also provides a connectivity option to indicate neighborhood structure. This value can be set to 4 or 8 for 4-connectivity or 8-connectivity.

Let’s generate a fake line raster and find the shortest path with A*.

  • First, we’ll generate a line raster by setting up a pandas DataFrame specifying the line coordinates.

  • Then, we’ll aggregate that into a lines raster with Canvas.line

  • Once we have that, we’ll choose a start and goal point to put into the a* pathfinding function.

  • For visualization, we’ll also aggregate those points and render them in an image together with the lines.

[2]:
from xrspatial import a_star_search

# define range of x and y
xrange = (0, 4)
yrange = (0, 4)

# create line raster
ys = [1, 1, 3, 3, 1, 1, np.nan, 1, 3, np.nan, 1, 3, np.nan, 1, 3, np.nan, 2, 2]
xs = [1, 3, 3, 1, 1, 3, np.nan, 1, 3, np.nan, 3, 1, np.nan, 2, 2, np.nan, 1, 3]
line_df = pd.DataFrame(dict(x=xs, y=ys))

W = 800
H = 600
cvs = ds.Canvas(plot_width=W, plot_height=H, x_range=xrange, y_range=yrange)
line_agg = cvs.line(line_df, x="x", y="y").astype(int)
line_shaded = dynspread(shade(line_agg, cmap=["black", "salmon"]))

# pick up 2 random locations
start = (3, 1)
goal = (1, 3)

start_df = pd.DataFrame({"x": [start[1]], "y": [start[0]]})
start_agg = cvs.points(start_df, "x", "y")
start_shaded = dynspread(shade(start_agg, cmap=["red"]), threshold=1, max_px=5)

goal_df = pd.DataFrame({"x": [goal[1]], "y": [goal[0]]})
goal_agg = cvs.points(goal_df, "x", "y")
goal_shaded = dynspread(shade(goal_agg, cmap=["lime"]), threshold=1, max_px=5)

set_background(stack(line_shaded, start_shaded, goal_shaded), "black")
[2]:

We’re now ready to apply a_star_search.

Calculating the 8-connectivity shortest path#

  • To calculate the path, we input the line raster and the start and goal point coordinates.

  • We also set the barriers; i.e. cells that are not crossable. In our case, any cell with a value of 0 (all the black non-line cells).

  • Finally, we’ll also set snap_start and snap_goal to True.

  • Note: since a_star_search uses 8-connectivity by default, we don’t need to pass that in.

The shortest path is highlighted in the rendering below.

[3]:
# find the path from start to goal,
# barriers are uncrossable cells. In this case, they are cells with a value of 0

path_agg_8_connectivity = a_star_search(
    line_agg, start, goal, barriers=[0], snap_start=True, snap_goal=True
)

path_shaded = dynspread(shade(path_agg_8_connectivity, cmap=["green"]))
set_background(stack(line_shaded, path_shaded, start_shaded, goal_shaded), "black")
[3]:

4-connectivity#

For 4-connectivity distance, we use the same arguments as above, but set the connectivity to 4.

[4]:
# find the path from start to goal,
# barriers are uncrossable cells. In this case, they are cells with a value of 0

path_agg_4_connectivity = a_star_search(
    line_agg, start, goal, barriers=[0], snap_start=True, snap_goal=True, connectivity=4
)

path_shaded = dynspread(shade(path_agg_4_connectivity, cmap=["green"]))
set_background(stack(line_shaded, path_shaded, start_shaded, goal_shaded), "black")
[4]:

References#