# Timing code¶

```
%reload_ext autoreload
%autoreload 2
from pathfinding import demo, grid, utils, finder
from pathfinding.grid import core, viz
cases = demo.get_case_files()
```

```
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')
```

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

```
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))
```

# 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

```
```

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