Put your work for this problem in a file called hwk5.py.
The function solvemaze(...) we wrote in Lecture 11 finds a path from the start of a maze to its goal. These two points are stored as attributes of a Maze instance.
One could just as well ask for a route between any two points in a maze, and your task for this problem is to modify solvemaze(...) in order to make a new function that does exactly that.
Specifically, write and submit a new function (still recursive) based on solvemaze that has the following definition line and which does as the docstring says.
def maze_path(M,p,q,path=None):
"""
Use recursion with backtracking to find a path in `Maze`
object `M` from point `p` to point `q` (both are `Point2`
objects). If `path` is given, it should be a list of
points beginning with `p`, and the search will only look
for paths that extend this list.
Points `p` and `q` must be free squares in the maze. If
either is wall, this function raises ValueError since the
question does not make sense.
Returns the path that is found, or if no such path exists,
returns `None`.
Does not modify `M` at all.
"""
I recommend you do this by starting with the code in the body of solvemaze and making a few changes.
# Basically, this is depth_first_maze_solution
# but we replace M.start with p and M.goal with q
def maze_path(M,p,q,path=None):
"""
Use recursion with backtracking to find a path in `Maze`
object `M` from point `p` to point `q` (both are `Point2`
objects). If `path` is given, it should be a list of points
beginning with `p`, and the search will only look for paths
that extend this list.
Points `p` and `q` must be free squares in the maze. If
either is wall, this function raises ValueError since the
question does not make sense.
Returns the path that is found, or if no such path exists,
returns `None`.
Does not modify `M` at all.
"""
if path == None:
# no path given, begin at p
path = [p]
if path[-1] == q:
# path reached q, so we're done
return path
# enumerate possible next steps
possible_next = M.free_neighbors(path[-1])
# then remove any places we've already been
possible_next = [x for x in possible_next if x not in path]
# consider next steps
for next_step in possible_next:
new_path = path + [next_step]
res = maze_path(M, p, q, new_path)
if res: # if res is a nonempty list, i.e. not None
# res is in fact a solution; return it
return res
# no possible next step worked out
return None
Put your work for this problem in the same file as the last problem, hwk5.py.
Suppose we have a maze that is like the random mazes generated by PrimRandomMaze in the sense that there is exactly one path between any two points $p$ and $q$ that are not walls. If you subtract one from the length of that path, the result is called the path distance between $p$ and $q$ which is denoted by $dist(p,q)$. Subtracting one ensures that $dist(p,p)=0$ and that $dist(p,q)=1$ if $p$ and $q$ are neighbors.
If $x$ is one of the points on the path from $p$ to $q$, then $dist(p,x) + dist(x,q) = dist(p,q)$. This reflects the fact that you can stop at $x$ on your way from $p$ to $q$ without making any detour. For a general point $x$, the quantity $$ dist(p,x) + dist(x,q) - dist(p,q) $$ tells you the detour distance of $x$ during a trip from $p$ to $q$, meaning the minimum additional distance you would need to add to your trip from $p$ to $q$ in order to stop at $x$.
Write a function
def maze_detour_dist(M,p,q,x):
that takes a maze M and Point2 objects p,q,x that are free locations (not walls) of M, and which computes and returns the detour distance of x during a trip from p to q.
You can (and should) use the function maze_path from problem 2 to do this. Even if you don't get the function to work in problem 2, we'll evaluate your answer to this problem on the basis of whether it works when a correct maze_path function is provided.
def dist(M,p,q):
"""
For a maze M with unique paths between any two free
squares, return the number of steps (i.e. path length
minus one) one must take to travel from `p` to `q`.
"""
return len(maze_path(M,p,q))-1
def maze_detour_dist(M,p,q,x):
"""
Additional path length required to stop at `x` on the
way from `p` to `q`, compared with making a direct trip,
assuming all of this is done while navigation maze `M`
which has unique paths between any two free squares.
"""
return dist(M,p,x) + dist(M,x,q) - dist(M,p,q)