Review

Linked List

Linked lists are dynamic sequences of data, where each set of data contains the address to the previous (or next, or both) set of data. Methods used in common are: finding the head / tail of the sequence, inserting in between elements, removing a specific element from the list etc.

Introduction

The objective of Lab 4 is to implement a console snake game using linked lists. If you are not familiar of what snake games are, you can try out Google Map's snake game at snake.googlemaps.com.

Gameplay

The goal of the game is to grow the snake as much as possible. The snake grows whenever it eats a fruit. The player has to navigate the snake to the fruits, while avoiding collisions against itself or the walls, which would cause the snake to die.

In this lab, empty space, the body of the snake, and the fruits are labelled by '.', 'o', '*' respectively. The walls are not printed onto the console - the snake going out of bounds is treated as colliding with the wall.

Players control the snake using by keying in 'w', 'a', 's', 'd' on the console (and enter), which corresponds to moving up, left, down, right respectively.

Brief Overview of Program

The rendering of the map onto the console is provided in the skeleton code. It is only required to implement the linked list methods (Snake.h), and the game logic of controlling the snake (SnakeGame.cpp).

Snake.h contains a struct Snake which represents a doubly-linked list. It contains these attributes:

• next - A pointer to the next element. Note that the tail has no next elements.
• prev - Pointer to the previous element. The head has no previous elements.
• x,y - Coordinates of the body of the snake on the grid.

You have to implement these functions in Snake.h, which are used to manipulate the doubly-linked list:

• get_head - Returns the head of the linked list.
• get_tail - Returns the tail of the linked list.
• get_next_body - Retrieves the element which is n elements next of the given element. If n is too large, returns the tail of the list.
• remove_self - Removes the given element from the list, but does not deallocate the element.
• insert_into_previous - Inserts a new element into the previous of the given element.
• insert_into_next - Inserts a new element into the next of the given element.

SnakeGame.cpp already contains the code to render the grid onto the console in the skeleton code. You only need to implement the following:

• int update_game(char option) - option is one of W, A, S, D (in capital letters) corresponding to moving up, left, down, right.

It is recommended that you complete the linked list methods before writing the game logic. Please refer to the Lab Work section for the details of the implementation of the methods. To ease debugging, you can compare your program with the demo program by running the Test mode, which manipulates a linked list and prints the contents directly to the console.

Lab Work

Task 1 - Implement linked list getter functions

Given any element in the body of the snake, these two functions returns the (pointers to the) head and the tail of the snake respectively.

SnakeBody* get_head(SnakeBody& body);
SnakeBody* get_tail(SnakeBody& body);

Obtains the n^th next element starting from the given element. If n is too large, returns the tail of the list. For example, if n=3, the linked list is ABCDEFGH with head A, and given body=C, the function returns F.

SnakeBody* get_next_body(SnakeBody& body, int n);

Task 2 - Implement linked list insertion functions

Both insertion functions contains two arguments, the current element (B, as reference) and the new element (N, as pointer). N is to be inserted into the previous / next of B. It is assumed that N is not an element already in the list. For example, take the list ABC with head A. Inserting N previously into B gives ANBC, while inserting N to the next of B gives ABNC.

void insert_into_previous(SnakeBody& B, SnakeBody* N);
void insert_into_next(SnakeBody& B, SnakeBody* N);

Task 3 - Implement linked list removal functions

Removes itself from the list (think of the three cases, whether the body is at the head, tail, or the interior of the list). Note that you should also set body.next, body.prev to nullptr.

void remove_self(SnakeBody& body);

Task 4 - Complete game logic

Complete the following function (in SnakeGame.cpp), which moves the snake according to player input (W - Up, A - Left, S - Down, D - Right, in capital letters). The function returns -1 if the game continues, otherwise returns 0 if the snake hits the wall, otherwise returns the position of the snake body the snake has collided with. (e.g. ABCDEFGH is the snake with head A, the indices are respectively 01234 etc.). This function should increase the snake length by one cell if it eats a fruit.

int update_game(char option);

The parameter option is a single character indicating the movement. You can assume it is one of the following upper-case letters: 'W', 'A', 'S' and 'D'.

Throughout the function, you can access the head of the current snake with the pointer snake_head. It is recommended that the function should proceed in this fashion:

1. Store the location of the tail. This is used if the snake grows by one cell.
2. Handle snake movement: remove the tail and place it on the front, and update snake_head.
3. If the snake head is out of bounds (collides with the wall), return 0. Note that the size of the grid is stored at GRID_SIZE.
4. If the snake head hits its body, returns the index of the collision.
5. If the snake head hits a fruit, the snake grows, and the player gains one point. The player score is stored in the variable score. The current position of fruits are stored in the 2D array fruits[FRUIT_SIZE][2].
   1. A new element should be inserted to the tail, having the position of the coordinates stored in step 1.
   2. Afterwards, the coordinates of the eaten fruit has to be updated by calling unique_coordinates(fruits[i][0], fruits[i][1]);, where i is the index of the eaten fruit. This regenerates the fruit at a new pseudo-random position in the map.
6. If the function has not returned a value at this point, then return -1 at the end to signify that the game will continue.

Note that the function should only call unique_coordinates at most once.

Resources

• Skeleton code: lab4_skeleton.zip
• Demo program: (Windows / MacOS (available soon))

We will grade your assignment based on whether it correctly handles the following situations. To ensure correctness of your program, you can check the output of the demo program on the situations below.

• Hitting the top, bottom, left, right walls
• Self-intersection of snake at different positions
• Eating fruit and growing the snake
• Score calculation

Submission & Grading

You may earn 1 point for each test case via Automated Grading on the ZINC Online Submission System. The deadline is 15th October 2021, 23:59 HKT. Please check here for a usage overview of ZINC. Zip your source files Snake.h, SnakeGame.cpp as lab4.zip for submission to ZINC.