En mi artículo principal, Pathfinding 3º parte “A*”, describí el A* en términos generales, también describí cómo crear una única función de uso general. Sin embargo, crear solo una función de pathfinding puede ser innecesariamente limitado.

Considera la siguiente situación en un RPG, donde un guerrero quiere encontrar el camino tras el muro cercano:

Con esta clase de mapa, podrías situar los nodos de muchas maneras, y usar también, cantidad de densidades. En este ejemplo, vamos a usar una red de nodos de densidad alta, tal y como se muestra abajo:

En este gráfico, los nodos blancos son transitables. Las áreas donde no hay nodos son intransitables. También hemos hecho las cosas de manera un poco diferente; este ejemplo  te permite rodear esquinas alrededor de cuadros intransitables. Además, los “cuadros” en sí mismos no existen; debido a que esto es un ejemplo isométrico. Por ello hemos agrupado el doble de nodos en el eje Y (el eje vertical) que en el eje x (horizontal). Esto permite caminos isométricos más apropiados.

Puedes ver que usando esta red de nodos tan densamente comprimida, podemos no solo rodear muros cercanos sino que además podemos pasar entre el muro y el barril en el proceso. Nuestra densa red de nodos también permite rodear la antorcha, donde el nodo de su base es intransitable. Esto es, en suma, un pathfinding preciso.

Eso está bastante bien en situaciones de distancias cortas, pero, ¿qué haremos si necesitamos encontrar el camino a través del todo el mapa? Usar una red de nodos tan densa, podría fácilmente dejarte con una búsqueda de más de 10.000 nodos en un sólo y único paso a través del bucle del A*. Lo más seguro es que ante esta situación, cualquier ordenador tuviese que detenerse a calcularlo.

Veamos una alternativa. ¿Qué ocurre si elegimos crear una red mucho menos densa como la que tenemos abajo?

En este ejemplo, los nodos están en el centro de grandes diamantes isométricos. Los datos sobre transitabilidad entre diamantes son almacenados en la misma matriz a lo largo de los bordes, y están representados en este gráfico con pequeñas manchas rojas. Para moverse desde una baldosa isométrica a una de sus 8 macro-baldosas adyacentes, la baldosa adyacente debe ser transitable, y el camino entre ambas no debe estar bloqueado.

Esta red de nodos es 72 veces menos densa que la anterior. En vez de manejar más de 10.000 nodos en cada momento, aquí solo manejas el 1/72 de eso, es decir, menos de 200. Nuestro ordenador, puede definitivamente manejar eso. Encontrar el camino a través del mapa ya no es un problema.

Uniendo los dos.

Así pues, ¿qué método elegimos? ….Ambos.

En cualquier búsqueda, deberías primero encontrar el camino que atraviesa el mapa usando el macro-buscador. Despues cambiarías al micro-buscador y buscarías un camino desde la localización inicial hasta dos macro-nodos más allá según el camino obtenido con el macro-buscador. Una vez que has entrado en cada nuevo macro-diamante, usarías el micro-buscador para encontrar el camino que llegue hasta el segundo de los 2 macro-nodos siguientes. Esto acaba por desechar la segunda mitad de cada micro-camino, pero necesitas hacer esto para asegurarte de que está correcto – además, tampoco se desecha mucho desde el momento que el micro-buscador atraviesa distancias relativamente cortas. Una vez que llegues a una distancia de 2 o 3 nodos del destino, deberías cambiar definitivamente al micro-buscador, y encontrar el destino final.

Usando esta aproximación, conseguirás mayor velocidad para cruzar el mapa completo, y serás capaz de rodear esquinas, barriles, etc. con un camino realístico, como en el ejemplo anterior del micro-buscador.

Y si eres realmente ambicioso y tuviese un mapa gigantesco, podrías desarrollar 3 buscadores ; uno en un macro-nivel, otro en uno medio y otro en uno micro. Los profesionales han hecho esto para juegos como Age of Empires. Esto solo depende de lo que necesites hacer.

Bueno, eso es todo.

Voy a tratar de explicar muy resumidamente y com palabras mas entendibles, como es el funcionamiento del Algoritmo Radar, respondiendo a nuestro amigo Jeeba, quien nos hizo el siguiente comentario:

