« Back to the main CS 300 website

Project 1: Snake :snake:

Part 1A checkin at TA hours due by Mon, Feb 7
Part 1 due Feb 11 at 6:00pm (EST)

All parts due Feb 18 at 6:00pm (EST)


Introduction

Welcome to the first project of CS 300! We’re excited that you’re here! :smiley:

In this project, you will develop a version of Snake, a famous early computer game widely cloned and reproduced. (Fun fact: Snake in QBASIC was the first computer game Malte played as a child, and Snake was also on his first mobile phone, a Nokia 3310.)

Since we’re writing the Snake game in the C programming language, this assignment requires you to work directly with memory and data representations. In the first portion of the project, you will set up a basic playable version of the game with customizable levels. In the second part, you will bring your implementation closer to the original snake game by supporting a growing snake (using your own linked list data structure), and explore different character representations that allow for player names from different cultures by supporting their alphabets.

Learning Objectives

In this assignment, you will:

Assignment

Assignment Installation

If you have completed Lab 0, you will already have created a private GitHub repository for your project work under the csci0300 organization.

:warning: If you have not completed Lab 0, we suggest that you do it now! :warning:

Recall, to clone your repository for the projects, you run this command (inside the course container, or on the computer you’re working on):

$ git clone git@github.com:csci0300-s22-projects-YOURUSERNAME.git

(You’ll hopefully have done this as part of Lab 0 already.)

Now, ensure that your repository has a handout remote. Type:

$ git remote show handout

If this reports an error, run:

$ git remote add handout https://github.com/csci0300/cs300-s22-projects.git

Then run:

$ git pull
$ git pull handout master

This will merge our Project 1 stencil code with your repository.

Once you have a local working copy of the repository that is up to date with our stencils, you are good to proceed. You’ll be doing all your work for this project inside the snake directory in the working copy of your project’s repository.

Infrastructure help

Stencil Overview

Below is an outline of all the files we provide you with an a brief description of what they do:

In snake/src/:

File Purpose
common.h Contains definitions for the input_key enum, game, board, and snake structs, and function headers for common.c
game_over.h Contains function headers for game_over.c
game_setup.h Contains the definition for the board_init_status enum and function headers for game_setup.c
game.h Contains function headers for game.c
linked_list.h Contains the definition for the node struct and function headers for linked_list.h
mbstrings.h Contains function headers for mbstrings.c
render.h Contains function headers for render.c
snake.c Contains support functions and skeleton version of main

In snake/test/:

File Purpose
traces.json Contains all of the traces that a working implementation will pass
autograder.c & autograder.py Autograder program/scripting

The files that you will have to modify in the project are:

Part 1: Snake Movement + Board Setup

Important Note: There are Testing and Debugging sections at the end of the handout. Make sure you read through these before attempting to implement any part of the project, so that you can run tests and productively debug your code.

The rules of the Snake game are as follows:

  1. The snake moves around a rectangular playing field bordered by walls, and with some optional internal walls.
  2. The player uses arrow keys to change the snake’s direction.
  3. Food appears at random locations on the playing field, and if the snake’s head hits the food, the snake eats it. The player’s score increases and new food appears elsewhere.
  4. When the snake runs into a wall (or into its own body), it dies and the game is over.

Your task is to take the stencil – which starts out doing nothing at all – and implement a game with these rules. Don’t worry, we’ll break this down for you!

We provide several helpful helper functions in the stencil, and will discuss these as we go along.

Task: Compile the stencil code and run it!

Hints on compiling

Make is a tool that enables us to generate executable files from source code. The Makefile defines rules and behaviors for compilation. You’ll learn more about Makefiles in Lab 1.

Navigate to your project directory and run make to create an executable file (called snake). You can also run tests with make — read through the rest of the handout!


You will see that it simply prints a message and exits:

$ make
$ ./snake
usage: snake <GROWS: 0|1> [BOARD STRING]
$ ./snake 0
             ____
Hello       / . .\
CS 300      \  ---<
student!     \  /
   __________/ /
-=:___________/

Part 1A: Board and Game Setup

Like any computer program, the Snake game consists of machine code (in the “code” or “text” segment of memory) and data. The data represents the state of the game, as well as its visual representation to the player. All of this is stored in the computer’s memory in the form of bytes.

Your first task is to extend the stencil with the necessary code to represent and update the game state in memory!

Take a look at the structs defined in common.h:

We have given you the definitions of both the board struct and the game struct, but you can choose to fill in the snake struct with the fields you think are most appropriate. It will be useful to note that one of the fields of the board struct is a pointer to a snake struct, which means that you can access a game’s snake struct through the game’s board struct (which you can, in turn, access from a game’s game struct).

First, we’ll give you an overview of the board and game structs. Once you understand how both the given structs work, you will need to define how you want to represent the snake.

The Board Struct

We know that the game board will have certain dimensions, and may contain walls. Our snake game will support user-provided levels, so the board dimensions may be different every time. We will also need to access and update the board based on arrow key inputs from the user.

So, what are some important details about the game board that we need to store? Additionally, what data structure(s) can we use to represent the board itself? Think on these questions before reading through our explanation of the struct that we give you in the stencil!

The Board Struct

Here is the board struct that we give you in the stencil (located in common.h):

typedef struct board {
    // Board struct — contains basic metadata
    size_t width;
    size_t height;
    int* cells;  // array of integers containing data for each cell on the board
    snake_t* snake; // pointer to the snake struct for this board
} board_t;

We have included both a width field and a height field to store the dimensions of the board. Notice that both of these fields have type size_t. This particular type actually represents values of type unsigned long, but we use the type definition size_t to indicate that the corresponding value represents a “size” of some other kind of data. In this case, we use size_t for our first two fields to indicate that we are storing two size measurements of our board, i.e., the width and height. To disambiguate between width and height, we will consider width to be the number of columns in a board and height to be the number of rows.

