Lekce 2 - Generování náhodného bludiště
V minulé lekci, Šíření do šířky (Vlna), jsme si popsali algoritmus šíření do šířky (Vlna) k hledání cesty v bludišti mezi překážkami.
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.
V další lekci, Jak najít nejkratší cestu z bodu A do bodu B?, si popíšeme algoritmus pro hledání nejkratší cesty z bodu A do bodu B se zdrojovými kódy.
