[Android Mini-Game] Form the word

This is my first mini-game for android. The objective is to form the word by touching the letters within time. Touch an invalid letter, or let the timer expire and the level fails.

As the player progress on the levels the word count will increase and the letters will disappear faster. Letter count starts from 4(very easy) to 14(hard)

Play store link: https://play.google.com/store/apps/details?id=fousteris.formtheword

Advertisements

2 tips for avoiding garbage collector in (android) gameloops

Currently implementing by first game in android i was excited to see the challenges a game (unlike any other software) introduces. One of them is the fact that because you have a loop running continiously you do not want to continiously request new memory. The reason is that smartphones have tight memory constraints and allocating objects means the garbage collector will be interrupting your game in order to reclaim unreferenced objects. However the operation of the garbage collector is not free. In case of a garbage collector interrupt your game will experience lags. In this article i present two ways i used in my game to avoid the garbage collector overhead.

1) Use an object pool
Every game needs to represent objects. So in the game loop you discard and create new objects all the time. For exaple if you have an enemy which dies or gets out of the game viewport, bviously this object doesn’t needed any more, but another enemy will appear very soon. If we create and discard objects in that fashion the overhead will be very high and the garbage collector will interrupt very often to reclaim the unusded objects.

So instead of allocating and discarding objects we maintain a list of instanciated objects ready to be used. If we need an object we remove it from the list we use it and when we are done with it we put it back to the list. That way we are not creating or destroying new objects.

ArrayList<Enemy> enemyPool = new ArrayList<Enemy>(); //This is our pool
ArrayList<Enemy> enemies = new ArrayList<Enemy(); //This is the list of enemies currently displayed

//Preallocate some enemies...
for(int i = 1; i <= 20; i++) {
   enemyPool.add(new Enemy());
}

//Game loop
while(true) {
     Enemy newEnemy = enemyPool.getEnemy();
     if (newEnemy != null) {
         enemies.add(newEnemy);
     }
     updateEnemies(); //Update the enemies list based on game logic.
     draw(); //Draw the frame
}

We are preallocating a pool of 20 enemies. The number depends on the game and the number of objects you will need.

2) Use char arrays / StirngBuilder instead of Strings
One of the traps in games are Strings. If you want to manipulate Strings in the game loop the String class is not a good idea. Strings are immutable and thus you need to create a new object when you want to change a character inside or concatenate it with another. You should use preallocated character arrays when aplicable instead of strings.

One example is the countdown timer in games. In my game i have one and i first implemented it with the naive approach. However the number of object allocations was pretty high, so i switched to a char array implementation and manually added the digits at the end.

This is the naive implementation

String timeDisplay = "TIME LEFT: " + String.valueOf(timer);

Howevever we are creating two new Strings per iteration. Not that good. Instead we should preallocate(out of the main loop of course) an array timeDisplay and manually change the digits at the end.

char[] timeDisplay = "TIME LEFT: ##".toCharArray();
char[] digits = { '0','1','2','3','4','5','6','7','8','9'};

Inside the game loop we extract the digits from the timer and set them at the array.

timeDisplay [timeDisplay.length - 2] = digits[(int)Math.floor(timer % 100 / 10)];
timeDisplay [timeDisplay.length - 1] = digits[(int)Math.floor(timer % 10)];

This code is less flexible than the naive method because you need to set the array length based on the timer number of digits. In my case the timer will always be a two digit number so it is ok. But it is fairly easy to make it support more digits. The big Plus here is that no more objects are allocated.

General rules
The object pool pattern is definitely your best friend when you are creating a game. You should preallocate every object you will need in game. Also always prefer StringBuilder/char arrays instead of strings. Immutability here is an enemy so we prefer using StringBuilder/char array. If you need to concatenate many strings then you should definitely need to use StringBuilder. If you have constant Strings which need to be mutated the char array is the best choice.

When data encapsulation is a bad idea

