| Autor | Zpráva | ||
|---|---|---|---|
| Dase Profil * |
#1 · Zasláno: 27. 8. 2015, 18:42:05
Ahoj, pracuju na generátoru mapy pro jednu hru a potřeboval bych poradit. Mapu mám organizovanou jako jednorozměrné pole objektů kde každý má souřadnice [x, y]. Potřebuji z tohoto pole vybírat úseky náhodného tvaru které budou reprezentovat například jezera nebo lesy. Používám následující algoritmus, ale jeho problémem je, že mi uvnitř jezer vznikají ostrovy. Potřeboval bych použít nějaký lepší algoritmus. Nevím ani pořádně co mám vlastně googlit, proto píšu o radu sem, jestli někoho něco nenapadne.
Algoritmus funguje tak, že na začátku vybere náhodou bunku z mapy, z jejího okolí vezme náhodný prvek u něj znovu zjistí okolí a znovu vezme náhodný a tak pořád dál. Díky náhodnému výběru z okolí bodu mi vznikají uprostřed volná místa. start = nahodnaBunka(); //vybere prázdnou bunku (neobsahuje jezero)
i = 0;
while(i < velikostMapy / 10){ //jezero zabírá maximálně 1/10 mapy
sousedi = najdiSousedy(start) //Vrací pole buněk 8-okolí bodu
soused = nahodnySoused(sousedi) //zde je ten problém. Díky náhodnému výběru z pole vznikají ostrovy
soused->typ = jezero
start = soused
i++
}Děkuji za radu |
||
| juriad Profil |
Pro jezera jsem používal tuto metodu: www.playfuljs.com/realistic-terrain-in-130-lines
Vygenerovat si 3D terén a pak oříznout. Cokoli má výšku <= 0 je voda. Cokoli > 0 je země. Les také záleží na nadmořské výšce; původně byly snad všude, ale zemědělská činnost je z určitých ploch odstranila (z těch, které jsou dostatečně rovné). To můžeš zkusit detekovat a vytvořit tam pole/louky. A iterovat pro simulaci lidské činnosti. Možná by ten generátor šel zjednodušit: vygeneruješ si hodně hrubou mapu biotopů a pak ji budeš zjemňovat - počítat pravděpodobnosti (nikoli výšku) podle sousedů v hrubé mapě + nějaký šum. Můžeš začít třeba mapou 8 x 8, která je pokrytá náhodně a pak zjemňovat až na požadovanou velikost. V každém případě ti neuškodí si přečíst odkázaný článek. Mimochodem, jaké jsou požadavky na mapu: - realističnost - konečnost/nekonečnost/omezenost - jak moc vadí extrémní mapy (souostroví, vysoké hory)? |
||
| Dase Profil * |
#3 · Zasláno: 27. 8. 2015, 19:01:34
Díky za odpověď. bude to pouze 2D mapa, takže výšku nepotřebuji řešit. Ideální by bylo aby jezera, lesy a další objekty v mapě měli realističtější tvary. mapa má přesně danou velikost. Jednotlivé objekty na mapě nejsou zatím nic jiného, než prvek v poli označený jako jezero nebo les. nejde o grafiku. zatím je to jenom práce s polem.
|
||
| tiso Profil |
#4 · Zasláno: 27. 8. 2015, 20:01:51
A čo je zlé na ostrovoch? Prípadne čistinkách v lese?
Skús niečo ako: ak je 5+ susedov rovnakého typu (jazero, les), tak aj ja budem taký typ
|
||
| juriad Profil |
Ukázka zjemňovacího algoritmu:
<?php
# definice typů políček
$types = array('voda', 'les', 'louka', 'pole');
$marks = array('~', '#', '.', ',');
$probs = array(1, 2, 1, 0.5);
# počáteční velikost (2^start + 1)
$start = 0; # mapa 2x2
# koncová velikost (2^end + 1)
$end = 6; # mapa 65x65
# šum (relativně k počtu sousedů)
$noise = 0.2;
# vrátí náhodné pole podle distribuce
function randomType($probabilities) {
$prefix = array($probabilities[0]);
for ($i = 1; $i < count($probabilities); $i++) {
$prefix[$i] = $prefix[$i - 1] + $probabilities[$i];
}
$r01 = mt_rand() / mt_getrandmax();
$r = $r01 * $prefix[count($prefix) - 1];
$prev = 0;
for ($i = 0; $i < count($prefix); $i++) {
if ($prev < $r && $r < $prefix[$i]) {
return $i;
}
$prev = $prefix[$i];
}
return 0; # to be sure
}
# vygeneruje náhodnou počáteční mapu
$map = array();
for ($y = 0; $y <= 1 << $start; $y++) {
$map[] = array();
for ($x = 0; $x <= 1 << $start; $x++) {
$map[$y][$x] = randomType($probs);
}
}
# spočítá distribuci typů v okolí políčka a přidá šum
function calculateProbs($notypes, $map, $y, $x, $diagonal = FALSE, $noise) {
$around = array();
for ($t = 0; $t < $notypes; $t++) {
$c = 0;
if ($diagonal) {
$c += $map[$y-1][$x-1] == $t;
$c += $map[$y-1][$x+1] == $t;
$c += $map[$y+1][$x-1] == $t;
$c += $map[$y+1][$x+1] == $t;
} else {
if ($y > 0)
$c += $map[$y-1][$x] == $t;
if ($y < count($map) - 1)
$c += $map[$y+1][$x] == $t;
if ($x > 0)
$c += $map[$y][$x-1] == $t;
if ($x < count($map[0]) - 1)
$c += $map[$y][$x+1] == $t;
}
$r01 = mt_rand() / mt_getrandmax();
$r = $r01 * $noise * 2 - $noise; # (-$noise, $noise)
$around[$t] = max($c + $r, 0);
}
return $around;
}
# vypíše mapu
function printMap($map, $marks) {
for ($y = 0; $y < count($map); $y++) {
for ($x = 0; $x < count($map[$y]); $x++) {
echo $marks[$map[$y][$x]];
}
echo "\n";
}
echo "\n";
}
printMap($map, $marks);
# postupně zjemňuje mapu
for ($l = $start + 1; $l <= $end; $l++) { # increasing level of details
# expand map
$map2 = array();
for ($y = 0; $y <= 1 << $l; $y++) {
$map2[] = array();
for ($x = 0; $x <= 1 << $l; $x++) {
$map2[$y][$x] = $map[(int)$y/2][(int)$x/2];
}
}
$map = $map2;
# fill centers
for ($y = 1; $y <= 1 << $l; $y += 2) {
for ($x = 1; $x <= 1 << $l; $x += 2) {
$p = calculateProbs(count($types), $map, $y, $x, TRUE, $noise);
$map[$y][$x] = randomType($p);
}
}
# fill borders
for ($y = 0; $y <= 1 << $l; $y += 2) {
for ($x = 1; $x <= 1 << $l; $x += 2) {
$p = calculateProbs(count($types), $map, $y, $x, FALSE, $noise);
$map[$y][$x] = randomType($p);
}
}
for ($y = 1; $y <= 1 << $l; $y += 2) {
for ($x = 0; $x <= 1 << $l; $x += 2) {
$p = calculateProbs(count($types), $map, $y, $x, FALSE, $noise);
$map[$y][$x] = randomType($p);
}
}
printMap($map, $marks);
}
# vypíše mapu
for ($y = 0; $y < count($map); $y++) {
for ($x = 0; $x < count($map[$y]); $x++) {
echo $marks[$map[$y][$x]];
}
echo "\n";
}Ukázka jeho výstupu: .# ,# .## ..# ,.# ..### ..~## ....# ,..,, ,,..# ...~##### ...~####, ....~,### .....#~## .....#.## ,~...~.,# ,.....,., ........# ,.,,...,# ......~########## ....#.~#,#####,#, ......~##~######, ..,...~.##,#####, ........~,,###### ........,,,###### .........,##~##,# ..........###.### ..........#~.#### ....#....##~~.### ,,~.......~~..,,# ,,~.......~.....~ ,...........,,.., ...#............. ...........#....# ,...,.........,.. ,...,.,......,,## ............~#################### .............~#,,################ ........#..~~~##,###########,###, ...........~~~~###~########,####, .......~...~~#####~#############, ...........~~.######,#.#######,,, .#.,,..,...~~..#####,,#########,, ..........~~~..,,##,,,##########, .,...#..........~~,~,,########### ..,.............~~,,,,########### ...........#...,,,,,,,########### ...............,,,,##,####..#,,#~ .................,,##~#~~~#.#,,## ................,,,####~~~~##.,## .................,..#####~..##### .....#...............####.####### ...,.............~.###~~..#.##### .........##........##~~~~.#.##### ........#........##~##~~~..###### ...~~..............~##~~...,,,,## ,,,,~...............~~~,...,,,,## ,,,~~~..........#...~~..,........ ,#,~~~..............~...........~ ,##,................~...,......~, ,#.....................,,,,,...., .........................,,...... ......#..................,.,..... ...........#..............#.....# ...#.................##.........# ....................#####........ ,..#....,...................,,.#. ,......,,...,............,..,,,## ,......,,,..,,.....~.....,,,,,### ...............#.......~~####################################,### .~~.....................~~~~~,,,,#####################,########## .................#.#...~..~###,#,########################,####### .................#.....~.~~~~#######~###################,,####### .,..............#....~~~~~~~####,##############.########,#######, ,,,...................~~~~~~~######~~##################,,,#####,, .............#.......~~~~~~~~######~~#################,########,, ...............~.....~~~~~##~#######~~###########..###########~,, .......,......~~......~~~~##########~############.###,##########, ............#.,.......~~~~~.################..######~########,##, ......................~~~..#############,###.###############,,,,, ..#...,,,,...,........~~~~..#.##########,,,#.###############,,,,, .##..,,,,,...,,......#~~~.....#########,,,,###################,,, ...#.,,,.....,,.....~~~~~......#.######,,,,###################,,, .......,............~~~~~~....,#,####,,,,,,#####################, .,,...............~~...........,,,~#,,,,,,,############~######.## .,,,......#..#..................~~~#,~~~,,,############~######### .,....~.........................~~~~,,,~,,,,,#################### ....,,.........................~~~~~,,,,,,,###################### ......~...............#.......,~~,,~~,,,,,,,##################### .............,........##......,,,,,.,,,#,,,,#######.############# ............................,,,,,.,,,,,###,,######...##..##,,##,, ...,.........................,,,,,,,,,###,,,#######..,.##,,,,##~~ ...............................,,,,#,,,###~~##~####.######,,,,,~# ...............................~.,,,,,###~~~##~~~#~~##.##,,,,##~# .................,.............~..,,,,#####~##~~~~~~~##..#.,,#### .................,.............~,.,,,,########~~~~~~~#####.#,#### ....#....................,,.......,,,.,########~~~~~~~~##.##,#### ...................#..............,.....#########~~~....#.####### ..........~.......................,....##########~.......######## ..........#..............................######~##.##########,### ......,........,,,...............#~~##..#######~#..##########,,## ......,..........#.....~.#........~~.#######~~~~...###.########## .................###.#...............###~~#~,~##...#....######~## ..................####...............##~#~~~~~~~~~..##.########## ..,..~..............#............####~~~~##~~~~~~~...############ ................##...............##.#~~~###~~~~~~~....########### .........~.......#...................######~~~,,.....,##,###,#### ...,..~~~~...........................#~.####~~~......,,#,#,,,#### #..,,~~~~~~.............................~~~#~~~......,,,,,,,##### ,,,,,,,,~~.......................,......~~~~~~,......,,,,,,,,#### ,,,,,,~~~~......................###....~~~...~.......,,,,,,,,...# ,,,,,~~~~~~................#.~..##......~~~....~,,.......,....... ,,,,,~~~~~~~...................#.#....##.......,,,............... ,##,,,~~~~~............................#~..................,...,~ ,,,##,,,,~~..............................~~...,,,.............~.. ,,###,,,...............................~~~......,.............~#, ,,##.....................................~~...,,,,,....,......~~~ ,,##..........................................,,,,,,,,,,.......,, ,#.#............................~..............,,,,,,,.........,, .#.#.............................................,,,,~........... .............##....##............................,,,,,,,......... ...~........#................................#...~,,.,,,......... ,...........#..........#..........................~..,....~....## .......#..............#............................##...........# .....#.#....~.........#.,...........,.....#####.....#....#....... .....##...................................###...................# ......#....................................######..............## ...............~........................#.########.............#. ,.............,,........................#...##....~......,,,,##.. ,,....#........,,........,...................#.....#....,,,,.###. ,..##............,.................,...............#..,,,,,,,.##. ,,...........,,,,~.,....,,.......#................,....~,,,,,.### ,,.............,,,,,,##,,,,.............###.....,,,..,,,,,,,,,### ,,...........,,,,,,..#.,,~,,.........~~........#..,.,,,,,,,,##### Ostrovy občas vzniknou, ale lze je eliminovat zmenšením šumu. Ukázka generování mapy. |
||
| Dase Profil * |
#6 · Zasláno: 27. 8. 2015, 20:25:13
Díky tan algoritmus vypadá zajímavě, ale moc se mi nelíbí že se musí mapa procházet v tolika krocích. jestli tomu rozumím správně tak se nejprve vygenerují části náhodně a potom se pole znovu prochází a některé části co jsou blízko u sebe se spojují? Raději bych chtěl vylepšit algoritmus přímo toho generování, tak aby se nebrali náhodné prvky z okolí ale podle nějakého kritéria..
|
||
| juriad Profil |
Dase:
Ne. Vezme se malinkatá náhodná mapička: #. ~# #.. ### ~~# #,... ##... ##.## ~~### ~~~## O výkon se bát nemusíš, generování mapy není častá činnost. Zvládá to (bez paměťových optimalizací) mapu 513x513. Pro výpočet každého políčka jsou potřeba v průměru: 4 přístupy do paměti pro každý typ a jelikož menší mapa je čtvrtinová, přispěje zhruba #typů přístupy. V celku můžeme řict, že generování je stejně náročné jako projít celou velkou mapu 5*počet typů, to už není tak strašné, ne? To je pro 4 typy a velikost 513x513 jen 5 263 380 operací. Trošku jsem upravil zdroják a ukázku, aby byl zřejmý postup generování. |
||
| Dase Profil * |
#8 · Zasláno: 27. 8. 2015, 21:08:19
Ok zkusím tvůj algoritmus použít. díky za pomoc
|
||
|
Časová prodleva: 9 let
|
|||
0