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

V předchozím dílu jsem předvedl jednoduchý algoritmus pro vytváření náhodně generovaných bludišť. Dnešní díl předvede, jakým způsobem se tento algoritmus dá upravit, aby generoval uzavřené místnosti, propojené mezi sebou dveřmi takovým způsobem, aby bylo možné se do každé místnosti dostat.

První část nového algoritmu bude podobná tomu z předchozího dílu, rozdíl je v tom, že místo jedné stěny generujeme z jedné značky stěny hned dvě. Tím pádem nám místo bludiště vznikne spousta zajímavě tvarovaných chodeb. Stále platí omezení pro hodnoty W, H, S, Ch, viz předchozí díl.

Algoritmus pro generování místností

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)
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é r z množiny {0, 1, 2, …, h – 1}
   2. Zvolme náhodný směr d1 z množiny {nahoru, doleva, dolů, doprava }
   3. Zvolme náhodný směr d2 z množiny {nahoru, doleva, dolů, doprava }
   4. Najděme souřadnice s rté značky v poli
   5. Pole[s] nastavíme na jedna
   6. Vytvoříme si pomocné proměnné s1 a s2, s1 je s posunuté ve směru d1, s2 je s posunuté ve směru d2
   7. Pro obě s1, s2 (dále indexované jako sn)
      1. Dokud pole[sn] není rovno 1
         1. Nastavme pole[s] = 1
         2. Upravme sn podle dn
6. Spočítejme si nový počet značek v poli a zaktualizujme hodnotu h

Algoritmus se v popisu dost rozšířil, ale pokud jste si z minulého dílu stáhli zdroják, tak si můžete povšimnout, že opravdový rozdíl je jen ve funkci drawLine, kterou je třeba upravit. Taktéž se vyplatí zmínit, že pokud vztáhnete na směry d1 a d2 podmínku, že musí být různé, taktéž tím dost ovlivníte variabilitu produkovaných místností. Tak jak tak, vygenerované místnosti nyní vypadají třeba takto:

Místnosti jsou ale teď samostatně stojící. Rádi bychom, aby bylo možné se do každé místnosti dostat, otázka ale je, jakou cestou. Můžeme propojit každou místnost se všemi jejími sousedy nebo můžeme být vychytralejší a aplikovat na problematiku třeba hledání kostry grafu, čímž značně upravíme flow hráčova postupu úrovní. Tak jak tak, v následujícím algoritmu jsou jakékoli podobné hrátky volitelné a snadno parametrizovatelné.

Generování dveří

1. Vytvořme si čítač cnt a nastavme ho na hodnotu -1
2. Pro každý prvek p pole
   1. Pokud p je rovno nule, pak od tohoto prvku spustíme semínkové vyplňování tak, aby všechny sousední prvky (a taky prvek p) nabyly hodnoty cnt
   2. Odečteme 1 od cnt
3. Hodnotu cnt vynásobíme -1. Hodnota cnt nám nyní říká, kolik separátních místností v poli máme. Zároveň je každá místnost indexovaná hodnotou všech svých prvků
4. Sestavíme orientovaný graf sousedních místností. Hrany jdou od místností s nižším indexem do místností s vyšším indexem
5. Volitelný krok – orientovaný graf zredukujeme na kostru grafu, algoritmus je blíže popsán zde
6. Pro každou hranu h grafu, která vede z místnosti m1 do místnosti m2
   1. Najdeme seznam l všech prvků pole, které mají hodnotu 1 (stěna) a sousedí s prvkem místnosti m1 i m2
   2. Náhodně vybereme jeden prvek z l a nastavíme ho na 0 (nebo libobolnou hodnotu označující dveře)
7. Pomocí semínkového vyplňování smažeme pomocné hodnoty pro identifikaci místností

A je hotovo! Oba dva algoritmy vypadají asi dost vyčerpávající, ve skutečnosti jde ale jen o rozšíření kódu z minula. Výsledný kód nakynul na dvojnásobek, což ale stále pouhých cca 350 řádků kódu. Zdrojový kód si můžete stáhnout zde, pod článkem se můžete pokochat screeny s výsledky. První dva propojují každou místnost se všemi sousedy, poslední používá kostru grafu pro výpočet dveří. Ostatní parametry:

W = 45
H  = 21
Ch = 3
S = 4

Poznámka na závěr

Moje řešení není zrovna paměťově jednoduché, pokud výrazně zvětšíte velikost mapy. Pokud by velikost mapy byla 101×101 a Ch bylo 4, tak se dostáváme na cca 400 místností na mapu, což zjednodušeným odhadem vede na 400×400 vrcholů grafu. Jelikož používám std kontejnery a dynamickou reallokaci paměti, program velice snadno může spadnout na nedostatku paměti. Podobný problém může mít funkce pro semínkové vyplňování. Využití fronty pro ukládání souřadnic pro další zpracování sice zamezí spadnutí na zaplnění programového zásobníku, ale i fronta může vyčerpat paměť stejně dobře.

< 1. díl | 3. díl >