How to find the point closest to most points when we have some blocks between them! (in 2D array - Snake Game)

Question

I am working on a snake game (Nibbles in Linux) played on a 60 * 60 field, with four snakes competing for an apple that is accidentally placed.

I implemented the movement of my snake using the A * (A star) algorithm.

My problem is this: when I will not be the closest snake to the apple, I do not want to go after the apple, because my chance of getting it is lower than at least one snake, so I want to find a place that I hope in the next the place where the apple will be created, Then I will be the closest snake to this apple. I mean, I'm looking for a place that is closest to the maximum number of potential places.

Please suggest any good way or any algorithm that will help me find this place.

Here is a picture of the game. Red dots are the heads of snakes.

Answer 1

I tested several methods and finally decided to use this method:

I think the best way is to create a 2D array with a size: 60 * 60, then for each node (x) array, calculate how many field nodes are walkable! (not block), this is the node (x) closest to.

then the answer will be max, then I set the target to node.

but due to the fact that I have to find the following movement in less than 0.1 seconds, and there are 4 loops of size to do this job: 60, (60 ^ 4), and when I find it, the A * algorithm will run, this job will never will not be executed in less than 0.1 s.

So, since the Snake cannot move diagonally, and it goes simply: up, down, right, left, I decided not to check all the nodes, since in each cycle (0.1 sec) I can just move 1 unit, I decided check only 4 nodes (up, down, left, right) and go to node whose size is Max.

Now it works almost correctly .;)

Answer 2

If you are closest to the apple, you should walk to get it, but if you are far from the apple, your best chance is in the middle of the map, you should find a strategy to take the middle of the map.

You can divide the map into four scaling (clockwise), upper left, upper right, lower right and lower left (1,2,3,4). We check this between two snakes: if the apple is currently on an enlarged scale of 1 (suppose the average is average) and you are in the center of the map, your opponent may be on a scale of 1,2,3,4 (again suppose that it is at the center of this scaling to average more easily) if it has an enlarged scale of 1, it has a better chance (1-0), if it has an increase of 2 or 4, your distance is sqrt (2) / 2, and the distance your opponent is 1, so you are closest, and finally, if your opponent is 3 on a larger scale, your distance is sqrt (2) / 2, and the distance of your opponent - sqrt (2), so in 3 cases, with one opponent you have a better chance.

But since your figure has several blocks, you must calculate the center position in a different way, in fact, for each point in your grid, its distance to all other points is calculated. it takes 60 ^ 2 * 60 ^ 2, which can be done quickly. and find the cells with the minimum amounts (you can choose the best 10 cells), these cells can be your centers, every time you have to move from one center to another (except when you are closest to an apple or your snake eats an apple and wants centers).

Answer 3

Since you have already implemented A *, after creating the map, you can use A * to create a map of values ​​for each cell based on the total cost of each cell to visit each other cell. If you create this after placing your blocks, your weighted map will take into account their presence.

To generate this, from my head, I would say that you can start with each cell and assign it one point for each cell that it can visit in one move. For example, a cell in the corner will receive two points for the first move, because it can only access two other cells. He will get five points in his second move, because he can get access to five cells in two moves. Repeat until you have visited all the other squares and then you have an estimate for that square.

From this moment, if an apple appears and your snake is not closest to it, your snake can go to the cage with the highest weight that you calculated in advance.

Edit: see comments below for a better solution.

Answer 4

The closest to the maximum number of places is the center, as others have indicated. Questions related to more places than other snakes are much more different questions. In this case, I had to lead each snake to see who controls most of the squares. This is a basic account. Then, when I draw a space, I would use a Monte Carlo random set of points around the map and select the point that gave the highest score as the destination. If you have the processing power, you can try every point on the grid and choose the best one, as KG suggested, but it can become quite intense.

The true test is when you find your point of view, find out how far in the future you will need to get, and run some AI for other snakes to see if they will intercept you. You start to fall into layers, like in chess. :)