Pooling with init : let’s throw ImpactJs classes in the pool.

Hello,

I explained a few times ago a quite simple way of recycling the objects created with true Javscript classes. (here).
Still there are other classes scheme, and impact -and probably other framework as well-, uses a variant of John Resig’s inheritance scheme (here).
Thoses classes rely on an init() member, that will be in charge of … -you guessed- initializing the object.
I’ll explain here this scheme, and then apply the Pooling strategy to those objects.

( You can find the pooling code here :
https://github.com/gamealchemist/Javascript-Pooling  )

How does those classes using the init() pattern work ?

Impact classes are all inherited from a base class, ‘Class’, using extend.

   ig.Entity = ig.Class.extend({
	pos : {x: 0, y:0}     ,      // property
	id  : 0  ,                   // property
        ...
        init   : function (x,y,settings) {
                             this.pos.x = x;
                             ...
        },     
        update : function() { 
                             this.pos.x += ....  
                             this.pos.y += ...
        },

	id: 0,
	settings: {},

	offset: {x: 0, y: 0}
      } );

Extend must be provided with an object,  which will be used to add properties and methods to the original Class.
All the properties and methods will be set on the protoype of the new Class (which is, in fact, a function as you know).
Then, when you create an object using  new (), it will be the constructor’s responsability to copy the properties of the prototype into the new object. This copy is required because otherwise, if we take the Entity example, all entities would share the same pos / velocity / … which would probably lead to a boring game.
It is important to notice that all objects do not get copied : look at copy() (Impact.js, line 125) and you’ll see that HTMLElement or ig.Class properties won’t be copied. So they are shared amongst all instances. That is why you cannot set the animations in the extend object : each Entity needs its own animation.
But how to create those per-instance objects  ?  You do not have any control other the constructor function (handled by the class system), and obviously the object provided to extend the Class doesn’t know anything about the ‘this’ of the objects you’ll later instanciate…
That’s when the init() comes into play : it is called at the end of the constructor, and allows you to perform an initialization on the new instance, for all properties that needs their own instance of an ig.Class ( ex : animation), or a specific new value (x,y).

How could we recycle such objects ?

Since -to state things in a simple way-, it is now init() which initialising just like the constructor function does it for true js classes. So, to pool those classes, we just have to call init instead of the constructor to have the object as clean as new when we retrieve it from the pool.

The constraints we had on the constructor function for true js classes to work with pooling now apply on the init() function :
- init should accept any number of arguments (including none).
- at the end of an init EVERY properties should be set either to its default value OR to a value provided in the arguments of init.
So if you plan on using pooling with a Class, you must do a quick review of all properties you are using in your code, an reset or set them to the provided values in the init().

     
       init (x,y,settings) {
           x = (!x) : x : 0;
           y = (!y) : x : 0;
           this.bananaCount = ( settings && settings.bananaCount ) ?  
                                            settings.bananaCount : 0;
           this.eatenBananas = 0;
           this.bananaRobbers = [];
           this.bananaTracker = new BananaTracker(this.bananaCount);
     }

Now you are sure that any call to init will set your object as shining as new.
But.
But…
Wait !

The goal of all this is to avoid garbage creation, and the init() above will create objects on each call : So any time you can, try to re-use the property objects of the previous life of your object as well :

     
       init (x,y,settings) {
           var noArgs = ( arguments.length == 0 );
           x = (!x) : x : 0;
           y = (!y) : x : 0;
  this.bananaCount = ( settings && settings.bananaCount ) ?  
                                    settings.bananaCount : 0;
           this.eatenBananas = 0;
           if (this.bananaRobbers) { 
                     this.bananaRobbers.length=0 
                     } else { 
                this.bananaRobbers = []; 
            };
           if (this.bananaTracker)  {
               // reset the bananaTracker in some way
           } else {
               this.bananaTracker = new bananaTracker(...);
           }

BananaTracker.pnew(this.bananaCount); 
     }

Rq : there are too many cases for me to explain here, but remember that when allocating an object for the pool, init will be called with no arguments. Then later, it will be called with your arguments (and *maybe* this second call is also performed with no arguments), and then again and again init will be called on each reuse. So think well about the best way to allocate the properties that uses objects. Do most work while initializing the pool if possible, and try to reset the properties in a fast and clean way.

Rq : you might use pooled object in the properties of your pooled object. It might be pooled ig.Classes or pooled true js classes. Just watch out for their disposal.

Another thing to keep in mind when using a Framework : the Framework might change some properties for you, properties that you should reset in the init.
Expl : For the Entity class, calling kill() will make this._killed to true, and make the object collides with nothing. So you have to unkill the object and restore its default collision settings…
OR … inject the framework to have it doing this for you, which i explain later.

Show us some code !!

Ok let us see the code for pooling Impact Classes :

var Initpnew     = function() {
    var pnewObj  = null     ; 
    if (this.poolSize>0 ) {
           // the pool contains objects -> grab one
           this.poolSize--  ;
           var  pnewObj = this.pool[this.poolSize];
           this.pool[this.poolSize] = null   ; // **

    } else {
          // the pool is empty -> create new object
          pnewObj = new this();    
          this.builtCount++;
    }
     if (pnewObj.init) {
    	                  pnewObj.init.apply(pnewObj, arguments); };
           return pnewObj;
};

var Initpdispose   = function() {
    var thisCttr = this.constructor             ;
    // throw the object back in the pool 
    thisCttr.pool[thisCttr.poolSize++] = this ;
};

ga.setupInitPool  =  function(func, initialPoolSize) {
    if (arguments.length<2) { 
        throw ('setupPool takes two arguments');    }
    func.pool                = []                 ;
    func.poolSize            = 0                  ;
    func.pnew                = Initpnew           ;
    func.builtCount          = initialPoolSize    ;
    func.prototype.pdispose  = Initpdispose       ; 
    // pre-fill the pool.
       for (var i=0; i<initialPoolSize; i++) {
                var newObj = (new func());
                newObj.pdispose(); 
            }                              
};

Rq : We can see that, when the pool is empty, init is called twice on the newly created object : once for the object creation (with empty arguments), and then we initialize it with provided arguments. But… well.. this shouldn’t happen ! The builtCount property is here to measure how many objects were built : at the end of a game, look at this figure and the intialPoolsize should be >= to this number.

How to use ?

1. Ensure the init performs a full initialisation of *all*
your object’s property, even when called with no arguments.
2. pool the class :

 ga.setupInitPool( MonkeyEntity, 100);

3. Instead of the new operator, use pnew :

MonkeyEntity.pnew(...)

4. don’t forget to pdispose() instances that you won’t use any more. :

 aMonkeyInstance.pdispose()

!!! Do not keep any pointer to a disposed entity. !!!

Helper for Entity classes.

Impact can handle the creation and disposal for you : if you use the standard function spawnEntity and entity.kill(), you might just as well have them handle the pooling. And while we are here, we can also have spawnEntity to restore some default values for you : _killed and the collisions settings.
I wrote a small function that injects the pooling for the Entities, so to have pooled entities, just write (in main.js for instance, where you must ‘requires’ your entities and also gaPooling.js ) :

   
   ga.autoPoolEntities();

   ga.setupInitPool(EntityMonkey, 20);

   ga.setupInitPool(EntityBadGorilla, 50);

And that’s all !
Take care of setting YOUR properties in the inits, use only the standard spawnEntity and kill functions with them (not ‘new’), and your monkeys and gorillas will swim in your pool.

Are you sure this can be usefull ?

Well, for, say, the hero entity used only once, i guess not. For monsters, it will depend on their number and spawning rate. For bullets, it should pretty much always useful.

You can see in my other article on Pooling some performance counter : they measure in fact a mix of the creation time and garbage collection time.
Since Javascript does not allow to know the memory use or when it performs a garbage collection, it is difficult to be accurate.
But i had this other idea : what about looking at the memory usage (in Chrome / Timeline), and measure the Garbage Collection rate by hand ? After all we know a G.C. occured when memory usage suddenly drops.
So i made a quick demo throwing quite a lot of bullets (100/s) and measured ‘by hand’ the number of G.C. performed.
As you can see, there are 0.26 GC/s with no Pooling, and 0.04 GC/s with pooling, so we have a X6 improvement. !!
We can see also that the pooled memory usage stays 2/3 MB or so below the non-pooled usage.

Memory usage when not pooling / pooling.

Let me know if you happen to use all this in your game (and are happy with it !).

Happy coding.

Let’s get those Javascript Arrays to work fast

Hi,

So now let us watch how to handle Javascript arrays with performances in mind. The array object is indeed very powerful, but you need to handle it with care since some quite innocent feature can be have a high time and/or garbage creation cost. I’ll show here a few simple techniques that avoids those costs.
The benefits can be very high (more than 10X) for some features, so all this is worth a look.

1. Stating the obvious : [] is better than {}

Any time you can, avoid using an {} object to store data/perform computations/…
It is quite likely that you can use an integer instead of string to identify your data. You might have to use another integer ->string array to do so, but it’s worth the performance gains.

2. [ integer ] is better then [ something else ]

In the same manner, prefer to use arrays of integers : arrays where *all* ‘slots’ of the array are filled with integers. In such a situation, most javascript engine will recognize that they are dealing with an array of integer and perform faster.

3. Do not loop backward within an array.

You might know this way to iterate through an array :

  var i=myArray.length;
  while (i--) {
     ... process myArray[i] ...
  }

Which makes you avoid an extra test.
But you know what ? this will be much slower than in the right order. Because caches expect the processing to be ‘straight’, you will have cache misses again and again, and a 2X slow down is what you’ll get when you are lucky.

So do not loop backward unless you have very good reasons to do so.

Notice that even lastIndexOf might be faster when straight, like this :

  var lastIndexOf(arr, value) {
     var i=0, len=arr.length, ind = -1;
     while (i != len) {
         if (arr[i] == value) { ind=i }
         i++;
     }
     return ind;
  }

Depending on array size, and value distribution ( == ? will we find a few or a lot of matches) ?, this one might be way faster in fact.

Surprising.

4. Do not change again and again the array’s size

One important thing to notice, that is hidden by the simplicity of push(), pop(), among others, is that any time you change the size of an array it might lead to memory allocation and/or memory fragmentation and/or memory copy.
Expl :

var A = [5,6]; 
var B = [1,2,3];   // allocation of 3 arrays. 
var C = [ 1, 2, 4, 5 ];      
                memory = AABBBCCCC
B.push(1);  // allocation for 1 item , no  contiguous
                           memory available,
// the array is de-allocated then a free lenght 4 area is allocated
// then array content is copied. 
                 memory = AA___CCCCBBBB
var G = [ 0,0,0,0,0] ; // let us create the G object : 
                 memory = AA___CCCCBBBBGGGGGG
// let's pop B
var last = B.pop() 
// one item is now not allocated : 
                 memory = AA___CCCCBBB_GGGGG
// memory is fragmented,
// it will be *later* re-organized by G.C. to match :
                 memory = AACCCCBBBGGGGG

// ... with quite a cost.

    Just on this very simple example, we are doing much more memory activity than we should. You have to imagine the case where you are using array of arrays, altogether with a lot of smaller objects, when such issue will become very important.

5. Remarks on performance measures

The performance measures -done with jsperf- are way too simple for the garbage collector :
- no-one knows when the garbage collector will happen, so it might even happen ‘later’,  when it is no longer the test that created garbage that is running. Yet, the high number of loops performed seems to be enough : i tested a few time to revert test order, and the impact on performance ratios was low.
- But worse : no memory is allocated before the test starts, so if we test with just one array, the memory management task is much much simpler than in real-life: let us see an example with push/pop :

	
jsperf Case : only an array in memory :
    var A = [0,0,0, ];
    initial memory status : AAAA (where A is an array item)
    A.push(XX) ;
    new memory state : AAAAA : the memory management just had 
                  to reclaim one more item.
    var val = A.pop();
    new memory state : AAAAA  (just reduce the size)

     // ...

No copy will never happen with a single array test, and all operations are simpler.
I noticed that when testing pooling objects within an array with only one type of object : even IE was faster at handling memory than Chrome (!), and pooling was useless on any browser. Then i just used 3 arrays of 3 differently sized object, which is a not so complex situation. The performances of IE went down in the deep sea, and all browsers had a hard time to get their memory straight : by avoiding memory allocation/fragmentation, pooling showed quite some improvements. But the single-object test case was just too simple.
The real-life case are way harder on the garbage collector, as you can see in paragraph 4.

Conclusion : When it comes to memory issues, expect the real performance improvements to be in fact higher than the jsperf result.

6. pre-allocate your arrays whenever you can.

In the case you want to fill an array with some values, allocate the needed memory all at once by using the Array constructor :

     var n = 1000;
     var myArray = new Array(n); 
     var i=0;
     while (i<n) { myArray[i] =i; i++; }

This way of proceeding is ***10 times**** faster then a push() loop. …
(http://jsperf.com/push-allocated-vs-dynamic)

I was surprised by the fact that pre-allocating the array like this :

        var myArray   = [];
        myArray[n-1]  = 0 ;

was not a good idea for performance. My guess is that an array filled by both undefined
(all the n-1 first items) and integer cannot be treated internally as an integer array.

On the other hand, when using the Array constructor (new Array(length)), Firefox and Chrome at least seems to be able to optimize internally the array without problems, so keep this in mind whenever you allready know the size your array will have.

6. write your own, push, pop, unshift, splice (among others).

All those nice features are to be avoided if you need performance : because they are functions : you pay the price of a call.
And also because often you know something about your array the function doesn’t (expl : all items are >0 integers).
Splice is especially to be avoided, since it returns an array of removed items : slower, useless, and creating garbage.
So replace those functions by your own code, and even inline the smallest one : depending on functions, browsers and devices, the performance gain can be from 2X to 10X.

push :      myArray[myArray.length] = XX ;
pop  :      var last=myArray[myArray.length--] ;
unshift :
var unshiftArray = function (arr, item) {
                     var len=arr.length;
                     while (len) { arr[len] = arr[len-1]; len--}
                     arr[0] = item; };
         // this unshift is around 4 to 10 times faster 
         // than the original
         // (http://jsperf.com/array-unshift-vs-prepend/8)
shift : i couldn't beat the original function by hand (FF/Ch).
Splice :
// if you plan on just removing one item, this one 
//    will be way faster :
var spliceOne = function(arr, index) {
                         var len=arr.length;
                         if (!len) { return }
                         while (index<len) { 
                               arr[index] = arr[index+1]; index++ }
                         arr.length--;
                };
indexOf :
var indexOf = function(arr, item) {
                  for (var i=0, len=arr.length; i!=len ; i++) {
                       if (arr[i] === item) { return i }
                   }
                   return -1;
              };
lastIndexOf :
var lastIndexOf = function(arr, item) {
                     var i=arr.length;
                     while (i--) { 
                           if (arr[i] === item) { break } }
                           return i;
                   }; // ... or the paragraph 3 version...

There are many functions that deals with arrays, as you can see here :

https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array

There are even more functions that can use arrays, since any function that takes an arbitrary number of arguments can be used with an array :

expl with min :

  // to use Math.min on an array, write :
  val mim = Math.min.apply(Math, myArray);
  // since min is context-less you can even write :
  val mim = Math.min.apply(null, myArray);
  // caching Math.min wins some time on slower devices/browsers
  var minfunc = Math.min;
  // ... but anyway min is faster when done with 
  //                       a properly coded function... 
  // (http://jsperf.com/math-min-apply-vs-loop/3)

Be carefull about what are doing the arrays or array-friendly functions you use, and if you happen to use one very frequently in critical sections of your code, ask yourself if you cannot beat the javascript engine.
In quite some not-so-special cases you can.

Rq about shift/unshift : beware, those are O(n) operations (meaning : each operation will take a time proportionnal to the number of the array length). Unless you really need to, you shouldn’t use them. push/pop are O(1) (constant time), way better.

7. Could i never de-allocate my arrays ? Yes, you can !

A nice way to never have allocation/disallocation issues is to handle a separate index,
and to handle its pseudo-length separately. Let us call this the ‘sLength’ (stackLength)
of the array.
The code could look like :

  var myStack = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ];
  var myStacksLength = 0;
  // to do a push :
  myStack[myStacksLenght++] = value; 
  // to do a pop :
  var val =  myStack[myStacksLength--]; // you might want to check 
                                       // myStacksLenght before...

So here, if you choose well the initial size, you have a stack with a
null memory cost for its whole life. If by any bad chance you lack space,
no special code is needed : the array will increase (with a memory cost), then
will stay in its new size. You might want to check at the end of one game the
highest stack length to avoid any such re-allocation during the game.

Rq for shift/unshift users : apply the same principle, with two indexes, to
avoid copy/reallocation. One index on the left, one on the right, both starting
at the middle of the array. Then you’ll be again in O(1) time. Better.
Don’t forget to re-center the indexes when they are ==.

If think you’ll easily figure out how to write min/max/indexOf/… such arrays, just use
the stackLength instead of the array length in the loops.

Rq about sLength.
You cannot add sLength as a property of your array : myArray.sLength = 3;
Because by doing so you’ll transform your [] into a {}, since it is the same as
writing myArray['sLength']=3. Expect the performances to drop dramatically if
you do so.

8. Some last words about Typed Array.

In javascript, one thing that makes array slower is the fact that they are, as everything in javascript, untyped.
That’s why html5 invented the typed arrays, which are super fast since they are optimized for a given type of integer. I was very excited about that, but when benchmarking or watching other’s benchmark, i quickly saw that the performance gain was null : Firefox and Chrome at least allready recognize the arrays that are integer array, so no interest in the extra coding for comon cases.

An very interesting article is here :

http://www.html5rocks.com/en/tutorials/webgl/typed_arrays/

But thoses arrays are worth a look : maybe you have special needs that they might fullfill.

If you often copy, the set() method allows to copy very fast, close from ten times faster than by hand.
( http://jsperf.com/typedarray-set-aliased-arrays ).

Another interest might be the ‘clamped’ array, that avoid you to test everything you write. Again a special case, but the gain might be interesting.

Last example : since you can set different views on the same buffer, you can test for some properties using one view, and do some other computation with another view.

Example : imagine you want to make a ‘tint’ effect on your canvas : if a point has a R,G,B above a given value, set the color to be brighter. Imagine also most pixels are black (0,0,0,0), so you can be much faster by testing that first : create a 32 bits view on the image to detect the black pixels at once.

Here’s how you’ll do it :

var tintMe = function( ctx, sizeX, sizeY) {  
    // let's retrieve the image :  
    var myGetImageData = ctx.getImageData(0,0, sizeX,sizeY);
    // get the image buffer
    var buff = myGetImageData.data.buffer;    
    // now here's a clamped byte view on it
    var sourceBuffer8     = new Uint8ClampedArray(buff);  
    // now an int32 view on it.
    var sourceBuffer32     = new Int32Array(buff);
    // this is a view pointing on the alpha part of each pixel
    var Alpha8  = new Uint8ClampedArray(buff, 0, 4); 
    // Alpha8[j] = alpha component of j-th pixel.

    var sum = 0; 
    // iterate through pixels :
    for (var i=0, j=0, len= sourceBuffer32.length ; 
                                 i!= len ; 
                                          i++, j+=4) {
        if (sourceBuffer32[i]) {  // process non-null pixels
            // sum R + G + B 
            sum = sourceBuffer8[j] + 
                   sourceBuffer8[j+1] + 
                    sourceBuffer8[j+2] ;       
           if (sum > 300) { // bright enough ?
                            // -> make it brighter.                         sourceBuffer8[j] = sourceBuffer8[j]+10;                            sourceBuffer8[j+1] = sourceBuffer8[j+1]+10;
         sourceBuffer8[j+2] = sourceBuffer8[j+2]+10;
              // notice that no need to test for values <=255
              // since it is clamped
           }
       }
     }
    // write updated image
    ctx.putImageData(myGetImageData, 0, 0);
    };

you can test it here : http://jsbin.com/ugeloz/2

i didn’t take the time to benchmark it, but no doubt it will be incredibly faster.
Yet another great Javascript feature.

So that’s it, we’ve seen quite some pitfalls to avoid, now your arrays won’t stand in the way .

Don’t you feel better ?

Thoughts on the Javascript game loop.

The game loop is the heart of the video game : each ‘pulse’, any video game calls a function that will :

1.  handle user input.
2.  update the world of the game.
3.  draw the world on the screen.

the looping function is called run and is called by a timer, typically 60 times a second.
Quite often the user input handling and the world update is done with a single function, update. In Javascript, most games spend more time on drawing than on the update,
which gives a sequence diagram which looks like that :

The number of images per second is the frame rate. Any frame rate below 15 images per second is not feeled as fluid by the player.

The common javascript code could look like :

var ga={}; // Game Alchemist namespace.

ga.Game = function(newFps) {
  this.fps = newFps;
  this.frameTime = 1000 / newFps ;
  this.runInterval = null;
  this.ctx = null;
};

ga.Game.protoype = { 
        run         : function () {       
                                  this.update (this.frameTime);
                                  this.draw   (this.ctx);
        },
        launchGame  : function() {
                        this.init(); 
                        this.runInterval 
                            = setupInterval(this.run.bind(this)) ;
        },
        init         : function( some parameters ) {
                              // get the 2D Context
                              // initialize the world
        }, 
        update       : function(frameTime) {
        },
        draw         : function(ctx) {
        }
};

So this would be a basic game loop. But as obvious as this code might seem, we can improve it…

First Issue : This will not work on every screen.

Some screens have a 50Hz refresh rate. Some 60, some others, on phone, are 30Hz, some high-end or 3D monitors are 75Hz, 100Hz or more. How can we match all those rates easily ??

Hopefully, we have a function that allows us to synchronise on the display : requestAnimationFrame. It works somehow like setTimeout : the argument you give is the function that will get called next time the display is available for a draw. So you cannot miss the next display refresh : it will be noticed to you by requestAnimationFrame. ( Some might know this principle under the name of ‘V-sync’, or vertical synchronisation.)

Rq : You might want to bind() your run function to have it keep its context.  Remember that bind() creates a new function each time, so in order to create no garbage, bind the run() in the init and use the bound function.

Now the code will look like :

ga.Game = function(newFps) {
  this.fps = newFps;
  this.ctx = null;
  this.boundGameRun = null;
};

ga.Game.protoype.init = function() {
  // get the context
  // init the world
  this.boundGameRun = this.gameRun.bind(this, this.ctx);
};

ga.Game.prototype.gameRun = function() {
  this.run();
  requestAnimationFrame(this.boundGameRun);
};

Second issue : We should draw, then update. In this order. .

When the game starts, it will initialize all its values (the player/monsters position, speed, … ) then it will call run, so if we follow the update-draw order, the first thing done … will be to update the world : the inital status will never get drawned.
So we have better permutate the order within the run function:  a draw, then an update.

Another reason to switch order : The draw is NEVER on time with the update-draw order.

If the update is before the draw, whatever the time the update takes, this time will add up BEFORE the drawn is made so the drawing will never be on time, right when the display is available -remember it is the purpose of requestAnimationFrame to say ‘hey, the screen is ready’, so when it is ready… use it with no delay !

Notice that you don’t have all the frame time to draw. First thing is that, if you are drawing in x ms, you draw should start before 20 – x ms. But this might not be enough : most devices have double or triple buffering; and have a given time range during which they can draw. Otherwise the effective display will be in fact postponed, leading to various strange artifacts. Again : jump on the train as soon as possible.

Last good reason to revert update/draw order : the Garbage collector

If the system needs to reclaim so memory, then a garbage collection occurs, which stops the current processing for a short time (and sometimes not so short).
But guess what ? when an intensive update occurs, it raises the chances that the garbage collector will be invoked, and the update will take even longer, thus making the two consequent draw nearer… before returning to the normal frame time. One way of describing the effect is that the game will seem to be very fast the time of a glimpse.
On the other hand, the draw() does not create garbage, and does computation. Put the draw first, and it will not create garbage, then the update that follows will create garbage, then during the free time that follows, the garbage collector can ‘breathe’ and use the free time to garbage collect. With the right order we minimise the chances that the garbage collector occurs before a draw and get noticed.

So from now on we’ll use the good order : draw, then update.
Game.run becomes :

Game.protoype.run = function() {
       this.draw(this.ctx);
       this.update(this.frameTime);
};

But even for a basic game loop, relying on requestAnimationFrame introduces some issues that leads us to handle time by ourselves.

Why we nee to handle a game time

1) Because we don’t know about the time any more

With requestAnimationFrame, the loop might be called 20 to 100 times a second. You cannot do any fixed computation, like for instance this one on position :

   if (rightKeyPressed) position.x = position.x + 10;

If you made this loop with a 60Hz device in mind, it will be 3 times slower on a 20Hz one, and almost 2 times faster on a 100Hz screen.
So you need to know the frame time, and do your computation based on this time :

if (rightKeyPressed)  position.x = position.x 
                                      + velocity.x * frameTime ;

2) Because there are very fast screens.

