Who doesn’t love Tetris? Until recently it was the most popular game of all time*, and for good reason. I had always wanted to write my own version of Tetris, but it always seemed to be more difficult than I was prepared for. This summer I finally decided to take an afternoon to sit down and write my own version. I finished about 6 months later.
I wrote the game in C using pthreads and ncurses. You can find the entire codebase on GitLab at https://gitlab.com/midfords/titanium-tetris. While writing the game I came across a few challenging problems, and I wanted to take some time to describe some of my more clever insights and solutions. If you’re interested, there are instructions for how to run and play the game in the project’s readme file.
* Surpassed by Minecraft in 2019.
Threading
My version of Tetris is broken down into a series of threads, each having a different responsibility. Each player runs in a separate thread, each with its own timer and fall thread. The input thread handles keypresses and the main game thread handles pausing and quitting.
The main breakdown of the threads looks like this:
-> input
main -> player (1) -> fall
-> timer
-> player (2) -> fall
-> timer
- The main thread is responsible for handling pause and quit actions, and joining the player threads once the game is over.
- The input thread is responsible for receiving all keyboard presses and queueing corresponding actions for each of the player threads and the main thread.
- The player thread handles the gameplay for a single player.
- The fall thread is a simple timer that forces a move down action on an interval.
- The timer thread just tracks the playtime for a player.
Action queues are set up between the input thread and the main and player threads. This allows input actions to be passed to the appropriate thread to handle.
I tried to write the code in such a way that most of the gameplay logic is unaware of how many players there are, be it one, two or more. There are only three spots in the code that specifically need to know how many players there are, the main thread, the input thread and the print controller. The player, fall and timer threads are duplicated for each of the players.
The only thing preventing additional players are physical limitations, like the number of keys on the keyboard or the size of the screen.
2D Arrays and Piece Orientations
Arrays in C can get messy. Dynamically generating a 2d array of size n x m means to create a pointer, point that pointer to an array of pointers of size n, then looping through and pointing each of those pointers to another array of size m in which the actual values are stored.
_ _ _ _ _
a* -> |_| -> |_|_|_|_|
|_| -> |_|_|_|_|
|_| -> |_|_|_|_|
|_| -> |_|_|_|_|
Changing the orientation of a 2d array in C would mean traversing all the elements in the sub arrays and swapping them around (a O(n) operation that can be fickle to get right). In Tetris, each tetra is a static shape and only the orientation will ever change. Allocating dynamic arrays for this is not ideal for a few reasons.
_
_ |_|_ _ _ _
_|_|_ -> |_|_| -> |_|_|_|
|_|_|_| |_| |_|
For one, we would not be able to treat the shapes as constants, even though they never change. For another, rotating each piece would take an inefficient O(n) operation to swap each of the elements with another. It would also mess up the code by adding more logic to allocate and free memory for each of the tetra types.
Instead of trying to manage a bunch of allocated 2d arrays and changing orientation by swapping positions, I allocate 1d arrays and interpret them as 2d using a point calculating function.
_ _ _
_ _ _ _ _ _ _ _ _ |_|_|_|
|_|_|_|_|_|_|_|_|_| -> f() -> |_|_|_|
|_|_|_|
Now each tetra can be defined as a 1d static array. All tetras are also defined as squares with equal height and width. This makes it possible to change them into any rotation. If a 1 represents a block, and a 0 represents transparency, the 1d static tetras would look like this:
tetra1 = {
0, 0, 0, _
0, 1, 0, -> _|_|_
1, 1, 1 |_|_|_|
}
tetra2 = { _ _
1, 1, -> |_|_|
1, 1 |_|_|
}
…
The 1d array is interpreted as a 2d array by using the following function:
p(x, y, l) -> x + (l * y)
This function takes the array length, the desired point (x, y) and finds the relative index in a 1d array. We can elegantly interpret any 1d array (of equal height and width) as a 2d array by using this function.
Even better is how easily orientation changes can be implemented using this method. All we need to do is define four point calculating functions, each interpreting a 1d array as a 2d array in a different orientation. So we define functions for north, east, south and west like so:
no(y, x, l) -> x + (l * y);
ea(y, x, l) -> l * (l – x – 1) + y;
so(y, x, l) -> (l * l – 1) – (x + (l * y));
we(y, x, l) -> l * (x + 1) – 1 – y;
To maintain a tetra’s state, I use a struct with a pointer to the current tetra array and a pointer to the function for the current orientation. We can essentially change a tetra’s orientation in O(1) time just by swapping out the point-interpreting function. Here’s what the struct for a tetra + state looks like:
struct tstate {
int* tetra; // static 1d array for the tetra
int (*p)(int, int, int); // pointer to the interpreting function
}And accessing the 2d tetra looks like this:
tstate->tetra[ tstate->p(x, y, l) ];
This works great to decouple the orientation logic from all other parts of the code. The entire program can remain blissfully unaware that there are different orientation states for a tetra, or that the tetras are stored as 1d arrays. Specifically, it helps to simplify the print controller and gameplay logic. The only part of the code that should be aware of the orientation changes, is the part of the code that handles them. We can now define simple, constant arrays for each of the tetras and manage the orientation separately. Best of all, we can rotate them in constant time!
Random Pieces
In a two player Tetris game, both players should receive the same pieces in the same order. Otherwise, how could it be a fair game? This poses a potential challenge though, since the game must then track a queue of pieces for each player thread to use simultaneously. It needs to allocate new pieces, free old pieces and keep track of the positions of both players in the queue. This can also be prone to bugs since each player is running in a separate thread, but the piece queue must be shared between them. Or does it?
The first approach I took seemed obvious. Being careful about mutex locking to avoid race conditions, I allocated a queue of pieces for both players to follow. When both players have used a given piece, the memory is freed. When a player is at the front of the queue and needs a new piece, one is allocated and added to the top of the queue. Here’s an example:
()->()->()->()->()->()->()->NULL
^ ^
1 2The head of the queue will be freed when player one requests their next piece, and a new tail will be randomly generated when player 2 requests a new piece.
This works, but it’s not very elegant. The code becomes a mess with checks for which player is in the lead, when it is safe to free a piece or when to allocate a new one. Not to mention, if one player game-overs and the other player continues, the piece queue will grow and consume more and more memory. Ideally we’d like to find a solution that does not require additional memory, is inherently thread-safe, and where the code is simple and elegant.
I’ll explain how I solved this, but first, a brief review of how random numbers work in a computer.
Random numbers
Generating random numbers in your computer is like trying to generate them on your calculator. Any method you use to get a number can be reproduced to get the same number every time. How then do we get random numbers in computers? The secret is we actually don’t. Random numbers in a computer are not truly random, they’re pseudo-random (or random enough).
They’re generated using clever mathematical equations that start with a certain number called a seed value, and then produce a seemingly random set of numbers thereafter. Since it’s just an equation, if the same seed value is used twice, then the same set of random numbers will be generated in exactly the same order.
So, instead of tracking a queue of pieces between the two players and freeing/allocating memory accordingly, all we really need is a custom random number generator. One where we can track the current seed state for each player separately. That way, each player simply starts with the same seed value, and because the random number generator is deterministic, it will produce the same “random” numbers in the same order.
From what I’ve read, this doesn’t seem to be possible using the C standard library. Their random number generator tracks its state internally, and can’t track multiple states or have a state passed in at the time of calculation. That’s okay, I just had to write my own:
unsigned long a = 282475249;
unsigned long r = 9223372036854775783;
double getDouble(unsigned long * seed) {
unsigned long s = *seed;
s = (s * a % r);
if (s < r) s = s + r;
*seed = s;
return (double) s / (double) r;
}Then the players retrieve their next pieces like so:
nextPiece(int *seed) -> getDouble(seed) * 7
In this version, a reference to the seed value is passed in each time. Both players can track their own state and get the next piece from the queue, without needing to allocate an actual queue. This solution not only takes about 10 lines of code, but is more efficient, doesn’t require any additional memory and is totally thread safe. Nice!
Print Diff Function
A large portion of the code written for this game is in the print controller. This is the part that handles all of the output for the game. Essentially the internal state of the game doesn’t look anything like the output of the game, and it’s up to the print controller to interpret the boards, pieces, and scores and output everything in a pleasing way.
My first solution to printing everything was crude, coupled, and messy (noticing a pattern?). Each operation exposed two functions, one for clearing an object and one for printing it. This method had pros and cons. A pro was that it left the print controller stateless and light on logic. The con, however, was that it was only light on logic because the main game and player threads were handling the printing logic instead.
Every time a piece was moved, the orientation changed, lines were cleared, or the output was otherwise changed, the game and player threads would send a call to the clear function for the previous state, do some operation, and then call a print function afterward. For example, tetras would have been updated like so:
// Clear the old state from the output
printer->clear_tetra(tetra);
// Do some operation. For example, a rotation
do_operation(tetra);
// Print the new state back to the output
printer->print_tetra(tetra); These clear and print functions were everywhere and ended up making a complete mess of the game logic. So I rewrote everything taking inspiration from Facebook’s React framework. Technically, it ended up being a little less efficient, but I think the trade-off was worth it since it made the code base much more readable.
Instead of exposing functions for clear/print tetra, clear/print board, clear/print score, etc. I expose a single function called update. The print controller holds an internal state of what is currently showing on the screen. The update function acts like a diff between the current state and the desired state of the output.
Current state Desired state
_ _ _ _
_ |_|_ |_|_| |_|_
|_|_|_|_| -> |_|_|_|_|_|
|_|_|_| |_|_|_|_|The print controller only updates the spots which have changed simplifying the game controller to this:
do_operation(board);
printer->update(board);Much better. We can clearly see where the board is being updated and the main game controller and player threads no longer care about how the board is being updated. All the game updates are now done using just a single update() function.
As I’ve said, this is a bit less efficient. Before, only the affected area would be checked and updated, and now a diff is done over the whole board every time an update is requested. However, since the board is only 20 x 10 = 200 blocks, the diff method is still lightning fast.
C Caveats
Although I’d like to think differently, this program isn’t perfect. There are a few awkward spots that I can’t find satisfying solutions to. These problems would probably be simpler to solve in a higher level language like Python or Java, I just choose C as a challenge to myself and so my low(er) level programming skills wouldn’t get too rusty.
I think the biggest problem in this program is caused by how Linux handles input streams. Ideally when playing Tetris you want the controls to be as responsive as possible, especially when playing at higher speeds. For example, if you hold the right arrow, you want the piece to continuously move across the board in uniform intervals. Unfortunately, how my version of the game works is more like key repeating in a word document. If you hold a key, the cursor pauses for a moment before the key repeating starts. This problem is exacerbated during two player games since the input for both games is being handled by a single thread. Players can interrupt each other’s key repeating inputs.
This problem is actually caused by how Linux handles the input pipe. Direct access to the hardware is not allowed, and we can only read a sequence of characters from the input stream. The key repeat action is handled by the operating system, and polling specific keys on the keyboard is not possible, so I can’t implement my own version of a key repeater specific to Tetris.
The other major problem has more to do with efficiency. The game is run in multiple threads: one for the game, one for each of the players, one for the input, etc. The ncurses keyboard input function that I’m using, getch(), is blocking. It also doesn’t work with multiple calling threads. This means the input thread must be responsible for serving all input to the program, and put action events in a series of queues to each of the player threads and the main thread.
The player threads can’t block waiting for input, because they also need to handle game overs or pauses which can be triggered by other parts of the code (not just from the input controller). To manage this, I use something that I call a “kick”. It works by having both players and the game controller wait in a function until a kick is sent. This can happen when either new input comes in, or when some other part of the program signals that something has changed (like a pause signal was received, or a game over occurred). The threads will wait until they’re unblocked from the wait function so they can handle whatever the event was.
I implemented the waitForKick() function with a spinning while loop that continually checks for a kick. This is bad because the spinning while loop is very inefficient, the proper way to implement this would be to use a pthread signal or conditional wait instead.
Conclusion
Although I enjoy using C very much, and relish the low-level control the programmer is given, it can be difficult to work with. Errors are not handled very well, they always manifest themselves as segmentation faults. The low level threading can also be tricky to get right.
Overall though, I’m pretty happy with how this program turned out. There are a few really great programming moments that elegantly solved challenging problems, and I managed to include all of the extra features that I dreamed up.
Cheers! 🍻