One of the basic concepts of Object-oriented programming is the data encapsulation principle. This princible says that you have an object which has it’s internal state private and provides public methods which forms the interface of the object and which is responsible for mutating the internal state. The internal state cannot be mutated directly from the client. This has the advantage of separation of the interface of the class with the internal implementation, so one can change the implementation without touching the interface used by client code.

However there is a case where we have plain data transfer objects with no logic. Those objects simple carry data and have no methods to perform logic on their state. For example consider that we have a point object which contains x,y coordinates:

class Point {
    private float x;
    private float y;

    public Point(float x, float y) {
        this.x = x;
        this.y = y;
    }

    public void setX(float x) {
        this.x = x;
    }

    public float getX() {
        return x;
    }

    public void setY(float y) {
        this.y = y;
    }

    public float getY() {
        return y;
    }
}

This is just a waste. The encapsulation pattern is simply redundant here, and the reason is that the class is used only for carrying data and have no logic to hide. So by this way we introduce unnecessary boilerplate code, and also introduce overhead of virtual method calling(which on some systems like Android) may make a difference.

In those situations is better to leave the fields public and remove all the accessor and mutator methods. That way we can directly access the fields without the burden of accessor/mutator methods and without breaking the data hiding principle(since this must be applied only on objects containing logic)

class Point {
    public float x;
    public float y;

    public Point(float x, float y) {
        this.x = x;
        this.y = y;
    }
} 

Point myPoint = new Point(10.5,15.2);

//Directly accessing data members
float x = myPoint.x;
myPoint.x = 5.5;

When NOT to apply this
This should be applied only in the case where your objects will be used to transfer data(for example serialized and transfered through a network) and containing NO logic. If we are unsure about planning to add logic later, then we should implement data hiding. The reason for that is that if we decide later to add logic to the class we will hide the members, and that will result breaking client code which uses this

Javascript – Functional programming – Closures & higher order functions

Javascript has gained many popularity on the last years. It is a language poorly misunderstood and often underestimated because it has some ‘weird’ features such as the Classless object oriented model. However it has some very nice feautres. One of them is that everything is object. This allows managing treating functions like traating ever other object such as an array, string, number etc. This eventually allows to define functions that accepts functions as arguments, and creating and returning functions, allowing javascript(which is an imperative) language to have functional programming features.

What is Functional programming
Functional programming is programming paradigm is which the central concept is the function as we know it from math. It just accepts input and returns and output. It does not have an side effects as in imperative languages. It does not manipulate state and thus makes programs easier to understand and debug.

Functional programming in an imperative language. But how?
As mentioned before javascript is an imperative language that has some nice features in order to do some partial functional programming. It is NOT a purely functional programming language such as Haskell. However we can facilitate some aspects of functional programming in our code in order to introduce more abstraction, and make it more easily understood and testable.

Higher order functions – Functions as objects
In Javascript everything is an object so we can declare a variable and assign to it a string, an array, or a function. For example we can have a variable called add in which a function performing add is assigned.

var add = function(x,y) {
    return x+y;
}

//We can call add normally
var result = add(10,5);
console.log(result);

Add is just a normal variable containing a reference to a function. As such we can pass it to another function or return it and call it later. As an example consider we want to create a function which will accept a list of numbers and an operation to be performed in these numbers. In imperative style we would do something like this:

function performComputation(list, computation) {
      var result = 0;
      if (computation == 'add') { //Add all alements
          for(var i = 0; i &amp;lt; list.length; i++) {
                result += list[i];
          }
      } else if(computation == 'substract') { //Substract all elements
           if (list.length &amp;gt; 0) {
               result = list[0];
               for(var i = 0; i &amp;lt; list.length; i++) {
                  result -= list[i];
               }
          }
      }

      //...more if else based on available computations 
      return result;
}

var result = performComputation([10,5,2], 'add');

