Šíření do šířky (Vlna)

Algoritmy Bludiště Šíření do šířky (Vlna)

Určitě znáte hru Pac-man. Žlutý koláček, požírající bobulky, který je však pronásledován několika bubáky.

Pacman

Zajímá vás, jak docílit toho, aby bubák nalezl danou cestu ke koláčku? Přesně k tomu se používá tento algoritmus, známý také pod názvem "vlna". Slouží k vyhledání cesty mezi překážkami v dvourozměrném poli.

Průběh

Dejme tomu, že se potřebujeme dostat z bodu S do bodu F. Do fronty tedy zapíšeme bod S a dáme mu hodnotu 0.
Fronta : [4;7]

Vyjmeme 1. bod ve frontě (tedy [4;7]) a pokud je v jednom ze 4 směrů volno, uděláme tam hodnotu o jednu větší, než je bod sám (bod S je nula, takže tam napíšeme jedničku). Já jsem si zvolil, že první udělám tu nahoře, pak nalevo, dole a poslední tu vpravo. Políčka, na které jsme položili jedničky, si zapíšeme do fronty.
Fronta : [4;6][3;7][4;­8][5;7]

Opět vyjmeme 1. bod ve frontě ([4;6]) a systémem nahoru, doleva, dolů, doprava napíšeme do políček, které jsou prázdné, číslo, které je zase o jednu větší, než to z fronty (takže 2). Body opět přidám do fronty.
Fronta : [3;7][4;8][5;­7][5;6]

Toto se stále opakuje...
...

...dokud není kolem políčka, které jsme sebrali z fronty, políčko F. Teď je krásně vidět sestupně očíslovaná cesta od políčka F k políčku S. Nyní stačí jen projít se od F k S technikou: jestli je nahoře nebo vlevo nebo dole nebo vpravo číslo o jednu menší, než to, na kterém stojím. Čísla si ukládám obráceně do fronty, abych měl souřadnici políčka F na konci.
Tak a je to, ve frontě máme zapsanou cestu bod po bodu, jak se dostat od bodu S do bodu F.


 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

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


 


Miniatura
Všechny články v sekci
Algoritmy pro bludiště
Miniatura
Následující článek
Generování náhodného bludiště

 

 

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

Avatar
OBU
Redaktor
Avatar
OBU:

boží :D :D ... některý věci se jenom jako složité tváří :P

 
Odpovědět  +1 21.11.2013 20:56
Avatar
anonyimek
Člen
Avatar
anonyimek:

paradne diki moc :)

 
Odpovědět  +1 24.12.2013 0:11
Avatar
Iwitrag
Člen
Avatar
Iwitrag:

Tak to je super :D A teď pro non-grid aplikace :D

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

Nejaký algoritmus na riešenie tohto hlavolamu?

CrazyCube - http://www.abelmartin.com/…zy_cube.html
alebo - http://www.superhry.cz/games/775/

Prípadne tip?

 
Odpovědět 8.5.2014 10:00
Avatar
PiskotPiskotovic
Redaktor
Avatar
PiskotPiskotovic:

Nikdy jsem nevěděl že je to tak lehký :D Úžasný článek, Davide ;)

Odpovědět  +1 27.7.2014 18:13
Error 404 - stránka motto.php nenalezena.
Avatar
Grimor
Člen
Avatar
Grimor:

Já to asi nechápu. "jestli je nahoře nebo vlevo nebo dole nebo vpravo číslo o jednu menší, než to, na kterém stojím." tak co? Ta věta není dokončena a z kontextu to nemůžu pochopit. Jestli začínáme od S a jdeme na jedničku nahoře, tak potom můžeme jen na dvojku a jsme někde úplně jinde a k tomu zaseknutí.

 
Odpovědět 13.9.2014 22:45
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:35
Avatar
rail52
Člen
Avatar
Odpovídá na Grimor
rail52:

Grimore jelikož si bot cestu značí pozpátku tak vždy dojde tam kam má :)

 
Odpovědět 4. července 17:26
Avatar
hocikto19
Člen
Avatar
hocikto19:

nie je to klasicky djikstrov algoritmus - vyhladavanie do sirky?

Odpovědět 4. října 12:54
Multum in parvo.
Avatar
Vlado Cukalovsky:

ano ak pouzijes dijkstru pri neohodnetom grafe(cize urcis kazdej hrane rovnaku hodnotu) tak ano je to rovnake ako vyhladvanie do sirky, ale dijkstra sa pouziva pri ohodnotenom grafe, kde cena cesty k jednemu bodu moze byt upravena, ak sa nasla lacnejsia cena

 
Odpovědět 4. října 15:44
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 23. Zobrazit vše