Our third field, cells, is what we use to represent the actual game board. For this representation, we use an array of integers, i.e., an int[]. You may observe that we don’t use an array type in the board struct, though! Recall from lectures the duality between arrays and pointers: even though int* is the type of a pointer to an integer, we can set aside a region of memory large enough to represent all individual cells in the board, put its address into the int* and treat the memory as an array. Then, we can set the memory address of the starting cell of the board as the pointer, and use pointer arithmetic to access, iterate through, or update the other cells in the board. This will become clearer as you work your way through the project!

The fourth and final field, snake, is a pointer to a snake struct, which will represent the snake in our game. This is the struct that you may have to finish defining!

Also note that we’re using a typedef here. We could have defined our game board struct just as a struct board { ... };, but the typedef provides an alias that lets us conveniently refer to the struct elsewhere in the code. For example, to initialize a pointer to a board_t struct called gameboard, we can now use the following syntax:

board_t* gameboard;

Note that declaring such a pointer does not actually allocate the memory for the board or initialize the struct’s fields; you will have to set them afterwards, as follows:

gameboard->width = ...;
gameboard->height = ...;
gameboard->cells = ...;
gameboard->snake = ...;

The Game State Struct

Now, we need to consider what information we might need to store about the state of the game. Before looking at the struct we have given you, first consider why a game state data structure is useful:

  1. Look through common.h, game_setup.c, game.c, and snake.c, and take note of which function signatures take in or output a game state. Based off of these functions, what data from the game state might we need to use or update in these functions as the game runs?
  2. What would happen if we tried to just use the game board referenced from the board structure (the array of cells) as a representation of the overall game state? Why might this be inefficient? How does using a separate structure for game state metadata make the game more efficient?

You’re welcome to discuss these questions with other students in the course, or with us at TA hours!

The Game State Struct

Here is the game state struct we have given you in the stencil (located in common.h):

typedef struct game {
  int game_over;  // 1 if game is over, 0 otherwise
  int score;      // game score: 1 point for every food eaten
  board_t* board; // pointer to the board struct for this game
} game_t;

The Snake Struct

Important Note: This project leaves deliberately leaves you some design freedom in how you represent your snake. You can use the snake struct, or you can choose another way to store the information in memory (but think about which memory lifetimes, and thus memory segments, are appropriate).

At some point, we will need to update the board based on the current direction of the snake’s movement. Consider how you will represent the snake’s position and its current direction of movement, so you can then use your representation to update the overall game state.

Important Note: In this part of the project, you only need to represent the head of the snake (i.e., your snake is always of length 1); in Part 2, you will need to implement snake growth.

Task: In common.h, either fill out the given snake struct with the fields you come up with OR define your own representation of the snake.

Hints!
  • You’ll need to keep track of the snake’s position on the board. How can you do so? (Remember that you need to be able to find the snake’s cell in the cell array contained in the board.)
  • How can you represent the snake’s direction of movement? (Hint: take a look at the input_key enum defined in common.h.)

Bit Flags

In the board struct provided in the stencil, the cells field is defined as an array of integers. This means that each cell on the board will have an integer representing what type of cell it is (i.e., a wall, an empty cell, a food cell, or a snake cell). We would like our game implementation to support cells that have multiple properties, so we use bit flags within an integer value to represent the states.

A 4-byte (32-bit) integer can hold up to 32 bit flags, but we only need four for the basic game, defined (in common.h):

// Bitflags enable us to store cell data in integers!
// The "0x" notation indicates hexadecimal numbers.
#define FLAG_PLAIN_CELL 0x0
#define FLAG_SNAKE 0x1
#define FLAG_WALL 0x2
#define FLAG_FOOD 0x4

In the game variant you implement first, no valid game can have a cell with multiple bit flags set: for example, if a cell had FLAG_WALL and FLAG_SNAKE set, the snake would have walked into a wall. However, you may exploit the fact that cells can be in multiple states at the same time in our exciting extra credit exercises ✨.

Board and Game Initialization

Now that we have our main three structs defined, we need to initialize all of them before we can run our game. First, take a look at the function initialize_default_board (in game_setup.c). You do not need to modify this function.

board_init_status_t initialize_default_board(board_t* board)

Function Description

Purpose: Initializes a board_t struct to contain a default board with 10 rows and 20 columns. The snake is initialized at the 3rd row down and 3rd column from the left. You do not need to modify this function.

Arguments:

  • board: Pointer to an empty board_t struct, which will be initialized in the function body to contain the cells and dimensions corresponding to the default board.

Output: INIT_SUCCESS (denoting that board initialization was successful)

This helper function that we’ve given you initializes the given board struct to a default board (see above dropdown), upon which you can implement basic snake motions. This board has no internal walls.

What is board_init_status_t?

You may notice that the return value of initialize_default_board is a value of type board_init_status_t. This type represents possible error codes for errors that could occur during board initialization.

You will need to use this enum when you support loading custom levels in part 1C. For now however, we are only initializing the default board, so the return value will always be INIT_SUCCESS.

You can find the full description of the board_init_status enum in game_setup.h.

Now take a look at the function initialize_game (also in game_setup.c):

board_init_status_t initialize_game(game_t* game, char* board_rep)

Task: Your task is to implement initialize_game, which should initialize all the fields of the game struct provided as a pointer argument named game. For now, to initialize the board field, call the initialize_default_board function given in the stencil. This will automatically fill in all the fields of the board_t as well as initialize the respective field of the game_t struct. You will also want to set the return value to the value returned from initialize_default_board.

