Gauss-Jordan Elimination - The Game
Tags: gamedev, mathematics, pico8
Published: 2023-08-06 20:39:52

Have you ever dreamed about playing educational games with fun mathematical concepts? No? Anyone?

In an attempt to make a casual puzzle game with new "innovative" mechanics I've spent countless showers thoughts trying to figure out how to use mathematical algorithms to create fun little games.
One of these algorithms is the [Gauss-Jordan elimination](https://en.wikipedia.org/wiki/Gaussian_elimination), an algorithm that I won't be able to forget after staying up late finishing my endless linear algebra homework over the weekends.

I won't be explaining the full details of this algorithm on this post, but here's a brief refresher. 

## Gauss-Jordan Elimination

This algorithm was designed to solve systems of linear equations through matrices and row operations. Let's say we have the following system:

- 2x – y + 3z = 9
- x – 3y – 2z = 0
- 3x + 2y – z = -1 

### Start-point
To solve it, we start by placing it all into a single 3x4 matrix, where the last column equals the results of each equation.
```
  x  y  z 
| 2 -1  3  9 | x
| 1 -3 -2  0 | y
| 3  2 -1 -1 | z
```

### End Goal
It'll be solved once we have an inner 3x3 identity matrix on the left. The results for each variable will be on the last remaining column.
```
  x y z
| 1 0 0 11/27 | x
| 0 1 0 5/27  | y 
| 0 0 1 62/27 | z
```

### Rules
To solve it we need to follow a set of rules and constraints, like a game. 
These rules consist of some basic row operations: 
- Any two rows in the matrix may be interchanged.
- Any row may be multiplied by a non-zero constant.
- A constant multiple of a row may be added to another row.

We can do these operations as many times as we want, although some ways are more efficient than others, the solutions are rather "open-ended".

## Making a game out of this
In my mind, this algorithm made for a "good" puzzle game. We have a set of rules, a initial state and an end goal. In a game, we could somehow get rid of the explicit numbers and arithmetic, change the initial state and the end goal to be whatever we want.
 
Maybe instead of the identity matrix as an end goal, we want a cross of 1s, or a sequence of numbers from 1 to 9, maybe we can use colors instead of numbers, or gems at different temperatures, etc.

So what does [the game](https://www.lexaloffle.com/bbs/?tid=37349) look like? Unfortunately, it looks like this:

![Gauss alchemyin action](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8r6wt4mb1lzm33nrnlp3.png)

To make development easier, I decided to use Pico8. A fun little tool that allows you to make fast pixelated game prototypes, or even a full fledged [Doom de-make](https://www.lexaloffle.com/bbs/?tid=45572).

I tried to get rid of the numbers to alleviate some of the complexity of the algorithm and came up with a simpler "circular" system of colored blocks. It's basically five colors that internally match five numbers from -2 to 2 (-2, -1, 0, 1, 2).

![Colors go from "hot" to "cold"](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/umrm98a8awsdclwotcwd.png)

Each colored block is supposed to represent a number, and you only have a 3x3 matrix of blocks to play with.

### How to play

The rules of the game are almost the same. You start with an initial state of colored blocks and your end goal is to produce the same block matrix as displayed on the small computer monitor below.

![Initial state](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xjjzvskl1kmr2l5gylr1.png)

![End goal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kwj80a07izir9luan2ri.png)

In order to achieve this, you have three basic actions at your disposal:
- Change colors of a row (Z and X keys)
- Add rows (Left arrow)
- Swap rows (Right arrow)

Changing the colors of a row is the equivalent of multiplying a row by a scalar in the Gauss-Jordan elimination. Internally, it's simply adding +1 or -1 to all the blocks in a row, changing each color to the next one.

Adding rows and swapping rows behave almost the same as the original algorithm, although internally the arithmetic behaves a bit differently.
Adding two blocks means adding two numbers, however, adding the same number will have no effect, so 2 + 2 = 2 (red + red = red).
Since the numbers system is "circular" adding 2 + 1 will overflow and result in -2.

```
if gem1 ~= gem2 then
    gem1 = gem1 + gem2
end
-- Control overflow
if gem1 > maxI then
    gem1 = minI
elseif gem1 < minI then
    gem1 = maxI
end
```

With these basic operations, you're good to go and achieve almost any desired block configuration as long as you understand what is even going on.

## Is it fun yet?

In the end this was a fun yet frustrating little experiment on game design. Learned a bunch of stuff about Pico8, Lua and what makes, or rather, what doesn't make a game fun. It turns out game design is a heavily iterative process and unlike Gauss-Jordan, you don't really know what your end goal is going to look like.

I spent so much time tweaking the game mechanics and changing stuff here and there, until I could find something that was close to being fun and accessible. Needless to say, I have yet to find a way to make this game fun and easier to understand. Maybe, just maybe, there's simply no way to make a fun game out of Gauss-Jordan.

Feel free to check out this [Github repo](https://github.com/Gecko05/GaussAlchemy) with the source code and comment any suggestions if you dare play [this half-baked game](https://www.lexaloffle.com/bbs/?tid=37349) :).