Diamond-square algorithm aneb náhodný terén
Jelikož jsem jeden z těch Fantasy world builder bláznů, tedy z lidí, kteří si vytvářejí svůj vlastní nezávislý fantasy svět, tak mě neberte až zas tak vážně. Moje mánie dospěla ve spojení s mým pseudo studiem geografie až tak daleko, že chci mít opravdu dobré a reálné mapy tohoto mého světa. Naskýtá se hned vícero problémů a otázek. Kdo mapy vymyslí, kdo je nakreslí, kolik jich bude potřeba k pokrytí známého světa, jak budou podrobné... a mnoho dalších. Jelikož jsem člověk od přírody líný, nehodlám se ručně babrat s mapami v měřítku 1:50,000 a raději jsem začal pátrat po možnosti náhodného generování terénu. Takových možností jsem našel spousty, dokonce i mnoho hotových programů, ale žádný mi úplně nevyhovoval a tak jsem si řekl, že si ten základ udělám sám.
Nejlepší se mi na to zdála metoda diamanto čtvercového algoritmu. Ten se skládá s následujících částí:
- Máme 4 rohy čtverce s určenými (nebo náhodnými) výškami
- V první polovině iterace veprostřed mezi těmito 4mi body vytvoříme další bod, který bude mít výšku průměru bodů rohových + náhodný koeficient
- V druhé polovině iterace doplníme body do pravidelné čtvercové sítě, při zachování předchozího (průměrového) postupu
<?php
// základní proměnné
$rozmer = "16"; // + 1 (protože pole začíná od 0)
$min = "-1";
$max = "1";
$uzel1 = "1"; // uzly první poloviny iterace
$uzel2 = "4"; // uzly druhé poloviny iterace
$pocet_uzlu = "4"; // pseudocelkový počet uzlů
$pocet_iteraci = "4";
$iterace = "1";
// rohy čtverce mají přiděleny hodnoty,
// lze samozřejmě přidělovat i náhodně
$pole[0][0] = "1";
$pole[$rozmer][0] = "2";
$pole[0][$rozmer] = "3";
$pole[$rozmer][$rozmer] = "4";
// funkce pro pseudo náhodné výšky uzlů
function soucet($pole1, $pole2, $pole3, $pole4, $min, $max)
{
if($pole1 == "" or $pole2 == "" or $pole3 == "" or $pole4 == "")
{
$delitel = "3";
}
else
{
$delitel = "4";
}
$soucet_poli = round((($pole1 + $pole2 + $pole3 + $pole4)
/$delitel)+rand($min,$max), 2);
return $soucet_poli;
}
while($iterace <= "$pocet_iteraci")
{
// nejprve musíme zjistit počet uzlů 1. části iterace
if($iterace == "1")
{
$uzel1 = $uzel1;
}
else
{
$uzel1 = 4*$uzel1;
}
// souřadnice prvního uzlu 1/2 dané iterace
$x1 = ($rozmer/sqrt($uzel1))/2;
$y1 = $x1;
$jump = 2*$x1;
// projede možné souřadnice pro 1/2 iterace
$pocet_uzel1 = "1";
while($pocet_uzel1 <= "$uzel1")
{
if($pole[$x1][$y1] == "")
{
$pole[$x1][$y1] = soucet($pole[$x1-($jump/2)][$y1-($jump/2)],
$pole[$x1+($jump/2)][$y1-($jump/2)],
$pole[$x1-($jump/2)][$y1+($jump/2)],
$pole[$x1+($jump/2)][$y1+($jump/2)],
$min, $max);
$pocet_uzel1++;
}
$x1 = $x1 + $jump;
if($x1 >= "$rozmer")
{
$y1 = $y1 + $jump;
$x1 = $jump/2;
}
}
// následující počet uzlů v 2. části iterace je
// součet uzlů předcházejících - 1
$uzel2 = ($pocet_uzlu + $uzel1) - 1;
$x2 = $rozmer/(pow(2, $iterace));
$y2 = 0;
$jump = $x2;
// projede možné souřadnice pro 2/2 iterace
$pocet_uzel2 = "1";
while($pocet_uzel2 <= "$uzel2")
{
if($pole[$x2][$y2] == "")
{
$pole[$x2][$y2] = soucet($pole[$x2][$y2-$jump],
$pole[$x2-$jump][$y2],
$pole[$x2+$jump][$y2],
$pole[$x2][$y2+$jump],
$min, $max);
$pocet_uzel2++;
}
$x2 = $x2 + $jump;
if($x2 > "$rozmer")
{
$y2 = $y2 + $jump;
$x2 = 0;
}
}
$pocet_uzlu = $pocet_uzlu + $uzel1 + $uzel2;
$iterace++;
}
// nakonec získaná data vypíšeme do sloupců pod sebou
$x = "0";
$y = "0";
while($y <= "$rozmer")
{
while($x <= "$rozmer")
{
$x_zobraz = $x;
$y_zobraz = $y;
$pole_zobraz = $pole[$x][$y];
echo "$x_zobraz $y_zobraz $pole_zobraz<br/>";
if(!$pole[$x][$y])
{
echo " ";
}
$x++;
}
$x = "0";
$y++;
}
?>
Ukázky z výstupů:
diamond-square-algorithm1.png
diamond-square-algorithm2.jpg
