Un poco perdido en A*

[BitEver]

Hola, me sabe mal registrarme en un foro para comenzar pidiendo ayuda, pero no llevo mucho tiempo en esto, y buscando por internet donde podría encontrar ayuda, he visto que este era uno de los mejores foros para ello.

Mi duda es más que de entender lo que hace que de programación, a ver si se explicarme correctamente:

Según entiendo, el algoritmo coge el primer nodo, lo convierte en padre, y mira todo los nodos vecinos, los mete en la lista abierta, y el nodo padre a la lista cerrada.
Después calcula el F de todos los nodos vecinos, y el que tenga el F más bajo, pasa a la lista cerrada.
Aquí el algoritmo empieza de nuevo, con el nuevo nodo padre, a buscar los nuevos nodos vecinos (descartando paredes, etc...) y volver a calcular el F.

Esto es lo que yo entiendo, pero aquí me surgen las dudas, que pasa cuando se encuentran dos Nodos vecinos con el mismo valor F??

Claro según como tengo configurados los nodos, el que lee primero como nodo con F más bajo es que pilla, pero a veces ese camino es el más largo.

Otra cosa que no entiendo muy bien, es como se hace al final cuando se llega al Nodo Objetivo, para dar la vuelta recorriendo todos los nodos, para que? si ya los has calculado en la ida??

Una ultima cosa, cada vez que se empiezan a analizar los Nodos Vecinos, hay que dejar la lista Abierta vacía?? y empezar a meter los nodos vecinos en la lista vacía??

Un saludo.

[Vicente]

Joer, nunca me acuerdo de la nomenclatura de lista abierta y lista cerrada, creo que la cerrada son nodos que ya has visitado y la abierta son nodos a los que puedes llegar desde los nodos de la lista cerrada. Segun eso:

a) si tienes dos iguales, coges el que quieras, es indiferente para el algoritmo (pero intenta deshacer los empates siempre de las misma manera).
b) A* puede haber mirado nodos que estan en la lista cerrada, pero no son parte del camino, por eso necesitas "caminar hacia atras" cuando llegas al final, para ver porque nodos pasaste.
c) Sobre la lista abierta (creo que esos son los posibles candidatos a visitar), no se vacia. Si la vacias el algoritmo no va a funcionar, porque A* puede muy bien investigar un camino que parece bueno y luego darse cuenta que hay otro mejor (o que ha llegado a un callejon sin salida).

A ver si te ayuda :) Un saludo!

Vicente

[BitEver]

Muchas gracias por la pronta respuesta, Vicente.

Sí, como dices, al menos como he leído hasta ahora, lista abierta es para poner los nodos que se van a analizar(nodos vecinos), descartando las paredes, etc... y la lista cerrada, se ponen los elegidos con el valor F más bajo.

Entonces, según me dices, si cojo el que quiera, a la hora de un empate, hay veces que me encuentra el camino más largo, que tengo que hacer?? analizar todos los posibles caminos, y después volviendo para atras es cuando se va eligiendo el camino correcto y más corto?

A la hora de llegar al final, que tengo que recorrer la lista cerrada hacia atrás, esto la verdad es que no entiendo mucho, el resultado no tendría que ser el mismo??

A ver si es que no estoy entendiendo el concepto bien, y por eso no me sale:

Tengo un Punto de inicio y un Punto final, el Punto de Inicio directamente lo añado a la lista cerrada, entonces cojo todos los vecinos transitables de este Punto, los meto en la lista abierta, calculo su valor F, y cojo el que tiene menor valor F, y lo meto en la lista cerrada. En caso de haber dos valores iguales F que son los más bajos, meto los dos en la lista cerrada. A partir de aqui obtengo todos los nodos vecinos del Nodo que he metido en la lista cerrada, y si son dos, obtengo los de los dos, y voy haciendo esto hasta llegar al Punto Final.

Una vez llegado a este Punto final, que tengo que hacer, ir recorriendo al revés, es decir desde punto final a punto inicio, haciendo los mismos pasos que al llegar hasta el punto final? O tengo que ir siguiendo, a traves de la lista cerrada o abierta, conseguida con el camino de ida??

Mas o menos, esto es la idea que he entendido, de lo que he podido leer.

Como ves estoy un poco perdido en el concepto, mañana volveré a intentarlo, hoy llevo todo el día con el, pero no lo he conseguido, pero no me gusta rendirme.

Gracias de nuevo por la ayuda.

[blau]

Vamos a ver:

1º. Para evitar recorrer la lista al reves para obtener el camino, un simple truco es intercambiar los nodos inicial y final.

2º. En la lista abierta tienes los nodos que no has llegado a procesar todavia y en la cerrada tienes los procesados.

