6

I am working with a uniform cost grid that only allows movements in the orthogonal directions. This is used as a base for the game snake where the snake must constantly move and try to eat apples on the board. The location of the food and collision avoidance is done using the classic AStar algorithm to find the shortest path between the snakes head and the food. However, this method sometimes results in the snake going for food that causes it to have no clear path to the next food. The snake ends up stuck in an irregularly shaped rectangle and has no future simulation at this point.

My question is this: Is there a way to find the longest chain of moves inside the irregular rectangle in order to stay alive longest and possibly have the tail of the snake stop blocking the path to the next food? I have looked at Hamilton Algorithms to try to visit all the nodes but it seems that there is no solution for irregular shapes. The solution need not be perfect but it should always try to give the snake the best chance of escaping from the trap.

Any thoughts?

peterSO
  • 158,998
  • 31
  • 281
  • 276
Cobey Hollier
  • 61
  • 6

1 Answers1

0

board[][] (Lets consider board as a 2D array)

now mark board[i][j] = 'S' for the cells occupied by your snakes

Mark board[i][j] = ' ' (empty space) for free cells

now your A* should give you a path from head of your snake to the food. Mark all the cells in this path to '#'. (Optional : Unmark n-1 number of 'S' cells from the tail of the snake where n is the shortest path from snake's head to the food. This is because after n steps, the snake's tail would also have moved)

Now for all future positions (take some 10 random empty points in the board) see if you can reach all these positions from the food position using only the empty space cells. (You can do this in a single DFS). If you are able to visit, then it's safe to use the path you chose. Otherwise, take a different path.

cegprakash
  • 2,937
  • 33
  • 60