Posible algoritmo de pathfinding

[Altair]

http://www.megaupload.com/?d=AYM0TFOO

Aqui os dejo en PDF lo que se me ha ocurrido, a ver que os parece.

PD: me bajo al supermercado a por unas cuantas botellas de agua y unos cuantos frascos de aspirinas  ^_^'

[[EX3]]

Arg... odio que la gente uséis Megaupload o Rapidshare para descargas tan pequeñas y directas, tío :P A mi automáticamente me da pereza descargarme nada de ahí. www.dropbox.com o http://letscrate.com/ son servicios mas livianos y sencillos para este tipo de cosas :)

http://www.stratos-ad.com/forums/index.php?topic=14174.0

Aqui os dejo en PDF lo que se me ha ocurrido, a ver que os parece.

Un consejo, a parte de subir un PDF explicando el algorritmo seria interesante que desarrollaras un poco la idea en el post, resulta mas comodo y llegas antes a la gente, objetivo que se supone cumple el foro (a parte que así invitas a la gente a participar, que es la idea supongo). El PDF puede estar bien para profundizar mas en el tema :)

Salu2...

[Altair]

Ya sabia yo que habia leido por algun sitio donde alojar archivos mas pequeños.

Veamos, el asunto esta en que al calcular el contenido de las tablas precalculadas podemos disponer de mas tiempo, un elemento critico en algoritmos en tiempo real.

La idea se basa en: "Si estas en el nodo X y vas al nodo Y, el primer paso es el nodo Z". Y eso es todo lo que nos interesa del camino entre X e Y, porque avanzamos un unico paso. Por tanto, la ruta completa es irrelevante. El ejemplo nos da 8 posibles nodos, hay que encontrar una ruta entre X e Y. Para no caer en bucles infinitos cada nodo solo se puede visitar una vez. Si miramos las taclas de "ramas" y "hojas", se ve que el recorrido del arbol es en profundidad .

En principio pagamos el tiempo mas alto. Pero... al eliminar nodos ya visitados, poco a poco empezamos a eliminar ramas enteras. En ejemplos pequeños no se nota tanto, pero en otros mas grandes (20 nodos, por ejemplo) se notan mucho mas las ramas eliminadas. Esto hace que el precio sea menor. No se si el mas optimo (lo dudo) pero si menor.

Una posible optimizacion es descartar tambien las ramas cuyas hojas hayan sido anuladas, aun no he hecho pruebas al respecto.

[Vicente]

Esto, en que se diferencia tu algoritmo de una busqueda en anchura?

[Altair]

En que no es solamente encontrar UN camino, sino  evitar (en lo posible) caminos mas largos de lo necesario. Es decir, en vez de 4,8,5, 2, que no salga 4, 8, 7, 3, 6, 5, 2, que tambien seria valido pero mas largo.

[blau]

En que no es solamente encontrar UN camino, sino  evitar (en lo posible) caminos mas largos de lo necesario. Es decir, en vez de 4,8,5, 2, que no salga 4, 8, 7, 3, 6, 5, 2, que tambien seria valido pero mas largo.

Esa idea es genial....  ^_^'   ahora en serio, eso que comentas sobre las busquedas de caminos es como el valor de los soldados, que se le supone. Lo interesante es ¿como lo consigues? ;)

[Vicente]

En que no es solamente encontrar UN camino, sino  evitar (en lo posible) caminos mas largos de lo necesario. Es decir, en vez de 4,8,5, 2, que no salga 4, 8, 7, 3, 6, 5, 2, que tambien seria valido pero mas largo.

La busqueda en anchura encuentra el camino mas corto tambien.

[Warchief]

Veamos, el asunto esta en que al calcular el contenido de las tablas precalculadas podemos disponer de mas tiempo, un elemento critico en algoritmos en tiempo real.

