Unity Spain

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 (//<___base_url___>/applications/core/interface/file/attachment.php?id=6209)

En cuanto pueda, lo pruebo.

Se agradece el aporte .

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.

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.

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

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

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.

Aviso de moderación: Editado el título por abuso de mayúsculas

Gracias por el aporte,tiene buena pinta

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.

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/ (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

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.

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.

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.

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); 

Entendido.

Muy buena explicación, con matrices y todo. Gracias de nuevo.

Pues exactamente eso es lo que he hecho y por eso he llegado a esos resultados, jeje. Ponérselo dificil al algoritmo, vaya, ya que le había puesto obstáculos en los bordes y también obstáculos en U...


Lo de los numeritos ya me di cuenta que sería por lo de tener un mapa más grande.

Intentaré mejorar el algoritmo en cuanto pueda ya que quiero seguir con mi idea de RTS. Me está gustando esto.

Un saludo!

Temo decir que el algoritmo que usas en totalmente erroneo, no he mirado el script - soy muy perrooo  , lo digo porque has puesto esto:

( 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);

Cuando el algoritmo correcto ha de dar como resultado:

( 3, 3, 3, 3, 3, 3, 4, 5, 0, 0);
( 2, 2, 2, 2, 2, 3, 4, 5, 0, 0);
( 2, 1, 1, 1, 2, 3, 4, 5, 0, 0);
( 2, 1, T, 1, 2, 3, 4, 5, 0, 0);
( 2,-1,-1,-1,-1,-1,-1,-1,-1,-1);
( 3, 3, 4, P, 0, 0, 0, 0, 0, 0);
( 4, 4, 4,-1,-1,-1,-1,-1,-1,-1);
( 5, 5, 5, 5, 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);

Donde '0' son los cuadros donde el algoritmo no ha tenido que revisar, pues en el paso 5 se da de narices con el P, de echo he puesto de más, pues no revisaria tantos cuadros. La diferéncia es simple, no mira los adyacentes en -1 pues son obstáculos no transitables; como ves ni siquiera necesita mirar todas las casillas pues se para en cuanto encuentra el objetivo, de no encontrarlo significa que no hay camino posible y jamás se equivoca; de echo el método correcto seria:

(-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1);
(-1, 3, 3, 3, 3, 3, 3, 4, 0, 0, 0,-1);
(-1, 2, 2, 2, 2, 2, 3, 4, 0, 0, 0,-1);
(-1, 2, 1, 1, 1, 2, 3, 4, 0, 0, 0,-1);
(-1, 2, 1, T, 1, 2, 3, 4, 0, 0, 0,-1);
(-1, 2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1);
(-1, 3, 3, 4, P, 0, 0, 0, 0, 0, 0,-1);
(-1, 4, 4, 4,-1,-1,-1,-1,-1,-1,-1,-1);
(-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1);
(-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1);
(-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1);
(-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1);

Pues con este método -poner intransitable alrededor- no es necesario comprobar si estás en el los límites de la zona y es mucho más rápido que poner if() para comprobar si está o no dentro de la zona cada vez que mires las 8 casillas adyacentes.

Recuerdo que un if es lentísimo para la CPU pues no existe un circuito que haga if, en realidad son comparaciones y compara bit a bit.

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

Ya he dicho que no lo he mirado por perro   . Yo creía que el algoritmo que has puesto hace esto:

1.- Mira las 8 casillas adyecentes y les da un valor dependiendo de lo lejos que esté del inicio primero sería 1, luego 2...

2.- Luego mira las 8 casillas adyacentes de las miradas anteriormente. De modo que si miras dese una casilla con valor 1 pones valor 2 y si miras desde una con valor 7 pones valor 8.

3.- Cuando ya has acabado el algoritmo -en mi caso cuando ya no hay más casillas o encuentras el destino- haces el camino inverso:
      3a- Miras las 8 casillas del objetivo y te quedas con la del valor más pequeño y lo añades como punto de paso -Waypoint-.
      3b- Miras las 8 casillas del valor más pequeño del punto anterior y te quedas con el más pequeño y lo añades como punto de paso.
      3c- Repites el paso 3b hasta llegar a la casilla de origen  -o de destino según como lo hayas echo-.
      3d- Ya tienes los Waypoints que ha de seguir el objeto para llegar a su destino.

Realmente eso es también lo que hace el mio, solamente que yo no miro los puntos intransitables y eso lo hace más rápido y que nunca se equivoque, pero la base es exactamente la misma. Creo que me pusiste un enlace al sistema que usas y solo lo miré de refilón y era igual que el mio pero voy a mirarlo mejor ahora

EDITADO: Vale el algoritmo que yo uso al parecer se llama BrushFire, no eras tu quien lo puso, aquí pongo un enlace que lo explica:
BrushFire explicación (http://www.starcostudios.com/blog/2009/12/grafos-de-claridad-algoritmo-de-brushfire-o-wavefront/)

aquí varios articulos en español, creo que valen la pena leerlos
PathFinders (http://www.starcostudios.com/blog/category/inteligencia-artificial/pathfinding-inteligencia-artificial/)

El algoritmo , como ya dije en el primer post, es una traducción de uno escrito en C++. Lo posteó Hasho. Este es el enlace:

http://www.catsoft-studios.com/article/index.php?artid=74 (http://www.catsoft-studios.com/article/index.php?artid=74)

Muy bueno el enlace que has puesto.

He leído el artículo del enlace, realmente el sistema es más simple que el que yo expuse pero no me gusta pues puede que aunque encuentre el camino correcto, y no tiene porque encontrarlo aunque exista, podría dar mucho rodeo.

Voy a ver si me bajo tu código y lo miro pero si que es practicamente idéntico al que puse yo, la pequeña diferéncia entre uno y otro es lo que hace que el que puse sea efectivo, mientras que el del enlace que me has puesto no lo es pudiendo llegar a callejones sin salida.

Me he bajado tu código y lo estoy probando y repasando, dios que pesado que soy  :evil: .

1.- Desconocia las instrucciónes: String.Substring y parseInt, gracias a tí ya las conozco   .

2.- No puede encontrar el camino si hay alguna "calle" cortada. Primero vuelve al principio en vez de intentar buscar otro camino, algo que con tu código no sería muy difícil de hacer, solo has de recalcular la ruta con tu función ActualizarMatriz(Target) donde Target sigue siendo el mismo de antes, creo que así funcionaría.

Cuando llega al punto 0, recalcula el camino pero si vuelve a encontrar un problema vuelve al punto inicial y ya no hace nada, por lo menos en el escenario que le impuse yo  :evil: .

3.- He visto que en el Start(), después de Escanear el Terreno, llama a la función ActualizarMatriz(Target) con Target en (0,0) -la posición inicial del jugador, lo cual es totalmente prescindible pues no va a hacer nada y estás perdiendo tiempo, ya se que para un ordenador moderno no es na de na.

3.- Lo de:

X = new Array( 0,  0,  1, -1,  1,  1, -1, -1);
Y = new Array( 1, -1,  0,  0, -1,  1, -1,  1);
....
u = P.x + X;
v = P.y + Y;

me parece muy bueno, nunca lo había pensado de hacerlo de esa manera, gracias creo que lo pondré en el mio y me ahorraré algunas líneas de código   .

4.- Bloque 1 y Bloque 2. He entendido que ese código mira si se está o no en movimiento, de no estarlo llama a la función de movimiento teniendo en Cuadricula la posición donde ha de ir. La función Moverse(Cuadrícula) -llamada desde el Bloque 2- se encarga de ver si ha llegado al siguiente nodo. La verdad esta parte, junto con la función  Moverse(Cuadrícula) la he encontrado algo liosa.

Conclusión:
 Es un pathfinder correcto si, tal y como está ese código, lo usas en un juego title donde no hay callejones sin salida, de lo contrario no encontraría su destino casi nunca y solo lo encontraría si tan solo se encuentra un callejón sin salida y además de una forma muy irreal, pues vuelve al punto de origen para volver a probar suerte -cambia eso  :kiss: .

En otro tipo de juego lo que veo es la forma de encontrar los nodos, pues el suelo está formado de objetos cuya posición hacen de nodos, ¿te imaginas un escenario de 500x500?, tendrías que crear 250.000 objetos, que burrada. De todas formas es un cambio tan simple como hacer una array bidimensional o tridimensioal con las coordenadas y listo.

Buen trabajo, mucho mejor que los que acuden a la Assest Store cada vez que quieren hacer algo.

Muy buena la página de Starco, si señor. Qué de información sobre PathFinding!

Yo voy a seguir con este script... Esta mañana en el trabajo traté de hacerme un script que me creara todo el conjunto de planos que conforman la cuadrícula, para así no tener que ir poniendo nombres tipo 0103 a cada plano. Ya casi lo tenía pero me vi con un lío de arrays así que ya lo tocaré otro día.

Como dices Hosuko, es limitado y servirá para pocos juegos, pero si se investiga un poco más sobre él, creo que puede valer perfectamente para un mapa complejo.

Un saludo!

Buenas, he escrito unos scripts para crearme el escenario con solo decir un número de filas y de columnas en el inspector.

El problema es que me lo crea de abajo a arriba y de izquierda a derecha... y luego el pathfinding no funciona, creo que debido a eso.

Puede ser esa la causa? Que no empiecen por arriba a la izquierda?


De todos modos os dejo aquí los scripts por si os interesan.
Solo necesitáis tener 2 prefabs; uno de PuntoMatriz y otro de Obstaculo. Con sus tags y todo lo necesario para que se vean.

CrearTablero.js // Este yo lo pongo en el player, por ejemplo.

var plano : GameObject;
var obstaculo : GameObject;
var alto: int;
var ancho  : int;

function Start () {

for (var i : int = alto; i >=0; --i)
{
        for (var j : int = 0; j 12)   
           Instantiate(plano,Vector3(i,0,j),Quaternion.identity);
           else
           Instantiate(obstaculo,Vector3(i,0,j),Quaternion.identity);
   }
}

}

RenombradoCelda.js  // ponedlo en los 2 prefabs que hablé antes.

private var nameaux : String;
private var cero : int;

function Start () {

cero = 0;

if(transform.position.z

Un saludo

Yo en mi programa para probar mi PathFinder lo que hago es que cree los obstáculos de forma aleatoria, en el editor puedo decir el tamaño de la tabla y el número de obstáculos; de ese modo veo muchas situaciones distintas, incluidas las que no puede llegarse al destino por estar encerrado y asi compruebo si da errores o no el código

//De forma aleatoria decidimos poner obstáculos
var nx : int;
var nz : int;
var NObstaculos : int = 10;  //se puede cambiar en el editor
var Correcto : boolean = false;
for(var nid = 0; nid 

También tengo puesto el punto inicial y final de forma aleatoria todo para probar distintas combinaciones y que nunca sea igual

El problema es que me lo crea de abajo a arriba y de izquierda a derecha... y luego el pathfinding no funciona, creo que debido a eso.
[/quote]

Recuerda poner el Tag "PuntoMatriz" y "Obstaculo" a las cuadriculas. Puede que sea eso

1.- Desconocia las instrucciónes: String.Substring y parseInt, gracias a tí ya las conozco   .

[/quote]

Las solia usar cuando programaba en Java. Supuse que también estarian en unityscript.

4.- Bloque 1 y Bloque 2. He entendido que ese código mira si se está o no en movimiento, de no estarlo llama a la función de movimiento teniendo en Cuadricula la posición donde ha de ir. La función Moverse(Cuadrícula) -llamada desde el Bloque 2- se encarga de ver si ha llegado al siguiente nodo. La verdad esta parte, junto con la función  Moverse(Cuadrícula) la he encontrado algo liosa.
[/quote]

Si es liosa esta parte. Lo que pasa es que la función te devuelve el siguiente punto, y en cuanto lo ha calculado, el player se dirige hacia él. Quiero decir que no se almacenan los puntos en un Array para después recorrerlo, que creo es lo que hacen los demás pathfinders. Va de punto en punto, calculando y moviéndose, caculando y moviéndose.

Está claro que es un pathfinder muy limitado.  Pero para el escenario donde iba a funcionar era suficiente.

Claro una cosa es escribir el código del algoritmo y otra es llevarlo a cabo en un escenario en Unity. Lo digo por el tema de la división del terreno. A mi se me ocurrió el tema de las cuadrículas pero he estado viendo otras formas en un post de foro de como escanear el terreno y dividirlo en cuadros. Seguro que lo conoceis. Es de un usuario que estaba trabajando en el A * Pathfinder.

Alñgoritmo A* para compartir (http://www.unityspain.com/index.php/foro/30-tutoriales/21081-algoritmo-a-para-compartir-actualizado#21081)

En cuanto tenga tiempo voy estudiar el algoritmo de Brushfire, y si consigo hacerlo funcionar lo subiré.

Es un tema apasionante esto de los pathfinders.

Está bien, Hosuko, lo de poner os obstáculos aleatorios, aunque siendo totalmente aleatorio, la matriz te puede quedar muy liosa y difícil. Yo ahora me he hecho otro script que funciona en edit mode, y lo que hace es cambiar la casilla seleccionada de transitable a obstáculo, pulsando una tecla, para cambiar rápidamente el mapa sin tener que volver a meterme en scrips.

Por otro lado, sigo atascado con mi player, no se que pasa que desde que me creé la matriz con este método, con el que al final conseguí tenerla bien ordenada con el 0000 arriba a la izquierda, no he conseguido que trace bien los caminos. Todo el rato se me va al 0000, o incluso se pasa y se va fuera de la matriz y  se queda allí xD.

Seguiré investigando a ver por qué ahora no me va  :dry:  

Muy buena pinta tiene el A* de lonog.

Por otro lado, sigo atascado con mi player, no se que pasa que desde que me creé la matriz con este método, con el que al final conseguí tenerla bien ordenada con el 0000 arriba a la izquierda, no he conseguido que trace bien los caminos. Todo el rato se me va al 0000, o incluso se pasa y se va fuera de la matriz y  se queda allí xD.
[/quote]

Puede que por algún motivo las cuadrículas no esten ordenadas. Revisa  el nombre de las cuadrículas a ver si tienes alguna cambiada. (Es algo que me ocurrió a mi.)  y no me funcionaba.

Si quieres puedes colgar el proyecto para poder ayudarte mejor.

Ok, gracias. En cuanto pueda cuelgo el proyecto.

No creo que puedan estár desordenados los puntos ya que los creo con un script

Buenos días.

He estado haciendo algún cambio y he conseguido ya que me funcione, con el mapa creado por scripts.

Ahora me toca ponerme a optimizarlo.

Después de ver una cosilla que fallaba, metí esta línea:

Matriz[PosicionPlayerSiguiente.x][PosicionPlayerSiguiente.y] = -2;
Matriz[PosicionPlayerActual.x][PosicionPlayerActual.y] = -2;

Al igual que actualizamos la casilla a la que vamos con valor -2, he actualizado también la casilla en la que estamos a -2, de forma que no la concibe como una casilla transitable en el resto del camino.

Creo que habrá casos en los que esto empeore el funcionamiento, pero en general, en mis pruebas, lo ha mejorado.
Me explico: Tengo la siguiente situación:

 6, 5, 4, 3, #, #, T, 1, 2, 3
 6, 5, 4, 3, #, #, 1, #, #, #
 6, 5, 4, 3, #, #, 2, #, #, #
 6, 5, 4, 3, 3, 3, 3, #, #, #
 #, #, #, 4, 4, #, #, #, #, #
 #, #, #, 5, 5, #, #, #, #, #
 #, #, #, #, 6, #, #, #, #, #
 #, #, #, #, 7, 7, P, #, #, #
 #, #, #, #, 8, 8, 8, #, #, #
 #, #, #, #, 9, 9, 9, 9, 9, 9

# = Obstáculo

P se encuentra en una casilla con un valor de 7.

Al usar la funcion PathFinder, elige desplazarse hacia la izquierda ya que 7 vale menos que 8. (Uso desplazamientos solo 4 direcciones)

Como no es el target, sigue moviéndose, y vuelve a recorrer las adyacentes:
como la casilla donde estaba el player era un 7, y es la última que recorre, se queda con esa como "siguiente posición", por lo que en vez de avanzar por el camino más coherente, vuelve a la casilla de inicio, y luego como la de la izquierda de P la dejó en valor -2, tira hacia abajo.

Si meto la línea que actualiza a -2 la casilla en la que se encuentra el player al principio, no vuelve a pasar por esa posición, por lo que en este mapa, el camino es bastante mejor. Izquierda y luego arriba en lugar de dar una vuelta.


Se que es una solución muy fácil y que en un callejón sin salida, te dejaría sin posibilidad de volver. Aunque sin esta línea ya te deja sin posibilidad de volver, en los callejones sin salida.

Hay que pensar alguna manera de que las casillas retomen su valor cuando ve frustrada su salida de un callejón. Me pondré con esto.

Un saludo

Buenas.

Os explico un poco un par de cambios que he hecho...

1ª Optimización:
Se trata sobretodo de la funcion Pathfinder, y unos contadores de casillas.
El primero, para tener en cuenta el número de posibles casillas que optan por ser la siguiente. Desechando las que quedan con -2, y los obstáculos.

De este modo, cuando hay solo 2 casillas que pueden ser elegidas, empleará otro método muy parecido al original, con el fin de no quedarse sin PosicionSiguiente, e irse al nodo (0,0).

Cuando este contador es 0, es decir, que no hay casillas libres a las que ir y por tanto el player está rodeado de casillas con valores -1 o -2, empieza otro método que contiene un contador más.

Este método va dando nuevos valores cada vez más negativos a las casillas que se han pisado repetidamente. Y recorriendo un ultimo for, el player se desplaza a la casilla que tenga un valor más alto esta vez. (en este caso todos los valores van a ser iguales o menores que -2)  

El contador de este método de momento sólo me sirve para debuguear. No le he dado uso aún.

El resultado, al menos en mis pruebas ha sido satisfactorio en cierto modo. Hay veces que si le pongo mucha velocidad al player, no le da la gana de pasar por alguna casilla, no se por qué, pero por lo demás, ahora no se va al nodo (0,0) ya que puede pasar por casillas marcadas con -2 y de hecho sigue buscando un camino tras pasar por ellas.


2ª Optimización:
También he cambiado la manera de recorrer el array que define las direcciones de las casillas adyacentes. (Solo lo he implementado para cuando usamos 4 direcciones posibles, sin diagonales).

Lo que hago es mirar dónde se encuentra el target relativamente al player, y cambiar el orden en el que se recorre el array de las posiciones adyacntes, de modo que en caso de tener dos posibles direcciones, deja para la última en chequear, la que es más intuitiva si no hubiese obstáculos.

Con esto se consigue tener más puntería a la hora de elegir un camino u otro en muchos casos.



Os dejo ahí el proyecto.  


[attachment=723]UnityProyecto3.part01.rar[/attachment]

[attachment=724]UnityProyecto3.part02.rar[/attachment]

[attachment=725]UnityProyecto3.part03.rar[/attachment]

No me dejaba subirlo de golpe en un archivo...

Espero que lo probéis y me digáis qué tal os funciona. Y las pegas que le veáis, o malas implementaciones que haya hecho.

Un saludo.

Que tal

He estado probando el proyecto. Ahora ya no va a (0,0) cuando no encuentra el camino y sigue buscando. En uno de los intentos ha estado buscando un buen rato pero al final lo ha encontrado jeje.

El algoritmo está bien y es rápido lo que pasa es que siempre estará en desventaja frente a el A* o el Brushfire ya que estos van almacenando el camino en un ArrayList y una vez encontrado es cuando empieza a moverse el personaje.

Habría que modificar el script pathfinder.js para que busque el camino y si existe lo almacene en un ArrayList, y una vez que tenemos todos los puntos del camino se dirija hacia el target. Y en el caso de que no lo encuentre no se mueva del sitio. Creo que es por ahí por donde se podría mejorar.

De todas formas sigo pensando que para un escenario simple funciona muy bien.  Yo voy a estudiar (cuando tenga tiempo) el Brushfire, que es muy parecido a este, pero te garantiza que va a encontrar el camino. Primero almacena los puntos y una vez tiene el camino es cuando el player se dirige hacia él.

Si lo implemento en unity lo colgaré en el foro.

Usaré tus scripts para la creación de la matriz.

He encontado esto sobre el algoritmo Brushfire o Wavefont:

Algoritmo brushfire en c++  (http://www.societyofrobots.com/downloads/wave_front_simulation_software.zip)

web original:http://www.societyofrobots.com/programming_wavefront.shtml (http://www.societyofrobots.com/programming_wavefront.shtml)

Buenas.

Si, hay algún caso en el que al no poder escojer la opción correcta en una división de caminos, ya se va por otro lado y se pone a usar el último for que le puse al algoritmo, hasta que encuentra el camino.
Se recorre todo el mapa y ya cuando vuelve al punto conflictivo, lo hace bien. Supongo que ahora el algoritmo vale apra más casos. Mientras no se líe mucho el laberinto. la verdad es que el que le he puesto yo para probar, parece un poco Pac-Man.

Pero si lo que se quiere hacer es un RTS, por ejemplo, creo que podría ser bastante útil.

De todos modos voy a mirar yo también el Brushfire este del que habláis, que tiene buena pinta.

Un saludo.

Por lo que he visto con tan solo modificar la funcion ActualizarMatriz()  podemos tener el pathfinder.js por el método brushfire.

Estoy en ello.

Parece sencillo, si. Pero no entiendo el valor inicial que cogen las celdas adyacentes al target.
De donde sacan ese valor?

Por lo demás, parece que hay que usar recursividad para rellenar el tablero.

Cuanto más investigo lo del brushfire, más se me parece al A*... que lío.

Parece sencillo, si. Pero no entiendo el valor inicial que cogen las celdas adyacentes al target.
De donde sacan ese valor?

Por lo demás, parece que hay que usar recursividad para rellenar el tablero.

Cuanto más investigo lo del brushfire, más se me parece al A*... que lío.[/quote]

La diferencia parece estar en que el A* usa Heurística para encontrar el camino más cercano mientras que el brushFire No.

Estoy trabajando en como crear la matriz para el método BrushFire, por ahora no lo he conseguido.  Una vez consiga crear la matriz la sustituire por ActualizarMatriz() y deberia funcionar.  Pero no es tan sencillo crear la matriz

He encontrado este programita por si te interesa, donde se ejecuta el método Brushfire o WaveFront:

A mi me ha servido para ver como va contruyendo la matriz.

Ya veo. Es que, en realidad todo el problema de busqueda del camino óptimo se hace al calcular los valores de la matriz.
Ayer estuve con un amigo informático que me contó más o menos cómo tenía que ser.
Me dijo que él una vez usó algo parecido para un problema de rellenado de polígonos.

Y si, lo de la diferencia, parece que es solo lo de la heurística. De todos modos, el brushfire encuentra el camino con mucha más lógica que el que teníamos. Yo creo que si sacamos este, ya iríamos sobrados para cualquier necesidad de pathfinding.  :side:

Bueno luego el problema será correlaccionar estas casillas con un terreno 3d por ejemplo, o cosas así.

Un saludo y ánimo.

Yo sigo por mi parte intentándolo también, con este pseudocódigo:

Funcion Inundación(x, y, col1, col2)
color = LeerPixel (x,y)
Si (color!=col1 && color!=col2) entonces
PintaPixel (x,y,col1)
Inundación (x+1, y, col1, col2);
Inundación (x-1, y, col1, col2);
Inundación (x, y+1, col1, col2);
Inundación (x, y-1, col1, col2);

Lo saqué de aquí. Creo que el método es el mismo:
Relleno por Inundación (http://http://serdis.dis.ulpgc.es/~ii-fgc/Tema%202%20-%20Primitivas%202D.pdf)


Por cierto, el .exe que has puesto está muy bien. Es útil si no quieres rellenar a mano . Vi ayer alguno parecido por ahí, y muchas gente que usaba el brushfire para movimientos de robots.

He estado mirando lo de colorear poligonos y he encontrado algo parecido.

Ve a la pagina 13.

EDITADO: Tengo problemas para subir el archivo te lo pongo aquí directamente:

5.3 Naive shortest paths through 
ooding
Our rst attempt was to use a slight modication of a shortest paths algorithm.
We call this a \
ooding" algorithm. This is a simple implementation of Kruskal's
shortest path algorithm made specic to mazes. Imagine a hose being placed
in a cell in the maze, and water being allowed to 
ow from a cell to a neighbor
in one unit time. A simple recursive algorithm will yield the amount of time
12
it takes for water to reach any point in the maze from any other point in the
maze, and an appropriate traversal of the matrix of 
ood values will yield the
shortest path.
Code for this algorithm is shown below. The 
ood values are represented
as a 16x16 array of integers (maze), and the wall congurations are represented
with four 16x16 boolean arrays called north, south, east, and west.

void Flood(int x, int y, int flood_val)
{
if (maze[y]
 > flood_val)
{
maze[y]
 = flood_val;
if (!east[y]
)
Flood(x+1,y,flood_val+1);
if (!west[y]
)
Flood(x-1,y,flood_val+1);
if (!north[y]
)
Flood(x,y+1,flood_val+1);
if (!south[y]
)
Flood(x,y-1,flood_val+1);
}
}

Once we have a 
ooding routine, it is easy to answer the question \what
is the best path from point a to point b". We simply 
ood the maze starting
at b with a 
ood value of zero, and then traverse the maze starting at a and
following decreasing 
ood values until we reach b. This works because once

ooding is done, the 
ood value at a is exactly the length of the path from a
to b. Therefore, if we follow the 
ood values in a monotonic decreasing order,
we are guaranteed to reach b in exactly the minimum amount of steps. Note
that the path generated by this algorithm is not unique, as there may be several
paths from a to b with identical lengths.
Also, because we know that the center of the maze is open, the maximum

ood value for any 
ood in any square is 254, so we can use 255 to initialize the

ood array, and can therefore represent the entire array of 
ood values in 256
bytes of memory. This is because the worst case for 
ooding is a spiral in which
the 
ow has to touch every square. If our 
ood starts at one corner of the maze,
and spirals towards the center, it will have length 252 when it enters the center
13
of the maze. Because we know that the center is an open 2x2 square, it will take
254 steps to get to the corner of the center, not 255 in the closed-center worst
case. Therefore, if all 
ood values are initialized to 255, a 
ood value of 255
represents an unreachable portion of the maze. MicroMouse maze designers will
often put these in the maze (i.e., a fully walled o square) to test the robustness
of the MicroMouse algorithms.
Although the straightforward 
ooding algorithm works well for a shortest
path com***tion, it does not allow our mouse to take full advantage of its acceleration
capabilities, and its ability to traverse diagonal paths without turning.
That is, because of how thin our mouse is, and the precise spacing of the sensors,
if we intend to traverse a \stairstep" pattern in the maze, we can simply turn 45
degrees and go straight without turning at all. This is a huge advantage, and is
yet another thing that MicroMouse maze designers will intentionally put in the
maze. The maze 
ooding algorithm is the one typically used by student mouse
projects when they are simply interested in getting something that works. It is
not a world class implementation of a physical maze solving algorithm, and we
clearly needed something better.

Si, todo esto es parecido.  Estoy intentándolo con algo de esta forma, basándome en ese algoritmo:

void ActualizarMatriz(Nodo NuevoTarget, int NuevoPeso){
   Target.x = NuevoTarget.x;
   Target.y = NuevoTarget.y;
   private int u,v;
   for (i = 0; i 


Antes de llamar a la función en el Start(), he puesto otro bucle que inicializa las celdas transitables a 9999.

Voy a ver qué tal va. 

Nota: Está en C# porque he cambiado otra vez a C#, simplemente para familiarizarme con él, Que quiero empezar a usarlo un poco más.

Un saludo.

Creo que lo he conseguido con el método de colorear poligonos. :cheer:

He creado una función llamada Flood() que es la que "inunda" la matriz. y he dejado ActualizarMatriz para que la inicialice a 99 o como tu dices a 9999 para no tener problemas con una Matriz mayor. Esta es la muy buscada y trabajosa  función Flood() jeje: :silly:

function Flood(x : int, y : int, flood_val: int){
    if (Matriz
[y] > flood_val && x = 0 && y >= 0){
        //Debug.Log("pos "+x+","+y+":"+Matriz
[y]);        
        Matriz
[y] = flood_val;
        if (Matriz
[y]!=-1 && x+1 = 0)
           Flood(x-1,y,flood_val+1);
        if (Matriz
[y]!=-1 && y+1 = 0)
            Flood(x,y-1,flood_val+1);
   }
}

En el bloque :

if(Input.GetKeyDown(KeyCode.Mouse0)){ 

}

He añadido :

 ActualizarMatriz(); //inicializa los valores de la matriz a 99
Flood(Target.x,Target.y,0); //inunda Matriz para meodo Brushfire o Wavefront

Ahora mismo me rellena toda la matriz pero con una leve modificación haré que se pare al dar con el Player

Pruebala   a ver que tal

He estado probando la función y Siempre encuentra el camino :silly: .

Te pongo una imagen de uno de los caminos que le he puesto: ( Lo encontró perfectamente sin desviarse ni hacer cosas raras

Le he puesto una matriz de 40 x 40 . Aún no he encontrado la manera de  que pare y no siga rellenando la matriz cuando encuentre al Player.

Ahí estamos!
En cuanto pueda la pruebo.
Estoy terminando mi implementación en C# de todo esto. A  ver si me funciona. Si veo que tengo muchos errores, me cojo tu Flood, y me vuelvo al Js.

Buen laberinto le has hecho, jeje. Es que está claro. Este método es mucho más eficaz.
Ahora habría que ponerse a pensar en lo que tú dices de que pare cuando encuentra al target, y luego ya mejoras en cuanto a costes de ir en diagonal , o en ortogonal, o distintos niveles de altura, que también cueste distinto subir, etc.
Lo veo asequible y muy útil.

Un saludo.

He estado haciendo cambios en Funcion Flood. La primera version era una locura, pisaba los valores de la matriz y se ejecutaba demasiadas veces.  Ahora compruebo que el valor de la casilla no ha sido asignado antes deañadir uno nuevo

ah, muy bien. Así mejor si.

Yo sigo con mi locura de hacerlo en C# pero me estoy desmotivando. Creo que terminaré volviendo al Js y cogiendo tu Flood.

Que ya tengo ganas de ver cómo va.

Buenas! Al final me ha funcionado el WaveFront en C# que tanto me estaba costando.

El problema no se si era el mismo que tenías tu. Los valores se pisaban por que no reinicializaba a cero la matriz con cada nuevo click de destino.



[attachment=747]pathFinderWaveFront.rar[/attachment]

Enhorabuena..por hacerlo funcionar. La verdad es que no es fácil.  A mi también me costó

Mi problema era que la funcion Flood() se quedaba ejecutandose un millon de veces pisando unos valores con otros. pero ya lo arreglé.

En cuanto pueda lo pruebo

Lo más difícil ya estaba hecho. Gracias a ti por el inicio de este hilo, que fue lo que me motivó a la hora de ponerme a estudiar a fondo estos algoritmos.

Ahora estoy pensando algún sistema para contemplar cambios de altura de las casillas, y rampas, etc.

Había pensado definir una matriz de estructuras o clases que además de tener un "valor de coste", tuvieran un valor de altura.
Y así a la hora de mirar las casillas adyacentes, se tuviera en cuenta la altura y se otorgase un valor u otro dependiendo de si es una rampa, o bien se le asignase un valor muy elevado de forma que esa casilla obtuviera un nuevo valor desde otro camino (no parace fácil), en caso de tratarse de otra altura inalcanzable desde donde se está comprobando.

De momento he cambiado que a las adyacentes en diagonal, se les asigne un valor de raiz de 2. Para eso he redefinido el valor de las matrices como float en vez de int.

Un saludo

Al decir que has asignado el valor de raíz de 2 te refieres a que lo has dejado así, con todos los decimales? Ya que para hacer calculos, es preferible que sean enteros, para operar mas rápidamente.
Yo suele usar los valores 10 y 14.

Lo había dejado en raiz de 2 pero tienes razón. Lo cambiaré.
Gracias

¿Raiz de 2?, pero por dios ¿porqué os complicais tanto la vida?

Leeros el post que puse sobre el pathfinder donde se explica paso a paso como es el brushfire, es mucho más simple de lo que lo estais haciendo vosotros

¿Raiz de 2?, pero por dios ¿porqué os complicais tanto la vida?

Leeros el post que puse sobre el pathfinder donde se explica paso a paso como es el brushfire, es mucho más simple de lo que lo estais haciendo vosotros[/quote]

Que tal Hosuko.

El Brushfire lo tenemos ya  dominado jeje :cheer: . Y funciona perfectamente.

Lo que esta haciendo aFisicos es perfeccionar su pathfinder para orientarlo a un juego determinado.Para tener en cuenta el relieve del terreno y demás.


Saludos

Lo más difícil ya estaba hecho. Gracias a ti por el inicio de este hilo, que fue lo que me motivó a la hora de ponerme a estudiar a fondo estos algoritmos.

Ahora estoy pensando algún sistema para contemplar cambios de altura de las casillas, y rampas, etc.

Había pensado definir una matriz de estructuras o clases que además de tener un "valor de coste", tuvieran un valor de altura.
Y así a la hora de mirar las casillas adyacentes, se tuviera en cuenta la altura y se otorgase un valor u otro dependiendo de si es una rampa, o bien se le asignase un valor muy elevado de forma que esa casilla obtuviera un nuevo valor desde otro camino (no parace fácil), en caso de tratarse de otra altura inalcanzable desde donde se está comprobando.

De momento he cambiado que a las adyacentes en diagonal, se les asigne un valor de raiz de 2. Para eso he redefinido el valor de las matrices como float en vez de int.

Un saludo[/quote]

Que tal.

Animo en tu proyecto, veo que quieres adaptar el pathfinder para el juego de estrategia que estas haciendo.

Yo estoy puliendo un jueguecito que he hecho estilo Pac Man para Android pero con diferencias sustanciales. En la IA de algunos  enemigos estoy usando la primera version de pathfinder que posteé y el brushifire para otros. Tengo muchos proyectos iniciados pero este es el primero que he terminado.

Buenas.

Mantis, Habrá que ver ese juego en cuanto se pueda. Haces bien en no complicarte demasiado.
Yo siempre tengo el mismo problema, empiezo muchos proyectos... (escritorio lleno de carpetas con proyectos Unity), y luego no acabo ninguno...
Excepto el Gotardo que ya lo subí al market pero que al final me pareció muy complicado de jugar, y tras 3 o 4 actualizaciones decidí darle un descanso.

Hosuko. Como dice Mantis, ya está dominado el BrushFire. Lo tenemos en Js y en C#. Y sí, se me fue la olla con el raiz de 2 jaja. Está claro que mejor usar enteros para el tema de costes diferentes en las diferentes direcciones.


Ahora estoy apunto de pillar vacaciones  2 semanas... A ver si por fín puedo dedicar un buen rato a todo esto y hacer algo de provecho como tu Mantis. Que tengo ganas de completar algún jueguecillo más.

Un saludo.

Hola, he visto este tema y alomejor alguno entiende mi tema y puede contestarme, aquí esta el link:
 

 
Muchas gracias.

[quote author=Mantis date=1339771388" data-ipsquote="" data-cite="Mantis" class="ipsQuote">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 (//<___base_url___>/applications/core/interface/file/attachment.php?id=6209)[/quote]El enlace está caído, si alguien hace el favor de resubirlo sería de gran ayuda. Título: Pathfinder muy sencillo en Javascript
Publicado por: Mantis en Diciembre 27, 2015, 09:34:53 PM

Voy a ver si lo encuentro y lo subo.