Menú

Mostrar Mensajes

Esta sección te permite ver todos los mensajes escritos por este usuario. Ten en cuenta que sólo puedes ver los mensajes escritos en zonas a las que tienes acceso en este momento.

Mostrar Mensajes Menú

Mensajes - Mantis

#421
Temo decir que el algoritmo que usas en totalmente erroneo, no he mirado el script - soy muy perrooo  ,
[/quote]

Temo decirte Hosuko que estas totalmenet equivocado.  Esta claro que no has mirado siquiera el algoritmo..

El algoritmo del que hablas es otro distinto de este. Este NO ES el que tu esbozaste en otro post.

Este tiene sus limitaciones que ya se han explicado, pero pienso que se pueden corregir.

El que tu has puesto parece muy interesante pero támbien mucho más complejo a la hora de construir la matriz.

saludos
#422


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?
[/quote]

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?
.[/quote]

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);
#423
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.[/quote]

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
#424
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.
#425
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.[/quote]

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



				
#426
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++ http://www.catsoft-studios.com/article/index.php?artid=74" rel="external nofollow">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