[Seriál] Generujeme herní úrovně, 1. díl

Napadlo mě, že by mohlo být zajímavé udělat seriál o různých algoritmech, které můžete použít ve svých hrách pro generování úrovní. Pochopitelně nejlepší hry používají velice specifické algoritmy, často na míru dělané, trocha inspirace ale nikdy neuškodí. Všechny mapy jsou „tile-based“, což znamená, že jsou tvořeny čtverci (přesněji řečeno obdélníky). Zajímá vás to? Čtěte dál!

Dnešní algoritmus bude velice jednoduchý na napsání, má cca 150 řádků v C++. Jeho využití spočívá v budování bludišť. Krásné na tomto algoritmu je to, že všechna místa jsou dosažitelná za každých okolností, což výrazně usnadňuje umisťování důležitých míst do úrovně. Zároveň, pokud chcete, můžete mít v úrovni i větší místnosti s nějakým tím sloupem.

Nevýhodou je například fixní šířka chodeb, fixní šířka stěn a také podmínky kladené na rozměry úrovně. Mapa je navíc vždy striktně obdélníková. Pokud jste ale stále zvědaví na algoritmus samotný, pokochejte se screenshotem níže a jde se na věc.

Prerekvizity

Mějme šířku chodby Ch, šířku mapy W, výšku mapy H a počet sloupů S, splňující následující podmínky (N i M jsou libovolná přirozená čísla):
1 <= Ch
0 <= S
W = (Ch + 1) * N + 1
H = (Ch + 1) * M + 1

Algoritmus

1. Vytvořme si 2D pole čísel o rozměrech W * H a naplňme ho nulami (nula znamená prázdný vzduch)
2. Prvky pole, které jsou na souřadnicích [x;y], kde x i y jsou násobky hodnoty Ch + 1, nastavme na hodnotu 2 (značka)
3. Kraje pole vyplňme hodnotami 1 (stěna). V tomto bodě pole vypadá asi takto:
4. Vytvořme si proměnnou h a uložme do ní sumu všech značek v poli (všech prvků s hodnotou 2)
5. Dokud je h > S
   1. Zvolme náhodné číslo r z množiny {0, 1, 2, …, h – 1}
   2. Zvolme náhodný směr d z množiny {nahoru, doleva, dolů, doprava}
   3. Najděme souřadnice s r-té značky v poli
   4. Dokud pole[s] není rovno 1
      1. Nastavme pole[s] = 1
      2. Upravme s podle d (pokud je d nahoru, s posuneme o jedna nahoru, atp)
   5. Spočítejme si nový počet značek v poli a zaktualizujme hodnotu h

A je hotovo! Tedy skoro… Pokud hodnota S je větší než nula, musíme ještě všechny zbývající značky změnit na stěny a pak máme hotovo. A jaké jsou výsledky? Podívejte se níže na obrázky! To je ode mě všechno pro tento díl seriálu, těště se na další díl!

A ještě poznámka na závěr, ukázkové levely jsou vygenerovány s parametry:
Ch = 2
S = 4
W = 61
H = 28

Pokud máte zájem o konkrétní implementaci v C++, wordpress mi nedovolí nasdílet nic moc rozumějšího, než pdf, tak tady to tedy je v pdf – mapgen1

2. díl >