Snake AI

olus2000

Snake AI

olus2000

BBS

PICO-8 Cartridges

speedsnake_ai

by olus2000

Cart #speedsnake_ai-9 | 2022-05-11 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

This is an implementation of an algorithm that plays snake very well. It's based on a path through all board cells and calculated shortcuts to get more efficiency.

Controls:
X - show/hide the path

Menu items:
ALG - controls which variant of the algorithm is used.
SPEED - Snake's speed, lower = faster.
SNAKE - Change snake visualisation.

The path was generated based on a Hilbert curve. It would work with any path that goes through all board cells, but the Hilbert curve has some nice properties and looks.

I have implemented two variants of this algorithm here, togglable in the menu. "Tail" algorithm tends to follow it's tail very closely when it can't get directly to food. "Blocky" algorithm curls on itself until it has a clear path to food resulting in big patches of snake body later in the game. I believe "Tail" is more efficient than "Blocky".

Algorithm explanation:

General idea

If there is a path through all cells of the board the snake can just follow it forever. It will reach all the food and grow to the maximum size. It will be quite slow though, having to go through an average of half of the board's area to reach every food. It can be made quicker in the early game by making some shortcuts.

Path preparation

The path is described as a 16x16 grid of cells. Each cell stores coordinates of the next cell on the path. They are also assigned consecutive numbers from 0 to 255 according to their order on the path. Each cell will also store some metadata during the algorithm execution.

What shortcuts are allowed?

Obviously only shortcuts that get the snake closer to its goal should be used. In addition, to ensure safety, every shortcut should bring the snake closer to its goal on the path, meaning that every cell of path between the snake and its goal remains empty, and the path between the snake and its goal only decreases. A reasonable approach is to make steps that skip over as big parts of the path as possible, but that isn't efficient on a Hilbert curve path because sometimes following the path can lead to a larger skip than just taking every possible shortcut.

The goals

Another thing is deciding what the snake's goal is. If the snake always went straight for the food it would quickly run into itself and die. In order to ensure its safety it must never overtake its own tail on the path. This means that if the path is clear between the food and snake's head it can target the food, but if it isn't it has to find some other target while waiting for its tail to get out of the way. The 'Tail' algorithm the snake will target the cell right behind its tail (according to the path). This way it's trying to go as far as possible so it has a good start when the path to the food is finally clear. If the 'Blocky' setting is ON the snake will just follow the path until there's a clear way from it to the food and only use the shortcuts for getting to food.

The Algorithm

Each frame the best cell to move to is calculated from the snake's head. Cells are scored like this (lower is better):

If the cell already has a score metadata stored return that score.
If the cell is at the goal, score is 0. Save the score as metadata and return 0.
Set best score to 2000 (arbitrary big value more than the cells on the board).
For each neighbouring cell do:
a. It it's not between the currently evaluated cell and the goal on the path, ignore it.
b. Otherwise, get it's score using this algorithm.
c. If it's smaller then the current best score update the best score.
This cell's score is best score + 1.
Save it as metadata of this cell, and return it.

All cells adjacent to the snake's head that are further along the path are evaluated and the smallest one is chosen. Remember, the goal doesn't have to allways be the food, and the path should always be clear between the head and the goal, so choose your goals carefully!

Complexity and final regards

This algorithm has O(n) time complexity where n is the distance from the head to the goal, which is never bigger than the size of the board, so I would call that a good one. PICO-8 can process it at 60FPS for a 16x16 board. It also has O(n) space complexity where n is the size of the board, which is the same as the game itself.

My explanations tend to be all over the place, so if you are confused about anything feel free to ask!

Inspired by: Code Bullet (YT)

ai snake demo

P#111610 2022-05-10 13:32 ( Edited 2022-05-11 08:01)

Cowirrie

This is really neat. I'm sure you're right that the "Tail" algorithm is more efficient, but I find the "Blocky" algorithm quite mesmerising to watch. Really pumping music, too.

Would there be a lot of work to draw the snake body with shaped segments so we can see just how it's filling the space?

P#111644 2022-05-11 00:47

olus2000

I think it would actually be a bit hard. Currently the snake is stored as a list of cells without any info on their orientations, and is drawn as a series of squares. The game code comes from a speed-coding challenge I had with a friend (I got a time of 3:34) so it's not pretty or very efficient. It's deffinitely possible and would make the visualisation way better.

Edit: It was way easier than I thought! If I have a list of body segments I can draw the snake line as a series of rectangles between the segments. The 'outline' is the same, but the rectangles are large and light blue and they overlap a lot. No need for checking orientation and still 0 sprites used!

P#111656 2022-05-11 07:40 ( Edited 2022-05-11 08:08)

Cowirrie

@olus2000 : Thank you, that makes it look even neater, especially to show what the "Tail" algorithm is doing, and how the layout constantly shifts once it's mostly full. I'm glad to hear it wasn't too much work.

Thank you also for the time put into explaining it. It all seems to make sense.

P#111666 2022-05-11 10:05