« Back to the main CS 300 website

Project 1: Snake

Part 1A checkin due by Friday, February 2nd
Parts 1 and 2 due Friday, February 9th at 6:00pm (EST)

All parts (1-3) due Friday, February 16th at 6:00pm (EST)

Introduction

Welcome to the first project of CS 300! We're excited that you're here!

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 and second portions of the project, you will set up a basic playable version of the game with customizable levels. In the third 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:

• Practice writing code in the C programming language.
• Understand how data is laid out in memory.
• Learn how to work with pointers.
• Become familiar with C strings, bitwise operations, and dynamic memory allocation (malloc and free).
• Understand the difference between ASCII and Unicode character representations.

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.

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:cs300-s24-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-s24-projects.git

Then run:

$ git pull
$ git pull handout main

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.

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/:

In snake/test/:

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

• game.c
• game_setup.c
• snake.c
• linked_list.c
• mbstrings.c
• common.h
• common.c
• Makefile
• game_over.c

Testing

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! Once you pass all your tests locally, make sure that they also pass on the grading server!

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 or 2, 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 data 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: Compile with the ASAN=0 flag when using GDB (e.g make -B all ASAN=0) to disable the address sanitizer! Sanitizers should not be used on binaries that are attached using GDB and may result in some unexpected errors! Make sure to remove ASAN=0 from your make command when you are done debugging.

MORE DEBUGGING INFO: For more detailed info on debugging and the address sanitizer see our C primer on debugging.

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.

Part 1: Snake Movement

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.
5. Some cells may also contain grass, which the snake or food can hide in, causing it to appear a different color.

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.

$ 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!

We have already created the local variables you need to store information about the game board in the main function of snake.c. We have also already created you the global variables you need to represent high-level game information in common.<c|h>. You will need to fill in the variables necessary to store information about the snake.

First, we'll give you an overview of the information stored on the board and game state. Then, you will come up with a representation for storing information about the snake.

Board Data

We know that the game board will have certain dimensions, may contain walls, and will have a snake. Our snake game will support user-created levels whose board dimensions may differ. We will also need to access and update the snake's position on 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 do we need to represent the board itself? Think on these questions before reading through our explanation of the variables that we give you in the stencil!

// Board data
size_t width; 
size_t height;
int* cells;  // array of integers containing data for each cell on the board

enum board_init_status
initialize_default_board(int* cells, size_t width, size_t height)

enum board_init_status
initialize_default_board(int** cells_p, size_t* width_p, size_t* height_p)

/* inside the initialize_default_board function */
*width_p = 20;
...

Game Data

Now, we need to consider what information we might need to store about the state of the game.

int g_game_over;  // 1 if game is over, 0 otherwise
int g_score;      // game score: 1 point for every food eaten

/* common.h */
extern int g_game_over;
extern int g_score; 

/* common.c */
int g_game_over;
int g_score; 

Snake Data

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.

Board and Game Initialization

Now that we have our representation of game data defined, we need to initialize all of our data 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 in this project.

This helper function that we've given you initializes the given board variables to a default board, upon which you can implement basic snake motions. This board has no internal walls.

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

Cleaning Up Resources

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

$ ./snake 0

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 malloc. malloc dynamically allocates memory, 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 malloc!

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

The Game Loop

But we still don't have any visual output! Let's change that.

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 (indicated by the g_game_over global variable in this project). 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).

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(int* cells, size_t width, size_t height, snake_t* snake_p, enum input_key input, int growing): the update function you will need to implement in Part 1B that updates the game state based on user input (see the stencil for more details).
3. render_game(int* cells, size_t width, size_t height): 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 pass in INPUT_NONE as the input argument to update. Additionally, since our snake does not yet grow, you will pass in 0 as the last argument to update. Furthermore, since we are not using the snake_p argument yet, you will pass NULL as this argument. In other words, your call to update will look like this: update(???, ???, ???, NULL, INPUT_NONE, 0), where you'll have to figure out what to pass for each ???.

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.

☑️ 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.

In other words, when you run ./snake 0, you should see the following:

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 variables storing the game and board data) 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.

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

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.

Bit Flags

In the stencil, the cells array is defined as an array of integers. This means that each cell on the board has an integer representing what type of cell it is (i.e., a wall, an empty cell, a food cell, a snake cell, or a grass cell). We would like our game implementation to support cells that have multiple properties, such as a snake hiding in grass, or food hidden in grass. To use a single integer to represent these properties of a cell, we use the different bits within the integer value to represent the different states a cell can be in.

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 and shown below). Additionally, we provide PLAIN_CELL, which is the integer corresponding to no bit flags being set (i.e., a plain cell).

// Bit flags enable us to store cell data in integers!
// The "0b" notation indicates binary numbers.
#define PLAIN_CELL  0b0000  // equals 0
#define FLAG_SNAKE  0b0001  // equals 1
#define FLAG_WALL   0b0010  // equals 2
#define FLAG_FOOD   0b0100  // equals 4
#define FLAG_GRASS  0b1000  // equals 8

