Monday, March 24, 2014

Touch Based Android Tetris Implementation

Introduction

In my earlier entry, I talked about how I published my first app on Google play. Even though it was an extremely simple and experimental application, I learned quite a lot from it. Especially about the process of getting an app published on Google play. This time, I felt it was time to do something more interesting "in a game related" context and since Tetris is usually the most given answer on "what game should I start with?", well, you guessed it, I chose to implement a Tetris clone.
This app wasn't released on the appstore, but instead its source has been released... There are probably a lot of things that could have been done better, but I decided to go with what works, instead of over-complicating things. After the first functional code was developed, the reusable parts were somewhat refactored so they could be reused in my future developments. The end result can be seen in the sourcecode. The following sections will mostly be a summary of the concepts I learned during the development of this Tetris game. These concepts range from design patterns to Tetris itself.
Since my phone (and testing device) has a screen resolution of 320 x 480 pixels, the game has been coded with this resolution in mind.
Lets start with some general concepts of an Android application.

Android application: main thread vs rendering thread

An Android application can exist out of one of the following components: activity, service, broadcast receiver and content provider. The Tetris game consists out of a single activity since this component is the basic choice if you want to provide a window / user interface in your app. As soon as the application is started, a new process is launched and only a single thread, the main thread or UI thread is used for its execution. Special care must be taken not to block this thread: blocking it for several seconds (about 5), comes with the risk of your app returning an ANR, "Application Not Responding", message to the user.
In order to define the look of the activity, you need to create a view. For this app, a GLSurfaceView was chosen since this view allows the developer to use OpenGL to define custom graphics.
When using a GLSurfaceView, it is interesting to notice how the GLSurfaceView.Renderer will be executed in its own thread, lets call this the render thread. This thread is particularly useful for the implementation of the game loop.

Game loop

For this application, the game loop will be an infinite loop where the game is continually updated and rendered at the fastest speed allowed by the processor, figure 1 illustrates the concept.
Simplest game loop
Figure 1: Simplest game loop
The gameobjects will be updated and rendered in the update() and render() functions respectively. This functionality is implemented in the onDrawFrame() function of a GLSurfaceView.Renderer and is executed by the rendering thread.

Since the speed of execution of this gameloop is a function of the processor speed, the game will not run equally fast on different devices. Therefore, a "gametick" has been defined, allowing to call update() only after a specific amount of time has passed and thus inducing a rather "discrete" (e.g.: a Tetromino will drop one line after a certain amount of time has passed) behavior of the gameobjects:

    @Override
    public void onDrawFrame(GL10 gl) {
        //Log.d(TAG, "onDrawFrame() called");
               
        float deltaTS = (System.nanoTime() - mTime) / 1000000000.0f;
        mTime = System.nanoTime();
        mTimeAccS += deltaTS;
        if(mTimeAccS > 0.1f) { //0.1f determines the gameticke time
            update(mContext, mTimeAccS);
            mTimeAccS = 0.0f;
        }
               
        render();

    }

We see that each time onDrawFrame() is entered, the mTime variable is incremented with the time, deltaTS, that has passed. As soon as mTime is bigger then the gametick, the logic of updating the gameobjects is executed.

Interactivity - Input Manager - Consumer/Producer

A game requires at least some form of interactivity. In the case of Tetris, the absolute minimum is the rotation and the movement of the Tetrominoes by the player. In our implementation, the tetromino is rotated if the player slides his finger upward or downward on the screen, the tetromino is moved to the right or left according to the movement of the finger.

These "screen touch events" are centralized by our Input Manager which implements the OnTouchListener interface, that requires the implementation of a callback function, onTouch(). The callback will be called by the main thread when an event is detected, which allows us to store the events in a buffer. Please note however that this buffer will be consumed from the render thread, since this is where our game logic resides. In order to avoid conflicts in reading and writing to the buffer, a double buffering scheme with a synchronization mechanism has been put in place:
  • Only the buffer that is referenced by "ActiveBuffer" will be written with events in the main thread (producer).
  • getMotionEventBuffer() will be called from the render thread and will change the "ActiveBuffer" to reference the other buffer and will return a reference to the buffer that was previously active. The render thread will "consume" these events.
  • The synchronization between the 2 threads is performed by an intrinsic lock.
You can find the code for the input manager below:
public class InputManager implements OnTouchListener {
    private static final String TAG = "INPUTMANAGER";
  
    private List<MotionEvent> mMotionEventBuffer1;
    private List<MotionEvent> mMotionEventBuffer2;
    private List<MotionEvent> mMotionEventBufferActive;
          
    public InputManager() {
        mMotionEventBuffer1 = new ArrayList<MotionEvent>();
        mMotionEventBuffer2 = new ArrayList<MotionEvent>();
        mMotionEventBufferActive = mMotionEventBuffer1;
    }
  
