This is a release announcement for Tetronimia: an implementation of a famous game mechanic for you terminal written in Nim.
“The only winning move is not to play”
There’s probably no one on the internet who doesn’t know the original game and doesn’t hear the earworm of a theme “Korobeiniki” instantly playing in their minds just from looking at these blocky figures.
To be honest, I don’t actually like computer games. This is a wrong thing to say for a game announcement, but bear with me for a moment. I feel good playing some of them but this actually annoys me even more, because in my mind there’s a few problems with this process. I think that computer games in general:
Tetronimia does all of the above and not a lot more. In this sense it’s the ideal. Writing a game shares a lot of the same features, just worse, and I find the irony of that perversely satisfying.
And, of course, making a version of the original game is kind of a rite of passage for coders so why not?
No complicated rotation systems, no wall kicks, no music, no gui, no net usage, no telemetry, no ads, no winning.
Installation instructions are given on the game’s Github repo.
You can download the binaries here: Download
The game has a basic set of options, available via --help or -h argument.
The keyboard controls are slightly unusual choice for a game, but some of you may know why and I hope most will appreciate the choice after a couple of minutes: HJKL for Left, Down, Rotate, Right, Space or D for Hard drop, F for the Hold box, P or Esc for pause, Q for quitting.
The defaults are chosen to be “perfectly balanced”. If you think you’re not good enough, use the Hold box (-b, off by default). If you think otherwise, choose the nastier -s w speed curve, turn off the Hard Drop (-D), the Ghost (-G) and that tiny delay on line clear (-L). You’ll suffer harder, but not for long.
Don’t try to translate it from Latin, it just pretends to be it (even though you might find the results of a translation surprisingly fitting).
It has Nim and that other thing inside and sounds like a disease, what’s more to want.
The Game is written in Nim and the source code is freely available. The only third-party libraries used are cligen and zero-functional.
The exploratory and for-fun nature of the project gave me a freedom to try a few things:
Unsurprisingly, the original game has a lot of official and licensed versions and some of them differ in rather substantial ways. Surprisingly for me, there’s a whole bunch of rotation schemes for the figures used in these games. They mostly differ in where the center of the rotation is, which sometimes results in different amounts of orientations for the given piece, and in the starting orientations. I implemented just one of the rotation schemes (the oldschool one) but I made it trivial to add more if necessary.
Some of the implementations I saw previously encode piece bitmaps as a sequence of 4×4 character grids such as @[@[" ", " # ", " ###", " "], ... ], sometimes these grids are even dragged throughout game logic. This is of course completely unacceptable for us! What a waste! Of course we strive for total man-machine singularity so we know there’s nothing in this world but ones and zeroes. In the code the pieces are encoded as arrays of uint16 which is exactly the number of bits we need for each cell:
[0b0000011100100000'u16, ...].
Much better! But we’d like to use the actual coordinates for the logic, so we need some way to convert this representation to a proper set of tuples. There’s a helper function tOffsets for this, and my favourite generic function apply:
func apply[T, N, U](a: array[N, T]; p: proc (x:T):U {.noSideEffect.} ): array[N, U]
I’m not going to explain it in case you don’t understand it from the declaration - you’ll need to trust me it’s cool. Using the couple of functions mentioned we get a nice static tuple containing arrays of occupied cell coordinates (in an array themselves) for each rotation of each figure. All done in compile time. That’s satisfying!
The pieces need to spawn and fall with a regular interval, independently of the player-induced movements. Some implementations use timers for this, but Tetronimia uses threads - let the OS do the work.
This is where new std/channels come in. They aren’t yet available in stable Nim, so you need a devel branch (you can easily install it using choosenim).
The code uses the channel as an event queue to send command messages between the threads. Before entering the main game loop we spawn a couple of them with spawn passing a message channel pointer in (instead of using a global variable). One thread for receiving keyboard commands and one for sending a “descend” message in a regular interval which depends on the current level. The threads send the appropriate messages in a timely manner, the main loop check the message buffer for new commands and reacts accordingly. Nothing blocks, everything works as expected.
The code doesn’t use any seqs which are the dynamic arrays in Nim, except for some string (which in Nim is just a distinct seq of chars) variables for the status line and game-over message. Both the terminal buffer and the field of cell objects (which hold the information about its kind and color) are a bunch of statically sized arrays. The size of the playing field is encoded as a const value and all the arrays used depend on it.
Another common trope is to “never use linked lists” in your code, so that’s exactly what I did! One of the main mechanics of the game is the disappearing of fully filled lines of cells. This happens fairly often so it’s natural to think you should use a data structure which allows for removing those lines as efficiently as possible. The one common data structure with the fastest element removal from the main body (not just from the beginning or the end) is a linked list. Find the node N-1 (previous to the one holding the element being deleted) and rewrite its next pointer with the next pointer of the node N about to be deleted. The operation would be just an ideal Θ(1) weren’t it for the search time you actually need to spend each time addressing a particular Node.
What’s worse, linked lists bring a layer of indirection necessary for following the pointers and have poor data locality and use more memory. It probably affects the performance stronger than rewriting the contents of a bunch of nested arrays. All in all, for the default measly size of a playing field it’s not a good choice. Just use the arrays, iterate them, zero the filled ones and swap them around with a couple of cursors (or bubbling the empty ones to the top). Very (extremely) cheap for short data. All done with a bunch of built-it functions. But this is not our way. When would I ever use singly linked lists if not here? It’s much more fun to write a version of keepIf (Nim’s inverse of a retain) for singlyLinkedList and I had to limit myself and not implement it as a generic higher-order version. By the way, the actual performance difference for removal is still an open question for me but it just gets too silly to benchmark it.
Oh, and of course, when you consider that even more frequent operation is the actual insertion of the pieces to the pile (which needs 4 direct addresses) you just chuckle and use linked lists anyway. Because what matters at this scale is just having fun.
I’d love very much to decrease the number of line of code without hurting the readability. I suspect some logic can be simplified, but I don’t see any easy ways to do so.
I’m also waiting for CPS to land and I suspect it would be fun to port all the asynchronous functionality from threads to it.
Other rotation schemes can be easily added but I don’t see it bringing any fun neither for the players nor for the coder.
I’ll be happy to hear your feedback, bug reports and code suggestions here in the comments or in the project’s issues.
Thank you and remember: The only winning move is not to play.