If we have a very fast screen, for instance a 100Hz screen, we need to skip one frame on two, and switch to 50Hz, because the 100Hz refresh will drive the CPU and its fan crazy, your game will eat quite some power. Not so good. We need to be able to detect a too fast frame rate.

3) Think about slow devices / long update() : frame miss.

If the device is slow or the update is taking time, or the draw, even, is very long, we might not always be able to keep the fps pace, and miss some frame, so when relying on requestAnimationFrame, counting the frames cannot give you the time elapsed, even if you know the screen refresh rate. So we need to know each time how many time REALLY elapsed since last update.

4) Sudden slow down / Pause of the game
If the user switch tabs in a Browser, or do some operation sudddenly takes all CPU, the game will stop without knowing it. Same happens if the game is paused (which happens automatically on some browsers/devices when focus is lost).
Notice that there are quite some common scenarios that require a pause : your player looking in the inventory / looking a map / a part of the plot is revealed / …
Whatever the sleep time the game should just quietly resume, and consider just one frame elapsed.

So we need a small object that will handle the time, and measure the frame time. This object will also keep track of the current game time.

ga.gameTime =  {  // we define just an object since 
                  //  there is only one instance.
  lastTime     : Date.now(),
  frameTime    : 0 ,
  typicalFrameTime : 20,
  minFrameTime : 12 , 
  time         : 0
};