Notice that initialize_game is called in the main function in snake.c (you do not need to write the call; we’ve written it for you), to initialize the game (and board) structs that are defined in main.

Cleaning Up Resources

Now that we have initialized our game and board structs, let’s run the program as it currently stands!

Task: Compile your code using make clean all, and run the program using the following command:

$ ./snake 0

No board shows up because we haven’t written the code to display it on the screen yet; instead, we still get our friendly Snake with the welcome message.

However, you should also get a colorful sanitizer error when the program exits! Expand the drop-downs below for additional details regarding the two types of sanitizers you’ll be working with for this assignment.

Leak Sanitizer

The leak sanitizer detects memory leaks upon the completion of a program. A memory leak occurs when memory allocated during our program is not freed before exiting.


Address Sanitizer

The address sanitizer detects invalid memory accesses when a program runs. There are several types of invalid memory accesses (which you’ll be exploring in detail in a future project), but they can all be broadly classified as either reading from or writing to memory that was not currently allocated to the program.

Note that by default, the address sanitizer comes packaged with the leak sanitizer, so compiling with fsanitize=address is sufficient :-).

The error you should just have encountered is a Leak Sanitizer error. Let’s figure out why that is!

Memory is a critical resource that we must clean up when we no longer need it. This is particularly true for dynamically-allocated memory (memory with a manual lifetime), since this memory will not be automatically cleared, and a long running program could eventually use all the memory in the computer. The LeakSanitizer looks for dynamically-allocated memory that is still live when your program exists, and warns you about this “leaked” memory. In other words, once our game ends, we need to make sure that we have freed all the data we allocated to play the game! As it currently stands, we seem to be forgetting to free some memory.

Luckily, the sanitizer error gives us a good idea of where to look. Look at the backtrace from the sanitizer error—you should see a call to a function called calloc. calloc dynamically allocates memory just like malloc, meaning that we as programmers are responsible for freeing that memory with a call to free. The Leak Sanitizer’s message is a reminder that we have forgotten to free the memory that we had previously allocated through calloc!

Now, at the end of the main function, uncomment the last line that calls end_game(&game). This function is responsible for freeing all the resources used up by our program, as well as stopping the renderer upon completion of our game. Click on the dropdown for more information.

void end_game(game_t* game)

Function Summary

Purpose: Reponsible for cleaning up all the memory used by the game and stopping the renderer.

Arguments:

  • game: pointer to the game struct that contains all the metadata used to render the game

Task: Add a call to free such that the memory that we have allocated through calloc is freed upon a call to end_game. In order to do this, you should:

  1. Use the backtrace from the Leak Sanitizer to find out where we call calloc, and where we store the pointer it returns.
  2. Look at the definition of end_game and to find out where we need to put a call to free.
  3. Insert an appropriate call to free! (Note that free takes in one argument: a pointer to our dynamically-allocated memory).

Once you have correctly implemented this section, you should not get any Leak Sanitizer errors when running the game with sanitizers until Part 1C.

Congrats! You have now ensured that once the game ends, all allocated memory is freed before main exits.

The Game Loop

Many computer games are designed around the idea of a core “game loop” that repeats over and over until the game reaches a “game over” state. For our version of Snake, the core game loop is as follows:

  1. wait (for some specified amount of time) for user input;
  2. retrieve user input;
  3. update the game state based on user input; and
  4. render the new game state to the screen.

To begin with, you will implement steps 1, 3, and 4 of the core game loop in the main function of snake.c (look for the TODO for Part 1A).

Note: You will initially update the game state without handling user input, so you will see your snake appear and move but not respond to arrow keys. This is okay! Once you have an update function that successfully updates the snake’s movement, overall game state, and checks for wall collisions, you will handle user input.

For now, there are three function calls you need to make in your game loop:

  1. usleep(useconds_t usec): a library function that suspends execution for a some amount of time, measured in microseconds (we recommend 100 milliseconds, i.e., 100,000 microseconds, but you can adjust this to speed up or slow down your snake!).
  2. update(game_t* game, input_key_t input, int growing): the update function you will need to implement that updates the game state based on user input (see the stencil for more details).
  3. render_game(game_t* game): a function we give you as part of the stencil that renders the given game state into a visual game! You will not need to modify this function.

Since we’re not handling user input yet, you will to pass in INPUT_NONE as the second argument to update. Additionally, since our snake does not yet grow, you will pass in 0 as the third argument to update. In other words, your call to update will look like this: update(???, INPUT_NONE, 0), where you’ll have to figure out what to pass for ???.

Read through the main function in snake.c to make sure you understand what it’s doing! We don’t expect you to know what every single function does, but you should understand the general structure.

Task: Implement the core game loop in the main function of snake.c!

☑️ Testing Point A:
Now go and read the testing section below if you haven’t already. It tells you how to run the tests!

You should pass tests 1 and 2 at this point! This means that you should be able to see a board with 10 rows and 20 columns, with walls around the edges, and a snake initialised at the third row down and third column from the left. The snake should not move.

Part 1B: Updating and Running the Game

Updating the Snake’s Position

Now that you have defined a way to represent the snake in our game, you can use your representation (as well as the game struct and board struct) to begin implementing the update function in game.c. First, you will need to write the functionality that allows your snake to move while on the board.

Note: In most versions of Snake, the snake initially moves to the right. Make sure that you replicate this convention and that your snake starts moving right when the game is initialized!

The full description of the update function can be found in the stencil, but below is a short summary for reference.

void update(game_t* game, input_key_t input, int growing)

Function Summary

Purpose: updates game according to input, including the game_over field of game, the snake’s position if the game is not over, and the score field of game if the snake eats any food.

