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.

A State in my snake game consists of the following:

		public Point snakeHead;
		public LinkedList<eDirection> snakeOrientation;
		public LinkedList<Point> foodLocations;
		public LinkedList<Point> wallLocations;
		public boolean isDeadState;
		

First is the location of the snake head. Next is the orientation of the snake. For example, the initial state of the snake is [LEFT, LEFT, LEFT, LEFT, LEFT]. It is the direction to the next body part of the snake, starting at the tail. It is also the direction to move that body part, if the snake moves forward. The tail can be inferred from the head/orientation, so it isn’t stored.

The game allows for multiple food locations and wall locations. Thus they are stored as lists.

A state is considered dead if the head is equal to any of the wall locations, the border of the game, or another part of the snake body itself. A state is considered a goal state if the head is equal to any of the food locations.

Two states are equal if any only if all of the above properties are equal. Thus, two states that have the same snakehead/foodLocations/wallLocations, but a different orientation, are considered different. This allows the snake to move on the same spot more than once, but in a different orientation. Although this makes solutions sometimes longer (in the case of DFS), it allows the snake to get “unstuck” if it is trapped within walls, but can reorient itself towards the goal.

Search Algorithms

1. Depth First Search

Finds an extremely long path to the food. However, it expands the least amount of nodes, so it is one of the quicker algorithms to execute.

2. Breadth First Search

Finds an optimal path, however it expands a very large amount of nodes and takes longer than DFS.

3. A* Search

Based on a heuristic, finds the optimal path. It expands a low amount of nodes but can take longer than the other algorithms. Three different heuristics (as well as the average of one with another) were used as an experiment to see which was better.

Heuristics

1. Euclidean Distance

Takes the snakehead and returns the minimum Euclidean distance to one of the food locations (square root of x^2+y^2). This heuristic is ensured to be less than the actual distance.

2. Manhattan Distance

Takes the snakehead and returns the minimum Manhattan distance to one of the food locations. This is involves going in a straight line horizontally and vertically (instead of diagonally). It was chosen because it is the simplest path the snake can take, and is always possible (unless there is a wall in the way)

3. Direction Rank

This involves determining if the direction this Node is moving is in the general direction of one of the food locations. If it’s going away from it, it returns a larger value. For example:
Moving down, and numbers represent where the food is and its rank

454
3D3
212

So if the food is UP and you are moving DOWN, return largest value. If it is DOWN and to the LEFT or RIGHT and you are moving DOWN, return the second smallest value, etc.

This heuristic was chosen because it logically makes sense. If you are headed in the direction of the food that is good, if you are headed in the opposite direction that is bad.

Comparison of Heuristics

Heuristic Min Nodes Expanded Average Nodes Expanded Max Nodes Expanded
Distance 2 1047 10740
Manhattan 4 153 1039
Direction 3 7949 24149

As you can see, the best heuristic in terms of node expansion (ie: speed) is Manhattan, and the worst is Direction.

I have uploaded the source code for your reference. You can download it here.

The game was made as a playable applet, but the libraries I used aren't working when on the internet. To play it on your computer, download this folder which contains a webpage that allows you to play the applet. I have to resort to this method until I can find a fix. Below is a screenshot.

Your screen resolution is too small to display the screenshot. Here is a link.

Snake AI Search