Description
Base Code Overview
You can find the base code here:
https://drive.google.com/a/ucsc.edu/folderview?id=0BPPiU3Ga8Z7fk5OWU40WXM0cXlMM
mJZUWhyd0NhRXl4Q0ZNWnNQSHFIN2hfbnhzTGQ3WWs&usp=sharing
p3_interactive.py
This is the interactive Tkinter driver program for this assignment. It takes three command line
arguments: an image file to display (must be a GIF), the filename of a pickled mesh data
structure (.mesh.pickle), and a subsampling factor. The subsampling factor is an integer used
to scale down large images for display on small screens.
$ python p3_interactive.py dungeonorig.gif dungeon.png.mesh.pickle 8
p3_pathfinder.py
This file is not given. You need to implement it yourself.
It should define a function called “find_path”. This function should take three arguments:
● source_point: (x,y) pair
● destination_point: (x,y) pair
● mesh: a mesh data structure (a fancy graph, described below)
The function should return two values:
● path: a list of points like ((x1,y1),(x2,y2))
● visited_nodes: a list of boxes explored by your algorithm identified by their bounds
(x1,x2,y1,y2) (this is the same as in the mesh format)
In p3_interactive.py, this is how your function will be called:
path, visited_nodes = p3_pathfinder.find_path(source_point, destination_point, mesh)
p3_meshbuilder.py
You do not need to run this program unless your Python version cannot load the
dungeon.png.mesh.pickle file we provide or you are creating a custom map.
This program can build navmeshes for userprovided images. This is the program that
produces the ‘.mesh.pickle’ files used by p3_interactive.py. “Pickle” is the name for Python’s
serialized binary data format. See the OPTIONAL steps at the end of this document for how to
make your own maps.
dungeon.png.mesh.pickle
● This is a binary data file created by p3_meshbuilder.py. You don’t need to regenerate
it.
● Once unpickled (this is done for you in p3_interative.py), this file yields a dict.
● The mesh dict has two keys: ‘boxes’ and ‘adj’.
● ‘boxes’ is a list of nonoverlapping white rectangular regions in dungeon.png. Think of
these as the nodes in a graph. Unlike in P1, your could *should* examine the structure
of these node identifiers.
● Boxes are defined by their bounds: (x1,x2,y1,y2)
● ‘adj’ is a dict the maps boxes to lists of boxes. Think of these as the edges in a graph.
Although there is a geometric relationship between boxes, a distance value is not
given in the mesh (because we don’t know which point on the border of a box you’ll be
using to enter or leave).
● For studentcreated maps, it may be the case that a box has no neighbors. However,
for the example dungeon map, every box has at least once neighbor in ‘adj’.
Suggested Workflow
● Identify the source and destination boxes. (earns 1 point)
○ Implement a trivial version of find_path() that simply returns an empty list for
the path (the first returned value) and an empty list for the collection of visited
boxes.
○ Scan through the list of boxes to find which contains the source point. Do this
as well for the destination point. Instead of returning a list indicating that you
haven’t visited any boxes, return a list of these two boxes.
● Implement the simplest completesearch algorithm you can. (earns 1 point)
○ Starting with the source box, run breadthfirst search looking for a gain of boxes
that reaches the destination box. If no such path can be found, make sure your
program can report this correctly (such as by printing out “No path!” in the
console). To earn the point, the “No path!” message needs to only show when
there really isn’t a path. Complete search algorithms buy us the ability to report
this confidently.
● Modify your simple search to compute a legal list of line segments
demonstrating the path. (earns 1 point)
○ Instead of doing your search purely at the box level, add an extra table (dict) to
keep track of the precise x,y position within that box that your path with
traverse. In the solution code, we call this table ‘detail_points’, a dictionary the
maps boxes to (x,y) pairs.
○ When considering a move from one box to another, copy the x,y position within
the current box and the constraint it (with mins and maxes) to the bounds of the
destination box. Use the Euclidean distances between these two points as the
length of the edge in the graph you are exploring (not the distance between the
midpoints of the two boxes).
○ When the search terminates (assuming it found a path), construct a list of line
segments to return by looking up the detail points for each box along the path.
In this assignment, the order of the line segments is not important. What
matters is that the line is legal by visual inspection of the visualization it
produces (see below).
● Modify your simple search to implement Dijkstra’s algorithm. (earns 1 point)
○ If you have already implemented an algorithm better than Dijkstra’s (such as A*
or bidirectional Dijkstra’s or bidirectional A*, skip this step.
○ If you were previously using a distanceignoring algorithm like BFS, upgrade it
to Dijkstra’s now. As in P1, this will probably involve using the heapq Python
module. Alternatively, you can use the PriorityQueue code that some students
have discovered referenced in the A* reading by Amit Patel.
○ After this change, your program should be producing nearoptimal paths. The
paths will not be precisely optimal because the structure of the navmesh
structurally disallows certain paths. For the example dungeon map, however,
your algorithm should always be choosing the right path at the scale of rooms
and hallways. Because of the box decomposition, the not every small
passageway will be actually passable (check the region atlas
dungeon.png.mesh.png to see how the boxes were formed).
● Modify your Dijkstra’s implementation into an A* implementation. (earns 1 point)
○ Find the part of your code where you are putting new boxes into the priority
queue.
○ Instead of using the new distance (distance to u plus length of edge uv) as the
priority for insertion, augment (add to) this with an estimate of the distance
remaining. If you already produced a helper function to measure the Euclidean
distance between two detail points, you can use this function to measure the
distance between the new detail point and the final destination point.
○ When you are dequeuing boxes from the priority queue, remember that their
priority value is not a distance. You’ll have to recover the true distance to the
justdequeued box by looking it up in your distance table.
○ To make sure A* is implemented correctly, try to find a path along a straight
vertical or horizontal hallway. The A* algorithm should mostly visit boxes
between the two points. Dijkstra’s however, will also explore in the opposite
direction of the destination point up to the radius at which it found the
destination. In the example dungeon map, there is a nice vertical hallway just
outside of the circular chamber at the topright.
● Modify your Dijkstra’s (or A*) into a bidirectional Dijkstra’s (or bidirectional A*).
(earns 1 last point)
○ Make a copy of the code you have working now for reference.
○ Where you had tables recording distances and previous pointers (‘dist’ and
‘prev’), make copies for each direction of the search (‘forward_prev’ and
‘backward_prev’). Don’t, however, duplicate the queue.
○ Find the part of your code where you put the source box into the priority queue.
○ Instead of just enqueuing the source box, also enqueue the destination box
(which will be used to start the backwards part of the bidirectional search). In
order to distinguish the two portions of the search space, instead of just
enqueuing boxes, you should also indicate which goal you are seeking.
○ Example:
■ heappush( (0, source_box, ‘destination’) )
■ priority, curr_box, curr_goal = heappop(queue)
○ Modify the rest of your queue operations to use this extra representation that
keeps track of the goal. Use the goal to decide which set of ‘dist’ and ‘prev’
tables to check and update.
○ If you are implementing bidirectional A*, change which point you are using as
an estimate based on the stated goal you dequeued. This strategy is called
fronttoback bidirectional A*. (Fronttofront bidirectional A* measures the
distance to the closest point on the opposite frontier it’s more complex than
you need here.)
○ Instead of terminating the search when you dequeue the destination box, stop
EVEN EARLIER when the justdequeued node is known in the table of
previous pointers for the other search direction. In other words, stop when
either direction of search encounters territory already seen by the other
direction.
○ Adjust your final path reconstruction logic to build segments from both parts of
the path your algorithm discovered.
Modify your bidirectional Dijkstra’s into bidirectional A*. (no extra points)
● If you haven’t already, try combining bidirectional search with A*. If you have this
version of your program running, you’ll be able to demonstrate all aspects of your
program at once without having to swap which search algorithm you are using.
● Note: You can earn full credit without doing this. Further, if you aim for this variation
too early on, you might get lost. The suggested workflow above has lots of safe places
where you can be sure you’ve earned points without losing them later.
Grading Criteria
Each bulleted item receives equal weight:
● Are the mesh boxes containing the source and destination points identified?So
long as these both show up in the set of visited boxes that your algorithm returns, you
are good. Beyond this, whether the set of visualized boxes represents boxes you have
actually dequeued or the larger set of boxes you have enqueued is up to you.
● When there is no path, can the program identify this state and report it? Printing
text in the command line is fine.
● Where there is a path, is it found an drawn in a legal manner? Legal means
forming a single connected polyline from the source to destination point that never
veers outside of the bounds of mesh box contained within the set of visited boxes.
● Is Dijkstra’s algorithm (or better) implemented correctly?
● Is the A* algorithm (or better) implemented correctly?
● Is a bidirectional search algorithm (or better) implemented correctly?
We will still accept your algorithms if they make nonoptimal choices on the last step or the
step that joins the two directions of bidirectional search. Terminating the search as soon as
you reach (dequeue) the destination node / a node from the opposite direction of search is
sufficient. We mainly care that your algorithm does not visit boxes unnecessarily, so small
errors in precise path length don’t matter.
Creating a Custom Map (OPTIONAL)
Here’s how to create your own test map:
STEP 1:Find some image that you think will be easy to turn into a blackandwhite occupancy
map. Save it as a GIF file. p3_interactive can only display GIF files.
ucsc_banana_slugorig.gif
STEP 2:In your favorite photo editor, create a blackandwhite version (e.g. by desaturating
and then applying brightness and contrast operators). Save this in a lossless format like PNG.
ucsc_banana_slug.png
STEP 3: Run the navmesh builder program. You must have SciPy (http://www.scipy.org/)
installed for this program to work.
$ python p3_meshbuilder.py ucsc_banana_slug.png
Built a mesh with 711 boxes.
This will produce two files. The first is the mesh as a pickled Python data structure:
ucsc_banana_slug.png.mesh.pickle. The second is a visualization of the rectangular polygons
extracted by the navmesh builder:
ucsc_banana_slug.png.mesh.png.
STEP 4:Run your pathfinding program giving the original GIF file, the pickled mesh data, and
some subsampling factor. A factor of 1 displays the image at original size, while a factor of 4
will scale the image down by a factor of four in each dimension for display (pathfinding will still
be done at the full resolution).
$ python p3_interactive.py ucsc_banana_slugorig.gif \
ucsc_banana_slug.png.mesh.pickle 1