A WIP concept of a multiplayer game server skeleton with lag compensation and stuff

QY.js

 /*
   Copyright (c) 2011 Ivo Wetzel.

   Permission is hereby granted, free of charge, to any person obtaining a copy
   of this software and associated documentation files (the "Software"), to deal
   in the Software without restriction, including without limitation the rights
   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   copies of the Software, and to permit persons to whom the Software is
   furnished to do so, subject to the following conditions:

   The above copyright notice and this permission notice shall be included in
   all copies or substantial portions of the Software.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
   THE SOFTWARE.
*/

// REALLY basic multiplayer server with lag compensation and stuff...
// based on: http://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

function ServerClient() {

    this.connection = null;
    this.lastSnapshot = {};
    this.ping = 70; // the ping of the client
    this.interpolate = 2; // how many snapshots are used for interpolation

}

ServerClient.prototype = {

    send: function(tick, snap, snapshotDelta) {

        if (snapshotDelta !== null) {
            console.log('sending ', tick, snap, snapshotDelta);

        } else {
//            console.log('sending ', tick);
        }

    },

    receive: function() {
        // Return the input state
        return null;
    }

};


function Actor() {
    this.id = Actor.id++;
    this.instant = true; // if true, this actor is affected by state rollback
                          // during client input
}

Actor.id = 1;

Actor.prototype = {

    // Snapshots are arrays for performance and traffic reasons
    // So make sure to NOT alter the array size during a game
    // session, or between server / client logic
    getSnapshot: function() {
        return [1, 2, 3];
    },

    /*
     * Called by the server when he sets back state of instant actors
     * for input calculation.
     *
     * This should revert all object properties that were return by getSnapshot
     * to the data in the snapshot.
     */
    applySnapshot: function(snapshot) {
        // apply the values, do stuff...
    },

    /*
     * Called when the server makes changes during a instant rollback and finds
     * differences in the values between the changed snapshot and the next one.
     *
     * It's given the state before the input was applied.
     * e.g. the input is a hit to the actor resulting in a loss of 5 HP
     * "beforeInput" would still have the old HP value, while in "afterInput" the HP
     * value would be the old one minus 5 hit poinzs
     *
     * Since the function is called *after* the actor is back at the latest state,
     * it up to the function to apply the differences between before and after
     * to the current state
     */
    applyDelta: function(beforeInput, afterInput) {
        // TODO apply the delta in an intelligent way
    }

};


function Server() {

    // Make these linked lists for performance
    this.actors = [];
    this.clients = [];

    // Game tick information
    this.tickTime = 0;
    this.tickRate = 30;
    this.tickCount = 0;

    // Snapshort information
    this.snapTime = 0;
    this.snapRate = 20;
    this.snapCount = 0;
    this.snapshots = new Array(this.snapRate);

    // Other stuff
    this.gameTime = 0;
    this.upTime = 0;
    this.lastTime = Date.now();

    var that = this,
        rate = Math.min(1000 / this.tickRate, 1000 / this.snapRate);

    setInterval(function() {
        that.loop();

    }, Math.floor(rate / 2));


    // Testing...
    this.actors.push(new Actor());
    this.actors.push(new Actor());
    this.actors.push(new Actor());
    this.clients.push(new ServerClient());

}


