Algoritmus generování bludiště:

V následujícím textu vám ukážu jednoduchý algoritmus, jak vygenerovat náhodné dvourozměrné bludiště. Dá se použít pro vytvoření jednoduchému procházení (např. bludiště), ale může se použít i pro generování náhodných map do různých složitějších her.

Samotná myšlenka je vcelku jednoduchá - vytvoříme si body a hrany mezi nimi, v jednom z nich (libovolném) začneme a budeme je postupně spojovat dohromady. Nakonec můžeme určit nebo náhodně vybrat cíl.

Generování probíhá v cyklu:

1) označím si počáteční bod, že jsem ho už navštívil. Uložím ho do zásobníku.
2) načtu si bod na zásobníku. Když je prázdný, skončím.
3) jestliže jsem už byl ve všech jeho sousedech jdu na 2)
4) uložím bod zpět na zásobník
5) vyberu náhodného nenavštíveného souseda a uložím ho na zásobník.
6) zpět na 2

V algoritmu používám sice zásobník, ale stejně dobře to jde udělat i pomocí fronty - mělo by pak vyjít více košaté bludiště s kratšími chodbami. Výsledkem celého algoritmu ovšem bude bludiště tvaru strom - tj. povede sice přez všechny možné vrcholy, ovšem nikde nebude kružnice - cesta, kudy by hráč mohl bloudit do kolečka. To se dá ale jednoduše napravit. Stačí náhodně probourat několik zdí.

Při programování se dá použít dvourozměrné pole. Jak se dá předchozí povídání o hranách a bodech (vrcholech) snadno přepsat na program, ukážu raději na konkrétním případě.

Zvolím si čísla n a m. Vytvořím pole integerů o rozměrech (2*n+1)X(2*m+1), tj. chci pole vždy o lichých rozměrech. Celé bludiště vyplním číslem znamenající zeď (např. 1, nula bude volná cesta). Okraje pole vyplním číslem cesty (tj. vytvořím cestu okolo celého bludiště. Proč, to vysvětlím později) a zvolím si start. Ten volím vždyv lichém sloupci a lichém řádku, ale ne na okraji (například 2,2 pokud počítám od nuly). Pole o souřadnicích startu vyplním číslem cesty a začnu postupovat podle algoritmu.
Pozor - za souseda bodu o souřadnicích (x,y) budu brát body o souřadnicích (x-2,y),(x+2,y),(x,y+2) a (x,y-2). To, že jsem je už navštívil, poznám tak, že budou přepsány na cestu. Pokud jsem je nenavštívil, přepíšu nejen je, ale i bod mezi tím novým a starým. Pokud tedy bude (x+2,y) vybraný soused, přepíšu na cestu i pole o souř. (x+1,y).

Červené kolečko značí bod, do kterého jsme se někdy v průběhu algoritmu dostali. Teď se snažíme najít nějaké nenavštívené sousedy - červený křížek označuje ty navštívené, do kterých nechcem, zelená fajfka ty přípustné.

No, a ještě vysvětlení, proč jsme dělali cestu na okraji okolo bludiště - díky ní nemusíme kontrolovat, zda jsme neopustili pole a nepíšeme někam do okolní paměti. Je ale možné tu cestu nakreslit i jinak a potom můžeme vytvořit (skoro) kulaté bludiště, bludiště ve tvaru stromečku nebo jiné tvary.

Nakonec malá ukázka, jak tvorba bludiště postupuje:

.....................
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.....................




.....................
.XXXXXXXXXXXXXXXXXXX.
.X.XXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.....................


  
.....................
.XXXXXXXXXXXXXXXXXXX.
.X...XXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.....................




.....................
.XXXXXXXXXXXXXXXXXXX.
.X...X.....XXXXXXXXX.
.XXX.X.XXX.XXXXXXXXX.
.XXX...X.X.XXXXXXXXX.
.XXXXXXX.X.XXXXXXXXX.
.XXXXXXX...XXXXXXXXX.
.XXXXXXXXXXXXXXXXXXX.
.....................


.....................
.XXXXXXXXXXXXXXXXXXX.
.X...X.....X.......X.
.XXX.X.XXX.XXXXXXX.X.
.X.X...X.X.X...X...X.
.X.XXXXX.X.X.X.X.X.X.
.X...........X...X.X.
.XXXXXXXXXXXXXXXXXXX.
.....................