Comunidad de diseño web y desarrollo en internet online

Pathfinding en Actionscript usando Waypoints

Hace un tiempo había intentado un acercamiento al tema usando vectores. Lamentablemente, el método era lento y no siempre encontraba un camino.

Entonces, me puse a trabajar en otro tipo de pathfinder. Uno que se basara en Waypoints.

Básicamente, los Waypoints son puntos que colocamos en un mapa que indican lugares a los que podemos ir. Estos Waypoints están conectados entre sí de forma tal que forman un grafo.

Por ejemplo, supongamos que tenemos el siguiente mapa:



Es obvio que no podemos ir directamente desde A a B en línea recta. La solución es crear 2 puntos de forma tal que pasando por éstos podamos llegar al objetivo:



Esos 2 puntos son los Waypoints, que de ahora en adelante, llamaremos nodos.

Ahora supongamos un mapa más complejo:



En éste mapa, podemos observar que desde cualquier nodo podemos movernos a cualquier otro (aunque no podamos directamente, siempre hay un camino). Además, no hay ningún punto (un punto no es un nodo) desde el que no se pueda ir en forma directa a, al menos, un nodo. Éso último es esencial y de eso va a depender que nuestro pathfinder funcione.

Ahora, queremos ir del nodo 1 al 6. Lo primero que hay que notar es que hay muchos caminos. Incluso, si decimos que podemos volver sobre nuestros pasos, éstos son infinitos (hay que tener en cuenta este detalle a la hora de programar el pathfinder). Igualmente, vemos que el ideal parece ser:

1 - 2 - 3 - 4 - 6

Pero si lo vemos nuevamente, nos damos cuenta que el camino puede ser más corto (con ésto me refiero al número de nodos y no a la distancia recorrida):

1 - 2 - 4 - 6

Ya que podemos saltar el nodo 3.

Entonces, cómo encontramos el camino? Es bastante simple, creamos un Array que llamaremos tree.

En el índice 0, ubicamos el nodo de inicio. El Array en el ejemplo es bidimensional, pero no es estrictamente necesario. Entonces, anotamos los nodos a los que se puede ir en línea recta, en el mapa anterior, sólo hay uno, el 2. Ese sería el índice 1 de nuestro Array.

Repetimos la operación anterior, nos fijamos qué nodos puede ver el 2 y los ubicamos en el siguiente índice. Ahora, repetimos, repetimos, repetimos. Siempre teniendo cuidado en no agregar 2 veces el mismo nodo, ni en el mismo índice ni en índices distintos.

Cuándo terminamos el loop? Bien, cuando hallamos encontrado el nodo destino. O cuando hallamos incluido todos los caminos hacía éste.

Vamos a analizar el primer caso. Si detenemos la búsqueda apenas encontremos el nodo destino, vamos a tener uno de los caminos con menor cantidad de nodos (si los nodos son equidistantes, tendríamos el camino más corto). Ésto tiene 2 ventajas, es rápido y al no encontrar siempre el camino idóneo, le agrega cierta torpeza a la IA.

El segundo caso requeriría analizar luego todos los caminos posibles. La ventaja de ésto es que incluso podríamos agregar que ciertos caminos sean menos transitables o cosas por el estilo (igual, si necesitan algo así, pueden considerar el algoritmo A* que se lee A-star)

Pero en éste caso, nos vamos a enfocar en la primer opción.

Es obvio que si llegamos al nodo destino, podemos hacer el camino inverso para llegar al nodo de partida. Entonces, tomamos el nodo de llegada y nos movemos hacia arriba en el tree hasta encontrar el nodo deseado.

Y listo, hemos conseguido un pathfinder relativamente simple (la función del ejemplo no está optimizada, encuentra los caminos en menos de 10ms, quizá, luego de optimizarla, logre bajarlo a 5). Simplemente hagan click en uno de los puntos y luego hagan click en el punto a donde quieren que se dirija.



Bajar el .fla

Tengo que aclarar que la idea de que un tree es un grafo en el que no podemos volver hacia atrás (idea en la que se basa el funcionamiento de éste ejemplo) la encontré en ésta página, aunque no tomé ni una línea de código de la misma. Además, querría agradecer a Zah, que me dio un método para hacer ésto que al final no pude usar porque no fui capaz de adaptarlo :P

¿Sabes SQL? ¿No-SQL? Aprende MySQL, PostgreSQL, MongoDB, Redis y más con el Curso Profesional de Bases de Datos que empieza el martes, en vivo.

Publica tu comentario

o puedes...

¿Estás registrado en Cristalab y quieres
publicar tu URL y avatar?

¿No estás registrado aún pero quieres hacerlo antes de publicar tu comentario?

Registrate