In [1]:
%reload_ext autoreload
%autoreload 2
from pathfinding import demo, grid, utils, finder
from pathfinding.grid import core, viz
In [5]:
cases = demo.get_case_files()
In [6]:
start, end, polygons = cases[0]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.bfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
In [21]:
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[21]:
In [22]:
start, end, polygons = cases[1]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.bfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
In [23]:
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[23]:
In [24]:
start, end, polygons = cases[3]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.bfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
In [25]:
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[25]:
In [26]:
start, end, polygons = cases[4]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.bfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
In [27]:
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[27]:
DFS¶
In [29]:
start, end, polygons = cases[0]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.dfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[29]:
In [30]:
start, end, polygons = cases[1]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.dfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[30]:
In [31]:
start, end, polygons = cases[2]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.dfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[31]:
In [32]:
start, end, polygons = cases[3]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.dfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[32]:
In [33]:
start, end, polygons = cases[4]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.dfs(maze, core.find_walkable_neighbors, start, end, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[33]:
A*¶
In [34]:
def cost(p0, p1): return 1
def md(p0, p1):
return abs(p1[0] - p0[0]) + abs(p1[1] - p0[1])
start, end, polygons = cases[0]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.astar(maze, core.find_walkable_neighbors, start, end, cost=cost, heuristic=md, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[34]:
In [35]:
start, end, polygons = cases[1]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.astar(maze, core.find_walkable_neighbors, start, end, cost=cost, heuristic=md, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[35]:
In [36]:
start, end, polygons = cases[2]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.astar(maze, core.find_walkable_neighbors, start, end, cost=cost, heuristic=md, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[36]:
In [37]:
start, end, polygons = cases[3]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.astar(maze, core.find_walkable_neighbors, start, end, cost=cost, heuristic=md, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[37]:
In [38]:
start, end, polygons = cases[4]
maze = grid.generate(200, 100, polygons)
path, expansion = finder.astar(maze, core.find_walkable_neighbors, start, end, cost=cost, heuristic=md, with_expansion=True)
utils.render_image(viz.generate_image(maze, start, end, path))
utils.render_anim(viz.generate_anim(maze, start, end, path, expansion))
Out[38]:
Let's now jump to timing and conclusions
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