Developing Tetris for Android in the Unity Game Engine – Part 1 (Falling Blocks)

Hello all – due to having a fairly busy schedule as of late (owing to the run-up to my exams in May and June), I have been unable to make regular blog posts recently. However, enough progress has been made on my previously-mentioned computing-related side project for me to decide that it should not be kept under wraps for any longer. As the title suggests, the following series of posts will be about developing the video game ‘Tetris’ for the Android platform using the Unity game engine (an explanation of the game’s rules can be found here). This first post will be about developing the ‘backbone’ of the game (that is, the system which enables blocks to be generated at the top of the screen and fall).

This series of posts will assume a rudimentary knowledge of the Unity game engine (very basic ideas such as ‘GameObjects’ and ‘Components’ will not be explained in great detail).

The final product of this post can be downloaded here.

Our first task is to create a new Unity project directory – we do not need to import any of the pre-made asset packages (as none of them are necessary for our project). Normally, Tetris has 2D graphics, so we can opt to create a 2D project as opposed to a 3D one.

Screen Shot 2017-03-13 at 8.08.21 AM

After this is done, the main scene can be built (this should be done after setting the aspect ratio of the ‘game’ window to a ratio appropriate for the Android platform, such as 9:16). On my project, I positioned the main camera at (6,6,-10) and set its orthographic size to 11.6 – these settings allow for a grid with 18 rows, each 13 blocks wide.

Screen Shot 2017-03-13 at 8.09.18 AM

Next, we create a ‘prefab’ of an individual block. This can be done by dragging an object from the ‘hierarchy’ interface into the ‘assets’ interface. In the Unity game engine, prefabs are game objects saved as files within the game directory – these files can then be referenced in scripts, and copies of them can be created in the game world from these references. All of the scaling work has been done in the camera settings earlier, so the block prefab can just be a single cube with the dimensions (1,1,1). Later on, we will be able to design ‘tetrominoes’ (the slightly more complex shapes seen in the original game) using these block prefabs – for now, we will just use single blocks.

Screen Shot 2017-03-13 at 8.10.55 AMScreen Shot 2017-03-13 at 8.11.22 AM

Now, we can design the main script which handles the falling block system (I named it ‘MainControl.cs’). This script must be able to both keep track of all of the blocks in the grid and directly reference the blocks which are currently falling. We can achieve this by using a multidimensional array of ‘GameObject’ variables – the camera settings created earlier allow for us to use the x position of a block  as its column in the grid, and the y position of any block as its row in the grid (since the blocks are positioned at integer points along both axes). The script must also have a reference to the block prefab created earlier (so that new blocks can be generated). Furthermore, the script should also contain a variable holding the player’s score.

Screen Shot 2017-03-13 at 8.12.12 AM

In the original game, the blocks fall at a constant rate (unless they are sped up by the player – we will implement this feature in a later post). Moreover, they are translated directly from row to row, as opposed to being moved downwards in a continuous, smooth motion. Therefore, in order to process falling blocks, a function which is repeatedly called once every second can be used. In my code, I named this function ‘Tick’ – first, it checks if there are any blocks at all falling. If there are no blocks falling, it creates a new block using the ‘Instantiate’ function and adds it to the list of falling blocks. The ‘Instantiate’ function takes the block prefab as its first argument, and then the intended position and the rotation of the newly created block as its second and third arguments, respectively. Using the function ‘Random.Range’ while setting the value of the second argument of the ‘Instantiate’ functions enables blocks to be generated anywhere along the top row.

Screen Shot 2017-03-13 at 8.14.42 AM

If there are blocks falling, each of these blocks are processed in a loop. The loop initially iterates through each block and checks if the block has fallen onto a surface – this surface could either be the bottom of the grid, or the top of another block. Therefore, this check can be performed by first checking that the row (that is, the y position) of the block is not 0, and then checking that the value of the grid element exactly one row below the grid element of the current block is null (that is, no game objects are in that position in the grid). If this check returns true for any block in the list, then the list is cleared and all of the blocks in the list are frozen into their positions – since one of the blocks in the current ‘tetromino’ has fallen onto something. However, if this check never returns true, the ‘Translate’ function is used to move all of the blocks downwards by one row each (and the appropriate values in the grid array are updated).

Screen Shot 2017-03-13 at 8.17.42 AM.PNG

In order to ensure that the ‘Tick’ function is called once every second, the ‘InvokeRepeating’ function is used in ‘Start’ (which is called immediately after gameplay begins). Additionally, the grid is also initialised here.

Screen Shot 2017-03-13 at 8.32.21 AM.PNG

Now, we can drag this script onto any object in the scene – in my project, I attached it to the main camera. Our final result is a system which generates single blocks at the top of the grid in random positions along the x axis – these blocks then fall downwards until they either fall on top of other blocks or reach the bottom of the grid. When this happens, new blocks are created. In the next post, we will give the user the ability to control the movement of the blocks through input.

Enumerating Boolean Sets Using Bit Arrays

Certain problems in computer science call for the complete search of all of the possible permutations of a set of Boolean values. For example, consider a set of x counters, from which we can ‘take’ any combination of counters, and leave the rest – that is, any given counter in the set containing x of them can be either ‘taken’ or left behind. Each of these counters could have a certain numeric ‘value’, and our program is tasked with finding all of the combinations of taken counters whose values sum up to a certain target number (which we will call s).

blogpiccounters

Obviously, there are same fairly elegant methods which can be used to do this efficiently, however, for the purpose of this post, we will focus on the ‘naive’ method.

