Snake AI

You can find the code for this project on my github.
Sample output can be found below the project description.

 This project was created to better understand of the AI Q-Learning algorithm and how it compares to the classic A* algorithm. The idea was to create a simple game of snake from the ground up in C++ and have the pathfinding algorithms determine how the snake should move. I chose to use the command line and terminal output to display the board state instead of a GUI to keep things simple and within scope.

 There is one clear limitation to my implementation. The path calculation is done at the start of the program, and each time a new apple is generated. This means the snake 'thinks' the apple is unreachable if its body is temporarily blocking its path at the time of generation. This can be fixed in future version should I chose to develope this further. One potential fix would be to recalculate the optimal path after each step, and pair that with moving towards the tail of the snake instead of giving up.

Q-Learning

 This algorithm appears to play more like a human than the other ones, at least in my opinion. The snake will take what seems like a middle ground between the direct diagnoal path of Euclidean distance A* and the block pathing of Manhattan distance A*. The clear downside is that the calculation takes some time to process which is why you can see the snake pause after eating each apple.

A* with Euclidean distance

 This algorithm is running using the Euclidean distance metric, which will translate into the snake taking a more diagonal path through the grid. In my test for this showcase, this algorithm scored the highest, but I want to note that there is a lot of variance due to the apples being generated randomely. This run just happened to get lucky with apple positions.

A* with Manhattan distance

 This algorithm is running using the Manhattan distance metric, which translates to a blocky type of movement. The snake will move over to the correct column, then go right up or down to the apple with minimal diagonal movement.