Path finding for 2D game in java [closed]

Question

(at first,sorry for my weak English)

there is a snake game that is like to "Nibbles "game in Linux.

some of the game features!:

-the board is in a 60*60 field, surrounded by walls, and there are some walls in the board too.

-there are four Snakes that 4 programmers must write a program for finding the Move Method of them.(each program for one Snake)

-time to decide the next move is 0.1sec, so we must find it before 0.1sec, otherwise, snake will go to the previous direction.

-Snake's head must not hit the walls or other snakes.

-Snake must not move backward(it's foul and has negative point)

...............

the coordiation of walls is been given to us at the game(x,y). the cooardiation of Other snakes is been given to us at every cycle(0.1sec) of the game

................

now the question is : how to find the best move?

can you please help me by suggesting any algorithms or ...?

Thank you.

You can see a Screenshot of the game here:

Answer 1

Most people are going to suggest something like the A* path finding algorithm which is very well documented on the web and I suggest you go and search for any of these suggestions. What you do need to do is modify these algorithms so that they work well within the constraints you have been given. (Suggesting A* and ignoring the 0.1sec limitation isn't very helpful).

There are a few points that I think you should consider

• When you are looking for a path, you should consider not only the other snakes and walls as an obstacle, but also their potential next moves. You don't want the snake heads to collide on the next move. This might require tracking their heads.

• You should limit your path search to a certain number of levels deep so that you don't run out of time. If you use the A* algorithm, you should find that the heuristic element will cause most paths to take you in the direction of the point you want to go to. So if you get closer, the next search will potentially be easier.

• Point selection isn't exactly that trivial. For example, you shouldn't just choose the nearest point, because you are racing other snakes. You should try to choose the points that you know or think you can get to first. You could simply measure the distance between the snakes and all of the points. Consider that each other snake is attempting to go for the closest point to them, and see if you can beat them because you are closer. Pick points you think you can win.

• Considering yourself an obstacle prevents any backwards moves.