Generovanie náhodného bludisko
Bludisko môže byť definované napr. Ako 2D pole hodnôt typu byte (alebo niečo podobne praktického), kde každý prvok tohto poľa predstavuje jedno políčko. Hodnoty políčok budeme potrebovať celkom tri:
- Nič (voľne priechodné políčko)
- Múr (nepriechodné políčko)
- Základ (imaginárny, využije sa len pri generovaní bludisko)
Pripravíme si základ bludisko:
Dookola je múr, políčka s krížikom znamenajú hodnotu "základ".
Budeme potrebovať nejakú funkciu, ktorá nám spočíta, koľko základov ešte v bludisku zostáva (prechádzame pole políčko po políčku a počítame hodnoty Základ - nič ťažké).
Tvorba bludisko prebieha takto. Najskôr náhodne vyberieme jedno základovej
políčko: spočítame základy, na výsledok použijeme funkciu Random, vyjde
číslo dajme tomu n. Potom prechádzame bludisko po riadkoch tak dlho, až
narazíme na n-tej základovej políčko:
Šípky znázorňujú štyri možné smery, ktorými môžeme viesť z políčka múr.
Teraz jeden z tých smerov náhodne zvolíme a začneme budovať múr.
Všetky voľná a základová políčka, na ktoré narazíme, sa mení na stene.
Skončíme, keď narazíme na inú stenu (preto musí byť bludisko na začiatku
ohraničené, aby nám múry neutiekli okolo):
Odtiaľ sa vrátime k náhodnému výberu základu a postavíme ďalšie
stenu a tak stále dokola, až kým všetky základová políčka v bludisku nie
sú zamurovaná:
A to je celé.
Výsledné bludisko má niekoľko príjemných vlastností:
- Medzi ľubovoľnými dvoma voľnými políčkami existuje vždy práve jedna možná cesta, ani viac, ani menej. To vyplýva z toho, že v bludisku nemôžu byť žiadne izolované "ostrovy" múrov, ktoré by neboli napojené na okraj.
- Všetky políčka označené tu na obrázku bodkou budú zaručene vždy
voľná, môžeme na ne teda podľa ľubovôle umiestniť štart, cieľ a
ďalšie veci:
Ak nám pripadá bludisko príliš ťažké na prejdenie, stačí na začiatku niekoľko náhodne vybraných základových políčok zmeniť na stenu - čím viac, tým jednoduchšie potom bludisko bude, pretože tým umožníme vznik izolovaných úsekov múrov, ktoré sa nedotýkajú okraje a idú teda obísť viacerými spôsobmi.
Ak máte radšej také bludisko, kde múry predstavujú tenké čiary na rozhraní medzi políčkami, nevadí. V pamäti počítača necháme bludisko uložené vo vyššie uvedenom formáte a modifikujeme iba procedúru, ktorá ho zobrazuje - nepárne riadky a stĺpce sa vykreslí ako čiary s nulovou šírkou, párne normálne ako štvorčeky.
