Drawing Six Million maps, or...

[Merlin]

Aragon Online has a very large World, 97 x 97 hexes, in which the game is played. Each hex can be zoomed to display the Region map, which is 25 x 25 hexes. In turn, each Region hex can be zoomed into to show the tactical map. There are 9,409 region maps, and 5,880,625 tactical maps. Each is unique.

So, how did we draw about 6 million maps? Well, we didn't. The World map was created with an editor program, but both the region and tactical maps are generated with a procedural method. Each is unique, and can be reliably generated at will for any hex, and will always be the same. (A "random" method wouldn't repeatable, in general, though there are ways of overcoming that.)

Only a handful of maps are ever saved in the database. (If we saved every tactical map, we'd have a table containing 3,675,390,625 hexes, which would be a very huge data set!)

The map generation routine uses the World hex characteristics to get the general contour of the map, then a Perlin Noise generator to fill-in the details.

Note: Ken Perlin invented this algorithm in the 1980s, and won an Academy Award for his work advancing the state of the art of computer graphics: http://mrl.nyu.edu/~perlin/doc/oscar.html

This algorithm is very widely used in computer graphics, and for many other applications, like this map system.

Here is my PHP implementation of the "improved" Perlin Noise generation.

PHP Code:

<?php
/* Aragon Online - Copyright 2003-2010 by Russell Shilling */
/* cls_perlin.php */

/*      Adapted from Ken Perlin's reference implementation
 *      of the improved noise function found here:
 *      http://mrl.nyu.edu/~perlin/noise/
 */

class perlin {

    var $permutation;

    function perlin() {

        $this->permutation = array( 151,160,137,91,90,15,131,13,201,95,96,53,
            194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,190,6,148,
            247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
            88,237,149,56,87,174,20,125,136,171,168,68,175,74,165,71,134,139,
            48,27,166,77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,
            41,55,46,245,40,244,102,143,54,65,25,63,161,1,216,80,73,209,76,
            132,187,208,89,18,169,200,196,135,130,116,188,159,86,164,100,109,
            198,173,186,3,64,52,217,226,250,124,123,5,202,38,147,118,126,255,
            82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,223,183,170,213,
            119,248,152,2,44,154,163,70,221,153,101,155,167,43,172,9,129,22,39,
            253,19,98,108,110,79,113,224,232,178,185,112,104,218,246,97,228,
            251,34,242,193,238,210,144,12,191,179,162,241,81,51,145,235,249,14,
            239,107,49,192,214,31,181,199,106,157,184,84,204,176,115,121,50,45,
            127,4,150,254,138,236,205,93,222,114,67,29,24,72,243,141,128,195,
            78,66,215,61,156,180 );

        for($i = 0; $i < 256 ; $i++) {
            $this->permutation[256+$i] = $this->permutation[$i];
        }
    }

    function noise($x, $y) {

        // Find unit square that contains point
        $xx = floor($x) & 255;
        $yy = floor($y) & 255;
        // Find relative x,y of point in square
        $x -= floor($x);
        $y -= floor($y);

        // compute fade curves for each x,y
        $u = $this->fade($x);
        $v = $this->fade($y);

        // Hash coords of the 4 corners
        $A = $this->permutation[$xx] + $yy;
        $AA = $this->permutation[$A];
        $AB = $this->permutation[$A + 1];
        $B = $this->permutation[$xx + 1] + $yy;
        $BA = $this->permutation[$B];
        $BB = $this->permutation[$B + 1];

        // And add blended results from 4 corners of square
        return $this->lerp($v,$this->lerp($u, $this->grad($this->permutation[$AA], $x, $y),
                                              $this->grad($this->permutation[$BA], $x-1, $y)),
                              $this->lerp($u, $this->grad($this->permutation[$AB], $x, $y-1),
                                              $this->grad($this->permutation[$BB], $x-1, $y-1)));
    }

    function fade($t) { return $t * $t * $t * ($t * ($t * 6 - 15) + 10); }
    function lerp($t, $a, $b) { return $a + $t * ($b - $a); }
    function grad($hash, $x, $y)
    {
        // convert low 4 bits of hash code into gradient directions
        $h = $hash & 15;
        $u = ($h < 8) ? $x : $y;
        $v = ($h & 4) ? $x : $y;

        return (($h & 1) == 0 ? $u : -$u) + (($h & 2) == 0 ? $v : -$v);
    }

    /* Test
    $perlin = new perlin();

    $min = 9999;
    $max = -9999;

    echo "<table>\n";
    for ($y = 0; $y <= 10; $y += 0.1) {
        echo "<tr>";
        for ($x = 0; $x <= 10; $x += 0.1) {

            $value = round(10*$perlin->noise($x, $y));
            if ($value < $min) $min = $value;
            if ($value > $max) $max = $value;

            echo "<td>";
            echo $value;
            echo "</td>";
        }
        echo "</tr>\n";
    }
    echo "</table>\n";

    echo "Min: " . $min . "<br/>";
    echo "Max: " . $max . "<br/>";
    */
}
?>

Here is a snippet of the code that uses the Perlin class to generate a map. $x_seed and $y_seed are the World or World/Region coordinates (essentially the "origin" of the map). I use the 3 separate noise calls because one property of the noise function is that the value is zero at the grid edge, where x and y are whole numbers without a fractional part. Adding 3 values, with those odd factors in the $xx1, $xx2 and $xx3 code below, guarantees that the 3 functions are never zero value simultaneously.

PHP Code:

    $lo = 0;
    $hi = 8;

    // Generate the terrain
    for ($xx = 0; $xx < X_MAX; $xx++) {
        for ($yy = 0; $yy < Y_MAX; $yy++) {

            $xx0 = $x_seed + $xx / X_MAX;
            if ($yy & 1)
                $yy0 = $y_seed + ($yy-0.5) / Y_MAX;
            else
                $yy0 = $y_seed + $yy / Y_MAX;

            $xx1 = $xx0 * 5 + $yy0 * 7 + 0.05;
            $xx2 = $xx0 * 7 + $yy0 * 9 + 0.05;
            $xx3 = $xx0 * 15 - $yy0 * 13 + 0.05;
            $yy1 = $yy0 * 5 + $xx0 * 7 + 0.05;
            $yy2 = $yy0 * 7 - $xx0 * 9 + 0.05;
            $yy3 = $yy0 * 15 + $xx0 * 13 + 0.05;

            // Limit to map guidelines
            $x1 = floor($xx/4);
            $y1 = floor($yy/4);
            $x2 = $xx/4 - $x1;
            $y2 = $yy/4 - $y1;
            $x3 = min(6,$x1+1);
            $y3 = min(6,$y1+1);

            $h = $perlin->lerp($y2, $perlin->lerp($x2, $hgt[$x1][$y1], $hgt[$x3][$y1]),
                           $perlin->lerp($x2, $hgt[$x1][$y3], $hgt[$x3][$y3]));

            // This makes the non-river areas more variable
            $pscale = 0.5;
            if ($h > 3) {
                $pscale += 0.2 * ($h - 2.5);

            // Make sure the river areas are watery
            } elseif ($h < 2.75) {
                $h -= 0.5;
            }

            $t = $h + $pscale * ($perlin->noise($xx1, $yy1)
                                + 0.7 * $perlin->noise($xx2, $yy2)
                                + 0.5 * $perlin->noise($xx3, $yy3));

            // Save this for use later
            $elev[$xx][$yy]['elev'] = $t;

            // Convert to int and limit
            $t = intval(round($t));

            if ($t < $lo) $t = $lo;
            if ($t > $hi) $t = $hi;

            $map[$xx][$yy]['terr'] = $t;
            $map[$xx][$yy]['feat'] = '';
        }
    } 


[Telarion]

Hey Merlin,

not to nitpick at code or anything but my years of experience with PHP has taught me to append string the output statement and instead of echos.
I append the data to a output string var such as sOutputString for example and then just echo the output string at the end of the processing.

Each echo acts as a function call, and function calls take more time than a simple append ie ( $sOutputString .= thisInfo )

This would improve your speeds when processing big areas, or even the little areas

Telarion

[Merlin]

Thanks for the tip - every little bit of speed helps.

That's probably unimportant in the test function, but I'll review other code and see where that can be improved. My older code, especially probably over uses echo. (I started this in 2003 as a PHP newb... Now I have a lot more experience using the language.)

[Telarion]

Oh I hear you on the overuse of certain functions.

I am still cleaning up code from when I was a php newb