    @Override
    public boolean onTouch(View v, MotionEvent e){
        synchronized(this) {
            if(e.getAction() == MotionEvent.ACTION_DOWN) {
                Log.d(TAG, "ACTION_DOWN");
            } else if(e.getAction() == MotionEvent.ACTION_MOVE){
                Log.d(TAG, "ACTION_MOVE");
            } else if(e.getAction() == MotionEvent.ACTION_UP){
                Log.d(TAG, "ACTION_UP");
            }
            mMotionEventBufferActive.add(MotionEvent.obtain(e));
        }
        return true;
    }
  
    public void clear(){
        synchronized(this){
            mMotionEventBuffer1.clear();
            mMotionEventBuffer2.clear();
        }
    }
  
    public List<MotionEvent> getMotionEventBuffer() {
        synchronized(this) {
            if(mMotionEventBufferActive == mMotionEventBuffer1){
                mMotionEventBufferActive = mMotionEventBuffer2;
              
                return mMotionEventBuffer1;
            } else {
                mMotionEventBufferActive = mMotionEventBuffer1;
              
                return mMotionEventBuffer2;
            }
        }
    }
}

GameScenes

The game has been subdivided in 2 gamescenes. A gamescene is nothing more then a set of gameobjects, where every gameobject can be updated and rendered. There is only 1 gamescene active at each moment. Hereafter an overview the different gamescenes:
  • The gamescene, used for the actual game, exists out of the following gameobjects (this can be seen in figure 3 on the left):
    • A background texture: this texture does not change and is always used as the background.
    • A "tetris-grid": The screen area was subdivided in a ficitional grid of 20 by 30 squares (so each square is 16 by 16 pixels big). The playing field were the Tetrominoes fall down is what I call, the tetris-grid, it is 10 cells wide and 22 cells high. In the code this is represented by an array of shorts. An empty array represents an empty playing field; all cells are empty.
    • A moving Tetromino: a Tetris block that is being manipulated on the Tetris-grid. Each gametick, the Tetromino drops a single cell. As soon as it hits the bottom or a block underneath it, the block reaches its end of life and the corresponding cells of the tetrisgrid are indicated as being occupied.
    • The next Tetromino: well, the name pretty much says it all.
  • The game-over screen is reached as soon as the "next Tetromino" can no longer become a "moving tetromino" (it immediately collides with an occupied cell of the Tetris-grid as soon as it comes onto the grid). This gamescene exists out of:
    • A background texture
    • A "Game Over" texture
    • A "Restart?" texture. This texture will actually behave as a button, since a touch event on the "Restart?" texture will be interpreted by the gamescene as a "click".

Figure 3: on the left, a picture can be seen of how the game looks like when it running. On the right, a picture can be seen of the ending screen



Tetromino implementation

It was interesting to realize that a Tetromino can be abstracted as a 4x4 grid where some fields are occupied. 

Figure 2: Tetrominoes and their orientations
We can see that instead of writing transformation matrices for the rotation of the Tetrominoes, 4 states are sufficient to describe the rotation of each block. As a disadvantage, we loose the genericity of the solution and the rotation state of each block needs to be hardcoded.

Block rotation and movement requires collision detection

In order to evaluate new positions and rotations of a Tetromino (e.g. due to a timer tick or input), a rather simple collision detection scheme was implemented. Its pseudocode can be seen below:
1. Store the current Tetromino state
2. New Tetromino state equals Tetromino state after rotation / movement
3. If Tetromino moves out of the playing field or the Tetromino collides with another Tetromino
    3a. Restore the Tetromino state from 1
4. Else
    4a. Keep the new Tetromino state
 Basically, it comes down to: "check if the updated state will cause collision".

Game state and state transitions between gamescenes

Since there can be only 1 gamescene active at a given moment in time, the game is keeping track of a state to identify which gamescene is currently active.

Rendering

Basically 2 concepts were sufficient to render this Tetris game:
  • Render a colored square
  • Render a textured rectangle with blending
Rendering a colored square was used to render an entire Tetromino, since each block can be subdivided in several squares. If you have a look at the figure with the block rotation states, then it can be seen that the decision if a square of the grid needs to be rendered, will simply depend on a boolean value: the given field is filled or it isn't.
Rendering a textured rectangle with blending was used to create the visualization of the button and the "Game Over" text. Nothing fancy as textures though, just some simple programmer art to understand the concept of creating a texture with transparency.

Some random thoughts - Further exploration

  • A textured rectangle can also be seen as a sprite. However the sprites used here are static. Dynamic sprites might be an interesting feature!
  • Would it be possible to put another Android view on top of the GLSurfaceView?
  • Only 1 screen resolution is supported - how to support multiple screen resolutions?
  • It might be interesting to have some means to render text from a texture atlas?

Conclusion

I finally managed to write my first game with a custom game engine for Android. A lot of interesting subjects were explored and a lot was learned from this implementation. In the line of this post on Hobby GameDev, I certainly got some ideas for future exploration! Now onto a more innovative implementation!

References

Since there is no point in reinventing the wheel (even though I created my custom game engine, but hey, as a hobby, I can indulge myself), several references where used during this work: