P1: Dijkstra’s in a Dungeon

CMPM 244

Overview

In this programming exercise, you will analyze the reachability between waypoints in an ASCII-art dungeon map. Using Dijkstra’s shortest path algorithm (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) you will find and display a shortest path or confirm that paths exists.

Practice goals:

• Loading ASCII-art maps in Python
• Interpreting a grid as a graph, lazily
• Implementing a graph search algorithm
• Creating a command-line tool that can answer design queries with visual feedback (text for now)

Reference

https://www.redblobgames.com/pathfinding/a-star/introduction.html

​

Dungeon map representation

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

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.*.X.d.X.**.X

X.......X...X...X....X

XXXXXXXXXXXXXXXXXXXXXX

​

Input

Output showing path from c to e

Impassable wall

Free space

Named waypoint

​

Example step

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” and “waypoints” 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.

​

• Create a program that will randomly generate a dungeon map design (including waypoints, spaces, and walls). Interpret “dungeon” however you like.

Solution sketch

def load_level(filename: str) :

…

return {

'walls': …, # set of cells� 'spaces': …, # set of cells� 'waypoints': …, # dict str->cell}

​

def show_level(level, path=None):

…

return … # printable string repr

​

def navigation_edges(level, cell):

…

return … # dict cell->float (cost)

​

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

…

return … # list of cells or None

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)

​

Cells can be represented by integer pairs (i,j).

​

The function adj accepts a graph (level) and a cell, and it returns a dictionary mapping adjacent cells to the distance required to reach those cells (with up to 8 entries).

​

Use heappush and heappop from Python’s heapq module to model the priority queue in Dijkstra’s algorithm.

Using the heapq module

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 == []

​

Grading criteria

[1pt] Can filenames and waypoints be changed easily enough to demonstrate functionality?

[1pt] Does the algorithm perform correctly when there exists a path?

[1pt] Does the algorithm perform correctly when no path is possible?

[1pt] Do the paths returned appear to actually be shortest paths?

[3pts] Upon inspection of the code, does it appear correctly implement Dijkstra’s algorithm on an implicitly represented graph (where the adjacency is computed as needed)?

[1pt] Upon inspection of the code, is early termination implemented?

[1pt] Was a new and interesting example map created?

[1pt] Was a map generator created?

​

​

When you demonstrate your solution in office hours, have the level design from slide 3 in a file like “example.txt”