Robbie Wolfe | Programming > Snake AI Search

Robbie Wolfe | Programming > Snake AI Search

Snake AI Search

For my fourth year Artificial Intelligence course, our first assignment was to implement the classic game Snake. The hard part was then to implement three different search algorithms so the snake will find the food by itself. The modified rules for the game were that there could be obstacles, and the snake wouldn't grow. For fun, I retained the original game's functionality of the snake growing when it ate food. The three search algorithms were Breadth First Search, Depth First Search, and A* Search. Each algorithm has its own advantages and disadvantages, which will be described.

I made the game highly customizable. You can change the grid size, the number of food pieces at a time, and the number of obstacles. You can speed up or slow down the animation rate. You can either play the classic game (uncheck "Custom Game"), or use the custom rules. You can turn on or off if the snake grows or not. Be aware that the algorithms get very slow if the snake gets too large or if the grid is too big. You can move the snake with the arrow keys or use one of the algorithms. You can have the game go on autopilot so you don't have to click an algorithm each time it finds a piece of food. Debug mode shows you the orientation of the snake with arrows.

State Space

A search algorithm in a game requires there to be a State Space. This is a snapshot of the game, which can be used to determine if the search is approaching the goal or not. The algorithm creates a tree of nodes, each containing a State and a value. This value is used to determine how far away the goal is. Once a goal is found, the path from the root of the tree to the goal is the solution.

Read full article from Robbie Wolfe | Programming > Snake AI Search