Grid Search¶

Here, we will finally see our algorithms in action!

Let's import the functions we have defined so far, as well as set some options to visualize our grid more clearly.

In [88]:

%reload_ext autoreload
%autoreload 2

import sys
import numpy as np
from pathfinding import grid, utils, finder
from pathfinding.grid import core, viz

# we do this so np print won't truncate
np.set_printoptions(threshold=sys.maxsize)

# let's alias core.find_walkable_neighbors to fwn for brevity
fwn = core.find_walkable_neighbors

BFS¶

Let's start by defining an empty 20x10 grid with start at (2, 2) and end at (20 - 3, 10 - 3)

In [89]:

polygons = []
maze, start, end = grid.generate(20,10, polygons), (2, 2), (20 - 3, 10 - 3)
path, expansion = finder.bfs(maze, fwn, start, end, with_expansion=True)

print(path)

[(2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6), (4, 6), (5, 6), (6, 6), (7, 6), (8, 6), (9, 6), (10, 6), (11, 6), (12, 6), (13, 6), (14, 6), (15, 6), (16, 6), (17, 6), (17, 7)]

To visualize our result clearer, let's print the grid, and set start to 2, and end to 3, with the path denoted by 4:

In [90]:

maze_pretty = np.copy(maze)
for coord in path:
    maze_pretty[coord[1]][coord[0]] = 4
maze_pretty[start[1]][start[0]] = 2
maze_pretty[end[1]][end[0]] = 3
print(maze_pretty)

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 0]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

As we can see above, our bfs algorithm DOES generate a correct path from start to end!

Let's try one with a square somewhere in the grid:

In [91]:

polygons = [[(14, 5), (14, 7), (16, 7), (16, 5)]]
maze, start, end = grid.generate(20,10, polygons), (2, 2), (20 - 3, 10 - 3)
path, expansion = finder.bfs(maze, fwn, start, end, with_expansion=True)

Let's visualize this, now, using a custom generate_text visualizer (viz module implementation details discussed later)

In [92]:

print(viz.generate_text(maze, start, end, path))

[[= = = = = = = = = = = = = = = = = = = =]
 [=                                     =]
 [=   S                                 =]
 [=   *                                 =]
 [=   * * * * * * * * * * * * * * * *   =]
 [=                           = = = *   =]
 [=                           =   = *   =]
 [=                           = = = E   =]
 [=                                     =]
 [= = = = = = = = = = = = = = = = = = = =]]

It looks like our algorithm worked! Indeed, the path 'shifted up' to take the polygon into account. Let's try visualizing it with the expansion path (visualized as @).

In [93]:

print(viz.generate_text(maze, start, end, path, expansion))

[[= = = = = = = = = = = = = = = = = = = =]
 [= @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ =]
 [= @ S @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ =]
 [= @ * @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ =]
 [= @ * * * * * * * * * * * * * * * * @ =]
 [= @ @ @ @ @ @ @ @ @ @ @ @ @ = = = * @ =]
 [= @ @ @ @ @ @ @ @ @ @ @ @ @ =   = *   =]
 [= @ @ @ @ @ @ @ @ @ @ @ @ @ = = = E   =]
 [= @ @ @ @ @ @ @ @ @ @ @ @ @ @         =]
 [= = = = = = = = = = = = = = = = = = = =]]

It looks like our expansion is correct! It expands the frontier until it reaches the end.

DFS¶

Now, let's try DFS

In [94]:

maze, start, end = grid.generate(20,10, polygons), (2, 2), (20 - 3, 10 - 3)
path, expansion = finder.dfs(maze, fwn, start, end, with_expansion=True)
print(viz.generate_text(maze, start, end, path))

[[= = = = = = = = = = = = = = = = = = = =]
 [=     * * * * * * * * * * * * * *     =]
 [=   S * * * * * * * * * * * * * *     =]
 [=   * * * * * * * * * * * * * * *     =]
 [=   * * * * * * * * * * * * * * * *   =]
 [=   * * * * * * * * * * * * = = = *   =]
 [=   * * * * * * * * * * * * =   = *   =]
 [=   * * * * * * * * * * * * = = = E   =]
 [=   * * * * * * * * * * * *           =]
 [= = = = = = = = = = = = = = = = = = = =]]

AHHHH!!! That path looks terrible! Is our implementation faulty?

It turns out, our implementation is indeed correct. Since depth first search traverses the deepest branches first, and since our adjacent neighbors will be given in order of bottom first, the algorithm traverses through the grid 'like a snake'.

This is easier shown than said. Let's up our visualization a bit:

In [95]:

utils.render_image(viz.generate_image(maze, start, end, path))

This shows our grid in an image. This time however, let's animate it to see the algorithm's expansion path (Note that anim generation might take a couple of seconds)

In [96]:

anim = viz.generate_anim(maze, start, end, path, expansion, frames=len(expansion))
utils.render_anim(anim, default_mode='loop')

Out[96]:

Indeed, it's shown very clearly how DFS traverses the state space. It expands until the deepest branch, which produces a clear 'snake like' effect as shown in the animation.

A*¶

Next, let's look at how A* holds up. First however, we need to define two functions, a cost and heuristic.

The cost between two neighbors is always going to be 1. Therefore we simply have a function that returns 1. (Note that we know cost function is only used for neighbors, this is NOT a general cost algorithm between two nodes).

The heuristic is a function that makes our algorithm 'expand to the target node more' - it is a function that estimates the cost of the cheapest path from node n to the goal node.

Due to this, we can simply use manhattan distance as the heuristic. Since manhattan distance returns the lowest distance between two points in a grid, this heuristic is admissible. That is to say, it never overestimates from the actual cost to the goal, so our algorithm is guaranteed to return the least-cost path.

Let's see A* in action, first without a polygon:

In [97]:

def cost(p0, p1): return 1
def md(p0, p1):
    return abs(p1[0] - p0[0]) + abs(p1[1] - p0[1])

maze, start, end = grid.generate(20,10, []), (2, 2), (15 - 3, 10 - 3)
path, expansion = finder.astar(maze, fwn, start, end, cost=cost, heuristic=md, with_expansion=True)

anim = viz.generate_anim(maze, start, end, path, expansion, frames=len(expansion))
utils.render_anim(anim, default_mode='loop')

Out[97]:

Notice how A* goes 'straight for the goal' as it were.

In [98]:

maze, start, end = grid.generate(20,10, polygons), (2, 2), (20 - 3, 10 - 3)
path, expansion = finder.astar(maze, fwn, start, end, cost=cost, heuristic=md, with_expansion=True)

anim = viz.generate_anim(maze, start, end, path, expansion, frames=len(expansion))
utils.render_anim(anim, default_mode='loop')

Out[98]:

Now that we've seen our grid search algorithms in action, let's dive in to the sample test cases.

This is a post in the CS 180 Pathfinding series.
Other posts in this series:

Mar 17, 2019 - CS 180 Pathfinding
Mar 17, 2019 - Grid
Mar 17, 2019 - Finders
Mar 17, 2019 - Grid Search
Mar 17, 2019 - Test Cases
Mar 17, 2019 - Running Test Cases
Mar 17, 2019 - Timing
Mar 17, 2019 - Viz