Quetal Noshy, buena voz con el radar, una pregunta, con este algoritmo del radar, es facil salir en caso una unidad se atasque por el camino? Por ejemplo digamos que arriba de la chica hay como una U formada por territorio no transitable y en el centro es transitable, si una unidad llegara al centro, el algoritmo apuntaria a la chica pero el siguiente nodo transitable esta alejado de la chica,se mueve ahi, pero en la siguiente ronda llegara de nuevo llegara al centro de la U y estara en una especie de bucle infinito. Umm lo explicaria mejor con una imagen, peroc reo que es entendible. Saludos

En realidad este error muy común en otros algoritmos, no se dá nunca en radar, porqué? Si repasamos como es el funcionamiento de un radar común, sabemos que la antena del radar emite una onda y al chocar con algun objeto, rebota y el radar vuelve a tomar esa onda calculando, tamaño y distancia del objeto. Aca pasa lo mismo.

En primer lugar, el radar (Origen del movimiento) lanza la onda, completando cada casilla con números correlativos y lindantes, o sea, tomando como valor 0 al radar (A) cargamos con 1 todas las casillas lindantes a éste, a su vez, cargamos con 2 todas las casillas lindantes a las que tienen el valor 1, luego cargamos con valor 3 todas las casillas lindantes al valor 2 y así sucesivamente hasta que una casilla sea igual a B, en el caso de tener un solo objeto o personaje que mover ya sea A hacia B o B hacia A, en el caso de tener varias B que van a A deberiamos llenar con valoras hasta que casillas B = n (casillas con B sea igual a nB), una vez que hayamos cumplido con la finalización de la emisión de la onda, Comenzamos a investigar el camino de regreso. Como lo hacemos? Simple, nos posicionamos en B y chequeamos que celda no vacía tiene el valor mas bajo.

En este ejemplo el 10, puede ser cualquiera de los dos que lindan, la distancia es igual entre ambos.

Luego tomamos esta celda con valor 10, y buscamos la celda lindante con esta que tenga el valor mas bajo, va a ser con valor 9 y puede ser cualquiera de las dos que lindan, volvemos a repetir que la distancia es la misma entre ambas (1 casilla), luego tomamos esta celda con valor 9 y buscamos la vecina con menor valor ( un 8 ) y así sucesivamente hasta que la celda sea igual a A:

De esta manera ya tenemos el camino marcado para ir tanto de A hacia B o de B hacia A.

Ahora respondiendo a la pregunta de Jeeba ¿Podemos caer en un bucle infinito? La respuesta en NO, porque en realidad el camino lo buscamos desde destino (B) hacia Origen (A) y si pudimos llegar con los valores hasta B quiere decir que B puede llegar hasta A. ¿y porqué no caemos en un bucle infinito? porque vemos que el único lugar que ubieramos caido en un bucle infinito esta totalmente vacio (sin valores o números) eso quiere decir que no lo utilizamos y si no lo utilizamos  es imposible caer en un buble.

Que hubiera pasado si tuvieramos 2 B, simple, seguimos completanto con los valores hasta encontrar la segunda B y trazar el camino desde B2 hasta A.

Espero haber sido claro en la explicación, cualquier cosa no duden en preguntarme.

Hasta la próxima…

Aunque es bastante fácil una vez que consigues manejarlo, el algoritmo A* (pronunciado A-star) puede ser complicado para los principiantes. Hay un gran número de artículos por la web que explican el A*, pero la mayoría están escritos por gente que ya sabe los fundamentos de este tema.

Este artículo no es específico de un lenguaje de programación, así que deberías ser capaz de adaptarlo a cualquier lenguaje ordenador. Sin embargo, podrías estar interesado en un programa de ejemplo que escribí ( una versión en C++, y otra en Blitz Basic).

De acuerdo, empecemos.

Introducción: El Área de Búsqueda

Vamos a asumir que tenemos a alguien que quiere ir desde el punto A hasta el punto B. Asumamos también que un muro separa estos dos puntos. El ejemplo queda ilustrado en el gráfico siguiente, donde el recuadro verde es el punto de inicio A, el rojo es el punto de destino B y la zona azul el muro que hay entre ambos.

[Figura 1]