In the game variant you will implement in this project, FLAG_GRASS can overlap with FLAG_FOOD or FLAG_SNAKE, but no other overlapping flags are allowed. For example, if a cell had FLAG_WALL and FLAG_SNAKE set, the snake would have walked into a wall. We will further discuss what overlapping cells look like in terms of bit flags in part 1B. Additionally, you may further exploit the fact that cells can be in multiple states at the same time in our exciting extra credit exercises ✨.

Overlapping Snake and Grass

Our version of the game allows for FLAG_GRASS to overlap with FLAG_SNAKE in a cell on the board. But how can we manipulate the indiviual binary bits within a cell? Enter: bitwise operators!

Bitwise operators allow manipulating the indiviual bits within a variable. C supports several bitwise operators, including but not limited to:

• & is AND, which puts a 1 bit in the result if both input numbers have a 1 in the same position, otherwise it puts 0. For example, 0b0110 & 0b1100 results in 0b0100.
• | is OR, which puts a 1 bit in the result if either one or both input numbers have a 1 in a position, otherwise it puts 0. For example, 0b0110 | 0b1100 results in 0b1110.
• ^ is XOR, which puts a 1 bit in the result if exactly one of the two input numbers has 1 in a specific position (but not if both do), otherwise it puts 0. For example, 0b0110 ^ 0b1100 results in 0b1010.

For the full list of the bitwise operators in C, see this section in part 3!

int cell = FLAG_SNAKE | FLAG_GRASS;

bool has_snake = cell & FLAG_SNAKE;

int new_cell = cell_state ^ FLAG_SNAKE;

Collisions with Walls

Now, your snake can move across the board and hide in grass! 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 g_game_over is set to 1.

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 enum input_key - one of the enums representing a key input. Currently, when you call update in your game loop, you pass in INPUT_NONE as input, 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 input parameter to update.

Now that your update function will take in different inputs (as its second to last 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. Note that it is valid for a snake of length 1 to double back on itself (e.g. to go from moving right to moving left.)

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:

• Your snake eats the food (so the food disappears)
• The snake's position is updated
• The game's score is updated
• New food is placed on the board

We have provided you with the function place_food ingame.c to randomly place food on the game board. It's up to you to determine the correct place to call place_food!

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

Yay!!! All done with Part 1.

Part 2: 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.

Of course, don't forget about grass! In the board string, we use "G" to represent a block with grass. Although a snake will never start on a block with grass, remember that once the game begins, the snake or food can be on the same cell as grass.

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

B7x10|W10|W1E4W5|W2E5G2W1|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!)

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 
};

B3x5|W5|W1E1S1E1W1|W1E3W1|W5

B3x3|W3|W1E1W1|W3

B3x3|W3|W1S1Z1|W3

A1-4|W2S1W1

enum board_init_status decompress_board_str(int** cells_p, size_t* width_p, size_t* height_p, snake_t* snake_p, char* compressed)

Woo! Congratulations on finishing part 2!

Part 3: Growing Snake + Game Over

Part 3A: Growing Snake

Before we add any functionality to our snake, let's reconsider how we store our snake's data. Currently, we use global variables to store our snake data. However, as the amount and complexity of the data we want to store about our snake increases, this becomes harder to keep track of–we have to keep a mental tally of how every function in our program interacts with these global variables. To remedy this, we will move to using a struct to represent snake data, allowing us to pack our snake data together in a much more coherent and readable way.

Take a look at common.h again. We have declared for you a snake struct that we will refer to as snake_t to store all your snake data. Also note that we already define a variable of type snake_t in main for you.

We've now got a moving snake with a better data structure… but it is still 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:

• We could add, say, 100 extra x- and y-position fields to our struct, and use them to store the snake's position(s) as it grows longer. However, we'd only be able to support snakes of up to length 100.
• We could replace the current coordinate fields with an array of positions, and extend the array as necessary. However, we'd have to update every entry in the array whenever the snake moves. (Note: it is possible to avoid doing so. Can you think of an approach that could avoid updating every single array entry at every step?)
• Or…

Linked Lists

• We could add a field with a pointer to a linked list of coordinates, and extend/trim the list as the snake moves. This would require fewer updates than either of the prior two approaches, while accomplishing our goal of implementing a longer-than-one-cell snake!

#include "linked_list.h"

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.

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!

Part 3B: 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:

• end_game, which calls render_game_over and manages some graphics boilerplate
• render_game_over, which renders a Game Over screen featuring the player's name and score.

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.

Oh no! It looks like one of our functions assumes that some global variables exist. 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?)

Prompting and reading in user input

We now have variables 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.

• If the user presses enter without inputting anything else, print an error message saying "Name Invalid: must be longer than 0 characters." and reprompt the user for their name.

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

