Wednesday, November 26, 2014

Binary Search vs. array.indexOf()

So I needed a binary search and decided to write a short tutorial on it. This binary search class uses ds.oop a small oop javascript framework which can be downloaded or cloned from github.

    ds.make.class({
        type: 'ArrayUtils.BinarySearch',
        constructor: function() {
        }
    });
Ok so this class is going to do a binary search of an array for us. If you don't know what a binary search is its just a much faster way of searching than simply starting at the beginning of a list and running through a for loop and testing each element to see if it matches. Instead of binary search starts in the middle and depending of if the value is more or less it jumps to the middle of the first half or the last half of the list. It continues to do this until it finds the matching item or until it can no longer divide up the list.
Visual representation of a binary decision tree.
So we know we need an array to search through so lets add an array property and initialize it with the constructor.

    ds.make.class({
        type: 'ArrayUtils.BinarySearch',
        properties: {
            array: []
        },
        constructor: function (array) {
            array.sort();
            this.array = array;
        }
    });

Ok great. Now we can pass in an array through the constructor and it will live in our class instance. Also we have sorted the array so the elements should be in alpha-numeric order. Now in order to do the binary search we will need to do some string comparisons so lets make a static class for all the string functions we will write.

    ds.make.static.class({
        type: 'string',
        compare: function (a, b) {
            if (a.toString() < b.toString()) return -1;
            if (a.toString() > b.toString()) return 1;
            return 0;
        }
    });

So now we can call `string.compare(a,b)` from anywhere and get a result. I could have just included this in the BinarySearch class, but we may want to use it again somewhere else in our project so its better if its in a separate class for string utility functions.

Ok so now we just need to add the search method.

    search: function (search) {
        var array = this.array;
        var length = array.length;
        var index = Math.floor(array.length * 0.5);

        while (length > 1) {
            var cmp = string.compare(search, array[index]);
            if (cmp == 0) return index;
            length = Math.ceil(length * 0.5);
            var half = Math.ceil(length * 0.5);
            index = index + (half * cmp);
        }
    }

So first this creates some local variables. We need to use `this.array` to access array now since it is a public property of the class. The index we use to search starts in the middle of the array. Then in the while loop we do a comparison between the search and the item at the current index. The result will be -1,0, or 1 (less than, equal, or greater than respectively). Then if its a match we return the index otherwise the index jumps to the middle of the first half or second half of the list and repeats the process.

Finally, lets test out the class and see if it works.
    var a = new ArrayUtils.BinarySearch(['Orange', 'Kiwi', 'Lime', 'Apple', 'Grape', 'Banana']);
    var index = a.search('Lime');
    alert('index: ' + index + '   item: ' + a.array[index]);

Ok. It seems like its works. We create the class instance and pass an array into it. Then we call the search method to return the index. Lets do a better test and also see how the speed compares to array.indexOf().

    // now lets test it
    var a = new ArrayUtils.BinarySearch(array);

    // accuracy test
    for (var i = 0; i < array.length; i++) {
        var item = array[i];
        var index = array.indexOf(item);
        var bindex = a.search(item);
        if (array[index] != array[bindex]) 
            throw 'The binary search result was incorrect!  i: ' +i +'  item: '+item+'  index: '
            +index + '>' +array[index]+'  bindex: '+bindex +'>' +array[bindex];
    }

    // speed test
    var iterations = 1000000;
    var old_time = (new Date()).getTime();
    for (var i = 0; i < iterations; i++) {
        var item = array[Math.floor(Math.random() * array.length)];
        var index = array.indexOf(item);
    }
    var new_time = (new Date()).getTime();
    var seconds_passed_indexOf = (new_time - old_time)/1000;

    old_time = (new Date()).getTime();
    for (var i = 0; i < iterations; i++) {
        var item = array[Math.floor(Math.random() * array.length)];
        var index = a.search(item);
    }
    new_time = (new Date()).getTime();
    var seconds_passed_binary_search = (new_time - old_time)/1000;

    alert(iterations + ' iterations\nindexOf:\t\t' + seconds_passed_indexOf 
            + '\nbinary search:\t\t' + seconds_passed_binary_search)

