En el anterior artículo hemos visto que en el algoritmo de Brushfire
sencillo podemos encontrar un camino aplicando un valor creciente desde
el punto de destino propagando valores hasta el punto final.

Esto sin embargo, no genera un grafo adecuado para ser calculado desde
cualquier punto sino que es necesario propagar la ‘ola’ para cada una
de las posiciones de destino.

La variante que se propone ahora es válida para cualquier posición del
entorno. En este caso cada elemento no travesable, es decir, cada obstáculo
es considerado como un generador de ‘Ola’ por lo que en cada posición
se representará la distancia al obstáculo más cercano.

El procedimiento de cálculo será el que vemos en la fotografía inferior.

Definido en pseudocódigo lo podremos calcular de la siguiente manera para conectividad 4:

check node A at [0][0]

now look north, south, east, and west of this node
(boundary nodes)

if (boundary node is a wall)
ignore this node, go to next node B

else if (boundary node is robot location && has a number in it)
path found!
find the boundary node with the smallest number
return that direction to robot controller
robot moves to that new node

else if (boundary node has a goal)
mark node A with the number 3

else if (boundary node is marked with a number)
find the boundary node with the smallest number
mark node A with (smallest number + 1)

if (no path found)
go to next node B at [0][1]
(sort through entire matrix in order)

if (no path still found after full scan)
go to node A at [0][0]
(start over, but do not clear map)
(sort through entire matrix in order)
repeat until path found

if (no path still found && matrix is full)
this means there is no solution
clear entire matrix of obstacles and start over
this accounts for moving objects! adaptivity!

Os incluyo el código fuente de la variante más sencilla del algoritmo de
Wavefront para que modifiqueis libremente y lo convirtais en la variante
que se explica aqui.

>Codigo fuente del algortimo Wavefront, cortesía de John Palmisano

Nos vemos!