Lo primero que deberías advertir es que hemos dividido nuestro área de búsqueda en una rejilla cuadrada. Simplificar el área, tal y como hemos hecho, es el primer paso en un pathfinding. Este particular método reduce nuestro área de búsqueda a una simple matriz bidimensional. Cada elemento de la matriz representa uno de los cuadrados de la rejilla, y su estado se almacena como transitable o intransitable. El camino se elige calculando qué cuadros deberíamos pisar para ir desde A hasta B. Una vez que el camino haya sido encontrado, el personaje de nuestro juego (o lo que sea) se moverá desde el centro de un cuadrado hacia el centro del siguiente hasta que el objetivo haya sido alcanzado.

A esos puntos centrales se les llama “nodos”. Cuando leas en cualquier otro sitio sobre pathfinding, a menudo verás a gente hablando sobre nodos. ¿Acaso no es más fácil referirse a ellos como cuadrados? Esto se debe a que es posible dividir nuestro área en otras cosas aparte de cuadrados. Podrían ser rectangulares, hexagonales, o de cualquier otra forma; y podrían situarse en cualquier lugar dentro de esas formas – en el centro, por los bordes, o en cualquier lugar. Nosotros usamos este sistema porque es el más simple.

Iniciando la Búsqueda

Una vez que hemos simplificado nuestro área de búsqueda en un número de nodos asequible, tal y como hemos hecho con la rejilla de la figura anterior, el siguiente paso es dirigir una búsqueda para encontrar el camino más corto. En el pathfinding A*, lo hacemos empezando desde el punto A, comprobando los cuadros adyacentes y generalmente buscando hacia fuera hasta que encontremos nuestro destino.

Empezamos la búsqueda haciendo lo siguiente:

1. Empieza en el punto inicial A y añádelo a una “lista abierta” de cuadrados a tener en cuenta. La lista abierta es como una lista de la compra. Ahora mismo solo tenemos un elemento en la lista, pero más tarde tendremos más. La lista contiene los cuadrados que podrían formar parte del camino que queremos tomar, pero que quizás no lo hagan. Básicamente, esta es una lista de los cuadrados que necesitan ser comprobados.
2. Mira en todos los cuadrados alcanzables o transitables adyacentes al punto de inicio, ignorando cuadrados con muros, agua u otros terrenos prohibidos. Añádelos a la lista abierta también. Por cada uno de esos cuadrados, guarda el punto A como su “cuadrado padre”. El cuadrado padre es muy importante para trazar nuestro camino. Lo explicaré más tarde.
3. Saca el cuadro inicial A desde tu lista abierta y añádelo a una “lista cerrada” de cuadrados que no necesitan, por ahora, ser mirados de nuevo.

En este punto, deberías tener algo como la siguiente ilustración. En este diagrama, el cuadrado verde oscuro del centro es tu cuadrado de inicio. Esta bordeado el azul claro para indicar que el cuadrado ha sido añadido a la lista cerrada. Todos los cuadros adyacentes están ahora en la lista abierta para ser comprobados, están bordeados con verde claro. Cada uno tiene un puntero gris que señala a su padre, el cual es el cuadro inicial.

[Figura 2]

Después, elegimos uno de los cuadrados adyacentes de la lista abierta y más o menos repetimos el proceso anterior como se describe un poco más abajo. Pero, ¿cual cuadro debemos elegir? Aquel que tenga el coste F más bajo.

Puntuando el camino

La clave para determinar que cuadrados usaremos para resolver el camino está en la siguiente ecuación:

F = G + H

donde

• G = el coste de movimiento para ir desde el punto inicial A a un cierto cuadro de la rejilla, siguiendo el camino generado para llegar allí.
• h = el coste de movimiento estimado para ir desde ese cuadro de la rejilla hasta el destino final, el punto B. Esto es a menudo nombrado como la heurística, la cual puede ser un poco confusa. La razón por la cual es llamada así, se debe a que es una suposición. Realmente no sabemos la distancia actual hasta que encontramos el camino, ya que toda clase de cosas pueden estar en nuestro camino (muros, agua, etc.) En este tutorial, estás viendo una forma de calcular H, pero hay muchas otras que puedes encontrar en otros artículos de la red.

Nuestro camino se genera por ir repetidamente a través de nuestra lista abierta y eligiendo el cuadrado con la puntuación F más baja. Este proceso se describirá con más detalle un poco más adelante. Primero veamos más de cerca cómo calculamos la ecuación.

