I thought it would be fun to make a one-shot snake game project to familiarise myself with the ncurses library and play around with some data structures, which led to this ripoff snake game you can find on my GitHub.

If you’re interested, you can take a look and perhaps give it a go!

The following sections of this post are just some code discussions for the nerds.

Building Cnake

I won’t talk too much about the ncurses library and will be writing more about the things I found interesting while building this project, mainly, these questions I had to answer while making the game.

How can I track where the snake is?
How do I handle input and movement?
How do I increase the length of the snake?

How can I track where the snake is?

The first thing that came to mind is to use a 2D matrix (int[N][M]) that corresponds to the x,y coodinates of the playing field. We can assign numbers to each array element to represent something such as 0 for empty, 1 for snake, 2 for food, 3 for border, etc.

On second thought, that’s not the fastest way of doing things. If I were to try and figure out where all the ‘Snake’ cells are, I would have to iterate through the ENTIRE matrix. If not that, I would have to conjure up some overcomplicated way of finding all the coordinates using a matrix.

Enter: Linked Lists. I don’t need to know where everything is. I just need to know where the important things are. Linked Lists would be the most intuitive way to track the snake. Conveniently, the linked list nodes can hold data (x,y coordinates) as well as references to the adjacent nodes. So, instead of having to iterate through N*M cells of the playing field, I just need to iterate through the length of the Snake to figure out where all the pieces are.

What this looks like…

0
1
2
3
4
5
6

// Doubly Linked List
struct SnakeCell{
    int x;
    int y;
    struct SnakeCell* next;
    struct SnakeCell* prev;
}

Displaying the Snake is as trivial as iterating through the linked list and using each node’s x,y data to populate a ncurses window. The following code describes how I initialised the Snake linked-list with an initial length of initialSize.

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Snake's head has been instantitated earlier on
struct SnakeCell* init_snake(WINDOW* window, struct SnakeCell *head, int initialSize){
    struct SnakeCell *cell = head;

    // Populate the linked list
    while(initialSize-- > 1){
        struct SnakeCell* newcell = malloc(sizeof(struct SnakeCell));
        cell->prev = newcell;
        newcell->next = cell;
        newcell->x = cell->x-1;
        newcell->y = cell->y;
        cell = newcell;
    }

    // Initialise the final node's prev pointer
    cell->prev = NULL;
    // Return the tail of the snake for manipulation later on
    struct SnakeCell * tail = cell;

    // Populate the game window (ncurses)
    while(cell != NULL){
        mvwaddch(window, cell->y, cell->x, '#');
        cell = cell->next;
    }
    wrefresh(window);
    return tail;
}

How do I handle input and movement?

The snake moves in 4 directions. The directions can be mapped to WASD/Arrow keys. I need to scan for these inputs and ignore any invalid key inputs. There’s also a potential issue where the user accidentally makes the snake go ‘backwards’. Meaning, when the snake is moving up, the user inputs down, when the snake is moving left, the user inputs right. These inputs are also invalid as the snake will collide with itself and should be ignored.

To handle movement logic, I have two variables that deal with direction. inertia and input. The latter is the raw stdin input from the user and the former the Snake’s last moved direction.

Parsing input: If we get a bad input, we ignore it and let the snake carry on with its current direction of motion (inertia!). Else, we update the snake’s inertia.

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

const int DXN_UP = 3, DXN_DOWN = 5, DXN_LEFT = 2, DXN_RIGHT = 4;

// inertia = parseInput(...);
int parseInput(int input, int inertia){
    // Return -1 if quit is pressed 
    // UP/DOWN will always give a remainder of 1 when %2
    // L/R will always give a remainder of 0 when %2
    // Use this to check if the input should be ignored (snake carries on with its inertial dxn)
    switch(input){
        case 'q':
            return -1;
        break;
        case 'w':
        case KEY_UP:
            return (inertia%2 != 0)? inertia:DXN_UP;
            break;
        case 's':
        case KEY_DOWN:
            return (inertia%2 != 0)? inertia:DXN_DOWN;
            break;
        case 'a':
        case KEY_LEFT:
            return (inertia%2 == 0)? inertia:DXN_LEFT;
            break;
        case 'd':
        case KEY_RIGHT:
            return (inertia%2 == 0)? inertia:DXN_RIGHT;
            break;
        default:
            return inertia;
            break; 
    }
}

How do I increase the length of the snake?

This is a classic Linked List question. I need to create a new node and return it as a head. In the context of Snake, when the snake needs to grow, it grows from the head in the direction of its inertia. I just allocate memory for the head, instantiate it and append it to the old head.

 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct SnakeCell* add_snake_cell(WINDOW* window, struct SnakeCell *head, int inertia){
    // Returns the new head
    struct SnakeCell *newhead = malloc(sizeof(struct SnakeCell));
    int newx, newy;
    if(inertia == DXN_UP){
        newhead->x = head->x;
        newhead->y = head->y - 1;
    } else if(inertia == DXN_DOWN){
        newhead->x = head->x;
        newhead->y = head->y + 1;
    } else if(inertia == DXN_LEFT){
        newhead->x = head->x - 1;
        newhead->y = head->y;
    } else if(inertia == DXN_RIGHT){
        newhead->x = head->x + 1;
        newhead->y = head->y;
    }
    head->next = newhead;
    newhead->prev = head;
    mvwaddch(window, newhead->y, newhead->x, '#');
    wrefresh(window);
    return newhead;
}

These are just some parts of the code I feel are interesting in relation to the usage of Linked Lists. If you know C/C++ and are interested in building GUI-like terminal applications, do give ncurses a try! It allowed this snake game to be made, and has birthed many utilities such a htop and nano.