Project 1: snek
Deadline: Wednesday, February 9, 11:59:59 PM PT
Welcome to the first project of 61C! In this project, you'll get some practice with C coding by creating a playable snake game. If you're not familiar with snake, you can try out a demo at this link.
Content in scope for this project: Lectures 2-4, Discussion 2, Labs 1-2, and Homework 2. Also, make sure you've finished the setup in Lab 0.
Setup
This assignment can be done alone or with a partner. Once you run these steps, you will not be able to change (add, remove, or swap) partners for this project, so please be sure of your partner before starting the project. If there are extenuating circumstances that require a partner switch (e.g. your partner drops the class, your partner is unresponsive), please reach out to us privately.
-
Visit Galloc. Log in and start the Project 1 assignment. This will create a GitHub repository for your work. If you have a partner, one partner should create a repo and invite the other partner to that repo. The other partner should accept the invite without creating their own repo.
-
Clone the repository on your workspace. We recommend using the hive machines.
(replace
USERNAME
with your GitHub username) -
Navigate to your repository:
-
Add the starter repository as a remote:
Conceptual Overview
The game board
A snake game can be represented by a rectangular grid of characters. The grid contains walls, fruits, and one or more snakes. An example of a game is shown below:
##############
# #
# dv #
# v # #
# v # #
# s >>> # #
# v # #
# *<< * # #
# #
##############
The grid has the following special characters:
#
denotes a wall.*
denotes a fruit.wasd
denotes the tail of a snake.^<v>
denotes the body of a snake.x
denotes the head of a snake that has died.
Each character of the snake tells you what direction the snake is currently heading in:
w
or^
denotes upa
or<
denotes lefts
orv
denotes downd
or>
denotes right
At each time step, each snakes moves according to the following rules:
- Each snake moves one step in the direction of its head.
- If the head crashes into the body of a snake or a wall, the snake dies and stops moving. When a snake dies, the head is replaced with an
x
. - If the head moves into a fruit, the snake eats the fruit and grows by 1 unit in length. Each time fruit is consumed, a new fruit is generated on the board.
In the example above, after one time step, the board will look like this:
##############
# * #
# s #
# v # #
# v # #
# s >>>># #
# v # #
# <<< * # #
# #
##############
After one more time step, the board will look like this:
##############
# * #
# s #
# v # #
# v # #
# >>>x# #
# s # #
#<<<< * # #
# #
##############
Numbering snakes
Each snake on the board is numbered depending on the position of its tail, in the order that the tails appear in the file (going from top-to-bottom, then left-to-right). For example, consider the following board with four snakes:
#############
# s d>>> #
# v <<a #
# v #
# ^ #
# w #
#############
Snake 0 is the snake with tail s
, snake 1 has tail d
, snake 2 has tail a
, and snake 3 has tail w
.
Once the snakes are numbered from their initial positions, the numbering of the snakes does not change throughout the game.
The game_state_t
struct
A snake game is stored in memory in a game_state_t
struct. The struct contains the following fields:
unsigned int x_size
: Width of the game board.unsigned int y_size
: Height of the game board.char** board
: The game board in memory. Each element of theboard
array is achar*
pointer to a character array containing a row of the map.unsigned int num_snakes
: The number of snakes on the board.snake* snakes
: An array of snake structs.
The snake
struct
Each snake
struct contains the following fields:
unsigned int tail_x
: The x-coordinate (column) of the snake's tail.unsigned int tail_y
: The y-coordinate (row) of the snake's tail.unsigned int head_x
: The x-coordinate (column) of the snake's head.unsigned int head_y
: The y-coordinate (row) of the snake's head.bool live
:true
if the snake is alive, andfalse
if the snake is dead.
Please don't modify the provided struct definitions. You should only need to modify state.c
and snake.c
in this project.
Task 1: create_default_state
Implement the create_default_state
function in state.c
. This function should create a default snake game in memory with the following starting state (which you can hardcode), and return a pointer to the newly created game_state_t
struct.
##############
# #
# * #
# #
# d> #
# #
# #
# #
# #
##############
create_default_state |
||
Arguments | None | |
Return values | game_state_t * |
A pointer to the newly created game_state_t struct. |
Hints
- The board has 10 rows and 14 columns. The fruit is at row 2, column 9 (zero-indexed). The tail is at row 4, column 4, and the head is at row 4, column 5.
- Which part of memory (code, static, stack, heap) should you store the new game in?
strcpy
may be helpful.
Testing and debugging
You can run make run-unit-tests
to check your implementation for each task. Please note that the unit tests are not comprehensive, and passing them does not guarantee that your implementation is fully correct. However, they should be helpful to get you started with debugging.
If your implementation isn't working, it's time to start debugging. You can add printf
statements in your code to print out variables during code execution, and then run make run-unit-tests
again to see the output of your print statements.
Also, you can use make debug-unit-tests
to start CGDB.
Task 2: free_state
Implement the free_state
function in state.c
. This function should free all memory allocated for the given state, including all snake
structs and all map
contents.
free_state |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be freed |
Return values | None |
Testing and debugging
To test if we correctly freed memory for the game state, run make valgrind-unit-tests
to check for memory leaks. If nothing is leaked, then you've passed the unit test for this task.
Task 3: print_board
Implement the print_board
function in state.c
. This function should print out the given game board to the given file pointer.
print_board |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be printed |
FILE* fp |
A pointer to the file object where the board should be printed to | |
Return values | None |
Hints
- The
fprintf
function will help you print out characters and/or strings to a given file pointer.
Testing and debugging
Run make run-unit-tests
and make debug-unit-tests
to test and debug, just like before. Remember to uncomment out the lines you commented out from the previous task before running tests.
If your function executes successfully (doesn't segfault or crash) but doesn't print the correct output, the board you printed will be in unit-test-out.snk
. A correctly-printed board should match the default board from Task 1.
Task 4: update_state
Implement the update_state
function in state.c
. This function should move the snakes one timestep according to the rules of the game.
You are free to implement this function however you want, but you'd like, you can work through this task by implementing the helper functions we've provided. Helper functions are not graded; for this task, we'll only be checking that update_state
is correct.
Task 4.1: Helpers
We have provided the following helper function definitions that you can implement. These functions are entirely independent of any game board or snake; they only take in a single character and output some information about that character.
bool is_tail(char c)
: Returns true ifc
is part of the snake's tail. The snake's tail consists of these characters:wasd
. Returns false otherwise.bool is_snake(char c)
: Returns true ifc
is part of the snake. The snake consists of these characters:wasd^<>vx
. Returns false otherwise.char body_to_tail(char c)
: Converts a character in the snake's body (^<>v
) to the matching character representing the snake's tail (wasd
).int incr_x(char c)
: Returns 1 ifc
is>
ord
. Returns -1 ifc
is<
ora
. Returns 0 otherwise.int incr_y(char c)
: Returns 1 ifc
isv
ors
. Returns -1 ifc
is^
orw
. Returns 0 otherwise.
Unit tests are not provided for these helper functions, but we encourage you to write your own tests to make sure that these are working as expected! You can modify test_is_tail
, test_is_snake
, test_body_to_tail
, test_incr_x
, and test_incr_y
in unit-tests.c
to write your own unit tests.
When writing a unit test, the test function should return false
if the test fails, and true
if the test passes. You can use printf
to print out debugging statements. assert_equals_char
might be a helpful function to use for these tests.
Once you've written your own unit tests, you can run them with make run-unit-tests
and make debug-unit-tests
as usual.
Task 4.2: next_square
Implement the next_square
helper function in state.c
. This function returns the character in the cell the given snake is moving into. This function should not modify anything in the game stored in memory.
next_square |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be analyzed |
int snum |
The index of the snake to be analyzed | |
Return values | char |
The character in the cell the given snake is moving into |
As an example, consider the following board:
##############
# #
# * #
# #
# d>x #
# #
# s #
# v #
# v #
##############
Assuming that state
is a pointer to this game state, then next_square(state, 0)
should return x
, because the head of snake 0 is moving into a cell with x
in it. Similarly, next_square(state, 1)
should return #
for snake 1.
The helper functions you wrote earlier might be helpful for this function (and the rest of this task too). Also, check out get_board_at
and set_board_at
, which are helper functions we wrote for you.
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 4.3: update_head
Implement the update_head
function in state.c
. This function will update the head of the snake.
Remember that you will need to update the head both on the game board and in the snake struct. On the game board, add a character where the snake is moving. In the snake struct, update the x and y coordinates of the head.
update_head |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be updated |
int snum |
The index of the snake to be updated | |
Return values | None |
As an example, consider the following board:
##############
# d>> #
# * #
# ^ #
# ^ #
# ^ #
# w #
# #
# #
##############
Assuming that state
is a pointer to this game state, then update_head(state, 0)
will move the head of snake 0, leaving all other snakes unchanged. In the snake_t
struct corresponding to snake 0, the head_x
value should be updated from 6 to 7, and the head_y
value should stay unchanged at 1. The new board will look like this:
##############
# d>>> #
# * #
# ^ #
# ^ #
# ^ #
# w #
# #
# #
##############
Note that this function ignores food, walls, and snake bodies when moving the head.
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 4.4: update_tail
Implement the update_tail
function in state.c
. This function will update the tail of the snake.
Remember that you will need to update the tail both on the game board and in the snake struct. On the game board, blank out the current tail, and change the new tail from a body character (^v<>
) into a tail character (wasd
). In the snake struct, update the x and y coordinates of the tail.
update_tail |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be updated |
int snum |
The index of the snake to be updated | |
Return values | None |
As an example, consider the following board:
##############
# d>> #
# * #
# ^ #
# ^ #
# ^ #
# w #
# #
# #
##############
Assuming that state
is a pointer to this game state, then update_tail(state, 1)
will move the tail of snake 1, leaving all other snakes unchanged. In the snake_t
struct corresponding to snake 1, the tail_y
value should be updated from 6 to 5, and the tail_x
value should stay unchanged at 9. The new board will look like this:
##############
# d>> #
# * #
# ^ #
# ^ #
# w #
# #
# #
# #
##############
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 4.5: update_state
Using the helpers you created, implement update_state
in state.c
.
As a reminder, the rules for moving a snake are as follows:
- Each snake moves one step in the direction of its head.
- If the head crashes into the body of a snake or a wall, the snake dies and stops moving. When a snake dies, the head is replaced with an
x
. - If the head moves into a fruit, the snake eats the fruit and grows by 1 unit in length. (You can implement growing by 1 unit by updating the head without updating the tail.) Each time fruit is consumed, a new fruit is generated on the board.
The int (*add_food)(game_state_t* state)
argument is a function pointer, which means that add_food
is a pointer to the code section of memory. The code that add_food
is pointing at is a function that takes in game_state_t* state
as an argument and returns an int
. You can call this function with add_food(x)
, replacing x
with your argument, to add a fruit to the board.
update_state |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be updated |
int (*add_food)(game_state_t* state) |
A pointer to a function that will add fruit to the board | |
Return values | None |
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 5: load_board
Implement the load_board
function in state.c
. This function will read a game board from a file into memory.
The game board can be of any size, but you may assume that the board is shaped like a rectangle (each row is the same length), with walls on all four sides.
Tasks 5 and 6 combined will create a game_state_t
struct in memory with all its fields set up. In this task, you can leave num_snakes
and the snakes
array uninitialized, as long as x_size
, y_size
, and board
are correctly set up.
load_board |
||
Arguments | char* filename |
The name of the file where the board is stored |
Return values | game_state_t * |
A pointer to the newly created game_state_t struct. |
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 6: initialize_snake
Implement the initialize_snake
function in state.c
. This function takes in a game board and creates the array of snake structs.
You are free to implement this function however you want, but you'd like, you can work through this task by implementing the helper function we've provided.
Task 6.1: find_head
Implement the find_head
function in state.c
. Given a snake struct with the tail coordinates filled in, this function traces through the board to find the head coordinates, and fills in the head coordinates in the struct.
find_head |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be analyzed |
int snum |
The index of the snake to be analyzed | |
Return values | None |
As an example, consider the following board:
##############
# #
# * #
# #
# d>v #
# v #
# ^ v #
# ^<<< #
# #
##############
Assuming that state
is a pointer to this game state, then find_head(state, 0)
will fill in the head_x
and head_y
fields of the snake 0 struct with 3 and 6, respectively.
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 6.2: initialize_snake
Using find_head
, implement the initialize_snake
function in state.c
. You can assume that the state passed into this function is the result of calling load_board
. This means the board-related fields are already filled in, and you only need to fill in num_snakes
and create the snakes
array.
You may assume that all snakes on the board start out alive.
initialize_snakes |
||
Arguments | game_state_t* state |
A pointer to the game_state_t struct to be filled in |
Return values | game_state_t* state |
A pointer to the game_state_t struct with fields filled in. This can be the same as the struct passed in (you can modify the struct in-place). |
Use make run-unit-tests
and make debug-unit-tests
to run the provided unit tests.
Task 7: main
Using the functions you implemented in all the previous tasks, fill in the blanks in snake.c
. Each time the snake.c
program is run, the board will be updated by one time step.
To test your full implementation, run make run-integration-tests
.
To debug your implementation, run cgdb --args ./snake -i tests/TESTNAME-in.snk -o tests/TESTNAME-out.snk
, replacing TESTNAME
with one of the test names in the tests
folder:
1-simple
2-direction
3-tail
4-food
5-wall
6-small
7-large
8-multisnake
9-everything
Task 8: README
Congratulations on finishing the project! This is a brand-new project, so we'd love to hear your feedback on what can be improved for future semesters. Fill in README.md
with your thoughts about the project: how long did each task take you? What were some bugs you encountered? What was the hardest/easiest/most fun/least fun part of the project? Anything you'd like to say about the project is fair game here, but 512 characters minimum, please!
Submission and Grading
Submit your code to the Gradescope assignment. Make sure that you have only modified snake.c
and state.c
. The score you see on Gradescope will be your final score for this project.
Just for fun: play snake
Now you can play a game with the code you've written by make interactive-snake
followed by ./interactive-snake
. To speed up the game, you can run ./interactive-snake -d 0.5
(replacing 0.5 with the number of seconds between time steps).