A la busqueda de un algoritmo

[Altair]

Buenas,

he estado leyendo sobre algoritmos de busqueda de caminos, y como veo que hay tropecientas opciones necesito algo de orientacion, os cuento un poco los detalles del caso.

Tenemos un escenario 2D de una resolucion 320 x 240 que es el mapa del juego, luego aparte tenemos un mapa de durezas de la misma resolucion, con dos colores. El color negro es no pisable (pared) y el blanco es pisable (suelo).

Ejemplo clasico: un laberinto. El jugador esta a la izquierda de la pantalla y la salida esta a la derecha

Al principio pense en usar el algoritmo A *, pero leyendo por Internet me encuentro con distinas opiniones. Que si tiene un coste computacional demasiado elevado, que si es orientado a grafos y no a cuadriculas, que si es el mas sencillo, etc.

Navegando por Google me encontre esto http://es.wikipedia.org/wiki/Categor%C3%ADa:Algoritmos_de_b%C3%BAsqueda

me he pasado por GameDev, pero solo ha servido para confirmar que lo relacionado con la IA es muy amplio. Busco saber cual es el algoritmo (o algoritmos) que mejor suelen adaptarse a este caso en concreto.

Estoy usando C/C++ y SDL

[blau]

El A* es una buena base... luego tendras que optimizar o buscarte la vida, para ir adaptandolo a lo que necesitas...


yo por ejemplo para un juego de defensa de torres no usaba A*, iba a Dijsktra a saco, y siempre calculaba el mejor camino... ¿que tardaba 0.5s en terminar en 256x256? ¿Y cual es el problema pregunto yo? las unidades empezaban a moverse sobre una solucion parcial y si habia ruta continuaban y si no se paraban a los 0.5s...

aun asi luego mejore el algoritmo porque me di cuenta que las destinos son siempre los mismos, asi que idee una busqueda que se basaba en la anterior desde el punto donde habia bloqueado el camino con una torre, y entonces la mayor parte de las veces era cero coma lo que tardaba...

caminante no hay camino... se hace camino al andar.. ;)

[Altair]

En este caso, el personaje debe aprender cuando ha llegado a un callejon sin salida y volver atras.

Hace algun tiempo hice el A * en DIV2, con casos en que el obstaculo era la letra "C", el personaje estaba a la izquierda de la letra y la salida estaba dentro de la "C". Funcionar funciono, pero joer lo que le costo...

[Altair]

Estoy mirandome Dijkstra y mira tu por donde, tal vez era justo la pista que necesitaba, estoy haciendo pruebas.

[Vicente]

Recuerda que Dijkstra se puede ver como un caso especial de A* donde la heurística siempre devuelve 0.

[Hechelion]

Al principio pense en usar el algoritmo A *, pero leyendo por Internet me encuentro con distinas opiniones. Que si tiene un coste computacional demasiado elevado, que si es orientado a grafos y no a cuadriculas, que si es el mas sencillo, etc.

El A* si te sirve para cuadriculas, si lo quieres pensar como grafos, entonces simplemente piensa que cada cuadricula es un punto que se encuentra conectado a sus 4 adyacentes (u 8 si usas las diagonales) y así sucesivamente. Además, Dijkstra también está orientado a grafos y no por eso deja de ser valido para cuadriculas.

Además 320*240 son más menos 10.000 grafos, y eso, un PC actual lo resuelve en menos de un segundo, Considerando el pero escenario en el cual el algoritmo deba revisar el mapa completo, lo que es raro, normalmente el camino se encuentra sin recorrer todo los caminos. Eso si, por lo que leo en tu post, debes tener en cuenta que A* y Dijkstra encuentran el camino más corto, no vas a ver al personaje buscando el camino, si no, que el algoritmo te retorna el camino más corto a seguir.

Si quieres que el personaje vaya recorriendo el laberinto y buscando la salida a medida que lo recorre, entonces busca por algoritmos para laberintos, así vas a encontrar un par que encuentra la solución a medida que avanza en vez de precalcularla.

[Altair]

Veamos, estoy trasteando con un algoritmo basado en Dijkstra, para tener un escenario mas claro he cogido unos cuantos mapas de pacman.

Lo esbozo un poco: trabajamos con dos mapas, uno es general y contiene todo; el otro es especifico de la zona. Baldosa es solo una casilla pisable, y pasillo son dos o mas baldosas contiguas.

El asunto es destacar todos los pasillos, tanto en horizontal como en vertical. Se pone un nodo de control en cada inicio de pasillo, fin de pasillo y en cada interseccion de pasillos. Es decir, en cada esquina y en cada cruce.