3º. Procesar un nodo significa obtener todos sus vecinos y añadirlos a la lista abierta sin son accesibles y no han sido procesados (estan en la cerrada) . Si estuviese en la lista de abiertos hay que comprobar cual de los nodos que te llevaron a este nodo tiene un coste menor y actualizar el padre en consecuencia.

EDIT: Veo que estas algo liado con el tema del padre.
Cuando añades un nodo a la lista abierta tienes que asignarle quien es su padre para saber a traves de que nodo llegaste a el. A traves de este padre podras obtener el camino una vez hayas encontrado el nodo final.

4º. La lista abierta estara ordenada por un criterio de coste de llegar hasta ese nodo.

5º. Muy importante: A* no devuelve el camino mas corto. Devuelve un camino. De lo que se trata es de que de una solucion lo mas rapido posible. Asi que los empates no te deben preocupar.

6º Si quieres que te de el mejor camino, no pares cuando hayas alcanzado el nodo final, sino cuando se vacie la lista abierta completamente.

Espero que te sirva de algo. Un saludo.

[BitEver]

Creo que ahora si que lo acabo de entender, tenías razón, me faltaba por entender la función del padre, que además de servir para seleccionar todos los Nodos vecinos, sirve para saber a la vuelta el camino correcto, pasando de hijo a padre.

Muchas gracias de verdad, ojalá todo el mundo fuera como aquí, hay veces que en algunos foros uno ya no se atreve a preguntar, por la manera en que se trata a uno, cuando los demás saben una cosa, que tu no sabes.

Voy a tirarme todo el día hasta la noche a intentar plasmarlo en el código, con los conceptos mejor entendidos por vuestra ayuda. Como puede enganchar tanto esto?? Me levanto pensando ya en el código...

Saludos!

[Vicente]

Estooo, A* tiene dos propiedades:

- es completo: si existe una solucion te garantiza que la encuentra.
- es optimo: si existen varias soluciones, encuentra la mejor.

Si no te encuentra el camino mas corto las causas pueden ser:

- el algoritmo esta mal
- la heuristica estima mal (puede ser por la propia heuristica o porque el mapa tenga cosas raras como teleportadores)

Para comprobar si es el algoritmo o la heuristica lo que esta mal, puedes poner la heuristica del algoritmo de dijkstra (el coste estimado es siempre 0), y asi ves el camino que te sale (deberia visitar muchos mas nodos, pero al final deberias tener el camino mas corto). Lo de los empates dan igual, mete el nodo que quieras, si luego hay otro camino mas corto el algoritmo deberia encontrarlo.

[Vicente]

6º Si quieres que te de el mejor camino, no pares cuando hayas alcanzado el nodo final, sino cuando se vacie la lista abierta completamente.

Una puntualizacion, A* termina cuando sacas el nodo destino de la lista abierta. No hace falta vaciarla del todo. Es decir, imaginate que tienes el nodo final en tu lista abierta y es el nodo con valor mas bajo. El nodo final tiene de coste estimado 0, es decir, su coste total es el coste real de llegar hasta el, y si es el mas bajo, es porque por cualquier otro camino A* piensa que va a tardar mas, y si la heuristica es correcta, es porque realmente va a tardar mas, asi que ya has encontrado el mejor camino :)

[blau]

Yo tengo la percepcion de que A* no tiene porque devolver el mejor camino, aunque si que es cierto que dara uno muy cercano al mejor, no te lo garantiza.

Si permites que se vacie la lista de abiertos, el algoritmo te da un resultado como el de dijkstra que si que es el mejor, puesto que ha comprabado todas las posibles soluciones.

[Vicente]

Si A* tiene una heuristica que cumple que:

- es admisible: nunca sobre-estima el coste para llegar al nodo objetivo.
- es  monotona: el coste estimado en el nodo objetivo es 0.

Entonces A* te garantiza las tres siguientes:

- completo: encuentra una solucion.
- optimo: encuentra la mejor solucion posible si hay varias.
- eficiente: ningun otro algoritmo que te garantice ser optimo y completo va a expandir menos nodos que A* con la misma heuristica.

Y esta demostrado :)

Djikstra simplemente es un caso especial de A*. La heuristica de Dijkstra es admisible y monotona, asi que por eso encuentra el mejor camino posible, pero como su estimacion se queda muy lejos de la realidad, expande muchos nodos. Cuanto mas cercana sea la heuristica que elijas a la realidad, menos nodos expande A*.

Si la heuristica no es admisible, entonces es posible que A* expanda menos nodos para llegar al objetivo pero ya no te garantiza que el resultado sea optimo.

[blau]

Si la heuristica no es admisible, entonces es posible que A* expanda menos nodos para llegar al objetivo pero ya no te garantiza que el resultado sea optimo.

Me quedo con eso... :)

Aunque usando el la función de mahattan y para la mayoría de situaciones que se plantean en los juegos puede ser mas que suficiente y ciertamente tendrás la mejor solución.

