How to find a safe path for an AI snake?

Question

I have been working on a game in which a player can compete with a snake ai to get the most apples. The current path finding technique i use (A* Pathfinding) works fine. But I am struggling with coming with an effective way to make sure that the AI snake does not go for an objective that leads to it trapping itself. Consider that the snake can teleport and that there may be max 4 apples on the map at any given time. The decision tree I am trying to create looks somewhat like this:

• If path to goal is safe : go for apple!
• Else check next apple until a safe path is found or all apples are checked.
• If no path to any apple is safe including the paths produced if teleportation is possible, Then find the farthest path to the tail and remain chasing the tail until a safe path to an objective becomes available. If no path to tail is found : stall until death!

The problem is that it is really hard to find a fast and efficient way to determine if a path is safe!

My question is: what is a good way to determine if a path into an enclosed area is safe given that you cannot take the same path back out of that area?

Answer 1

Take a look at https://github.com/stevennl/Snake, a project demonstrating a few AI algorithms for the game Snake. The project README has a very nice explanation of the algorithm.

The key is for the snake to follow a Hamiltonian circuit (a path that visits every square, and loops back on itself). Many such paths exist for a simple 2D grid, you just have to find one. So something like this:

Finding such a path is also known as the longest path problem. If you make your AI follow this circuit, it will never trap itself and will be able to grow to the largest size possible - filling the entire grid. If you're lazy you can stop here - your AI doesn't even need to care where the fruit is. Of course, this AI will be horribly slow, and maybe boring to watch.

To make the snake faster at eating fruit, you can make it take shortcuts within the Hamiltonian circuit, as long as taking such shortcuts won't make its head overlap its body after taking the shortcut. Here's an image covering the key points:

https://johnflux.com/2015/05/02/nokia-6110-part-3-algorithms/

This algorithm is much better, but still not the best, since it is still following the original Hamiltonian circuit. It's possible that finding other circuits will allow it to take better shortcuts.

Other things that can complicate the algorithm include:

• Grids with obstacles; these can really complicate the longest path algorithm
• Multiple snakes

Answer 2

I assume this is in 2D,

Wouldn't this be doable with iterating? Like, generating a straight line from snake head to goal. Then checking the line for errors, like if there's an obstacle in the way, then create a midpoint that dodges the obstacle.

Like, this: https://www.youtube.com/watch?v=-L-WgKMFuhE

But after you find the path, do two things: 1. With the current state, check if the goal is in an enclosed space with the snake, like the snake is the lid of the jar (terrain) that surrounds the goal. Then confirm there's enough space to jam the snake in there and coil it out. 2. Simulating the "head touches goal in most efficient path", check if you generated a jar, like in (1.)

Either way you'll need to do a lot of pixel crawling, unless you index everything somehow. But with modern day processing power, I doubt you'd need any indexes or optimizations.

I trid to help.