Generování náhodného bludiště
Algoritmy Bludiště Generování náhodného bludiště


Bludiště může být definováno např. jako 2D pole hodnot typu byte (nebo něco podobně praktického), kde každý prvek tohoto pole představuje jedno políčko. Hodnoty políček budeme potřebovat celkem tři:
- Nic (volně průchodné políčko)
- Zeď (neprůchodné políčko)
- Základ (imaginární, využije se jen při generování bludiště)
Připravíme si základ bludiště:
Kolem dokola je zeď, políčka s křížkem znamenají hodnotu "základ".
Budeme potřebovat nějakou funkci, která nám spočítá, kolik základů ještě v bludišti zbývá (procházíme pole políčko po políčku a počítáme hodnoty Základ - nic těžkého).
Tvorba bludiště probíhá takto. Nejdřív náhodně vybereme jedno
základové políčko: spočítáme základy, na výsledek použijeme funkci
Random, vyjde číslo dejme tomu n. Potom procházíme bludiště po řádcích
tak dlouho, až narazíme na n-té základové políčko:
Šipky znázorňují čtyři možné směry, kterými můžeme vést z políčka
zeď.
Nyní jeden z těch směrů náhodně zvolíme a začneme budovat zeď.
Všechna volná a základová políčka, na která narazíme, se mění na zdi.
Skončíme, když narazíme na jinou zeď (proto musí být bludiště na
počátku ohraničené, aby nám zdi neutekly okolo):
Odtud se vrátíme k náhodnému výběru základu a postavíme další zeď
a tak pořád dokola, dokud všechna základová políčka v bludišti nejsou
zazděná:
A to je celé.
Výsledné bludiště má několik příjemných vlastností:
- Mezi libovolnými dvěma volnými políčky existuje vždy právě jedna možná cesta, ani víc, ani míň. To vyplývá z toho, že v bludišti nemohou být žádné izolované "ostrovy" zdí, které by nebyly napojeny na okraj.
- Všechna políčka označená zde na obrázku tečkou budou zaručeně vždy
volná, můžeme na ně tedy dle libosti umístit start, cíl a další věci:
Pokud nám připadá bludiště příliš obtížné na projití, stačí na začátku několik náhodně vybraných základových políček změnit na zeď - čím víc, tím jednodušší pak bludiště bude, protože tím umožníme vznik izolovaných úseků zdí, které se nedotýkají okraje a jdou tedy obejít více způsoby.
Jestli máte radši takové bludiště, kde zdi představují tenké čáry na rozhraní mezi políčky, nevadí. V paměti počítače necháme bludiště uložené ve výše uvedeném formátu a modifikujeme jenom proceduru, která ho zobrazuje - liché řádky a sloupce se vykreslí jako čáry s nulovou šířkou, sudé normálně jako čtverečky.
Komentáře


Zobrazeno 10 zpráv z 13. Zobrazit vše