LAB 8

Using recursion to solve a maze.
Consider the Maze above. Can you find a path from the S to the E? Try it and come up with a written set of instructions on how you do it.
Can we write a program to do this?
Consider the following repl.it that generates a random maze like the one above: https://repl.it/@JimSkon/MakeMaze
Note that the maze generating has the maze code in a separate file, makemaze.py.
Play around with the program. the command maze=createMaze(16,8,2) creates a maze. What do the parameters?
How can we try to make a program to solve a given maze? Let's start out with a random walk.
The following code creates a matrix of "." (periods). And prints it. Try it out. Make sure you understand it.
def makeMatrix(h,w): "Make a h,w matrix of spaces" m=[] row=["."]*w for i in range(h): m.append(row[:]) return(m) def printMatrix(maze): "Print out a maze" for i in range(len(maze)): for j in range(len(maze[i])): print(maze[i][j],end="") print()
We want to be able to start from a point on the matrix, and put a "*" there. from there we move either to the right, up, left, or down, and put the next "*". In this way we "walk" across the matrix, making a path. We need to be able to pick a random direction, and go that way. How can we do that?
Now consider code to take a position (row, column) in the grid, and a direction "U","R","D","L", and return a row and column. See how it works in repl.it:
def goDir(dir,r,c): "given U, R. D, L, return the coordinates for that cell" if dir=="U": return r1,c elif dir=="R": return r,c+1 elif dir=="D": return r+1,c elif dir=="L": return r,c1 else: print("goDir error:",dir) return r,c
Now write code to start from a point, and "walk" a random path:
def randomWalk(m,r,c,steps): "Random walk through a matrix" "m is the matrix, r,c are where to start" "Steps  how many steps to take" # Pick a random direction # and set r, c to the new location # and put a "*" m[r][c]="*" printMatrix(m) for i in range(steps): # Pick a random direction # and set r, c to the new location # and put a "* printMatrix(m) w=20 h=20 mat = makeMatrix(w,h) randomWalk(mat,10,10,100)
Finish the function, and try it with increasing values for the number of steps. What happens when you get to the edge of the the matrix, and go over it?
https://repl.it/@JimSkon/MazeDay2
Let's try to random walk an actual maze. We can start with a fork of: https://repl.it/@JimSkon/MakeMaze
What you will need to do is create a maze. Set the start location to the "S" in the maze (1,1). Write a function
from makemaze import createMaze import random def goDir(dir,r,c): "given U, R. D, L, return the coordinates for that cell" if dir=="U": return r1,c elif dir=="R": return r,c+1 elif dir=="D": return r+1,c elif dir=="L": return r,c1 else: print("goDir error:",dir) return r,c def printMaze(maze): "Print out a maze" for i in range(len(maze)): for j in range(len(maze[i])): print(maze[i][j],end="") print() def isOpen(maze,r,c): "return true if r,c is open (space)" def isEnd(maze,r,c): "return true if r,c is the end (E)" def randomWalk(maze): r=1 c=1 dirs=getDirs(maze,r,c) while len(dirs)>0: # while there is a open adjacent space # pick a direction # go in that direction (place a "." there) # print the update maze # stop is you have nowhere to go, or reach the "E" maze=createMaze(10,10,1) printMaze(maze) randomWalk(maze) printMaze(maze)
What's the problem with this solution?
End of Day 2: https://repl.it/@JimSkon/MakeMazeDay2
Let's try something else. Image you have a loaf of bread. Before moving that way you set down a piece of bread so you remember where you have been. You pick an open direction (a way without a wall or a piece of bread) and go that way. You then do the same thing again, you put down a piece of bread, pick an open direction, and go that way. The bred keeps you from doubling back. eventually you reach a dead end. At this point you follow the bread along the way you came, until you see an open direction, and then explore that way. This later process is know of as "backtracking". Along the way, you keep you eye out for a "E", and if you find it, you have succeeded. If you don't, eventually you will have searched everywhere, and you declare the maze "unsolvable".
Consider the following algorithm for arecursive Depth First Search (DFS)
DFS(maze,row,col) If maze[row][column] is an "E" return True If maze[row][column] is not a space or "S" return False maze[row][column] = "." for each direction dir in (U,R,D,L) if DFS(maze,newr,newc) return True return false
Try this algorithm out a few times.
Write the DFS algorithm in your maze program, and get it working. You will end up with something like this:
Look at the solved Maze above. Notice how it includes false as well as successful paths. How can we see the actual path the led to the end? What if as you "return" back, at each level, place a different color marker?
Do the following, when you find the "E", before you return, change the "." below you to red. How can we do this? Following two character codes will help:
R = '\033[31m' # red X = '\033[0m' # reset
The string R will change subsequent letters to red, and the string X will change back to what it was (there are other color codes here: http://www.siafoo.net/snippet/88 )
If you replace the "." with R+"."+X, it will be leave a trail of red periods as you return to the beginning.
Turn in a link to fully commented code.
I  Attachment  History  Action  Size  Date  Who  Comment 

png  Screenshot_20181103_213358.png  r1  manage  13.2 K  20181104  01:35  JimSkon  
png  Screenshot_20181104_181738.png  r1  manage  11.7 K  20181104  23:17  JimSkon  
png  Screenshot_20181104_183057.png  r1  manage  13.9 K  20181104  23:31  JimSkon  
png  Screenshot_20181104_184118.png  r1  manage  11.1 K  20181104  23:42  JimSkon  
png  Screenshot_20181104_184141.png  r1  manage  17.0 K  20181104  23:42  JimSkon  
png  Screenshot_20181104_194908.png  r1  manage  77.4 K  20181105  00:49  JimSkon 