Arguments:

  • game: a pointer to the game struct we want to update. (Note that this struct contains as one of its fields, a pointer to the board struct!)
  • input: the last keyboard input received from the user
  • growing: an int representing whether we want the snake to grow upon eating food (growing = 1), or not (growing = 0).

Returns: Nothing! But the function should modify the game struct appropriately to reflect the user’s input and the snake’s behavior.

For now, we will only consider the case where the user input is INPUT_NONE (i.e. there is no user input). This means that your update function should shift the snake’s position by one cell to the right, because the snake’s default initial direction is to the right and we aren’t taking any user input yet.

Task: Implement update so that your snake’s position shifts by one cell to the right whenever update is called, and the game board is updated to reflect the new snake position.

Hints!

You will need to update both your snake representation and the board (from the game struct passed into update) to reflect the snake’s new position.

  • This is an instance of a common pattern in computer systems: metadata about the system state and the actual system state must always be updated together. This maintains an invariant that system state and metadata always match (the metadata would be rather unhelpful if this were not the case!).

When should you initialize your snake? Where on the board should you initialize your snake?

  • Hint: The board struct should be initialized – with bit flags set – before the snake is initialized.

Collisions with Walls

Now, your snake can move across the board! But, as you should notice, your snake doesn’t stop when it hits a wall, and passes right through instead!

We don’t want this to happen; if your snake hits a wall, it should stop moving and the game should end immediately (think back to the game loop you wrote in snake.c: when does your loop break?). Your next task is to modify your update function so that if your snake’s new position has a wall there, then the game ends. Make sure your game ends before your snake actually moves into the wall! We don’t want your snake to appear to move through walls. Make sure to think about what update should do if game_over is set to 1.

Note: So far, we have been using the default board to run your game, but later on, you will need to handle custom boards, which may or may not have internal walls that your snake can crash into.

Task: Modify your update function so that your snake collides with walls and the game ends if any such collision happens.

☑️ Testing Point B: You should pass tests 3 and 4 at this point. Your moving snake should hit the wall to the right of the board, which should then cause the game to end.

Getting User Input

