SHARE
TWEET

Untitled

a guest Feb 26th, 2020 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Backtracking Maze - DFS
  2.  
  3. import turtle
  4. from random import randint
  5. from time import sleep
  6.  
  7. class Stack:
  8.     def __init__(self):
  9.         self.items = []
  10.  
  11.     def isEmpty(self):
  12.         return self.items == []
  13.  
  14.     def push(self, item):
  15.         self.items.append(item)
  16.  
  17.     def pop(self):
  18.         return self.items.pop()
  19.  
  20.     def peek(self):
  21.         return self.items[len(self.items)-1]
  22.  
  23.     def size(self):
  24.         return len(self.items)
  25.  
  26. screen = turtle.Screen()
  27. myPen = turtle.Turtle()
  28. screen.tracer(0)
  29. myPen.speed(0)
  30. myPen.hideturtle()
  31.  
  32.  
  33. def text(message, x, y, size):
  34.     FONT = ('Arial', size, 'normal')
  35.     myPen.penup()
  36.     myPen.goto(x, y)
  37.     myPen.write(message, align="left", font=FONT)
  38.  
  39.  
  40. # This function draws a box by drawing each side of the square and using the fill function
  41. def box(intDim):
  42.     myPen.begin_fill()
  43.     # 0 deg.
  44.     myPen.forward(intDim)
  45.     myPen.left(90)
  46.     # 90 deg.
  47.     myPen.forward(intDim)
  48.     myPen.left(90)
  49.     # 180 deg.
  50.     myPen.forward(intDim)
  51.     myPen.left(90)
  52.     # 270 deg.
  53.     myPen.forward(intDim)
  54.     myPen.end_fill()
  55.     myPen.setheading(0)
  56.  
  57.  
  58. ##Here is an example of how to draw a box
  59. # box(boxSize)
  60.  
  61. ##Here are some instructions on how to move "myPen" around before drawing a box.
  62. # myPen.setheading(0) #point to the right, 90 to go up, 180 to go to the left 270 to go down
  63. # myPen.penup()
  64. # myPen.forward(boxSize)
  65. # myPen.pendown()
  66.  
  67. # Here is how your PixelArt is stored (using a "list of lists")
  68. palette = ["#FFFFFF", "#000000", "#00ff00", "#ff00ff", "#AAAAAA"]
  69.  
  70. def create_maze(n):
  71.     maze = [[1] * n]
  72.     for row in range(n-2):
  73.         row = [1]
  74.         for col in range(n-2):
  75.             if randint(0,3) == 0:
  76.                 row.append(1)
  77.             else:
  78.                 row.append(0)
  79.         row.append(1)
  80.         maze.append(row)
  81.     maze.append([1] * n)
  82.    
  83.     maze[0][1] = 0
  84.     maze[n-2][n-1] = 2  
  85.            
  86.     return maze
  87.    
  88. def print_maze(maze):
  89.     # system('cls')
  90.     for row in maze:
  91.         print((row))
  92.     # sleep(0.8)
  93.  
  94.  
  95. def drawMaze(maze):
  96.     boxSize = 15
  97.     # Position myPen in top left area of the screen
  98.     myPen.penup()
  99.     myPen.goto(-130, 130)
  100.     myPen.setheading(0)
  101.     for i in range(0, len(maze)):
  102.         for j in range(0, len(maze[i])):
  103.             myPen.color(palette[maze[i][j]])
  104.             box(boxSize)
  105.             myPen.penup()
  106.             myPen.forward(boxSize)
  107.             myPen.pendown()
  108.         myPen.setheading(270)
  109.         myPen.penup()
  110.         myPen.forward(boxSize)
  111.         myPen.setheading(180)
  112.         myPen.forward(boxSize * len(maze[i]))
  113.         myPen.setheading(0)
  114.         myPen.pendown()
  115.  
  116.  
  117. def is_valid_pos(tup):
  118.     print('checking {}'.format(tup))
  119.     (row, col) = tup
  120.     if col < 0 or row < 0 or col >= MAZE_SIZE or row >= MAZE_SIZE:
  121.         return False
  122.     return maze[row][col] == 0 or maze[row][col] == 2
  123.  
  124.  
  125. # A backtracking/recursive function to check all possible paths until the exit is found
  126. def exploreMaze(maze, row, col):
  127.     s = Stack()
  128.     # text('pushing ({},{})'.format(row, col), -300, -170, 20)
  129.     s.push((row, col))
  130.  
  131.     while not s.isEmpty():
  132.        
  133.         text('Stack contents: {}'.format(s.items),-300, -200, 20)
  134.         # input('Press Enter to continue: ')
  135.         text('Popping stack', -300, -230, 20)
  136.         (row, col) = s.pop()
  137.         text('Current position: ({}, {})'.format(row, col),-300, -260, 20)
  138.        
  139.         sleep(0.25) # Change to control speed of animation
  140.  
  141.         if maze[row][col] == 2:
  142.             # We found the exit
  143.             return True
  144.         elif maze[row][col] == 0:  # Empty path, not explored
  145.             maze[row][col] = 3
  146.             myPen.clear()
  147.             drawMaze(maze)
  148.             myPen.getscreen().update()
  149.            
  150.            
  151.             # As we are using a stack, the order of searching is reversed compared to the recursive version
  152.             if is_valid_pos((row, col + 1)): s.push((row, col + 1))
  153.             if is_valid_pos((row + 1, col)): s.push((row + 1, col))
  154.             if is_valid_pos((row,col - 1)): s.push((row,col - 1))
  155.             if is_valid_pos((row - 1, col)): s.push((row - 1, col))
  156.  
  157.             maze[row][col] = 4
  158.             myPen.clear()
  159.             drawMaze(maze)
  160.             myPen.getscreen().update()
  161.  
  162. while True:
  163.     myPen.clear()
  164.     maze = create_maze(5)
  165.     # print_maze(maze)
  166.     drawMaze(maze)
  167.     myPen.getscreen().update()
  168.     MAZE_SIZE = len(maze)
  169.  
  170.     solved = exploreMaze(maze, 0, 1)
  171.     if solved:
  172.         print("Maze Solved")
  173.         text("Maze Solved", -100, -150, 20)
  174.         sleep(2)
  175.     else:
  176.         print("Cannot Solve Maze")
  177.         text("Cannot Solve Maze", -130, -150, 20)
  178.         sleep(2)
  179.  
  180.     myPen.getscreen().update()
  181. turtle.done()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top