// move the clock one tick. return true if new frame, 
//      false otherwise.
 ga.gameTime.tick = function() {
    var now = Date.now();
    var delta = now - this.lastTime;
    if (delta < this.minFrameTime ) return false;
    if (delta > 2*this.typicalFrameTime) { // +1 frame if too much time elapsed
       this.frameTime = this.typicalFrameTime;
    } else
    {  this.frameTime = delta;      
    };   
    this.time+=this.frameTime;
    this.lastTime = now ;
    return true;
}

ga.Game.prototype.gameRun = function() {
  if (!gameTime.tick()) {
                     requestAnimationFrame(this.boundGameRun);
                     return; }
  this.run();
  requestAnimationFrame(this.boundGameRun);
};

ga.Game.protoype.run = function() {
       this.draw(this.ctx);
       this.update(gameTime.frameTime);
};

Beware : from now on, you should use game time and not the real time in all your time related computations.

Imagine we have a boucing ball. x and y defines the position on screen ( say x=0..640, y=0..480 ) and vx, vy  defines velocity. The update of the ball position shouldn’t be a constant increase, but rather depend on the current frame time.

Ball update should looks like :

  Ball.update = function ( frameTime) {
                               this.x = this.x + vx*frameTime;
                               this.y = this.y + vy*frameTime;        };