De esta forma, cuando tenemos un nodo-origen y un nodo-destino, solo hay que saber cual es el primer nodo del camino, y por tanto a que baldosa hay que ir.

¿Como lo veis?. ¿Me estoy complicando?, ¿voy en una direccion mas o menos correcta?, ¿falta o sobra algo?

Estoy haciendo pruebas sobre el papel y parece funcionar. Eso si, parece bastante laborioso de programar el tema de "cualquier nodo a cualquier nodo". Menos mal que esa parte es solo con el mapa especifico de zona, y no con el mapa general.

[Hechelion]

Por lo que describes, diría que vas bien, en especial si quieres optimizar, pero date cuenta de lo siguiente.

Si tienes un pasillo de 5 baldosas tienes 2 formas de atacar el problema

Una, es optimizar y decir que esas 5 baldosas son en realidad 2 nodos y los voy a llamar Nodo Inicio y Nodo Final.

La otra, es dejar las 5 baldosas como 5 nodos y dejar que el algoritmo las recorra uno por uno. En ese caso, como es imposible doblar a la izquierda o a la derecha, el algoritmo por si sólo va a llegar del Nodo Inicial al Nodo final, la diferencia es que si no optimizar por pasillo, el algoritmo hará 5 cálculos de nodo en lugar de 1, es más fácil de programar porque todo tu mapa son solo baldosas o cuadrados y le dejas la carga a la CPU.

Acá viene la decisión, ¿Qué es mejor para tu juego?. que la CPU haga 5 calculos u optimizar y disminuir los nodos.
Si tu mapa es de 320*240, mi respuesta es que dejes todo como baldosas y dejes que el algoritmo descubra el camino.

[Altair]

Llevo unos cuantos dias dandole al asunto este, he aprendido unas cuantas cosas que no conocia (gracias, wikipedia) y he terminado elaborando un metodo que no se si existe ya o que, porque despues de tanto algoritmo, tanta "variante de" y tanta historia, llega un momento que marea hasta lo indecible.

Paso a describir el metodo, potenciales meteduras de pata aparte.

retro_preview.png

   Este es el mapa inicial, donde tenemos las baldosas y las paredes. La imagen esta sacada de Kapman, un clon de Pacman en KDE.

   Las zonas negras interiores indican suelo pisable (baldosa) y las claras son las paredes.

regiones_pintadas.png

   Aqui tenemos las distintas zonas del mapa inicial,destacadas cada una de un color.

region_1_zonas.png

   Necesitamos poner nodos en puntos concretos, de forma que sea cual sea Origen y sea cual sea Destino, sepamos exactamente a que baldosa ir.

   Un problema que presenta esto es que hay que poner el menor numero de nodos posible; a mayor numero de nodos, mayor cantidad de calculos.

   Para saber donde colocar cada nodo, debemos trazar lineas que indiquen donde esta cada pasillo. Un pasillo se forma cuando dos o mas baldosas
   van en la misma direccion, sea horizontal o vertical.

   Las lineas rojas indican los pasillos horizontales, las lineas amarillas los verticales.

region_1_nodos.png

   En cada interseccion ponemos un nodo (verde).

region_1_nodos_ejemplo.png

   Los nodos tienen dos tipos de conexiones: directa y remota. Entre el nodo rojo y el nodo amarillo hay una conexion directa, pues hay un pasillo que
   lleva de uno a otro. Entre el nodo rojo y el nodo azul hay una conexion remota, pues hay que pasar por al menos un nodo adicional para llegar a el.

   En este mapa de ejemplo, un nodo puede tener un maximo de cuatro conexiones directas, una por cada lado. Cada nodo tiene unas coordenadas XY definidas,
   por lo que ir de uno a otro es directo.

   Si vamos del nodo rojo al azul, necesitamos recorrer las baldosas hasta encontrar el camino mas cercano.

   El siguiente algoritmo se basa parcialmente en el "Metodo del Comerciante", consistente en que cada nodo solo se puede visitar una vez.

   Para ir del rojo al azul necesitamos unas normas:

   * Tenemos un total de 10 nodos, pues se descuenta el nodo inicial (rojo). Esto hace un grupo de X (numero desconocido) "comerciantes".
   * Cada nodo sabe cuales son sus nodos directos, en caso del nodo rojo son sus nodos directos verde y amarillo.
   * Cada vez que llegamos a un nodo, sale un comerciante hacia cada uno de los nodos directos, excepto hacia el nodo directo del que venimos.
   * Cada comerciante tiene una memoria que indica el numero del nodo por el que ha pasado.
   * Antes de ir a un nodo, el comerciante comprobara su memoria. No se puede ir mas de una vez a un nodo concreto.
   * Si un comerciante no puede avanzar en un momento dado por estar "atascado", consultara su memoria para retroceder una o varias posiciones y continuar.
   * En el momento que un comerciante alcance el destino, se consulta su memoria para conocer la primera posicion de su trayecto. Fin de la exploracion.

   Esto en si mismo es algo asi como una exploracion por fuerza bruta, estilo recorrido en profundidad de arboles binarios.

   No soy experto en temas de inteligencia artificial, pero me da la impresion que es un algoritmo que consume bastante.

   Supongamos un juego en el que tenemos varias decenas, o incluso cientos, de enemigos que recorren un trayecto, usar ese algoritmo en cada paso que dan, con
   cada uno de los enemigos, no parece practico. Esto me ha hecho pensar en tablas precalculadas, a modo de un array 2D. Si estas en el nodo X y quieres ir
   al nodo Y, sabes directamente que tienes que viajar al nodo Z, que es el primer paso para llegar al nodo Y.

