Vjeux

While on holidays, I played that old (bought in the 80's) board game called Fief. After several games I wanted to point at the good and bad things about this game in order to find some general rule.

Fief - Board Strategy Game

Some assets of the game are innovative and worth mentioning.

The resources are really limited. It is common to have limited number of soldiers or houses, but the limitations are often relative to a player. In this game, there is a limited amount of money. After several rounds, there's no money left in the bank and people cannot earn their income. This opens the possibility to organize bankruptcy.

Movement design is clever. The only way to move your army from town to town are Lords. They are special soldiers that can walk 2 towns a round. While moving, they are able to carry any amount of soldiers with them. Once they are well positioned, the Lords allow you to move around the map really fast.

However, that's not a perfect game, the main problem could be summarized with the statement "10 pages rules book". Here are some consequences of that fact.

• Many rules leads to contradictions and unclear statements
• The learning curve is disastrous
• More time spent reading and discussing the rules than playing the game

In order to find a solution, we are going to analyze some facts and get general rules off them.

Could we play without this rule? Yes. Drop it.

In the game, there are 2 types of building that gives resources: Mill [cost 300, give 200] and Press [cost 200, give 100]. Basically, you first buy all the Mills and when there are no left you start taking Presses. These two buildings are just about the same, do not give any kind of reflexion but have to be learned by the players. Removing one building would not affect the decision range of the user and would make the game easier to play.

Ten things doing slightly different things? Merge them!

There are lots of cards but you can never use them. There are offensive cards and their respective defensive cards. Offensive cards are targeted against a player and aren't that common. No need to say that you never have the defensive card when needed. That's about the same for cards that gives money, you either have to be Clergy, have a Fief or be King to use them. Since most of the time you are nothing, these cards are trash. Being given useless card over useless card is a really bad feeling.

A solution would be to transform these useless cards would be to make them generic. What about having a rare card that can counter any offensive attack. As for the money card, it would give money based on the highest rank you have. By changing how to attribute the cards, we could keep the same usage rate. They would be seen like a great reward and as a side effect simplify the game.

Simple rules, great flexibility.

The methodology adopted by the game is: "There's a problem? Add a special rule for this exact problem". What if we let the user the possibility to do it anyway? It will give flexibility and make the game easier to understand! For further thoughts about this philosophy in the web development, i would suggest you to read the free book Getting Real.

Mysqli Wrapper is shortening the code required to run queries, make them 100% safe against SQL Injections and gives a handy Array as result. No more pain writing queries!

When developing a PHP application, SQL queries is the most dangerous area. This is because the built-in tools are either not secure by conception or too much complicated to use. I've made a little wrapper to mysqli that solves all these problems and make you enjoy writing queries!

You are probably writing your queries like this. We assume we have $zip(string) and $pop(int) variables previously declared in the code.

// Basic Method
mysql_connect('host', 'user', 'pass');
mysql_select_db('database');
$query = "SELECT Name, CountryCode FROM City 
    WHERE Zip = '".mysql_real_escape_string($zip)."' AND Population > ".(int) $pop;
$result = mysql_query($query);
while ($row = mysql_fetch_array($result)) {
    // $row['Name'], $row['CountryCode']
}

With this method, you have to secure all the fields yourself. To do it, you have to type the loooong function mysql_real_escape_string and you must not forget the quotes around the parameter. The code is unreadable, not safe by concept because you may forget to sanitize a field ... And, it is annoying to write!

Mysqli was intended to be a wrapper around Mysql that would provide safe queries. You may wonder why this has not become the default way to write queries. Have a look at the exact same code written with mysqli.

// Mysqli Method
$mysqli = new mysqli('host', 'user', 'pass', 'database');
$query = "SELECT Name, CountryCode FROM City WHERE Zip = ? AND Population > ?";
if ($stmt = $mysqli->prepare($query)) {
    $stmt->bind_param('si', $zip, $pop);
    $stmt->execute();
    $stmt->bind_result($name, $code);
    while ($stmt->fetch()) {
        // $name, $code
    }
    $stmt->close();
}

Yes, 10 lines to make a SELECT. Obviously they failed to design an easy to use API. It is also too restrictive: you have to assign a variable for each of the field you want to select. This seems to be a really waste of time: it's already in the query, why would you write it another time? Also, that's not possible to use '*' to select all the fields.

Here is my attempt to easily to write and safe queries:

// My method
$db = new dbWrapper('host', 'user', 'pass', 'database', true);
$result = $db->q("SELECT Name, CountryCode FROM City WHERE Zip = ? AND Population > ?",
  'si', $zip, $pop);
foreach ($result as $key => $city) {
  // $city['Name'], $city['CountryCode']
}

What's good about this:

• A single 6 characters function
• Secure because parameterized
• Returns an Array
• Easy migration from the basic method

I'm really happy with that wrapper. It is faster to write the queries because you don't have to sanitize the parameters neither you have to think about safety and there's only a 6 character function to remember. The code is smaller and easier to use because it returns a real Array! Also, this allows to display mysql errors on the development server only and doesn't requires to type or die(mysql_error()); everytime.

If you don't know by advance the number of parameters (A custom search where field may be selected or not by the user for example), this implementation becomes really tricky to deal with. I have no solution at this time for this problem. The v8cgi Query API would handle this problem really well, however i am not confident enough in letting a script writing my queries.

The wrapper code is really hacky but fits in 60 lines so can be embedded really easily. Download

Class dbWrapper {
    protected $_mysqli;
    protected $_debug;
 
    public function __construct($host, $username, $password, $database, $debug) {
        $this->_mysqli = new mysqli($host, $username, $password, $database);
        $this->_debug = (bool) $debug;
        if (mysqli_connect_errno()) {
            if ($this->_debug) {
                echo mysqli_connect_error();
                debug_print_backtrace();
            }
            return false;
        }
        return true;
    }
 
    public function q($query) {
        if ($query = $this->_mysqli->prepare($query)) {
            if (func_num_args() > 1) {
                $x = func_get_args();
                $args = array_merge(array(func_get_arg(1)),
                    array_slice($x, 2));
                $args_ref = array();
                foreach($args as $k => &$arg) {
                    $args_ref[$k] = &$arg; 
                }
                call_user_func_array(array($query, 'bind_param'), $args_ref);
            }
            $query->execute();
 
            if ($query->errno) {
              if ($this->_debug) {
                echo mysqli_error($this->_mysqli);
                debug_print_backtrace();
              }
              return false;
            }
 
            if ($query->affected_rows > -1) {
                return $query->affected_rows;
            }
            $params = array();
            $meta = $query->result_metadata();
            while ($field = $meta->fetch_field()) {
                $params[] = &$row[$field->name];
            }
            call_user_func_array(array($query, 'bind_result'), $params);
 
            $result = array();
            while ($query->fetch()) {
                $r = array();
                foreach ($row as $key => $val) {
                    $r[$key] = $val;
                }
                $result[] = $r;
            }
            $query->close(); 
            return $result;
        } else {
            if ($this->_debug) {
                echo $this->_mysqli->error;
                debug_print_backtrace();
            }
            return false;
        }
    }
 
    public function handle() {
        return $this->_mysqli;
    }
}

Update February 17 2010: Now works for php >= 5.3.0. Added debug_print_backtrace to get the sql query when there is an error.

The bracket notation for string is incomplete in Javascript and does not work in IE7. This is really painful to migrate to the .charAt(pos) equivalent, this is why i recommend you not to use it.

// Bracket Notation
"Hello World!"[6]
// > "W"
 
// Real Implementation
"Hello World!".charAt(6)
// > "W"

The bracket notation to get a character from a string is a shortcut to .charAt(pos) added by the vast majority of the browsers. However, i would not recommend to use it for several reasons.

This notation does not work in IE7. The first code snippet will return undefined in IE7. If you happen to use the bracket notation for strings all over your code and you want to migrate to .charAt(pos), this is a real pain: Brackets are used all over your code and there's no easy way to detect if that's for a string or an array/object.

You can't set the character using this notation. As there is no warning of any kind, this is really confusing and frustrating. If you were using the .charAt(pos) function, you would not have been tempted to do it.

var string = "Hello World!";
string[6] = '?';
console.log(string);
// > "Hello World!";

By overriding the toString Object prototype, it is possible to speed up by 5x the sort function. This is an easy to implement trick that gives astonishing results

I wanted to know if there were ways to speed up the Javascript Sort function. I came across an interesting article (Yet another faster Javascript Sorting) that presents a way to boost the builtin sort function. However, the link with the detailed explanation is dead, so i make you a summary here.

To sort some data, you are likely to do something that looks like that:

data.sort(function (a, b) { return b.key - a.key; });

The comparison function is being called n log n times. Since it's a javascript function, it is slow. sort() with no parameters will first convert all elements into strings and then use native (therefore faster) string comparison.

To make this work, we just have to override the toString method of the Object prototype to return the key.

var save = Object.prototype.toString;
Object.prototype.toString = function () { return this.key; };
 
data.sort();
 
Object.prototype.toString = save;

You have to make sure that the key variable is a string. In my application, the key range is [0, 100] so the it is written as String.fromCharCode(key). If you have to deal with larger key range, the best solution is to convert the number into base 256. Make sure the number is padded with 0 because of the string comparison.

I made a little benchmark of the implementation to see how well it performs

*: Script time limit has been exceeded

It gives about a 5x increase of all the browsers I have tested with except in Chrome with a 3x decrease.

Since Chrome is already times faster than all the browsers, it doesn't look slowed by this feature. However it gives a real boost to all other browsers.

Update (24 December 2009): Chrome Array.sort() function is written directly in javascript and calls the ToString function everytime when a comparison is needed. Therefore, it is making 2 function calls (ToString(x), ToString(y) instead of one (compare(x, y)).

In order to check if that optimization will indeed give an actual boost, we can count the number of time the ToString method is being executed for 3 values. 3 times means that it is executed n time and more means that it is executed n log n times.

var need_custom_sort = (function () {
  // Fill the array with 3 values
  var array = new Array(3);
  for (var i = 0; i < 3; ++i) {
    array[i] = new Object();
  }
 
  // Override the toString method that counts how many times it is being called
  var count = 0;
  var save = Object.prototype.toString;
  Object.prototype.toString = function () { count += 1; return ""; };
 
  // Sort
  array.sort();
  Object.prototype.toString = save;
 
  // 3 times is good, more is bad!
  return (count === 3);
}());

SmallHash encodes any range of integers into the smallest possible string. This way, you can use the hash part of your url with efficiency.

My problem is having these options stored in the minimum characters as possible.

• Faction: Alliance, Horde
• Region: US, Europe
• Type: PvE, PvP, RP
• Lang: EN, FR, ES, DE, RU

The two faction and region could be stored in base 2 with no problem. However, if we wanted to store the others in base 2, there would have been space left. So i started digging up into the base conversion.

Here is the code to do a base2 to base10 conversion.

base10 = 0
foreach (bit in base2) {
  base10 *= 2
  base10 += bit
}

As you can see, we multiply the final number by 2, which is the number of possibilities. So, instead of multiplying by 2, we multiply by the number of possible options and it works! The decoding process is using the same technique by changing the divisor.

To get back to our example. [Alliance, US, PvP, DE] can be expressed as [0,0,1,3] over [2,2,3,5]. It will be encoded and decoded easily with the SmallHash library:

var input = [0,0,1,3];
var encoded = SmallHash.encode(input, [2,2,3,5], 'abcdefghijklmnopqrstuvwxyz');
var decoded = SmallHash.decode(encoded, [2,2,3,5], 'abcdefghijklmnopqrstuvwxyz');
console.log(input, encoded, decoded);
// Result: [0, 0, 1, 3], "bo", [0, 0, 1, 3]

As you can see, it fits into 2 characters instead of 4 with the easy way. The gain increases with the number of data you have to encode. This can also be improved by enlarging the base characters (uppercase letter, digits and special characters).

The algorithm is fairly easy, it is the same one explain before but using the range instead of 2 (when converting in base 2). This is the pseudo-code version.

 
SmallHash = {
  // encode( [2, 4], [10, 15], '0123456789' ) : '42'
  encode: function (input, ranges, base) {
    var result = 0
    for offset = ranges.length - 1 downto 0
      result = result * ranges[offset]
      result = result + input[offset]
 
    return int2str(result, base)
  },
 
  // decode( '42', [10, 15], '0123456789' ) : [2, 4]
  decode: function (input, ranges, base) {
    input = str2int(input, base)
    var result = []
 
    for offset = 0 to ranges - 1
      result[offset] = inputs % ranges[offset]
      inputs = inputs / ranges[offset]
 
    return result;
  }
};

Here is the full source code. This is the same code but being less readable due to the use of BigInt and the need of managing the allocation size.

// Requires BigInt.js ( https://blog.vjeux.com/wp-content/uploads/2009/08/BigInt.js )
SmallHash = {
  encode: function (input, ranges, base) {
    // Rough majoration of the final result size
    // It makes the sum of all the minimum of bits required for each range
    var size = 0;
    for (var i = 0, len = ranges.length; i < len; i = i + 1) {
      size += Math.ceil(Math.log(ranges[i]) / Math.LN2);
    }
    var result = bigInt.int2bigInt(0, size);
    for (var bit = ranges.length - 1, pos = 0; bit >= 0; bit = bit - 1, pos = pos + 1) {
      // If the value is higher than the expected range, the value is maximized
      // Therefore the result is always valid, even if the input is not
      var parsed_bit = Math.min(Math.abs(Math.floor(input[bit])), ranges[bit] - 1);
      bigInt.mult_(result, bigInt.int2bigInt(ranges[bit], 32));
      bigInt.add_(result, bigInt.int2bigInt(parsed_bit, 32));
    }
    return bigInt.bigInt2str(result, base.length, base);
  },
  decode: function (input, ranges, base) {
    input = bigInt.str2bigInt(input, base.length, base);
    var remainder = bigInt.dup(input); // Allocates enough room for the remainder
    var result = [];
    for (var pos = 0, len = ranges.length; pos < len; pos = pos + 1) {
      bigInt.divide_(input, bigInt.int2bigInt(ranges[pos], 32), input, remainder);
      result[pos] = Number(bigInt.bigInt2str(remainder, 10, '0123456789'));
    }
    return result;
  }
};

This script is using the BigInt library from Leemon Baird. I made some changes in order not to pollute the global namespace and added the possibility to modify the base string.

Update January 2010 - SmallHash is now being used on production at wowtal.com and you can download the source at http://static.mmo-champion.com/db/js/smallhash.js.