By this way our function is not abstract enough, and lacks flexibility. If we wanted say another computation we would need to edit the function body and add another else-if block for the new computation. It introduces boilerplate code too! There must be another way… And what it is? Yes ou got it! The Functional one! Instead of passing a string which will represent the operation we will pass a function which will accept two numbers and return a result. The performOperation will calculate the result based on the function passed.

function performOperation(list, computation) {
     var result = 0;
     for(var i = 0; i &amp;lt; list.length; i++) {
          result = computation(result, list[i]);
     }

     return result;
}

var summed = performOperation([1,2,3], function(x,y) {
     return x+y; 
}); //summed will be 6

var substracted = performOperation([1,2,3], function(x,y) { 
     return x-y; 
}); //substracted will be -6

console.log('summed: ' + summed + ', substracted: ' + substracted);

As you can see we reduced the size and complexity of our code. Instead doing the calculation on the main fucntion we separated the list looping functionality and the calculation, leading into two very simple functions. This leads to more easier to understand and flexible code. Note that we are passing a function as argument. Thus the performComputation function has become a higher-order function. Actually the previous performOperation function is a popular method often performed in lists. It is called reduce. Reduce takes a list of data and aggregates them into a single result based on some computation between elements.

Another example – Map implementation
Another example is the map function. Is a function which accepts a list and transforms every element of the list based on transform function. For example let’s say we want to create a function which will accept a list and return a list with the elements of the original list doubled.

function map(list, operation) {
     var result = [];//Result will be a list
     for(var i = 0; i &amp;lt; list.length; i++) {
         result.push(operation(list[i]));
     }

     return result;
}

//Result will be [2,4,6,8];
var result = map([1,2,3,4], function(x) {
    return x * 2;
});

console.log(result);

Very easy! Each element is passed to the operation function which just doubles it. If now we want to add another operation no need to touch the original map function.

var result = map([1,2,3,4], function(x) {
    return x*x;
});

Now the result will hold every value of the list multiplied b itself. Looking at the implementation of the previous function we saw a common point. The for loop. Can we abstract this even more? The answer is yes. We can create a forAll function which will accept a list and an operation to be performed.

//Now we abstracted the loop code in a separating function so we can reuse it 
//in other functions and without caring of the details of the looping process.
function forAll(list, operation) { 
     for(var i = 0; i &amp;lt; list.length; i++) { 
         operation(list[i]); 
     } 
} 

function map(list, operation) { 
     var result = [];//Result will be a list 
     forAll(list, function(x) {
         result.push(operation(x)); 
     }); 
     return result; 
} 

var result = map([1,2,3,4],  function(x) { 
    return x*x; 
}); 

console.log(result);

Closures
Another concept of functional programming is closures. Closures are nested function(that is functions declared inside a function) which share their lexical scope with the function they are included. What does this practically means? This means that you declare a nested function. Inside the outer function you have declared some variables. You can access those variables from the nested function(closure) even when the original function has returned! Not undertood? Don’t worry an example is coming!

function makeAdd(x) {
     function closure(y) {
         return x+y;
     }

     return closure;
}

We declared a function makeAdd which accepts an argument x. Inside we declare another function which will be our closure and will accept an argument named z. Inside our closure we perform an addition of x and y. But wait. x is not declared anywhere in function closure. Yes, because it references the x variable in makeAdd. Thus the inner function becomes a closure. This means that closure can be returned and used on it’s own using the variable x from the makeAdd.

What this practically means?
With closures we can do many things. The example above shows a very simple use case. If we invoke makeAdd we get a function as a result:

var adder = makeAdd(10); //adder is now a function which sums it's argument with 10
var result = adder(20); //Result will be 30

console.log('Result: ' + result);

From now on every time we invoke makeAdd it will add the argument passed to it with 10. We can create another one which will add with 20 or every other number.

In the general case closures allows us to create functions whose behavior can be customized based on the arguments passed on the creating functions.

A more real world example
Now for a more real world example of a closure. Let’s say you have a list of people and we want to filter them by an attribute.

The following example finds all the people whose age is above a specified value.