And here are the results. I ran the test with an array of 7000 random strings. As you can see, our BinarySearch class is waaaaayyy faster.

    1000000 iterations
    indexOf:  15.387 seconds
    binary search: 0.207 seconds

To see this class in action check out the tutorial folder. Thanks for reading!

Sunday, November 23, 2014

Singletons in ds.oop and Phaser State Management

State management is one of the things that separates a demo from a complete game. Phaser has a great state manager that helps to get states up and running quickly. While writing a game state manager is a good academic exercise for any game developer but since phaser already has one I'll just use it instead of writing my own.

So lets just get right into the code. We will be using the ds.oop framework to create a static class to encapsulate the phaser game and state management system. This class allows us to setup the state switching in one place which makes it easier to read and makes it easy to load states from a json file or later if we want.

// Singleton Class
ds.make.static.class({
    type: 'Game.State',
    constructor: function () {
        this.width = 800;
        this.height = 600;
        this.game = new Phaser.Game(this.width, this.height, Phaser.WEBGL, 'cartest');
        this.states = [];

        this.add(Game.Boot);
        this.add(Game.Loader, false);
        this.add(Game.World);
        this.start();
    },
    add: function (stateClass, clearWorld, clearCache) {
        this.game.state.add(stateClass.prototype.type, stateClass);
        this.states.push({
            state: stateClass.prototype.type,
            clearWorld: clearWorld,
            clearCache: clearCache
        });
    },
    start: function () {
        this.stateIndex = -1;
        this.next();
    },
    next: function () {
        var p = this.states[++this.stateIndex];
        this.game.state.start(p.state, p.clearWorld, p.clearCache);
    }
});

So this is the entry point for our phaser game. The constructor creates the phaser game object and adds all the game states. The add method will cache the parameters for the game.state.start method until we are ready to switch the state. The state order is completely linear in this example but it would be trivial create a branching structure that switches states conditionally if needed.

Here is the first state class. I created this jut as an example to show how the state switching works now. As you can see there is no need to keep track of which state is next. The order is already set in the Game.State class. All we are doing is calling the next() method to signal the state change.

ds.make.class({
    type: 'Game.Boot',
    create: function () {
        Game.State.next();
    }
});

The first task for our state manager is to display some graphic like a loading bar while the user waits for the game assets to load. The loading screen is a standard way to manage loading assets in a game. Here i'm just updating some text with the percentage loaded. Later we will load some loading screen assets and display an animated loading screen with a progress bar but for now this should give you the general idea.

ds.make.class({
    type: 'Game.Loader',
    preload: function() {
        var style = { font: "12px Lucida Console", fill: "#ffff44", align: "left" };
        this.text = this.game.add.text(5, 5, 'Loading...', style);
        this.text.fixedToCamera = true;
        // Load all the assets here
    },
    loadUpdate: function () {
        this.text.setText('Loading: ' + this.game.load.progress + '%');
    },
    create: function () {
        Game.State.next();
    }
});

Part 2 of this tutorial coming soon...

Tuesday, November 18, 2014

Combining Phaser and Three.js to make 2.5D games.

I wanted to incorporate 3D elements into a phaser game and since phaser does not support 3D I started looking at Three.js. Phaser and Three are both great game libraries on their own but individually neither one of them did everything that I wanted so I thought, why not combine them?

To see the demo in action click here.
here is the demo source code

Maybe I should take a step back for a moment. For those of you who don't know, Phaser is a great javascript game library for writing HTML5 games. It is based on PIXI.js as supports seamless canvas and webGL rendering of 2D games as well as tweening, tilemaps, sprites, collision detection, and physics. Three.js is another great javascript game library but unlike Phaser which only supports 2D, Three.js is designed to abstract away the complexities of working with 3D rendering in webGL.

