# Implementing movement on a grid

I have a simple snake game, where I have other NPC snakes on the field. How do I calculate the movement of those other snakes so that they did not hit walls, and each other?

So far I have it like this:

I check for current coordinates and when there is a wall nearby I change direction to some other one. And so on, this way the snakes never collide the walls.

But not actually colliding other snakes, how do I prevent this?

I figured I could probe for the direction I'm heading and if there is anything there I would change direction too, but there is a set of situation where this won't work, for example if another snake will block off all exits later.

• Short answer - you can't, especially in the case of completely random NPC movement. Long answer - you can have NPCs solve for a free path and collaborate to prevent boxing each other in. The moment you add a non-collaborating snake, though (that is, the player), things start to go out the window, and snakes may have no free spaces left... Commented May 27, 2014 at 11:32
• @Clockwork-Muse My game field is very large and I doubt that there is real opportunity for a player to block enemy snakes, since snakes are short and have similar move speeds. Commented May 27, 2014 at 11:38
• You're going to need to write a decent AI, then, capable of planning sufficiently far ahead so as to not be blocked by the player against the wall or themselves. Commented May 27, 2014 at 11:44

I can't think of a way to make it work 100% of the time but you can make the snakes choice more likely to be the best.

## Easier way

You can calculate which side of the snakes has more free squares. For example (see image below) with the snake 1. You can calculate that there is only 4 free squares on the right and much more on the left so it should probably go left.

An easy way to calculate the number of free squares would be with a recursive function. Pseudo code:

int num_free_square(positionX, positionY)
{
int num = 1;

if (arrayMap[positionX+1,positionY] == FREE)
{
num += num_free_square(positionX+1, positionY)
}

... same for each direction

return num;
}


(You would of course have to check if each square has already been counted and if you don't access space outside the array)

## Harder way

The previous solution is far from perfect. For example, on the following image the snake 1 would go right because there is only 1 square free on the left and 4 on the right. Although the next snake 3 move would have freed the path.

The solution could be to calculate the number of move the snake 1 would be able to do if the other snakes were changing direction randomly after meeting a wall. Before choosing a direction you calculate the deplacement of all the snakes during few moves.

This would require a lot of computation but you could stop at 10 moves for example and say : if the snake can go 10 moves on both way then I pick a random direction, else I go to the direction with the highest number of move. Although the choices of the other snakes will probably not be what you planned so the snakes will still be able to block each other.

• To add to this idea: a square S is only blocked for snake A by snake B if the Manhattan distance for A to S lower than the number of segments of B that still need to traverse through S Commented May 27, 2014 at 11:50