// velocity { vx, vy } is set in Kpixel per millisecond in this example.
// frameTime = ga.gameTime.frameTime

Another example of time dependency : Imagine now you have a bouncing object, the code might loook like :

SomeObj.update = function( frameTime ) {
       this.x = / some constant /;
       this.y = this.y0 + 
                this.amplitude * sin( this.freq * Date.now());
};

The bad thing about this code is that, if a pause ever happens, when the game resume, Date.now() will have a random value, hence the bouncing object will suddenly jump to an other value. The only way to avoid this is to rely on game time, which will stop when the game pauses.
New code :

SomeObj.update = function( frameTime ) {
        this.x = / some constant /;
        this.y = this.y0 + 
           this.amplitude * sin( this.frequ * ga.gameTime.time ); 
};

A remark though : if you plan on implementing multiplayer games, you should NOT skip frames when a too big time elapsed. And you should have an update function that can handle a big time elapsed properly. Which means, on the other hand, have a program that can deal with a player’s momentary silence.

What about handling Update on a different timer ?

Some people suggest that the only way to handle properly the logic and the draw is to have them run on separate timing : the draw would be synced on rAf, while the update would have its own timer.

So first thing about this : do NOT rely on setTimeout to perform a  regular update. setTimeout’s accuracy might be less than 12ms on some browsers/devices, and since 50Hz, for instance, is 20ms, this is just a no-go, and i don’t even mention the overhead of setting a timer : rely on setInterval, way way more accurate.