You’ve probably watched your snake crash into the right wall of the board many times now :(

Let’s give your snake a way to avoid crashing! Your next task will be to modify your game loop in snake.c and your update function so that you can get user input, and update your snake’s position based on the direction specified by the user.

We’ve given you a function in snake.c, called get_input, that gets arrow key input from your keyboard and converts it into an input_key_t - one of the enums representing a key input. Currently, when you call update in your game loop, you pass in INPUT_NONE as the second argument, and update defaults to shifting the snake to the right. Now, you will now need to change this so that you pass in the output of get_input as the second argument to update.

Task: Modify your game loop in snake.c so that you can get input from the user, and pass this input into the call to update.

Now that your update function will take in different inputs (as its second argument), you will need to modify it once again to handle each of these different inputs, so that your snake’s position is updated according to the last input by the user.

Aside: For both Part 1 and Part 2 of this project, try playing the Google Maps version of Snake to figure out how to handle any edge cases you come up with! This will also be useful when trying to pass any of our tests that test for specific edge cases.

Task: Modify your update function so that it can handle every type of user input, and update the snake position in the snake struct and board accordingly.

☑️ Testing Point C: You should pass tests 5-9 at this point. You should now be able to control your snake’s movement using the arrow keys! Your snake should still be able to crash into the wall and end the game.

Food

You almost have a fully playable game! The last component that we’re missing is the food (without which, of course, you can’t score). Next, you will need to modify your update function further so that if your snake “collides” with a cell on the board that contains food, update does the following:

We have provided you with a helper function in the stencil that randomly places food on a given board (see place_food in game.c) to place food on your game board. It’s up to you to decide where and when to call place_food!

For now, your snake does not need to grow when it eats food. You will implement this functionality in Part 2 of this project.

Task: Modify your update and initialize_game functions so that your snake can eat food, and new food is placed on the board whenever the snake eats.

Hint!

Why did we include initialize_game in the task? What does that function have to do with food placement?

☑️ Testing Point D: You should pass tests 10-14 at this point. Your snake should now be able to move around the board and eat food, as long as you don’t crash into a wall!

Part 1C: Board Decompression (game_setup.c)

Introduction to Run-Length Encoding

Now that we have basic game play set up for our default board, we can now implement the functionality for setting up and running custom boards.

Because the Snake game is more fun when you can play custom levels, your game will have support for loading user-specified board layouts as a command-line argument. Let’s think about how you might tell the game what board you want to run!

Humans are good at dealing with readable strings, so our first plan is to encode the state of each square of the board (wall, empty, contains snake, etc.) as a letter. For example, “E” denotes an empty square, “W” denotes a square that contains a wall, etc. If we teach our program how to read these strings, we can give it any board we want.

In this representation of a custom board, the board is represented by a looooong string that contains exactly one character for every cell on the board. For example, an 80x24 board (a typical terminal size, which goes back to the 1970s) would look like this:

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

This is a 1,920 character string! It would be very tedious to type in if you found an exciting new Snake level posted in a retro gaming magazine. How can we make this representation more efficient?

Clearly, there is a lot of redundancy in this representation: many lines just consist of repeated “W” or “E” characters. To avoid this repetition, we can specify the number of instances of a character, such as “E78” to mean “78 instances of E”. This is a common compression technique called a Run-Length Encoding (RLE).

A run-length encoded version of the above board (going row-by-row) yields this much shorter string:

W80W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1
W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1W1E78W1
W1E78W1W80

To make this more readable, let’s introduce a delimiter between adjacent rows:

W80|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|
W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|W1E78W1|
W1E78W1|W1E78W1|W80

As a sanity check against incorrect transcription, we can add the board size at the beginning, encoded as “B” followed by the height (number of rows) and width (number of columns), and we can use the “S” character to encode the starting position of the snake. For this project, we will use “S1” to encode a single-cell snake. While it would be more efficient to encode the snake as a single S, we’ll opt to keep things consistent with the encoding scheme, which will hopefully make things easier! You should never start off with more than one snake cell.

The following example represents a 7-row, 10-column board with some internal walls and a snake at the bottom center:

B7x10|W10|W1E4W5|W2E7W1|W1E8W1|W1E4W1E3W1|W1E2S1E1W1E3W1|W10

On the screen, this board will look something like this:

Handling Errors

As you may have thought about, there are countless ways that a RLE-encoded board representation can be incorrect. These can range from problems with the actual board, to errors when writing the string.

As a general design principle, we prefer that our programs be able to explicitly handle expected errors, rather than leaving it up to undefined behavior to dictate what our code will do. However, because there are many different errors, our tests only require that you handle a subset of them. (You are welcome to still handle other errors if you wish!)

Errors you are required to handle:

In game_setup.h, you are provided the following board_init_status_t enum:

typedef enum board_init_status {
    INIT_SUCCESS, // no errors were thrown
    INIT_ERR_INCORRECT_DIMENSIONS, // dimensions of board do not match dimensions specified by the string
    INIT_ERR_WRONG_SNAKE_NUM, // no snake or multiple snakes are on the board
    INIT_ERR_BAD_CHAR // string contains a character that was unexpected 
} board_init_status_t;

We guarantee the following about the strings that we will test your implementation against (although once again, you are more than welcome to cover other error cases):

INIT_ERR_INCORRECT_DIMENSIONS
Definition: INIT_ERR_INCORRECT_DIMENSIONS should be returned if the dimensions specified at the start of the encoded string do not match the dimensions of the board specified by the string.

Example:
B3x5|W5|W1E1S1E1W1|W1E3W1|W5

The above string is wrong, because the dimensions at the front specify that the board should have 3 rows, but rest of the string encodes 4 rows worth of cells.

This error also applies to mismatches between the dimensions specified and the number of columns. Think about what a string that is incorrect in this way would look like!


INIT_ERR_WRONG_SNAKE_NUM
Definition: INIT_ERR_WRONG_SNAKE_NUM should be returned if there does not exist exactly one snake cell on the board.

Example:
B3x3|W3|W1E1W1|W3

In the above example, there are no snake cells. This error also applies to boards that start with too many snake cells: try and come up with example strings that demonstrate this!


INIT_ERR_BAD_CHAR
Definition: INIT_ERR_BAD_CHAR should be returned if you encounter an "alien" character. There are many ways to define what an "alien" character is, but we will define it as characters that are not expected to be found in a correctly formatted RLE-encoded board string.

Examples:
B3x3|W3|W1S1Z1|W3
A1-4|W2S1W1

In the first example, we see an unexpected character, "Z" that does represent any valid cell type on our board. In the second example, "-" is used as a delimiter between the height and the width of the board, where we expect to see "x". Additionally, the string starts with “A” instead of “B”.

Task: Implement decompress_board_str() with proper error handling. Look at the dropdown for more details (and a helpful hint)!

Function Summary
board_init_status_t decompress_board_str(board_t* board, char* compressed)

Takes in a pointer to a board (board) and a RLE-encoded string containing the custom board (compressed), and should populate the cells of the board with the correct values that correspond to the string.

This function returns a value of type board_init_status_t. This type represents whether the board decompression was successful, and will be communicated to the main game loop by initialize_game. (This means that the return value of initialize_game should no longer unconditionally be the return value of initialize_default_board!) If no errors arise, then INIT_SUCCESS should be returned.


A Rough Strategy

Below, we have given you some of the steps you could take to write decompress_board_str (but there can be many other valid ways of implementing this function!)

  1. Try and first break down the compressed string into smaller pieces. Think about how you can leverage the delimiter character “|”, which separates the encoding of our board by row.

  2. Figure out how to set the dimensions of your board according to what was specified in the prefix of the encoded string. Here, “x” is your magical delimiter—you know that everything between the starting “B” and “x” should be an integer that corresponds to the height of the board, and everything between the “x” and the first “|” delimiter will correspond to the width of the board.

  3. You will likely want to loop through your strings and fill in the board’s cells as you go. This means that you will need to store some information regarding where in the board you are, what type of cell you are currently reading, and how many consecutive cells of that type you want to fill in.


Hints!
  1. It may be a good idea to first take a look at C’s string library functions. Many of these functions will likely handle some of the steps you come up with to decode a compressed board string, so make sure to take a look at some of their descriptions!

  2. There are a few different ways to convert strings to integers. A helpful function to look at is atoi! Alternatively, you can also leverage the fact that the hex-encodings of numerical characters range from 0x30 (0) to 0x39 (9), and subtract accordingly.

  3. It is strongly recommended that you design and implement some helpers for decompress_board_str. Parsing and manipulating strings in C can become complicated, so having a few helpers that handle repeated subtasks will help you organize your code. We specifically suggest you write a helper that takes in a row and a column of the board, and returns the corresponding index of the board’s cell array.

Task: If you have not already done so, update initialize_game to support decompression! This function should call on decompress_board_str if the string passed into it (board_rep) is not NULL. If it is, then just initialize the default board with initialize_board.

Notice that now, initialize_game must not always return INIT_SUCCESS, because decompression can return a number of failure statuses. If necessary, update the return value accordingly!

☑️ Testing Point E: You should pass tests 15-27 at this point. You should also be able to create custom boards from compressed board strings, and play through them.

Woo! Congratulations on finishing part 1!

Part 2: Growing Snake + Game Over

Part 2A: Growing Snake

We’ve now got a moving snake… or, rather, a very very short snake. It would be nice if our snake would actually grow upon eating food.

This means we’ll need to extend our current snake struct definition to handle multiple snake coordinates (one for each cell of the snake). We could do this in a number of ways:

Linked Lists

:warning: This part of the project makes use of your linked list code from Lab 2.

If you have not completed Lab 2, we suggest that you do it now! :warning:

Task: Copy your (fixed!) linked list code from Lab 2. Place it in the (currently empty) linked_list.<c|h> file in your project folder.

Additionally, now that your snake representation will need to use the structs and functions from linked_list.<c|h>, we need to introduce the linked list code to common.<c|h>, where our snake and board are defined.

To do so, add the following line to the top of common.h:

#include "linked_list.h"

Task: Update your snake struct to use a linked list to store the snake’s current position, and update your update function to handle this new structure. The snake doesn’t need to grow yet, but your code should still pass the same tests.

A Snake that Grows

We’re almost there! Now we need to figure out how to 1) extend the snake when it eats food and 2) update the list of positions when the snake moves.

