Difference: MazeSearchRecursion (9 vs. 10)

Revision 102019-04-15 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="IntroToCSF2018"

LAB 8Maze SearchDepth First SearchRecursion

Changed:
<
<
>
>

Goal

Using recursion to solve a maze.

Part 1 - Make 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?

Part 2 - Random Walk

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.

`<-- SyntaxHighlightingPlugin -->`
```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()```
`<-- end SyntaxHighlightingPlugin -->`

We want to be able to start from a point on the matrix, and put a "*" there. from ther we move either to the right, up, left, or down, and put the next "*". In thi way we "walk" across the matric, 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:

`<-- SyntaxHighlightingPlugin -->`
```def goDir(dir,r,c):
"given U, R. D, L, return the coordinates for that cell"
if dir=="U":
return r-1,c
elif dir=="R":
return r,c+1
elif dir=="D":
return r+1,c
elif dir=="L":
return r,c-1
else:
print("goDir error:",dir)
return r,c```
`<-- end SyntaxHighlightingPlugin -->`

Now write code to start from a point, and "walk" a random path:

`<-- SyntaxHighlightingPlugin -->`
```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)```
`<-- end SyntaxHighlightingPlugin -->`

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?

Part 3 - Random walk the Maze

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

`<-- SyntaxHighlightingPlugin -->`
```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 r-1,c
elif dir=="R":
return r,c+1
elif dir=="D":
return r+1,c
elif dir=="L":
return r,c-1
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)```
`<-- end SyntaxHighlightingPlugin -->`

What's the problem with this solution?

End of Day 2: https://repl.it/@JimSkon/MakeMazeDay2

Part 4 - A depth first search using recursion

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:

Part 5 - Marking the path

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:

`<-- SyntaxHighlightingPlugin -->`
```R = '\033[31m' # red
X = '\033[0m' # reset
```
`<-- end SyntaxHighlightingPlugin -->`

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.

Moodle

Turn in a link to fully commented code.

 META FILEATTACHMENT attachment="Screenshot_20181103_213358.png" attr="" comment="" date="1541295330" name="Screenshot_20181103_213358.png" path="Screenshot_20181103_213358.png" size="13495" user="JimSkon" version="1" attachment="Screenshot_20181104_181738.png" attr="" comment="" date="1541373476" name="Screenshot_20181104_181738.png" path="Screenshot_20181104_181738.png" size="11946" user="JimSkon" version="1" attachment="Screenshot_20181104_183057.png" attr="" comment="" date="1541374288" name="Screenshot_20181104_183057.png" path="Screenshot_20181104_183057.png" size="14223" user="JimSkon" version="1" attachment="Screenshot_20181104_184118.png" attr="" comment="" date="1541374963" name="Screenshot_20181104_184118.png" path="Screenshot_20181104_184118.png" size="11391" user="JimSkon" version="1" attachment="Screenshot_20181104_184141.png" attr="" comment="" date="1541374963" name="Screenshot_20181104_184141.png" path="Screenshot_20181104_184141.png" size="17446" user="JimSkon" version="1" attachment="Screenshot_20181104_194908.png" attr="" comment="" date="1541378964" name="Screenshot_20181104_194908.png" path="Screenshot_20181104_194908.png" size="79219" user="JimSkon" version="1"

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback