examples/Pathfinding_Austin_Road_Network.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Path Finding in the City of Austin\n",
    "\n",
    "This notebook demonstrates pathfinding along the city of Austin street network using Xarray-spatial's `pathfinding` module.\n",
    "The a_star_search function provides the shortest path between any two points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Setup:\n",
    "\n",
    "First, we'll need to import some packages: these include the basic array manipulation ones,  \n",
    "as well as some geospatial-focused ones.\n",
    "We'll also grab a few datashader functions for easy rendering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datashader as ds\n",
    "from datashader.transfer_functions import shade, stack, dynspread, set_background\n",
    "import geopandas\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import spatialpandas\n",
    "import xarray as xa\n",
    "\n",
    "from xrspatial import a_star_search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Load data\n",
    "\n",
    "Now, we're ready to load up the data and transform it into a format we can work with.\n",
    "\n",
    "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": [
    "We'll start by opening the shapefile, transforming the crs (coordinate reference system) to the commonly-used longitude/latitude,  \n",
    "and, after a quick clean-up, transforming it to a spatialpandas GeoDataFrame.\n",
    "\n",
    "Now our data is ready to be aggregated to an xarray DataArray raster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "streets = geopandas.read_file(\n",
    "    \"data/geo_export_9c395dda-0b29-41ec-89b4-a51a898f7104.shp\"\n",
    ")\n",
    "streets = streets.to_crs(\"EPSG:4326\")\n",
    "streets = streets.explode(\"geometry\").reset_index(drop=True)\n",
    "streets_spd = spatialpandas.GeoDataFrame(streets, geometry=\"geometry\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define study area (find range of x and y) and aggregate:\n",
    "\n",
    "To finish off our set-up:\n",
    "- We'll define a study area, with xmin, xmax, ymin, and ymax; this set the x, y coordinates we'll be using in our aggregate.\n",
    "- We'll set up a datashader Canvas object, which provides an easy frame for setting up a new raster and aggregating data to it.\n",
    "- Finally, we'll aggregate the streets data into a lines raster with Canvas.line.\n",
    "\n",
    "- We also set up the start and goal point (y, x) coordinates, and set up a DataFrame and aggregation for visualization.\n",
    "\n",
    "Some shading and stacking of all of this displays our complete setup below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xmin, ymin, xmax, ymax = (\n",
    "    streets.geometry.bounds.minx.min(),\n",
    "    streets.geometry.bounds.miny.min(),\n",
    "    streets.geometry.bounds.maxx.max(),\n",
    "    streets.geometry.bounds.maxy.max(),\n",
    ")\n",
    "xrange = (xmin, xmax)\n",
    "yrange = (ymin, ymax)\n",
    "xrange, yrange"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H, W = 600, 800\n",
    "cvs = ds.Canvas(plot_width=W, plot_height=H, x_range=xrange, y_range=yrange)\n",
    "\n",
    "street_agg = cvs.line(streets_spd, geometry=\"geometry\")\n",
    "street_shaded = dynspread(shade(street_agg, cmap=[\"salmon\"]))\n",
    "\n",
    "# Pick two locations\n",
    "start = (30.08214069, -97.73662282)\n",
    "goal = (30.17656606, -97.63753489)\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(street_shaded, start_shaded, goal_shaded), \"black\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shortest path using A* from start location to goal location\n",
    "\n",
    "Now, we can do some pathfinding:\n",
    "\n",
    "In `a_star_search`, we'll input the Austin city streets lines aggregate we built above, the start and goal point coordinates, and barriers:\n",
    "    - Barriers defines all non-crossable points in the raster: for our streets raster, this includes all non-street areas, all of which have 0 set as their value. \n",
    "\n",
    "We've also set `snap-start` and `snap-goal` to `True`: this helps ensure the start and goal points are set correctly.\n",
    "\n",
    "The result is a the shortest path al\n",
    "    "
   ]
  },
  {
   "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 = a_star_search(\n",
    "    street_agg, start, goal, barriers=[0], snap_start=True, snap_goal=True\n",
    ")\n",
    "\n",
    "path_shaded = dynspread(shade(path_agg, cmap=[\"green\"]), threshold=1, max_px=1)\n",
    "set_background(stack(street_shaded, path_shaded, start_shaded, goal_shaded), \"black\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}