{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Pathfinding" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Importing Packages" ] }, { "cell_type": "code", "execution_count": 1, "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*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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": 2, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAyAAAAJYCAYAAACadoJwAAAUkUlEQVR4nO3dTW7cSBaFUarR8IK9gfIKasHVA/fASlVKyh8yGbx8EXEOYMCQPciJIH16N8W3ZVl+LwAAAAH/OfsFAAAA8xAgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACDmv2e/AKjo942PvcVfBQDAeFxA4Itb8fHo4wAArCdA4MqzyBAhAAD7CBB4tzYuRAgAwOsECAAAEONN6PCCf379PPslAFDcj19/n/0SoCQBAi/wRQX+hLjPBfjMD6jgORMsAIAGLlEuzOExAQLv1j7nw/NAAPjKRRDWEyBw5VlcvC3O6wD8659fP8UHbOQ9IPDF2/L4Seg/fv39ESG+4ADMS3jAa1xA4Ia39z//+/Xz4+/XLhtf1xCAOYkPeJ0AgR1ECMBcTK5gPxMs2MkkC2AOwgPacAGBBkyyAMYmPqAdAQINiRCAsZhcQXsmWNCYSRbAGIQHHMMFBA5gkgXQN/EBxxEgcCARAtAXkys4ngkWHMwkC6APwgMyXEAgwCQLoDbxATkCBIJECEAtJleQZ4IFYSZZADUIDziHCwicwCQL4FziA84jQOBEIgQgy+QKzmeCBSczyQLIEB5QgwsIFGCSBXAs8QF1CBAoRIQAtGVyBfWYYEExJlkAbQgPqMkFBAoyyQLYR3xAXQIEChMhANuYXEF9JlhQnEkWwDrCA/rgAgIdMMkCeEx8QD8ECHREhAB8ZnIF/THBgs6YZAH8ITygTy4g0CGTLGB24gP6JUCgYyIEmI3JFfTPBAs6Z5IFzEJ4wBhcQGAAJlnA6MQHjEOAwEBECDAakysYjwkWDMYkCxiF8IAxuYDAgEyygN6JDxiXAIGBiRCgNyZXMD4TLBicSRbQC+EBc3ABgQmYZAHViQ+YhwCBiYgQoBqTK5iPCRZMxiQLqEJ4wJxcQGBCJlnA2cQHzEuAwMRECJBmcgWYYMHkTLKAFOEBLIsLCLCYZAHHEx/AhQABPogQoDWTK+ArEyzgE5MsoBXhAdziAgJ8Y5IF7CU+gHsECHCXCAG2MrkCnjHBAh4yyQLWEh7AGi4gwFMmWcAz4gNYS4AAq4kQ4CuTK2ArEyxgE5Ms4EJ4AK9wAQE2M8kCxAfwKgECvEyEwHxMroC9TLCAXUyyYB7CA2jBBQTYzSQLxic+gFYECNCMCIHxmFwBrZlgAU2ZZME4hAdwBBcQoDmTLOif+ACOIkCAw4gQ6I/JFXA0EyzgUCZZ0A/hASS4gACHM8mC+sQHkCJAgBgRAvWYXAFpJlhAlEkW1CE8gDO4gABxJllwPvEBnEWAAKcRIZBncgWczQQLOJVJFuQID6ACFxDgdCZZcDzxAVQhQIAyRAi0Z3IFVGOCBZRikgXtCA+gIhcQoByTLNhPfABVCRCgLBEC25lcAdWZYAGlmWTBesID6IELCFCeSRY8Jz6AXggQoBsiBL4zuQJ6Y4IFdMUkC/4lPIAeuYAA3THJAvEB9EuAAN0SIczI5AronQkW0DWTLGYiPIARuIAA3TPJYgbiAxiFAAGGIUIYkckVMBoTLGAoJlmMRHgAI3IBAYZjksUIxAcwKgECDEuE0COTK2B0JljA0Eyy6InwAGbgAgIMzySLHogPYBYCBJiGCKEikytgNiZYwFRMsqhEeAAzcgEBpmOSRQXiA5iVAAGmJUI4g8kVMDsTLGBqJlkkCQ8AFxAAkywixAfAHwIE4J0I4QgmVwCfmWABXDHJoiXhAfCdCwjAFyZZtCA+AG4TIAB3iBBeYXIF8JgJFsADJllsITwAnnMBAXjCJIs1xAfAOgIEYCURwi0mVwDbmGABbGCSxTXhAbCdCwjARiZZLIv4AHiVAAF4kQiZk8kVwD4mWAA7mGTNRXgA7OcCArCTSdYcxAdAGwIEoBERMiaTK4C2TLAAGjLJGovwAGjPBQSgMZOsMYgPgGMIEICDiJA+mVwBHMsEC+BAJll9ER4Ax3MBATiYSVYfxAdAhgABCBEhNZlcAWSZYAEEmWTVIjwA8lxAAMJMsmoQHwDnECAAJxEh5zC5AjiXCRbAiUyysoQHwPlcQABOZpKVIT4AahAgAEWIkGOYXAHUYoIFUIhJVlvCA6AeFxCAYkyy2hAfADUJEICiRMhrTK4AajPBAijMJGsb4QFQnwsIQHEmWeuID4A+CBCAToiQ20yuAPpiggXQEZOsz4QHQH9cQAA6Y5L1h/gA6JMAAejUrBFicgXQNxMsgI7NNskSHgD9cwEB6NwskyzxATAGAQIwiFEjxOQKYCwmWAADGW2SJTwAxuMCAjCYUSZZ4gNgTAIEYFC9RojJFcDYTLAABtbbJEt4AIzPBQRgcL1MssQHwBwECMAkqkaIyRXAXEywACZSbZIlPADm4wICMJkqkyzxATAnAQIwqbMixOQKYG4mWAATS0+yhAcALiAAk0tNssQHAMsiQAB4d1SEmFwBcM0EC4APrSdZwgOAr1xAAPik1SRLfABwiwAB4KZXI8TkCoBHTLAAuGvrJEt4APCMCwgAD62dZIkPANYQIACsci9CTK4A2MIEC4DVvkaI8ABgKwECTxz9cDbonc8RALYQIPCEn+7CZ1+Dw+cIfCfM4T7vAQFgtcvk6hIdl0mWb7YAWEuAALDKvfd7tHpwIQBzECAAPLT2t1yJEADW8B4QAO7a+luutj64EID5uIAAcNOrv2LXJAuARwQIAJ+0erCgCAHgFhMsAD60frCgSRYAX7mAALAsy3FPNTfJAuCaAAGYXKvJ1TMiBIBlMcECmFoiPK6ZZAHgAgIwqXR8XJhkAcxNgABMJjW5ekaEAMzJBAtgIhXC45pJFsB8XEAAJlEtPi5MsgDmIkAABldlcvWMCAGYgwkWwMB6CI9rJlkA43MBARhUb/FxYZIFMDYBAjCYXiZXz4gQgDGZYAEMZITwuGaSBTAeFxCAQYwWHxcmWQBjESAAnRtlcvWMCAEYgwkWQMdmCI9rJlkA/XMBAejUbPFxYZIF0DcBAtCZWSZXz4gQgD6ZYAF0RHh8ZpIF0B8XEIBOiI/bTLIA+iJAAIozuVpHhAD0wQQLoDDhsY1JFkB9LiAARYmP15hkAdQmQACKMblqQ4QA1GSCBVCI8GjLJAugHhcQgCLExzFMsgBqESAAJzO5yhAhADWYYAGcSHhkmWQBnM8FBOAk4uMcJlkA5xIgAGEmVzWIEIBzmGABBAmPWkyyAPJcQABCxEdNJlkAWQIE4GAmV30QIQAZJlgABxIefTHJAjieCwjAQcRHn0yyAI4lQAAaM7kagwgBOIYJFkBDwmMsJlkA7bmAADQiPsZkkgXQlgAB2Mnkag4iBKANEyyAHYTHXEyyAPZzAQF4kfiYk0kWwD4CBGAjkyuWxSQL4FUmWAAbCA+umWQBbOcCArCS+OAWkyyAbQQIwBMmV6whQgDWMcECeEB4sIVJFsBzLiAAd4gPXmGSBfCYAAH4wuSKFkQIwG0mWABXhActmWQBfOcCAvBOfHAEkyyAzwQIMD2TKxJECMAfJljA1IQHSSZZAC4gwMTEB2cwyQJmJ0CA6ZhcUYEIAWZlggVMRXhQiUkWMCMXEGAa4oOKTLKA2QgQYHgmV/RAhACzMMEChiY86IlJFjADFxBgWOKDHplkAaMTIMBwTK4YgQgBRmWCBQxFeDASkyxgRC4gwDDEByMyyQJGI0CA7plcMQMRAozCBAvomvBgJiZZwAhcQIBuiQ9mZJIF9E6AAN0xuQKTLKBfJlhAV4QH/MskC+iRCwjQDfEB35lkAb0RIEB5JlfwnAgBemGCBZQmPGA9kyygBy4gQFniA7YzyQKqEyBAOSZXsJ8IAaoywQJKER7QjkkWUJELCFCG+ID2TLKAagQIcDqTKzieCAGqMMECTiU8IMckC6jABQQ4jfiAPJMs4GwCBIgzuYLziRDgLCZYQJTwgDpMsoAzuIAAMeID6jHJAtIECHA4kyuoT4QAKSZYwKGEB/TDJAtIcAEBDiM+oD8mWcDRBAjQnMkV9E+EAEcxwQKaEh4wDpMs4AguIEAz4gPGY5IFtCZAgN1MrmB8IgRoxQQL2EV4wDxMsoAWXECAl4kPmI9JFrCXAAE2M7kCRAjwKhMsYBPhAVyYZAGvcAEBVhMfwFcmWcBWAgR4yuQKeEaEAGuZYAEPCQ9gLZMsYA0XEOAu8QFsZZIFPCNAgG9MroC9RAhwjwkW8InwAFoxyQJucQEBPogPoDWTLOArAQKYXAGHEyHAhQkWTE54ACkmWcCyuIDA1MQHkGaSBQgQmJDJFXA2EQLzMsGCyQgPoAqTLJiTCwhMRHwA1ZhkwXwECEzA5AqoToTAPEywYHDCA+iFSRbMwQUEBiY+gN6YZMH4BAgMyOQK6J0IgXGZYMFghAcwCpMsGJMLCAxEfACjMcmC8QgQGIDJFTA6EQLjMMGCzgkPYBYmWTAGFxDomPgAZmOSBf0TINAhkytgdiIE+mWCBZ0RHgB/mGRBn1xAoCPiA+AzkyzojwCBDphcATwmQqAfJlhQnPAAWMckC/rgAgKFiQ+AbUyyoD4BAgWZXAHsI0KgLhMsKEZ4ALRhkgU1uYBAIeIDoC2TLKhHgEABJlcAxxIhUIcJFpxMeABkmGRBDS4gcCLxAZBlkgXnEyBwApMrgHOJEDiPCRaECQ+AGkyy4BwuIBAkPgBqMcmCPAECASZXALWJEMgxwYKDCQ+APphkQYYLCBxIfAD0xSQLjidA4AAmVwB9EyFwHBMsaEx4AIzBJAuO4QICDYkPgLGYZEF7AgQaMLkCGJsIgXZMsGAn4QEwB5MsaMMFBHYQHwBzMcmC/VxA4AV+AgYwt0uEfPs68Pv935e/l+Wv94+9RV8alCdAYCNXDwCW5cYk6/ed//h7ESFwRYDABuIDgGsfXxPuxceFCIEPAgRWMLkC4K5n8XH9/0QICBB4xtUDAKCdt2V9t8N0/JYTAJ758deGH1K5gIAAAQDYZct3UgIEPAcEAADIESAAAHusvWq4fsCyLAIEAGC/Z3EhPuCDAAEAaOFeZIgP+MSb0AEAgBgXEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMT8H3GXoHurIy+ZAAAAAElFTkSuQmCC\n", "text/html": [ "" ], "text/plain": [ "\n", "array([[4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " ...,\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080]], dtype=uint32)\n", "Coordinates:\n", " * x (x) float64 0.0025 0.0075 0.0125 0.0175 ... 3.982 3.987 3.993 3.998\n", " * y (y) float64 0.003333 0.01 0.01667 0.02333 ... 3.983 3.99 3.997" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- 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": 3, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAyAAAAJYCAYAAACadoJwAAAWjElEQVR4nO3dS44cR7IF0GDjQQvWBmQr6AXrDdQDfkQ6K8vTMiMs/HMOIDh1wUFOCOmW3Sp+OY7jnwMAAKDAf+7+AAAAwD4UEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAEAZBQQAACijgAAAAGUUEAAAoIwCAgAAlFFAAACAMgoIAABQRgEBAADKKCAAAECZ/7v7A8CI/vkg+1L+KQAA1uMCAo2PysdnOQAAz1NA4Ce9kqGEAAC8RwGBb54tF0oIAMDrFBAAAKCMb0KHF/wdf979EQAY3B/x37s/AgxJAYEX+I8KfC3i/izAr3yBCvpMsAAATvC9lCvm8DkFBL559u/5+BLHccR1nwOA+bgIwvNMsOAnX47Pf8rVl/jpX6J5AdjO98mV8gHPU0Cg8aiEPLyQxKGEAGzI1QNeY4IFH/jy7Z//jz9//Po4jsdF41EOwJKUD3idCwhkRfP2cgCWYXIF73MBgVdFMgdgan7KFZxDAYF3RDIHYEomV3AeEyx4VzRvLwdgGiZXcD4XEDhLJHMAhmZyBddQQOBMkcwBGJLJFVzHBAvOFs3bywEYhskVXM8FBK4SyRyAW5lcQQ0FBK4UyRyAW5hcQR0TLLhaNG8vB6CMyRXUcwGBKpHMAbiUyRXcQwGBSpHMAbiEyRXcxwQLqkXz9nIATmNyBfdzAYG7RDIH4C0mVzAGBQTuFMkcgJeYXME4TLDgbtG8vRyAp5lcwXhcQGAUkcwB+JTJFYxJAYGRRDIH4EMmVzAuEywYTTRvLwfgB5MrGJ8LCIwqkjnA5kyuYA4KCIwskjnApkyuYB4mWDC6aN5eDrARkyuYjwsIzCKSOcDiTK5gTgoIzCSSOcCiTK5gXiZYMJto3l4OsBCTK5ifCwjMKpI5wORMrmANCgjMLJI5wKRMrmAdJlgwu2jeXg4wEZMrWI8LCKwikjnA4EyuYE0KCKwkkjnAoEyuYF0mWLCaaN5eDjAQkytYnwsIrCqSOcDNTK5gDwoIrCySOcBNTK5gHyZYsLpo3l4OUMjkCvbjAgK7iGQOcDGTK9iTAgI7iWQOcBGTK9iXCRbsJpq3lwOcyOQKcAGBXUUyB3iTyRVwHAoI7C2SOcCLTK6A70ywYHfRvL0cIMHkCmi5gABfRTIH6DC5Aj6igAD/imQO8IDJFfCICRbwq2jeXg7wE5MroMcFBPhYJHNgeyZXwDMUEOCxSObAtkyugGeZYAGfi+bt5cBWTK6ALBcQ4DmRzIHlmVwBr1BAgOdFMgeWZXIFvMoEC8iJ5u3lwFJMroB3uYAAr4lkDkzP5Ao4gwICvC6SOTAtkyvgLCZYwHuieXs5MBWTK+BsLiDAOSKZA8MzuQKuoIAA54lkDgzL5Aq4igkWcK5o3l4ODMXkCriaCwhwjUjmwO1MroAKCghwnUjmwG1MroAqJljAtaJ5ezlQyuQKqOYCAtSIZA5czuQKuIMCAtSJZA5cxuQKuIsJFlArmreXA6cyuQLu5gIC3COSOfA2kytgBAoIcJ9I5sDLTK6AUZhgAfeK5u3lQIrJFTAaFxBgDJHMgS6TK2BECggwjkjmwEMmV8CoTLCAsUTz9nLgFyZXwOhcQIAxRTIHTK6AKSggwLgimcPGTK6AWZhgAWOL5u3lsBmTK2A2LiDAHCKZwwZMroAZKSDAPCKZw8JMroBZmWABc4nm7eWwGJMrYHYuIMCcIpnDAkyugBUoIMC8IpnDxEyugFWYYAFzi+bt5TAZkytgNS4gwBoimcMETK6AFSkgwDoimcPATK6AVZlgAWuJ5u3lMBiTK2B1LiDAmiKZwwBMroAdKCDAuiKZw41MroBdmGABa4vm7eVQzOQK2I0LCLCHSOZQwOQK2JECAuwjkjlcyOQK2JUJFrCXaN5eDiczuQJ25wIC7CmSOZzA5ApAAQF2Fskc3mByBfCVCRawt2jeXg5JJlcAv3IBATgO1xAuYXIF8DsFBOC7SObwCZMrgI+ZYAH8LJq3l0PD5Argcy4gAB+JZA6HyRXAMxQQgEcimbM1kyuA55hgAXwmmreXsx2TK4AcFxCAZ0QyZwsmVwB5CgjAsyKZszSTK4DXmGABZETz9nKWY3IF8B4XEIBXRDJnCSZXAO9TQABeFcmcqZlcAZzDBAvgHdG8vZzpmFwBnMsFBOAMkcyZgskVwPkUEICzRDJnaCZXANcwwQI4UzRvL2c4JlcA13IBAbhCJHOGYHIFcD0FBOAqkcy5lckVQA0TLIArRfP2csqZXAHUcgEBqBDJnBImVwD1FBCAKpHMuZTJFcA9TLAAKkXz9nJOZ3IFcC8XEIA7RDLnFCZXAPdTQADuEsmct5hcAYzBBAvgTtG8vZw0kyuAsbiAAIwgkjlPMbkCGI8CAjCKSOZ8yuQKYEwmWAAjiebt5fzG5ApgbC4gACOKZM5xHCZXADNQQABGFcl8cyZXAHMwwQIYWTRvL9+QyRXAXFxAAGYQyXwTJlcA81FAAGYRyXxxJlcAczLBAphJNG8vX5DJFcDcXEAAZhTJfBEmVwDzU0AAZhXJfHImVwBrMMECmFk0by+fkMkVwFpcQABWEMl8EiZXAOtRQABWEcl8cCZXAGsywQJYSTRvLx+QyRXA2lxAAFYUyXwQJlcA61NAAFYVyfxmJlcAezDBAlhZNG8vv4HJFcBeXEAAdhDJvIjJFcB+FBCAXUQyv5jJFcCeTLAAdhLN28svYHIFsDcXEIAdRTI/ickVAAoIwK4imb/J5AqA4zDBAthbNG8vf4HJFQA/cwEB4LJriMkVAC0FBICvIpl3mFwB8BETLAD+Fc3byz9gcgXAZ1xAAPhdJPNvTK4A6FFAAPhY5HKTKwCeYYIFwGPRvD/lfxxfy4bJFQAZCggAfXF8fPkIxQOAHAUEOr5/dRf49+rxiziOvw9/TgB4jgICHb66C7/6O/78rYj8+Peo/zwwIl+8gsd8EzoAT/vxjebx4Dc8ygHgGwUEgKe0P+Xq4ewqaj4PAHMywQLgU5/+lKto3l4OwPZcQAB46Om/WDCSOQDbUkAA+FD6LxaMZA7AlkywAPjFW3+xYDRvLwdgOy4gAPzw9OSqJ5I5ANtQQAA4juOFyVVPJHMAtmCCBbC5tyZXPdG8vRyA5bmAAGzstMlVTyRzAJalgABs6vTJVU8kcwCWZIIFsJlLJ1c90by9HIDluIAAbKRsctUTyRyAZSggAJson1z1RDIHYAkmWACLu3Vy1RPN28sBmJ4LCMDChplc9UQyB2BaCgjAooabXPVEMgdgSiZYAIsZenLVE83bywGYjgsIwEKmmVz1RDIHYBoKCMAipptc9UQyB2AKJlgAk5t6ctUTzdvLARieCwjAxJaZXPVEMgdgWAoIwKSWm1z1RDIHYEgmWACTWXpy1RPN28sBGI4LCMBEtplc9UQyB2AYCgjAJLabXPVEMgdgCCZYAIPbenLVE83bywG4nQsIwMBMrp4UyRyA2yggAIMyuUqKZA7ALUywAAZjcvWGaN5eDkA5FxCAgZhcnSSSOQBlFBCAQZhcnSySOQAlTLAAbmZydaFo3l4OwOVcQABuZHJVJJI5AJdRQABuYnJVLJI5AJcwwQIoZnJ1o2jeXg7A6VxAAAqZXA0ikjkAp1FAAIqYXA0mkjkApzDBAriYydXAonl7OQBvcwEBuJDJ1SQimQPwMgUE4CImV5OJZA7AS0ywAE5mcjWxaN5eDkCaCwjAiUyuFhHJHICnKSAAJzG5WkwkcwCeYoIF8CaTq4VF8/ZyALpcQADeYHK1iUjmADykgAC8yORqM5HMAfiQCRZAksnVxqJ5ezkAv3EBAUgwueI4DtcQgDcoIABPMrniF5HMATiOwwQLoMvkioeieXs5AC4gAJ8xueIpkcwBNqaAADxgckVKJHOATZlgATRMrnhZNG8vB9iQCwjAT0yuOEUkc4CNKCAA35hccapI5gCbMMECtmdyxWWieXs5wAZcQICtmVxRIpI5wMIUEGBbJleUimQOsCgTLGA7JlfcJpq3lwMsyAUE2IrJFUOIZA6wEAUE2IbJFUOJZA6wCBMsYHkmVwwrmreXAyzABQRYmskVU4hkDjAxBQRYlskVU4lkDjApEyxgOSZXTCuat5cDTMgFBFiKyRVLiGQOMBEFBFiGyRVLiWQOMAkTLGB6JlcsK5q3lwNMwAUEmJrJFVuIZA4wMAUEmJbJFVuJZA4wKBMsYDomV2wrmreXAwzIBQSYiskVHK4hwNQUEGAaJlfwk0jmAIMwwQKGZ3IFD0Tz9nKAAbiAAEMzuYInRDIHuJECAgzL5AoSIpkD3MQECxiOyRW8KJq3lwPcwAUEGIrJFZwgkjlAIQUEGIbJFZwokjlAERMs4HYmV3CRaN5eDlDABQS4lckVFIhkDnAhBQS4jckVFIpkDnAREyygnMkV3CSat5cDXMAFBChlcgUDiGQOcCIFBChjcgUDiWQOcBITLOByJlcwqGjeXg5wAhcQ4FImVzCBSOYAb1BAgMuYXMFEIpkDvMgECzidyRVMKpq3lwO8wAUEOJXJFSwgkjlAggICnMbkChYSyRzgSSZYwNtMrmBR0by9HOAJLiDAW0yuYAORzAE+oYAALzO5go1EMgd4wAQLSDO5gk1F8/ZygA+4gAApJleAawjwDgUEeJrJFfBDJHOAb0ywgC6TK+BD0by9HOBwAQE6TK6ArkjmwNYUEOAhkyvgaZHMgW2ZYAG/MbkCXhLN28uBLbmAAL8wuQLeFskc2IoCAvxgcgWcJpI5sA0TLMDkCrhGNG8vB7bgAgKbM7kCLhfJHFiaAgIbM7kCykQyB5ZlggUbMrkCbhHN28uBJbmAwGZMroDbRTIHlqKAwEZMroBhRDIHlmGCBRswuQKGFM3by4EluIDA4kyugOFFMgempoDAwkyugGlEMgemZYIFCzK5AqYUzdvLgSm5gMBiTK6A6UUyB6aigMBCTK6AZUQyB6ZhggULMLkClhTN28uBKbiAwORMroDlRTIHhqaAwMRMroBtRDIHhmWCBRMyuQK2FM3by4EhuYDAZEyugO1FMgeGooDAREyuAL6JZA4MwwQLJmByBfCBaN5eDgzBBQQGZ3IF0BHJHLiVAgIDM7kCeFIkc+A2JlgwIJMrgBdE8/Zy4BYuIDAYkyuAN0UyB0opIDAQkyuAk0QyB8qYYMEATK4ALhDN28uBEi4gcDOTK4CLRTIHLqWAwI1MrgCKRDIHLmOCBTcwuQK4QTRvLwcu4QICxUyuAG4WyRw4lQIChUyuAAYRyRw4jQkWFDC5AhhQNG8vB07hAgIXM7kCGFwkc+AtCghcyOQKYBKRzIGXmWDBBUyuACYUzdvLgZe4gMDJTK4AJhfJHEhRQOBEJlcAi4hkDjzNBAtOYHIFsKBo3l4OPMUFBN5kcgWwuEjmwKcUEHiDyRXAJiKZAw+ZYMELTK4ANhTN+1H+z9df/nH89zj++pZ/ufRTwXQUEEhy9QDYXBwfXz7+efD7/zmUEPiJCRYkKB8AHMfxewH566Pf9JNH5QQ25AICTzC5AuA38e19tly4hMBxHAoIdLl6AACc58vhKAgPfb98AMAjf/yV+CKVCwgoIAAAb8n8n5QCAr4JHQAAqKOAAAC849mrhusHHMehgAAAvK9XLpQP+EEBAQA4w6OSoXzAL3wTOgAAUMYFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQBkFBAAAKKOAAAAAZRQQAACgjAICAACUUUAAAIAyCggAAFBGAQEAAMooIAAAQJn/Aeznl865rzbbAAAAAElFTkSuQmCC\n", "text/html": [ "" ], "text/plain": [ "\n", "array([[4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " ...,\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080]], dtype=uint32)\n", "Coordinates:\n", " * x (x) float64 0.0025 0.0075 0.0125 0.0175 ... 3.982 3.987 3.993 3.998\n", " * y (y) float64 0.003333 0.01 0.01667 0.02333 ... 3.983 3.99 3.997" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For 4-connectivity distance, we use the same arguments as above, but set the connectivity to 4." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAyAAAAJYCAYAAACadoJwAAAUk0lEQVR4nO3dS1YjSRZFUadWrRxwTqAYQQ44O1GNQIQAfdzl5tefme3dJGioQ4jDu5LelmX5tQAAAAT85+wHAAAAzEOAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAICY/579AKCiXze+9hZ/FAAA43EBgW9uxcejrwMAsJ4AgSvPIkOEAADsI0Dgw9q4ECEAAK8TIAAAQIwXocML/n3/++yHAEBxf73/c/ZDgJIECLzAkwr8DnE/C/CVP1DBcyZYAAANXKJcmMNjAgQ+rP2cD58HAsB3LoKwngCBK8/i4m1xXgfgj3/f/xYfsJHXgMA3b8vjT0L/6/2fzwjxhAMwL+EBrxEgcMPbsizL+9UX3r/+++UJx5MPwJz8/w+vM8GCHa6vIQCMz+QK9nMBgZ1MsgDmIDygDRcQaODytouuIQBjEh/QjgCBhkQIwFhMrqA9EyxozCQLYAzCA47hAgIHMMkC6Jv4gOMIEDiQCAHoi8kVHM8ECw5mkgXQB+EBGS4gEGCSBVCb+IAcAQJBIgSgFpMryDPBgjCTLIAahAecwwUETmCSBXAu8QHnESBwIhECkGVyBeczwYKTmWQBZAgPqMEFBAowyQI4lviAOgQIFCJCANoyuYJ6TLCgGJMsgDaEB9TkAgIFmWQB7CM+oC4BAoWJEIBtTK6gPhMsKM4kC2Ad4QF9cAGBDphkATwmPqAfAgQ6IkIAvjK5gv6YYEFnTLIAfhMe0CcXEOiQSRYwO/EB/RIg0DERAszG5Ar6Z4IFnTPJAmYhPGAMLiAwAJMsYHTiA8YhQGAgIgQYjckVjMcECwZjkgWMQnjAmFxAYEAmWUDvxAeMS4DAwEQI0BuTKxifCRYMziQL6IXwgDm4gMAETLKA6sQHzEOAwERECFCNyRXMxwQLJmOSBVQhPGBOLiAwIZMs4GziA+YlQGBiIgRIM7kCTLBgciZZQIrwAJbFBQRYTLKA44kP4EKAAJ9ECNCayRXwnQkW8IVJFtCK8ABucQEBfjDJAvYSH8A9AgS4S4QAW5lcAc+YYAEPmWQBawkPYA0XEOApkyzgGfEBrCVAgNVECPCdyRWwlQkWsIlJFnAhPIBXuIAAm5lkAeIDeJUAAV4mQmA+JlfAXiZYwC4mWTAP4QG04AIC7GaSBeMTH0ArAgRoRoTAeEyugNZMsICmTLJgHMIDOIILCNCcSRb0T3wARxEgwGFECPTH5Ao4mgkWcCiTLOiH8AASXECAw5lkQX3iA0gRIECMCIF6TK6ANBMsIMokC+oQHsAZXECAOJMsOJ/4AM4iQIDTiBDIM7kCzmaCBZzKJAtyhAdQgQsIcDqTLDie+ACqECBAGSIE2jO5AqoxwQJKMcmCdoQHUJELCFCOSRbsJz6AqgQIUJYIge1MroDqTLCA0kyyYD3hAfTABQQozyQLnhMfQC8ECNANEQI/mVwBvTHBArpikgV/CA+gRy4gQHdMskB8AP0SIEC3RAgzMrkCemeCBXTNJIuZCA9gBC4gQPdMspiB+ABGIUCAYYgQRmRyBYzGBAsYikkWIxEewIhcQIDhmGQxAvEBjEqAAMMSIfTI5AoYnQkWMDSTLHoiPIAZuIAAwzPJogfiA5iFAAGmIUKoyOQKmI0JFjAVkywqER7AjFxAgOmYZFGB+ABmJUCAaYkQzmByBczOBAuYmkkWScIDwAUEwCSLCPEB8JsAAfggQjiCyRXAVyZYAFdMsmhJeAD85AIC8I1JFi2ID4DbBAjAHSKEV5hcATxmggXwgEkWWwgPgOdcQACeMMliDfEBsI4AAVhJhHCLyRXANiZYABuYZHFNeABs5wICsJFJFssiPgBeJUAAXiRC5mRyBbCPCRbADiZZcxEeAPu5gADsZJI1B/EB0IYAAWhEhIzJ5AqgLRMsgIZMssYiPADacwEBaMwkawziA+AYAgTgICKkTyZXAMcywQI4kElWX4QHwPFcQAAOZpLVB/EBkCFAAEJESE0mVwBZJlgAQSZZtQgPgDwXEIAwk6waxAfAOQQIwElEyDlMrgDOZYIFcCKTrCzhAXA+FxCAk5lkZYgPgBoECEARIuQYJlcAtZhgARRiktWW8ACoxwUEoBiTrDbEB0BNAgSgKBHyGpMrgNpMsAAKM8naRngA1OcCAlCcSdY64gOgDwIEoBMi5DaTK4C+mGABdMQk6yvhAdAfFxCAzphk/SY+APokQAA6NWuEmFwB9M0EC6Bjs02yhAdA/1xAADo3yyRLfACMQYAADGLUCDG5AhiLCRbAQEabZAkPgPG4gAAMZpRJlvgAGJMAARhUrxFicgUwNhMsgIH1NskSHgDjcwEBGFwvkyzxATAHAQIwiaoRYnIFMBcTLICJVJtkCQ+A+biAAEymyiRLfADMSYAATOqsCDG5ApibCRbAxNKTLOEBgAsIwORSkyzxAcCyCBAAPhwVISZXAFwzwQLgU+tJlvAA4DsXEAC+aDXJEh8A3CJAALjp1QgxuQLgERMsAO7aOskSHgA84wICwENrJ1niA4A1BAgAq9yLEJMrALYwwQJgte8RIjwA2EqAwApHf0Ab9MzPBwBbCBBYwV944Y/vweHnA34S5nCf14AAsNplcnWJjsskyy9bAKwlQABY5d7rPVp9cCEAcxAgADy09l2uRAgAa3gNCAB3bX2Xq60fXAjAfFxAALjp1bfYNckC4BEBAsAXrT5YUIQAcIsJFgCfWn+woEkWAN+5gACwLMtxn2pukgXANQECMLlWk6tnRAgAy2KCBTC1RHhcM8kCwAUEYFLp+LgwyQKYmwABmExqcvWMCAGYkwkWwEQqhMc1kyyA+biAAEyiWnxcmGQBzEWAAAyuyuTqGRECMAcTLICB9RAe10yyAMbnAgIwqN7i48IkC2BsAgRgML1Mrp4RIQBjMsECGMgI4XHNJAtgPC4gAIMYLT4uTLIAxiJAADo3yuTqGRECMAYTLICOzRAe10yyAPrnAgLQqdni48IkC6BvAgSgM7NMrp4RIQB9MsEC6Ijw+MokC6A/LiAAnRAft5lkAfRFgAAUZ3K1jggB6IMJFkBhwmMbkyyA+lxAAIoSH68xyQKoTYAAFGNy1YYIAajJBAugEOHRlkkWQD0uIABFiI9jmGQB1CJAAE5mcpUhQgBqMMECOJHwyDLJAjifCwjAScTHOUyyAM4lQADCTK5qECEA5zDBAggSHrWYZAHkuYAAhIiPmkyyALIECMDBTK76IEIAMkywAA4kPPpikgVwPBcQgIOIjz6ZZAEcS4AANGZyNQYRAnAMEyyAhoTHWEyyANpzAQFoRHyMySQLoC0BArCTydUcRAhAGyZYADsIj7mYZAHs5wIC8CLxMSeTLIB9BAjARiZXLItJFsCrTLAANhAeXDPJAtjOBQRgJfHBLSZZANsIEIAnTK5YQ4QArGOCBfCA8GALkyyA51xAAO4QH7zCJAvgMQEC8I3JFS2IEIDbTLAArggPWjLJAvjJBQTgg/jgCCZZAF8JEGB6JlckiBCA30ywgKkJD5JMsgBcQICJiQ/OYJIFzE6AANMxuaICEQLMygQLmIrwoBKTLGBGLiDANMQHFZlkAbMRIMDwTK7ogQgBZmGCBQxNeNATkyxgBi4gwLDEBz0yyQJGJ0CA4ZhcMQIRAozKBAsYivBgJCZZwIhcQIBhiA9GZJIFjEaAAN0zuWIGIgQYhQkW0DXhwUxMsoARuIAA3RIfzMgkC+idAAG6Y3IFJllAv0ywgK4ID/jDJAvokQsI0A3xAT+ZZAG9ESBAeSZX8JwIAXphggWUJjxgPZMsoAcuIEBZ4gO2M8kCqhMgQDkmV7CfCAGqMsECShEe0I5JFlCRCwhQhviA9kyygGoECHA6kys4nggBqjDBAk4lPCDHJAuowAUEOI34gDyTLOBsAgSIM7mC84kQ4CwmWECU8IA6TLKAM7iAADHiA+oxyQLSBAhwOJMrqE+EACkmWMChhAf0wyQLSHABAQ4jPqA/JlnA0QQI0JzJFfRPhABHMcECmhIeMA6TLOAILiBAM+IDxmOSBbQmQIDdTK5gfCIEaMUEC9hFeMA8TLKAFlxAgJeJD5iPSRawlwABNjO5AkQI8CoTLGAT4QFcmGQBr3ABAVYTH8B3JlnAVgIEeMrkCnhGhABrmWABDwkPYC2TLGANFxDgLvEBbGWSBTwjQIAfTK6AvUQIcI8JFvCF8ABaMckCbnEBAT6JD6A1kyzgOwECmFwBhxMhwIUJFkxOeAApJlnAsriAwNTEB5BmkgUIEJiQyRVwNhEC8zLBgskID6AKkyyYkwsITER8ANWYZMF8BAhMwOQKqE6EwDxMsGBwwgPohUkWzMEFBAYmPoDemGTB+AQIDMjkCuidCIFxmWDBYIQHMAqTLBiTCwgMRHwAozHJgvEIEBiAyRUwOhEC4zDBgs4JD2AWJlkwBhcQ6Jj4AGZjkgX9EyDQIZMrYHYiBPplggWdER4Av5lkQZ9cQKAj4gPgK5Ms6I8AgQ6YXAE8JkKgHyZYUJzwAFjHJAv64AIChYkPgG1MsqA+AQIFmVwB7CNCoC4TLChGeAC0YZIFNbmAQCHiA6AtkyyoR4BAASZXAMcSIVCHCRacTHgAZJhkQQ0uIHAi8QGQZZIF5xMgcAKTK4BziRA4jwkWhAkPgBpMsuAcLiAQJD4AajHJgjwBAgEmVwC1iRDIMcGCgwkPgD6YZEGGCwgcSHwA9MUkC44nQOAAJlcAfRMhcBwTLGhMeACMwSQLjuECAg2JD4CxmGRBewIEGjC5AhibCIF2TLBgJ+EBMAeTLGjDBQR2EB8AczHJgv1cQOAF/gIGMLdLhPx4Hvj18e/LP8vyv4+vvUUfGpQnQGAjVw8AluXGJOvXnW/8tYgQuCJAYAPxAcC1z+eEe/FxIULgkwCBFUyuALjrWXxcf58IgeVtWf9jA3N5P/sBANCF/z3/lk8CBLwLFgAAkCNAAACAGBMsAIA9tvwmZYIFLiAAALusjQrxAcuyCBAAgP2exYX4gE8CBACghXuRIT7gC68BAQAAYlxAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAECNAAACAGAECAADECBAAACBGgAAAADECBAAAiBEgAABAjAABAABiBAgAABAjQAAAgBgBAgAAxAgQAAAgRoAAAAAxAgQAAIgRIAAAQIwAAQAAYgQIAAAQI0AAAIAYAQIAAMQIEAAAIEaAAAAAMQIEAACIESAAAECMAAEAAGIECAAAEPN/bfSaix5pkkEAAAAASUVORK5CYII=\n", "text/html": [ "" ], "text/plain": [ "\n", "array([[4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " ...,\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080],\n", " [4278190080, 4278190080, 4278190080, ..., 4278190080, 4278190080,\n", " 4278190080]], dtype=uint32)\n", "Coordinates:\n", " * x (x) float64 0.0025 0.0075 0.0125 0.0175 ... 3.982 3.987 3.993 3.998\n", " * y (y) float64 0.003333 0.01 0.01667 0.02333 ... 3.983 3.99 3.997" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "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": [ "### References" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- A* search algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 2 }