Razón Artificial

La ciencia y el arte de crear videojuegos

Pathfinding A* de 2 niveles

Escrito por adrigm el 3 de abril de 2010 en Inteligencia Artificial, Noticias, Programación | 1 Comentario.

En mi artículo principal de A* Pathfinding, 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 en la siguiente imagen:

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.

Traducido por Elthan, con el permiso de Patrick.

Un Comentario en "Pathfinding A* de 2 niveles"

  1. jose dice:

    Basicamente describes el hierarchical pathfinding :)
    Buen blog

Deja un comentario