gd reflections

Memylon: the language wars are over!

2011-04-25T12:19:00.000-07:00

Meet my cat:
He's programming (and JavaScript in particular) illiterate, but likes to program anyway. And situation like this is perfectly fine, unless that code, which is written to learn things, goes into production. We all know that never happens, though. We do, right?..

Anyway, one day he wanted to play with Html5 canvas and make a small silly game or something.

And that's what he came up with:

Misses: 0 Sure, but what is this?..

This is a classical Memory game:

At the beginning all the cards are shown for a couple of seconds. Try to remember their positions!
Then click on two cards at time to flip them over.
If a matching pair is revealed, then those cards disappear.
But the cards flip back if they do not match, and this counts as a "miss".
The goal is to find all the matching pairs with the least amount of misses.

As you may have noticed, the cards are corresponding to different programming languages, thus the name of the game: Memylon (what cat does not love cheap puns?..)

The full source code to the game can be found on github.

The unsophisticated animal did not use any existing JavaScript libraries. He definitely should have, but sometimes reinventing a bicycle is so much fun (oh yeah, of course he did peek into the jQuery source a couple of times, to check what shape the wheels are there)!

And of course, please pardon the silly animal if it does not work in your browser. It seemed to in the latest Chrome, Opera, Firefox and Konqueror on Linux, as well as in Chrome, Opera, Firefox, Safari and IE9 on Windows (even though with Chrome on Linux the global alpha value on the canvas' context did not seem to affect text transparency... which might be a bug or again a result of illiteracy - go figure).

First thing he did is running GIMP and gathering a collection of programming language pics into an "atlas" image (it should be mentioned that all the language logos/trademarks belong to the corresponding authors/owners, and background image is a courtesy of Renaissance):

Of course, every programmer knows that one should start from the hardest things. Not from the ones which are the most fun!!!

But come on, he's just a cat.

After that the illiterate creature opened a text editor and typed in a pile of JavaScript code:

//  the main entry point 
window.onload = function () { 
    Memylon.init(); 
} 
 
//  the game module 
var Memylon = function() { 
    //  constants 
    var FRAME_TIME = 50, FLASH_TIME = 1000; 
    var CARD_W = 64, CARD_H = 60, CARDS_IN_ROW = 11, CARDS_NUM_VARIATIONS = 54; 
    var FLIP_TIME = 500, HIDE_TIME = 500, SHOW_TIME = 300; 
    //  variables 
    var cards  = [], anims = []; 
    var numCardsW = 6, numCardsH = 4; 
    var prevIdx = -1; 
    var numMisses = 0; 
    var canInteract = false; 
    var bgImage, cardsImage; 
    var context; 
 
    // the initialization function 
    function init() { 
        var canvas = Utils.$('gameArea'); 
        if (canvas && canvas.getContext) { 
            context = canvas.getContext('2d'); 
            Utils.$('restartGame').onclick = function () { 
                this.value = 'Restart'; 
                resetGame(); 
            }; 
            canvas.addEventListener('mousedown', function (e) { 
                    onMouseClick(e.clientX - canvas.offsetLeft, e.clientY - canvas.offsetTop); 
                }, false); 
            setInterval(updateBoard, FRAME_TIME); 
        } 
 
        bgImage = Utils.$("bg"); 
        cardsImage = Utils.$("cards"); 
    } 
    //  draw a card sprite on canvas 
    function drawCard(cardID, x, y, scaleX, scaleY) { 
        var glyphID = cardID > 0 ? cardID : 0; 
        var cx = x + CARD_W*(1 - scaleX)/2; 
        var cy = y + CARD_H*(1 - scaleY)/2; 
        var glyphX = (glyphID%CARDS_IN_ROW)*CARD_W; 
        var glyphY = Math.floor(glyphID/CARDS_IN_ROW)*CARD_H; 
 
        context.drawImage(cardsImage, 
            glyphX, glyphY, CARD_W, CARD_H, 
            cx, cy, CARD_W*scaleX, CARD_H*scaleY);    
    } 
    //  play a "flash cards" animation 
    function playFlashCards() { 
        canInteract = false; 
        for (var i in cards) { 
            var card = cards[i]; 
            var startDelay = (i%numCardsW + 1)*80; 
            var flashTime = FLASH_TIME*numCardsW; 
            card.anim = createAnim( 
                ['pose', startDelay, card.id], 
                ['flip', FLIP_TIME,  card.id], 
                ['pose', flashTime, -card.id], 
                ['flip', FLIP_TIME, -card.id]); 
        } 
        anims = [createAnim(['exec', numCardsW*80 + FLIP_TIME*2 + flashTime, 
            function () { canInteract = true; }])]; 
    } 
    //  game-specific animation update functions 
    var AnimFunctions = { 
        //  "draw static card" animation 
        pose : function(t, cardID, card) { 
            drawCard(cardID, card.x, card.y, 1, 1); 
        }, 
        //  "flip card" animation 
        flip : function(t, cardID, card) { 
            var scale = Math.cos(Math.PI*t); 
            var id = (scale > 0) ? cardID : -cardID; 
            drawCard(id, card.x, card.y, Math.abs(scale), 1); 
        }, 
        //  "dissolve card" animation 
        hide : function(t, cardID, card) { 
            if (t < 1) { 
                context.globalAlpha = 1 - t; 
                drawCard(cardID, card.x, card.y, 1, 1); 
                context.globalAlpha = 1; 
            } 
        }, 
        //  flying text animation 
        text : function (t, params) { 
            //  append missing parameters with defaults 
            Utils.setDefaults(params, {sizeFrom: 10, xFrom: 182, yFrom: 150, alphaFrom: 1, 
                font: 'Arial', bold: true, color: '#2222AA'}); 
            Utils.setDefaults(params, {sizeTo: params.sizeFrom, alphaTo: params.alphaFrom, 
                xTo: params.xFrom, yTo: params.yFrom}); 
            //  interpolate current text parameters 
            var size = Utils.lerp(params.sizeFrom, params.sizeTo, t); 
            var x = Utils.lerp(params.xFrom, params.xTo, t); 
            var y = Utils.lerp(params.yFrom, params.yTo, t); 
            var alpha = Utils.lerp(params.alphaFrom, params.alphaTo, t); 
 
            context.font         = (params.bold ? 'bold ' : '') + size + 'px ' + params.font; 
            context.fillStyle    = params.color; 
            context.textBaseline = 'middle'; 
            context.textAlign    = 'center'; 
            context.globalAlpha  = alpha; 
            context.fillText(params.text, x, y); 
            context.globalAlpha  = 1; 
        }, 
        //  executes a function at the end of animation period 
        exec : function(t, fn) { 
            if (t === 1) { 
                fn(); 
            } 
        }, 
        //  empty "spin doing nothing" animation 
        wait : function(t) { 
        } 
    }; 
    //  create an animation sequence 
    function createAnim() { 
        var arg, animType, duration, param; 
        var anim = new AnimSequence(); 
        for (var i = 0, nArg = arguments.length; i < nArg; i++) { 
            arg = arguments[i]; 
            animType = arg[0]; 
            duration = arg[1]; 
            param = arg[2]; 
            anim.add(AnimFunctions[animType], duration, param);    
        } 
        return anim; 
    } 
    //  play the "game is won" scene 
    function playFinalScene(cardID) { 
        var xCenter = 190; 
        anims = [ 
            createAnim(['wait', 1000], ['text', 500, { 
                text: 'This is it.', 
                color: '#5F5B60', alphaTo: 0.8, 
                yFrom: 30, xFrom: 400, xTo: xCenter, 
                sizeFrom: 50 
            }]), 
            createAnim(['wait', 2000], ['text', 700, { 
                text: 'the language wars', 
                color: '#735551', 
                yFrom: 75, xFrom: -200, xTo: xCenter, 
                sizeFrom: 30 
            }]), 
            createAnim(['wait', 2700], ['text', 1000, { 
                text: 'ARE OVER.', 
                color: '#81878C', 
                xFrom: xCenter, yTo: 120, 
                sizeFrom: 0, sizeTo: 40 
            }]), 
            createAnim(['wait', 5000], ['text', 1500, { 
                text: 'and the winner is...', 
                color: '#B2A89B', 
                xFrom: 500, xTo: xCenter, yFrom: 160, 
                sizeFrom: 30 
            }]), 
            createAnim(['wait', 6500], ['text', 5000, { 
                text: getCardInfo(cardID).name, 
                color: '#D91122', 
                xFrom: -100, xTo: xCenter, yFrom: 210, 
                sizeFrom: 0, sizeTo: 55 
            }]), 
            createAnim(['exec', 10000, function () { 
                var winnerURL = Utils.$('winnerURL'); 
                winnerURL.style.visibility = 'visible'; 
                winnerURL.href = getCardInfo(cardID).url; 
            }]) 
        ]; 
    } 
    //  process the "card clicked" event 
    function clickCard(cardIdx) { 
        var card = cards[cardIdx]; 
        if (prevIdx === -1) { 
            //  no cards are flipped yet 
            prevIdx = cardIdx; 
            card.anim = createAnim(['flip', FLIP_TIME, card.id]); 
            card.id = -card.id; 
        } else { 
            var prevCard = cards[prevIdx]; 
            if (Math.abs(card.id) === Math.abs(prevCard.id)) { 
                //  animation for the already flipped card: wait and dissolve 
                prevCard.anim = 
                    createAnim(['pose', FLIP_TIME, prevCard.id], 
                               ['hide', HIDE_TIME, prevCard.id]); 
                //  animation for the current card: flip and dissolve 
                card.anim = 
                    createAnim(['flip', FLIP_TIME, card.id], 
                               ['hide', HIDE_TIME, -card.id]); 
                //  animation of the flying card caption 
                anims = [createAnim(['text', 2000, { 
                    text: getCardInfo(card.id).name, 
                    alphaFrom: 1, alphaTo: 0.01, 
                    sizeFrom: 10, sizeTo: 300}], ['wait'])]; 
                var cardID = card.id; 
                prevCard.id = card.id = 0; 
                if (Utils.every(cards, function (card) { return (card.id === 0); })) { 
                    //  all matches are found, show the final scene animation 
                    playFinalScene(cardID); 
                } 
            } else { 
                //  animation for the already flipped card: wait and flip back  
                prevCard.anim = 
                    createAnim(['pose', FLIP_TIME + SHOW_TIME, prevCard.id], 
                               ['flip', FLIP_TIME,  prevCard.id], 
                               ['pose', undefined, -prevCard.id]);                    
                //  animation for the current card: flip, wait, flip back  
                card.anim = 
                    createAnim(['flip', FLIP_TIME,  card.id], 
                               ['pose', SHOW_TIME, -card.id], 
                               ['flip', FLIP_TIME, -card.id], 
                               ['pose', undefined,  card.id]); 
                prevCard.id = -prevCard.id; 
                setNumMisses(numMisses + 1); 
                } 
            prevIdx = -1; 
        } 
    } 
    //  reset the game board into the initial state 
    function resetGame() { 
        var ids, i, idx1, idx2; 
 
        //  generate a random subset of card variations 
        ids = []; 
        for (i = CARDS_NUM_VARIATIONS - 1; i >= 0; i--) ids[i] = i + 1; 
        Utils.shuffleArray(ids); 
        cards = []; 
 
        for (i = numCardsW*numCardsH - 1; i >= 0; i--) { 
            cards[i] = { 
                id   : -ids[Math.floor(i/2)], 
                anim : createAnim(['pose']) 
            } 
        } 
        Utils.shuffleArray(cards); 
 
        //  cache the card positions 
        for (i in cards) { 
            cards[i].x = (i%numCardsW)*CARD_W; 
            cards[i].y = Math.floor(i/numCardsW)*CARD_H; 
        } 
 
        setNumMisses(0); 
        anims = []; 
        prevIdx = -1; 
 
        playFlashCards(); 
        Utils.$('winnerURL').style.visibility = 'hidden'; 
    } 
    //  update/draw the game board 
    function updateBoard () { 
        var i; 
        context.drawImage(bgImage, 0, 0); 
        for (i in cards) { 
            var card = cards[i]; 
            card.anim && card.anim.update(FRAME_TIME, card); 
        }    
        for (i in anims) { 
            anims[i] && anims[i].update(FRAME_TIME); 
        }      
    } 
    //  update the miss counter 
    function setNumMisses(num) { 
        numMisses = num; 
        Utils.$('attemptsCounter').innerHTML = numMisses; 
    } 
    //  mouse click handler 
    function onMouseClick(x, y) { 
        var cardIdx = Math.floor(x/CARD_W) + numCardsW*Math.floor(y/CARD_H); 
        var card = cards[cardIdx]; 
        if (canInteract && card && (cardIdx !== prevIdx) && (card.id !== 0)) { 
            clickCard(cardIdx); 
        } 
    } 
    function getCardInfo(cardID) { 
        var cardIdx = Math.abs(cardID) - 1; 
        var a = Utils.$('links').children[cardIdx]; 
        return {name:a.innerHTML, url:a.href}; 
    } 
 
    return { 
        init : init 
    } 
}(); 
 
//  helper utility functions 
var Utils = { 
    //  randomly shuffles the array using Fisher-Yates algorithm 
    shuffleArray : function (arr) { 
        for (var i in arr) { 
            var k = Math.floor(Math.random()*i); 
            var val = arr[k]; 
            arr[k] = arr[i]; 
            arr[i] = val; 
        } 
    }, 
    //  returns true if all elements of the array satisfy the given predicate 
    every : function (arr, predicate) { 
        for (var i in arr) { 
            if (!predicate(arr[i])) return false; 
        } 
        return true; 
    }, 
    //  linear interpolation between a and b with factor t 
    lerp : function (a, b, t) { 
        return a + t*(b - a); 
    }, 
    //  append parameters in "params" with default values from "defaults" 
    setDefaults : function (params, defaults) { 
        for (var i in defaults) { 
            if (params[i] == undefined) { 
                params[i] = defaults[i]; 
            } 
        } 
    }, 
    //  poor man's jQuery 
    $ : function (id) { 
        return document.getElementById(id); 
    } 
} 
 
// a simple class representing a list of animations played in sequence 
AnimSequence = function () { 
    this.anims = []; 
    this.curAnim = 0; 
    this.curTime = 0; 
}; 
AnimSequence.prototype.add = function (updateFn, duration, startParam) { 
    this.anims.push({updateFn: updateFn, duration: duration, startParam: startParam}); 
}; 
AnimSequence.prototype.update = function (dt, updateParam) { 
    var anim = this.anims[this.curAnim]; 
    this.curTime += dt; 
    if (anim.duration && this.curTime >= anim.duration) { 
        anim.updateFn(1, anim.startParam, updateParam); 
        if (this.curAnim < this.anims.length - 1) { 
            this.curTime = 0; 
            this.curAnim++; 
        } 
    } else { 
        anim.updateFn(anim.duration && this.curTime/anim.duration, 
            anim.startParam, updateParam); 
    } 
};

That's what happens when you give a keyboard to a cat.

Of course, the cat ran the program through JSLint, and it hurt his feelings.

And that was it.

Loot drop and other epic problems of probability theory

2011-04-15T10:18:00.000-07:00

One day my old friend called me and asked if I could give a hand in solving some school math problems (he was trying to tutor his nephew).

Among the problems was:

The factory produces some parts. Given that from every 60 parts 12 are defective, find the probability that from 10 parts at least two are defective.

Frankly, the solution did not occur immediately at all - it's been a while since the student years.

What did occur to me immediately, though, is that something is wrong with the way people are usually taught those things at school. There are often troubles remembering them afterwards. Why?..

Apparently, one of the reasons is that the problems which students are asked to solve are usually plain boring.

Why would I care about those "defective parts", indeed?...

Now, the funny part is that it has nothing to do with the mathematical apparatus at hand (which is the thing we are supposed to learn): being abstract as it is, it can be applied to many practical problems. And some of them might appear more interesting than others, depending on the context.

For example, what about:

Two friends are playing World of Warcraft. They agreed to group for farming a boss, who drops a certain epic loot with a chance of 20%. What are the odds that after killing it 10 times both friends would get the desired epic gear?

See what I have done here?.. It is exactly the same problem. Except now it's better flavoured, and furthermore, it's actually a problem of practical interest to people playing WoW.

And something makes me feel that there are more young people playing WoW these days than those making defective parts at factories!

So, here's the (interactive) answer to the problem. Try entering different numbers and pressing the "Recompute" button (keep in mind that the code here does not attempt to be too robust with the boundary cases... also, values might be rounded, so 99.999999% will be shown as 100%, which is not correct):

With the loot drop chance of %, the odds of getting at least drop(s) after attempts are 0.012%.

It is computed by substituting values into a somewhat intimidating formula:

Here n is the total amount of boss kills, p is the loot drop chance and x is the minimal desired amount of drops we can get.

The mentioned article uses particular case of this formula, when x is 1 (i.e. when we want to know the chance that the item drops at least once):

Alright, but this is an answer, not a solution!

However, chances are that it is almost the implied solution to the original problem about the defective parts: the student is supposed to identify the Bernoulli process (AKA "repeated coin flipping"), remember that the number of successes in a given amount of trials has a binomial distribution, and use cumulative distribution function formula for that.

But this brings another problem with education: we are tought more about "what's" (facts and answers), than of "why's" (motivation and solutions). Resorting to just memoizing the formulas is not too reliable from the point of view of problem solving abilities.

So, let's try to unlearn all that again and start from the beginning.

Step 1

First, let's treat all our probabilities as being in the range [0, 1], not in percents (converting back and forward is just about multiplication/division by 100%).

One fundamental formula to consider is:

Here P(A) means "probability that event A happens", and P(not A) means "probability that event A does not happen".

The chance of loot drop is 0.2 (which corresponds to 20%). What is the chance that there will be no loot drop?

The answer is 0.8 (1 - 0.2, using the formula).

Step 2

The chance that two independent events A and B would happen both is:

The boss can drop the epic sword with 0.1 chance. What is the chance to kill the boss two times, and both times to get the sword?

The answer is 0.01 (0.1*0.1). We want both of the idependent events (sword drops) happen.

Step 3

One more basic formula from probability theory: if events A and B are mutually exclusive (either of them can happen, but not both together), then:

The boss can drop one of two items: an epic sword (0.1 chance) or an epic shield (0.2 chance). What is the chance to get either of them?

The answer, according to the formula, is 0.3 (0.1 + 0.2). The two possible loot drop scenarios are mutually exclusive.

This is a special case of the so-called addition law of probability.

Step 4

Back to the serial boss kills.

The boss can drop an epic sword with 0.2 chance. What is the chance for the two friends to kill the boss 10 times, and get the sword exactly twice, and do that during the last two kills?

Here's how this scenario does look like:

Using the knowledge from steps 1 and 2, we find that the answer is (0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.2)*(0.2), or in general form: We've got n events here, they are all independent, and should all happen together (thus we have a product of probabilities).

Step 4

The boss can drop an epic sword with 0.2 chance. What is the chance for the two friends to kill the boss 10 times, and get the sword exactly twice?

Notice that now we actually don't care if that loot necessarily drops exactly during the last two kills. As long as it manages to drop exactly twice during the total 10 kills - we're good. Which means there are more possible scenarios which satisfy our needs:

The total amount of such scenarios is C(n, k), which is called binomial coefficient (the number of distinct k-element subsets of n-sized set): We won't go into details of this particular formula this time, but here's a really nice and intuitive explanation.

Remembering the step 3, and the fact that all of the scenarios are mutually exclusive (if one scenario happens, another one can not happen anymore), and we want any of them happen (Scenario1 or Scenario2 or ...), the answer is:

This is so-called probability mass function of binomial distribution.

Step 5

In the original problem, we don't want the loot drop happen exactly twice. It's rather at least twice (indeed, I bet nobody would mind if the loot actually drops 2, 3 or even all 10 times, which is also theoretically possible).

But first let's look at a slightly modified problem:

Two friends are playing World of Warcraft. They agreed to group for farming a boss, who drops a certain epic loot with a chance of 0.2. What are the odds that after killing it 10 times the gear will drop less than 4 times?

"Less than 4 times" means: "exactly 3 times or exactly 2 times or exactly once or not at all".

So it's essentially a sum of formulas from the step 4:

There is a name for this one, it's called cumulative distribution function.

We are interested in the loot dropping "at least 2 times", not "less than 2 times", so simply take that formula and apply the step 1, giving us the final result:

Now this formula looks much less intimidating, and actually makes sense!

Isn't it amazing?..

The code

JavaScript function which computes the answer:

/**
  * Computes the chance that in given amount of attempts the loot would 
  *  drop at least desiredDrops times
  * @param {integer} attempts Total attempts at getting the loot dropped
  * @param {integer} desiredDrops The desired least amount of the actual loot drops
  * @param {number} dropChance Probability of the loot to drop
  */
function computeDesiredDropsChance(attempts, desiredDrops, dropChance) {
    return 1 - Probability.binomialCDF(desiredDrops - 1, attempts, dropChance); 
}

The probability helper functions:

var Probability = {

/**
  * Computes the sum of function values over given integer range
  * @param {integer} i0 First index value
  * @param {integer} iN Last index value
  * @param {function(integer)} fn Function with values to sum up
  * @return {number} fn(i0) + fn(i0 + 1) + ... + fn(iN)
  */
sum: function (i0, iN, fn) {
    var res = 0;
    for (var i = i0; i <= iN; i++) {
        res += fn(i);
    }
    return res;
},

/**
  * Computes the product of function values over given integer range
  * @param {integer} i0 First index value
  * @param {integer} iN Last index value
  * @param {function(integer)} fn Function with values to multiply
  * @return {number} fn(i0)*fn(i0 + 1)* ... *fn(iN)
  */
product: function (i0, iN, fn) {
    var res = 1;
    for (var i = i0; i <= iN; i++) {
        res *= fn(i);
    }
    return res;
},

/**
  * Computes binomial coefficient (the number of distinct k-element 
  *  subsets of n-sized set).
  *
  * Note that we use the multiplicative formula, as opposed to the 
  *  standard n!/(k!(n-k)!) one,in order to improve robustness/efficiency.
  * (http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula)
  * @param {integer} k Subset size
  * @param {integer} n Set size
  * @return {number} The binomial coefficient, C(n, k)
  */
binomialCoefficient : function (k, n) {
    return Probability.product(1, k, function(i) { 
        return (n - (k - i))/i; 
    });
},

/**
  * Probability mass function for binomial distribution
  * http://en.wikipedia.org/wiki/Binomial_distribution
  * @param {integer} k Amount of successes
  * @param {integer} n Amount of trials
  * @param {number} p Probability of success
  * @return {number} Probability that amount of successes in Bernoulli 
  * experiment with n trials is exactly k
  */
binomialDistribution : function (k, n, p) {
    return Probability.binomialCoefficient(k, n)*
        Math.pow(p, k)*Math.pow(1 - p, n - k);
},

/** 
  * Cumulative distribution function 
  *  http://en.wikipedia.org/wiki/Cumulative_distribution_function
  * @param {integer} x Upper bound value
  * @param {function(integer)} pFn Probability mass function 
  * @return {number} Probability that random value with 
  *     probability mass function pFn is smaller or equal to x
  */
CDF: function (x, pFn) {
    return Probability.sum(0, x, pFn);
},

  /** 
  * Cumulative distribution function for binomial distribution
  * @param {integer} x Upper bound value
  * @param {integer} n Amount of trials
  * @param {number} p Probability of success
  * @return {number} Probability that amount of successes 
  *     in Bernoulli experiment with n trials is less or equal to x
  */
binomialCDF : function (x, n, p) {
    return Probability.CDF(x, function(i) { 
        return Probability.binomialDistribution(i, n, p); 
    });
}

}

Some final notes

While it's not too relevant to the main point here, we've still made a bunch of assumptions about how the loot dropping mechanism may work.

One of them is that we can use the Bernoulli process to model the loot drops.

In simple words, it means that outcome of the previous boss kills are not connected in any way to the outcomes of all the next boss kills.

It may be the case in WoW (after all, it's the most simple/efficient model from the implementation point of view), in practice the loot dropping code could be more complex than that, i.e. the history of the loot drops could have been taken into account.

For example, the code could make sure that those two friends would have 100% guarantee/satisfaction to get their loot after 10 boss kills.

But that's a totally different story.

P.S.

Just to be clear: the point is not about World of Warcraft making things interesting.
It's rather about how cognition is related to empathy, and how academia could exploit that.

9 of 10 guys are jerks. What is the chance that after dating 5 guys you'd meet the one who's not a jerk?

Hexagonal grid math

2011-02-15T01:47:00.000-08:00

Uniform hexagonal grid is a recurring pattern in computer games and graphics applications.

There are few operations one might need to perform:

finding hexagon's position by its index in the grid;
picking a hexagon by mouse;
finding neighbor cells;
finding hexagon's corner coordinates etc.

While these things do not appear hard at all (something like primary school-level geometry/arithmetics), it's not as straightforward as with a rectangular grid, hovewer.

Having tried to consult with internets I've found a neat article on CodeProject, which was solving exactly the problems mentioned. It's considerably highy rated, which I guess means that this stuff is indeed in demand.

What have confused me, though, is that presented solution (and code) seemed to be more complex than one could expect:

hexagon positions are found iteratively, based on the previously computed positions;
a bunch of corner cases are treated in the process;
a whole lot of state is stored for each hexagon;
there is a separate codepath for the alternative hexagon orientation mode (aka "pointy" orientation), which interwines with the main one;
to pick a hexagon by mouse, the code iterates on the array of hexagons, and performs generic "point-in-polygon" test for each, using stored corners' coordinates.

Can we do any simpler?..

Hexagonal grid properties

Let's examine the geometric properties of a hexagon and define some constants:

We define the hexagon by its radius R, and find some other parameters based on it, such as W ("width"), S ("side") and H ("height").

Now, let's examine the hexagonal grid itself:

Finding hexagon position by its array index

From that picture one can figure out the formula for finding position of the top left corner of a hexagon cell by its array index (i, j):

Taking into account that for odd columns i%2 (remainder from division of i by 2) equals 1, and for even columns it equals 0, we can rewrite it:

Finding hexagon index by a point

Another operation is to find the hexagon array index from a point coordinates on the screen, which is used for mouse picking.

Let's start from the observation that hexagonal grid can be completely covered by the set of rectangular tiles (of width S and height H). They are drawn as green rectangles with purple triangular insets in the picture above. Each tile overlaps with three hexagons.

Finding which of those tiles our picking point gets into is not too hard: Here (it, jt) are the column/row of the rectangular tile picked by the point. Those fancy brackets is a floor operation.

Coordinates of the point inside the tile are: After we have all this, now we can find which one of the three possible hexagons corresponds to our point. For that we zoom into the rectangular cell's coordinate system and build a plot of the separating line (the fat red line in the picture). Its function is xt=R|0.5-yt/H|, and for all the points above the line (they fall into the green area) we have that xt>R|0.5-yt/H|.

For all the other points inside the rectangle, we have to pick either top or bottom hexagon to the left. This is decided based on value of yt.

Aditionally, we have to mind the odd/even rows indexing difference (as rows in the hexagon array go in zigzag pattern).

Putting it all together, the final array indices of the picked hexagon are:

The "pointy" grid orientation

So far we've been only considering the "flat" grid orientation (i.e. hexagons are "lying" on their sides).

What happens if we want to have the alternative orientation, when hexagons are oriented corners upwards, should we rewrite all the formulas?..

One simple observation about the "pointy" orientation is that one can get it by mirroring the "flat" one around the diagonal axis.

The direct consequence of this is that all the calculations for the "pointy" case can be performed by:

swapping the input coordinates (i.e. "mirror" them around the diagonal): x<->y or i<->j;
applying the formulas as described above;
swapping the output coordinates back ("unmirroring" them): i<->j, x<->y.

The operation is quite straightforward to do in code (as opposed to having a separate codepath for each case), I am leaving it as an exercise to the reader.

The code

Here's an example Java code, which has the formulas implemented:

package com.rush;

/**
 * Uniform hexagonal grid cell's metrics utility class.
 */
public class HexGridCell {
    private static final int[] NEIGHBORS_DI = { 0, 1, 1, 0, -1, -1 };
    private static final int[][] NEIGHBORS_DJ = { 
            { -1, -1, 0, 1, 0, -1 }, { -1, 0, 1, 1, 1, 0 } };

    private final int[] CORNERS_DX; // array of horizontal offsets of the cell's corners
    private final int[] CORNERS_DY; // array of vertical offsets of the cell's corners
    private final int SIDE;

    private int mX = 0; // cell's left coordinate
    private int mY = 0; // cell's top coordinate

    private int mI = 0; // cell's horizontal grid coordinate
    private int mJ = 0; // cell's vertical grid coordinate

    /**
     * Cell radius (distance from center to one of the corners)
     */
    public final int RADIUS;
    /**
     * Cell height
     */
    public final int HEIGHT;
    /**
     * Cell width
     */
    public final int WIDTH;

    public static final int NUM_NEIGHBORS = 6;

    /**
     * @param radius Cell radius (distance from the center to one of the corners)
     */
    public HexGridCell(int radius) {
        RADIUS = radius;
        WIDTH = radius * 2;
        HEIGHT = (int) (((float) radius) * Math.sqrt(3));
        SIDE = radius * 3 / 2;

        int cdx[] = { RADIUS / 2, SIDE, WIDTH, SIDE, RADIUS / 2, 0 };
        CORNERS_DX = cdx;
        int cdy[] = { 0, 0, HEIGHT / 2, HEIGHT, HEIGHT, HEIGHT / 2 };
        CORNERS_DY = cdy;
    }

    /**
     * @return X coordinate of the cell's top left corner.
     */
    public int getLeft() {
        return mX;
    }

    /**
     * @return Y coordinate of the cell's top left corner.
     */
    public int getTop() {
        return mY;
    }

    /**
     * @return X coordinate of the cell's center
     */
    public int getCenterX() {
        return mX + RADIUS;
    }

    /**
     * @return Y coordinate of the cell's center
     */
    public int getCenterY() {
        return mY + HEIGHT / 2;
    }

    /**
     * @return Horizontal grid coordinate for the cell.
     */
    public int getIndexI() {
        return mI;
    }

    /**
     * @return Vertical grid coordinate for the cell.
     */
    public int getIndexJ() {
        return mJ;
    }

    /**
     * @return Horizontal grid coordinate for the given neighbor.
     */
    public int getNeighborI(int neighborIdx) {
        return mI + NEIGHBORS_DI[neighborIdx];
    }

    /**
     * @return Vertical grid coordinate for the given neighbor.
     */
    public int getNeighborJ(int neighborIdx) {
        return mJ + NEIGHBORS_DJ[mI % 2][neighborIdx];
    }

    /**
     * Computes X and Y coordinates for all of the cell's 6 corners, clockwise,
     * starting from the top left.
     * 
     * @param cornersX Array to fill in with X coordinates of the cell's corners
     * @param cornersX Array to fill in with Y coordinates of the cell's corners
     */
    public void computeCorners(int[] cornersX, int[] cornersY) {
        for (int k = 0; k < NUM_NEIGHBORS; k++) {
            cornersX[k] = mX + CORNERS_DX[k];
            cornersY[k] = mY + CORNERS_DY[k];
        }
    }

    /**
     * Sets the cell's horizontal and vertical grid coordinates.
     */
    public void setCellIndex(int i, int j) {
        mI = i;
        mJ = j;
        mX = i * SIDE;
        mY = HEIGHT * (2 * j + (i % 2)) / 2;
    }
    
    /**
     * Sets the cell as corresponding to some point inside it (can be used for
     * e.g. mouse picking).
     */
    public void setCellByPoint(int x, int y) {
        int ci = (int)Math.floor((float)x/(float)SIDE);
        int cx = x - SIDE*ci;

        int ty = y - (ci % 2) * HEIGHT / 2;
        int cj = (int)Math.floor((float)ty/(float)HEIGHT);
        int cy = ty - HEIGHT*cj;

        if (cx > Math.abs(RADIUS / 2 - RADIUS * cy / HEIGHT)) {
            setCellIndex(ci, cj);
        } else {
            setCellIndex(ci - 1, cj + (ci % 2) - ((cy < HEIGHT / 2) ? 1 : 0));
        }
    }
}

Testing the code

To test the code I've written a small Java applet.

It's a hexagonal version of the game called "Lights Out" (the idea of which I've borrowed from here).

One starts the game with all the "lights" on (all the hexagons are yellow), and the goal is to switch all of them off (so all the hexagons become gray).

Whenever user clicks on a hexagon, it toggles its light, together with all the neighbor hexagons.

package com.rush;

import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;

import javax.swing.JFrame;
import javax.swing.JOptionPane;

/**
 * Example applet which uses hexagonal grid. It's a hexagonal version of the
 * "lights out" puzzle game: http://en.wikipedia.org/wiki/Lights_Out_(game)
 */
public class HexLightsOut extends Applet implements MouseListener {
    private static final long serialVersionUID = 1L;

    private static final int BOARD_WIDTH = 5;
    private static final int BOARD_HEIGHT = 4;

    private static final int L_ON = 1;
    private static final int L_OFF = 2;

    private static final int NUM_HEX_CORNERS = 6;
    private static final int CELL_RADIUS = 40;

    //  game board cells array
    private int[][] mCells = { {    0, L_ON, L_ON, L_ON,    0 }, 
                               { L_ON, L_ON, L_ON, L_ON, L_ON }, 
                               { L_ON, L_ON, L_ON, L_ON, L_ON },
                               {    0,    0, L_ON,    0,    0 } };

    private int[] mCornersX = new int[NUM_HEX_CORNERS];
    private int[] mCornersY = new int[NUM_HEX_CORNERS];

    private static HexGridCell mCellMetrics = new HexGridCell(CELL_RADIUS);

    @Override
    public void init() {
        addMouseListener(this);
    }

    @Override
    public void paint(Graphics g) {
        for (int j = 0; j < BOARD_HEIGHT; j++) {
            for (int i = 0; i < BOARD_WIDTH; i++) {
                mCellMetrics.setCellIndex(i, j);
                if (mCells[j][i] != 0) {
                    mCellMetrics.computeCorners(mCornersX, mCornersY);

                    g.setColor((mCells[j][i] == L_ON) ? Color.ORANGE : Color.GRAY);
                    g.fillPolygon(mCornersX, mCornersY, NUM_HEX_CORNERS);
                    g.setColor(Color.BLACK);
                    g.drawPolygon(mCornersX, mCornersY, NUM_HEX_CORNERS);
                }
            }
        }
    }

    @Override
    public void update(Graphics g) {
        paint(g);
    }

    /**
     * Returns true if the cell is inside the game board.
     * 
     * @param i cell's horizontal index
     * @param j cell's vertical index
     */
    private boolean isInsideBoard(int i, int j) {
        return i >= 0 && i < BOARD_WIDTH && j >= 0 && j < BOARD_HEIGHT
                && mCells[j][i] != 0;
    }

    /**
     * Toggles the cell's light ON<->OFF.
     */
    private void toggleCell(int i, int j) {
        mCells[j][i] = (mCells[j][i] == L_ON) ? L_OFF : L_ON;
    }

    /**
     * Returns true if all lights have been switched off.
     */
    private boolean isWinCondition() {
        for (int j = 0; j < BOARD_HEIGHT; j++) {
            for (int i = 0; i < BOARD_WIDTH; i++) {
                if (mCells[j][i] == L_ON) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Resets the game to the initial position (all lights are on).
     */
    private void resetGame() {
        for (int j = 0; j < BOARD_HEIGHT; j++) {
            for (int i = 0; i < BOARD_WIDTH; i++) {
                if (mCells[j][i] == L_OFF) {
                    mCells[j][i] = L_ON;
                }
            }
        }
    }

    @Override
    public void mouseReleased(MouseEvent arg0) {
        mCellMetrics.setCellByPoint(arg0.getX(), arg0.getY());
        int clickI = mCellMetrics.getIndexI();
        int clickJ = mCellMetrics.getIndexJ();

        if (isInsideBoard(clickI, clickJ)) {
            // toggle the clicked cell together with the neighbors
            toggleCell(clickI, clickJ);
            for (int k = 0; k < 6; k++) {
                int nI = mCellMetrics.getNeighborI(k);
                int nJ = mCellMetrics.getNeighborJ(k);
                if (isInsideBoard(nI, nJ)) {
                    toggleCell(nI, nJ);
                }
            }
        }
        repaint();

        if (isWinCondition()) {
            JOptionPane.showMessageDialog(new JFrame(), "Well done!");
            resetGame();
            repaint();
        }
    }

    @Override
    public void mouseClicked(MouseEvent arg0) {
    }

    @Override
    public void mouseEntered(MouseEvent arg0) {
    }

    @Override
    public void mouseExited(MouseEvent arg0) {
    }

    @Override
    public void mousePressed(MouseEvent arg0) {
    }
}

The source is also available on github.

The applet in action can be seen here (all the usual java applet related disclaimers apply).

UPDATE: Ferris Thomas made an ActionScript 3 port of the code, kudos for that!

Additional thanks to Ruurd for spotting typos in the formulas.

A cute quick colorpicker

2010-12-06T10:02:00.000-08:00

Declarative user interface programming is slowly becoming a mainstream, being backed by technologies like WPF, JavaFX, Flex and others.

And now Qt is catching up with Qt Quick and QML.

While the basic ideas behind it are pretty similar to what we've already seen in those other technologies, there are several things which potentially can make it stand out, not the last one being the fact that Qt is open-source and multi-platform and that Qt Quick is naturally built on top of the solid, tried and true Qt Framework.

There is hardly a better way of getting the impression of some technology than just trying to make something functional with it, struggling your way through the documentation/examples and counting the number of hoops to jump through in the process.

So let's try and make a simple QML colorpicker control from scratch, just for the hell of it.

The first step is, obviously, downloading and installing Qt SDK (at the time of writing it was Qt Creator 2.0.1 with Qt Libraries 4.7.0). Run it and create a new QML project, named "colorpicker" (File-> New File or Project... -> Qt Quick Project -> Qt Quick UI -> Choose...).

After we're done, the final code can be found here.

Act 1

Scene 0

Enter Rectangle, Gradient.

It all starts with a simple square, filled with a white-red gradient (so it does not appear completely dull).

QML script essentially descibes a hierarchy of objects, with a single root element. Every object can have nested children objects, as well as a list of property values.

That's pretty common way of specifying what the UI's logical structure is (e.g. XAML does the same thing via XML with its tags and attributes). The "is" part here is essential, because that's where "declarative" comes from (as opposed to imperative code, which describes what something "does").

We make a Rectangle as a root element, tell that its "width" and "height" properties should be 120 pixels, and it's "gradient" property (which is by default a vertical gradient, from top to bottom) is itself a Gradient object, going from "white" to "red" color (those colors are in turn described inside GradientStop objects, its children):

import Qt 4.7
Rectangle {
    width: 120; height: 120
    gradient: Gradient {
        GradientStop { position: 0.0; color: "white" }
        GradientStop { position: 1.0; color: "red" }
    }
}

Pressing Ctrl+R will open the QML Viewer window, which would show the result.

Scene 1

Enter Rotation, Anchors, Blending, Color Notation.

Now, let's try to mimic the saturation/brightness picking area appearance. For that we take our red/white square, rotate it by 90 degrees, and blend a black square on top, with a gradient alpha.

Here we use an alternate color representation, as a string in a form "#RRGGBB" or "#AARRGGBB" (where, "AA" stands for "transparency", or "alpha").

We'll stuff both rectangles as children of a common parent object, an Item, which is a base visual object type in QML (all other types, including Rectangle, derive from it). It handles basic positioning and size, and also is often used as a lookless grouping container for other objects.

We'd explicitly specify the size only for this top-level object, and for the children rectangles use the "anchors.fill" property, which means "use the same size as some other object", the other object in this case being the "parent" object (in fact, here we see the first example of the property binding in action. Besides, the "." in the property name means that property is an attached property... but let's ignore these gory details for now):

import Qt 4.7
Item {
    width: 120; height: 120
    Rectangle {
        anchors.fill: parent;
        rotation: -90
        gradient: Gradient {
            GradientStop {
                position: 0.0; color: "#FFFFFFFF"
            }
            GradientStop {
                position: 1.0; color: "#FFFF0000"
            }
        }
    }
    Rectangle {
        anchors.fill: parent
        gradient: Gradient {
            GradientStop {
                position: 1.0; color: "#FF000000"
            }
            GradientStop {
                position: 0.0; color: "#00000000"
            }
        }
    }
}

Interlude

A bevel made with rectangles.

Continuing the rectangles topic, let's make a fancy "bevel", which could serve, for example, as a border for an edit box control.

Here we have a more intense usage of anchor-properties, margins in particular. Also, borders width and color for Rectangles, as well as corner radius.

The clip: true property is used to cut away right and bottom parts of the dark ("shadow") rectangle. Note, that the outermost rectangle here is used just as a background for our "bevel":

import Qt 4.7
Rectangle {
    color: "#3C3C3C"
    width: 80; height: 35
    Rectangle {
        x: 20; y: 10
        width : 40; height : 15; radius: 2
        border.width: 1; border.color: "#FF101010"
        color: "transparent"
        anchors.leftMargin: 1; anchors.topMargin: 3
        clip: true
        Rectangle {
            anchors.fill: parent; radius: 2
            anchors.leftMargin: -1; anchors.topMargin: -1
            border.width: 1; border.color: "#FF525255"
            color: "transparent"
        }
    }
}

Scene 2

Enter Custom Properties, Property Binding, Expressions.

I guess at this point everyone should be fed up with rectangles, so let's try something else.

Circles, for example. Let's try and make a visual representation for the cursor in the saturation/brightness area of the colorpicker.

So, we'll make our circles with... correct, with Rectangles.

The QML code here is pretty similar to the "bevel" example, with a new twist: custom properties.

We add our own new property to the root Item, and call it "r" (as in "radius"):

    property int r : 8

This will behave as a regular, existing property of the object (e.g. the "width" property) would. In this case, "8" will be a default value for the radius of our cursor.

Next, let's use this new custom property to turn the child rectangle into a proper circle:

       radius: parent.r

which means "keep the radius of this rectangle the same as the value of parents r property is".

What just happened here is called property binding (AKA "data binding") and is another cornerstone in declarative UI programming.

Property binding is a mechanism which keeps the values of certain properties in sync, i.e. when one property changes its value, then the corresponding bound property will update it's value automatically.

Furthermore, this value can be transformed ("converted") on the way. In QML this is done in a simple and elegant way, by using expressions, written in JavaScript language:

width: parent.r*2; height: parent.r*2

Here it means "keep the width and height of the object equal to be a double of the parent's r property". Expressions can refer more than one property from more than one object, in which case all of them get automatically "bound".

I must admit, WPF's converters and multiple bindings look quite a bit more awkward comparing to this... anyway, here's our cursor's code:

import Qt 4.7
Item {
    property int r : 8
    x: 50; y: 50; width: 100; height: 100;
    Rectangle {
        x: -parent.r; y: -parent.r
        width: parent.r*2; height: parent.r*2
        radius: parent.r
        border.color: "black"; border.width: 2
        color: "transparent"
        Rectangle {
            anchors.fill: parent; anchors.margins: 2;
            border.color: "gray"; border.width: 2
            radius: width/2
            color: "transparent"
        }
    }
}

Scene 3

Enter IDs, Grid, Repeater, Data Models.

What about some more rectangles?.. I knew you looked forward.

This time, though, let's organize them in a checkerboard pattern.

But first, let's mention that every object in QML object tree can have it's own "identifier", specified by the id property. This identifier can be used in property binding, so properties of one object get bound to properties of another object, referenced by its identifier. Here, we'll name the root object as "root":

    id: root

Next, let's combine a Grid element, which lays out its children in a grid with the given number of rows/columns, together with a Repeater element, which creates many similar objects based on two main parameters: visual template (specified as a child of the Repeater object) and data model.

Data model, generally, is a list of data items, each of them serving as an input context to the corresponding separate object created by the Repeater. In simpler cases (such as ours) it can be just a number, specifying how many copies of the object to create. The visual template can reference the property called index, which corresponds to the order of the item in the array.

We paint all the even elements gray and all the odd elements white, assuming, for the sake of simplicity, that the number of rows in the grid is always odd:

import Qt 4.7
Grid {
    id: root
    property int cellSide: 10
    width: 110; height: 110
    rows: height/cellSide; columns: width/cellSide
    Repeater {
        model: root.columns*root.rows
        Rectangle {
            width: root.cellSide; height: root.cellSide
            color: (index%2 == 0) ? "gray" : "white"
        }
    }
}

Act 2

Scene 0

Enter MouseArea, Signals, Inline JavaScript Code

Let's add some interaction now and make a circle, draggable with the mouse. For that we'll use a MouseArea element, which handles basic mouse tracking. One of the ways it does it is by receiving signals whenever certain changes in mouse status happen.

In this case particular signals of interest are onPositionChanged and onPressed, as we want to change cursor position in both the case when user clicks with the mouse and when the mouse cursor is dragged. The code, is going to be identical in both cases, so it looks like a good idea to put it into a separate JavaScript function (which we'll call "handleMouse"). The mentioned signals pass a MouseEvent object (named "mouse") with parameters describing the mouse status change ("x" and."y" corresponding to the current mouse position in particular).

Our helper JavaScript function can reside right in the scope of the MouseArea object (which makes this a kind of "custom method" for this object, somewhat similarly tho the custom properties case we've looked into earlier).

Additionally, the standard JavaSript Math module is used to clamp the cursor position to the area of interest:

import Qt 4.7
Item {
    width: 120; height: 120
    Item {
        id: pickerCursor
        Rectangle {
            x: -10; y: -10
            width: 20; height: 20; radius: 10
            border.color: "black"; border.width: 2
        }
    }
    MouseArea {
        anchors.fill: parent
        function handleMouse(mouse) {
            if (mouse.buttons & Qt.LeftButton) {
                pickerCursor.x = Math.max(0, 
                    Math.min(width,  mouse.x));
                pickerCursor.y = Math.max(0, 
                    Math.min(height, mouse.y));
            }
        }
        onPositionChanged: handleMouse(mouse)
        onPressed: handleMouse(mouse)
    }
}

Scene 1

Enter Components, Layout

Now, let's start putting things together.

Besides of the saturation/brightness picking area, we'd also like to have a couple of vertical sliders - one for hue and one for transparency. The only difference betwen them would be a background picture. I the case of hue slider it is a gradient of colors from the rim of the color wheel, and for the alpha slider it's a good old checkerboard with a black-white gradient on top. The vertical slider can be made in exactly the same way as the draggable cursor from the previous example, except it's limited to the vertical direction.

We don't really want to copypaste around the identical code for sliders, and that's where components come into play.

Components are reusable chunks of code (most often extracted into a separate file), and they serve as building blocks for Qt Quick application.

Let's create three separate files: ColorSlider.qml (the vertical slider component, used in hue and alpha sliders), SBPicker.qml (saturation/brightness picking box, with code from the earlier examples) and Checkerboard.qml (also familiar checkerboard rectangle) and put them inside the folder named, for example, "content". Our project starts to get some structure:

Note that component file names should start from a capital letter (CamelCasing is a common idiom here), and those names will be used to reference components from other code. A QML file can reference all the components, wich have files placed in the same folder. In our case, though, in order for the root file (colorpicker.qml) to use components from the "content" folder, we add the following line:

import "content"

This makes all the components from the "content" folder available inside colorpicker.qml.

Now that we can reference ColorSlider and SBPicker components, we'd like to arrange them horizontally. For that we use QML's Row element, which does exactly that:

// colorpicker.qml
import Qt 4.7
import "content"

Rectangle {
    width: 230; height: 200
    color: "#3C3C3C"
    Row {
        anchors.fill: parent
        spacing: 3

        // saturation/brightness picker box
        SBPicker {
            id: sbPicker
            hueColor : "green"
            width: parent.height; height: parent.height
        }

        // hue picking slider
        Item {
            width: 12; height: parent.height
            Rectangle {
                anchors.fill: parent
                gradient: Gradient {
                    GradientStop { position: 1.0;  color: "#FF0000" }
                    GradientStop { position: 0.85; color: "#FFFF00" }
                    GradientStop { position: 0.76; color: "#00FF00" }
                    GradientStop { position: 0.5;  color: "#00FFFF" }
                    GradientStop { position: 0.33; color: "#0000FF" }
                    GradientStop { position: 0.16; color: "#FF00FF" }
                    GradientStop { position: 0.0;  color: "#FF0000" }
                }
            }
            ColorSlider { id: hueSlider; anchors.fill: parent }
        }

        // alpha (transparency) picking slider
        Item {
            id: alphaPicker
            width: 12; height: parent.height
            Checkerboard { cellSide: 4 }
            //  alpha intensity gradient background
            Rectangle {
                anchors.fill: parent
                gradient: Gradient {
                    GradientStop { position: 0.0; color: "#FF000000" }
                    GradientStop { position: 1.0; color: "#00000000" }
                }
            }
            ColorSlider { id: alphaSlider; anchors.fill: parent }
        }

    }
}

Scene 2

Enter TextInput, Validators, Property Aliases

What we also want to have in our colorpicker is a textbox displaying the whole color in "#AARRGGBB" string format, as well as separate numeric boxes with H, S, V and R, G, B, A values.

Those numeric boxes, again, are all lookalike, so it's a perfect candidate for a new component.

The element, which in QML is used for a simple one-line text input, is called TextInput, and it has a few properties, specific to text editing - such as if text is selectable, what is the selection color, font properties etc.

One interesting property is validator, which has a function of allowing only input of a certain type from the user. DoubleValidator, in particular, only allows floating-point numbers in a specified range and with a specified number of digits after the decimal point.

So, the NumberBox component would consist of three parts: text input, caption text (drawn to the left of the text input), and a border around the text input.

External clients are not supposed to see the internal structure of a component, for them it's a black box with an interface. Property aliases is a convenient way of wiring certain properties of component's internal objects as a part of component's interface. For example, an internal Text component, which is used to display the NumberBox's caption, can have its "text" property "routed" to the component's interface without exposing the unnecessary details to client:

    property alias  caption: captionBox.text

The final number edit box component we place into a separate file: NumberBox.qml.

//  NumberBox.qml
import Qt 4.7

Row {
    property alias  caption: captionBox.text
    property alias  value: inputBox.text
    property alias  min: numValidator.bottom
    property alias  max: numValidator.top
    property alias  decimals: numValidator.decimals

    width: 80;
    height: 15
    spacing: 4
    anchors.margins: 2
    Text {
        id: captionBox
        width: 18; height: parent.height
        color: "#AAAAAA"
        font.pixelSize: 11; font.bold: true
        horizontalAlignment: Text.AlignRight; verticalAlignment: Text.AlignBottom
        anchors.bottomMargin: 3
    }
    PanelBorder {
        height: parent.height
        anchors.leftMargin: 4;
        anchors.left: captionBox.right; anchors.right: parent.right
        TextInput {
            id: inputBox
            anchors.leftMargin: 4; anchors.topMargin: 1; anchors.fill: parent
            color: "#AAAAAA"; selectionColor: "#FF7777AA"
            font.pixelSize: 11            
            maximumLength: 10
            focus: true
            selectByMouse: true
            validator: DoubleValidator {
                id: numValidator
                bottom: 0; top: 1; decimals: 2
                notation: DoubleValidator.StandardNotation
            }
        }
    }
}

Note that this in turn uses another component, the bevel we already know: PanelBorder.qml.

And then the QML file for the details part of the colorpicker looks like this:

import Qt 4.7
import "content"
Rectangle {
    width: 100; height: 200
    color: "#3C3C3C"
    Column {
        anchors.fill: parent
        anchors.leftMargin: 4; anchors.rightMargin: 3
        height: parent.height
        spacing: 4

        // current color/alpha display rectangle
        Rectangle {
            width: parent.width; height: 30
            Checkerboard { cellSide: 5 }
            Rectangle {
                width: parent.width; height: 30
                border.width: 1; border.color: "black"
                color: "#AAFFFF00"
            }
        }

        // "#AARRGGBB" color value box
        PanelBorder {
            id: colorEditBox
            height: 15; width: parent.width
            TextInput {
                anchors.fill: parent
                color: "#AAAAAA"
                selectionColor: "#FF7777AA"
                font.pixelSize: 11
                maximumLength: 9
                focus: true
                text: "#AAFFFF00"
                selectByMouse: true
            }
        }

        // H, S, B color values boxes
        Column {
            width: parent.width
            NumberBox { caption: "H:"; value: "0.1" }
            NumberBox { caption: "S:"; value: "0.2" }
            NumberBox { caption: "B:"; value: "0.3" }
        }

        // filler rectangle
        Rectangle {
            width: parent.width; height: 5
            color: "transparent"
        }

        // R, G, B color values boxes
        Column {
            width: parent.width
            NumberBox {
                caption: "R:"; value: "255"
                min: 0; max: 255
            }
            NumberBox {
                caption: "G:"; value: "255"
                min: 0; max: 255
            }
            NumberBox {
                caption: "B:"; value: "0"
                min: 0; max: 255
            }
        }

        // alpha value box
        NumberBox {
            caption: "A:"; value: "100"
            min: 0; max: 255
        }
    }
}

We've used another layout element here, Column, which is a vertical version of Row.

Act 3

Scene 0

Enter Qt Source Code, JavaScript Modules

We have all the controls in place, and what is left is wiring them together with property binding. For that we need to have some ways of converting between QML's color values, "#AARRGGBB" text representations, as well as between hue/saturation/brighness/alpha and red/green/blue/alpha.

The original expectation was that QML would already provide the methods needed. Unfortunately, it turned to be not as straightforward. One of the problems, for example, is that when converting color value to string, the "AA" part in "#AARRGGBB" is for some reason omitted. The documentation regarding the QML color type is rather scarce at the moment.

But we have the source code, which is a kind of documentation on its own, given that one has time and desire to understand the internal workings of Qt Framework. Personally I do find this kind of looking inside the black box to be quite a useful experience, especially since Qt has generally nice code and architecture.

The source code can be conveniently browsed in the Qt Creator itself, by opening the "[QtSDK Folder]/src/src.pro" project.

Looking into the code confirms that current support for the color manipulation is indeed rather basic (not going beyond what documentation suggests), and problem with the color-to-string conversion appears to be a bug, as code does indeed just ignore the alpha component when composing the color string. Which basically leaves us on our own with the color conversion.

What we can do, however, is to write the corresponding utility functions ourselves, in a separate JavaScript file. So let's create a file named ColorUtils.js and add it to the "components" folder:

//  ColorUtils.js
//  Color manipulation utilities

//  creates color value from hue, saturation, brightness, alpha
function hsba(h, s, b, a) {
    var lightness = (2 - s)*b;
    var satHSL = s*b/((lightness <= 1) ? lightness : 2 - lightness);
    lightness /= 2;
    return Qt.hsla(h, satHSL, lightness, a);
}

//  creates a full color string from color value and alpha[0..1], e.g. "#FF00FF00"
function fullColorString(clr, a) {
    return "#" + ((Math.ceil(a*255) + 256).toString(16).substr(1, 2) +
            clr.toString().substr(1, 6)).toUpperCase();
}

//  extracts integer color channel value [0..255] from color value
function getChannelStr(clr, channelIdx) {
    return parseInt(clr.toString().substr(channelIdx*2 + 1, 2), 16);
}

There are many things which are wrong with this code, but hopefully its main purpose - to demonstrate the idea - is fulfilled.

One thing to note is that it uses Qt.hsla method, which is a built-in QML function for creating color value from hue/saturation/alpha/lightness values. As we use HSB space, not HSL, there is an additional conversion performed.

Now, to be able to use these utilities in our colorpicker.qml file, we add the following line:

import "content/ColorUtils.js" as ColorUtils

and refer to the utility functions as, e.g. "ColorUtils.hsba(hue, saturation, brightness, alpha);".

After that, we finally wire all the text in the numberboxes to the actual color value, the color in the saturation/brightness picking area to correspond to the current hue slider position, and the color/alpha display rectangle to be of the current color, which gives us the final version of colorpicker.qml.

Grand Finale

I've been fascinated with the idea of declarative user interface programming, even playing with that in a game development framework long time ago (quite ironically, my "JML" markup language from 2003 was pretty similar to QML).

The paradigm does indeed seem to improve productivity when developing user interfaces, and experience with QML in particular was that it's fun to learn and use.

There've been a few gotchas, however.

For example, I could not figure out how to emulate two-way property binding, that's why our colorpicker does not react on input in the edit boxes. While there might be an obscure way of doing this, it's not supported out of the box.

Also, the layout engine is rather flaky - e.g. margins do not seem to work as expected when using Row and Column containers, and in few cases I had to use direct property binding to simulate the desired layout behaviour.

There is no complex brushes and vector graphics, as one would see in WPF, etc.

However, there is also a plenty of strong points, which competitors lack, and those points are extremely appealing.

Let's wait and see where it moves. I sincerely hope that Qt Quick/QML will take a strong position eventually.

Learn yourself some innovation

2010-04-13T19:02:00.000-07:00

Looking at today's programmer job positions, a lot of them, along with those usual lists of funky acronyms, include a somewhat confusing line: "strong problem solving skills."

To measure "amount of experience" in any concrete technology is already a tricky business, so how does one go with such an abstract thing as "problem solving ability"?

In software development there usually are many problems to solve, and for each of them there are many possible solutions. So it's not just about finding a solution, but rather about consistently picking the right solutions from many possible (and picking the right problems, for that matter). At this point we start talking about creativity and innovation.

The question is: is it possible at all to develop such a skill, in a deliberate way? Is this a personality trait, or intuition, experience, knowledge... or all of these?..

Turns out, people were trying to answer the question for ages. Socrates, Descartes, Poincare and many more researched the topic of creativity, innovation and problem solving, looking for answers to the same question: how good ideas are born in human mind?

The particular research which I've been poking into for a while, is called "Theory of Inventive Problem Solving" (aka TRIZ). The author, Russian inventor Genrich Altshuller, having worked in a patent office (it's interesting that Einstein had similar experience) and examined thousands of technical inventions, embarked on a task of finding some common traits in all these seemingly unrelated innovative ideas.

Essentially, he was reverse-engineering - first the good technical solutions themselves, and then mental processes, which could lead to such solutions emerging as an idea in one's head. And he came up with some core principles, building them later into his methodology, which managed to become quite recognized.

As with any good and recognized methodology which goes mainstream and gets the potential to commercialize (it's claimed to have been used at Xerox, Jonson&Jonson, Ford and other industrial giants), it eventually became somewhat complex and confusing, quite often being diluted with a snake oil (must...not...mention...agile...).

However, the core principles are simple and sound.

The first step is to understand the environment (system) in which problem is being solved. This includes building a mental model of what are the actors in the system, the useful (desired) and harmful properties of the system.

Furthermore, one should try to extend the boundaries of vision and see not just the system itself, but other interacting systems. Then, going even wider and seeing macro-level ("metasystems") and micro-level ("subsystems"). And not just that - all this should also be extended in time to the past and the future.

TRIZ claims that there are certain principles of technical systems evolution, and the need of inventions stems from the fact that some parts of the system are not developed in harmony with some other parts. This tension essentially creates the problems we are trying to solve.

At this point one is supposed to understand which exactly problem is tried to be solved, and thus this problem then gets reduced to a simple model. Essential part of this is about finding so called contradiction between two certain properties (parts) of the system. Note that real-world problems usually are not that straightforward - there can be more than single conflicting pair of system properties, but it's claimed that most of the problems can be decomposed to simpler subproblems which would satisfy that duality requirement.

The next thing to realize is the exact locality of the contradiction in time and space (when and where exactly the conflict does take place) - so called operating zone.

Then, solving the problem is essentially about overcoming the contradiction, but not in just any way - while doing that one should aim for so called ideal solution.

Ideal solution is another central principle in TRIZ. What we are trying to achieve should happen "on it's own", i.e. desired new property of the system should be achieved without modifying the system at all (remember "the fastest code is the one you never run"?..)

Now, it's obviously not always possible, and in practice one would end with some kind of compromise anyway. But the point here is to build a proper mental setup, which would divert mind from aiming at compromises prematurely.

To achieve this ideal solution we try to identify existing system resources and then employ them in some way. If there is no easy way - we may try transforming them first.

Particular resources and their transformations are subject of rigorous classification in TRIZ - there are tables, guidelines, principles which are built as the result of analysis of classes of existing good solutions. Some of those may be directly applied to the the software development as well (even though I am skeptical about attempts to map all of them). But what is more important here is another (rather obvious) principle: borrow existing good ideas.

For that to happen one has to build the awareness (implicit "knowledge base") about what good software ideas are already out there. No, it's not just about Design Patterns, even though they are certainly have some place in this awareness.

This proccess has iterative nature. One should be ready to "restart" the chain of thinking in the case that particular original model does not really lead to the desired solution. In this case it means returning back to analysing the system (subsystems, metasystems) and either building a different model, or even trying to solve different problem. It's also important to constantly reflect on own thinking process and especially on the solutions which are being found.

Now, just for an example of how this kind of thinking could map to the activity of problem solving in software development world. There was this wonderful talk, "Self and Self" by David Ungar, which I highly recommend watching.

He mentions about how the idea of generational garbage collector (today used in some form in the most of modern virtual machines) visited him when solving performance problems in virtual machine of Self.

There are some parallels to observe:

Memory usage/CPU conflict during garbage collection (two useful system properties conflicting with each other)

Exploiting skewed probabilities (identify and use existing system resources)

Optimize by eliminating work (ideal solution)

Optimize what's important (operating zone)

Garbage collection should happen to free the memory, and it should not happen because it is time-consuming (contradiction)

"Generations" - birth, getting old, dying ("little fellas" method)

I dare to speculate that there is a chance that aforementioned mental devices could lead to this idea. Even though it's a pure speculation, it's still interesting.

According to the authors, TRIZ "works" because it helps to chunk the solution space and direct the mind of inventor towards good solutions, shifting the focus away from the "bad" ones.

Metaphorically, if problem solving is a game (so one is picking the "best" move out of many possible), then TRIZ is probably something like alpha-beta pruning with heuristics. It reduces the amount of solutions to examine by cutting away the whole "bad solutions branches" when searching the game tree. Essentially, "the algoritm of invention" is nothing else as an attempt to heuristically optimize the huge solution space search, which happens in human mind:

The conclusion is that in normal chess play, certain types of situation recur - certain patterns - and it is to those high-level patterns that master is sensitive. He thinks on a different level from the novice; his set of concepts is different. Nearly everyone is surprised to find out that in actual play, a master rarely looks ahead any further than a novice does - and moreover, a master usually examines only a handful of possible moves!

The trick is that his mode of perceiving the board is like a filter: he literally does not see bad moves when he looks at a chess situation - no more than chess amateurs see illegal moves when they look at a chess situation. [...] This might be called implicit pruningof the giant branching tree of possibilities. By contrast,explicit pruning would involve thinking of a move, and after superficial examination, deciding not to pursue examining any further.

Does it all mean that one can universally apply TRIZ or similar methodology to creatively solve programming problems?.. I don't really think so. Every person is unique in which mental processes work for them better.

Still, the described principles, such as: refining the problem, finding the contradiction and bending it to extreme, looking for an ideal solution and trying to employ existing resources of the system (possibly transforming them), borrowing the ideas from existing great software solutions, fighting the psychological inertia - all of them can be useful regardless.

I guess the process of developing one's own mental toolset is neverending and happens continuously through the career and life.

And this is just another tool. Who knows, maybe it will find its place.

Getting a good habit, the easy way

2010-04-02T06:23:00.000-07:00

I consider myself an extremely unorganized person, which makes me sometimes wonder what the hell am I doing being a programmer.

In software development, planning is an essential activity for getting the job done - something that I've learned the hard way - and personal traits must be essential in this regard.

However, I've also learned that some of those traits can be actually gained with a bit of effort. Specifically, when we talk about habits, there are several mind exploits, which can be used to rewire the brain.

Here's one particularly dead simple, nevertheless useful professional habit, which I managed to get during the last year: using ToDo list for everyday microplanning.

As with any good habit, there are several things which can help:

should be simple to do, non-burdened with time-wasting activities
consistent, repeatable in a simple ritual-like steps
providing positive feedback
have some triggering mechanisms
be forgiving to yourself, no giving up early because of false starts
some kind of public commitment, even artificial one, can also help

I use AbstractSpoon ToDoList (it's really nice and free but Windows-only, unfortunately... however there are many Linux alternatives - the particular application does not really matter).

There are some simple things to make its usage feel streamlined:

system-wide shortcut to toggle the application window quickly (Ctrl+Shift+T in my case)
it starts on system start and resides as an icon in the system tray
auto-saves on window losing focus
I use dropbox as a simple way to share the tasklist between different computers.

I start every working day with a simple ritual:

open ToDoList with keyboard shortcut and create the new top-level task named by the current date (e.g. "30 mar").
look at the previous day's ("29 mar") undone tasks, and either move them to the new day, or to the special "Maybe Later" top-level task.
think about what else is to be done today (usually there is some higher-level issue tracking system, such as Trac or JIRA, which already has a list of issues assigned to me and can serve as a guide), and roughly populate "30 mar" with today's goals.
look into the "Maybe Later" box and consider if there's something that can be fetched from there for this day. Also, close those of the entries there which are not actual anymore.
the current day's goals should be pretty fine-grained (I feel more or less comfortable when there are around 10 of them, doable during the working day), but it's not necessary to go into all the details now, they can be refined later, when it actually comes to doing them.
assign priorities to all the entries (10 being the highest), and they get automatically sorted, topmost being with the highest priority.
close the task list and start working on the topmost task.

During the day the shape of the list can change - and it's fine.

Some new things may pop in, in which case they get dispatched correspondingly:

if it's an urgent emergency task, then it gets right to the top of the current task list, with the highest priority.
if it is something which needs to be done, but not necessarily today, then it gets into "Maybe Later" box.
if this is just a "nice to have" kind of thing, then it gets into the special "IDEAS" box, which is located below the "Maybe Later" one.
some tasks can happen to become obsolete during the day, then they just get crossed out.

Also, priorities of the tasks can change during the day - I also consider it to be an expected phenomena.

Whenever this "popping in", or any other kind of distraction (quite usual on the working place, unfortunately) happens, there is always this magical "what was I doing" keyboard shortcut, which helps to switch the context back and focus again at the task at hand.

It did not work all that well from the first attempt, of course, but eventually I managed to get into this simple everyday rhythm and started to feel comfortable with it.

There is this inherent sense of satisfaction in seeing several things crossed out at the end of the day, and being able to answer these simple, yet important questions: "what have I done today? is there anything exceptional about it? why not, exactly?"

I believe that this manner of dispatching tasks somewhat resembles the Getting Things Done method.

There are few "buckets" of prioritized tasks, which periodically get processed, with the "short term" bucket being a list of today's tasks.

It's not exactly the same, of course. But perhaps I will try to follow the GTD method more closely, eventually.

After all, it's just another useful habit to try developing. There is no harm in trying it, and no penalty if it does not work for me.

Doing the impossible things (such as changing one's personality traits, for example) turns out to be not that hard - with a little bit of persistence and open-mindedness.

The Dragon Age of mainstream game scripting

2010-03-17T20:39:00.000-07:00

It's amazing how much depth great role-playing games can have to them. Some of the quests, which start as usual pre-canned in-game experience, can suddenly spill themselves onto higher layers of reality, sometimes in quite unanticipated ways.

I had been enjoying Dragon Age: Origins for quite a while already, before I found myself engaged into one of such meta-quests, which I'd like to tell about.

So, I went to Orzammar, the underground dwarven capital, where the "A Paragon of Her Kind" storyline subplot started to unwrap. There was quite intricate political struggle for the crown between two houses going on there, and apparently I was expected to eventually side with one of the parties.

In quite a boilerplate way, the two emissaries were giving tasks to be fullfilled in order to prove the loyalty to either of houses. Apparently, it was also anticipated by the developers that player might want to try playing both sides in a double-agent kind of way, and that's what I've tried doing...
just to find out that the whole plot got stuck into a logical deadlock, which turned out to be a bug. Of course, I did not have the recent save games to reload from (of course!), so I became disappointed and unmotivated.

Luckily, Bioware released the Dragon Age Toolkit, which any owner of the game can download and use to modify the game to his taste. It's a great move from their side to have it released, which me and I believe a lot of other people really appreciate. So, I downloaded it, installed and digged straight into the scripts trying to find the place which could be patched to allow me keep playing.

Long story short, I succeeded at hacking the game plot script and could enjoy the game again. It would be a perfect time for the happy end, perhaps, but the whole "fix the quest scripts to allow continuing playing the game" meta-quest spawned even new set of quests in different layers of reality.

The first quest was about learning how the DA Toolset works, getting insight into the tools and workflow which developers used to produce this great game, examining its strengths and weaknesses. Very useful experience.

But there was another thing, which somewhat stroke me. In the process of digging the scripts I've got the impression that the script code structure is quite a bit more complicated than it could be. The logical deadlock bug in the scripts, mentioned above, turned out to be not as surprising as one would expect, given that author had to anticipate the combinatorial explosion of all the many possible developments in the plot, and the language used for that did not seem helping much in that... and I wonder how much QA efforts and bugfixes it needed before getting into the shippable state.

This another meta-quest was about understanding the current state of higher-level game programming DSLs (aka "game scripting languages"), which in turn made me also sidetracked into such side-quests as trying to learn about the Prolog programming language, semantic networks and what else... but I digress.

In case of Dragon Age, the scripting language has a simple C-like structure, and workflow in scripts is centered around events coming from the engine and other scripts.

When it comes to the story development, scripts collaborate closely with the conversation editor, which is used to build the dialog trees (which are not actually trees, but rather DAGs, still represented in a tree view in the editor). Each branch in the dialog tree can be masked out by some global flag, as well as it can change some global flag if player picks this dialog branch in the conversation.

This leads to the following patterns:

there is a rather extensive set of global flags, related to the given storyline. Sometimes these flags can be quite complicated (e.g. "A_HAPPENED_BUT_B_HAVENT_HAPPENED_YET_AND_PLAYER_DID_C")
when flag changes (triggered by the player picking certain dialog branch or for some other reason), it fires the event. Events are handled in the scripts, in rather big switch/case blocks.
every case block can have complex and nested conditions checks, which may change other flags as the result, for example enabling/disabling some other dialog tree branches.

All in all, amount of bookkeeping-style code compared to the actual logic code seems to be incredibly high, and logic code itself is spread over different places, the code being heavy on side-effects. And it's not due to the bad coding, obviously, but rather because of the traits of the scripting language and framework itself.

It seems that one of the main criterias in picking the scripting language for game development still remains familiarity, which most of the time just means syntax familiarity.
Familiarity is considered to be important, so that designers and generally people not having "extensive programming background" can use it without much problems.

And I guess it makes sense. For example, in case of Dragon Age, majority of the scripts appear to be written by intern and fresh from the college folks (one can track the author names from the scripts themselves). Now, by no means I am trying to imply that it somehow correlates with the code quality - years of experience quite often mean nothing, and no doubt those people coming from college are brilliant. But I believe it still kind of shows the general attitude in the industry. Which is: "Game logic scripting is a beginner level, routine task".

Still, the question arises: is this really the most productive level of abstraction to work with? Could be low-level imperative manipulation with global flags and multiply nested blocks of if-then-else logic, giant case switches with side effects replaced with something which maps better into the domain area? Something, which would allow to do more complex, rich, interesting, emergent things without need focusing attention on the spaghetti logic and fighting the peculiarities of the scripting language?..

Despite all the interest, research and developments in this area, it seems that on the industrial, mainstream level, the technologies which serve as the game designer's medium for creating the high-level game playing experience, remain grossly underdeveloped. But it would be unfair to call it "the stone age", of course. It is developing, albeit slowly. And, no matter what tools are used to achieve it, in the end of the day it's the end result which matters.

Thus I dub the present as "The dragon age of mainstream game scripting".

Code opera: using Gource to watch a story of Perforce depot

2010-01-27T15:58:00.000-08:00

Gource is a neat open-source tool which allows to visualize dynamics of source code repositories, using a planar, spring-based tree layout ("balloon tree").

Showing P4 depot
Why being interested in Perforce in particular - a proprietary, non-free (and rather expensive) software?.. For a couple of reasons:
* It's quite commonly used in a big, corporate software shops (including the one I am working at), and still theoretically can be used in open software projects, for free (as in a beer)
* Gource does not seem to have an official support for it yet (it supports Git/Mercurial out of the box, and SVN/CVS via contrib Python scripts)

As an example we can check Adobe Source Libraries:

export P4PORT=stlab.adobe.com:10666
export P4USER=guest
echo "AdobeGuest" | p4 login
perl gource-p4.pl //adobe_source_libraries/ > gil.log
gource --log-format custom gil.log

(it may take a little while to gather the log file).

Another example is Jam (open-source build system) depot. This time in Windows command line:

p4 set P4PORT=public.perforce.com:1666
p4 set P4USER=anon
p4 login
perl gource-p4.pl //public/jam/src/ > jam.log
gource --log-format custom jam.log

The gource-p4.pl script looks like this:

#!/usr/bin/perl

$root = $ARGV[0];
map { my($change, $user) = $_ =~ /Change (.*) on.*by (.*?)@.*/;
    map { my($file, $act, $time) = 
            $_ =~ /$root(.*)\n.+headAction (.*)\n.+\n.+headTime (.*)\n.*/; 
        $act =~ s/edit|integrate|branch/M/; 
        $act =~ s/delete/D/; $act =~ s/add/A/; 
        $line = $time."|".$user."|".$act."|".$file."|\n";
        print $line if $file;
    } split(/\.+ depotFile /, `p4 fstat -e $change $root...`);
} reverse split(/\n+/, `p4 changes $root...`);

Granted, both examples of open-source Perforce depots visualizations do not look very exciting, because neither of them seems to be a primary development depot, and most of the commits are done by a few maintenance people.

However, I've also tried it at the company where I work, watching one-year's worth evolution of the main code branch, and that was quite insightful.

Gource also allows to supply a folder with images to be used as user portraits, which adds personality to the show, so I used that as well.

Stories in code

And I was quite amazed with what I've seen: the code tells stories.

To an outsider it might look like just a boring pictures flying around and zapping with lasers some colored circles tagged by the file names.

And generally that's the way how it is - plain boring. Boring when observed out of the context, that is.

And even if one of those flying pictures was myself, I was quite under-impressed at first.

But then small stories began to pop in my head:

"Oh yes, I remember that refactoring when part of public API was renamed and it triggered the chain reaction..."

"Here, ... Bill integrates his branch to ours"

"Oh, he found the reason for that bug everyone was puzzled about... see, three seemingly unrelated folders were changed to fix it"
"We have quite an activity of people working at the same on that clump of files, maybe we should improve modularity there?.. and then some people have to touch too many different files at once, it seems... could it be bad cohesiveness of code?"
"Yeah... there, Peter makes that commit with funny comments we laughed at all together"

"Right... Christmas. No commits, obviously... And then, see - what a rush! People fly around like crazy, apparently having a few days off was a good idea"
"And here Mark and Frank are working on that new API together... it's nice to see an activity in the unit tests' folders"

"Oh, see, John have just committed his new system there, in that new tidy bunch of files... cool stuff, he knows his job... surgical changes"

"Ah, that... such a pity we had to revert that... And now - ha-ha, see, Brandon started to fly around like crazy, such a productivity again, huh?.. What was that? A new girlfriend or something?"

And so on.

That really reminds me the topic of emergent storytelling in games, when players create their own stories and enjoy them:

Human beings like stories. Our brains have a natural affinity not only for enjoying narratives and learning from them, but also for creating them. In the same way that your mind sees an abstract pattern and resolves it into a face, your imagination sees a pattern and resolves it into a story.

Games have always had a close affinity with story-making. Adding a few lines of description to a video game or a background and artwork to an abstract board game gives dramatic context and an added sense of depth, allowing the player to create an internal narrative as the game progresses.

(from "Second Person: Role-Playing and Story in Games and Playable Media")

Here it's not a game, but rather a meta-game of a kind (it's quite ironic that this is rather a process of making a game in this particular case, because I work in a game development company). There are still quite a few parallels, it seems.

Quite frankly, Gource provides only the most basic display. It does not tell too much about the code structure and how well different areas of work are factored between different contributors (even though quite often well-though folder structure is a sign of overall good code organization).

But I can imagine even more narrative devices added, for example:

* Fetching the information from the continuous integration system and display some crazy particle explosions when build was broken

* Doing similar, but even more intense display when automatic regression tests were broken

* Integrate with bug tracker, and give some visual cues about the nature of work being done (bugs, regressions, crashes, new features)

* Visually tracking the physical code dependencies as well (like #include graphs in C++) and their evolution

I believe all this is can be useful in a practical sense as well.

It seems that entertaining things generally have bigger cognitive potential. Andy Hunt tells in "Pragmatic Thinking&Learning":

...In fact, additional studies have shown exactly that: positive emotions are essential to learning and creative thinking. Being "happy" broadens your thought processes and brings more of the brain's hardware online.
Aesthetics make a difference, whether it's an user interface, the layout of your code and comments, the choices of variable names, the arrangement of your desktop or whatever.

Nice things matter, especially if they provide a useful view, yet another mental projection upon the code base, which allows to extend one's mental models of this code in a fun, aesthetically pleasing way.

Work should not necessary be boring.

So what?..
From the practical perspective, one quite satisfying thing to me was that such generally useless one evening exercise gave me quite a bit of awareness about several (seemingly unrelated) things:

* Reading the source code of Gource (C++), compiling and running it both on Linux and Windows
* Making up somewhat artificial problem in this context (how to use it with Perforce) and figuring out what steps can be taken to solve it
* Getting to know a little bit of Perl (yes, this is my first Perl script ever... it must be quite obvious from the code, anyway), while solving a real-life problem
* Trying to do it in a (somewhat) functional programming style
* Improving my regular expressions skills
* Getting to know a bit of p4 command line interface, again while solving a real-life problem
* Getting some insight about the Adobe GIL and Perforce Jam open source code bases
* Using Gource to visualize evolution of the code base at the company where I work.
* Reflecting on it

I am certainly not sure if regular solving of such small artificial problems (and learning a few random things while doing that) make you a better developer or something.
Perhaps it does. But if it does not - who cares?..
It was fun, after all.

Boost C++ libraries and game engines

2010-01-20T17:21:00.000-08:00

There is a neat development cost calculator on the boost web site. Pretty easy to use. You enter "code only" into the "include" combo box and get your magic answer:

$188,229,523

Wow. I mean... Wow! You get almost two hundred millions for free, into your personal disposal!
Only that makes it worth including Boost into your project, whatever you develop. Right?..

If we talk game engines in particular, there is certainly no need for all the excessive functionality the Boost libraries provide.
However, there are surprisingly many parts of it, which I've seen being reimplemented in the small and big game engines over and over again (and, frankly, implemented quite a few bits of functionality myself).
Such as:

- these usually find their place in the "core" part of the game engine. Also there are more specialized parts, like:

All of these facilities (and many more) can be considered of direct use for your typical modern game engine.

Also, it's no doubt that boost code is of very high quality, tried and true, well-tested, portable and besides it is slowly moving into C++ standard. It uses template metaprogramming, which presumably in certain cases can improve efficiency due to aggressive inlining and doing some stuff at compile time. The code is also considered to be generic, so one is supposed to be able to flex it to high degrees adapting to one's own needs.

Jason Gregory in Game Engine Architecture book (in my opinion, rather good one) mentions the topic:

Boost provides a lot of useful facilities not available in STL.

In some cases, Boost provides alternatives to work around certain problems with STL's design or implementation.

Boost does a great job of handling some very complex problems, like smart pointers. (Bear in mind that smart pointers are complex beasts, and they can be performance hogs. Handles are usually preferable; see Section 14.5 for details).

Th Boost libraries' documentation is usually excellent. Not only does the documentation explain what each library does and how to use it, but in most cases it also provides an excellent in-depth discussion of the design decisions, constraints, and requirements that went into constructing the library. As such, reading the Boost documentation is a great way to learn about the principles of software design.

If you are already using STL, then Boost can serve an excellent extension and/or alternative to many STL's features. However, be aware of the following caveats:

Most of the Boost classes are templates, so all one needs in order to use them is the appropriate set of header files. However, some of the Boost libraries build into rather large .lib files and may not be feasible for use in very small-scale game projects.

While the world-wide Boost community is an excellent support network, the Boost libraries come with no guarantees. If you encounter a bug, it will ultimately be your team's responsibility to work around or fix it.

Backward compatibility may not be supported.

The Boost libraries are distributed under the Boost Library License. Read the license information carefully to be sure it is right for your engine.

But frankly, while I agree about smart pointers and documentation, there are bigger concerns usually popping up regarding Boost:

Compiling time - due to all inter-dependencies and heavy template use
Code readability
Performance (usually as a tradeoff for flexibility and safety, there are quite a few horror evidences)
Easiness of misuse and building extra complexity out from nothing
Versioning problems
Huge size of the library itself, when used as a third-party dependency

It turns out that there is still a lot of controversy regarding the very topic of using boost in games. People are quite often cautious about it, and in many cases avoid using it altogether.

Of course, it does not really come as much surprise in regards to the game industry as specific branch of software development. The mental model of your typical game engine architecture, sketched directly from my head into an (almost) UML diagram looks like this:

...which hopefully explains a lot.

Recently I've started to try porting some of five years old code to Linux, and on the quest of eradicating windows.h dependencies found out that there is a class called "FilePath", which allows to do some basic filesystem operations and uses WinApi directly.

It came into my mind that its functionality is an ad-hoc implementation of a subset of what boost::filesystem library provides. Except that the latter is portable, has more functionality, is more stable and well-documented.

There are certain biases I've got, and due to all aforementioned factors (including the NIH syndrome), the decision did not seem to be as simple to make.
Another mental model of mine has crystallized with time, and here's the sketch of it:

I remember Joe Armstrong saying in Coders at Work:

Seibel: But do you think it's really feasible to really open up all those black boxes, look inside, see how they work, and decide how to tweak them to one's own needs?

Armstrong: Over the years I've kind of made a generic mistake and the generic mistake is not to open the black box. To mentally think, this black box is so impenetrable and so difficult that I won't open it[...] But it's not actually difficult. [...] ...you should certainly consider the possibility of opening them.

Shattering the personal biases by means of opening black boxes sounds like a good plan.

So, where do all the dependencies come from?

Here's the layout of the whole boost include directory (which is roughly 50 Mb, while the whole boost directory is 200 Mb), made with StepTree:

We don't really need all of that. Luckily, there is bcp utility, which is part of boost distribution and does exactly that - it allows to strip away only the subset of code needed. So, if I am interested in boost::filesystem library:

cd boost
mkdir ../boost_fs
bcp --boost=boost filesystem.hpp boost_fs

It creates boost_fs folder, which has only the code needed to compile this particular library and use it. However, this folder is around 8 Mb, which is a bit more than could be expected (keep in mind that most of this code is header files, which most certainly are going to be included into the project). The layout looks like this (this time rendered in WinDirStat):

The boost::filesystem code itself takes just about 3%! The rest is occupied mostly by:

mpl - which is an "all-around c++ template tricks" kind of library
preprocessor - which is a library to do the copypasting job for the programmer in very smart way
type_traits - which allows to get and use some basic information about templated types in case of templated classes

Granted, code reuse is generally a good thing, and boost (having the goal of being highly reusable library itself) is known to do it heavily, cross-referencing between the libraries. But this looks a bit extreme.
Ironically, though, the development guidelines for the Boost libraries do discuss the topic of excessive library interdependencies.
Let's run again bcp in "report mode":

bcp --report filesystem.hpp fs_report.html

This generates html report file with all the dependencies gathered. At the bottom of this file there are all the include chains gathered (the file is big, mind you).
This representation is only helpful in showing that there are very many header inclusion paths starting from boost/filesystem.hpp and most of them end in either of other aforementioned boost libraries.
Let's try to build an inclusion graph using Doxygen:

sudo apt-get doxygen graphviz
cd ../boost_fs
doxygen -g
emacs Doxyfile

Then edit the file to ensure parameters are set:

HAVE_DOT = YES
RECURSIVE = YES
EXTRACT_ALL = YES

Save, and then:

doxygen Doxyfile

The part of inclusion graph for the main header, boost/filesystem.hpp look like this:

The gate to the flurry of includes seems to be opened via boost/iterator/iterator_facade.hpp, which has another graph on it's own:

Browsing these graphs on its own already starts to give some insight, but to get things even more clear we could try to inspect even different representation of the source code... the source code itself.

Doing that, it becomes more clear where do these dependencies come from. For example, there is a directory iterator, which is templated by the path type, which in fair enough, as the path can have possibly Unicode representation. Iterator classes are generic in a sense that they don't do many assumptions about the particular type uses, and thus require the general metaprogramming facilities provided by mpl and typetraits. Mpl, in turn, uses preprocessor libraries for its needs. And then there are preprocessed headers for several compilers... quite a lot of things are happening in order to provide the functionality which you actually may not need.

In this particular case there is, for example, physfs library which might suite the needs even better without providing nearly all the generic facilities as boost does.

Does it mean that there is no use for boost? Of course not:

One still can use it, but physical dependencies tracking is important even more than usual. In case of filesysem it could be wrapped with an additional interface, so as few cpp translation units as possible include boost/filesystem.hpp and the rest which is pulled in together with it.
One can also possibly take the parts of interest and "strip" them out of unneeded generic parts. Here's a good example: OgreAny.h
One can read the documentation and, most importantly, the code to borrow good practices and ideas (and to examine the "bad" ones as well).

Whatever you do, just make sure you crack the black box open first.

Programmer's arrogance graph

2010-01-11T13:29:00.000-08:00

We know that majority of programmers, even the most ingenious ones, are egotistical bastards, driven by arrogance.

Programmer's arrogance is both a blind, powerful driving force and also the reason for many failures.

For example, anecdotal evidence tells that initial programmer's estimate has to be multiplied at least twice to get the "realistic estimate":

Why are competent coders so bad at estimating? There are a number of reasons. The main ones are:

Unforeseeable problems:

Many of the problems that come up during software development are unforeseeable. If you have ever started a "simple" home improvement project and later found it was much more complicated than you realized...then you know first hand how programming can be...even for the experts.

Misunderstood/unclear requirements:

When the requirements are unclear, the programmer usually underestimates what it takes to build your software. To use an analogy, they may estimate building your software as if it were a comfortable house. Only mid-project do they realize that you were expecting the Taj Mahal!

Or they just fall a victim to their own arrogance. Which is a bit simpler explanation.
Same stands for "Not Invented Here", "Invented here but not by myself", "My co-workers are all jerks" syndromes. And many more. Oh well.

Now, I've got a theory (which is built on empirical experience, of course), that if we imagine that amount of "arrogance" can be measured with a scalar value (let's call it a "magnitude of arrogance"), and if we try to build a graph of this value changing with the lifetime of the programmer, we might get pretty similar shape in 80% of cases:

The person (remember that we talk about future programmer) starts on some level of initial arrogance as a child/teenager, goes to school where everything is very new and unknown at first (point marked as "S" on the lifeline, which is horizontal).

But then he (not being sexist, just intentionally taking only males here) suddenly realizes that he's the "smartest kid in the class". The next thing he figures out is that his programming teacher "does not know a sh*t". Besides some boring, irrelevant and ages old stuff, that is. And sure he does not have any bleeding edge knowledge about, say, patching KDE under freeBSD.

Naturally, this skyrockets the level of arrogance significantly, and it keeps fluctuating somewhere at the top until our geek graduates and gets a job ("J").

Here the arrogance might drop down slightly again, because of the things being new and not familiar.

However, being used to the "best kid in the class" status, our soon-to-become programmer quite quickly catches up.

It might happen because of initial tasks being moderately doable and initial responsibility being not quite high, so this "gee, I can do the stuff" feeling warms up the ego.

Also, when coming to a corporate environment, young programmers often get a maintenance job in some legacy codebase. Knowing the nature of (most of the) legacy code bases, one would not get surprised if quite soon our kid gets to realize the thing.

See, it happens that all these "experienced" folks out there don't know a sh*t about programming either. As Gerald M. Weinberg puts it:

We often find material in programs that is [...] really present because of the history of the development of the program. For example, once the [...] function is changed to an [...] function, there is no longer any reason for the program [...] to appear. Nevertheless, things being what they are in the programming business, it is unlikely that anyone is going to delve into a working program and modify it just because the definition of [...] function has been changed. And so, some years later, a novice programmer who is given the job of modifying this program will congratulate himself for knowing more about [the subject] than the person who originally wrote this program. Since that person is probably his supervisor, an unhealthy attitude may develop - which, incidentally, is another psychological reality of programming life which we shall have to face eventually.

Soon he realizes, though, that things do not quite work as it appeared at first. There are several failures happening, which he fortunately realizes should be blamed on himself, and he suddenly faces the understanding that he knows, in fact, nothing about his job.

Then goes a long and painful learning, getting better and better every day, and finally getting to the next level of personal development, where one can look back and say: "see, I am not nearly as lame as I used to be when I started".

So we get another boost of overconfidence, which may or may be not followed by similar, multiple and abrupt drops and consequent slow raises.

What usually happens next is the point "P".

Which is promotion to the lead position (it does not seem that there is too many ways to get "promoted" in corporate programming business without becoming a manager), or becoming an entrepreneur, or changing the working place to work in considerably more "advanced" company. You name it.

The fresh feeling of power gives another arrogance boost. It only lasts that long, though, and soon again come disappointments.

And so on.

After many bumps on the road, if being lucky, passionate, persistent and introspective, one might slowly approach the level, which is marked as "H" on the vertical axis.

Which is "The Humble Programmer", as E.W.Dijkstra puts it:

We shall do a much better programming job, provided that we approach the task with a full appreciation of its tremendous difficulty, provided that we stick to modest and elegant programming languages, provided that we respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers.

The question is how close projection of this point upon the horizontal axis will happen to be to the point "R" (retirement).

And to the point "D", which comes next.

Bees in Space, or story of my first freeware game project

2009-12-30T15:51:00.000-08:00

It was around five years ago when I decided to try making a small game project on my own and publish it on the internets as freeware.

The reason was that I wanted to experience myself a "full" game development cycle in miniature.

And for fun, of course.

Probably the end result is not such a big deal, but I've certainly enjoyed the process and learned quite a bit from it. Actually doing the things, no matter how small they appear, gives that invaluable insight into their very nature, which can not be gained otherwise. When those small, non-uniform (and often beyond the boundaries of one's present competence) things form a complete whole, a closed loop, then this insight may get even more eyes-opening.

At least that's my feeling about it, in the end.

So now, after five years I've suddenly realized that it was not that bad, after all, and it might be a good idea to reflect on that past thing. Just for fun, again.

Picking a theme
The old-school game called Hexxagon was a primary inspiration for that. It was very tempting, of course, to start something grand, like Diablo or GTAIII clone, but that would obviously defeat the whole purpose of trying to finish the game and see what happens after that.

Being as simple as it is, it still involves quite a bit of work in different areas of programming, gameplay design, user interface, art, "marketing", maintenance and support etc - even though every problem here is a toy one, as comparing to a "real-life" game project.

The Game

Essentially, it's a zero sum, deterministic two-players game, somewhat similar to othello.

In it's simplest form AI for such a game is using minimax algorithm, quite often with alpha-beta pruning optimization, to search the game tree, depth first, to a certain level (or until the time limit is reached).

There is quite a bit of research in this area, with a lot of heuristics proposed to improve the "smartness" of the evaluator and game tree search. They would be certainly interesting to try implementing, but as soon as I've got the basic minimax with alpha-beta pruning working, I decided not to bother with this for the time being.

Again, for the sake of being able to work on other things and finish the game.

The board evaluation procedure was dead simple - it was the difference between the one's and rival's balls, the bigger the better, weighted together with the possibility to move, based on some simple heuristic, details of which I don't remember.

The "board" was represented as a bitmask, wrapped by rows, with bit being set if there is something in the corresponding cell (with "something" having different meaning depending on the context), and the whole board state was represented as a triple of bitmasks: one for black balls, one for white balls, and one for empty cells.

Then the bulk of operations/queries on the board state can be conveniently/efficiently done with the bitwise operations.

This, I believe, is called "bitboards", and is quite common trick when programming similar two-player games.

The Engine
I admit that quite a bit of things here could be done in much simpler way, especially in context of such a simple task at hand.

However, in retrospective it does not look that bad. It was certainly good learning experience, and some of the engine design decisions taken seem to have saved quite a bit of time, which would be otherwise wasted doing boring and repetitive things manually and then fixing all the mistakes done in the process.

Few of the things, in no particular order:

Game-specific code was minimal and separated from the rest (an "engine" code)
The engine code itself was quite modular and layered, different layers were communicating through the interfaces (for example, widgets are using the sprite manager to display sprites, which is using the renderer interface to draw the textured quads, and the renderer interface can have separate implementations for different graphics APIs - I used to have two of them dx8 and dx9).
Sprites were packed into "packages", using custom format, every sprite was cut into power-of-two chunks in a quadtree, and then those chunks were laid out in runtime on the surfaces in the texture memory cache. There was a custom C# tool which did the packing of the sprites, and generating of the font packages as well.
A poor man c++ reflection system (using macro and template tricks) for the classes, derived from the "base game object" class, which made it possible to automatically serialize object hierarchies in text/binary format.
Custom text format for representation of the object hierarchies in "scripts". I used XML at first (because I knew that rolling your own is a sin, and XML is the answer), but it turned out to be extremely ugly and hard to edit manually. So I did roll my own (which I called JML), using flex/bison, and it turned out to be not as bad as they said.
There is a "data binding" mechanism in scripts, the idea I've borrowed from Qt back then, and then eventually Microsoft has stolen it from me and implemented in WPF :)
I've got a set of ad-hoc python scripts which would generate project files (.vcproj/.sln, .dsp/.dsw). Every module had a text file called depends.txt, which used a simple syntax to describe which other internal/external libraries it references. The python script would then walk the source tree, find these files and do the generation. This way I could experiment with different physical source code layouts and manage dependencies explicitly without tinkering for ours in Visual Studio property dialogs.

So, for example, the main menu dialog script would look like this:

dialog "MainMenu"
{
    // ...
    picture "Logo"
    {
        skinpack        = "logo";
        extents         = { 40, 30, 330, 100 };
        stretch         = true;
        skinframe       = 0;
    }

    shortcut "EditorShortcut"
    {
        Key             = "E";
        Action          = >>MenuSystem.OnEditor;
    }
        
    button "ContinueGame"
    {
        text            = L"Continue Game";
        extents         = { 290, 160, 270, 48 };
        font            = "font_menu";
        fontheight      = 48;
        fgcolor         = 0xFF49CD49;
        shadowcolor     = 0xFF11FF11;
        hoverfgcolor    = 0xFF88FF88;
        unpress         = >>MenuSystem.OnContinueGame;
        visible         = <<Core.Game.HasPlayers;
    }
    // ...
}

Design

It was obviously programmer art, from the beginning to end.

I've found a few free sound samples on the internets, painted basic game screen elements myself in gimp (that included the space bee from the main menu screen).

I've used Comic Sans MS in user interface, which is a trademark of amateurish design.The interface itself is not consistent, not intuitive, badly laid out and uses a horrible color palette.

So it's hard to call it a "design", rather an inconsistent pile of placeholders. Which I did realize back then, but again did not overfocus on that, hoping that eventually I might get a help from someone who has a taste and gets interested in this.

The Editor

I've decided to add a certain "non-linear" twist to the original Hexxagon gameplay.

The player would progress through the sequence of "levels", which get more complex in terms of the original board setup (the "smartness" of the computer opponent would still remain the same, as it is essentially the same limited depth/time minimax solution tree search). When certain level is won, it opens one or more new ones, and it's up to player to pick which one to play next.

So, it is not necessary to win all the levels in order to "beat the game". The levels form a kind of a graph with nodes being the particular board setups. And if there is an edge from a source level to destination one, it means that destination is available to play after the source is won.

While all the levels and transitions between them could perfectly be "designed" in Notepad (and probably it would be a better idea to keep it that simple), I've decided to make an "in-game" editor for those.

Which turned out to be pretty rad in the end:

One could pan, zoom the whole graph, select node groups, move them around, double click on nodes and edit them etc.

The whole game, when zoomed away, would look like a big DAG, where the leftmost node here is the starting level, and the rightmost one is the end level, which has to be won to finish the game.

Release
The testing (including the focus testing) was done by myself and my friends. The game was obviously far away from being ready, but at least it was somewhat playable, so I decided not to wait an eternity "til it's done" and publish an early version.

I used NSIS for the installer, and was quite happy with that, as the whole distributable size was below 1Mb, which was pretty good for the downloadable game.

Funny enough, I clearly remember myself not counting the things like making an installer or the game's web page as work, which has to be taken into account.

Turned out, that even with the help of such great tools like NSIS or Inno Setup (which make life much, much easier in this regard), it still took considerable amount of time, especially since I did not have much previous experience in these areas.

So that was another good lesson to learn.

Evaluation
I have submitted "version 0.4" to tucows for evaluation and basically forgot about it, because the evaluation queues are pretty long, and it can take a few months before your software gets there (well, it used to be the case five years ago, but I presume it's not very different today).

So it was quite a surprise for me to finally get my game reviewed and rated... with whooping three cows! Which according to the tucows folks themselves means:

If your application receives a three-, four-, or five-cow rating, congratulations! As you'll see by reading the Ratings Guide, this is no small feat. You are in the company of some of the best programmers in the world. We receive hundreds of requests each week for inclusion in the Tucows software library. The fact that you scored in the three-cow range or higher has earned you a spot on our site. This is a sign that your product is among the best of its kind.

See? My little game is among the best of it's kind!

Seriously, though, I've got an extremely good feedback in an e-mail soon after, where they were giving a detailed explanation about how did they evaluate the game, separately on topics of visuals, sound, fun and longevity, user interface, easiness to grasp etc.

Obviously, graphics, sound and user interface were quite far from being the strongest sides, and that was very expected.

Another weak side was perceived complexity of the game, and most of all that it is very hard for a new person to figure out what are the rules of the game and how to play in general (even though the rules are quite simple).

It was also quite expected, as I was observing it myself during my "focus tests", and was going to "fix" it in later versions by making a tutorial (quite frankly, I had to postpone it to "later versions" because it also turned out harder than I was originally expecting).

But still, I've got my three cows and that was quite a revelation.

Aftermath
Well, there is none. Soon after I've decided to change my job and move to live in another country, so it was left where it was, at version 0.4.

I did not finish the game, there were quite a bit of things to do yet, but still managed to experience one iteration of the possible game project life cycle, from beginning to what can be called "end".

It's not on tucows anymore, but still is downloadable on the internets.
I've also made the source code public, and it was available until my hosting period has ended.

But all in all, being a failure it is (i did not really finish the game, and it did not find its players), it still was a success to me personally, in the experience it has brought.

Kozma Prutkov, one of the brightest minds in the software development

2009-07-02T11:27:00.001-07:00

Alright, that's quite a stretch. Not only Kozma Prutkov is by no means a software developer (he was a writer, one and a half centuries ago), it's also not a real person (but rather three people behind a single fictional name).

The reason that he's not that well known is that it appears to be quite hard to translate his aphorisms, which are hugely based on the wordplay. Which reminds of what Douglas Hofstadter said about Gödel, Escher, Bach translation:

There were a million issues to consider in any potential translation, since the book is rife not only with explicit wordplay but also with what Scott Kim dubbed "structural puns" - passages where form and content echo or reinforce each other in some unexpected manner, and very often thanks to happy coincidences involving specific English words.

And I think it's a shame in case of Kozma Prutkov. Those little revelations, hidden in a generally tongue-in-a-cheek perls of wisdom, in some ways defined my own world-view long time ago, and I am even more amused to see how do they manage to take new forms when I return to them today.

Fortunately, some people tried to translate it, anyway.

The good thing about this kind of ambiguous and satirical aphorisms is that one is free to put into them whatever meaning he feels fits better himself.

However, in this particular case I was really impressed to discover so many empirical truisms of the software development, which can be directly mapped upon Kozma Prutkov's aphorisms.

Well, this discovery is quite a pleasant exercise on its own. People tend to get enjoyment in finding familiar patterns observing seemingly unrelated phenomenas ("We experience delight when we recognize patterns, yet we're also surprised by them").

So, I will dare to cite some of them.

To be honest, my original plan was to append my own thoughts/associations (and possibly explanatory links) triggered by these sentences. But then I understood that most of those thoughts are pretty obvious, and besides that would possibly rob some people from having a kind of enjoyment I had while discovering these associations themselves.

So for only the couple of the first ones:

Do not cut everything that grows.

If it ain't broke don't fix it

Buy a painting first, and then frame it.

You are not gonna need it

The first step of a baby is the first step to his death.

Most of the software designs are deemed to die much sooner than one would expect. But chances are that they will give a birth to the next generation, and many others after that. One has to consider it when designing the systems.

Now, I challenge you to find your own associations for the rest:

Many things are incomprehensible to us not because our comprehension is weak, but because those things are not within the frames of our comprehension.
If upon a cage of an elephant you will see a sign reading: "buffalo", do not believe your eyes.
When casting pebbles into water, look at the ripples being formed thereby. Otherwise this activity will be an empty amusement.
Never run to the extreme: who wants to dine too late today takes chances to instead breakfast tomorrow, early in the morning.
What other people can say about you if you can't say anything about yourself?
Trace everything back to the beginning and you will understand a lot.
New boots always pinch.
Nobody will embrace the unembraceable.
There is no great thing that would not be surmounted by a still greater thing. There is no thing so small that no smaller thing could fit into it.
Look in the root!
Better say little, but well.
People's memory is like a piece of white paper: sometimes it writes well, and sometimes bad.
What is the best? - Having compared the past, link it to the present.
If you have a fountain, plug it up. Let the fountain too have a rest.
Only reason on what your notions allow you to discuss. Thus, knowing nothing about the laws of the Iroquois language, can you pass a judgement on it that would not be ill-founded and stupid?
Having lied once, who will believe you?
Looking into the distance, you will see the distance; looking to the sky, you will see the sky; looking in a small mirror, you will only see yourself.
Where is the beginning of the end that comes at the end of the beginning?
Do not seek for unity in the whole, but rather in the uniformity of distinction.
We don't care for what we have, we deplore what we have lost.
Every thing is a manifestation of infinite diversity.
Who prevents you from inventing waterproof gun-powder?
When looking at the sun, squint your eyes - and you'll readily discern the spots upon it.
If all the past were present, and the present existed along with the future, who would be able to distinguish, where are the causes and where are the consequences?
Virtue is an award for itself. A man excels the virtue, if he serves never receiving an award.
The harm or benefit of an act depend on the combination of circumstances.
Things can be great or minor not only by fate's will, or contingency, but also by every person's notions.
Sometimes, zeal overcomes even the common sense.
When it concerns art, every tailor has views of his own.
People could not stop living together, even if they walked far away from each other.
If you want to be happy, be!

I'd be really happy to hear from you, and compare it with the picture in my own head.

There will be no substitute for COBOL

2009-07-01T03:00:00.000-07:00

I've bought that book quite some time ago, and only recently managed to fetch it from my bookshelf (did I already mention that I am a book junkie)?..

Being a second edition of the classic book, some kind of a new thin wrap around ten years old candy, it still manages to sound insightful in some places.

Well, that candy is not just old, it's ancient (first edition is 1990, second one is 2005)... well, at least from the perspective of everchanging software development world.

Still, I'm done through the bigger half of that, and I am not regretting doing that so far. However, there was one part which has turned out to be mind provoking in a somewhat unexpected way:

But there's something else happening here, too. With all that heavy use of COBOL in the business world, where money is to be made by cutting costs wherever possible, why haven't at least a few companies switched to something better? No, I don't mean 4GLs. I mean 3GLs that provide the same capabilities as COBOL. Why haven't the innovative, advanced firms started using a better COBOL?
Here's where I want to get to the real point of this essay. I want to take the position that people aren't switching away from COBOL because there really isn't anything better to switch to.
Heresy! Ignorance! Stupidity! I can hear the silent cries from my reading audience now. But wait, there is method in my madness, and I would like to explain.
...What other tools have been invented to address [the business] problem domain?.. That better way is still COBOL. That's the gist of my heresy.
Does that mean that I think COBOL is a good language?
Emphatically, my answer is a resounding "No."
...Why? Why is this ancient and clumsy language not replaced by something that does its job more cleanly? Because, I would assert, the research world which might create a better language is so disdainful of business application software in general, and the COBOL language in particular, that it is blind to the thought that a major research challenge lies in defining a better COBOL.

COBOL, eh?

Now, certainly, COBOL is out from the scene, and that's something Robert Glass acknowledges himself (what a surprise!) in that "special 2nd edition chapter". But that's not the point.

"COBOL" is just a label, and if one blurs it away from the picture (together with probably some other vintage things), the pattern extracted seems to be very familiar.

As it usually happens with my poor mind, when it's being provoked by something, I see a reference to several (possibly non-related) things at once:

That Deja Vu feeling one gets often when reading discussions about the present state of the technology. So, does C++ looks like COBOL in this context?..
And what about that too well known Tim Sweeney talk?..
And what is a "programming language", after all? Is it programmers' or users' thing, or maybe both?
Is really software development history developed in a spiral (pretty much like the human history)?
What is the point in developing the new "programming languages"? It seems that users do not care about languages, they prefer working software.
And what about our's today arrogance? Like in, "C++ is going to stay here for a while, because it's the most efficient language, and computer games do demand performance".
Could it be, that business value of the software is higher if users have more control over the way this software is applied to their domain?

I mean, yeah, of course. C++ is not COBOL. And Java is not COBOL. And C# is not COBOL. And F# is not COBOL.

Those are bloody modern and mainstream.

Or are they?..

Or maybe they are just an another coil of the Spiral?

What we are, then? Are we the pivot of that spiral, or just a part of a coil?

All our experience, knowledge, mental models - all of it can happen to become nothing in the long term.

So, what do we do to prevent that?

Learn COBOL, of course.

Programmer's workout

2009-06-29T15:48:00.000-07:00

There was another metaphor concerning the programmer's skills development, which I personally feel is quite sound.

We had this discussion with the fellow programmers, about learning new programming languages and technologies, and generally doing the work which is not just something that you are not really get paid for, but also you don't get any visible benefit at all from doing it. You don't produce any measurable value.

As in, for example, writing a throw-away code in some new programming language just for the sake of learning that language itself.

The notion of "throw-away code" turns out to be more painful than it could be expected: quite often people get extremely personally attached to their designs, algorithms, code, and time spent on some certain activity in general. So, how come one can even remotely be attached to the throw-away "garbage"?..

That takes different forms and flavours: one feels sorry that he had spent years in the university studying something which does not seem to help to find a job, others are reluctant to get interested in anything outside their own area of expertise ("we don't have time for that, it's not our job"). In the case of programmers, in particular, it often turns out in discarding any kind of mentioning related to the technologies, programming languages, libraries, development methodologies, practices which appear to be unrelated to their job.

That's not just cognitive biases in action (which I wholeheartedly confess in being affected by myself), but also pure and perfectly reasonable human behavior, which does it's best to optimize the actions taken by the human being.

So, why would one voluntarily do anything, which is deemed to be discarded almost instantly?

Now, here is where comes a programmer's workout metaphor into action.

Consider yourself going to the gym, and spending some hours per week there, doing the exercises. What you do there, that "weight's pumping" is nothing else as taking heavy things at one place and lifting them up many times during some period of time, just to put those weights back to their place in the end.

So, without any doubt, whatever happens there is:

boring
hard
time-consuming
does not give any visible outcome in the end (those weights end up in the original position).

What's the point, then?.. What is the point in doing something, which is barely enjoyable, and gives no visible outcome immediately?

The stock answer would be that benefit is invisible, long term, and whatnot.

But I honestly think that there really is no point, unless you can tune yourself into the state, where you can consistently come up with short-term achievable goals, and furthermore have the feeling of the success every time those goals are achieved.

So, you've pumped up that thing 12 times two days ago?.. what about adding a couple of kilos on top today and do the same? What about going an extra mile?.. Can you spend 10 more minutes in the gym today?.. You can't?.. Well, it's fine, who cares, there's always next time to try again.

You make this small game out of seemingly boring endeavor, and then eventually, unnoticeably you get to the point where you get used to the process and you start to like it.

You start to enjoy it.

And then, what happens next? The forementioned long-term success comes, that's what happens. You don't really feel it "suddenly coming". At that point it's already with you, and it's hard to tell a difference. But it's there. You see it when you start looking at your old photos. Or at your old code, for that matter.

And even if it does not do it that soon - who cares, that was just a game, right?

So, you get a positive outcome out from doing those throw-away exercises, producing the value from nothing.

What really happens is building a solid background, be it physical or intellectual.

The only problem is that this building can be very routine and hard.

In this case helping yourself into making it a game can help a lot.

Pragmatic Thinking&Learning by Andy Hunt

2009-06-21T06:53:00.000-07:00

So, the book was on my wish list for a while, and then I've suddenly bought it.

And read.

Fortunately, it's not too big and not too mind-pressing, so it did not fall a victim to my occasional bibliomania (yes, I've bought a few other interesting books, some of them still not finished, such a shame). It was a good read, overall.

Sometimes very insightful, even though sometimes it was giving impression of the text being added just for the sake of keeping the format of the book (which otherwise could be a good article).

The style is very accessible (which is pragmatic trademark), there are anecdotes and humorous remarks here and there, which makes for easier reading.

...a controversial study done in the United Kingdom noted that if you constantly interrupt your task to check e-mail or respond to an IM text message, your effective IQ drops ten points. By comparison, smoking a marijuana joint drops your IQ a mere four points. Whatever you do, please don't do both.

However, some things are abused a bit, in my opinion. For example there is too much fuzz around Dreyfus model, or around brain's L-mode/R-mode. To the extent, that sometimes it gives an impression of the marketing speech, rather than revelation, which most of the pragmatic bookshelf books traditionally are. Still, I think the book was a good money investment. Interesting points I've got from it:

There is no golden rules to follow in the software development, everything should be considered in the context, i.e. which systems are there, how they interact (in explicit or hidden ways).
The role of "subconsciousness" in the problem-solving should not be underestimated (that's w.hat is called "R-mode"), as it tends to see "the big picture", and has generally access to much bigger amounts of knowledge.
Experts, the ones which are true masters of their profession, rely deeply upon "intuition" to take decisions. Intuition, as ephemeral as it might sound, is nothing else as the ability to access all the knowledge and experience packed into non-linear way deep inside one's mind.
One does not just "switch to R-mode" to solve complex problems. It's proper interaction/switching between L/R modes what is important.
One can "train" oneself to operate more efficiently on the knowledge access inside the brain (this includes developing of the R-mode).
It's not only that learning constantly is important, also the way learning happens matters a lot. There are ways to make cognition more effective, such as mind maps, collaborative learning, exploration, playing, engaging metaphors and analogies etc.
It's important to maintain diversity in the personal skills, trying to learn thing which might seem "irrelevant" to one's profession.
Stress kills cognition, positive thinking is important for being able to use the brain effectively.
Failure is important and inseparable part of the learning. One has to embrace failure as the opportunity to gain the experience and to stretch the boundaries of the cognition. On the other hand, it should be safe and non-expensive to fail as often as possible (because stress kills cognition).
In the 5-tier Dreyfus model (novice, advanced beginner, competent, proficient, expert) applied to the programming skill, most of the people are on the advanced beginner level.
Software documentation is not as important, as documenting process.

About Qt

2009-06-17T13:41:00.000-07:00

I've accidentally found out today, that one nice guy from my language courses actually works for Trolltech.

So he has told me that, and also that Trolltech is actually a part of Nokia now (again, "revelation" to me, even though these news are 1.5 years old already).

I have this "not surprised" feeling, for some reason.

Qt made a good bargain by being multi-platform, GPL, well-designed, productive and appealing GUI toolkit back then.

Today, when MFC is in the past (well, almost), as well as C++ usage for the newly created desktop applications, and when Microsoft itself provides "free" and much better alternatives (such as .NET platorm, WPF etc.), it probably makes sense to adjust business strategies in order to still have a chance to occupy a bigger niche.

Qt still seems to be the most appealing alternative in case of pure C++ applications. The bulk of those these days, though, are the ones with the roots in the past century, so it's highly unlikely that a lot of them would make a business decision to switch to Qt (in some cases, I imagine, it's hardly possible also).

In any case, it's always entertaining to observe such movements on the market.

It's very possible that in 10 years software market (and game development in particular) will work by somewhat different rules than we've got used to.

The case of the immediate feedback

2009-06-14T06:30:00.000-07:00

I've spent some time today to make a "hello world" kind of application in Visual Studio 2010 using Axiom engine (which in turn is build upon Ogre3D).

The goal was to be able to make a small game, which would have all the bookkeeping part done in C#, and all the game logic done in F#.

Well, I've kind of managed to do that, except that the final setup is not that snappy in regards of iterative experimenting, as it was an initial hope to achieve with F#.

It'd take some while to startup Axiom/Ogre every time the change is made, thus partially defeating the purpose of trying F# in the first place.

Of course, it's very possible that due to my close to zero experience with Axiom I am doing the whole thing in a wrong way, so the mentioned feedback loop could be shortened by introducing some shortcuts.

Or, I am approaching the problem in a wrong way.

It might be very well also possible to avoid starting the 3D engine for developing the game logic, by using some kind of placeholder interface (made in WPF, for example). Something to think about.