Recursion Visualization Using Python Turtle Module

# The Three Laws of Recursion 
# 1. A recursive algorithm must have a base case.
# 2. A recursive algorithm must change its state and move toward the base case.
# 3. A recursive algorithm must call itself, recursively.

import turtle

myTurtle = turtle.Turtle()
myWin = turtle.Screen()

# Recursion Visualization
# Draw Spiral
def drawSpiral(myTurtle, lineLen):
  if lineLen > 0:
    myTurtle.forward(lineLen)
    myTurtle.right(90)
    drawSpiral(myTurtle, lineLen - 5)
    
# Draw Sierpinski   
def drawTriangle(points, color, myTurtle):
  myTurtle.fillcolor(color)
  myTurtle.up()
  myTurtle.goto(points[0][0], points[0][1])
  myTurtle.down()
  myTurtle.begin_fill()
  myTurtle.goto(points[1][0], points[1][1])
  myTurtle.goto(points[2][0], points[2][1])
  myTurtle.goto(points[0][0], points[0][1])
  myTurtle.end_fill()
  
def getMid(p1, p2):
  return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
  
def sierpinski(points, degree, myTurtle):
  colormap = ['blue', 'red', 'green', 'white', 'yellow', 'violet', 'orange']
  
  drawTriangle(points, colormap[degree], myTurtle)
  if degree > 0:
    sierpinski(
      [points[0], getMid(points[0], points[1]), getMid(points[0], points[2])], 
      degree - 1,
      myTurtle)
    sierpinski(
      [points[1], getMid(points[0], points[1]), getMid(points[1], points[2])], 
      degree - 1,
      myTurtle)
    sierpinski(
      [points[2], getMid(points[2], points[1]), getMid(points[0], points[2])], 
      degree - 1,
      myTurtle)      

# Maze
PART_OF_PATH = 'O'
TRIED = '.'
OBSTACLE = '+'
DEAD_END = '-'

class Maze:
  def __init__(self, mazeFileName):
    rowsInMaze = 0 
    columnsInMaze = 0
    self.mazelist = []
    mazeFile = open(mazeFileName, 'r')
    for line in mazeFile:
      rowList = []
      col = 0
      for ch in line[:-1]:
        rowList.append(ch)
        if ch == 'S':
          self.startRow = rowsInMaze
          self.startCol = col
        col += 1
      rowsInMaze += 1
      self.mazelist.append(rowList)
      columnsInMaze = len(rowList)
    
    self.rowsInMaze = rowsInMaze
    self.columnsInMaze = columnsInMaze
    self.xTranslate = -columnsInMaze / 2
    self.yTranslate = rowsInMaze / 2
    self.t = turtle.Turtle()
    self.t.shape('turtle')
    self.wn = turtle.Screen()
    self.wn.setworldcoordinates(
      -(columnsInMaze-1)/2-.5, 
      -(rowsInMaze-1)/2-.5,
      (columnsInMaze-1)/2+.5,
      (rowsInMaze-1)/2+.5)
      
  def drawMaze(self):
    self.t.speed(10)
    self.wn.tracer(0)
    for y in range(self.rowsInMaze):
      for x in range(self.columnsInMaze):
        if self.mazelist[y][x] == OBSTACLE:
          self.drawCenteredBox(x+self.xTranslate, -y+self.yTranslate, 'orange')
      
    self.t.color('black')
    self.t.fillcolor('blue')
    self.wn.update()
    self.wn.tracer(1)
    
  def drawCenteredBox(self, x, y, color):
    self.t.up()
    self.t.goto(x-.5, y-.5)
    self.t.color(color)
    self.t.fillcolor(color)
    self.t.setheading(90)
    self.t.down()
    self.t.begin_fill()
    for i in range(4):
      self.t.forward(1)
      self.t.right(90)
    self.t.end_fill()
    
  def moveTurtle(self, x, y):
    self.t.up()
    self.t.setheading(self.t.towards(x+self.xTranslate, -y+self.yTranslate))
    self.t.goto(x+self.xTranslate, -y+self.yTranslate)
    
  def dropBreadcrumb(self, color):
    self.t.dot(10, color)
    
  def updatePosition(self, row, col, val = None):
    if val:
      self.mazelist[row][col] = val
    self.moveTurtle(col, row)
    
    if val == PART_OF_PATH:
      color = 'green'
    elif val == OBSTACLE:
      color = 'red'
    elif val == TRIED:
      color = 'black'
    elif val == DEAD_END:
      color = 'red'
    else:
      color = None
    
    if color:
      self.dropBreadcrumb(color)
      
  def isExit(self, row, col):
    return (
      row == 0 or 
      row == self.rowsInMaze - 1 or 
      col == 0 or 
      col == self.columnsInMaze-1)
      
  def __getitem__(self, idx):
    return self.mazelist[idx]
    
    
def searchFrom(maze, startRow, startColumn):
  # try each of four directions from this point until we find a way out.
  # base case return values:
  # 1. we have run into an obstacle, return False
  maze.updatePosition(startRow, startColumn)
  if maze[startRow][startColumn] == OBSTACLE:
    return False
  # 2. we have found a square that has already been explored
  if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:
    return False
  # 3. we have found an outside edge not occupied by an obstacle
  if maze.isExit(startRow, startColumn):
    maze.updatePosition(startRow, startColumn, TRIED)
    return True
  maze.updatePosition(startRow, startColumn, TRIED)
  
  # Otherwise, use logical short circuiting to try each direction in turn (if needed)
  found = searchFrom(maze, startRow-1, startColumn) or \
          searchFrom(maze, startRow+1, startColumn) or \
          searchFrom(maze, startRow, startColumn-1) or \
          searchFrom(maze, startRow, startColumn+1)
  if found:
    maze.updatePosition(startRow, startColumn, PART_OF_PATH)
  else:
    maze.updatePosition(startRow, startColumn, DEAD_END)
  
  return found
  
  
# maze.txt format example
# ++++++++++++++++++++++
# +   +   ++ ++     +
# + +   +       +++ + ++
# + + +  ++  ++++   + ++
# +++ ++++++    +++ +  +
# +          ++  ++    +
# +++++ ++++++   +++++ +
# +     +   +++++++  + +
# + +++++++      S +   +
# +                + +++
# ++++++++++++++++++ +++
  

def main():
  # Recursion Visualization
  # Spiral
  #drawSpiral(myTurtle, 100)
  #myWin.exitonclick()
  
  # Sierpinski
  #myPoints = [[-100, -50], [0, 100], [100, -50]]
  #sierpinski(myPoints, 3, myTurtle)
  #myWin.exitonclick()
  
  # Maze
  myMaze = Maze('maze.txt')
  myMaze.drawMaze()
  myMaze.updatePosition(myMaze.startRow, myMaze.startCol)
  
  searchFrom(myMaze, myMaze.startRow, myMaze.startCol)
  
  
main()