Šírenia do šírky (Vlna)

Určite poznáte hru Pac-man. Žltý koláčik, požierajúci bobuľky, ktorý je však prenasledovaný niekoľkými bubáky.

Zaujíma vás, ako docieliť, aby prízrak našiel danú cestu ku koláčika? Presne k tomu sa používa tento algoritmus, známy tiež pod názvom "vlna". Slúži na vyhľadanie cesty medzi prekážkami v dvojrozmernom poli.

Priebeh

Dajme tomu, že sa potrebujeme dostať z bodu S do bodu F:

Do fronty zapíšeme bod S a dáme mu hodnotu 0.

Fronta: [4; 7]

Vyberieme 1. bod vo fronte (teda [4; 7]) a ak je v jednom zo 4 smerov voľno, urobíme tam hodnotu o jednu väčšiu, než je bod sám (bod S je nula, takže tam napíšeme jednotku). Ja som si zvolil, že prvý urobím tú hore, potom naľavo, dole a posledná tú vpravo:

Políčka, na ktoré sme položili jedničky, si zapíšeme do fronty.

Fronta: [4; 6] [3; 7] [4; 8] [5; 7]

Opäť vyberieme 1. bod vo fronte ([4; 6]) a systémom hore, doľava, dole, doprava napíšeme do políčok, ktoré sú prázdne, číslo, ktoré je zase o jednu väčšiu, než to z frontu (takže 2). Body opäť pridáme do fronty.

Fronta: [3; 7] [4; 8] [5; 7] [5; 6]

Toto sa stále opakuje ...

... kým nie je okolo políčka, ktoré sme zobrali z frontu, políčko F:

Teraz je krásne vidieť zostupne očíslovaná cesta od políčka F k políčku S. Stačí len sa prejsť od F k S technikou: či je hore alebo vľavo alebo dole alebo vpravo číslo o jednu menšiu, než to, na ktorom stojím. Čísla si ukladám obrátene do fronty, aby som mal súradnicu políčka F na konci.

Tak a je to, vo fronte máme zapísanú cestu bod po bode, ako sa dostať od bodu S do bodu F.