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.

  • #
    Figure 1
    Snake Game

    The blue square represents the snake's head and the green square represents the food. Gray segments represent the snake itself.

  • #
    Figure 2
    Snake Game - Running

    Running autopilot algorithm. Algorithm pathfinding mode and safety check mode are shown in the top right corner.

  • #
    Figure 3
    Snake Game & Algorithm Visuals

    Autopilot algorithm visuals are shown. The green box represents the start of the pathfinding algorithm and the red box represents the destination. The blue circles show the explored free nodes. The grey circles show the frontier nodes that have not been explored yet.

  • #
    Figure 4
    Snake Game & Algorithm Visuals - Running

    Autopilot algorithm visuals can be enabled at any point by toggling the 'Visuals' button.

  • #
    Download
    Python Code & Executable

    Download the Snake game program source and executable.

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


Excel VBA Version

Similar version of the python game except it is programmed with VBA in Excel. Customized walls can be drawn and the algoirthm will avoid them.

  • #
    Figure 1
    Snake Game

    Snake game in Excel.