En primer lugar vamos a definir con palabras comunes el significado de Pathfinding.
Pathfinding es la idea de varios algoritmos que podemos llamarlos de AI (Inteligencia Artificial) con el cual podemos buscar caminos en un mapa virtual, ya sea creado a raíz de un lugar físico o netamente virtual, uniendo dos puntos, recorriendo la menor distancia posible y esquivando todos los obstáculos que pueda tener el terreno.
Hay mucha variedad de este tipo de algoritmo, y el uso de los mismos depende del tipo de terreno (mapa) a recorrer como asi también su tamaño y dimensiones (2D y 3D).
En esta primera parte voy a explicar uno de los algoritmos de Pathfinding mas fáciles de realizar, así como es el más fácil también tiene sus limitaciones, y ellas son que este algoritmo no lo podemos utilizar en mapas o terrenos demaciados grandes, como por ejemplos los mapas del WOW, ya que serían demaciados lentos para la busqueda de los caminos y cuando hablamos de grande nos referimos a cientos de miles de millones de nodos, si así como lo lee, cientos de miles de millones.
ALGORITMO SONAR
1.- COMO NACIO EL SONAR.
Este algoritmo de pathfinding nació del estudio del estupendo algoritmo de pathfinding desarrollado por Elthan: el algoritmo “Ameba”.
De hecho el “Sonar” se puede considerar como un “Ameba” mejorado.
2.- POR QUE SE LLAMA “SONAR”.
Porque funciona igual que el sonar de un barco. Emite una onda que recorre toda la tabla de nodos y de una sola pasada calcula el valor de los cuadros.
3.- QUE TIENE EL SONAR QUE MEREZCA LA PENA.
Rapidez. Es tremendamente rápido. Tal vez sea el más rápido. En tablas relativamente chicas.
Sencillez. Si lo comparamos con otros algoritmos de pathfinding.
4.- FUNCIONAMIENTO GENERAL DEL “SONAR”.
Partimos de una tabla (array) de dos dimensiones.
Esta tabla es como un mapa cuadriculado del escenario donde se va a desarrollar el juego o rutina donde queremos aplicar el Sonar.
Las dimensiones de la tabla dependen del nivel de exactitud con el que queremos dotar al movimiento de los personajes así como de la naturaleza del escenario.
Por ejemplo: Tenemos una matriz de 4000×4000 en sus ejes X y Z. Supongamos que es un terreno más o menos plano y sin obstáculos. El objetivo del juego es escapar del ataque de unos bichitos redondos que nos persiguen.
El Sonar le indicará a esos bichitos el camino a seguir para darnos alcance.
Si el tamaño del bichito es, por ejemplo, de 36, con una tabla de 40×40 nodos tendríamos suficiente. Si la tabla es de 40×40 quiere decir que entre nodo y nodo hay una distancia de 100. (4000 / 40 = 100) Bueno, esto no es exactamente así pero a grandes rasgos puede valer. Ten en cuenta que la tabla de nodos puede ser menor que la matriz ya que todo terreno en un juego tiene unos límites.
Esto deja un margen de seguridad a los movimientos del bichito bastante grande.
Cuando avance por la senda marcada por el sonar tendrá un espacio de 32 a cada lado. (32+36+32=100) Y si tiene que pasar de un nodo a otro en diagonal no hay mucho riesgo de que se “fusione” con algún otro objeto o bichito.
Pero ahora supongamos que en el terreno hay obstáculos que dejan un estrecho paso a nuestros bichitos. En ese caso deberemos aumentar el número de nodos para que el cálculo de la ruta a seguir sea más exacto y el bichito no roce con esos obstáculos. El ancho del nodo no debe ser inferior al tamaño del objeto. Si tuviéramos que manejar un bicho muy grande por un escenario muy tortuoso tal vez deberíamos marcar más de un nodo como ocupado por el bicho.
A más nodos, más exactitud. Pero también mayor tiempo de proceso.
La elección del número y del tamaño de los nodos es vital para el correcto funcionamiento del programa que queramos hacer. Lo recomendable sería hacer que el código que vas a escribir permita cambiar el tamaño de la tabla sin tener que modificar el resto de las líneas del programa, usando variables y no valores fijos. A base de probar y probar darás con el número exacto de nodos que te hacen falta y con el tamaño idóneo.
Se podría declarar la tabla así:
Global Num_nodos=0 as integer
Num_nodos=100
Dim nodo(Num_nodos,Num_nodos) as integer
¿Por qué declaro la tabla como “integer”?
Pues para poderle dar valores negativos y positivos.
Los valores negativos pueden ser:
- La posición (el nodo) donde se encuentra en cada momento mi personaje y los
bichitos que le persiguen.
- Nodos ocupados por objetos (obstáculos).
- Zonas no transitables (Agua, montaña, borde del terreno, etc.)
Los valores positivos pueden ser:
- Cálculos de la rutina (número de paso)
- Ruta encontrada.
(Más adelante lo explicaré mejor)
El valor cero es un nodo libre, transitable.
Básicamente el Sonar lo que hace es partir de la posición (nodo) del objeto B (un bichito si seguimos con el ejemplo) e ir buscando los nodos adyacentes paso a paso hasta llegar al objeto A (el personaje al que quiere alcanzar).
En cado paso los nodos que rodean a un nodo del paso anterior son puestos con el valor de paso actual.
Así, en el primer paso, todos los nodos que rodean al bichito y que valían cero son puestos a uno.
En el segundo paso todos los nodos que rodean a los nodos que valen 1, y que valen 0, son puestos a 2.
En el tercer paso todos los nodos que rodena a los nodos 2 y sean 0 son puestos a 3.
Y así hasta que encontremos el nodo donde está el objeto A o se llene la tabla.
Si la tabla se llena es porque no hay ningún camino que lleve de B hasta A.
Una vez encontrado el nodo del objeto A el Sonar desanda el camino desde A hasta B buscando un nodo próximo de menor valor, hasta llegar a un nodo de valor 1, que lógicamente estará junto al nodo del objeto B.
Si sabemos donde está el objeto B (coordenadas x y z) y sabemos qué nodo de valor 1 es el nodo hacia el que tenemos que dar el siguiente paso, podemos calcular la dirección del movimiento, el ángulo.
Efectivamente, Sonar es una función que nos devuelve un ángulo.
Si giramos nuestro bichito en ese ángulo y lo hacemos avanzar, estaremos yendo por el camino correcto.
5.- IMPLEMENTACION.
La forma de hacer esto depende de cada lenguaje. En Dark Basic Proffesional sería:
Direccion#=sonar(objetoB,objetoA)
yrotate object objetoA,direccion#
x#=newxvalue(object position x(objetoB),Direccion#,velocidad#)
z#=newzvalue(object position z(objetoB),Direccion#,velocidad#)
position object objetoB,x#,y#,z#
La primera línea llama a la función sonar() pasándole en número de los objetos B y A. Nos devuelve un número real. Un ángulo.
En la segunda línea giramos el objeto B para que se dirija hacia la posición marcada por ese ángulo. Es decir, se gira hacia el primer nodo de la ruta encontrada por Sonar para ir hasta el objeto A.
Con las línea 3 y 4 calculamos las coordenadas para posicionar el objeto B. El desplazamiento dependerá del valor de la variable “velocidad#”. Cuidado con este valor. Si la velocidad es mayor que el ancho del nodo nos podemos pasar de largo el nodo de destino. Si esto sucede el bichito andará haciendo eses y cosas raras como si estuviera borracho. O lo que es peor, puede que se meta dentro de un muro, o atraviese un árbol, o vaya usted a saber.
Por último, con la quinta línea, posicionamos el objeto B en el sitio calculado.
Si el objeto A estuviese quieto podríamos calcular y guardar la ruta encontrada por Sonar en una tabla aparte y con una sola llamada a la función bastaría.
Pero si el objeto A se está moviendo, como es el caso en nuestro ejemplo, deberemos llamar a la función sonar() cada vez que el objeto A ó el objeto B, en su deambular, cambien de nodo.
De todas formas, si la tabla de nodos no es excesivamente grande y dado la rapidez de la rutina Sonar, podrías llamar a la función sonar() en cada pasada del bucle principal del programa, sin una perdida notable del rendimiento.
6.- DESTRIPANDO EL “SONAR”.
El secreto por el cual la rutina Sonar es tan eficiente reside en guardar los nodos revisados en un paso en unas tablas y utilizar esos valores en el paso siguiente, en lugar de repasar toda la tabla buscando nodos del paso anterior.
Puede parecer lioso pero verás que no lo es tanto.
En Sonar solo se revisan los cuadros adyacentes a los cuadros del paso anterior. Para ello utilizo dos tablas donde guardar las coordenadas de los nodos encontrados y un puntero ó índice para ir añadiendo datos a esas tablas.
Dim nodoX(Num_nodos*Num_nodos) as byte
Dim nodoZ(Num_nodos*Num_nodos) as byte
(Puedes declararla “as byte” si Num_nodos no es mayor de 255)
En la primera pasada solo hay que analizar los cuadros que rodean la cuadricula donde se encuentra el objeto B.
Es el paso 1.
Paso=1
Puntero=1
nodo(3,3)=-1
nodoX(Puntero)=3
nodoZ(Puntero)=3
Revisamos los cuadros que rodean el nodo(nodoX(Puntero),nodoZ(Puntero)), es decir, revisamos los cuadros de rodean el nodo(3,3).
De esto se encarga la subrutina de búsqueda.
Hay ocho nodos que rodean al nodo(3,3) con valor cero.
A los nodos (2,4), (3,4), (4,4), (2,3), (4,3), (2,2), (3,2) y (4,2) se les mueve un 1, osea, se les mueve el valor de “paso”.
Se guardan en las tablas nodoX() y nodoZ() las coordenadas de esos nodos
nodoX(2)=2, nodoX(3)=3 …… nodoX(9)=4
nodoZ(2)=4, nodoZ(3)=4 …… nodoZ(9)=2
Como son ocho nodos el “puntero” queda incrementado en 8.
Ahora “puntero” vale 9.
Vamos con el paso 2.
Del paso anterior sabemos que solo hay que revisar los cuadros adyacentes de los 8 cuadros del paso 1.
Volvemos a llamar a la rutina de búsqueda pasándole los valores guardados en nodoX() y nodoZ() del 2 al 9.
Revisando los nodos de valor 1 se han encontrado 10 nodos próximos que valían 0 y pasan a valer 2.
Las coordenadas de las cuadriculas del paso 2 se guardan a continuación en las tablas nodoX() y nodoZ(), en las posiciones 10 a 19.
Y así sucesivamente hasta encontrar el punto A o completar la tabla.
En el peor de los casos solo se revisaran tantos nodos como tenga la tabla y nunca se revisará dos veces el mismo nodo.
Este sistema es la principal causa de la rapidez del algoritmo Sonar.
Pero aún hay otros trucos para mejorar su rendimiento.
La tabla del ejemplo no es de 10×10. Es de 11×11. La creamos con L=9, y la declaramos como DIM TABLA(L+1,L+1).
Tabla usada: 9×9
Tabla real: 11×11
Si queremos manejar una tabla de 100×100 nodos hay que crear una tabla de 102×102 nodos.
L=100
DIM TABLA(L+1,L+1).
Usaremos 100 nodos, del 1 al 100.
Los nodos para x=0, z=0, x=101 y z=101, los nodos que rodean la tabla nos los reservamos.
Después hay que poner los nodos que rodean la tabla como no transitables.
Este sería el aspecto real de la tabla, con todo el borde marcado como no transitable.
Nuestros personajes solo podrán moverse por una tabla de 9×9 nodos.
Se podría utilizar el -3 para zona no transitable.
Y el -1 y -2 para los nodos con los objetos B y A.
En la rutina nos movemos por coordenadas que van del 1 a la L-1. Se ignoran los valores para x=0, z=0, x=L y z=L.
Resumiendo, una tabla de L=100 es en realidad una tabla de 101 por 101. (Del 0 al 100 van 101).
¿Y para qué todo este rollo?
Para ahorrarnos unos cuantos “if” y mejorar la velocidad de la rutina.
¿Qué “if’s” nos ahorramos?
Estos: “if x+1<=L then” ó “if z-1>0 then”.
Estos “if” son los que, al revisar los cuadros adyacentes a un cuadro, evitan acceder a posiciones no válidas de la tabla.
Pero en la rutina “Sonar” solo se revisan cuadros con un número de paso.
Los cuadros no transitables no se revisan.
Si toda la tabla está rodeada de cuadros no transitables cualquier cuadro a revisar tendrá los ocho cuadros que le rodean dentro de los límites de la tabla.
Por ejemplo. Si estamos revisando el nodo (1,9) miraremos los nodos con valor x del 0 al 2, y valor z del 8 al 10.
Para x=1 y z=9:
if nodo(x-1,z+1) = 0 then … if nodo(0,10) = 0 then …
if nodo(x,z+1) = 0 then … if nodo(1,10) = 0 then …
if nodo(x+1,z+1) = 0 then … if nodo(2,10) = 0 then …
if nodo(x-1,z) = 0 then … if nodo(0,9) = 0 then …
if nodo(x+1,z) = 0 then … if nodo(2,9) = 0 then …
if nodo(x-1,z-1) = 0 then … if nodo(0,8) = 0 then …
if nodo(x,z-1) = 0 then … if nodo(1,8) = 0 then …
if nodo(x+1,z-1) = 0 then … if nodo(2,8) = 0 then …
Todos esos nodos están en los límites de la tabla.
Hasta aquí sería la búsqueda desde el objeto B hasta el objeto A.
Ahora nos queda otro paso importante: decidir la ruta a seguir.
¿Cómo, si no me he guardado la casilla “padre”?
Pues desandando el camino por las cuadriculas de menor valor adyacentes, pero eso sí, en un orden determinado.
El orden consiste en mirar primero las cuadriculas situadas arriba, abajo y a los lados, y después las diagonales.
Esos valores se guardan en una tabla de 8 elementos.
Al repasar la tabla buscando el menor valor, si hay dos cuadros iguales pero uno de ellos está al lado y el otro en una esquina, el valor del situado al lado será el que se toma. El de la esquina no, porque vale lo mismo y la comparación es “menor que” no “menor o igual que“.
La razón para dar preferencia a una casilla lateral frente a una diagonal estriba en la distancia que separa el centro de un nodo de otro nodo dependiendo de que se encuentre al lado o de esquina.
Dicho más técnicamente, el cateto es más corto que la hipotenusa.
Tags: artificial, inteligencia, juegos, pathfinding, radar, sonar