Warning: The snake should only grow if snake_grows is equal to 1. If your snake grows when snake_grows is 0, your code may fail prior tests!

Task: Implement snake growth on food consumption (and provided snake_grows is 1).

Hints on growth

Start by considering the list corresponding to a snake with a length of at least three. When the snake moves one step:

  • Which elements can you keep the same?
  • Which elements should you discard from the list?
  • What do you want to add to / update about the list?

We recommend you draw this out for yourself!

You may also run into a couple of edge cases while testing your implementation:

  • What happens if the snake hits itself?
  • What if the head of the snake moves into the space that the tail of the snake just left?
  • See the note below about the snake backing into itself!

Aside: In the actual snake game, if the snake immediately tries to go back the way it came (backing into itself), the movement is not accepted and the snake continues to move in its previous direction. We would like you to replicate this behavior so that the game doesn’t end any time the snake tries to collide with itself by moving backwards!

Last but not least, even though your game loop in snake.c should break out of the loop when the game is over, one could imagine a different implementation that just stops updating the board once the game ends. In these cases, we don’t want to be able to continue responding to keystrokes and updating the board after the game has ended. In order to make your update function extensible to multiple different game loop implementations, we’ll add one final feature!

Task: If game->game_over is set to true (1), make sure your update function does nothing!

☑️ Testing Point F: You should pass tests 28-36 at this point. Your snake should now grow when it eats food!

Part 2B: Game Over

You’ve almost got a complete game! Let’s wrap it up nicely with a personalized Game Over screen featuring the player’s name and their score.

Rendering the Game Over screen

We’ve provided a few helper functions for rendering the Game Over screen:

render_game_over is located within game_over.c (and game_over.h), which has not been included in compilation up until this point. This is because it isn’t in the Makefile. Makefiles tell the compiler how to manage your source code files; you’ll learn more about this in Lab 1.

Task: Look through the Makefile and find OBJS = src/game.o src/game_setup.o …. Add game_over.o to the list of objects to be compiled.

Now, try compiling the project. What happens?

Oh no! It looks like one of our functions assumes that a struct features certain fields. Look through the code in game_over.c and see if you can figure out why they are needed, and what their types are. (Hint: How do we represent strings in C?)

Task: Add the necessary fields to the game_t struct so that the project compiles successfully.

Prompting and reading in user input

We now have a field in our struct for the player’s name and its length. We still need a way to prompt the user to enter their name and parse the input. Head on over to the read_name function in game.c, where you’ll implement this functionality for reading in user input.

First, you want to print out a prompt for the user (e.g. "Name > "). Then, use the read system call to read their response.

Once the user inputs a name with at least one character (apart from hitting enter), then store their name and return.

Task: Implement read_name as detailed in the dropdowns below. Once you have done so, uncomment the following lines in main (snake.c):

// TODO: Implement (in Part 2B)
char name_buffer[1000];
read_name(name_buffer);
void read_name(char* write_into)
Function Summary

