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ě:
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:
náhodně vybrané 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):
zedničina

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á:
nové políčko...  ...a nová zeď  hotové bludiště

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: volná políčka

 

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.


 

  Aktivity (1)

Článek pro vás napsal Mircosoft
Avatar
Autor je amatérský pascalista, assemblerista a bastlíř. Profesionálně psal nebo píše v HLASM, Rexxu, Cobolu, ST, LAD, FBD, PHP, SQL, JS, Basicu a pár dalších jazycích, které kupodivu stále existují a používají se :-).

Jak se ti líbí článek?
Celkem (9 hlasů) :
55555


 


Miniatura
Předchozí článek
Šíření do šířky (Vlna)
Miniatura
Všechny články v sekci
Algoritmy pro bludiště

 

 

Komentáře
Zobrazit starší komentáře (3)

Avatar
Awaraine
Člen
Avatar
Awaraine:

Moc dobrý článek, hned jsem si to naprogramoval a zjistil, že při omezení délky budovaných zdí na větších mapách vzniká více možných cest (které se celkem hodí při hledání nejkratší cesty) a zároveň to vypadá líp, když nejsou zdi téměř přes celé bludiště.

 
Odpovědět  +2 22.8.2013 19:16
Avatar
ondrejkuhejda:

Super článek. Navíc se pak dá kód jednoduše modifikovat. Moc dík.

 
Odpovědět 18.10.2013 15:48
Avatar
Iwitrag
Člen
Avatar
Iwitrag:

Tak to je opravdu super, dá se to pak krásně přizpůsobovat a jednoduše "naseedovat" :) klobouk dolů

Odpovědět 18.1.2014 13:05
Učím se ostře vidět.
Avatar
hocikto19
Člen
Avatar
hocikto19:

Implementoval som to pod javascriptom a mám taký problém, že mi to zvykne občas zamurovať vchod, alebo východ. Dá sa to ošetriť aj inak, ako tým, že tam implementujem pathfinding ako overenie, ktorý keď zlyhá, tak vygeneruje novú mapu?

Link: http://kovko.yweb.sk/…o/index.html

Odpovědět 16.6.2014 17:12
Multum in parvo.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na hocikto19
Jan Vargovský:

Dej si tam počet políček (výška, šířka) lichý, pak ti to vygeneruje lépe a nebudeš tam mít takové dvojstěny.

 
Odpovědět 16.6.2014 17:19
Avatar
hocikto19
Člen
Avatar
Odpovídá na Jan Vargovský
hocikto19:

No to som spravil. Vyzerá to síce lepšie, ale nerieši to môj problém.

Odpovědět 16.6.2014 17:32
Multum in parvo.
Avatar
hocikto19
Člen
Avatar
Odpovídá na hocikto19
hocikto19:

Ešte som trochu skrátil maximálnu dĺžku stien a potom sa mi to na asi 20 pokusov neobjavilo. Uvidíme, či to je riešenie, alebo len náhoda. Každopádne zatiaľ ďakujem.

Odpovědět 16.6.2014 17:34
Multum in parvo.
Avatar
Mircosoft
Redaktor
Avatar
Mircosoft:

Jediná podmínka úspěchu jsou dvě liché věci: rozměry bludiště a souřadnice startu a cíle (pokud je počítáš od nuly). Pak si je nezazdíš, ani kdybys chtěl.

Zdroják z mobilu nezkontroluju, ale zvenku se ti to chová naprosto správně.

 
Odpovědět 16.6.2014 18:30
Avatar
Pavol Hejný
Redaktor
Avatar
Pavol Hejný:

Díky moc za skvělý článek! Rozhodně tenhle princip použiju.

Odpovědět 17.3.2015 23:43
http://pavolhejny.cz/
Avatar
koZis
Člen
Avatar
koZis:

Díky za úvod do problematiky, ušetřilo mi to mnoho šedin!

 
Odpovědět 4.9.2015 15:34
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

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