examples/user_guide/7_Pathfinding.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Xarray-spatial\n",
    "### User Guide: Pathfinding\n",
    "-----\n",
    "\n",
    "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.\n",
    "\n",
    "[A* Pathfinding](#A*)\n",
    "\n",
    "-----------\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's use datashader to render our images...\n",
    "\n",
    "First, we'll import some basic packages and some functions from datashader for image rendering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import datashader as ds\n",
    "from datashader.transfer_functions import shade\n",
    "from datashader.transfer_functions import stack\n",
    "from datashader.transfer_functions import dynspread\n",
    "from datashader.transfer_functions import set_background\n",
    "from datashader.colors import Elevation\n",
    "\n",
    "import xrspatial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A*\n",
    "\n",
    "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, ...). \n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's generate a fake line raster and find the shortest path with A*.\n",
    "\n",
    "- First, we'll generate a line raster by setting up a pandas DataFrame specifying the line coordinates.\n",
    "- Then, we'll aggregate that into a lines raster with Canvas.line\n",
    "- Once we have that, we'll choose a start and goal point to put into the a* pathfinding function.\n",
    "- For visualization, we'll also aggregate those points and render them in an image together with the lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from xrspatial import a_star_search\n",
    "\n",
    "# define range of x and y\n",
    "xrange = (0, 4)\n",
    "yrange = (0, 4)\n",
    "\n",
    "# create line raster\n",
    "ys = [1, 1, 3, 3, 1, 1, np.nan, 1, 3, np.nan, 1, 3, np.nan, 1, 3, np.nan, 2, 2]\n",
    "xs = [1, 3, 3, 1, 1, 3, np.nan, 1, 3, np.nan, 3, 1, np.nan, 2, 2, np.nan, 1, 3]\n",
    "line_df = pd.DataFrame(dict(x=xs, y=ys))\n",
    "\n",
    "W = 800\n",
    "H = 600\n",
    "cvs = ds.Canvas(plot_width=W, plot_height=H, x_range=xrange, y_range=yrange)\n",
    "line_agg = cvs.line(line_df, x=\"x\", y=\"y\").astype(int)\n",
    "line_shaded = dynspread(shade(line_agg, cmap=[\"black\", \"salmon\"]))\n",
    "\n",
    "# pick up 2 random locations\n",
    "start = (3, 1)\n",
    "goal = (1, 3)\n",
    "\n",
    "start_df = pd.DataFrame({\"x\": [start[1]], \"y\": [start[0]]})\n",
    "start_agg = cvs.points(start_df, \"x\", \"y\")\n",
    "start_shaded = dynspread(shade(start_agg, cmap=[\"red\"]), threshold=1, max_px=5)\n",
    "\n",
    "goal_df = pd.DataFrame({\"x\": [goal[1]], \"y\": [goal[0]]})\n",
    "goal_agg = cvs.points(goal_df, \"x\", \"y\")\n",
    "goal_shaded = dynspread(shade(goal_agg, cmap=[\"lime\"]), threshold=1, max_px=5)\n",
    "\n",
    "set_background(stack(line_shaded, start_shaded, goal_shaded), \"black\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're now ready to apply `a_star_search`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating the 8-connectivity shortest path:\n",
    "\n",
    "- To calculate the path, we input the line raster and the start and goal point coordinates.\n",
    "- 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).\n",
    "- Finally, we'll also set snap_start and snap_goal to True.\n",
    "- Note: since `a_star_search` uses 8-connectivity by default, we don't need to pass that in.\n",
    "\n",
    "The shortest path is highlighted in the rendering below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the path from start to goal,\n",
    "# barriers are uncrossable cells. In this case, they are cells with a value of 0\n",
    "\n",
    "path_agg_8_connectivity = a_star_search(\n",
    "    line_agg, start, goal, barriers=[0], snap_start=True, snap_goal=True\n",
    ")\n",
    "\n",
    "path_shaded = dynspread(shade(path_agg_8_connectivity, cmap=[\"green\"]))\n",
    "set_background(stack(line_shaded, path_shaded, start_shaded, goal_shaded), \"black\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4-connectivity\n",
    "\n",
    "For 4-connectivity distance, we use the same arguments as above, but set the connectivity to 4."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# find the path from start to goal,\n",
    "# barriers are uncrossable cells. In this case, they are cells with a value of 0\n",
    "\n",
    "path_agg_4_connectivity = a_star_search(\n",
    "    line_agg, start, goal, barriers=[0], snap_start=True, snap_goal=True, connectivity=4\n",
    ")\n",
    "\n",
    "path_shaded = dynspread(shade(path_agg_4_connectivity, cmap=[\"green\"]))\n",
    "set_background(stack(line_shaded, path_shaded, start_shaded, goal_shaded), \"black\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "\n",
    "### References\n",
    "\n",
    "- A* search algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}