Merlin

03-07-2010, 07:04 PM

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 (http://mrl.nyu.edu/%7Eperlin/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

/* 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,1 1,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,1 47,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,2 18,246,97,228,

251,34,242,193,238,210,144,12,191,179,162,241,81,5 1,145,235,249,14,

239,107,49,192,214,31,181,199,106,157,184,84,204,1 76,115,121,50,45,

127,4,150,254,138,236,205,93,222,114,67,29,24,72,2 43,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.

$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'] = '';

}

}

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 (http://mrl.nyu.edu/%7Eperlin/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

/* 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,1 1,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,1 47,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,2 18,246,97,228,

251,34,242,193,238,210,144,12,191,179,162,241,81,5 1,145,235,249,14,

239,107,49,192,214,31,181,199,106,157,184,84,204,1 76,115,121,50,45,

127,4,150,254,138,236,205,93,222,114,67,29,24,72,2 43,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.

$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'] = '';

}

}