Purpose: Prints a prompt to the console asking the user to input their name (e.g. "Name > ", and reads in the user input. If at least one character is inputted, stores the input in the string buffer, write_into. Otherwise, prints an error and reprompts.

Arguments:

  • write_into: String buffer where the user’s input will be stored

Returns: Nothing, but if the user enters without typing any other characters, the function should print the following error to the console and repeat the earlier steps of the function.

  • Error: "Name Invalid: must be longer than 0 characters."

Implementation Notes!

Prompting

You may use the printf function to print out your prompt to the console.

File Descriptors

The first argument to the read system call is an integer representing a file descriptor. You’ll learn more about file descriptors later in the course, but for now, you can think of it as telling the computer where it should read from. Listed below are three very common file descriptors and the locations that they correspond to. It’s up to you to figure out which one you want to read input from!

FD Location Abbreviation
0 Standard Input STDIN
1 Standard Output STDOUT
2 Standard Error STDERR

Length to read

The third argument to the read system call is a value of type size_t denoting how many bytes we want to read. While we ideally do not want to be making assumptions about how long people’s names are, we unfortunately need to tell the computer how much to read. To that end, set this value to 1000 in order to be fairly generous with the size of our input.

Erroring appropriately

When the user presses enter without entering any other characters, what will be the string read into the buffer? What will read return? Use this to assess how you will know to print an error and reprompt the player!

Note: At this point, you should be able to see your prompt print, wait for input, and start the game once a newline is entered after a nonzero-length string is entered.

If you do not see your text prompt, try inserting this line of code after you print out your prompt:

fflush(<file descriptor of where you are reading from>);

This is because by default, whatever you wish to write gets added to a buffer, so you sometimes need to forcefully flush the buffer before reading in input!

Socially Responsible Computing: Character Sets

The default string encoding in C, as you might recall from lectures uses the ASCII standard, which represents each character as one byte. ASCII is the American Standard Code for Information Interchange. However, ASCII is only meant for English and it does not support accents or characters from non-Latin alphabets.

To ensure that we are able to read in all player names that a user could input, and render them correctly, we will need to support a different character encoding. Programmers often turn to extended character sets (most commonly Unicode, and specifically its UTF-8 encodiing) to create more inclusive applications.

When programming for extended character sets, some of the standard library support functions for single character (ASCII) strings will not work as intended. C provides support for multibyte characters through their wchar_t struct, which represents a character in 4 bytes. However, since many extended character sets have variable length characters (for example, UTF-8 encodes characters in 1-4 bytes), using wchar_t leads to wasted space in memory. Moreover, programs often receive UTF-8 text as input that isn’t nicely laid out in 4-byte chunks, and must still be able to process it. (As an example, consider a website that processes input from a form: users may put strings like “γνωρίζω” or “❤️😺” into the form!)

UTF-8 characters follow a set byte format based on their length. 1 byte UTF-8 characters are meant to be compatible with ASCII, which means that they always begin with a 0 bit. For 2-4 byte UTF-8 characters, the number of leading 1s indicates the length of the character (in bytes). Each subsequent byte begins with the bits 10. You can find an overview of the format below:

Length (bytes) Encoding (binary)
1 0xxxxxxx
2 110xxxxx 10xxxxxx
3 1110xxxx 10xxxxxx 10xxxxxx
4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

mbslen()

Now, to ensure that we are able to read in any name that a user could input, and render them correctly, we need to implement a function that will allow us to find the number of UTF-8 characters that a user inputs.

Task: Implement mbslen() in mbstrings.c.

mbslen: Counts the number of UTF-8 code points ("characters") in a UTF-8 encoded string.

Synopsis:
mbslen counts the number of code points in the UTF-8 multi-byte string stored in bytes until a null character is hit. Note that in this part of the assignment the number of “characters” does not correspond to the number of bytes, but to the number of valid UTF-8 code points; see the UTF-8 encoding table for more details.

size_t mbslen(const char *bytes);

Examples:

char *emojis = "🥳😊😄";
size_t len = mbslen(emojis);  
// len = 3

Task: Once you have successfully implemented mbslen(), call it in snake.c on the name the user inputs and store the result in the appropriate place.

We’re almost done! Let’s tie it all together and present the game over screen.

Task: Edit end_game(…) and uncomment the lines around and including render_game_over(…) (which implicitly requires the name and its length) so that your snake game renders the final screen when the game is over.

☑️ Testing Point G: You should pass all the tests at this point! You should be able to prompt a user for their name, and then store their name and name’s length (according to unicode characters), and see the final game over screen rendered when a game ends.

More on Unicode and Reflection Questions

relevant xkcd

Write your answers to the following questions in the SRC section of your README.

The primary goal of the Unicode character encodings is to accurately represent “all characters in widespread use today.” With that, the Unicode Consortium, the organization responsible for maintaining and updating the Unicode standard, must appropriately decide which characters to include.

  1. Who founded the Consortium? What are your thoughts on the composition of the Consortium members? What process would you suggest for selecting them, and how does that compare with what happens today?

Accounting for every possible language is difficult; the Unicode standard supports many, but not all.

  1. Find a language that is not yet in Unicode, has only recently been supported (e.g., in the last 10 years), or is/was missing important characters. What is/was missing, and how does this affect the users of the language?

Beyond missing languages and characters in languages, Unicode has also faced controversies with representing (and unifying) similar languages. One of the biggest controversies is Han Unification, an attempt to unify the Chinese, Japanese, and Korean (CJK) languages into one common encoding.

  1. Research some of the reasons behind, and controversy surrounding, Han Unification. Then, read this Unicode Technical Note on why CJK languages are unified, while Latin, Greek, and Cyrillic scripts aren’t. Do you agree with Unicode? Why or why not?

Youdidit!! 😃 Go get some high scores (and post them on Ed) 🎮

Testing

⚠️ Make sure that you run all tests inside the course Docker container!

Even though this project may compile on your host OS, you may spuriously fail tests if your C standard library generates a different sequence of random numbers than the library version in the course container. For example, the C standard library that comes with macOS uses a different random number generator than the standard library in Linux, and consequently the food will appear in the wrong places if (and you’ll fail the tests) on macOS.

We’ve provided an automated test suite for you to check your implementation against. As you progress through the project, you will pass more and more of the tests until you pass them all!

To run all the tests, you can use

$ make check

To run a specific test you can use

$ make check-<n>

For instance make check-5 to run test 5. To run a range of tests, use

$ make check-<n>-<m>

For instance, make check-3-10.

A single test contains a compressed board string, a random seed that determines the order of food generation, a flag that says whether or not the snake should grow (the snake doesn’t grow in part 1, but does in part 2), and a series of keyboard inputs. The autograder will use those inputs to pretend to play your snake game. The game runs for as many steps as there are key inputs. When the inputs run out, the autograder takes a snapshot of your game struct and compares it against an expected output, notifying you of any discrepancies.

By default, if your board doesn’t match the expected output the autograder will print your board and the expected board so you can see the errors. If you also want to see all the intermediate boards as the autograder plays snake, you can run in verbose mode:

$ make -B check V=1 # `-B` forces a rebuild and `V=1` sets verbose mode

To switch back to normal output, you can use

$ make -B check V=0

Debugging

NOTE: Comment out the -fsanitize=address flag in the second line of the Makefile when using GDB. Sanitizers should not be used on binaries that are attached using GDB and may result in some unexpected errors! Make sure to add this line back in after debugging to make sure that your program still passes the sanitizers.

As you’ll discover (or have discovered!), gdb is an invaluable tool for debugging your C programs. However, our snake program represents a challenging debugging problem: how can we run our program in gdb when we also need to see the graphical output?

It turns out gdb has an answer for this–we can run the program in one terminal and attach to it with gdb from another terminal. We’ve provided small scripts to make this easy for you. You can run them as follows:

In one terminal, run the listen script. It takes any arguments you would normally pass to the snake program. Here, we pass 0 to indicate that the snake shouldn’t grow.

./gdb-listen.sh 0

In another terminal, run the attach script

./gdb-attach.sh

The first terminal will have your snake game, and the second will have gdb. However, you won’t see much in the first terminal, as the game window hasn’t been set up yet. Try typing continue in gdb to start the game.

With this setup, you can use gdb how you normally would. For instance, you can set breakpoints on initialize_game, update or decompress_board_string.

Another question you may have is how to debug test cases. These are simpler since they don’t require graphical output. We’ve included an extra make rule to run tests under gdb. You can use it like so:

make check-gdb-<n> # for instance, make check-gdb-3

By default, this will pause program execution in autograder.c:main(), which you don’t need to understand. All that’s important to know is that autograder.c calls many of the same functions as snake.c, so if you set breakpoints on initialize_game, update, decompress_board_string, etc. you can get to your code to start debugging.

GDB looks weird?

If you run into issues where the terminal doesn’t start new lines in the correct place, try a new terminal and do not change its default size. Your terminal may sometimes report the wrong dimensions to GDB.

The Address Sanitizer

Modern C compilers includes a plugin called the address sanitizer. The address sanitizer helps detect memory access and leakage errors, and is enabled via the flag -fsanitize=address. Notice that we’ve added this flag in the Makefile. The grading server will compile your handin with this flag — your code must pass the tests with sanitizers enabled!

You may find that gdb sometimes conflicts with the address sanitizer. If so, you can comment out the flag in the Makefile and re-make the project (make -B all). Just remember to reenable it once you’ve finished debugging with GDB!

Extra Credit

If you’re feeling adventurous, try to extend your game with some additional fun features! Make sure to gate your extra credit with a command line flag, special optional characters in board strings, or a #define so that existing tests don’t break.

The amount of TA help you can get here may be limited. Please describe your implementation and how to test it in the “Extra Credit Attempted” section of your README.

Extra credit is in no sense required to get an A, except if you’re a graduate student taking CSCI 1310, in which case we require you to achieve 3 extra credit points on this project.

Extra credit’s contribution to your grade is limited to 10 points. You’re very welcome to attempt more, though, and impress us 😊.

Gameplay

Grow more than one length on each food

Make a bot

Powerups!

Set your creativity free with the following freestyle ideas! Figure out what thesy could mean and add support to the game. There is no right or wrong design here, just FUN 🥳!

Wraparound

Visuals

These ideas will likely involve working with the renderer (render.c), which uses the ncurses and ncursesw libraries (for wide character support).

Better Snake visuals

Bell character on food 🔔

Better UI

Misc

Interesting Level Design

Handing In Your Code

You will hand in your code using Git. In the snake/ subdirectory, you MUST create and fill in a text file called README.md. The README.md file will include the following:

  1. Any design decisions you made and comments for graders, under “Design Overview”. If there’s nothing interesting to say, just list “None”.
  2. Any collaborators and citations for help that you received, under “Collaborators”. CS 300 encourages collaboration, but we expect you to acknowledge help you received, as is standard academic practice.
  3. Your answers to the SRC reflection questions under “Responsible Computing Questions”.
  4. A description of your extra credit work (if any) under “Extra Credit Attempted”.
  5. Notes on approximately how long it took you to complete the project. We won’t use this for grading, but we collect the data to calibrate for future years.

Here’s a Markdown template for your README. We strongly recommend that you use this template!

CSCI 0300 Project 1 - Snake
===========================

## Design Overview:

*TODO!*

## Collaborators:

*TODO!*

## Responsible Computing:

*TODO!*

## Extra credit:

If you choose to do extra credit, detail it here.

## How long did it take to complete Snake?

*TODO!*

Grading breakdown:

Your submission will not be graded until you configure the grading server. You should have used the grading server for Lab 0 already.

If you were registered for CS 300 on the first day of classes, you should have received credentials by email.

If you only recently registered or you’re shopping the course but haven’t registered, you won’t have an account yet. In that case, please complete this form and wait until you receive your credentials. We will create accounts based on the form entries at 8pm every day.

Step 1: Log into the grading server with the password you received. Once you’re logged in, enter your GitHub username (at the top).

Step 2: Add the repository URL under the “Project 1: Snake” category. Click “Project 1: Snake” to initiate a fetch of your repository from GitHub.

Note: If your GitHub account is not linked to your Brown email address, the grading server will give you a command to run to verify your project repository.

Step 3: You should see your commit listed on the “Project 1: Snake” page. You can use the buttons below the commit list to test your code in our grading environment. Make sure it still passes all the tests!

Congratulations, you’ve completed the first project! :clap:


Acknowledgements: This project was developed for CS 300 by Benjamin Lee, Casey Nelson, Livia Zhu, Rhea Goyal, Sreshtaa Rajesh, Paul Biberstein, Richard Tang, Sophia Liu, Vic (Shihang) Li, and Malte Schwarzkopf.