Part 2: Snake AI

BFS and DFS

You’ll be doing breadth first search so it’ll be important to get familiar with the concept. Read the following paper that goes over what you’ve trying to do and also gives a comparison between breadth-first and depth-first.

BFS vs. DFS

Artificial Intelligence

We’ll try to give our snake some intelligence. By using BFS, we can search through the possible available paths and we can pick which path will work best.

In SnakeProBrain.java:

Write the method getNextCellFromBFS(), which returns the BoardCell on the path to the nearest food. This method only tells us which is the next move that we should do, it doesn’t give us the WHOLE closest path. Essentially it tells us whether we should move N, W, S, or E next.

How does it do that? Well it keeps a Queue (watch this video) which holds the cells we want to search next. The order of how things are enqueued and dequeued is very important and will determine if BFS is being used.

Lets image a snake head trying to make a decision of where to go next. Well, we need to find the food first. Should we search NWSE, in that order, or should be start at E and go W then N the S? The order in which you search will determine whether you’re use BFS or not.

Let’s say we chose to look at the N cell first, then we’ll continue looking at each cell in the Queue until we find the food, dequeueing in the appropriate order. Once we find it, we need to backtrack and figure out which is the first cell in the path to the food.

Here are some useful methods that you should look at:

Boardcell:

• setParent
• getParent
• among others

Queue:

• dequeue (in java .poll() is used)
• enqueue (in java .add() is used)
• remove()
• peek()

SnakeProBrain:

• getFirstCellInPath()
• any other helper methods you want to add are allowed

Testing

• SnakeProBrainTest_CheckParentsBFS.java 
  • This test file uses a method of “clear-box testing”, where we look inside the structures (here we look at the parent references of BoardCells) to make sure that the algorithm is behaving as intended.
  • These tests assume the BFS algorithm as described in the paper, which does not stop until a target (food) is dequeued.  If you prefer to implement a “more efficient” version that stops immediately when food is first discovered (rather than waiting for that food to make its way to the front of the queue), you will need to run SnakeProBrainTest_CheckParentsBFS_fast.java.
  • Either version is perfectly acceptable.
• SnakeProBrainTest_GetNextCellFromBFS.java 
  • This test file uses a method of black-box testing, where we just test the functionality of the methods without needing to know the algorithm or data structures used.