Busqueda De Caminos

[dracks]

 Hola,

Aprovecho, que tenengo un apartado Inteligencia Artificial en un foro, para preguntar:

En mi RTS, no puedo poner link de descarga, porque no tengo alojamiento para el, je je :D, estoy buscando la forma de que una unidad me pueda evitar una murralla sin problemas, y que si esta, esta cerrada, que directamente no se me mueva (y si esto, que me ensenyasse un mensajito por pantalla, diciendo, no hay camino, y la muralla es nuestra, y en caso que la muralla sea enemiga, (esto es facil), que directamente le habra un agujero... :P si ha de passar pa que me interessa evitarla si abriendo un agujero no pierdo nada?


Weno, pos esto, en realidad la intencion es que tambien haya barrancos y todo esto...



P.D.: el juego esta hecho en fenix, pero si encuentro algun buen manual de SDL con C++ (a ser possible en español) me parece que lo reprogramare, y aun sin encontrar el manual, seguramente tambien... pero weno...

[Lord Trancos 2]

 A mi este tuto me fue bastante bien;
http://www.policyalmanac.org/games/aStarTutorial.htm

[zupervaca]

 Cuando entre en la web me di cuenta que había visto ese mismo tutorial en algún sitio, pero en español ;)

http://www.policyalmanac.org/games/aStarTu...Tutorial_es.htm

[nsL]

 Ese tuto q poneis me lo lei hace bastante tiempo y lo explica bastante guay  (ole)  

[vicho]

 es bueno ese tuto me lo puse en la pocket pc para leerlo en la cama  (ole)  

[dracks]

 Vale, me lo he empezado a leer, y weno, hasta donde he llegado, ya savia... ahora viene cuando lo matan, pero es tarde y tengo sueño, con lo que mejor lo dejo para terminar de leermelo mañana....



Suerte!

 Hola soy Elthan el tío q tradujo eso, mi primer dia de visita a Stratos y me encuentro con esto.

Joder Patrick Lester me ha cogido mi traducción sin pedirme permiso... yo para traducir ese tocho si q tuve q
pedirle permiso a él.

En fin espero q te sea de ayuda, si el A* te resulta muy complicado puedo indicarte algun q otro método muchisimo mas simple y casi igual de eficiente.

X cierto, Patrick no ha publicado todo el documento completo, ahora mismo se lo envío.

[[Vil]]

 Un saludo Elthan! a ver si te veo el pelo más por estos foros!

[dracks]

 Muchissimas gràcias... Si no entiendo algo, pos, ya pedire ayuda... pero espero entender-lo...

Elthan muchas gràcias y lo tengo en cuenta, y si no lo entendiesse, pues ya pediria ayuda, ahora vuelvo a tener el Robots en la cola de tareas, es el problema de no poderme clonar :P que solo puedo ponerme a hacer una cosa a la vez... y en este momento estoy con una practica de la uni...

Si quereis ver mi cutre-juego, pos, me lo decis, i os lo hago llegar... mediante e-mail...


Suerte, y vuelvo a repetir muchissimas gracias...

[marcode]

 Gracias Elthan. (ole)  

[Elthan]

 Vil acabo de registrarme, te aseguro q a partir de ahora me verás más.

marcode y dracks: no hay de que.

Solo he de subrayar 2 cosas:

 1.- Q aunq en la pagina de patrick solo haya publicado 1 articulo, en realidad hay 3 más
 2.- Hay otros algoritmos de pathfinding mucho más sencillos y fáciles de implementar. Como ya ye he dicho yo mismo creé una variante del flood fill q es tan simple q cualquier persona con unos minimos conocimientos de programación puede comprender.

[chechocossa]

 Elthan, se puede ver pseudocode o el algoritmo de esa variante que hablas?

[Elthan]

 Y tanto, imagina q lo hice para Darkbasic Pro.

Si has visto alguna vez un codigo de dbpro habras podido observar q es casi pseudocódigo. Aún así no solo tengo hecho el propio codigo, sino q tb cree un tutorial a la postre.

Aqui lo tienes:
http://portalxuri.dyndns.org/darkbasico/de...iales/ameba.zip

Ten en cuenta q este algoritmo no esta para nada optimizado, y aunq encuentra un camino en un mapa de 100x100 en pocos milisegundos no es lo q diriamos una liebre.

Este algoritmo es util para la gente q nunca ha comprendido el tema de la busqueda de caminos, es decir, q está pensado para no asustar. Cuando lo veas podras ver q incluso el num de lineas q lo compone es realmente ridiculo.

Un amigo mío creo una versión optimizada del mismo, esa versión optimizada es increiblemente rápida. Tanto q en muchos casos puede incluso vencer al A*.

Si quieres, una vez q lo asimiles hablamos de las cosas tipicas como la restriccion a 4 direcciones o la esquiva de las esquinas al hacer movimientos en diagonal.

[chechocossa]

 Muchas gracias, Elthan, lo voy a ver.

En realidad, me interesa algo simple, aunque no sea ultrarápido o demasiado exacto, para implementarlo en juegos para móviles.

Por lo general he visto que cosas como A* consumen mucha pila... y bueno, es una de las limitaciones con este hardware.

Saludos!

[Pogacha]

 Sobre path finding:

La busqueda del camino minimo es un problema cubico, dadas ciertas condiciones puede llevarse a mejor andar ( en una maquina mono procesante ) a n log2 n con respecto a los arcos, en nuestro caso: Un tablero de nodos con arcos conocidos y valores unitarios,  levemente conexo, y con euristicas de proximidad triviales. Este no pasa de lineal con respecto a los nodos  :P

Resolución trivial. Busqueda en ancho.

Se marcan todos los nodos con la peor marca. Se marcan los nodos imposibles para invalidar las adyacencias no deseadas.
Se vacia una cola.
Se agrega a la cola el nodo "Destino" el cual es marcado con 0
Mientras la cola no este vacia y no llegué a "Origen": se toma elemento de la cola y para cada adyacente valido se compara la marca con la de este nodo mas uno, si es menor, se marca el nodo adyacente con este valor y se agrega a la cola.
Terminado el bucle me aseguro de que la cola este vacia.
Desde el nodo "Origen" buscar cualquier adyacencia que tenga una marca menor, agregar a la cola y recursar hasta llegar al nodo "Destino".
En la cola esta el camino desde Origen a Destino, ojo que el tamaño de esta cola puede ser muy grande, el tamaño maximo sera n/2!

Aun asi este algoritmo es lento, muy lento ...
La primera optimización que se puede hacer es hacerlo goloso, o sea que trate de acercarse al destino a medida que recorre el grafo dando prioridad por la euristica de proximidad que es la distancia real de un nodo al final, esto mejora bastante la situación.
Otra optimización importante para mapas grandes, es precomputar el grafo y determinar conexividades, de esta manera se crea otro grafo hecho de zonas donde se sepa que el camino minimo sera la linea recta ( no hay obstaculos entre medio ), el grafo debera ser dinamico para el caso de que halla obstaculos dinamicos . En este caso nuestra busqueda en ancho no nos servira y deveremos recurrir a nuestro nunca bien ponderado Dijsktra para recorrer nuestro grafo de zonas ... pero esto es otra historia.

Saludos.