Part 1: Exploring the Snake Game
Building the Code
After cloning the homework repository and opening it in VS Code, open the terminal pane and run make (or cs70-make -H) to build the provided code.
Running the Game
Then run the program in the terminal with
./snake
Press any key to start the game, then use these keys to control the snake (you don't need to hold the keys down, just tap them when necessary to change to a new direction):
| Key | Action |
|---|---|
| Q | Move Up |
| A | Move Down |
| O | Move Left |
| P | Move Right |
| Escape | Quit the game |
In the game, the snake (represented as oooo@) moves around the grid to eat food. Each time the snake eats food, it grows longer. The game ends if the snake runs into itself or the walls (#). There are three kinds of food in the game:
| Symbol | Kind | Points | Effects |
|---|---|---|---|
* |
Normal food | 1 | Increases length by 1 |
$ |
Mutagenic food | 5 | Increases length by 5 at/near tail end |
! |
Poisonous food | — | Calcifies part of tail into wall, decreases length |
By default, the layout of the game will be randomized each time you run it. If you want to play the same game again, you can use the --seed option to set the random seed. For example, ./snake --seed 42 will reproduce the game shown in the ascii-cast on the main assignment page.
Meh. Doesn't seem to have much to do with data structures. And, hey, it seems like it already works fine, so can we just quit now?
MORE games! I love games!
Wait, I think I see where this is going. The snake itself is a data structure, right? It has to keep track of all its segments, and it grows and shrinks as it eats food. So maybe we have to implement the snake using a linked list or something?
Motivation — Why We Need a Linked List
In the game, there are two key data structures. The first is the Gameboard, which keeps track of the walls, empty spaces, and food; it is exactly like the Maze class from the last assignment (in fact, it's just a relatively modest edit of that code). But in this game, we need to make the snake move across the screen. Let's call each o in the snake a segment of the snake, and, for simplicity, let's imagine that the snake's head is just another o segment. The key insight is that to make the snake appear to move, say, left-to-right across the game board, we draw the head of the snake in a new cell to the right and erase the leftmost tail segment of the snake, restoring it to an empty space—all the other segments stay the same and don't need to be redrawn. Just by changing two cells on the board, we would create the illusion of the entire snake moving right.1
These requirements make the snake a perfect example of a queue data structure in action: to move the snake we add the position of the new head segment to the queue (using our current movement direction), and remove the position of the final tail segment from the queue and erase it. (Somewhat confusingly perhaps, the newest head segment position is at the back of the queue, and the oldest tail segment position is at the front of the queue.)
-
Okay, but how does the snake GROW?
For normal growth, all we have to do is not do something. If we don't remove the tail-segment position on the next move, the snake will grow by one segment. For mutagenic growth, we need to go beyond the basic queue operations. For example, if we have the option to push a new segment position onto the front of the list rather than the back, we can extend the tail of the snake. (We're simplifying a bit, since the mutagenic growth is supposed to happen somewhere near the tail, not necessarily at the very end, we'll stick with this explanation for right now.)
Hay! This totally reminds me of the
CoordVectorclass we built in the last assignment! It does exactly what we need!
The CoordVector class we built in the last assignment seems like the perfect fit for implementing the snake, given that it supports efficient addition and removal of elements at both ends. However, CoordVector is implemented using a primitive array with successive doubling, which means that growing the snake can sometimes require all the elements to be copied to a new, larger, array. There's an argument we'll use in a future lesson that—across the entire execution time of the program—the average time per operation is still constant time, but in an application like a game, we don't care about the entire execution time, we care about the time per frame. If a frame takes a long time to compute, the game will appear to stutter or lag, which is bad for user experience, and that's exactly what can happen if we periodically have to copy the entire array to a new location. And that is where a linked list comes in… (more details in the next part of the assignment!).
-
Hay! I didn't see any stuttering when I played the game just now.
Well, that's because our server machine is so fast that the copying happens very quickly. But people play Snake games on all sorts of devices, including phones, wearables, and retro computers, which might not be as fast. And even on a fast machine, if the snake gets very long, the copying could still take a noticeable amount of time.
So you're saying we should use a linked list instead of an array-backed list?
-
Yes! A linked list can perform all the operations we need in constant time, without ever needing to copy the entire list. So it will provide a smoother experience for the user.
-
Cool! So we need to implement a linked list, right?
-
Right! But before we do, let's take a step back and think about the interface and encoding of the data structure we want to implement.
You can move on to the next part, but here's a little more about the game for those who are curious…
In this assignment, rather than use lists of Coord values, we've used lists of ints. We've added pack and unpack functions to the Coord type that convert between a Coord and a single int value. (This change is mostly just for variety, so that you're making a different kind of list than you did in the last assignment.)
Although you won't need to edit the game code in this assignment, it has a lot in common with the maze code from the last assignment. Specifically, it uses exactly the same Display class to handle terminal output, and, as mentioned above, the Gameboard class is very similar to the Maze class. The game logic itself is in the Game class, which should be easy enough to follow if you're curious.
-
Moving the snake actually requires us to update three
Gameboardcells, as we need to change the old head cell from@tooas well. If we hadn't decided to make the head of the snake look different, we'd only need to modify two cells. ↩
(When logged in, completion status appears here.)