Lekce 1 - Šíř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.

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.

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 další lekci, Generování náhodného bludiště, si popíšeme algoritmus pro generaci náhodného bludiště.