## Description

Objectives

● Revisit your past knowledge of Dijkstra’s shortest path algorithm.

● Practice building the graph to be searched on the fly.

● Practice using Python’s highlevel data structures such as lists and dicts.

● Understand the ASCIIart dungeon map format that we’ll be using throughout the

quarter.

Requirements

● Implement a function to compute the adjacent cells to a given cell on the level map. It

should allow movement in 8 directions on the grid, including the diagonals. The cost

for horizontal and vertical moves should be 1. The cost for diagonal moves should be

sqrt(2). (Find sqrt in the Python math module). Movement should only allowed

between “spaces” in the level file (not “walls”).

● Implement a version of Dijkstra’s shortest path algorithm between a given pair of cells,

returning the path (including the source and destination cells). The algorithm should

stop searching as soon as the destination cell is found (not exploring the whole graph

if it is not needed). If no path is possible, the algorithm should explicitly signal this (by

returning None, an empty path, or raising an appropriately named exception).

● Create the top level logic of your program so that you can demonstrate your algorithm

on any given map file and pair of waypoints. It should be possible to change these

values either via command line arguments or changing a single line of code.

● Create your own interesting map that is larger than the example map, and be prepared

to show us why that map is interesting. (Does it test edge cases of your algorithm? Is it

based on a map you’ve seen elsewhere?) Have fun being a level designer.

Grading Criteria

(equal weight for each question)

● Can filenames and waypoints be changed easily enough to demonstrate functionality?

● Does the algorithm perform correctly when there exists a path?

● Does the algorithm perform correctly when no path is possible?

● Do the paths returned appear to actually be shortest paths?

● Upon inspection of the code, does it appear correct? (This includes computing the

graph on the fly.)

● Upon inspection of the code, is early termination implemented?

● Was a new and interesting example map created?

Code Sketch

Download the p1_support module here:

https://drive.google.com/a/ucsc.edu/file/d/0BPPiU3Ga8Z7Rk1RTGo5eHpseUU/view?usp=sh

aring

Download this example code here:

https://drive.google.com/a/ucsc.edu/file/d/0BPPiU3Ga8Z7bXJVNXVSeWcwOGs/view?usp=s

haring

from p1_support import load_level, show_level

from math import sqrt

from heapq import heappush, heappop

def dijkstras_shortest_path(src, dst, graph, adj):

raise NotImplementedError

def navigation_edges(level, cell):

raise NotImplementedError

def test_route(filename, src_waypoint, dst_waypoint):

level = load_level(filename)

show_level(level)

src = level[‘waypoints’][src_waypoint]

dst = level[‘waypoints’][dst_waypoint]

path = dijkstras_shortest_path(src, dst, level, navigation_edges)

if path:

show_level(level, path)

else:

print “No path possible!”

if __name__ == ‘__main__’:

import sys

_, filename, src_waypoint, dst_waypoint = sys.argv

test_route(filename, src_waypoint, dst_waypoint)

References

● https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

○ Suggested differences from the pseudocode from Wikipedia:

■ Skip the entire initialization loop, instead use dicts:

● “dist = {}” and “dist[state] = better_distance”

● “prev = {}” and “prev[state2] = state1”

■ Because dist will not be defined for unvisited states, the expression “alt

< dist[v]” must be implemented as “v not in dist or alt < dist[v]” or “alt <
dist.get(v,alt+1)”.
■ Use Python’s heapq module to implement the priority queue. The queue
will simply be a Python list containing tuples (distanceandstate pairs),
but you’ll use the heapq library to add and remove elements from it.
https://docs.python.org/2/library/heapq.html
■ Instead of returning the “dist” and “prev” tables (dicts), recover a specific
shortest path and return it instead. Represent it as a list of states that
starts with the source state and ends with the destination state.
● A similar IPython Notebook implementation for breadthfirst search (BFS):
○ http://nbviewer.ipython.org/urls/dl.dropbox.com/s/7oo0eu4e0p6fwl4/BFS%20Ex
ample.ipynb
● The depthfirst search (DFS) code we developed live in class:
https://drive.google.com/a/ucsc.edu/file/d/0BPPiU3Ga8Z7ZlEwbEhtZjNTUGs/view?us
p=sharing
● Using heapq for priority queue operations:
from heapq import heappush, heappop
queue = [] # Just a plain list
heappush(queue, (2, 'a')) # enqueuing some pairs
heappush(queue, (42,'b'))
heappush(queue, (1, 'c'))
p1, x1 = heappop(queue) # dequeuing some pairs
p2, x2 = heappop(queue)
p3, x3 = heappop(queue)
assert [x1, x2, x3] == ['c','a','b']
assert [p1, p2, p3] == [1, 2, 42]
assert queue == []
Example Level File (example.txt)
XXXXXXXXXXXXXXXXXXXXXX
X....................X
X..a..............b..X
X...............X....X
XXXXXXXXXX..XXXXX..XXX
X...............X....X
X...............X.XX.X
X........XXXXXXXX....X
X.......X...X...X.XXXX
X.......X.e.X.d.X..c.X
X.......X...X...X....X
XXXXXXXXXXXXXXXXXXXXXX
The “load_level” function provided in the “p1_support” module returns a dictionary:
from p1_support import load_level
level = load_level('example.txt')
level.keys() # > [‘walls’, ‘spaces’, ‘waypoints’]

level[‘walls’] # > {(0, 0): ‘X’, (0, 1): ‘X’, (0, 2): ‘X’, (0, 3): ‘X’, … }

level[‘spaces’] # > {(7, 3): ‘.’, (6, 9): ‘.’, (12, 1): ‘.’, … }

level[‘waypoints’] # > {‘a’: (3, 2), ‘b’: (18, 2), ‘c’: (19, 9), …}