The last library that I should mention is ds.oop. This is not a game library at all. It is a very lightweight abstraction layer for creating highly reusable classes in javascript. ds.oop streamlines object oriented programming in javascript by hiding all of the ugliness of inheritance and class creation in javascript and leaving you with a simple easy to maintain class object. Most importantly it just works. I highly recommend it for any javascript project.

Required Libraries:

There are likely many ways to combine phaser and three in a project but for my purposes, I wanted to use phaser primarily and just use three for incorporating some 3D elements into the game so I decided to keep the typical phaser game structure. I'm using the normal phaser rendering pipeline. Initially I thought about rendering everything from phaser onto a textured plane in three but I decided to do it the other way around and just render some elements in three and then grab the bitmap data and render it in phaser like any other sprite. This turned out to be easier than I thought.

The Phaser.Three class

This class allows you to create a layer in your phaser game that consists of a scene rendered by three.js. The class is fairly minimal. The init method starts an instance of THREE.WebGLRenderer with the same dimensions as the currently running phaser game. Then it creates a sprite from the off screen canvas to use as an layer. The sprite is attached to the phaser camera. Finally this method setup up the three.js scene and camera based on the current aspect ratio.
ds.make.class({
    type: "Phaser.Three",
    constructor: function () {
        throw 'Do no instantiate this class. Inherit it and call the init method from your constructor!';
    },
    init: function (game) {
        this.game = game;

        // renderer
        this.renderer = new THREE.WebGLRenderer({ alpha: true });
        this.renderer.setSize(game.width, game.height);

        // setup canvas to be used as a sprite texture
        this.canvas = this.renderer.domElement; 
        this.context = this.canvas.getContext('2d');
        this.baseTexture = new PIXI.BaseTexture(this.canvas);
        this.texture = new PIXI.Texture(this.baseTexture);
        this.textureFrame = new Phaser.Frame(0, 0, 0, this.game.width, this.game.height, 'debug', game.rnd.uuid());
        this.sprite = this.game.add.sprite(0, 0, this.texture, this.textureFrame);
        this.sprite.fixedToCamera = true;

        // camera
        var fov = 45;
        var camera = new THREE.PerspectiveCamera(fov, game.width / game.height, 1, 10000);
        var dist = game.height / 2 / Math.tan(Math.PI * fov / 360);
        camera.position.z = dist;
        //camera.position.y = 200;
        camera.lookAt(new THREE.Vector3(0, 0, 0));
        this.camera = camera;
        this.maxHeight = dist;

        // scene
        var scene = new THREE.Scene();
        this.scene = scene;

        var ambientlight = new THREE.AmbientLight(0xF0F0F0); // soft white light
        scene.add(ambientlight);
    },
    update: function () {

        this.scene.position.x = -this.game.camera.position.x * 2;
        this.scene.position.y = -this.game.camera.position.y * 2;

        // render
        this.renderer.render(this.scene, this.camera);

        PIXI.updateWebGLTexture(this.baseTexture, this.game.renderer.gl);
    }
});

So this is the base class that takes care of setting up the camera for you. The update function in this class will lock the three camera to the phaser camera position so when you move game.camera to a new position the scene will also render that position.

Using this class in easy. Just inherit it and start adding some meshes or whatever you need to render in Three.js
ds.make.class({
    type: 'Game.Layer3D',
    inherits: Phaser.Three,
    constructor: function (game) {
        this.init(game);

        // make a box
        var geometry = new THREE.BoxGeometry(100, 100, 100);
        mesh = new THREE.Mesh(geometry, new THREE.MeshNormalMaterial());           
        mesh.position.z = 50;
        mesh.position.x = 300;
        mesh.position.y = 300;
        this.scene.add(mesh);
    }
});

Now to see it in phaser you have to create the Layer3D object in the phaser create function:
this.layer3d = new Game.Layer3D(game);

Finally, don't forget to call update in your update function. This will update the camera position in the three.js scene and render the scene to the viewport.
this.layer3d.update();

And That's really all there is to it. Special thanks to Rich on the Phaser forums for posting an example of rendering into Phaser from an off-screen canvas and also to everyone reading this, I hope this short tutorial was helpful for you to get started with 3D mix-ins in phaser.