But if you think about handling update on a different timer, just ask yourself : why would i draw again when no update occured ? or why would you update when you cannot have no time to draw the update result ?

The arguments against rAf are that 1) it might slow down if battery policy requires so, and 2) it might even stop if the game gets out of focus. But why would a game perform some computations if they do not lead to a display refresh ?
The real solution to this real problem is : you should handle game time by yourself, and perform computations based only on the game time. And the second aspect of the solution is to resume properly after a long time of inactivity, for multiplayer games.

For a single player game, resuming properly is simple : just resume ONE frame later when the player comes back.
For multi-player game, the answer is more complicated : and it might be in fact more simple to handle iteration by small steps only : imagine a game where trees grows, get cut, … in ‘real’ time. So in this case we would have an update loop running on a setInterval, which will indeed perform update *only if* the rAf update did not happened for a while. – In fact this might be the subject of a whole article, so i’ll stop here -

But let’s get back to the point : having a separate timer for updates and draws leads to a much higher complexity, since you must both get sure the useless draw / useless updates / or the synchronisation logic in between update and draw is not leading the solution to be worse than the problem…

Some code you might copy-paste

So here’s a piece of code you might use to do a simple-yet-not-so-bad animation loop :

(function() {
  var requestAnimationFrame = window.requestAnimationFrame ||
                           window.mozRequestAnimationFrame ||
                        window.webkitRequestAnimationFrame || 
                            window.msRequestAnimationFrame;
  window.requestAnimationFrame = requestAnimationFrame;
})();

