Aragon Online

Go Back   Aragon Online > Discussion > Programmer's Cubicle

Programmer's Cubicle A place where some code snippets and other nerdy things will be posted for the general programmer community's benefit.
Note that this is not a programming HELP forum. Posts not about the code here will be deleted or moved.

Reply
 
Thread Tools Display Modes
  #1  
Old 03-07-2010, 07:04 PM
Merlin's Avatar
Merlin Merlin is offline
Supreme Wizard
Administrator
 
City: Riverton
Race: Human
Wealth: 870,002
Population: 1,582
 
Join Date: Dec 2003
Location: The deepest dark of Oregon
Posts: 3,265
Merlin is on a distinguished road
Default Drawing Six Million maps, or...

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 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) == $u : -$u) + (($h 2) == $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 $yy0 0.05;
            
$xx2 $xx0 $yy0 0.05;
            
$xx3 $xx0 15 $yy0 13 0.05;
            
$yy1 $yy0 $xx0 0.05;
            
$yy2 $yy0 $xx0 0.05;
            
$yy3 $yy0 15 $xx0 13 0.05;

            
// Limit to map guidelines
            
$x1 floor($xx/4);
            
$y1 floor($yy/4);
            
$x2 $xx/$x1;
            
$y2 $yy/$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'] = '';
        }
    } 
__________________
Do not meddle in the affairs of wizards, for they are subtle and quick to anger.
The Lord of the Rings
Gildor, Chapter 'Three is Company'.

Last edited by Merlin; 03-07-2010 at 07:28 PM.
Reply With Quote
  #2  
Old 05-01-2010, 03:57 AM
Telarion's Avatar
Telarion Telarion is offline
Playtester
Scribe
 
City: Imaldris
Race: Elf
Wealth: 289,569
Population: 1,356
 
Join Date: Apr 2010
Location: Greater Vancouver Region
Posts: 46
Telarion is on a distinguished road
Default

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
__________________
Something Profound goes Here
Reply With Quote
  #3  
Old 05-01-2010, 03:12 PM
Merlin's Avatar
Merlin Merlin is offline
Supreme Wizard
Administrator
 
City: Riverton
Race: Human
Wealth: 870,002
Population: 1,582
 
Join Date: Dec 2003
Location: The deepest dark of Oregon
Posts: 3,265
Merlin is on a distinguished road
Default

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.)
__________________
Do not meddle in the affairs of wizards, for they are subtle and quick to anger.
The Lord of the Rings
Gildor, Chapter 'Three is Company'.
Reply With Quote
  #4  
Old 05-01-2010, 09:25 PM
Telarion's Avatar
Telarion Telarion is offline
Playtester
Scribe
 
City: Imaldris
Race: Elf
Wealth: 289,569
Population: 1,356
 
Join Date: Apr 2010
Location: Greater Vancouver Region
Posts: 46
Telarion is on a distinguished road
Default

Oh I hear you on the overuse of certain functions.

I am still cleaning up code from when I was a php newb
__________________
Something Profound goes Here
Reply With Quote
Reply

Bookmarks

Tags
code, noise, perlin, php, procedural map

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT. The time now is 07:11 PM.


Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright ©2003 - 2012 by Unintended Features