6
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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:

Hamiltonian circuit

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:

shortcut 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
\$\endgroup\$
  • \$\begingroup\$ Hey thank you so much for putting your time and effort into this answer. I have tried many things. I think I have even looked at that project. I have not solved all my issues regarding making the snake competitive and safe but i have managed to make it last longer. In this video: youtu.be/vg2k24SuX5k you can see my progress. I have stopped working on it due to other school work and project. I will try to resume my work now during the summer break. Once again thank you and I will look into the halmintonian circuit a bit more in detail and also look into the provided git project :) \$\endgroup\$ – Eudy Contreras Jun 5 '17 at 6:00
-1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.