Jump to content
Mantis

Pathfinder muy sencillo en Javascript

Recommended Posts

Hola a todos He estado trabajando con el tema de Pathfinder para mi proyecto y quería compartir lo que he conseguido hasta ahora. No es el A* pathfinder, pero es muchísimo más sencillo. Esta basado en el algoritmo que posteó un usuario del foro, el código del algoritmo estaba escrito en C++ Código en C++y lo traduje a javascript.

 

El algoritmo esta basado en una Matriz como el A* pathfinder He estado observando la idea de escanear el terreno y dividirlo en cuadriculas de un compañero del foro que está realizando el A* Pathfinder. En mi proyecto también escaneo el terreno pero de manera diferente. Lo que se me ocurrió fue crearme una Matriz de Objetos (Planos en este caso). El nombre de cada cuadrícula (Objeto) de la matriz me indica las coordenadas que ocupa en dicha matriz. Así el punto (0,0) tendrá de nombre "0000", el punto (0,1) será el "0001". Los dos primeros caracteres me indican la coordenada x y los siguientes la coordenada y. Recupero ese nombre lo paso a Entero y lo uso para trabajar con la Matriz lógica . Mejor veis el código y lo probais: El algoritmo funciona perfectamente en escenarios como el que hay en el proyecto. Con los laterales libre de obstáculos. El problema es que en escenarios con laterales cerrados el Player puede fallar al encontrar el camino. Esto es algo que hay que mejorar. 

 

 

PATHFINDER.zip

Share this post


Link to post
Share on other sites

Se agradece el aporte :D. La verdad es que está todo muy claro, y seguro que a más de uno le viene muy bien. Lo bueno de este sistema, la rapidez, ya que no busca todo el camino, sino el siguiente nodo o los 2 siguientes nodos (yo no he mirado mucho tampoco el código). Y lo malo es que depende el terreno, puede que vaya a un callejón sin salida, o andar mas de la cuenta. Lógicamente, no está comparando que camino es mas corto. Todo no se puede jeje. Aún así, no siempre se necesita un A* para hacer una IA de un juego. Este sistema puede valer perfectamente y yo mismo no dudaría en ponerlo en un juego para móvil, ya que por la experiencia que estoy teniendo, el rendimiento baja mucho al aplicar algoritmos de búsqueda de caminos en un móvil. Lo dicho, un buen aporte sin duda, y un buen tutorial para los que comienzan a aprender sobre IA. Saludos.

Share this post


Link to post
Share on other sites

Primero de todo, felicitar a Mantis por hacer la conversión! Me hace mucha ilusión! :-) Y contestando a Lonog, el algoritmo si que asegura el camino mínimo, y si encuentra un callejon sin salida sencillamente lo ignorará. La gran diferencia con el A* es que el coste de generar el camino es "algo" mayor.

Share this post


Link to post
Share on other sites
Primero de todo, felicitar a Mantis por hacer la conversión! Me hace mucha ilusión! :-) Y contestando a Lonog, el algoritmo si que asegura el camino mínimo, y si encuentra un callejon sin salida sencillamente lo ignorará. La gran diferencia con el A* es que el coste de generar el camino es "algo" mayor.
Hola a todos. Que tal hasho. como habrás comprobado es la trdaducción al algoritmo que tu colgaste en otro post. He estado estudiandolo y no es como tu dices. El algoritmo no encuentra el camino mas corto. Ten en cuenta que al hacer la búsqueda en lo 8 puntos que rodean al player. La hace en un orden y depende de ese orden el que vaya por el camino más corto o más largo. Imagina una matriz :
 
(3, 3, 3, 3, 3, 3, 0, 0, 0, 0);
(2, 2, 2, 2, 2, 3, 0, 0, 0, 0);
(2, 1, 1, 1, 2, 3, 0, 0, 0, 0);
(2, 1, T, 1, 2, 3, 0, 0, 0, 0);
(2,-1,-1,-1,-1,-1,-1,-1, 0, 0);
(2, 2, 2, P, 2, 3, 0, 0, 0, 0);
(3, 3, 3, 3, 3, 3, 0, 0, 0, 0);
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);

El primer punto que se comprueba es el de la derecha , entonces el MinValue es ahora = 2, y continua buscando por ese lado hasta encontrar el target Puedes comprobarlo en el proyecto. Aunque eso es algo que se podría mejorar




			
		

Share this post


Link to post
Share on other sites

Hola Mantis; Tienes toda la razón del mundo. La verdad es que no había pensado en eso. El algoritmo que escribí es una variación de uno llamado BrushFire, que si que encuentra el camino mínimo. La diferencia es la siguiente: En nuestro caso añadimos valores alrededor de un pivote (en este caso el target T) sin tener en cuenta si hay obstáculos. Por ejemplo, donde has puesto la pared, a la parte de la derecha, dentro de la pared irían los valores (de izquierda a derecha) 1,1,1,2,3, 0, 0, ... En el algoritmo original, la diferencia es muy sutil, pero marca la diferencia. Lo que hace no es generar los valores en cuadrados alrededor del target, sino que los añade alrededor del último cuadrado hecho. Es decir, que si hay una pared, no se expande a través de ella. Entonces, usando la misma figura que has hecho tu, quedaria como lo siguiente (hecho a mano, espero que no haya ningún error :-)

