Snake game logic

Question

So I'm thinking about making snake game. I started thinking about it. I figured out almost everything, but I have found one fundamental problem I can not fix myself and I need your help. The logic here is simplified.

We have a grid 10 by 10. A snake is 3 segment long thing that occupies 3 sectors of the grid. I think of implementing the container for snake body as two-dimensional array. So if the snake is somewhere in the middle horizontally and we calculate position from lower left, it might be in positions array[5][5], array[5][6], array[5][7].

Now, to move snake we need to add another segment at the direction it moves and remove segment from its tail. For that we need int direction that holds 4 possible directions and two Structures each of which contains x and y coordinate of segment in array. We may set the length and coordinates of snake in the init steps. So we have structures preset for us at start. Lets imagine they are

Tail.y = 5, Tail.x = 5; Head.y = 5, Head.y = 7;

And the direction will be some arbitary number that we decided says it is east.

So when we move our snake, we look for head, check direction, and add a segment in that spot, and set our head struct to point at that spot. So our new head is array[5][8]. Then we check for tail. Our struct says its array[5][5]. We remove it from array. Here comes the problem with my logic. How do we get our struct to point on the last element of our snake that becomes a new tail?

Easy solution seems to check direction and look for segment next after last tail in that direction, but if our snake is not straight line it will fail.

I understand that my question is huge but it is all simple, just need some guidance.

The language I use is Objective-C.

EDIT:

As nobody suggested, I used NSMutableArray of CGPoints (wrapped in NSValue). I can freely add objects to array and remove from it. This way the first object is always head and the last object is always tail. It gets trivial at that point.

Answer 1

You could go for a linked list, as others suggested. But basically, a snake is just a FIFO stack (sometimes called a queue) of grid coordinates:

• When the snake grows one bit, you just push an element on top of the stack
• When it moves one square, you push an element on top and pop an element off the bottom

For an implementation of a queue in Objective-C, you can check this answer on SO, it seems OK by looking at all the upvotes.

Also, check this answer for some more snake implementation tips.

[self-promotion] Oh, and for an interesting snake implementation, you could check the source code for SnakeDemocracy! [/self-promotion]

Answer 2

Instead of implementing the snake as an array, why not implement it as a linked list, where each entry in the list is a point where the snake's body turns? For example, you could have the list {<5,5>, <8,5>, <8,10>, <12,10>} with <5,5> being the head, <12,10> being the tail, and the points in the middle being curves in the snake's body. Then when the player turns the snake, you only have to add a new entry to the front of the list, and when the snake moves you just update the tail until it overlaps the next point, at which time you remove it.

Answer 3

You don't actually need a linked list, nor any other complex data structure (outside of the board array itself) to do a snake game.

You just need certain pieces of information:

The head position, head direction, the tail position, the current length, and the maximum length.

Within each board cell, you must have a way to mark what type of segment is present.

I typically do this with either booleans or bitflags. Either work.

For ease of understanding, consider booleans. One for each of snake body segment present, connection to the north, connection to the east, connection to the west, connection to the south (thinking of a screen in terms of a map).

Next, when moving the head, you know which direction you are moving, so you add that directional connection to that board cell, you move the head, then you add the OPPOSITE direction connection. When you move the head, you add 1 to the length of the snake.

Example:

Head is at (5,5), direction south (+0,+1), snake length 4.

Add SOUTH flag to (5,5), move head to (5,6), add NORTH flag to (5,6).

Snake length ++ to 5.

When the length is greater than the maximum length, you find the tail, and it will have exactly one connection flag to another cell. remove that connection flag, then move the tail that direction, then remove the OPPOSITE direction connection.

Example:

Tail is at (2,3), connection to the west(-1,+0), snake length 5.

Remove WEST connection from (2,3).

Move tail to (1,3).

Remove EAST connection from (1,3).

Snake length -- to 4.

Hope this helps.

Answer 4

What I would do, is have a SnakeNode class, and mimic a linked list data structure.

For example:

class SnakeNode
{
    SnakeNode next;
    SnakeNode prev;

    public SnakeNode(SnakeNode next, SnakeNode prev)
    {
         this.next = next;
         this.prev = prev;
    }
}

You will know you are at the head if prev is null. The tail will be when next is null. Start at the head and move your way down to the tail, using your next/prev objects.

Doing it this way, it becomes trivial. Simply reposition them one by one working your way down the list.

Answer 5

The simple answer is that you need to track all of the snake's body positions, not just the head and tail. If the snake is always going to stay 3 segments long, you can stick to an array of (x,y) positions of length three.

When doing your movement logic, before you update the head with a new position, loop through the array from tail to head. For each position in the array, you need to change it to the next value in the array. So in some pseudo-code:

for(int i=snakeArray.length-1; i>0; i--)
    snakeArray[i].x = snakeArray[i-1].x
    snakeArray[i].y = snakeArray[i-1].y

You can then find the next position for the snake's head and set snakeArray[0] to that.

If you're going to be making the snakes grow and shrink a lot, then consider the linked list answers. Lists will make your life easier, but are not mandatory.

Answer 6

Why not have the value for the array[x][y] increment down to zero each update (move) where when you move the head of the snake you place down a value of the length of the snake itself. Using this you could search the board for the value 1 for the snake tail and a defined value for the snake head (-1). Upon an expansion of the snakes length just decide not to decrease the valued for the board that turn.