El algoritmo Brushfire o Wavefront para grafos de Claridad presenta dos variantes, la de un solo emisor y la de varios emisores. Veremos las dos variantes.

Los grafos de claridad representan el mundo donde se mueven los agentes como medidas al obstáculo más cercano, es decir, se abstraen del entorno generando una representación más ligera del mismo y computacionalmente más apropiada.

Un ejemplo de grafo de claridad es el que vemos a continuación, en el se
pueden apreciar las distancias al objeto no travesable más cercano. En este
caso para simplificar el cálculo se divide en zeldas el mundo y se calcula a partir de
aqui. Para generalizar se define una unidad de grid o generalizada, que define que tamaño tiene cada una de ellas en pixels. Las unidades usarán tambien esta medida, por ejemplo un soldado ocupará 1×1 grids un tanque 2×2 …etc.

Conforme la complejidad del entorno crece, se necesitan los Grafos de claridad con varios tipos de terreno,
es decir, cada zelda vendrá identificada con un valor de terreno {agua/tierra/aire…etc}.

Para calcular este grafo de claridad se emplea el algoritmo Brushfire o tambien llamado wavefront.
Este algoritmo se utiliza tambien en robótica móvil para generar caminos de forma dinámica en función del entorno.
De esta forma, lo que aprendeis aqui os sirve también para cualquier entorno donde podamos dividir en
malla el mundo: robots moviles, juegos, aplicaciones industriales…etc. Esta variante se centra en la meta como único
emisor de la ‘Ola’

Cómo calculamos la distancia a los obstaculos. Lo vemos mediante un ejemplo, en el que de momento no se tienen en cuenta los tamaños de las unidades.

-Primero.Creamos el mundo
-Segundo. Rellenamos con los valores adecuados.
-Tercero. Aplicamos el Wavefront o Brushfire

>1.Creando el mundo

Lo primero que tenemos que hacer es calcular el mallado a partir de nuestro mundo. Esto se hará
como hemos comentado anteriormente definiendo el tamaño de malla y creando el entorno a partir de
estos valores.

>2. Rellenando con valores adecuados

En este paso definimos un punto de inicio y otro de meta. {Start/Goal points}

Marcamos todos los elementos de la malla que no son obstáculos con un 0
y todos los demás con un 1. El punto de meta lo marcamos con un 2, por ejemplo.

>3. Desde la casilla de meta aplicamos la ola o el wavefront asignando a todos los
valores adyacentes el valor de la casilla mas una unidad.

>4. Buscamos el camino recorriendo los adyacentes de la casilla desde el punto de
partida siempre disminuyendo en 1 los valores. Esto hace que sobre caminos cerrados
no se propague la ‘ola’ y siempre encuentre el camino a la meta, si este existe.

En este caso el camino será:
(0,7) -> (1,7) -> (2,7) -> (3,7) -> (4,7) -> (5,7) -> (6,7) -> (7,7)
-> (8,7) -> (9,7) -> (10,7) -> (10,6) -> (11,6) -> (11,5) -> (12,5) ->
(12,4) -> (12,3) -> (13,3) -> (13,2) -> (14,2) -> (14,1) -> (15,1) -> (15,0)

Este es uno de los métodos más sencillos para aplicar pathfinding, hay otros mucho más
eficientes que veremos posteriormente. Lo siguiente será ver la variante de este algoritmo donde no solo el destino genera la ‘Ola’ sino cada obstáculo es emisor, por lo que se puede aplicar a diferentes tamaños de unidades.

Hasta la próxima!