Yo mi duda la habia planteado desde el punto de vista de que a veces te puede interesar por condiciones de diseño que los nodos que visitas tengan un coste no fijo, sino asociado a zonas menos peligrosas o a zonas por las que prefieres pasar para caminos largos, en las que la heuristica es mas dificil de calcular y por eso puedes tener soluciones no optimas.

De todas gracias por aportar una informacion tan formal al respecto... me ha venido bien reconsiderarme el tema.

Ya puestos, últimamente le he estado dando vueltas a un juego de estrategia/puzzle en la que necesito lidiar con formaciones, ¿algun material interesante por ahi?

[Vicente]

Formaciones al estilo de tener un monton de bichos y que se muevan de forma ordenada? Si es eso tienes el tema de flocking:

http://www.red3d.com/cwr/boids/

Y lo bueno es que es bastante facil de implementar :) Si es formaciones mas al estilo de como coloco mis bichos para maximizar su eficacia, (arqueros delante, piqueros detras pero cerca, caballeria a los lados, y cosas asi), poca cosa :( Mirare a ver si encuentro algo.

[blau]

Hay mucha informacion ahi, pero no es extactamente, eso lo que busco, aunque pueda inferir algunos cosillas de ahi.

Me refiero mas bien a soldados, que van hacia un mismo lugar y que dependiendo de la accion, pueden quedarse en formacion, buscar una posicion optima para atacar, o rodear a un enemigo y sobre todo evitando colisiones con los obstaculos del terreno.

Mucha tela... :)

[Vicente]

Para eso lo mejor son arboles de comportamientos (behavior trees). El mejor lugar para comenzar con ellos para mi es aigamedev:

http://aigamedev.com/open/articles/bt-overview/
http://aigamedev.com/insider/presentations/behavior-trees/ (te tienes que registrar para ver esta, pero es gratuito y merece la pena)

Otro articulo que tiene buena pinta (no lo he leido a fondo).

http://altdevblogaday.org/2011/02/24/introduction-to-behavior-trees/

Si buscas salen bastantes mas articulos e incluso algunas implementaciones. Por ejemplo:

http://behaviortrees.codeplex.com/

Y con eso ya tienes un monton para leer :D

[blau]

Perdona BitEver.. pq me estoy aprovechando del post, pero sguiendo el hilo voy a exponer mi idea sobre el algoritmo que estaba maquinando para las formaciones.

La idea es calcular con Dijkstra el mapa, puesto que tengo un mismo destino para todos los soldados y los mapas no son muy grandes, o se pueden limitar por zonas.

El caso es que de esta forma de cada celda del mapa tengo cual es la siguiente celda que debería escoger para llegar al destino.

El grupo tiene un esquema de formación predefinido que se ajusta a las celdas, y en cada celda solo puede haber un soldado.

A la hora de mover al grupo elijo un soldado como referencia, y según lo que haga este soldado intentaran actuar los demás. Es decir se moveran igual que el soldado de referencia.

Para cualquiera de los demás soldados:

Si no puede continuar porque la celda esta bloqueada por otro soldado que este  en movimiento, esperara su turno hasta que se libere la celda.
Si alguno de los demás no puede continuar porque la celda no es accesible, intentar seguir a por la celda que a la que le pertenecería ir por calculo del camino.
Si llega a la celda que le toque por su formación que se pare,
Si intenta acceder a una celda ocupada por un soldado en su formación definitiva que haga una  búsqueda A* pequeña para llegar a su puesto en la formación.

Y la idea es que según la acción a desarrollar pueda cambiar la formación.

Voy a ver si lo implemento estos días festivos y se mueve bien. Aunque tengo muchas cosas pendientes... veremos a ver si tengo tiempo para todo. :)

[TrOnTxU]

Este hilo se pone interesante  :o

Mucha información y bien contrastada :)

En cuanto a utilizar behaviour tree para formaciones al estilo rts, creo que es una aproximacion. Pero personalmente, y aunque he utilizado y estoy utilizando algunas implementaciones de behavior trees (y alguna simplificacion rollo decision trees), para un RTS quizas utilizaria otros tipos de toma de decisiones. Pero quizas el planificador para controlar las tareas de cada agente y por grupo, y un diseño del arbol basada en GOALS funcione, no lo sé  ???

Para calcular las influencias de areas peligrosas, etc en un mapa de "celdas" hay bastantes articulos de "influence maps" por ahi.
En aigamedev hay algunos pero son premium. Creo haber leido algo tambien en un "game programming gems" o "ai programming widsom"  (puedes buscar en las tablas de contents de la web para ver si esta en alguno).
En aigamedev hay un articulo sobre potential fields que quizás te http://aigamedev.com/open/tutorials/potential-fields/:

Espero haber sido de ayuda

ADEW!

[EDIT] una pagina con el toc de game programming gems: http://www.asawicki.info/Download/Misc/GameProgrammingGemsTOC.html