var ga = {};

ga.gameTime =  {  // we define just an object since 
                  //  there is only one instance.
  lastTime     : Date.now(),
  frameTime    : 0 ,
  typicalFrameTime : 20,
  minFrameTime : 12 , 
  time         : 0
};

// move the clock one tick. return true if new frame, 
//      false otherwise.
 ga.gameTime.tick = function() {
    var now = Date.now();
    var delta = now - this.lastTime;
    if (delta < this.minFrameTime ) return false;     if (delta > 2*this.typicalFrameTime) { // +1 frame if too much time elapsed
       this.frameTime = this.typicalFrameTime;
    } else
    {  this.frameTime = delta;      
    };   
    this.time+=this.frameTime;
    this.lastTime = now ;
    return true;
}

ga.Game = function(nCtx, nUpdate, nDraw) {
  this.ctx = nCtx;
  this.update = nUpdate;
  this.draw = nDraw; 
  this.boundGameRun = this.gameRun.bind(this, this.ctx);
};

ga.Game.prototype.gameRun = function() {
  if (!ga.gameTime.tick()) {   requestAnimationFrame();
                               return; }
  this.run();
  requestAnimationFrame(this.boundGameRun);
};

ga.Game.prototype.run = function() {
       this.draw(this.ctx);
       this.update(ga.gameTime.frameTime);
};

var myUpdate = function(dt) {
  // put here your update computations, relative to dt	
};

var myDraw = function(ctx) {
  // ...
};

var myGame = new ga.Game(ctx, myUpdate, myDraw);

myGame.gameRun();

That’s about it, thanks for reading, and any comment welcome.

No more garbage : Pooling objects built with constructor functions

Why creating an object creates an issue.

We all know about the evil garbage collector of Javascript, a cruel monster that might at any moment freeze your game to recollect unused memory, and waste some frames or loose some inputs events, spoiling the game experience.
The fight against garbage creation must be led on several fronts : I’ll adress here the specific case of object creation using a constructor function, and in this article, i’ll use ‘object’ to talk about ‘object created by a constructor function’.

(For those who likes to know the end of the movie before it starts : The simple and classical pattern i expose here leads to X2 to X5 performance boost, and reduces game freeze.)