We have already observed that each counter can either be taken or left – expanding on this idea, we can say that each counter has one of two states. Remember that a bit also only has one of two possible values (either 0 or 1). Additionally, binary numbers (numbers in base 2) also only contain digits with values of either 0 or 1 – notice that as we count up from 0 to 3 (note that this is 2^2 – 1) in binary, we enumerate all possible combinations of the bit values in a set of 2 bits.

Binary (Base 2)  |  Denary (Base 10)

00                               0

01                                1

10                                2

11                                 3

This is a pattern that is repeated for all positive powers of 2 – counting up to 2^2 – 1 in binary will give all of the possible combinations of bit values in a set of 2 bits, and counting up to 2^3-1 in binary will give all of the possible combinations of bit values in a set of 3 bits, and so forth. To generalise the idea:

Counting up to 2^n-1 in base 2 (binary) gives all of the possible combinations of bit values in a set of n bits.

Given that a bit can only have a value of either 0 or 1, we can use the value of a given bit to represent a yes/no decision. Therefore, in our original problem dealing with counters, we could describe a set of chosen counters by using an array of bits where a single bit with a value of 0 denotes a counter which has not been chosen, while a bit with a value of 1 denotes a counter a counter which has been chosen. This array of bits would have a length of x, as each individual bit represents an individual counter.  Furthermore, we can then obtain all of the possible combinations of chosen bits by counting up to 2^x-1 in base 2, and parse through every resulting binary number in turn to find the sum of the chosen counter scores in each combination, and print the selections which have a sum of s.

Obviously, given that this technique is a complete search of a full range, we can come to the conclusion that it is highly inefficient. The time complexity of the algorithm creating the bit arrays is 2^n; so having a value of n much higher than 20 to 30 can result in incredibly long running times.

The code below uses this algorithm by counting up to 2^x-1 in base 10 and converting each number to binary – in order to ensure that each resulting bit array has a length of x, the program ‘pads’ every base 2 number with leading zeroes (in the interest of maintaining the scope of this post, the problem of converting a denary number to base 2 will not be looked at in detail here). Each binary number is represented by a string, which the program parses through in order for a ‘counter selection score’ to be calculated. The binary numbers which have a  ‘counter selection score’ of s are printed to the standard output.

 

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//This function converts the denary number num
//to binary, padding the resulting bit array
//with leading zeroes such that it is returned
//from the function with a length of x.
string CreateBitArray (int num, int x) {
    int dividedNum = num;
    string bitArray = "";
    while (dividedNum > 0) {
        int rem = dividedNum % 2;
        char remChar = '0' + rem;
        bitArray += remChar;
        dividedNum /= 2;
    }
    while (bitArray.length() < x) {
        bitArray += "0";
    }
    reverse (bitArray.begin(), bitArray.end());
    return bitArray;
}

//Return a 'counter selection score' given a bit array
//denoting which counters to take and which counters to leave.
int GetCounterSelectionScore (string bitArray, vector &lt;int&gt; counters) {
    int score = 0;
    for (int i = 0; i < counters.size (); i++) {
        if (bitArray[i] == '1') {
            score += counters[i];
        }
    }
    return score;
}

int main () {
    int x; //We are dealing with a set of x counters.
    cin >> x; //Take x from the standard input.

    //Take the value of each counter in turn from the standard input.
    vector <int> counters;
    for (int i = 0; i < x; i++) {
        int c;
        cin >> c;
        counters.push_back (c);
    }

    int s; //s denotes the target 'counter selection score'.
    cin >> s;

    //Now, begin counting up to 2^x-1 in denary,
    //converting each number to binary
    //and padding the resulting bit array in order
    //to get all of the possible selection combinations.
    for (int i = 0; i <= (pow(2, x) - 1); i++ ) {
        string bitArray = CreateBitArray (i, x);
        int score = GetCounterSelectionScore (bitArray, counters);
        //Print out this bit array if it has the required score.
        if (score == s) {
            cout << bitArray << "\n";
        }
    }
    return 0;
}

Another potential method of enumerating boolean a set of boolean decisions using a bit array involves recursion – this technique allows the program to bypass any conversions between number bases. Instead, a single function repeatedly calls itself twice such that all of the possible bit combinations are generated in a ‘tree’ format.

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//Store all of our possible bit arrays in a single vector,
//which we will built using recursion.
vector <string> bitArrays;
void ConstructBitArrays (string curArray, int targetArraySize) {
    if (curArray.length () == targetArraySize) {
        bitArrays.push_back (curArray);
    } else {
    string newCurArray0 = curArray + "0";
    string newCurArray1 = curArray + "1";
    ConstructBitArrays (newCurArray0, targetArraySize);
    ConstructBitArrays (newCurArray1, targetArraySize);
    }
}

//Return a 'counter selection score' given a bit array
//denoting which counters to take and which counters to leave.
int GetCounterSelectionScore (string bitArray, vector <int> counters) {
    int score = 0;
    for (int i = 0; i < counters.size (); i++) {
        if (bitArray[i] == '1') {
            score += counters[i];
        }
    }
    return score;
}

int main () {
    int x; //We are dealing with a set of x counters.
    cin >> x; //Take x from the standard input.

    //Take the value of each counter in turn from the standard input.
    vector <int> counters;
    for (int i = 0; i < x; i++) {
        int c;
        cin >> c;
        counters.push_back (c);
    }

    int s; //s denotes the target 'counter selection score'.
    cin >> s;

    //Create all of the possible bit combinations using the
    //recurring function, and then iterate through all of
    //the generated combinations and give those that
    //have a score equal to s.
    ConstructBitArrays ("", x);
    for (int i = 0; i < bitArrays.size (); i++) {
        if (GetCounterSelectionScore (bitArrays[i], counters) == s)
            cout << bitArrays[i] << "\n";
    }
    return 0;
}