(3, 3, 3, 3, 3, 3, 4, 5, 6, 7);
(2, 2, 2, 2, 2, 3, 4, 5, 6, 7);
(2, 1, 1, 1, 2, 3, 4, 5, 6, 7);
(2, 1, T, 1, 2, 3, 4, 5, 6, 7);
(2,-1,-1,-1,-1,-1,-1,-1, 7, 7);
(3, 4, 5, P, 7, 8, 9, 9, 8, 8);
(4, 4, 5, 6, 7, 8, 9, 9, 9, 9);
(5, 5, 5, 6, 7, 8, 9,10,10,10);
(6, 6, 6, 6, 7, 8, 9,10,11,11);
(7, 7, 7, 7, 7, 8, 9,10,11,12);

Ahora que lo recuerdo, hice lo que hice porque en este caso tienes que recorrer la matriz de una forma no-sequencial, es decir, que no puedes hacerlo con el típico doble bucle desde i hasta el final, por lo que puede que haya mas fallos de caché (si no recuerdo mal, las tablas de caché y los procesadores están optimizados para acceder a vectores y matrices de esta forma, pero vamos... que el usuario no lo notaria nunca). En fin, siempre se aprende algo! Luego miraré si en el articulo puse que encontraba el camino mínimo. En tal caso lo cambiaré ;-) EDIT: Artículo actualizado

Share this post


Link to post
Share on other sites

Que tal Hasho , me parece muy interesante el último método que has expuesto. Aunque ya de por sí la primera idea me parece genial, muy simple y suficiente para un proyecto en el que no se necesite el camino óptimo. De todas maneras estudiaré la manera que has explicado. Por ejemplo, en mi proyecto manejo a cuatro players. Uno de ellos es el sargento o capitán (no lo he pensado aún) y es que lidera al grupo. En alguna misión cada uno de ellos se puede encontrar en una parte del mapa poniendo explosivos o lo que sea que vayan a hacer. El pathfinder lo uso para que a una orden del sargento vayan a un punto de reunión que les indique este. Entonces cada player buscará la manera (gracias al pathfinder) de alcanzar ese punto de reunión. Me da igual que lo hagan por el camino más largo con tal de que lleguen al destino. Además al no ser unos escenarios muy laberínticos el camino que tomen (si no es el más corto) diferirá muy poco este.

Share this post


Link to post
Share on other sites

Muy buen tema. Horas y horas he echado yo a intentar idear un pathfinder basado en raycast, pero las soluciones siempre me han salido muy acaparadoras de recursos, y al fin y al cabo, es mejor dividir el escenario en cuadrados o nodos y hacer un pathfinder inspirado en A*. De todos modos, este que comentáis, me voy a bajar el código para estudiarlo bien, porque tiene pinta de estar bastante optimizado, y como bien decís, a veces no necesitas el camino más corto, si no simplemente llegar al punto esperado. Gracias por eel aporte.

Share this post


Link to post
Share on other sites
Muy buen tema. Horas y horas he echado yo a intentar idear un pathfinder basado en raycast, pero las soluciones siempre me han salido muy acaparadoras de recursos, y al fin y al cabo, es mejor dividir el escenario en cuadrados o nodos y hacer un pathfinder inspirado en A*. De todos modos, este que comentáis, me voy a bajar el código para estudiarlo bien, porque tiene pinta de estar bastante optimizado, y como bien decís, a veces no necesitas el camino más corto, si no simplemente llegar al punto esperado. Gracias por eel aporte.
El código está muy comentado y está todo en un solo script. Lo que comentas del raycast, cuando estube liado con el pathfinder encontré uno que te puede ser de utilidad en: http://www.arongranberg.com/unity/pathfinding/ No es el A *. Esta basado en Raycast y no va mal tampoco, aunque no es tan sencillo como este. Me alegro que te sirva el aporte Saludos

Share this post


Link to post
Share on other sites

Muchas gracias Mantis. He bajado el código del pathfinding de Arongramberg usando raycast, y la verdad es que está trabajado. Lo iré estudiando poco a poco. De todos modos también he bajado tu package y he visto que el código es simple y muy entendible. Creo que probaré a hacer cosas con él. Ya te contaré qué tal me va. Además entiendo mucho mejor el Js que el C# no sé por qué. Un saludo.

Share this post


Link to post
Share on other sites

Guau, ya he leído tu código y entendido creo que todo. Está perfectamente comentado, enhorabuena. Solo me falta ponerme a usarlo en el unity. A ver si tengo hoy un ratillo y lo intento. Además, con tu código, he aprendido que hacer clases con Js no es tan diferente de C#. Un saludo. Te seguiré informando.

Share this post


Link to post
Share on other sites

