Finding a path for a 2D game in java

(first, sorry for the weak english)

there is a snake game similar to the Linux Nibbles game.

some of the features of the game !:

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

- there are four Snakes that 4 programmers have to write a program to find the Move method of them (each program is for one snake)

-time to solve the next move is 0.1 s, so we have to find it before 0.1 s, otherwise the snake will go to the previous direction.

-Press your head to avoid hitting walls or other snakes.

-Snake must not move backwards (he has a foul and has a negative point)


the coordination of the walls is given to us in the game (x, y). the combination of Other snakes is given to us at each cycle (0.1 s) of the game


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

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


You can see a screenshot of the game here:

Snake game


source to share

1 answer

Most people are going to suggest something like the A * pathfinding algorithm that is very well documented on the internet and I suggest you go and search for any of these suggestions. What you need to do is modify these algorithms so that they work well within the constraints you provided. (Suggestion A * and ignoring the 0.1sec limit is not very helpful).

There are several points I think you should consider

  • When looking for a path, you should not only view other snakes and walls as obstacles, but also your potential subsequent movements. You don't want the kite heads to bump into the next move. This may require tracking their heads.

  • You should limit your search for paths to a certain number of levels so that there is no time. If you are using 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 is potentially easier.

  • Point selection is not quite that trivial. For example, you shouldn't just pick the closest point because you are racing with other snakes. You should try to pick the points that you know or think you can get to them. You can simply measure the distance between the snakes and all points. Think that every other snake is trying to get closer to them and see if you can beat them because you are closer. Select the items that you think you can win.

  • If you think the obstacle is preventing any return movement.



All Articles