Tal y como está descrito más arriba, G es el coste de movimiento para ir desde el punto de inicio a un cierto cuadro usando el camino generado para llegar allí. En este ejemplo asignaremos un coste de 10 a cada cuadro vertical u horizontal hacia el que nos movamos, y un coste de 14 para un movimiento diagonal. Usamos estos números porque la distancia actual para mover diagonalmente es el cuadrado de la raíz de 2 ( no temas), o mas o menos 1,414 veces el coste del movimiento horizontal o vertical. Usamos 10 y 14 con el fin de simplificar. El rango es bastante bueno, y así nos libramos de tener que calcular raíces cuadradas y sus decimales. Esto no es solo porque seamos idiotas y no nos gusten las matemáticas; usar números enteros  también es mucho más rápido para el ordenador. Pronto descubrirás que el pathfinding puede ser muy lento si no usas atajos como este.

Ahora que hemos calculado el coste G mediante un camino específico hasta cierto cuadrado, la forma de resolver el coste G del cuadrado es coger el coste G de su padre, y luego añadirle  10 o 14 dependiendo de si está en diagonal u ortogonal (no diagonal) con respecto a ese cuadro padre. Este método se hará más claro cuando llevemos este ejemplo un poco más allá y nos alejemos un cuadro del inicial.

H puede ser estimado de diferentes maneras. El método que hemos usado aquí se llama el método Manhattan, donde calculas el número total de cuadros movidos horizontalmente y verticalmente para alcanzar el cuadrado destino desde el cuadro actual, sin hacer uso de movimientos diagonales. Luego multiplicamos el total por 10. Se llama método Manhattan porque es como calcular el número de manzanas que hay desde un lugar a otro, donde no puedes acortar atravesando en diagonal una manzana. Cabe señalar que cuando calculamos H, ignoramos cualquier obstáculo que intervenga. Es una estimación de la distancia que queda, no de la distancia actual, es por eso que se llama heurística. ¿Quieres saber más? Puedes encontrar ecuaciones y notas adicionales de heurística aquí.

F se calcula sumando G y H. El resultado del primer paso en nuestra búsqueda puede ver se en la ilustración inferior. Las puntuaciones F, G y H están escritas en cada cuadrado. En el cuadro inmediatamente a la derecha de cuadro inicial, la F está impresa arriba a la izquierda, la G abajo a la izquierda y la H abajo la derecha.

[Figura 3]

Así pues, vamos a mirar algunos ejemplos de estos cuadros. En el cuadrado con letras, G =10. Esto es debido a que está solo a un cuadro del cuadrado inicial en dirección horizontal. Los cuadrados inmediatamente encima, abajo y a la izquierda del cuadrado inicial; tienen todos el mismo valor G de 10. Los cuadros diagonales tienen un valor G de 14.

Las puntuaciones H se calculan estimando la distancia Manhattan hasta el cuadrado rojo objetivo, moviéndose solo horizontal y verticalmente e ignorando el muro que está en el camino. Usando este método, el cuadro de la derecha del inicial, está a 3 cuadros del cuadrado rojo con una puntuación H de 30. El cuadrado está a solo 4 cuadros de distancia (recuerda que solo nos movemos en horizontal y vertical) con una puntuación H de 40. Probablemente comprendas como se calculan las puntuaciones H para los demás cuadros.

De nuevo, la puntuación F de cada cuadro se calcula simplemente sumando G y H.

Continuando la búsqueda

Para continuar la búsqueda, simplemente elegimos la puntuación F más baja de todos aquellos que estén en la lista abierta. Después hacemos lo siguiente con el cuadro seleccionado:

4) Sácalo de la lista abierta y añádelo a la lista cerrada.

5) Comprueba todos los cuadrados adyacentes, ignorando aquellos que estén en la lista cerrada o que sean intransitables terrenos con muros, agua, o cualquier terreno prohibido), añade los cuadros a la lista abierta si no están ya en esa lista. Haz al cuadro seleccionado el “padre” de los nuevos cuadros.

6) Si el cuadro adyacente ya está en la lista abierta, comprueba si el camino a ese cuadro es mejor que este. En otras palabras, comprueba que la G de ese cuadro sea más baja que la del que estamos usando para ir allí. Si no es así, no hagas nada. Por otro lado, si el coste G del nuevo camino es más bajo, cambia el padre del cuadro adyacente al cuadro seleccionado (en el diagrama superior, cambia la dirección del puntero para que señale al cuadro seleccionado). Finalmente, recalcula la F y la G de ese cuadrado. Si esto te parece confuso, podrás verlo ilustrado más abajo.

