path: root/docs/projects/sirtet.md

# SIRTET

2022-06-17

I saw my mother play a mobile game the other day. She invited me to play
along. It was one of these Tetris knockoffs where you drag one of the
three given tetromino-like pieces (although there are many more, some
aren't even continuous) onto an 8x8 map without overlapping, and each time
you fill a row or column it clears up with a pleasant explosion effect.
When you manage to place all three, they give you three more. The game is
over once none of your pieces can be placed. This is fun and all, but
there were ads after each game. I began to ponder: Can I make it in C?

Of course I can. The map is just an 8x8 array (but I wish to make the size
adjustable), and the pieces are just smaller arrays with some metadata.
This just sounds like another CS101 assignment. I just need to be really
careful with pointers and better yet, double pointers.

## First prototype

The initial design is that the map is an array of pointers representing
rows, which point to arrays representing blocks of each row. Each block is
a `char`, which is a space (`0x20`) for vacant blocks and a plus sign
(`0x2b`) otherwise. Both the `char`s and `char*`s were manually malloc'd
so as to avoid variable length arrays (VLA).

As to the pieces, I defined `struct piece` with three attributes:

- Height `int h`
- Width `int w`
- `char* blocks`

The length of `blocks` is `h * w + 1` including the null terminator, and
represent the flattened shape of the piece. Examples are:

- `+` ← a single block
- `++` ← 1x2 or 2x1, depending on `h` and `w`
- `++++  ` ← a 2x3 L shape (see below)

(For consistency, when I say `m x n`, I mean `m` rows by `n` columns.)

I came up with 17 shapes, but a problem arises. If you need a slim
L shape, there are four directions you can rotate it into; moreover, you
can transpose each of them, making it eight:

```
++   ++   +     +
+     +   +     +
+     +   ++   ++

+++  +    +++    +
+    +++    +  +++
```

We can either define all the rotated and transposed versions for these 17
shapes, or implement some rotation and transposition functions, which
turned out not difficult to write. They basically did these four things:

- Take a `struct piece*`, denoted `pc`
- Make a backup of `pc->blocks` in local variable `old`
- Carry out the rotation/transposition from `old` to `pc->blocks`
- Swap `pc->h` and `pc->w`

When handing out a piece to the player I just need to

- Draw a random piece from the pool of 17
- Rotate it 0 to 3 times
- Transpose it 0 or 1 time
- Put its pointer somewhere in the player's array of `struct piece*`s

It turns out, since the pool of 17 should be (and is) immutable, I have to
make a copy before I do anything to them. It is malloc'd and thus has to
be free'd when it is placed on the map.

The rest of the code is just `if`s and `for` loops. Within a few hours
I was able to throw together a stdin-stdout version of the game, which
I named SIRTET (its relationship to Tetris is left to the reader to
decide). Here is a demo of the first two steps of the game:

```
$ ./sirtet
 --------
|        |
|        |
|        |
|        |
|        |
|        |
|        |
|        |
 --------
Piece 0
++
++

Piece 1
   +
++++

Piece 2
++
++
++

Input [piece #] [row #] [col #]: 0 0 0
 --------
|++      |
|++      |
|        |
|        |
|        |
|        |
|        |
|        |
 --------
Piece 1
   +
++++

Piece 2
++
++
++

Input [piece #] [row #] [col #]: 2 2 0
 --------
|++      |
|++      |
|++      |
|++      |
|++      |
|        |
|        |
|        |
 --------
Piece 1
   +
++++

Input [piece #] [row #] [col #]:

```

And guess what? Zero memory leak! Check out this beauty:

```
$ valgrind --leak-check=full --show-leak-kinds=all ./sirtet
==46064== Memcheck, a memory error detector
==46064== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==46064== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==46064== Command: ./sirtet
==46064== 
 --------
|        |
   ....
|        |
 --------
Piece 0
+++
+++
+++

...

Input [piece #] [row #] [col #]: 0 0 0

[15 steps later]

Game over
==46064==
==46064== HEAP SUMMARY:
==46064==     in use at exit: 0 bytes in 0 blocks
==46064==   total heap usage: 115 allocs, 115 frees, 3,069 bytes allocated
==46064==
==46064== All heap blocks were freed -- no leaks are possible
==46064==
==46064== For lists of detected and suppressed errors, rerun with: -s
==46064== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```

I know it's a tiny accomplishment, but it made my day.

Now, a few problems. This `Input [piece #] [row #] [col #]: ` prompt isn't
super friendly, and ideally I should be able to control everything with
a consistent keybinding. And having a map that appears twice as high as
it's wide sure isn't pretty. That's when I thought of ncurses.

## ncurses

I've always wanted to use ncurses somewhere. My CS professor promised
a bonus if I had used ncurses for a course project called One Card, an Uno
knockoff (why are all my projects knockoffs?), but I was struggling to
stop it from segfaulting. Now that I've tackled those, I can finally try
it out. I got my tutorial at [tldp](https://tldp.org/HOWTO/NCURSES-Programming-HOWTO/).

It turns out pretty straightforward. Instead of `printf`ing, you just `mvprintw`
(where `mv` stands for move and `w` stands for window) by supplying a pair of
coordinates; the same goes for other functions. To draw a solid block at `(y,
x)`, all I had to do is print two inverted spaces:

```
mvaddch(y, x, (' ' | A_REVERSE));
addch(' ' | A_REVERSE);
```

The second line did not need a `mv` because the `mvaddch` above
automatically moves the `x` coordinate to the right by one. To draw
a rectangle, I just put `ACS_HLINE`, `ACS_VLINE`, `ACS_ULCORNER` etc. at
all the right places. ncurses provided macros and functions for colors
too.

Soon, I was able to draw the map, the piece hovering above to be placed,
and the rest of the pieces.

I also managed to react to the player's keystrokes with `getch()`.
I defined three sets of navigation keys: arrow keys, wasd, and of course
the vim user loyalty, hjkl. The player may also press `[` and `]` to
switch pieces. There were a lot of switch-cases and bound checking.

Finally I used `getopt.h` for the first time to parse CLI arguments, aka
`argv`. The concept of storing argument values in global variables
honestly surprised me, but having done some AVR, I got over it very soon.
You can customize the map size (both height and width independently), and
the maximum number of pieces you have at once. My editor plugin warns me
about insecurities in `sscanf`, but I disregarded them.

I tried valgrind on the ncurses version, but the results were monstrous.
It was later revealed to me that ncurses does a lot of memory management
itself and inevitably it will confuse valgrind. ncurses does provide
a workaround to debug memory usage. Anyway, at this point there is no
longer any point. I proceeded to add a few fancy things like game stats
and called this project complete.

## Demo

<video controls><source src="../img/sirtet/demo.mp4"></video>

MPEG-4 Video (252 KiB)

## Room for improvement

This whole project was made with a premise in mind that no one else would
play it. If anyone else were to play it, I would have made a few
adjustments:

- `--no-color` option, i.e. use monochrome indicators other than red/green
- Highscore
- `--help` option