Subscribe to MentalFloss Minutes        RSS Feed
-----

Design: Snake

Icon Leave Comment
I saw a couple posts about the Snake game recently, and I realized that I've never actually tried to tackle this game. This post is only about design, so if that idea doesn't interest you, feel free to skip this entry.

Alright, so Snake is played on a grid of W,H where W = some width and H = some height. A snake segment is a 1x1 cell at position (x,y). The head moves through the grid and changes direction in two ways (left, right) or continues in the direction it's facing until x >= W or x <= 0 or y >= H or y <= 0 or there is a collision with its own body.

Randomly, a food item spawns with size 1x1 somewhere on the grid. If the head of the snake collides with the food, then the number of segments of the snake increases by 1, and that increase is applied at the end of the snake. There are two choices here. We can apply it after the tail or directly before the tail. Let us consider the following model for a snake of length 3 that just ate a food item where H=head, B=body, T=tail, N=new:

STEP 0:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | |T|B|H| | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+

Spawn new segment between tail and body:
STEP 1:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | |T|N|B|H| | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+

STEP 2:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |T|B|B|H| |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+

Spawn new segment after tail:
STEP 1:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | |N|T|B|H| | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+

STEP 2:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |T|B|B|H| |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+




Both methods are viable, and the answer depends on whether or not the tail is a special entity component of the snake or not. If so, then we wish to preserve the tail, and go with option A. Otherwise, it would make more sense to simply tack on the new piece at the end of the snake with option B. Further analysis is required.

We assumed that we can spawn a snake with three segments initially. So, is that true? Moving the snake should tell us. We will consider orientations symmetric to cut down on possibilities. However, we have a new problem. Do we move the snake forward and then turn or do we turn and move forward?

STEP 0:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | |T|B|H| | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+

Moving forward and then turn:

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | | | | | |H| | |
+-+-+-+-+-+-+-+-+-+
| | | | | |T|B| | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+

Turning and then moving forward:

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | | | | |H| | | |
+-+-+-+-+-+-+-+-+-+
| | | | |T|B| | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+




Here we can clearly see that by moving forward and then turning we have displaced the tail by two cells instead of 1, which means that we should be performing a turn and then move forward.

Let's consider a longer body of 5, where the segments are lettered A-E.

STEP 0:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
|E|D|C|B|A| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |A| | | | |
+-+-+-+-+-+-+-+-+-+
| |E|D|C|B| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 2:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |A| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |B| | | | |
+-+-+-+-+-+-+-+-+-+
| | |E|D|C| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 3:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |A| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |B| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |C| | | | |
+-+-+-+-+-+-+-+-+-+
| | | |E|D| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 4:
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |A| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |B| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |C| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |D| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |E| | | | |
+-+-+-+-+-+-+-+-+-+



So, we see here that a turn creates a heading. If we have each turn stored at a certain point with a configured heading, then every piece that touches it will keep that heading.

Let's look at that in more detail with just body piece following a head that has turned (R,L).

STEP 0:
+-+-+-+-+-+-+-+-+-+
| | | | |R| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |B| |L| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | | | |R| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | |B|L| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 2:
+-+-+-+-+-+-+-+-+-+
| | | | |R| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |B| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 3:
+-+-+-+-+-+-+-+-+-+
| | | | |R| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |B| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |L| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 4:
+-+-+-+-+-+-+-+-+-+
| | | | |B| | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |L| | | | |
+-+-+-+-+-+-+-+-+-+

STEP 5:
+-+-+-+-+-+-+-+-+-+
| | | | |R|B| | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | |L| | | | |
+-+-+-+-+-+-+-+-+-+



Then, it would be the case that the tail is a special component, since passing over a heading with the tail should delete the heading. Therefore, going back to spawning new segments, we want to spawn between the tail and body instead of spawning after the tail and moving the tail.

To summarize: The head creates a heading at the turn of x,y, and every body segment passing over the heading maintains that heading, and the tail passing over the heading maintains that heading and deletes the heading.

Let's consider collisions with the body now. We have near-misses and actual hits to think about. Let's consider a long snake where the head is to collide. We don't currently care about the movement of the rest of the snake. Pretend it's very long and off-screen. This is just a segment of screen.

STEP 0:
+-+-+-+-+-+-+-+-+-+
| | |X| | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |X| |H|X| | | |
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | |X| | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |X|H|X|X| | | |
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+

STEP 2:
+-+-+-+-+-+-+-+-+-+
| | |X| | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |H|X|X|X| | | |   DEAD
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+



And rewind to see the near miss:

STEP 0:
+-+-+-+-+-+-+-+-+-+
| | |X| | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |X| |H|X| | | |
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | |X| | | | | | |
+-+-+-+-+-+-+-+-+-+
| | |X|H|X|X| | | |
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+

(player presses UP)

STEP 1:
+-+-+-+-+-+-+-+-+-+
| | |X|H| | | | | |
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+
| | |X|X|X|X| | | |
+-+-+-+-+-+-+-+-+-+



And as it turns out, collisions with the body would be very straight-forward.

Summary

We would create a grid with each cell size equal to one segment of snake, and spawn the snake with a Head, a sequence of Body initially equal to 1, and a Tail where Head is at (x,y), body is at (x-1,y) and tail is at (x-2,y) with some food item at (rand_x,rand_y) under stipulation that food != any part of snake.

Then we would start game loop. If no input, each segment applies heading until collision with walls. If input, we store current position of head.

Algorithm

At this point, we can establish a game loop algorithm, since all factors are known.

INIT:
    spawn snake head at (W/2=x, H/2=y)
    spawn snake body at (x-1, y)
    spawn snake tail at (x-2, y)
    spawn food at (rand_x, rand_y) where food != snake{head, body, tail}
    directions:{ UP=(0,-1), DOWN=(0,1), LEFT=(-1,0), RIGHT=(1,0) }

LOOP:
    while snake.alive:
        UPDATE:
            IF USER_INPUT:
                snake.head.direction = directions[input]
                add heading (snake.head.x, snake.head.y, snake.head.direction)

            // We change the direction of every part of snake that is currently on a heading marker
            FOR EACH segment in snake:
                FOR EACH heading in headings:
                    if segment == heading:
                        segment.direction = heading.direction

            // We change the direction of the tail, and delete the heading
            FOR EACH heading in headings:
                if tail == heading:
                    tail.direction = heading.direction
                    remove heading
                    break

            // This moves each part of snake except tail in its designated heading based on last heading marker it passed over
            Apply each heading to each snake segment

            // Collision detection hand-wave:
            if snake.head == any part of snake or any wall:
                snake.alive = false

            // Added food makes new food, and will grow the snake
            if food == snake.head:
                snake.food++
                delete food
                spawn food at (rand_x, rand_y) where food != snake{head, body, body*, tail}

            // When there's food, we don't move the tail, but use the tail to create a new piece.
            If snake.food != 0:
                Create segment at (tail.x + tail.direction.x, tail.y + tail.direction.y)
                Set segment's heading to tail.direction
                snake.food--
            else:
                Apply heading to tail.

        RENDER() // not shown




And that should be enough to code the game. I guess I probably will code it in the coming days because why not? It's mostly designed anyway.

Regardless, this was my attempt at designing the Snake game. Hope it was fun.

0 Comments On This Entry

 

October 2019

S M T W T F S
  12345
6789101112
13141516171819
2021 22 23242526
2728293031  

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)