BF Summer sales
Pouze tento týden sleva až 80 % na HTML & CSS a JavaScript
80 % bodů zdarma na online výuku díky naší Letní akci!

Šíř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 zapíšeme bod S a dáme mu hodnotu 0.

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

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áme 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:

Nyní je krásně vidět sestupně očíslovaná cesta od políčka F k políčku S. Stačí jen se projít 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.


 

Všechny články v sekci
Algoritmy pro bludiště
Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
13 hlasů
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 sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity (2)

 

 

Komentáře

Avatar
Laaca
Neregistrovaný
Avatar
Laaca:23.10.2006 12:22

Perfektně jsi vysvětlil prohledávání do šířky. Fakt dobrý!

 
Odpovědět
23.10.2006 12:22
Avatar
Minexew
Neregistrovaný
Avatar
Minexew:9.2.2008 21:36

ten motion planning je fakt cool, dikes :)

 
Odpovědět
9.2.2008 21:36
Avatar
...
Neregistrovaný
Avatar
...:9.2.2008 22:15

a ten genarator dungu bych bral :D ;)

 
Odpovědět
9.2.2008 22:15
Avatar
sdraco
Tým ITnetwork
Avatar
sdraco:10.2.2008 22:30

OK, přidám ho.... Do konce měsíce tu bude :)

Odpovědět
10.2.2008 22:30
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Collodi
Neregistrovaný
Avatar
Collodi:23.4.2008 18:56

Ja bych zde uvital ten generator bludiště, dost me zaujal ten algoritmus jak z A do B pomoci alg. vlny-proste krasa :-)

 
Odpovědět
23.4.2008 18:56
Avatar
john02
Neregistrovaný
Avatar
john02:10.2.2009 18:19

mas to tu super. s pascalem teprve zacinam a tak obcas jen kopiruju a nevim co vlastne pisu, ale zacinam tomu vsemu prichazet na kloub :)

 
Odpovědět
10.2.2009 18:19
Avatar
franta
Neregistrovaný
Avatar
franta:17.11.2009 14:06

tohle je moc hezky udelané. Děkuju

 
Odpovědět
17.11.2009 14:06
Avatar
mishan
Neregistrovaný
Avatar
mishan:3.3.2010 21:49

Dik, hodilo se mi to pri simulaci dopravniho systemu co sme dostali za ukol. Bylo to rychlejsi nez to co nas ucil ucitel.:D

 
Odpovědět
3.3.2010 21:49
Avatar
Umbra et Mors
Neregistrovaný
Avatar
Umbra et Mors:21.10.2010 22:09

Díky moc za článek. Vlna mi moc pomůže při úloze - hledání cesty ve dvourozměrném prostoru :):)

 
Odpovědět
21.10.2010 22:09
Avatar
Witiko
Neregistrovaný
Avatar
Witiko:29.3.2011 14:36

Pěkný článek. Jenom bych ale dodal, že právě zmiňovaný Pacman A* nevyužívá, hledí vždy jen o pole dopředu. Viz. http://gameinternals.com/…ost-behavior :)

 
Odpovědět
29.3.2011 14:36
Avatar
m.chalupova
Člen
Avatar
m.chalupova:29.3.2011 15:20

A tohle děláte v jakém programu?
Můžu se zeptat, jakou školu zmiňujete? Myslím obor.

 
Odpovědět
29.3.2011 15:20
Avatar
sdraco
Tým ITnetwork
Avatar
Odpovídá na Magda
sdraco:29.3.2011 20:49

Na programu nezáleží, algoritmus je obecný postup, který může být implementován v kterémkoli jazyce. Když si rozkliknete v menu Programování, je tam jejich seznam.

Odpovědět
29.3.2011 20:49
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
m.chalupova
Člen
Avatar
Odpovídá na David Čápka
m.chalupova:29.3.2011 22:01

Aha, budu to muset všechno pročíst.;)

 
Odpovědět
29.3.2011 22:01
Avatar
OBU
Redaktor
Avatar
OBU:21.11.2013 20:56

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

 
Odpovědět
21.11.2013 20:56
Avatar
anonyimek
Člen
Avatar
anonyimek:24.12.2013 0:11

paradne diki moc :)

 
Odpovědět
24.12.2013 0:11
Avatar
vfsdfsdfdsf
Člen
Avatar
vfsdfsdfdsf:18.1.2014 13:00

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

 
Odpovědět
18.1.2014 13:00
Avatar
a3228823
Člen
Avatar
a3228823:8.5.2014 10:00

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:27.7.2014 18:13

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

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

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:4.9.2015 15:35

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:4.7.2016 17:26

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

 
Odpovědět
4.7.2016 17:26
Avatar
hocikto19
Člen
Avatar
hocikto19:4.10.2016 12:54

nie je to klasicky djikstrov algoritmus - vyhladavanie do sirky?

Odpovědět
4.10.2016 12:54
Multum in parvo.
Avatar
Vlado Cukalovsky:4.10.2016 15:44

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.10.2016 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 23 zpráv z 23.