Ein Auto mit turtle zeichnen.

maze.py 7.7KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250
  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  3. """
  4. Author: Leo Vidarte <http://nerdlabs.com.ar>
  5. This is free software,
  6. you can redistribute it and/or modify it
  7. under the terms of the GPL version 3
  8. as published by the Free Software Foundation.
  9. """
  10. import random
  11. import Tkinter as tk
  12. import sys
  13. class Application(tk.Frame):
  14. def __init__(self, width=21, height=21, size=10):
  15. tk.Frame.__init__(self)
  16. self.maze = Maze(width, height)
  17. self.size = size
  18. self.steps = 0
  19. self.grid()
  20. self.create_widgets()
  21. self.draw_maze()
  22. self.create_events()
  23. def create_widgets(self):
  24. width = self.maze.width * self.size
  25. height = self.maze.height * self.size
  26. self.canvas = tk.Canvas(self, width=width, height=height)
  27. self.canvas.grid()
  28. self.status = tk.Label(self)
  29. self.status.grid()
  30. def draw_maze(self):
  31. for i, row in enumerate(self.maze.maze):
  32. for j, col in enumerate(row):
  33. x0 = j * self.size
  34. y0 = i * self.size
  35. x1 = x0 + self.size
  36. y1 = y0 + self.size
  37. color = self.get_color(x=j, y=i)
  38. id = self.canvas.create_rectangle(x0, y0, x1, y1, width=0, fill=color)
  39. if self.maze.start_cell == (j, i):
  40. self.cell = id
  41. self.canvas.tag_raise(self.cell) # bring to front
  42. self.status.config(text='Movidas mínimas: %d' % self.maze.steps)
  43. def create_events(self):
  44. self.canvas.bind_all('<KeyPress-Up>', self.move_cell)
  45. self.canvas.bind_all('<KeyPress-Down>', self.move_cell)
  46. self.canvas.bind_all('<KeyPress-Left>', self.move_cell)
  47. self.canvas.bind_all('<KeyPress-Right>', self.move_cell)
  48. def move_cell(self, event):
  49. if event.keysym == 'Up':
  50. if self.check_move(0, -1):
  51. self.canvas.move(self.cell, 0, -self.size)
  52. self.steps += 1
  53. if event.keysym == 'Down':
  54. if self.check_move(0, 1):
  55. self.canvas.move(self.cell, 0, self.size)
  56. self.steps += 1
  57. if event.keysym == 'Left':
  58. if self.check_move(-1, 0):
  59. self.canvas.move(self.cell, -self.size, 0)
  60. self.steps += 1
  61. if event.keysym == 'Right':
  62. if self.check_move(1, 0):
  63. self.canvas.move(self.cell, self.size, 0)
  64. self.steps += 1
  65. args = (self.steps, self.maze.steps)
  66. self.status.config(text='Movidas: %d/%d' % args)
  67. self.check_status()
  68. def check_move(self, x, y):
  69. x0, y0 = self.get_cell_coords()
  70. x1 = x0 + x
  71. y1 = y0 + y
  72. return self.maze.maze[y1][x1] == 0
  73. def get_cell_coords(self):
  74. position = self.canvas.coords(self.cell)
  75. x = int(position[0] / self.size)
  76. y = int(position[1] / self.size)
  77. return (x, y)
  78. def check_status(self):
  79. if self.maze.exit_cell == self.get_cell_coords():
  80. args = (self.steps, self.maze.steps)
  81. self.status.config(text='Resuelto en %d/%d movidas!' % args)
  82. def get_color(self, x, y):
  83. if self.maze.start_cell == (x, y):
  84. return 'red'
  85. if self.maze.exit_cell == (x, y):
  86. return 'green'
  87. if self.maze.maze[y][x] == 1:
  88. return 'black'
  89. class Maze(object):
  90. """
  91. ## MAZE GENERATOR ##
  92. Based on Depth-first search algorithm:
  93. http://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search
  94. 1. Start at a particular cell and call it the "exit."
  95. 2. Mark the current cell as visited, and get a list of its neighbors.
  96. For each neighbor, starting with a randomly selected neighbor:
  97. 1. If that neighbor hasn't been visited, remove the wall between
  98. this cell and that neighbor, and then recurse with that neighbor as
  99. the current cell.
  100. __author__ = "Leonardo Vidarte"
  101. """
  102. def __init__(self, width=21, height=21, exit_cell=(1, 1)):
  103. self.width = width
  104. self.height = height
  105. self.exit_cell = exit_cell
  106. self.create()
  107. def create(self):
  108. self.maze = [[1] * self.width for _ in range(self.height)] # full of walls
  109. self.start_cell = None
  110. self.steps = None
  111. self.recursion_depth = None
  112. self._visited_cells = []
  113. self._visit_cell(self.exit_cell)
  114. def _visit_cell(self, cell, depth=0):
  115. x, y = cell
  116. self.maze[y][x] = 0 # remove wall
  117. self._visited_cells.append(cell)
  118. neighbors = self._get_neighbors(cell)
  119. random.shuffle(neighbors)
  120. for neighbor in neighbors:
  121. if not neighbor in self._visited_cells:
  122. self._remove_wall(cell, neighbor)
  123. self._visit_cell(neighbor, depth+1)
  124. self._update_start_cell(cell, depth)
  125. def _get_neighbors(self, cell):
  126. """
  127. Get the cells next to the cell
  128. Example:
  129. Given the following mazes
  130. The a neighbor's are b
  131. # # # # # # # # # # # # # #
  132. # # # b # # # # a # b # # #
  133. # # # # # # # # # # # # # #
  134. # b # a # b # # b # # # # #
  135. # # # # # # # # # # # # # #
  136. # # # b # # # # # # # # # #
  137. # # # # # # # # # # # # # #
  138. """
  139. x, y = cell
  140. neighbors = []
  141. # Left
  142. if x - 2 > 0:
  143. neighbors.append((x-2, y))
  144. # Right
  145. if x + 2 < self.width:
  146. neighbors.append((x+2, y))
  147. # Up
  148. if y - 2 > 0:
  149. neighbors.append((x, y-2))
  150. # Down
  151. if y + 2 < self.height:
  152. neighbors.append((x, y+2))
  153. return neighbors
  154. def _remove_wall(self, cell, neighbor):
  155. """
  156. Remove the wall between two cells
  157. Example:
  158. Given the cells a and b
  159. The wall between them is w
  160. # # # # #
  161. # # # # #
  162. # a w b #
  163. # # # # #
  164. # # # # #
  165. """
  166. x0, y0 = cell
  167. x1, y1 = neighbor
  168. # Vertical
  169. if x0 == x1:
  170. x = x0
  171. y = (y0 + y1) / 2
  172. # Horizontal
  173. if y0 == y1:
  174. x = (x0 + x1) / 2
  175. y = y0
  176. self.maze[y][x] = 0 # remove wall
  177. def _update_start_cell(self, cell, depth):
  178. if depth > self.recursion_depth:
  179. self.recursion_depth = depth
  180. self.start_cell = cell
  181. self.steps = depth * 2 # wall + cell
  182. def show(self, verbose=False):
  183. MAP = {0: ' ', # path
  184. 1: '#', # wall
  185. 2: 'B', # exit
  186. 3: 'A', # start
  187. }
  188. x0, y0 = self.exit_cell
  189. self.maze[y0][x0] = 2
  190. x1, y1 = self.start_cell
  191. self.maze[y1][x1] = 3
  192. for row in self.maze:
  193. print ' '.join([MAP[col] for col in row])
  194. if verbose:
  195. print "Steps from A to B:", self.steps
  196. if __name__ == '__main__':
  197. from optparse import OptionParser
  198. parser = OptionParser(description="Random maze game")
  199. parser.add_option('-W', '--width', type=int, default=21,
  200. help="maze width (default 21)")
  201. parser.add_option('-H', '--height', type=int, default=21,
  202. help="maze height (default 21)")
  203. parser.add_option('-s', '--size', type=int, default=10,
  204. help="cell size (default 10)")
  205. args, _ = parser.parse_args()
  206. for arg in ('width', 'height'):
  207. if getattr(args, arg) % 2 == 0:
  208. setattr(args, arg, getattr(args, arg) + 1)
  209. print "Warning: %s must be odd, using %d instead" % \
  210. (arg, getattr(args, arg))
  211. sys.setrecursionlimit(5000)
  212. app = Application(args.width, args.height, args.size)
  213. app.master.title('Maze game')
  214. app.mainloop()