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):

1. If the cell already has a score metadata stored return that score.
2. If the cell is at the goal, score is 0. Save the score as metadata and return 0.
3. Set best score to 2000 (arbitrary big value more than the cells on the board).
4. 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.
5. This cell's score is best score + 1.
6. 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.