LAB 8
Maze Search
Depth First Search
Recursion

Due: Nov 19
Moodle
Screenshot_20181104_184118.png Screenshot_20181104_184141.png

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.

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 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:

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

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?

Day 2 start:

https://repl.it/@JimSkon/MazeDay2

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

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)

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:

Screenshot_20181104_181738.png

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:

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.

Screenshot_20181104_183057.png

Screenshot_20181104_194908.png

Moodle

Turn in a link to fully commented code.

Solution

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng Screenshot_20181103_213358.png r1 manage 13.2 K 2018-11-04 - 01:35 JimSkon  
PNGpng Screenshot_20181104_181738.png r1 manage 11.7 K 2018-11-04 - 23:17 JimSkon  
PNGpng Screenshot_20181104_183057.png r1 manage 13.9 K 2018-11-04 - 23:31 JimSkon  
PNGpng Screenshot_20181104_184118.png r1 manage 11.1 K 2018-11-04 - 23:42 JimSkon  
PNGpng Screenshot_20181104_184141.png r1 manage 17.0 K 2018-11-04 - 23:42 JimSkon  
PNGpng Screenshot_20181104_194908.png r1 manage 77.4 K 2018-11-05 - 00:49 JimSkon  
Edit | Attach | Watch | Print version | History: r11 < r10 < r9 < r8 < r7 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r11 - 2019-10-14 - JimSkon
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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