I was thinking about how to implement snake today, in particular, how to ensure the snake moves optimally from one target to the next.
This seems like a shortest path problem, but it's a bit tricky because you have to keep track of the snake's body positions for every node in the BFS traversal, which could take up a lot of memory. Is there a better approach than what I'm envisioning here?
The problem isn't getting to the apple, it's making sure you have an escape route after eating the apple.
[Edited for clarity, comments may not make sense]
What you're looking for is a Hamiltonian cycle (a single, continuous path that passes through every square on the board). It's the only way to guarantee you won't trap yourself, but finding an optimal one is non-trivial.
The YouTube channel AlphaPhoenix has a fantastic video detailing the various problems and optimisations.
AlphaPhoenix: How to Win Snake
At a high level, you need to ensure you always have a Hamiltonian path, so you can never get stuck.
Then you need to
To explain why you always need the cycle, here's part of two frames from the linked video
To start with, heading straight to the apple makes sense.
But when you actually turn in to bite it, you can trap yourself in a dead-end.
If you're using a pure BFS approach, the obvious move is "down", directly to the closest apple.
Unfortunately, that would be a game-over situation in 2 more moves.
For a BFS-approach to work, you'd need to find paths that lead not only to the apple but also to every free square on the board (accounting for snake movement in the interim) and track/choose the one with the shortest distance to the apple.
To be explicit: Any path that can't also reach every square after collecting the apple has to be rejected before you can pick a safe path.
That means your breadth-first search has to reach maximum depth in all cases.
I believe you'll find that's computationally infeasible in anything even close to real-time.
For every node occupied by the snake, you can compute in how many steps it will be freed. So if you keep track of how many steps you are doing in your path search, you can compare that to know if the node would be occupied when the snake reaches it.
Addendum: You might be worried about nodes occupied by future movement of the snake, but if your reach algorithm does not create paths that repeat nodes to begin with, then that is not a concern.