La idea se basa en: "Si estas en el nodo X y vas al nodo Y, el primer paso es el nodo Z". Y eso es todo lo que nos interesa del camino entre X e Y, porque avanzamos un unico paso. Por tanto, la ruta completa es irrelevante. El ejemplo nos da 8 posibles nodos, hay que encontrar una ruta entre X e Y. Para no caer en bucles infinitos cada nodo solo se puede visitar una vez. Si miramos las taclas de "ramas" y "hojas", se ve que el recorrido del arbol es en profundidad .

No he mirado el pdf, pero por lo que comentas parece pathfinding con lookup tables.
Las lookup tables se usan extensivamente, pero tienen sus problemas:

• -Un cambio en el estado de un nodo requiere recalcular la tabla (si W falla, puede que el camino entre X e Y ya no pase por Z)
• -No hay informacion de los objetos dinamicos
• -Requieren mucho espacio (a veces en consola hay mas procesador libre que memoria)
• etc

Dicho lo cual, tambien tienen sus beneficios, claro (velocidad, como dices.)

Por ejemplo:
http://www.cgf-ai.com/products.html#lutexplorer
The value of path look-up tables is in their speed, with path lookup 50 to 100 times faster than an optimized A*. The downsides of path lookup tables are their memory consumption, their static nature and the limited ability to handle game unit variations such as movement capabilities and dimensions.

[Altair]

Para Vicente:
Pues no lo sabia, es lo que suele pasar cuando te metes en berenjenales que conoces poco tirando a menos  ^_^'  yo pensaba que se obtenia un camino que no necesariamente era el mas corto, al menos eso es lo que daban a entender los ejemplos que vi.

Para Warchief:
Pues parece que si, eso de las http://es.wikipedia.org/wiki/Lookup_table o es lo mismo que se me ocurrio o se parece bastante. Lo malo son los puntos en contra que comentas, como los cambios en nodos o objetos dinamicos.

[Warchief]

Ahora si he mirado el pdf. Es un comienzo para construir LUTs, pero le falta anyadir costes de movimiento (por ejemplo, el coste para ir de 4 a 8 puede ser mayor que el coste de ir de 4 a 7.)

En realidad estas haciendo una busqueda, aunque lo llames tabla. Tienes el path completo de 4 a 2. Una tabla seria

Código [Seleccionar] Expand


LUT  para ir de X a Y el siguiente nodo es Z

X > Y      Z
4 > 2      8
4 > 5      8
4 > 1      8
4 > 8      8
4 > 7      7
4 > 3      7
4 > 6      7
8 > 2      5
...
5 > 2      2
...


Con esa LUT, puedes construir un camino "sin hacer busqueda", ya que la busqueda esta guardada en cada nodo.
Para ir de 4 a 2, se construye:

Código [Seleccionar] Expand


4 > 2 = 8
8 > 2 = 5
5 > 2 = 2

Camino = 4 8 5 2

El problema es el tamanyo de la tabla N*N, recalcular, etc.

Lo que has hecho en el pdf es una busqueda en profundidad. Si 8 fallara (no se puede llegar a 2 a traves de 8 ,) tendrias que volver a examinar 7.
http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidad

Si guardas los resultados de una busqueda (profundidad, anchura, heuristica, lo que quieras) en una tabla, entonces si tienes una LUT.

[Warchief]

Este ppt puede orientarte al respecto de LUTs vs algorithms:
www.cse.lehigh.edu/~munoz/CSE348/classes/ChristmanPathfinding.pptx

[Altair]

No sabia yo nada de esto de los "LUTs", ni que existian. Pues nada, estoy esperando a que me llegue la conversion del formato a PDF para leerlo.

Lo de calcular una especie de prioridades es algo que se me ha ocurrido hace unas horas, basandome precisamente en manhattan de A-Star. Es decir, si estoy en el nodo 8, el nodo 5 es mas importante que el nodo 1 porque esta "fisicamente" mas cerca. Esto haria que en la primera tabla, en la rama del 8, quedara asi:

8: 5, 1

Que conste que sigo con lo de "ramas" y "hojas" solo porque estoy esperando que me llegue el PDF  ^_^'

