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:
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.
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.
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.
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.
Each frame the best cell to move to is calculated from the snake's head. Cells are scored like this (lower is better):
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!
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.