In Projects

Snake Game & Autopilot Algorithm

This python program recreates the common video game concept, Snake. The objective of the game is to steer the snake towards the randomly placed food while avoiding running into the walls or any part of the snake. The game gets progressively more difficult as the snake grows because free space runs a path finding and decision making algorithm that plays the game automatically without user input. The autopilot algorithm consists of several components, including a path finding algorithm and a contiguous free space finding algorithm.

Python Code

snake.py
1    # Program:
2    # snake.py
3    # Snake Video Game with Autopilot Algorithm
4    #
5    # Description:
6    # This python program recreates the common video game concept, Snake. The objective of the game is to steer
7    # the snake towards the randomly placed food while avoiding running into the walls or any part of the snake. The game
8    # gets progressively more difficult as the snake grows because free space becomes increasingly limited. The program
9    # runs a path finding and decision making algorithm that plays the game automatically without user input. The autopilot
10   # algorithm consists of several components, including a path finding algorithm and a contiguous free space finding
11   # algorithm.
12   #
13   # Algorithm:
14   # - Find path from snake head to food
15   # - If Path to food is found:
16   #   - Create future game board where snake has just completed the proposed path then recursively check 9 moves ahead to
17   #     verify if snake will be safe by taking this path.
18   #        - Snake is safe if there is at least the minimum required contiguous free space.
19   #          Required minimum free space is a function of snake length.
20   #        - Snake is safe if it can pathfind to tail.
21   #   - If snake will be in a safe position after completing path to food:
22   #        - Take path.
23   #   - Else if snake will not be safe after completing path to food:
24   #        - Coil towards closest prioritized corner.
25   #        - Search through prioritized neighbor list to see which neighbors are free and then recursively check 9
26   #          moves ahead to verify if snake is still safe.
27   #        - If safe neighboring tile is found:
28   #            - Take path.
29   #        - Else if no safe neighboring tile is found:
30   #            - Game Over!
31   # - Else if path to food is not found:
32   #   - Coil towards closest prioritized corner (See above).
33   # - If snake length == 256:
34   #   - Win!
35   
36   
37   # -------- Imports -------- #
38   from tkinter import Tk, ttk, Canvas, Label, Button, Frame, Entry, Toplevel,\
39       IntVar, StringVar, END, N, W, S, E, LAST, LEFT, RIGHT, CENTER, BOTH
40   import datetime
41   from win32api import GetSystemMetrics       # Used to detect monitor setup
42   import time
43   import math
44   import random
45   
46   RUNNING = 'running'                         # Game is running
47   STOPPED = 'stopped'                         # Game is stopped
48   FOOD = 'food'                               # Tile state
49   SNAKE = 'snake'                             # Tile state
50   FREE = 'free'                               # Tile state
51   WALL = 'wall'                               # Tile state (Manually placed walls)
52   HEAD = 'head'                               # Tile Visual
53   BODY = 'body'                               # Tile Visual
54   TAIL = 'tail'                               # Tile Visual
55   HIGHLIGHT = 'highlight'                     # Tile Visual
56   DEBUG_PATH_1 = 'debugPath1'                 # Tile Visual
57   DEBUG_PATH_2 = 'debugPath2'                 # Tile Visual
58   DEBUG_SPACE_1 = 'debugSpace1'               # Tile Visual
59   DEBUG_SPACE_2 = 'debugSpace2'               # Tile Visual
60   DEBUG_START = 'debugStart'                  # Visual
61   DEBUG_END = 'debugEnd'                      # Tile Visual
62   PROJECTED_SNAKE = 'projectedSnake'          # Tile Visual
63   PATH_TO_FOOD = 'PathToFood'                 # Flag - Pathing Method
64   PATH_TO_TAIL = 'PathToTail'                 # Flag - Pathing Method
65   SAFE = 'Safe'
66   NOT_SAFE = 'notSafe'
67   PATH = 'path'
68   NO_PATH = 'noPath'
69   PASS = 'pass'
70   FAILED = 'failed'
71   GRID_SIZE = 25
72   S = 'S'                                     # Object sizes on grid
73   M = 'M'
74   ML = 'ML'
75   L = 'L'
76   XL = 'XL'
77   SHAPE_LIBRARY = {
78       'highlight': {
79           'color': 'yellow',
80           'size': S,
81           'type': 'rectangle'
82           },
83       'debugPath1': {
84           'color': 'deep sky blue',
85           'size': S,
86           'type': 'circle'
87           },
88       'debugPath2': {
89           'color': 'light blue',
90           'size': S,
91           'type': 'circle'
92           },
93       'debugSpace1': {
94           'color': 'MediumPurple3',
95           'size': S,
96           'type': 'circle'
97           },
98       'debugSpace2': {
99           'color': 'MediumPurple1',
100          'size': S,
101          'type': 'circle'
102          },
103      'debugStart': {
104          'color': 'Green3',
105          'size': XL,
106          'type': 'rectangleOutline'
107          },
108      'debugEnd': {
109          'color': 'red',
110          'size': XL,
111          'type': 'rectangleOutline'
112          },
113      'head': {
114          'color': 'SteelBlue1',
115          'size': L,
116          'type': 'rectangle'
117          },
118      'tail': {
119          'color': 'silver',
120          'size': L,
121          'type': 'rectangle'
122          },
123      'body': {
124          'color': 'grey30',
125          'size': L,
126          'type': 'rectangle'
127          },
128      'projectedSnake': {
129          'color': 'SkyBlue',
130          'size': M,
131          'type': 'rectangle'
132          },
133      'food': {
134          'color': 'green3',
135          'size': ML,
136          'type': 'rectangle'
137          },
138      'wall': {
139          'color': 'black',
140          'size': L,
141          'type': 'rectangle'
142          }
143      }
144  
145  
146  class clsTile:
147      def __init__(self, main, x, y):
148          self.main = main
149          self.x = x                                          # Tile x coordinate
150          self.y = y                                          # Tile y coordinate
151          self.quadrant = None                                # Tile grid quadrant
152          self.directionPriority = []                         # Tile direction priority given tile location
153          self.dist = None                                    # Tile distance holding variable
154          self.prev = None                                    # Tile prev path holding variable
155          self.state = {}                                     # Tile state holding variable
156          for i in range(0, 10):
157              self.state[i] = FREE                            # Tile state for board
158          self.setDirectionPriority()                         # Get direction priority list given tile location
159          self.seqNeighbors = []                              # Populated during finishSetup() after all tiles created
160          self.freeSpaceAfterMove = None                      # Used to store free space after moving
161          self.canvas = mainApp.w                             # Tile canvas object
162          self.xShape = self.x                                # Tile canvas coordinate
163          self.yShape = mainApp.canvasHeight - self.y         # Canvas y and material y coord system differ
164          self.shapeCoords = {}                               # Shape coordinates for shape objects
165          for sizeClass, size in [(S, 6), (M, 8), (ML, 14), (L, 18), (XL, 48)]:
166              self.shapeCoords[sizeClass] = self.xShape - 1 - size / 2, \
167                                            self.yShape - 0 - size / 2, \
168                                            self.xShape - 0 + size / 2, \
169                                            self.yShape + 1 + size / 2        # 1px offsets to center shapes with grid
170          self.shape = {
171              HIGHLIGHT: None,
172              DEBUG_PATH_1: None,
173              DEBUG_PATH_2: None,
174              DEBUG_SPACE_1: None,
175              DEBUG_SPACE_2: None,
176              DEBUG_START: None,
177              DEBUG_END: None,
178              HEAD: None,
179              TAIL: None,
180              BODY: None,
181              PROJECTED_SNAKE: None,
182              FOOD: None,
183              WALL: None
184              }                                               # Dict of tiles shape objects on canvas
185          
186      def drawShape(self, shape):
187          self.delShape(shape)
188          if SHAPE_LIBRARY[shape]['type'] == 'rectangle':
189              self.shape[shape] = self.canvas.create_rectangle(*self.shapeCoords[SHAPE_LIBRARY[shape]['size']],
190                                                               fill=SHAPE_LIBRARY[shape]['color'])
191  
192          if SHAPE_LIBRARY[shape]['type'] == 'circle':
193              self.shape[shape] = self.canvas.create_oval(*self.shapeCoords[SHAPE_LIBRARY[shape]['size']],
194                                                          fill=SHAPE_LIBRARY[shape]['color'])
195  
196          if SHAPE_LIBRARY[shape]['type'] == 'rectangleOutline':
197              self.shape[shape] = self.canvas.create_rectangle(*self.shapeCoords[SHAPE_LIBRARY[shape]['size']],
198                                                               outline=SHAPE_LIBRARY[shape]['color'], width=3)
199  
200      def delShape(self, shape):                              # Delete tiles shape by given type
201          if self.shape[shape] is not None:
202              self.canvas.delete(self.shape[shape])
203              self.shape[shape] = None
204  
205      def getNeighborByDir(self, direction):                  # Return neighbor tile by direction
206          xMod, yMod = 0, 0
207          if direction == 'U':
208              xMod, yMod = 0, GRID_SIZE
209          elif direction == 'D':
210              xMod, yMod = 0, -GRID_SIZE
211          elif direction == 'L':
212              xMod, yMod = -GRID_SIZE, 0
213          elif direction == 'R':
214              xMod, yMod = GRID_SIZE, 0
215          for tile in mainApp.Tiles:
216              if (tile.x, tile.y) == (self.x + xMod, self.y + yMod):
217                  return tile
218          return None
219  
220      def getSeqNeighbors(self):                              # Return prioritized neighboring tile list
221          neighborsList = [self.getNeighborByDir(self.directionPriority[0]),
222                           self.getNeighborByDir(self.directionPriority[1]),
223                           self.getNeighborByDir(self.directionPriority[2]),
224                           self.getNeighborByDir(self.directionPriority[3])]
225          return [tile for tile in neighborsList if tile is not None]         # Return the list with 'None's removed
226      
227      def getFreeSeqNeighbors(self, board):                   # Return prioritized FREE neighboring tile list
228          return [tile for tile in self.seqNeighbors if tile.state[board] == FREE]
229  
230      def setDirectionPriority(self):
231          if 8*GRID_SIZE < self.x < 16*GRID_SIZE and 8*GRID_SIZE < self.y < 16*GRID_SIZE:     # Quadrant 1, Top Right
232              self.quadrant = 1
233              self.directionPriority = ['U', 'R', 'L', 'D']
234          if 0*GRID_SIZE < self.x < 8*GRID_SIZE and 8*25 < self.y < 16*GRID_SIZE:             # Quadrant 2, Top Left
235              self.quadrant = 2
236              self.directionPriority = ['U', 'L', 'R', 'D']
237          if 0*GRID_SIZE < self.x < 8*GRID_SIZE and 0*GRID_SIZE < self.y < 8*GRID_SIZE:       # Quadrant 3, Bottom Left
238              self.quadrant = 3
239              self.directionPriority = ['D', 'L', 'R', 'U']
240          if 8*GRID_SIZE < self.x < 16*GRID_SIZE and 0*25 < self.y < 8*GRID_SIZE:             # Quadrant 4, Bottom Right
241              self.quadrant = 4
242              self.directionPriority = ['D', 'R', 'L', 'U']
243          
244      def flyToEndDistance(self, end):
245          return math.sqrt(math.pow(self.x - end.x, 2) + math.pow(self.y - end.y, 2))
246  
247  
248  class clsPathfind:
249      def __init__(self):
250          self.tile = None
251          self.frontier = []                          # List of tiles to explore tiles to explore next
252          self.explored = []                          # List of tiles already explored
253          self.solution = []                          # Resulting optimized path
254  
255      def solve(self, start, end, board, method):     # Pathfind from start to end using given board and method
256          self.reset()
257          self.frontier.append(start)
258          start.dist = 0                              # Initialize pathfind start distance to 0
259          if mainApp.oVisualDebug:
260              mainApp.labelBoard_text.set('%s' % board)
261          else:
262              mainApp.labelBoard_text.set('-')
263  
264          if method == PATH_TO_FOOD:
265              mainApp.labelAlgo_text.set('Pathfind to Food')
266          if method == PATH_TO_TAIL:
267              mainApp.labelAlgo_text.set('Pathfind to Tail')
268              
269          # Show the relevant board for visual debug
270          if mainApp.oVisualDebug:
271              start.drawShape(DEBUG_START)
272              end.drawShape(DEBUG_END)
273              if board != 0:
274                  mainApp.showProjectedBoard(board)
275  
276          # Creates a dict of board's snake's neighbors and their associated reverse snake index.
277          # If any of these tiles gets explored and the path dist to the tile > rev index, then this tile will be tail by
278          # time reached. Must check board's snake neighbors instead of snake, because snake tiles are not FREE and wont
279          # be explored. Effectively looks for safety by path to tail or path to what will be tail by the time head
280          # reaches that tile.
281          if method == PATH_TO_TAIL:
282              willBePassedFutureTailNodes = {}
283              willBePassedFutureTailNodes.clear()
284              for tile in mainApp.snake[board]:
285                  for neighbor in tile.seqNeighbors:
286                      willBePassedFutureTailNodes[neighbor] = len(mainApp.snake[board]) - mainApp.snake[board].index(tile)
287  
288          while True:
289              # If all tiles explored, return solution
290              if len(self.frontier) == 0:
291                  if mainApp.oVisualDebug:
292                      mainApp.deleteAllDebugVisuals()
293                  return NO_PATH, []
294  
295              # Sort tile list and choose first tile
296              self.frontier.sort(key=lambda x: x.dist)                # Sort list in place for shortest dist first
297              self.tile = self.frontier.pop(0)                        # Select first tile and remove it from list
298  
299              # If reached tail or a part of snake body that will be tail by the time head is there and method
300              # is PATH_TO_TAIL then return solution
301              if method == PATH_TO_TAIL and self.tile in willBePassedFutureTailNodes.values() \
302                      and self.tile.dist >= willBePassedFutureTailNodes[self.tile]:
303                  if mainApp.oVisualDebug:
304                      mainApp.hideProjectedBoard()
305                      mainApp.deleteAllDebugVisuals()
306                  raise ValueError('This never fires')
307                  return PATH_TO_TAIL, self.reverseTraceSolution(start, self.tile).copy()     # Use copy of list
308  
309              # If reached tail then return solution
310              if method == PATH_TO_TAIL and self.tile == end:
311                  if mainApp.oVisualDebug:
312                      mainApp.hideProjectedBoard()
313                      mainApp.deleteAllDebugVisuals()
314                  return PATH_TO_TAIL, self.reverseTraceSolution(start, end).copy()   # Use copy of list
315  
316              # Draw visuals if they are enabled
317              if mainApp.oVisualDebug:
318                  self.tile.drawShape(DEBUG_PATH_1)
319                  mainApp.root.update_idletasks()
320                  time.sleep(0.001)
321  
322              # If reached food tile and method is PATH_TO_FOOD then return solution
323              if method == PATH_TO_FOOD and self.tile == end:
324                  if mainApp.oVisualDebug:
325                      mainApp.hideProjectedBoard()
326                      mainApp.deleteAllDebugVisuals()
327                  return PATH_TO_FOOD, self.reverseTraceSolution(start, end).copy()   # Use copy of list
328  
329              # Explore neighbors of selected tile
330              for neighbor in self.tile.getFreeSeqNeighbors(board):                   # Analyze FREE neighboring nodes
331                  if neighbor not in self.explored:
332                      self.frontier.append(neighbor)
333                      self.explored.append(neighbor)                                  # No neighbor node explored twice
334                      if mainApp.oVisualDebug:
335                          neighbor.drawShape(DEBUG_PATH_2)
336                      if neighbor.dist > self.tile.dist + 1:
337                          neighbor.dist = self.tile.dist + 1
338                          neighbor.prev = self.tile
339  
340      def reverseTraceSolution(self, start, end):
341          tile = end
342          while tile != start:
343              self.solution.insert(0, tile)
344              tile = tile.prev
345          return self.solution                # First element in self.solution is first step tile, not start tile
346  
347      def reset(self):
348          for tile in mainApp.Tiles:          # Re-initialize all tiles.dist to large distance
349              tile.dist = 999
350          self.frontier.clear()      
351          self.explored.clear()
352          self.solution.clear()
353  
354  
355  class clsFreeSpace: 
356      def __init__(self):
357          self.tile = None
358          self.frontier = []                 # List of tiles to explore tiles to explore next
359          self.explored = []                 # List of tiles already explored
360  
361      def solve(self, start, board):          # Return size of contiguous free space surrounding start with given board
362          self.reset()
363          self.frontier.append(start)
364  
365          if mainApp.oVisualDebug:
366              mainApp.labelBoard_text.set('%s' % board)
367          else:
368              mainApp.labelBoard_text.set('-')
369  
370          mainApp.labelAlgo_text.set('Free Space')
371              
372          # Show the relevant board for visual debug
373          if mainApp.oVisualDebug:
374              mainApp.showProjectedBoard(board)
375  
376          while True:
377              # If explored all tiles, return solution
378              if len(self.frontier) == 0:
379                  if mainApp.oVisualDebug:
380                      mainApp.hideProjectedBoard()
381                      mainApp.deleteAllDebugVisuals()
382                  return len(self.explored)                           # Return count of tiles explored
383  
384              # Select tile to explore
385              self.tile = self.frontier.pop(0)                        # Select first tile and remove from list
386  
387              # Draw visuals if they are enabled
388              if mainApp.oVisualDebug:
389                  self.tile.drawShape(DEBUG_SPACE_1)
390                  mainApp.root.update_idletasks()
391                  time.sleep(0.001)
392  
393              # Explore neighbors of selected tile
394              for neighbor in self.tile.getFreeSeqNeighbors(board):   # Explore FREE neighboring nodes
395                  if neighbor not in self.explored:
396                      self.explored.append(neighbor)                  # No neighbor node explored twice
397                      self.frontier.append(neighbor)
398                      if mainApp.oVisualDebug:
399                          neighbor.drawShape(DEBUG_SPACE_2)
400  
401      def reset(self):
402          self.frontier.clear()
403          self.explored.clear()
404  
405  
406  class clsMainApp:
407      def __init__(self, root):
408          print('\nRunning...')
409          self.root = root
410          self.cycleTime = 50                     # Core loop time (ms)
411          self.iteration = 0                      # Iteration count
412          self.queueStop = False                  # Queue stop request
413          self.queueReset = False                 # Queue reset request
414          self.setPause = False                   # Set pause state
415          self.oVisualDebug = False               # Frozen working copy of visualDebugSetting
416          self.visualDebugSetting = False         # Toggle for turning on debugging visuals
417          self.pauseForBoards = True              # Toggle for pausing when future boards displayed
418          self.showCurrentBoardEveryIter = False  # Toggle for showing current board at end of every iteration
419          self.iterationStartTime = None          # Timestamp of current iteration start
420          self.mode = None
421          self.messagePop = None
422          self.runStatus = STOPPED
423          self.pathfind = clsPathfind()
424          self.freeSpace = clsFreeSpace()
425          self.Tiles = []
426          self.snakeLength = 2                    # Initial snake length
427          self.snake = {}                         # Dict of snakes for each board (0-9), each with list of snake tiles
428          for i in range(0, 10):                  # Snake[0] = Current Board's snake list of tile objects, head first
429              self.snake[i] = []                  # Snake[0][0] = Current snake head tile object 
430          self.head = None
431          self.tail = None
432          self.food = None
433          self.freeSpaceForEachMove = {}
434  
435          # Window Setup
436          self.root.title("Snake")
437          self.root.configure(bg='white')
438          self.appWidth = 800                     # Overall window width
439          self.appHeight = 800                    # Overall window height
440          self.canvasWidth = 400                  # Canvas Width
441          self.canvasHeight = 400                 # Canvas Height
442          self.combinedSW = GetSystemMetrics(78)  # Combined multi-monitor width
443          self.sw = root.winfo_screenwidth()      # Single monitor width
444          self.sh = root.winfo_screenheight()
445          if self.combinedSW < 2600:
446              self.screenType = 'Single'          # Single screen
447              self.root.geometry('+%d+%d' % (self.sw - self.appWidth - 800,
448                                             self.sh - self.appHeight - 300))
449          else:
450              self.screenType = 'Dual'            # Dual screen
451              self.root.geometry('+%d+%d' % (self.sw - self.appWidth + 1500,
452                                             self.sh - self.appHeight - 180))
453  
454          # Frames
455          topFrame = Frame(root, bg='#4682B4', padx=20, pady=20)
456          middleFrame = Frame(root, bg='white', padx=20, pady=20)
457          bottomFrame = Frame(root, bg='#4682B4', padx=20, pady=20)
458          topFrame.pack(fill='x'), middleFrame.pack(expand=1, fill='both'), bottomFrame.pack(fill='both')
459  
460          # Top Frame Widgets
461          self.labelSnakeTitle = Label(topFrame, text='Length', width=10, borderwidth=1, relief="solid", pady=4)
462          self.labelSnake_text = StringVar()
463          self.labelSnake_text.set('-')
464          self.labelSnake = Label(topFrame, textvariable=self.labelSnake_text, borderwidth=1, relief="solid", pady=4,
465                                  font=("Courier", 26), bg="white")
466  
467          self.labelBoardTitle = Label(topFrame, text='Board', width=10, borderwidth=1, relief="solid", pady=4)
468          self.labelBoard_text = StringVar()
469          self.labelBoard_text.set('-')
470          self.labelBoard = Label(topFrame, textvariable=self.labelBoard_text, borderwidth=1, relief="solid", pady=4,
471                                  font=("Courier", 26), bg="white")
472  
473          self.labelMessageTitle = Label(topFrame, text='Algorithm', width=38, borderwidth=1, relief="solid", pady=4)
474          self.labelMessage_text = StringVar()
475          self.labelMessage_text.set('-')
476          self.labelMessage = Label(topFrame, textvariable=self.labelMessage_text, borderwidth=1, relief="solid",
477                                    pady=4, bg="white")
478  
479          self.labelAlgoTitle = Label(topFrame, text='Pathing', width=40, borderwidth=1, relief="solid", pady=4)
480          self.labelAlgo_text = StringVar()
481          self.labelAlgo_text.set('-')
482          self.labelAlgo = Label(topFrame, textvariable=self.labelAlgo_text, borderwidth=1, relief="solid", pady=4, 
483                                 bg="white")
484  
485          # Middle Frame Widgets
486          self.w = Canvas(middleFrame, width=self.canvasWidth, height=self.canvasHeight, bg='white',
487                          borderwidth=2, highlightthickness=1, relief='groove')
488  
489          # Create grid lines
490          for i in range(0, self.canvasWidth, 25):
491              self.w.create_line([(i, 0), (i, self.canvasHeight)], tag='grid_line', fill='grey')
492          for i in range(0, self.canvasHeight, 25):
493              self.w.create_line([(0, i), (self.canvasWidth, i)], tag='grid_line', fill='grey')
494  
495          # Bottom Frame Widgets
496          self.startButton = Button(bottomFrame, text='Start', command=self.start, width=11, borderwidth=1, 
497                                    relief="ridge", bg='white')
498          self.resetButton = Button(bottomFrame, text='Reset', command=self.requestReset, width=11, borderwidth=1, 
499                                    relief="ridge", bg='white')
500          self.pauseButton = Button(bottomFrame, text='Pause', command=self.togglePause, width=11, borderwidth=1, 
501                                    relief="ridge", bg='white')
502          self.skipButton = Button(bottomFrame, text='Skip', command=self.skipAhead, width=11, borderwidth=1, 
503                                   relief="ridge", bg='white')
504          self.visualsButton = Button(bottomFrame, text='Visuals', command=self.toggleVisuals, width=11, borderwidth=1,
505                                      relief="ridge", bg='white')
506          self.fastButton = Button(bottomFrame, text='Fast', command=self.setFastSpeed, width=11, borderwidth=1, 
507                                   relief="ridge", bg='white')
508          self.normalButton = Button(bottomFrame, text='Normal', command=self.setNormalSpeed, width=11, borderwidth=1,
509                                     relief="ridge", bg='white')
510          self.slowButton = Button(bottomFrame, text='Slow', command=self.setSlowSpeed, width=11, borderwidth=1,
511                                   relief="ridge", bg='white')
512          self.crawlButton = Button(bottomFrame, text='Crawl', command=self.setCrawlSpeed, width=11, borderwidth=1,
513                                    relief="ridge", bg='white')
514  
515          self.labelSnakeTitle.grid(row=1, column=1, pady=(0, 0), sticky=W+E+S+N)
516          self.labelSnake.grid(row=2, column=1, rowspan=3, pady=(0, 0), sticky=W+E+S+N)
517          self.labelBoardTitle.grid(row=1, column=2, pady=(0, 0), sticky=W+E+S+N)
518          self.labelBoard.grid(row=2, column=2, rowspan=3, pady=(0, 0), sticky=W+E+S+N)
519          self.labelMessageTitle.grid(row=1, column=3, pady=(0, 0), sticky=W+E+S+N)
520          self.labelMessage.grid(row=2, column=3, pady=(0, 0), sticky=W+E+S+N)
521          self.labelAlgoTitle.grid(row=3, column=3, pady=(0, 0), sticky=W+E+S+N)
522          self.labelAlgo.grid(row=4, column=3, pady=(0, 0), sticky=W+E+S+N)
523  
524          topFrame.columnconfigure(0, weight=1)
525          topFrame.columnconfigure(4, weight=1)
526  
527          self.w.pack(expand=1)
528  
529          self.startButton.grid(row=0, column=1, sticky=W+E)
530          self.resetButton.grid(row=0, column=2, sticky=W+E)
531          self.pauseButton.grid(row=0, column=3, sticky=W+E)
532          self.skipButton.grid(row=0, column=4, sticky=W+E)
533          self.visualsButton.grid(row=0, column=5, sticky=W+E)
534          self.fastButton.grid(row=1, column=1, sticky=W+E)
535          self.normalButton.grid(row=1, column=2, sticky=W+E)
536          self.slowButton.grid(row=1, column=3, sticky=W+E)
537          self.crawlButton.grid(row=1, column=4, sticky=W+E)
538  
539          bottomFrame.columnconfigure(0, weight=1)
540          bottomFrame.columnconfigure(6, weight=1)
541  
542          self.root.update_idletasks()                                # Update window geometry
543  
544      def finishSetup(self):                                          # Run finishSetup after initializing mainApp
545          self.createTiles()
546          self.setTileNeighbors()
547          self.setNormalSpeed()
548  
549      def createTiles(self):                                          # Create each tile object, append to Tiles
550          for i in range(13, self.canvasWidth, 25):
551              for j in range(13, self.canvasHeight, 25):
552                  self.Tiles.append(clsTile(self, i, j))
553  
554      def setTileNeighbors(self):                                     # Create a list seq neighbors for each tile
555          for tile in self.Tiles:
556              tile.seqNeighbors = tile.getSeqNeighbors()
557  
558      def initializeSnake(self):                                      # Init snake to random location then move
559          start = mainApp.Tiles[random.randint(0, 255)]               # Random initial starting location
560          self.moveHead(start)                                        # Initialize snake[] with first tile
561          self.moveHead(random.choice(start.getFreeSeqNeighbors(0)))  # Move in random FREE direction
562          self.markTail()                                             # Mark last tile in snake[] as tail
563  
564      def skipAhead(self):
565          self.snakeLength = self.snakeLength + 60
566  
567      def start(self):
568          if self.runStatus == STOPPED and not self.setPause:
569              mainApp.reset()
570              self.runStatus = RUNNING
571              self.run()
572  
573      def messageUpdate(self, printMsg, labelMsg, labelColor):
574          print(printMsg)
575          self.labelMessage_text.set(labelMsg)
576          self.labelMessage.configure(bg=labelColor)
577  
578      def reset(self):
579          self.setPause = False                                       # Reset buttons if they are set
580          self.pauseButton.configure(bg='white')
581          self.visualDebugSetting = False                             # Reset buttons if they are set
582          self.visualsButton.configure(bg='white')
583  
584          for i in range(0, 10):
585              self.snake[i].clear()                                   # Clear Snake list for all boards
586          self.snakeLength = 2
587          self.iteration = 0
588  
589          for tile in self.Tiles:
590              for i in range(0, 10):
591                  tile.state[i] = FREE
592              tile.delShape(HIGHLIGHT)
593              tile.delShape(HEAD)
594              tile.delShape(BODY)
595              tile.delShape(TAIL)
596              tile.delShape(WALL)
597  
598          self.initializeSnake()
599          self.spawnFood()                                        # Initial food location
600          if mainApp.messagePop is not None:
601              mainApp.messagePop.place_forget()
602  
603      def toggleVisuals(self):
604          if self.visualDebugSetting:
605              self.visualDebugSetting = False
606              self.visualsButton.configure(bg='white')
607          else:
608              self.visualDebugSetting = True
609              self.visualsButton.configure(bg='slategray3')
610  
611      def togglePause(self):
612          if self.setPause:
613              self.setPause = False
614              self.pauseButton.configure(bg='white')
615              self.showProjectedBoard(0)
616              self.hideProjectedBoard()
617              self.root.after(50, self.run)
618          else:
619              self.setPause = True
620              self.queueStop = True
621              self.pauseButton.configure(bg='slategray3')
622  
623      def requestReset(self):
624          if self.runStatus == RUNNING:
625              self.queueStop = True
626              self.queueReset = True
627          else:
628              self.reset()
629  
630      def setFastSpeed(self):
631          self.cycleTime = 10
632          self.fastButton.configure(bg='slategray3')
633          self.normalButton.configure(bg='white')
634          self.slowButton.configure(bg='white')
635          self.crawlButton.configure(bg='white')
636  
637      def setNormalSpeed(self):
638          self.cycleTime = 50
639          self.fastButton.configure(bg='white')
640          self.normalButton.configure(bg='slategray3')
641          self.slowButton.configure(bg='white')
642          self.crawlButton.configure(bg='white')
643  
644      def setSlowSpeed(self):
645          self.cycleTime = 150
646          self.fastButton.configure(bg='white')
647          self.normalButton.configure(bg='white')
648          self.slowButton.configure(bg='slategray3')
649          self.crawlButton.configure(bg='white')
650  
651      def setCrawlSpeed(self):
652          self.cycleTime = 500
653          self.fastButton.configure(bg='white')
654          self.normalButton.configure(bg='white')
655          self.slowButton.configure(bg='white')
656          self.crawlButton.configure(bg='slategray3')
657  
658      def highlightPathSolution(self, solution):
659          self.delHighlightPathSolution()
660          for tile in solution[:-1]:                              # Highlight solution except the last tile which is food
661              tile.drawShape(HIGHLIGHT)
662  
663      def delHighlightPathSolution(self):
664          for tile in self.Tiles:
665              tile.delShape(HIGHLIGHT)
666  
667      def showProjectedBoard(self, board):                        # Show projected snake visuals
668          for tile in self.Tiles:
669              if tile.state[board] == SNAKE:
670                  tile.drawShape(PROJECTED_SNAKE)                 # Draw shapes for PROJECTED_SNAKE
671  
672      def hideProjectedBoard(self):
673          for tile in self.Tiles:
674              tile.delShape(PROJECTED_SNAKE)                      # Remove all shapes for PROJECTED_SNAKE
675  
676      def deleteAllDebugVisuals(self):
677          for tile in self.Tiles:
678              tile.delShape(DEBUG_PATH_1)
679              tile.delShape(DEBUG_PATH_2)
680              tile.delShape(DEBUG_SPACE_1)
681              tile.delShape(DEBUG_SPACE_2)
682              tile.delShape(DEBUG_START)
683              tile.delShape(DEBUG_END)
684  
685      def moveHead(self, newHead):
686          if len(self.snake[0]) > 0:
687              self.snake[0][0].delShape(HEAD)
688              self.snake[0][0].drawShape(BODY)
689          self.snake[0].insert(0, newHead)                        # Add new head tile to start of snake []
690          newHead.state[0] = SNAKE  
691          newHead.drawShape(HEAD)                                 # Mark snake head color
692  
693      def checkTail(self):
694          if len(self.snake[0]) > self.snakeLength:
695              self.snake[0][-1].delShape(TAIL)
696              self.snake[0][-1].state[0] = FREE
697              del self.snake[0][-1]
698              self.markTail()
699  
700      def markTail(self):
701          # Tail should be marked with tail shape, but state set to FREE state because it is valid for the head to move
702          # to the tail space because the tail will move away at same time.
703          # This also enables valid pathfinding to tail as it can only explore FREE tail tiles.
704          # Do not mark tail as FREE if snakeLength == 2 or else snake can reverse through tail, which is not valid.
705          if self.snakeLength > 2:
706              self.snake[0][-1].state[0] = FREE                   # Mark tail as FREE, except when short enough to reverse
707          self.snake[0][-1].delShape(BODY)
708          self.snake[0][-1].drawShape(TAIL)
709  
710      def checkFood(self):
711          if self.snake[0][0] == self.food:
712              self.snakeLength += 1
713              self.labelSnake_text.set('%i' % self.snakeLength)
714              self.spawnFood()
715  
716      def spawnFood(self):
717          while True:
718              tile = self.Tiles[random.randint(0, len(self.Tiles)-1)]     # Pick a random tile in Tiles
719              if tile.state[0] == FREE and tile not in self.snake:        # Don't pick FREE tail tile
720                  if self.food is not None:
721                      self.food.delShape(FOOD)
722                  tile.drawShape(FOOD)
723                  self.food = tile
724                  break
725  
726      def checkSafety(self, board):
727          tailSafe = self.checkPathToTail(board)
728          freeSpaceSafe = self.checkFreeSpace(board)
729          if tailSafe == SAFE or freeSpaceSafe == SAFE:
730              return SAFE
731          else:
732              return NOT_SAFE
733  
734      def checkPathToTail(self, board):                           # Note that tail must be marked as FREE for pathfinding
735          tailPathStatus, tailPath = self.pathfind.solve(self.snake[board][0], self.snake[board][-1], board, PATH_TO_TAIL)
736          if tailPathStatus == NO_PATH:
737              print('[Safety Check][Check Path To Tail][Board %i] - Did Not Find Path to Tail' % board)
738              return NOT_SAFE
739          elif tailPathStatus == PATH_TO_TAIL:
740              print('[Safety Check][Check Path To Tail][Board %i] - Did Find Path to Tail' % board)
741              return SAFE
742          else:
743              print('Debug: %s' % tailPathStatus)
744              raise ValueError('Invalid Value Found Here')        # Raise error if invalid values
745  
746      def checkFreeSpace(self, board):
747          # Important to have a large margin on minFreeSpace late in the game because the snake can possibly orphan off
748          # a large portion of the free space and be unable to utilize it.
749          freeSpace = mainApp.freeSpace.solve(self.snake[board][0], board)
750          reqFreeSpace = int(self.snakeLength*1.5)
751          if freeSpace >= reqFreeSpace:
752              print('[Safety Check][Check Free Space][Board %i] - Enough Free Space: %i / %i'
753                    % (board, freeSpace, reqFreeSpace))
754              return SAFE
755          else:
756              print('[Safety Check][Check Free Space][Board %i] - Not Enough Free Space: %i / %i'
757                    % (board, freeSpace, reqFreeSpace))
758              return NOT_SAFE
759  
760      def generateBoard(self, board, projectedSnake):
761          self.clearBoard(board)                                  # Marks every tile as FREE on board
762          for tile in mainApp.Tiles:
763              if tile.state[0] == WALL:
764                  tile.state[board] = WALL
765          for tile in projectedSnake:
766              tile.state[board] = SNAKE
767          projectedSnake[-1].state[board] = FREE                  # Mark tail as free since it is FREE for current move
768  
769      def clearBoard(self, board):
770          for tile in self.Tiles:
771              tile.state[board] = FREE
772  
773      def getProjectedSnake(self, projectedPath, currentSnake):   # Creates projected snake from projected path
774          combinedPath = projectedPath + currentSnake
775          return combinedPath[:mainApp.snakeLength]               # Return snakeLength elements of combined path
776  
777      def checkGameEndConditions(self):
778          if len(self.snake) >= 256:
779              self.messagePop = Label(self.w, text='Win!', width=30, bg='Green', fg='white',
780                                      wraplength=300, borderwidth=1,  relief="solid", font=('Helvetica', 16))
781              self.messagePop.place(relx=0.5, rely=0.85, anchor=CENTER)
782              self.queueStop = True
783  
784          if len(self.snake[0][0].getFreeSeqNeighbors(0)) == 0:
785              self.messagePop = Label(self.w, text='Game Over!', width=30, bg='Green', fg='white',
786                                      wraplength=300, borderwidth=1,  relief="solid", font=('Helvetica', 16))
787              self.messagePop.place(relx=0.5, rely=0.85, anchor=CENTER)
788              self.queueStop = True
789  
790      def recursivePrioritizedNeighborsCheck(self, board):
791          if board == 8:
792              return PASS, self.snake[1][0]                       # Break out of recursion and return next move's head
793          freeSeqNeighbors = self.snake[board][0].getFreeSeqNeighbors(board)
794          for tile in freeSeqNeighbors:
795              self.snake[board + 1] = self.getProjectedSnake([tile], self.snake[board])
796              self.generateBoard(board + 1, self.snake[board + 1])
797              if self.checkSafety(board + 1) in [SAFE]:
798                  return self.recursivePrioritizedNeighborsCheck(board + 1)
799          return FAILED, None
800  
801      def cornerCoilByMaintainingFreeSpaceGuessing(self):   # Corner coil as long as >80% of best free space maintained
802          print('No Guaranteed Safe Moves Found! Proceeding by best guess anyways.')
803          self.messageUpdate('[Move Method] - Corner coil while preserving max space',
804                             'Corner coil while preserving max space', '#FF6565')
805  
806          self.checkGameEndConditions()                           # Game over if no more possible moves
807  
808          # Look at all possible next moves and get free space remaining after each move
809          self.freeSpaceForEachMove.clear()
810          for neighbor in self.snake[0][0].getFreeSeqNeighbors(0):
811              self.snake[1] = self.getProjectedSnake([neighbor], self.snake[0].copy())       # Use copy of list
812              self.generateBoard(1, self.snake[1])
813              self.freeSpaceForEachMove[neighbor] = self.freeSpace.solve(self.snake[1][0], 1)
814  
815          # Find max free space left after best move
816          print('***Number of neighbors %i' % len(self.snake[0][0].seqNeighbors))
817          print('***Number of free neighbors %i' % len(self.snake[0][0].getFreeSeqNeighbors(0)))
818          for item in self.snake[0][0].seqNeighbors:
819              print('***seqNeighbor state %s' % item.state[0])
820          maxFreeSpace = max(value for key, value in self.freeSpaceForEachMove.items())
821          print('***Max free space: %i' % maxFreeSpace)
822  
823          # Make next move based on corner coil priority as long as > 80% of best free space is maintained
824          for tile in self.snake[0][0].getFreeSeqNeighbors(0):
825              # maxFreeSpace == 0 occurs when head chases tail closely, but move is safe
826              if maxFreeSpace == 0 or self.freeSpaceForEachMove[tile] / maxFreeSpace >= 0.8:
827                  self.moveHead(tile)
828                  break
829  
830      def run(self):
831          print('\n#%i' % self.iteration)
832  
833          self.iterationStartTime = datetime.datetime.now()
834  
835          # --------- Path Planning Algo -------- #
836  
837          # Find path to food
838          print('[Path To Food Search] - Start')
839          foodPathStatus, foodPath = self.pathfind.solve(self.snake[0][0], self.food, 0, 'PathToFood')
840          self.highlightPathSolution(foodPath)
841  
842          # If path to food is found
843          if foodPathStatus in [PATH_TO_FOOD]:
844  
845              # Generate board, 9, where snake has just eaten the food
846              self.snake[9] = self.getProjectedSnake(list(reversed(foodPath.copy())),
847                                                     self.snake[0].copy())    # Use copy of list
848              self.generateBoard(9, self.snake[9])
849  
850              # Check if path to food is safe and make it the next move if it is
851              foodPathSafety = self.checkSafety(9)
852              if foodPathSafety in [SAFE]:
853                  self.moveHead(foodPath[0])                                  # Next tile is first tile in solution
854                  self.messageUpdate('[Move Method] - Pathfind to Food', 'Path to Food', '#C6E0B4')
855  
856          # If no path to food found or path is found, but not safe
857          if foodPathStatus in [NO_PATH] or foodPathSafety in [NOT_SAFE]:
858  
859              print('[Recursive Search] - Start')
860              recursionStatus, recursionNextMove = self.recursivePrioritizedNeighborsCheck(0)  # Pass current board, 0
861              if recursionStatus in [PASS]:           # Recursively check all possible next moves by priority
862                  self.moveHead(recursionNextMove)    # Next snake head is the tile to move to when recursion hits break
863                  print('[Recursive Search][Safety Check] - Passed')
864                  self.messageUpdate('[Move Method] - Coil in Corner (Checked 8 moves ahead)',
865                                     'Coil in Corner - Recursive', '#FFE699')
866              elif recursionStatus in [FAILED]:
867                  print('[Recursive Search][Safety Check] - Failed')
868                  # No proven safe moves found, proceed by corner coil as long as it preserves >80% possible free space
869                  self.cornerCoilByMaintainingFreeSpaceGuessing()
870  
871          # --------- Core Mechanics -------- #
872  
873          self.checkTail()                                        # Check and remove tail if needed
874          self.checkFood()                                        # Check if ate the food
875          self.checkGameEndConditions()                           # Check for game end conditions
876          self.oVisualDebug = self.visualDebugSetting             # Frozen working copy of VisualDebug switch for iter
877          iterationTime = int((datetime.datetime.now() - self.iterationStartTime).total_seconds() * 1000)  # Milliseconds
878          delay = int(self.cycleTime - iterationTime)
879          if delay < 1:
880              delay = 1                                           # Must be at least 1 or error
881          self.iteration += 1
882  
883          if not self.queueStop:                                  # Check for game stop request
884              self.runStatus = RUNNING
885              self.root.after(delay, self.run)                    # Loop after delay milliseconds
886          else:
887              self.queueStop = False
888              self.runStatus = STOPPED
889  
890          if self.queueReset and self.runStatus == STOPPED:       # Check for game reset request
891              self.queueReset = False
892              self.reset()
893  
894  
895  # -------- Main -------- #
896  
897  if __name__ == '__main__':
898      root = Tk()
899      mainApp = clsMainApp(root)
900      mainApp.finishSetup()
901      mainApp.requestReset()
902      root.mainloop()
903  


Another version of the game programmed with VBA in Excel. Customized walls can be drawn and the algoirthm will avoid them.

  • #
    Figure 1
    Snake Game

    Snake game in Excel.