As a way of spending my bank holiday Sunday afternoon, I decided to embark on a small project; I didn't know what the project would be when I first began browsing through Wikipedia but eventually I ended up in About.com's C++ challenge section, one of which concerned John Horton Conway's "Game of Life": a rudimentary cellular automaton which, after its inception in 1970, had immeasurable impact on fields as diverse as philosophy and theology. After toying with some ideas, I decided to build a script which automatically creates animations of a number of generations of the game. From that seed the project grew into the first steps towards an avatar system, much like the automatically generated Gravatars that currently adorn so many Wordpress based blogs.
private function tick($currentState)
{
// copy
$newState = $currentState;
$width = count($currentState[0]); $height = count($currentState);
for($h = 0; $h < $height; $h++)
{
for($w = 0; $w < $width; $w++)
{
$neighbours = 0;
for($i = 0; $i < 8; $i++)
{
$newH = $h; $newW = $w;
switch($i)
{
case 0:
$newW -= 1; $newH -= 1;
break;
case 1:
$newH -= 1;
break;
case 2:
$newW += 1; $newH -=1;
break;
case 3:
$newW += 1;
break;
case 4:
$newW += 1; $newH += 1;
break;
case 5:
$newH += 1;
break;
case 6:
$newW -= 1; $newH += 1;
break;
case 7:
$newW -= 1;
break;
}
$newW = ($newW < 0) ? ($width + $newW) : $newW;
$newW = ($newW >= $width) ? ($newW - $width) : $newW;
$newH = ($newH < 0) ? ($height + $newH) : $newH;
$newH = ($newH >= $height) ? ($newH - $height) : $newH;
$neighbours += ($currentState[$newW][$newH]);
}
if($currentState[$w][$h] == 1)
{
if(($neighbours < 2) || ($neighbours > 3))
{
$newState[$w][$h] = 0;
}
}
else
{
if($neighbours == 3)
{
$newState[$w][$h] = 1;
}
}
}
}
return $newState;
}
Part of the development of this involved settling on a suitable debug output. Initially this was just a pre-formatted output of each state with a 0 representing an inactive cell and a 1 representing an active one; this is fine for quickly checking the state but matching up against more detailed debug output (such as neighbours for a specific cell) proved tricky, especially when you take into account line-heights and other annoyances. I settled on a quick HTML table which had a caption for the current generation of the algorithm and also added co-ordinate references for easy look ups.
This is fine for checking a limited number of states or small grids but when those variables climb higher then browser rendering time and page payload size becomes an issue. As mentioned previously, this is the most basic implementation of the algorithm and has not been subject to any optimisation: each cell requires eight lookups and with no heuristic pruning larger grids will take exponentially longer to calculate. There are obvious improvements that could be made as well as storage alterations (quad trees et. al.) that could benefit, however until I could measure the algorithm's performance, this is a decent first attempt. The next step was to output something more useful than HTML tables - enter GD. Putting together a very quick function to create a static GIF file:
private function outputStateToGif(array $state, $generation, $outputDir, $foreground, $background)
{
$width = count($state[0]); $height = count($state);
$img = imagecreate($width * 2, $height * 2);
imagefill($img, 0, 0, imagecolorallocate($img, $background[0], $background[1], $background[2]));
$onColour = imagecolorallocate($img, $foreground[0], $foreground[1], $foreground[2]);
for($h = 0; $h < $height; $h++)
{
for($w = 0; $w < $width; $w++)
{
if($state[$w][$h] == 1)
{
imagefilledrectangle($img, $w*2, $h*2, $w*2+1, $h*2+1, $onColour);
}
}
}
$outputDir = rtrim($outputDir, "/");
$filename = sprintf("%04d", $generation);
imagegif($img, "{$outputDir}/{$filename}.gif");
imagedestroy($img);
}
With all of this in place it meant that I could now create animated GIF files of the Game of Life without any hassle - combining the GIF files together at the end is a simple case of firing up ImageMagick with the command:
convert -delay 10 -loop 0 output/*.gif output/output.gif
This will merge all of the GIF files together and loop at the end with each frame lasting a 10th of a second (default ticks per section is 100). There is the possibility of optimising the animated GIF further with transparency so that each frame takes up the minimum amount of space however with 200 frame animations being scarcely over 100 kilobytes, there doesn't seem much point especially when taking into account the complexities involved.
With the algorithm in place and output more or less sewn up, it was time to concentrate on the avatar aspect of the project. Ideally I wanted something that was deterministic and identifiable - both of these are currently fulfilled by the automatically generated Gravatar icons which are based off Scott Sherrill-Mix's WP_Identicon plugin. I would be examining how to turn an e-mail address into a seed for the algorithm and generating colours to make them unique: trickier said than done with innumerable ways to achieve these goals, but producing good results is tricky.
To generate the seed I converted each character of the e-mail address to a number and then performed some operations on that. Using the built-in PHP function ord() was out of the question as this would only deal with ASCII characters (until PHP get their finger out and natively support Unicode) and this would potentially be dealing with Unicode characters; I briefly considered rolling my own function but stumbled upon an implementation by Henri Sivonen which was based off code from the Mozilla project which would have been scrutinised far more than something I would have cooked up on a sleepy Sunday afternoon. The utf8ToUnicode() function takes a string as a parameter and returns an array of Unicode code point integers: perfect for what I was going to use them for. I spent a great deal of time trying out different operations on those values and eventually settled on one that worked for seeds of dimensions less than 6:
$pieces = utf8ToUnicode($email);
$previous = 124;
foreach($pieces AS $piece)
{
$k = intval(sprintf("%01b", (($piece * $previous) >> PHP_INT_SIZE) & 0x1));
$seed[] = (count($seed) < ($width * $height)) ? $k : (array_shift($seed) & $k);
$previous = $piece;
}
After multiplying the value by the previous one (a static initial value is used, I went for 124 as a general ASCII midpoint value), the result is shifted to the right to obtain a single binary value. If the string is longer than the seed (e.g. greater than 25 for a 5x5 grid) then it shifts the first entry from the generated seed and bitwise ANDs it with the value.
This fulfils the deterministic nature of the seed and means the entire string is used rather than stopping when the seed length is reached. If the string is shorter than the seed, it is padded with inactive cells (0's). This method produces decent results, while they weren't exactly wildly different from each other (i.e. the chance of seed collisions is fairly high) it successfully went from a string to a seed with acceptable results. I had initially considered cribbing some one-way hash functions from algorithms such as SHA or HAVAL and flicked through Applied Cryptography to that end, however I eventually decided that this would be overkill for such a simple implementation.
The next step was generating colours. I wanted the domain part of an e-mail address to represent the background colour while the local part would represent the foreground colour; this way it would be obvious who was using Google Mail or Live Mail etc. but visitors would still be able to remain unique. This generation is definitely an area for improvement as the results will show:
public static function colours($string)
{
list($local, $fqdn) = explode("@", $string);
$multiplier = array_sum(utf8ToUnicode($string));
$localProduct = array_sum(utf8ToUnicode($local)) * $multiplier;
$fqdnProduct = array_sum(utf8ToUnicode($fqdn)) * $multiplier;
$fg = array(($localProduct >> 16) & 0xFF, ($localProduct >> 8) & 0xFF, $localProduct & 0xFF);
$bg = array(($fqdnProduct >> 16) & 0xFF, ($fqdnProduct >> 8) & 0xFF, $fqdnProduct & 0xFF);
return array($fg, $bg);
}
In short this sums the Unicode values of each part of the address and multiplies it by the sum of the entire string, the reason for the multiplication is that the values within a common e-mail address are usually fairly low (ironically within the first 128 ASCII characters) and the resultant number definitely favoured the green / blue end of the spectrum, multiplication introduces a red component in most cases. I toyed with other methods of producing a usable number such as using the product of the values rather than a summation, unfortunately this created a number that was too large to be useful - frequently breaking the maximum integer value limit.
With both the seed and the colours now able to be generated from an e-mail address, it was time to trial it out on a large number of possible addresses.
This is a random sampling from over 1,300 addresses which I used to get benchmarks and timing data (a topic for another time) - each is a 32x32 grid (double sized to 64x64 for the images) and are limited to 50 generations. The colours are obviously all shifted towards the blue/green area of the spectrum due to the way they are generated, there are no bright reds or certain colour mixtures such as yellows or oranges which makes them very bland, especially when combined with the choice of foreground colours which can easily lack contrast. The next problem is the mixed bag of animations given a 5x5 seed, obviously I wasn't expecting a raft of infinite growth seeds but, having looked at them in aggregate, the majority tend to dissolve after only a few generations or become static, both of which make for boring avatars.
Ways forward
I'm certainly not finished with this idea yet as I think it definitely has legs although the measure will be in the details. The first aspect to address is the visuals, I had expected more growth within 50 generations but a lot of the grids could be reduced down to 16x16 which would allow for visibly larger and subsequently more interesting cell animations - as the environment is toroidal in nature this may turn out to be beneficial to growth. Colours are also high priority, choosing a background colour based upon domain name of the e-mail was perhaps the wrong way to go and settling on a single background colour and a different foreground colour will likely help immeasurably with aesthetics.
I've still to collate the timing data I gathered from the run on the e-mail database however my initial examination indicates that the Game of Life algorithm itself likely doesn't need overhauling to improve speed, proposed optimisations such as Hashlife improve speed at the cost of memory and with such small grids the effect would likely be negligible. The most time consuming aspect of the script is the generation of the GIF files and subsequent I/O which is done regardless of whether the state has normalised or entirely died out - pruning and state checking would likely be immensely beneficial.
Conclusion
For a Sunday afternoon the results are not exactly ground breaking but are interesting and act as a good base for further enhancement - the possibilities are immense and it's always gratifying to see a project come together in a short space of time. That said, I think I've seen enough animated GIFs of tiny blinking blocks for one day.