Monday 28 March 2016

The inner workings of the game

Like many, I just released some games. Like not so many, they let you contribute to science. And since it's all for science, I have opened up the source for all to see. Here it is, on Dropbox. There are both Xcode and Unity projects here. Witness my coding and despair!

My games are pretty simple. It's all just buttons and text and pictures. Someone more competent than I could probably knock it out in a day or two. In fact, I plan to make a video where I will build one of the games pretty much from scratch, live!

This blog post explains what is going on in the code for version 1 of the Game Decodoku. Everything else is built on very similar principles.

How the game works

The game is basically an L grid of numbers, with L=8 for iPads and L=7 for iPhones. You push the numbers around and they add up (mod 10). Every so often, more of the buggers will come. The game ends when it all gets a bit messy. You can check out an extended tutorial here. I'll wait here while you read it.

So the main things to know are:
  1. How are the numbers generated and changed?
  2. What is the 'Game Over' condition?
Before we answer these, we should get to know a couple of arrays that describe what's happening on our grid

    int anyons[8][8], clusters[8][8]

Probably we should really have made these L×L arrays, but L is never larger than 8 so there's always room in these arrays to do what we need.

The purpose of the anyons array is to store all the numbers. If there is nothing on the square at (x,y), then

    anyons[x][y] = 0;

If there is a 7, for example, then

    anyons[x][y] = 7;

The array clusters deals with what we've called 'groups' of numbers in the tutorial. But we'll call them 'clusters' here. Each number in anyons that isn't 0 is assigned to a cluster. The first cluster ever to be created is called 1, and so on. For every non-zero entry of anyons, the corresponding entry of clusters will tell us what group it belongs to. Wherever there is a 0 in anyons, the entry in clusters is also 0.

Changing the numbers

Now we know where all the necessary info lives, let's get on with question 1. For this, we look at the generateNoise function in GameViewController.m.

The numbers always change in pairs. These pairs are always neighbouring squares. The amount that the numbers on the two squares will be changed by always adds up to 0 mod 10. Other than this, it's a random process.

To pick our random pair of squares, first we randomly pick one square by generating random x and y. Then we randomly pick one of its four neighbours, (x,y+1), (x,y-1), (x+1,y) or (x-1,y). We also have to remember that, on the edge, not all squares have four neighbours. So best not to choose a neighbour that doesn't exist.

Once we have the squares, we choose how much to change the one at (x,y) by. This will be a random number from 1 to 9 that we call a.

    anyons[x][y] = (a + anyons[x][y])%10;

The other one is similarly changed by aa=10-a to ensure that the sum of the changes is a multiple of 10.

This gives us things like this, where colours are just for emphasis.
Once generateNoise has done a pair of changes, it'll go back and do it again. So when does it stop?

Each pair of changes is assigned a different weight, depending on what kind of changes were made. Those that create two new numbers (meaning that there were only zeros in those squares before) have weight 1. Those that create one new number, and either change or remove a number on the other square, also have a weight of 1. Those that don't create anything new, just changing or removing what's already there, have a weight of 0.1.

The function generateNoise keeps adding changes until a weight of 6 is reached. Then the player is allowed to actually do something at last.

What the player can do is move a number from one square to a neighbour. When this happens, they add up mod 10. So we are basically trying to undo what the errors have done. However, we only have 5 moves before generateNoise returns and does another bunch of changes with total weight of 6.

Since this function basically does 6ish bad things and we only have time for 5 good things, the numbers are going to build up over time. In quantum error correction, this is called operating above the noise threshold and is bad. In gaming it is called not having a game that goes on too long and gets boring, and is good.

When do we lose?

The losing condition is all about the clusters. Once a cluster spans from top to bottom or left to right, you lose.

Actually, that's not quite true, if it's generateNoise that grows the clusters until they span the grid, you are still given your 5 moves to try fixing it. But if you fail, you fail.

To check, we do this

    int spanners = 0;
    for (int J=0;J<L;J++){
        for (int K=0;K<L;K++){
            spanners += (clusters[J][0]==clusters[K][L-1])*clusters[J][0];
            spanners += (clusters[0][J]==clusters[L-1][K])*clusters[0][J];
        }

    }

If spanners ends up anything but 0, it's Game Over.

But how do we work out what cluster a number should belong to? That's all done by generateNoise. There's 4 cases to consider when each pair of changes is made.
  1. If neither of the pair of squares is part of a cluster (because neither had a non-zero number before the changes), they become part of a brand new cluster.
  2. If only one is part of a cluster, all resulting numbers become part of that cluster.
  3. If they are both part of the same cluster, all resulting numbers become part of that cluster.
  4. If they are part of different clusters, these clusters are combined. All resulting numbers become part of that cluster.
Also, always remember that squares stop being part of a cluster if their value ever goes back to zero.

Easter Egg

There's an undocumented feature in the game. Since you can (obviously) see it in the source, I'd better tell you about it. Note that it did not make it over to the Unity versions.

What if you want to go back a few moves to remind yourself what was going on? To do this, long press on the grid. If the time between touch down and touch up is long enough, you'll go into 'back-in-time' mode.

At first it'll just move you back one move. The variables secs counts the number of moves that have been made, and secsShown keeps track of the move you are looking at. So secsShown = secs - 1 when we enter this mode. To look at earlier moves, tap on the left side of the grid. To move forward again, tap on the right side. If you get back up to secsShown = secs, you move back into normal mode and can start moving the numbers around again. As a shortcut, swiping anywhere in back-in-time mode will bring you straight back into normal mode.

Have fun!

Now you have the code, distributed under the MIT license. You can make improved versions, release them yourselves and get far more downloads than us. We won't even be mad, but make sure you point your users back to this blog so that they can learn about the science and share their results, should they wish.