Server.prototype = {

    /*
     * The server loop.
     *
     * This function handles ticks and snaps
     */
    loop: function() {

        // current time
        var now = Date.now(),
            diff = now - this.lastTime;

        // Server up time
        this.upTime += diff;

        // Simulate world and make snaphots
        this.tickTime += diff;
        this.snapTime += diff;

        // We don't use two separate loops because that would create issues with snaphots when
        // we ticked twice due to server
        var tps = 1000 / this.tickRate,
            sps = 1000 / this.snapRate;

        do {

           var ticked = this.tickTime > tps,
               snapped = this.snapTime > sps;

            if (ticked) {
                this.nextTick();
                this.tickCount++;
                this.gameTime += tps;
                this.tickTime -= tps;
            }

            if (snapped) {
                this.nextSnap();
                this.snapCount++;
                this.snapTime -= sps;
            }

        } while(ticked || snapped);

        this.lastTime = now;

    },

    /*
     * Called on each "game" tick.
     *
     * Fetches input from clients and applies the input state to the
     * calculated snapshot from client time.
     *
     */
    nextTick: function() {

        // Process client input, in case there is any
        var clients = this.clients;
        for(var i = 0, l = clients.length; i < l; i++) {

            var client = clients[i],
                input = client.receive();

            // This is where the fun begins...
            // We revert the actors back to the calcuated state when the
            // client send his input
            // afterwards we revert back to server state..
            // so the called function here sees the state when the input
            // happened

            // Receive should return null when the state didn't change
//            if (input !== null) {

                // Calculate the approximate snapTick at which the client
                // send the input
                var clientSnap = (this.snapCount - client.interpolate)
                                 - Math.round(client.ping / (1000 / this.snapRate));

                var clientSnapshot = this.getSnap(clientSnap),
                    clientSnapshotNext = this.getSnap(clientSnap + 1);

                // TODO optimize by keeping a list of instant affected actors
                var instantActors = [],
                    instantSnapshots = [],
                    actors = this.actors;

                for(var a = 0, al = actors.length; a < al; a++) {

                    var actor = actors[a];

                    // Rollback state on the actor if instant
                    if (actor.instant) {
                        instantActors.push(actor);
                        instantSnapshots.push(actor.getSnapshot());
                        actor.applySnapshot(clientSnapshot);
                    }

                }

                // Apply input
//                this.gameInput(client, input);

                // Calculate changes and rollback to world state
                // then trigger the delta applies
                for(var a = 0, al = instantActors.length; a < al; a++) {

                    var actor = instantActors[a];
                        changed = actor.getSnapshot();

                    // rollback to old state
                    actor.applySnapshot(instantSnapshots[a]);

                    // Apply the delta TODO only do this if stuff changed
                    actor.applyDelta(clientSnapshot, changed);

                }

//            }

        }

//        this.gameLoop(this.tickCount, this.gameTime);

    },

    /*
     * Handles (creates) the next snapshot and sends out diffs to all clients.
     */
    nextSnap: function() {

        // Save the snapshot
        var snapshot = this.snapshots[this.snapCount % this.snapRate] = this.getSnap();

        var clients = this.clients;
        for(var i = 0, l = clients.length; i < l; i++) {

            var client = clients[i],
                delta = this.snapDelta(snapshot, client.lastSnapshot);

            // .send() should only send the tickCount when delta is NULL
            client.send(this.tickCount, this.snapCount, delta);
            client.lastSnapshot = snapshot;

        }

    },

    /*
     * Returns a snapshot of all actors.
     *
     * @params {Number} id If omitted, a new snapshot is returned
     * @returns {Object} In case a new snapshot was created or the
     *                   one with the given ID was found
     */
    getSnap: function(id) {

        if (id === undefined) {

            var snapshot = {},
                actors = this.actors;

            for(var i = 0, l = actors.length; i < l; i++) {

                var actor = actors[i];
                snapshot[actor.id] = actor.getSnapshot();

            }

            return snapshot;

        } else {

            id = Math.max(id, this.snapCount - 20);
            return this.snapshots[id % this.snapRate];
        }

    },

    /*
     * Create a delta between two snapshots.
     *
     * @returns {Object} With keys for all changed actors
     *                   If the actor was removed, the value is null
     *                   Otherwise the value is an array with the data
     *                   Indexes set to undefined indicate unchanged fields
     *
     * @returns {null} When there is no difference
     */
    snapDelta: function(snapshot, old) {

        var snapDiff = {},
            snapChanged = false;

        // Diff all current actors against the previous snapshot
        for(var a in snapshot) {

            var actor = snapshot[a],
                oldActor = old[a];

            // Diff the actor data against the old data
            var actorChanged = false,
                actorDiff = [];

            for(var i = 0, l = actor.length; i < l; i++) {

                var value = actor[i];

                // Did it change? Or is there no old actor at all?
                if (!oldActor || value !== oldActor[i]) {
                    actorDiff[i] = value;
                    actorChanged = true;

                } else {
                    actorDiff[i] = undefined;
                }

            }

            if (actorChanged) {
                snapDiff[a] = actorDiff;
                snapChanged = true;
            }

        }

        // Now check for removed actors
        for(var o in old) {

            if (!snapshot[o]) {
                snapDiff[o] = null;
                snapChanged = true;
            }

        }

        return snapChanged ? snapDiff : null;

    }

};

new Server();