// TODO: Implement (in Part 3B)
char name_buffer[1000];
read_name(name_buffer);

void read_name(char* write_into)

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

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:

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.

size_t mbslen(const char *bytes);

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

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

More on Unicode and Reflection Questions

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? Who is represented among the current members, and how might that affect decisions being made for Unicode?

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

2. 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.

The Ideographic Research Group (IRG) is responsible for creating and detailing the principles of Han unification. The IRG is made up of experts from China, Japan, North and South Korea, Vietnam, and other regions that have historically used Chinese characters, as well as representatives from the Unicode Consortium. Here is an excerpt from version 1.0 of The Unicode Standard that explains some of the history and rationale of Han Unification. Please read sections 2.1 and 2.2 and feel free to skim the rest of the document. (Note that the IRG is the modern reincarnation of the CJK-JRG mentioned in the document.)

This Unicode Technical Note explains why CJK scripts are unified, while Latin, Greek, and Cyrillic scripts aren’t. Meanwhile, Suzanne Topping of IBM explains some of the downfalls of this decision:

The problem stems from the fact that Unicode encodes characters rather than "glyphs," which are the visual representations of the characters. … While the Han root character may be the same for CJK languages, the glyphs in common use for the same characters may not be.

For example, the traditional Chinese glyph for "grass" uses four strokes for the "grass" radical, whereas the simplified Chinese, Japanese, and Korean glyphs use three. But there is only one Unicode point for the grass character (U+8349) regardless of writing system.

3. For this question, you will need to work with a classmate! Make sure to coordinate so that you outline opposing positions for Part A (e.g. if you outline the 'for' position, your partner defends the 'against' position). Then, come together and discuss Part B!

   In your README, include your:

   • Partner’s CS login
   • Your individual answer to Part A
   • A summary of your discussion for Part B. You should be summarizing both the conclusion you came to, and the process by which you got there (e.g. disagreements you had, ideas you had in common, convincing evidence you encountered, etc.)
     • Feel free to represent this discussion however you think is most effective (e.g. bullet points, as a dialogue, standard written paragraph(s), etc.).
     • This summary can be identical to your partner's.

   a. Outline either the position for Han Unification, or the position against Han Unification. (~2 short paragraphs)

   b. Describe the tradeoff that Unicode has made with this decision. Which "goods" (e.g. accuracy, efficiency, fairness, sustainability) did they choose to prioritize?

You did it!! 😃 Go get some high scores (and post them on Ed) 🎮

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

• You may find that some online snake implementations have the snake grow more than one unit on each food. #define a constant that corresponds to the snake's growth length, and have the snake grow accordingly (2 points).

Make a bot

• Create a simple bot that plays your game by moving the snake in random directions! (3 points).
• Go beyond the simple bot — make it do better (3 points).

Powerups!

• MULTISNAKE (2 points for design, 4 for implementation).
• Multi-speed snake? Support areas of the board (or items the snake can collect) that make it slower or faster. [Hint: recall that we use bit flags to represent cell state, so a cell could be in "slippery" state and change the snake speed when the snake is on it!] (2 points).

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 🥳!

• A snake that shrinks??? (2 points).
• Temporarily Incorporeal Snake? (2 points).
• Extra Life Snake? (2 points).
• Enemy snakes (4 points).
• Rainbow invincible snake (2 points).

Wraparound

• We currently do not define behavior when the snake hits the edge of the board (N.B.: the edge, not an outside wall). Make it so that the snake wraps around to the other edge when it runs off the board. (4 points)

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

• Rather than rendering "S" characters, make a solid green snake [Hint: use Unicode characters like we do for the walls] (2 points).
• Make the food look like food [Hint: Unicode food emojis] (2 points).

Bell character on food 🔔

• Read about the "bell" character (ASCII 0x7, Unicode U+0007) and then add it to the game at relevant points (2 points).

Better UI

• Add a startup menu screen (2 points).
• Add a pause menu screen (1 point).
• Add a high score board! For this, you'll need to be able to run the game multiple times on one run of snake.c, and find a data structure to track high scores (3 points).

Misc

Interesting Level Design

• Make a cool level and share it on EdStem (0.1 points per heart received).
• Make the coolest level as voted by your peers (1 point, gold star and a round of applause).
• Recreate a Brown building's floorplan as a level (0.5 points).

Handing In Your Code

You will hand in your code using Git. In the snake/ subdirectory, you MUST fill in the text file called README.md given in the stencil. 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! (This template is already given to you in the stencil.)

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:

• 15% (15 points) answers to Socially Responsible Computing questions.
• 5% (5 points) completed README.
• 80% (80 points) tested functionality.
  • Each test is weighted equally: 1.5 points per test, and you get 0.5 points for passing them all.
  • Note that even if you pass every test, you will lose points if your game isn't playable.
• Extra Credit will be worth up to 10 additional points. Students in CSCI 1310 need to complete at least 3 points of extra credit.

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

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.

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!

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.