Monday, September 10, 2018

algorithm - How to find a safe path for an AI snake?


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?




No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...