function findPersons(persons, age) {
     return persons.filter(function(person) { //Closure
          return person.age &amp;gt;= age;
     });    
}

var persons = [ { name: 'Mike', age: 17 }, 
                { name: 'Jim', age: 23 }, 
                { name: 'Kate', age: 30 } ];

var adults = findPersons(persons, 18);

//Will print Jim,Kate
for(var i = 0; i &amp;lt; adults.length; i++) {
	console.log(adults[i].name);
}

In the example above we define a function findPersons which accepts a list of perSons and an age value. Inside we call the filter function passing to it a closure which returns true if a specified perSon’s age if equal-or-greater than the age specified when we called findPersons. Notice that the inner function references the age variable of the findPersons. Thus it is a closure.

Conclusion
In this tutorial we have only scratched the surface of javascript’s ability to treat functions as first-class objects. Surely it is not have the features of a pure functional programming language but we can surely make code cleaner and more easy to debug.

ThreadJS: Simple convinience wrapper for web workers

Web workers are a new HTML5 API enabling web developers to separate time consuming tasks in a separate thread so the UI thread is not blocked. Eventually every web worker results spawning a new real os-level thread.

However the API requires you to create a separate javascript file which contains the code you want to execute. This may be a burden sometimes as you need to refer to an external file to see what a specific worker is doing.

So i created a simple wrapper on top of web workers which allows you create a thread using a custom function, and (optional) arguments.

The usage is simple as that:

var thread = new Thread(function (customArgs) {
    //Code here will be executed in a web worker.
    //You can use postMessage to send data back to main thread, just like plain web workers.
});

//Optionally handle onmessage &amp; onerror to receive data and error from thread.

thread.onmessage = function(e) {
    console.log('Received message: ' + e.data);
}

thread.onerror = function(e) {
    console.log('Error: ' + e.message);
}

var custom_args = { test: [1,2,3] };

//Start thread passing optional custom parameters
thread.start(custom_args);

//You can stop the thread at any time using the stop method
thread.stop()

You can find the library & an example in github

Websocket UDP proxy with Node.js

A few days ago we faced the following problem. We needed to be able to send messages via javascript in browser to UDP based server. But browsers just do not allow you to send UDP packets, and we didn’t want to reimplement the server so it accepts web connections.

So we decided to put a proxy which will accept websocket connections(we couldn’t use an ajax based mechanism since the client code won’t be on the same domain on the server) and forward that data using udp on the server. When the proxy receives a UDP packet from the server it will forward it to the appropriate websocket client. We choose Node.js because we needed a simple and lightweight solution.

We used the ws wbsocket library for node.js. The code for the proxy is simple as that:

var Buffer = require('buffer').Buffer;
var dgram = require('dgram');
var WebSocketServer = require('ws').Server;

var wss = new WebSocketServer({port: 8080});

//The ip &amp; port of the udp server
var SERVER_IP = '10.0.2.4'
var SERVER_PORT = 11000

wss.on('connection', function(ws) {
    //Create a udp socket for this websocket connection
    var udpClient = dgram.createSocket('udp4');

    //When a message is received from udp server send it to the ws client
    udpClient.on('message', function(msg, rinfo) {
        ws.send(msg.toString());
    });

    //When a message is received from ws client send it to udp server.
    ws.on('message', function(message) {
        var msgBuff = new Buffer(message);
        udpClient.send(msgBuff, 0, msgBuff.length, SERVER_PORT, SERVER_IP);
    });
});

Save the file as proxy.js and launch the server by opening a cmd(or terminal) and type in:

node proxy.js

The server should be listening on port 8080, and ready to accept websocket connections. No we can connect to it using websockets at the client side in browser.

var ws = new WebSocket('http://10.0.2.4:8080/');

ws.onmessage = function(evt) {
      console.log('received from server: ' + evt.data);
}

ws.send('some data to be sent to the udp server..');

That’s it. Simple enough!