( You can find the code here :

https://github.com/gamealchemist/Javascript-Pooling/tree/master/True_JS_Classes )

Reminder : using  a constructor function looks like :

var myObject = new MyClass(param1, param2, ...);

var MyClass = function (param1, param2, ...) {
    this.prop  = param1;
    this.prop2 = param2;
    return this;
};

For such an object, the memory system is used three times :

1. using the new operator is equivalent, in Javascript, to create a new object : {}, and assigning it to the ‘this’ of the function.
2. The constructor function (MyClass) will then perform intialisation and add some properties to the object. Memory will again be allocated for those properties.
3. When the object is no longer in use (‘goes out of scope’), its memory it is not recollected at once : rather it is marked for recollection, hence feeding the evil garbage collector. When, at some random point in time, memory is lacking, a large amount of memory is reclaimed all at once : garbage collection occurs, freezing the game for up to 10ms – a disaster-.

Let us see a very simple example :

// in the init of the game...
var someBadGuy = new BadGuy() ;

// later on during a fight...
if ( Hero.strength > someBadGuy.strength ) {
   Hero.kills++;
   someBadGuy = new BadGuy(); //create a new enemy to fight against
}

Here, when we create a second bad guy after defeating the first one, we have no more reference to the first guy : We created garbage.
Hence the first guy is marked to be later recollected : this simple code is allready exhibiting a potential issue (in fact it created a performance issue in the future).

The performance hit due to object depends on two factors : the frequency of creation/disposal of objects, and the size of those objects.
Some sensitive cases might be :

• Frantic games (no, i’m not talking about Super Crate Box )
• Games using a particle engine (for explosions, rainbows, …).
• Games using 2D/3D physic engine(hence vectors computations).

But even in a slow-paced game, the recollection will randomly occur and make your character sometimes react oddly to, say, keystrokes, and hinder player’s experience.

Another thing worth noticing : Some (most?) game frameworks generates quite some garbage only to handle mouse moves or key strokes, and/or to handle object collisions, and/or use a class system that makes any class instance -even for simple classes- use quite some memory.
So before you even started to put some action, you can rest assured that the garbage collector will score in your game.
Still, this is not a reason to quit the fight.

The solution : let’s go to the pool

There is a much neater way to handle your objects : use a pool.

A pool is a stack of object that you put aside for your game :

• When a new object is required, just take it from the pool then initialize it.
• When you no longer use your object, throw it back in the pool.
• If you need an object and the pool is empty, then -too bad- just use standard new() to get a new one.

So allocations happens less frequently, and recollection never happens (during the game).
Even better : if you determine the maximum number of objects your game might use, you can even pre-fill your pool with this number of objects, and you’ll never have to create or wait for recollection for this object.

How nice !

So how do we implement this in Javascript ?

Preliminary remark : I’ll make use here of ‘true’ Javascript ‘classes’,
i.e. classes :

• setting properties in the constructor.
• defining methods on the prototype.

This is the fastest and most memory efficient way to create objects in JS, and objects created this way also have the best performances.

Second remark : I won’t adress how to handle pooling with any of the many class library available for JS (like JQuery’s class system).

So here’s a (very simple) example of such a true JS class :

var BadGuy = function(posX, posY, gun, ammo) {
      this.posX   = posX  ;  this.posY   = posY  ;
      this.speedX = 10    ;  this.speedY = 0     ;
      this.gun    = gun   ;  this.ammo   = ammo  ;
      this.isAlive  = true  ;
      };

BadGuy.prototype.move = function(dt) {
      this.posX += this.speedX * dt;
      this.posY += this.speedY * dt;
};

BadGuy.prototype.canShoot = function() {       
       return (this.ammo != 0);
};

(yes, very simple )
And you use it with :

// create a new bad guy like this :
var myBadGuy = new BadGuy( 100, 10, 'AK47', 100);

// later on you can use it like this  :
if (myBadGuy.isAlive && myBadGuy.canShoot()) {
      Hero.runAwayShouting('please do not use your '
                                  + myBadGuy.gun +' on me !!');
};

So now let’s get back to pooling : the two things you have to change to a true JS constructor function to enable pooling is to handle a call with no arguments and return this :

var BadGuy = function(posX, posY, gun, ammo) {
      this.posX   = ( posX === undefined ) ? 100   : posX  ;  
      this.posY   = ( posY === undefined ) ? 0     : posY  ;
      this.speedX = 10    ;  this.speedY = 0               ;
      this.gun    = ( gun  === undefined ) ? 'AK47': gun   ;  
      this.ammo   = ( ammo === undefined ) ? 100   : ammo  ;
      this.alive  = true  ;
      return this;
      };

This not a limitation, since even if you’re not pooling, returning this doesn’t hurt, and handling undefined arguments :

• Protect your function from calls to new() with a wrong number of arguments.
• Ensures inner JS engine optimisations, since properties always have the same inner type (they never have the doomed ‘undefined’ value ).
• It allows you to call the constructor with only the relevant parameters :

var myBadGuy = new BadGuy(100);  // this bad guy is on the floor (posY=0),
                                                        // and has an AK47 with 100 bullets.

What you mustn’t do, though, is to add properties or methods on a created object, like with :

myBadGuy.isSmiling = true;

This, again,  is not a limitation, since late object change is a bad practice : it breaks inner optimisations of the JS engine (The JS engine creates a cached backing class for your object : this cache is broken if you change the object on the go).
- Simple solution for this : pour all the stuff you need in your object in the first place -.

So let us now create our pool :

BadGuy.pool = [];  // this one was hard.

(this code, as well as following code, has to be inserted
before the first object creation, but i don’t copy everything for clarity).

Now to get a new bad guy, we need another method that retrieves an object from the pool if one is available : pnew :

 BadGuy.pnew = function( posX, posY, gun, ammo) {
         var newGuy = null;
         // use the pool if object available... 
         if (this.pool.length >0) {
              newGuy = this.pool.pop();
          } else {
          // ... or create a new object if pool is empty.
              newGuy = new BadGuy();
         }
         // initialize and return object.
         BadGuy.apply( newGuy, arguments );
         return newGuy;  
};

Use the pnew function like this :

var myBadGuy = BadGuy.pnew(100, 50, 'M16', 90);

Now, to dispose of the object, we also need a specific method that throws back the object on the pool : pdispose :

BadGuy.prototype.pdispose = function() {
     this.pool.push(this);        
};

Notice that this has to be set on the prototype (it is an instance we are disposing), while pnew is set on the creator function.
use the pdispose function like this :

if ( myBadGuy.health <= 0 ) {
     myBadGuy.pdispose();
     myBadGuy = null    ;
}

Notice that i set the myBadGuy var to null after disposal : this is to ensure we never reference twice the same object.
Here’s an example of what might occur if we do not pay attention :

var firstBadGuy = BadGuy.pnew(10); // get a guy, posX=10
firstBadGuy.pdispose();            // finally we don't need him...
                                   // ... but keep the reference..

var secondBadGuy = BadGuy.pnew(50); // get another guy posX=50 
                                    // It is taken from the 
                                    //  pool, and it is the latest
                                    // pushed, so === to firstGuy

// so now we have two references to the same object.
// if we do :
firstBadGuy.posX = 200 ; 
// we have for the second guy :
console.log( secondBadGuy.posX ); // --> output is 200, not 50 !!!

The issues that might be caused by multiple references might be a nightmare to detect and debug : each time you call pdispose(), ensure you don’t hold any reference to the disposed object.

So now, you must change all your new() calls to pnew(), and whenever an object is no longer in use, you must take care of pdisposing it and clearing any reference to it.

and then …

HURRA !!!!

At this point we have our pooling system, and the ugly garbage collector is defeated !!

or is he ?

Not quite, i am afraid : we have two concerns left.

Issue 1 : We still create some garbage.

When using push() and pop(), we do allocate/disallocate memory, so we still feed the monster with some crumb, so let us use an always-growing stack by handling the lenght separatly.  You’ll see how in the final code.

Issue 2 : what about re-use ?

We obviously need a way to avoid re-writing the same code for each pooled class.
We could define pnew and pdispose directly into the JS Object class (from which all objects, including Functions, inherit), but this would break the Object class definition, from which anything inherits in JS, which, as told earlier, is not wise for performances.
So the best solution is to have a function that inject the pooling system into our function : setupPool.

var setupPool  =  function(func, initialPoolSize) {
    if (arguments.length<2) { 
        throw ('setupPool takes two arguments');    }
    func.pool                = []        ;
    func.poolSize            = 0         ;
    func.builtCount          = initialPoolSize ;
    func.pnew                = pnew      ;
    func.prototype.pdispose  = pdispose  ; 
    // pre-fill the pool.
    if (initialPoolSize>0)
    {
       for (var i=0; i<initialPoolSize; i++) {
          (new func()).pdispose();
        }
    }
};

var pnew     = function() {
    var pnewObj  = null     ; 
    if (this.poolSize>0 ) {
           // the pool contains objects -> grab one
           this.poolSize--  ;
           pnewObj = this.pool[this.poolSize];
           this.pool[this.poolSize] = null   ; // **
    } else {
           // the pool is empty -> create new object
           pnewObj = new this() ;
           this.builtCount++;
    }
    // return initialized object.
    return this.apply(pnewObj, arguments);
};

var pdispose   = function() {
    var thisCttr = this.constructor             ;
    // throw the object back in the pool 
    thisCttr.pool[thisCttr.poolSize++] = this ;
};

A few comments on this code :

1. As told earlier, i use an always-growing array/stack, so i handle its length separately in a poolSize property.
2. I added here the possibility to pre-fill the pool, so no object creation occurs even within the first seconds of the game.
3. I set, within the pool, to null the reference of the object we just grabbed to allow recollection in case it is not pdisposed afterwise, and just goes out of scope.
4. maxPoolSize allows you to easily, at the end of a game cession, know the initialPoolSize that you should use for this class.
5. You might want to detect if you forget to pdispose some objects by counting all calls to pnew and to pdispose. At any moment you should have :
   activeObjectsCount == pnewCount  - (pdisposedCount – initialPoolSize)

Use setupPool like this :

setupPool(BadGuy,100);

Reminder : the constructor function must handle undefined parameters, and return this.

So now victory is complete and all this was a very nice fight. Thank you for reading.

No ! Come On ! We want to know about the performance boost !

Ho, yes.

sure.

In fact this quite difficult to build a test that reflect an actual game sequence, where many object of different sizes have very different lifespan, and where ‘standard’ object ({}, [], strings, closures, functions, …) might be forgotten as garbage all along the way by many not-so-efficient game frameworks.
Another thing is that the performance measure won’t show us for how long the garbage collector froze the JS code during the tests. But i watched on FF/Chrome and we can see that garbage collection occurs often without pooling, and never when pooling (as expected).

Anyway i built a test in JSPerf that reflects *somehow* the performance gain you can expect from pooling.

So i consider that we have 4 different pooled objects, with different memory footprint (more realistic), and a given number of active object that i select randomly within those 4 classes.
We’ll create/dispose of them using three methods :

• standard way : using new / relying on garbage collection.
• using an empty-at-first pool.
• using an pre-filled pool.

You can see the test and experiment by yourself at http://jsperf.com/pooling-test/6

I took 100 active objects, and 50000 of them will be created/disposed randomly.

Here is a screenshot of the results for :
Win8 Chrome / mac OS FF / win 8 IE10 / ipad Safari / mac OS Safari :

pooled vs non-pooled performance

We can see that :

pre-filling the pool helps either a little or not at all.
Chrome sees a near X2 boost.
Firefox manages poorly memory, bust can be as fast as Chrome if helped : X5 boost.
IE10 gets a X3.3 boost.
The ipad appreciates the pre-fill, and gets a X2 boost.
Safari on mac OS, also enjoys pre-fill X2 boost.

Let me know if you experiment pooling in your game : i especially think here of games using intensively vector computation, where the speed boost should be tremendous.

I hope you enjoyed reading this article, and i wish you a good game.

Opening

A blog about my experiments in web game development. It will talk about Html5, a promissing standard, about Javascript, an amazing land where all bricolages are possible, and about the wondefull and long awaited Canvas.

Feel free to comment -as long as it is relevant to the topic- and do not hesitate to contact me for article request or partnership or wathever good idea you might have.

Cheers,

Vincent