Otra posibilidad que se me habia ocurrido era asignar un "peso" a cada nodo, el cual se va incrementando de padres a hijos. Es decir; el nodo 2 tendria un peso de "1", el nodo 5 y 6 tendrian un "peso" de "2" y asi sucesivamente. Seria una busqueda en profundidad, pero empezando por Destino. De esta forma, voy por prioridades, si estoy en nodo 8 puedo ir a los nodos 1, 5, 7, sin embargo al mirar los "pesos" de esos mismos nodos ya se que el camino mas corto pasa por el nodo 5. Esto creo que haria que las busquedas fueran mas cortas. Ahora el colmo seria que esto mismo ya se haga con los LUTs  :D

[Vicente]

Un par de cosas:

- normalmente en algoritmos de grafos, los nodos se "colorean" para saber que ha pasado con ellos. Creo que los colores que se suelen usar son blanco (no visitado), gris (en la cola para visitar) y negro (ya visitado). En una busqueda en anchura normal si no tienes pesos, no tienes que volverte loco, simplemente cualquier nodo que no sea blanco no lo vuelves a visitar y listo.

- Si tienes pesos, entonces mirate el algoritmo de Djikstra, que es un poco lo que estas intentando hacer (y que a la vez es simplemente un caso especial del A*). El peso es muy facil de calcular: es el peso del nodo anterior mas el coste de la arista. Para ti por ejemplo las aristas podrian pesar todas 1, con lo cual el origen tiene peso 0, los que estan pegados tienen peso 1 (0 del origen + 1 que es lo que cuesta llegar,...).

Luego que los caminos los quieres salvar en una tabla o lo que sea, eso es totalmente independiente :)

[Altair]

Al fin pude leer el archivito de marras, me ha tocado instalar el Presentation de OpenOffice.

He visto confirmadas ahi muchas cosas que me habia encontrado en las hojas y hojas que llevo llenas haciendo pruebas. Teorias, problemas en potencia, posibles soluciones (no confirmadas hasta ahora), etc.  Por ejemplo, lo que pone en la pagina 13 es exactamente lo mismo que habia pensado yo. No lo he leido del todo porque hay palabras que no recuerdo que significa, pero no pasa nada porque tengo el diccionario Ingles-Español aqui al lado.

Ayer a ultima hora estuve mirandome http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra por enesima vez. y aunque una vez mas no entendi la explicacion (cuando uno es un negado para las mates, eres un negado y punto, es lo que hay  ^_^'  ) se me ocurrio una cosa mirando la ejecucion del ejemplo, basandome en lo que veia.

http://tinypic.com/r/5wfpf4/7

En negro, el numero del nodo. En rojo el "peso" del nodo. Se empieza por Destino (nodo 2) y se hace un recorrido en profundidad, evitando los nodos repetidos, hasta llegar a Origen (nodo 4). El peso de cada nodo esta repartido en plan padre-hijo.

Al empezar la busqueda (nodo 4) solo necesitamos mirar cual de los posibles nodos vecinos tiene el menor peso. A menor peso, mas cerca esta Destino (nodo 2). En caso de varios nodos con el mismo peso minimo, cogemos uno cualquiera de los dos. Esto hace que la busqueda del camino sea mas eficiente, creo.

Hay una cosa que me llama la atencion, los nodos sin descendencia (3 y 1) no afectan a la busqueda del camino pese a ser redundantes. Posiblemente esto sea despreciable a nivel de recursos y velocidad en mapas de nodos pequeños, pero en otros con muchos mas nodos quiza habria que añadir una poda antes de la busqueda, liberando asi recursos.

No se si esto en concreto se trata en el archivo que me pasaron, pero me parecio una buena idea. Y ahora, a leer con mas calma el archivo porque me parecio muy interesante xD

[Vicente]

Que no entiendes de Djikstra, lo mismo te lo podemos explicar :) Y por cierto, los pesos no estan en los vertices, estan en las aristas (las lineas que unen dos vertices).