Buenas. Tengo una duda a la hora de poner en marcha el pathfinder. En la escena qué tengo que crearme, un plano por cada punto de la matriz, y renombrarlo con 0000,0100,0101, etc? El caso es que no entiendo bien porqué al hacer el Parseint, usas los 2 caracteres para cada componente. Si tenemos una matriz de 10x10, no haría falta solo 1 carácter por componente? EDITO: Ya he conseguido hacer que funcione. He añadido unas frases para que me coloree las casillas de obstáculo de verde y así ver si funciona bien. Tras probar un buen rato, he visto que funciona bastante bien y tiene mucho potencial. Hay veces que funciona perfecto, y alguna vez que no se por qué, al buscar un camino, se va hasta la casilla (0,0) y luego desde allí busca el camino en vez de buscar desde donde se encuentra en principio. Te ha pasado lo mismo? Seguiré haciendo pruebas. Un saludo.

Share this post


Link to post
Share on other sites
En la escena qué tengo que crearme, un plano por cada punto de la matriz, y renombrarlo con 0000,0100,0101, etc? El caso es que no entiendo bien porqué al hacer el Parseint, usas los 2 caracteres para cada componente. Si tenemos una matriz de 10x10, no haría falta solo 1 carácter por componente?
En el proyecto en el que iba a usar el pathfinder tenia un escenario de 60 x 60 por ello los dos digitos para cada coordenada. Asi te servirá cuando hagas un aescenario mayor de 10 x 10.
Tras probar un buen rato, he visto que funciona bastante bien y tiene mucho potencial. Hay veces que funciona perfecto, y alguna vez que no se por qué, al buscar un camino, se va hasta la casilla (0,0) y luego desde allí busca el camino en vez de buscar desde donde se encuentra en principio. Te ha pasado lo mismo? .
Me ha pasado exactamente lo mismo ya que es un (defecto-limitación) del algoritmo Como expliqué en el primer post, el algoritmo busca los ocho nodos adyacentes de donde se encuentra el Player, y comprueba cual el de menor valor para dirigirse hacia él y así sucesivamente hasta llegar al Target. El problema está en que si se encuentra en un callejón donde no hay salida puede encontrarse con que los valores adyacentes entán a -2 porque ya ha pasado por ahí y vuelve a (0,0). ¿Y porque llega a un callejón sin salida? Pues por el orden en que comprueba los puntos adyacentes; Veamos un escenario como este:
(3, 3, 3, 3, 3, 3, 4, 5,6, 7);
(2, 2, 2, 2, 2, 3, 4, 5, 6, 7);
(2, 1, 1, 1, 2, 3, 4, 5, 6, 7);
(2, 1, T, 1, 2, 3, 4, 5, 6, 7);
(0,-1,-1,-1,-1,-1,-1,-1, -1, -1);
(2, 2, 2, P, 2, 3, 4, 5, 6, 7);
(3, 3, 3, -1, -1, -1, -1, -1, -1, -1);
(4, 4, 4, 4, 4, 4, 4, 5, 6, 7);
(5, 5, 5, 5, 5, 5, 5, 5, 6, 7);
(6, 6, 6, 6, 6, 6, 6, 6, 6, 7);

A la hora de comprobar los nodos adyacentes, este comprueba primero el que esta a su derecha con (valor = 2 ) y pone el minValue con ese valor. Después de comprobar los ocho puntos ve que ninguno es menor que el minValue por tanto se dirige hacia la derecha. Poniendo el valor de ese nodo a -2 y continuando la búsqueda hacia la derecha, dirigiendose pues hacia un callejón sin salida. Una vez en el útimo punto del callejón ve que la única casilla libre está a -2 por que ya ha pasado por ahí y se dirige a (0,0). Debido a esta linea de la función Pathfinder:
    
        //Nodo que almacena las coordenadas del próximo punto al que hay que moverse
        var NextNodo : Nodo = new Nodo(0,0);
Para evitar que el player fallara en encontrar el camino, en mi escena evité poner obstaculos en el perímetro exterior y también evité poner obstáculos en forma de U. Con los que ocurriria el mismo problema. De esta manera el algoritmo encontrará siempre el camino sin problemas con un 100% de fiabilidad (siempre y cuando no te equivoques en nombrar las cuadrículas correctamente) pues también fallará si eso ocurre, aunqeu eso ya no es un fallo del algoritmo. Esta son las limitaciones de este algoritmo. Algo que se puede mejorar. Resumiendo: El algoritmo encontrara con un 100% de fiabilidad el camino en escenarios como:
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
(0,-1,-1, 0,-1,-1, 0, 0, 0, 0);
(0,-1,-1, 0, 0, 0, 0, 0, 0, 0);
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
(0,-1,-1,-1,-1,-1,-1,-1, 0, 0);
(0, 0, 0, P, 0, 0, 0, 0, 0, 0);
(0, 0, 0, 0, 0, 0, -1, 0, 0, 0);
(0,-1,-1,-1, 0, 0, -1, 0, 0, 0);
(0, 0, 0, 0, 0, 0, -1, 0, 0, 0);
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);

Y puede fallar en escenarios como:
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
(0,-1,-1, 0,-1,-1, 0, 0, 0, 0);
(0,-1,-1,-1,-1,-1,-1,-1 -1,-1); 

Share this post


Link to post
Share on other sites

UnitySpain © Todos los derechos reservados 2020
×
×
  • Create New...