dodání ihned! nové
Hledáme programátora do rostoucího týmu ITnetwork.cz, 100% home office, 100% flexibilní pracovní doba. Více informací
Black Friday je tu! Využij jedinečnou příležitost a získej až 80 % znalostí navíc zdarma! Více zde
BF

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).

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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
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.

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.


 

Předchozí článek
Šíření do šířky (Vlna)
Všechny články v sekci
Algoritmy pro bludiště
Přeskočit článek
(nedoporučujeme)
Jak najít nejkratší cestu z bodu A do bodu B?
Článek pro vás napsal Mircosoft
Avatar
Uživatelské hodnocení:
11 hlasů
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 :-).
Aktivity

 

 

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

Avatar
hocikto19
Člen
Avatar
hocikto19:16.6.2014 17:12

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ý:16.6.2014 17:19

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:16.6.2014 17:32

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:16.6.2014 17:34

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:16.6.2014 18:30

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
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Pavol Hejný
Člen IT Redactor Gang
Avatar
Pavol Hejný:17.3.2015 23:43

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

Odpovědět
17.3.2015 23:43
/^(web )?(app )?developer$/
Avatar
koZis
Člen
Avatar
koZis:4.9.2015 15:34

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

 
Odpovědět
4.9.2015 15:34
Avatar
Virlupus
Redaktor
Avatar
Virlupus:11.3.2019 1:46

Dost dobrý a trochu jsem si s tím hrál... zatím není celý http://virlupus.cz/…/src/blud.py

 
Odpovědět
11.3.2019 1:46
Avatar
Josef Kahoun
Člen
Avatar
Josef Kahoun:9. května 19:28

Hotové řešení JS:
https://github.com/…azeGenerator

 
Odpovědět
9. května 19:28
Avatar
Kryštof Krátký:11. května 10:59

Hotové řešení online ;)
https://krystofex.github.io/…enerator-js/

 
Odpovědět
11. května 10:59
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 16. Zobrazit vše