Y esto es todo, no se si lo he complicado innecesariamente, o si ya hay algun algoritmo que haga lo mismo, o que
Lenguaje usado, C/C++

Link a donde esta todo:

http://rapidshare.com/files/448065301/Algoritmo.tar.gz

[Vicente]

Muchas veces en juegos con muchas unidades (como por ejemplo el Starcraft), el pathfinding lo hacen solo unas pocas y las demás les siguen (por eso se ponen en fila cuando las mueves de una esquina a la otra del mapa :p).

Optimizaciones luego hay mogollón, pero depende del tipo de juego.

[Altair]

Veamos, el motivo por el que estoy siendo tal vez un poco difuso es porque no estoy haciendo un juego, sino una libreria.

La idea es usar el lenguaje C, con la libreria SDL y  otras asociadas (SDL_image, SDL_ttf, etc) para facilitar la creacion de juegos 2D bajo Linux. Seria algo asi como una especie de DIV2, pero en Linux.

DIV2 tenia un algoritmo para esto, el "A estrella", y la superficie del mapa de durezas era de como maximo 256x256 pixels. Todo este asunto es para eliminar las limitaciones que en su dia dio el algoritmo (como usuario que fui, para algunas cosas era un calvario), tras leer unas cuantas opiniones por ahi y por alla, pense que posiblemente una buena opcion seria tablas precalculadas. De esta forma, esten donde este el punto de origen del trayecto y el punto destino, se va siempre por una ruta optima.

La verdad es que tengo ganas de tener este asunto resuelto, porque a la libreria le queda muy poco ya para terminarse y publicar la beta1, bajo licencia LGPL

[Vicente]

A* tiene una propiedad matemática muy graciosa: no existe algoritmo mejor posible :D

Sobre que permitir al usuario de tu librería, a veces A* es la mejor solución, otras veces podrás usar rutas precalculadas,... No existe la solución perfecta para todos los problemas desgraciadamente, y menos en la IA que es muy específica de un juego. Tienes que darle unas bases, y luego que el usuario las adapte, y si no puede o le dan problemas, ya te darán feedback de que hace falta.

Otra alternativa, es que antes de lanzar tu librería hagas un par de juegos con ella, ya verás como descubres mil cosas que cambiar o corregir... Un saludo!

[Altair]

Ya hay, a modo de tutorial, una serie de mini-programas que muestran el funcionamiento de la mayoria de las cosas.

Tal vez lo mejor sea hacer la libreria sin un algoritmo concreto de busqueda de caminos, y que los usuarios aporten diversos algoritmos adaptados a la forma de trabajar de la libreria.

[[EX3]]

Otra alternativa, es que antes de lanzar tu librería hagas un par de juegos con ella, ya verás como descubres mil cosas que cambiar o corregir... Un saludo!

Muy cierto! No te haces idea de las cosas que descubres que le faltan a tu herramientas hasta que intentas desarrollar juegos con ella :)

Ya hay, a modo de tutorial, una serie de mini-programas que muestran el funcionamiento de la mayoria de las cosas.

No es lo mismo, una cosa es probar funciones por separado y otra crear un programa que realmente las ponga a todas en conjunto, osease, un juego.

Yo te diria que trataras de hacerte algun minijuego para ver capacidades de la libreria e incluso testar el rendimiento de la misma (una prueba de estress) :)

Salu2...