## Text mode 2048 game in C, algorithm explained

2048 is hot! It may be considered the next Flappy Bird. I implemented 2048 in the C programming language, so you can run it on your Linux server on the console (in text mode). You can find the 2048.c project on Github.

### Rules

You can move the tiles in four directions using the arrow keys: up, down, left, and right. All numbers on the board will slide into that direction until they hit the wall and if they bump into each other then two numbers will be combined into one if they have the same value. Each number will only be combined once per move. Every move a new number 2 or 4 appears. If you have a 2048 on the board you have won, but you lose once the board is full and you cannot make a move.

### Algorithm

I chose to store the field in a two-dimensional array called board that is 4×4.

```[2][0][8][2]          [2][4][8][4]
[0][4][0][2]  press   [4][8][4][4]
[4][0][2][2]  up key  [0][0][0][0]
[0][8][2][2]          [0][0][0][0]
```

Since I want the board to be addressed as board[x][y], the board consists of a set of four columns size four. So the first column is the array [2,0,4,0]. If we press the up button this should become [2,4,0,0]. The function “slideArray()” is reponsible for this. This function will “slide” the numbers in the arrays like this:

```[2,0,4,0] => [2,4,0,0]
[0,4,0,8] => [4,8,0,0]
[8,0,2,2] => [8,4,0,0]
[2,2,2,2] => [4,4,0,0]
```

The algorithm can just use board[x] to point to a column and work directly on that. In pseudocode, this is what the algorithm does:

```- walk over the array from the first to the last number
- for each original number in the array that is not zero
- look backwards for a target position that does not contain a zero (unless it is position zero)
- if the target position does not contain the original number use the next position
- if the target position is different from the original position
- add the number to the number on the target position
- replace the original number by zero
```

The above algorithm executed will do all transformations, it will:

```[2,2,2,2] => [4,4,0,0]
[0,8,2,2] => [8,4,0,0]
```

But there is a problem, it will also do this:

```[2,2,4,4] => [8,4,0,0]
```

The two’s are merged into a four and then the first four is merged into that making it an eight. This is wrong. It should be doing this:

```[2,2,4,4] => [4,8,0,0]
```

This is avoided by adding a “stop” variable that will be initially set to zero, but when a merge has been done it will be set to the merge position plus one. This will make sure any next slide will stop before it merges into this number again, since double merges are not allowed.

To prevent complex programming I use a function rotateBoard that rotates the board 90 degrees counter-clockwise. This allows the moveLeft(board) to be implemented as:

```rotateBoard(board);
moveUp(board);
rotateBoard(board);
rotateBoard(board);
rotateBoard(board);
```

As long as you rotate four times in total everything works as expected. This method is not very efficient, but reduces the complexity of the code.

### Compiling and running

Since 2048.c is a single C file it is easy to get running, just execute the following commands:

```wget https://raw.githubusercontent.com/mevdschee/2048.c/master/2048.c
gcc -o 2048 2048.c
./2048
```

This will run on most machines. If not, then execute the following command to install the compiler:

```sudo apt-get install build-essential
```