Ahora vamos a ver como funciona. De nuestros 9 cuadros iniciales, dejamos 8 en la lista abierta después de que el cuadrado inicial fuera incluido en la lista cerrada. De estos, el que tiene el coste F más bajo es el de inmediatamente a la derecha del cuadro inicial, con una F de 40. Así que seleccionamos este cuadrado como nuestro siguiente cuadrado. Está resaltado en azul en la siguiente ilustración.

[Figura 4]

Primero, lo sacamos de nuestra lista abierta y lo añadimos a nuestra lista cerrada (por que ahora está resaltado en azul). Luego comprobamos los cuadros adyacentes. Todos los que hay a la derecha son cuadros de muro, así que no los tenemos en cuenta. El de la izquierda es el cuadrado inicial; ese está en la lista cerrada, así que lo ignoramos también.

Los otros 4 cuadrados ya están en la lista abierta, así que necesitamos comprobar si alguno de los caminos hasta esos cuadros es mejor que el del cuadrado actual hasta ellos. Para eso usaremos la puntuación G como punto de referencia. Miremos debajo de nuestro cuadrado seleccionado; su G actual es 14. Si fuésemos a través del cuadro actual hasta allí, la G sería igual a 20 (10, la G del cuadro actual, más 10 de un movimiento vertical hacia el cuadro superior). Una G de 20 es mayor que una de 14, así que no es un buen camino. Todo eso debería cobrar sentido si miras el diagrama. Es más directo llegar a ese cuadro desde el cuadro inicial moviéndote un cuadro en diagonal, que moverte horizontalmente un cuadro y luego verticalmente otro.

Cuando repetimos este proceso para los otros 4 cuadros adyacentes que ya están en la lista abierta, descubrimos que ninguno de los caminos ha mejorado por ir a través del cuadro actual (el de la derecha bordeado de azul), así que pasamos de él. Ahora que hemos mirado en todos los cuadros adyacentes y ya nos hemos hecho con este nuevo cuadro, estamos listos para movernos al siguiente cuadrado.

Recorremos el grupo de cuadros de nuestra lista abierta, ahora ha bajado a 7 cuadrados, cogemos el que tenga el coste F más bajo. Interesante…, en este caso hay dos cuadros que tienen una puntuación de 54. Así que, ¿cual elegimos? La verdad es que no importa. Para propósitos de velocidad, puede ser más rápido elegir el último que añadimos a la lista abierta. Esto influencia a la búsqueda en favor de cuadros que fueron encontrados más tarde justo cuando estés más cerca de alcanzar tu objetivo. De todas formas no es verdaderamente importante.

Así pues, y ya que lo elegimos anteriormente, escogemos el cuadro justo debajo del cuadrado que desechamos antes. La siguiente ilustración lo aclara:

[Figura 5]

Esta vez, cuando comprobamos los cuadrados adyacentes encontramos que el de la izquierda y el superior a este son cuadros de muro así que los ignoramos. Tampoco tenemos en cuenta el cuadro que está debajo del muro. ¿Por qué? Porque no puedes llegar a ese cuadrado sin que tu personaje se raspe el hombro con la esquina al intentar pasar en diagonal; lo mejor es dar un pequeño rodeo, primero bajando y luego yendo hacia la derecha. (Nota: Esta regla de bordear esquinas es opcional. Su uso depende de como estén situados tus nodos.)

Eso nos deja otros 5 cuadros. Los otros 2 cuadros bajo el actual no están en la lista abierta así que los añadimos y el cuadro actual se convierte en su padre. De esos otros 3 cuadros, 2 ya están en la lista cerrada (el cuadro inicial, y el cuadro que hay encima del actual, ambos resaltados en azul en el diagrama) así que los ignoramos. El último cuadro, el de la izquierda del cuadro actual, se comprueba para ver si el coste G hasta él desde el cuadro actual, es menor que llegando directamente desde el cuadro inicial. Lo hacemos y no hay suerte,  así que ya estamos listos para comprobar el siguiente cuadro de nuestra lista abierta.

