Timing code¶

In [14]:

%reload_ext autoreload
%autoreload 2

from pathfinding import demo, grid, utils, finder
from pathfinding.grid import core, viz
cases = demo.get_case_files()

In [8]:

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

for i, case in enumerate(cases):
    start, end, polygons = case
    maze = grid.generate(200, 100, polygons)

    print('Case: ', i + 1)

    print('BFS')
    %timeit -n 3 path, = finder.bfs(maze, core.find_walkable_neighbors, start, end)
    print('DFS')
    %timeit -n 3 path, = finder.dfs(maze, core.find_walkable_neighbors, start, end)
    print('A*')
    %timeit -n 3 path, = finder.astar(maze, core.find_walkable_neighbors, start, end, cost=cost, heuristic=md)
    print('\n')

Case:  1
BFS
118 ms ± 2.96 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
DFS
3.53 s ± 30.4 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
A *
227 ms ± 2.79 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)



Case:  2
BFS
121 ms ± 1.91 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
DFS
116 ms ± 3.13 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
A *
177 ms ± 3.6 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)



Case:  3
BFS
148 ms ± 1.57 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
DFS
3.52 s ± 66.9 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
A *
692 ms ± 17.9 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)



Case:  4
BFS
161 ms ± 4.1 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
DFS
364 ms ± 8.4 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
A *
463 ms ± 7.33 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)



Case:  5
BFS
186 ms ± 911 µs per loop (mean ± std. dev. of 7 runs, 3 loops each)
DFS
5.94 s ± 92 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)
A *
431 ms ± 2.69 ms per loop (mean ± std. dev. of 7 runs, 3 loops each)

Here we show/format the output as per spec (start, end, number of expanded nodes, cost and running time)

In [41]:

for i, case in enumerate(cases):
    start, end, polygons = case
    maze = grid.generate(200, 100, polygons)

    print('Case: ', i + 1)

    # demo version of finders contain the (a, b, c, d, e) output as per spec (and some functions implicitly set)
    print('BFS')
    utils.render_demo(demo.bfs(maze, start, end))
    print('DFS')
    utils.render_demo(demo.dfs(maze, start, end))
    print('A*')
    utils.render_demo(demo.astar(maze, start, end))

Case:  1
BFS
 Start:  (2, 2)
 End:  (197, 97)
 Number of Expanded Nodes:  9419
 Cost:  443
 Running time: 0.12145209312438965 seconds


DFS
 Start:  (2, 2)
 End:  (197, 97)
 Number of Expanded Nodes:  7225
 Cost:  4865
 Running time: 3.680464744567871 seconds


A*
 Start:  (2, 2)
 End:  (197, 97)
 Number of Expanded Nodes:  6767
 Cost:  443
 Running time: 0.22876715660095215 seconds


Case:  2
BFS
 Start:  (9, 7)
 End:  (174, 84)
 Number of Expanded Nodes:  9964
 Cost:  355
 Running time: 0.11522197723388672 seconds


DFS
 Start:  (9, 7)
 End:  (174, 84)
 Number of Expanded Nodes:  1374
 Cost:  1031
 Running time: 0.115264892578125 seconds


A*
 Start:  (9, 7)
 End:  (174, 84)
 Number of Expanded Nodes:  7510
 Cost:  355
 Running time: 0.17552900314331055 seconds


Case:  3
BFS
 Start:  (4, 4)
 End:  (195, 95)
 Number of Expanded Nodes:  12190
 Cost:  283
 Running time: 0.14322686195373535 seconds


DFS
 Start:  (4, 4)
 End:  (195, 95)
 Number of Expanded Nodes:  7773
 Cost:  7509
 Running time: 3.881817102432251 seconds


A*
 Start:  (4, 4)
 End:  (195, 95)
 Number of Expanded Nodes:  6000
 Cost:  283
 Running time: 0.6704928874969482 seconds


Case:  4
BFS
 Start:  (2, 2)
 End:  (195, 95)
 Number of Expanded Nodes:  12785
 Cost:  287
 Running time: 0.16221904754638672 seconds


DFS
 Start:  (2, 2)
 End:  (195, 95)
 Number of Expanded Nodes:  2364
 Cost:  2305
 Running time: 0.3908839225769043 seconds


A*
 Start:  (2, 2)
 End:  (195, 95)
 Number of Expanded Nodes:  4674
 Cost:  287
 Running time: 0.46894216537475586 seconds


Case:  5
BFS
 Start:  (2, 2)
 End:  (195, 95)
 Number of Expanded Nodes:  14786
 Cost:  287
 Running time: 0.19643592834472656 seconds


DFS
 Start:  (2, 2)
 End:  (195, 95)
 Number of Expanded Nodes:  9324
 Cost:  9317
 Running time: 5.998751878738403 seconds


A*
 Start:  (2, 2)
 End:  (195, 95)
 Number of Expanded Nodes:  4599
 Cost:  287
 Running time: 0.4391360282897949 seconds

Analysis and conclusions¶

As we can see with the above, A* and BFS always have equal cost, and they are always lower than DFS. This makes sense, as these 2 algorithms are optimal.

The running time of DFS varies quite a bit - it can get slow, or fast, depending on the graph/maze. This makes sense as DFS depends on how 'lucky' it can get in expanding to the goal node (if the goal node is near the end of the first few branches). However, note that DFS is not optimal - it's cost can be larger than the actual lowest cost to the goal.

Comparing the running time between A and BFS, we see that BFS is faster on most cases, whilst A expands way less nodes.

A* expanding less nodes makes sense, as it uses the heuristic function to 'expand in the direction' of the goal.

BFS is a bit faster due to a couple of reasons. One is that we have most starting points and endpoints at corners - this cuts the extra nodes expanded by BFS by quite a lot (imagine an example where the starting point is in the center and end point at top, BFS would expand in both directions while A* would only expand in one direction).

There also quite a few optimizations we can make for our current implementation of A*. Our A* algorithm supports arbitrary use cases, as long as it's provided a way to traverse the graph, and a cost and heuristic function. We can trade these flexibility and inline these functions, which would increase its speed. Note as well that there's no priority queue in the current implementation, and instead use a linear pass to get the node with the lowest cost.

Back to Index or look into Extra: Viz

In [ ]:

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