Repetimos este proceso hasta que añadimos el cuadro objetivo a la lista abierta, en ese momento parecería algo como la ilustración inferior:

[Figura 6]

Observa que el cuadro padre para el cuadrado dos cuadros por debajo del cuadro inicial ha cambiado desde la ilustración anterior. Antes tenía un coste G de 28 y apuntaba al cuadrado encima suya y a la derecha. Ahora tiene una puntuación de 20 y apunta al cuadrado encima suya. Esto ocurrió en algún momento por la forma en la que se ejecuta nuestra búsqueda, donde la puntuación G fue comprobada y devuelta más baja usando un nuevo camino – el padre cambió y G y F fueron recalculadas. A pesar de que este cambio no parece demasiado importante en este ejemplo, hay muchas posibles situaciones donde este constante control significará la diferencia en la determinación del mejor camino hasta tu objetivo.

Pero, ¿cómo determinamos el camino actual en si mismo? Fácil, sólo empiezas desde el cuadro objetivo rojo, y vas hacia atrás de un cuadrado a su padre, siguiendo las flechas. Eso te llevará de vuelta al cuadrado inicial y tus movimientos serán el camino a seguir. Debería parecerse a la siguiente ilustración. Moverse desde el cuadro inicial A hasta el cuadro destino B es solo cuestión de ir moviéndose desde el centro de un cuadro (el nodo) al siguiente hasta alcanzar el objetivo. Sencillo!

[Figura 7]

1.- ¿RADAR?  ¿SONAR?  ¿QUE DIFERENCIA HAY?.

Sonar es un algoritmo idóneo para buscar un camino entre dos objetos. Dos únicos objetos.

Radar, por el contrario, es más apropiado para buscar todos los caminos que unen una serie de objetos con otro objeto.

2.- ¿CUANDO DEBO UTILIZAR “RADAR” ?

 

Cuando tengamos un buen número de individuos intentando llegar hasta nuestro personaje.

Con “Radar” se rellena la tabla de nodos con valores para el calculo de la ruta de una sola pasada. Con una sola llamada a “Radar” podemos calcular la ruta para todos y cada uno de los individuos.

Bueno, en realidad no calcula la ruta completa. Eso lo hacer “Sonar”. “Radar” solo nos dice hacia donde dar el siguiente paso. Y en muchas ocasiones con esto nos bastará.

3.- FUNCIONAMIENTO GENERAL DEL “RADAR”.

Es muy parecido al de “Sonar”.

Partimos de una tabla (array) de dos dimensiones.

La diferencia está en que no buscamos el camino de B (el robot malo) a A (la chica).

Al contrario.

Comenzamos por el nodo ocupado por A y vamos buscando nodos libres alrededor hasta rellenar la tabla o hasta que todos los nodos ocupados por un objeto B (un robot) tengan algún nodo próximo con valor.

Es decir, utilizando la misma técnica que vimos en “Sonar” de buscar, guardar y analizar nodos adyacentes vacíos y darles el valor del “paso”, vamos a recorrer la tabla hasta que todos los robots tengan un nodo próximo desde el que comenzar su camino hasta A (la chica), o hasta que no queden nodos vacíos para seguir.

Para no complicarlo, lo haremos hasta que no queden nodos adyacentes vacíos.

Un ejemplo: Tenemos a la chica (A) rodeada por robots (B)

En vez de calcular la ruta desde cada objeto B hasta A, como lo haría “Sonar”, vamos a llamar a “Radar”.

Este sería el resultado:

En 7 pasos hemos llenado la tabla.

Ha quedado un nodo vacío porque no tiene ningún nodo próximo de un paso anterior. Pero es lo mismo. Se considera la tabla llena.

Ya podemos buscar el nodo al que cada robot va a dar el siguiente paso, que lógicamente va a ser al nodo de menor valor.

Al revisar los nodos que rodean al robot buscando en nodo con número de paso más bajo debemos poner el valor del nodo encontrado a no transitable.

Así, si hay cerca otro robot que también tenga ese nodo como el más bajo, no enviaremos a dos ó más robots al mismo nodo.

Y si marcamos los nodos que lo rodean también como no transitables nos aseguramos de que no se acercarán unos a otros demasiado.

Ya tenemos cada robot con el nodo al que se tiene que dirigir.

Transformamos esa información en un ángulo, y a correr.

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.