Pequeña duda acerca de A*

[NullPointerException]

Vale, tengo claro que este algoritmo encuentra el mejor camino entre 2 nodos y que se basa en una funcion F que va en funcion del coste (G) y la Heurística (H).

La Heurística se calcula el coste "a ojo", o sea, cuanto costaría llegar al nodo final.

Pero en donde tengo dudas es en el coste real (G). Como calculo este coste?

Miro un nodo y, para ese nodo, miro el coste real de sus hijos de forma recursiva?

[bnl]

Es la suma de los costes de todas las aristas recorridas hasta llegar a ese nodo

Si de A te mueves a B con un coste de 3 y luego a C con un coste de 2. G seria igual a 5

[NullPointerException]

Es la suma de los costes de todas las aristas recorridas hasta llegar a ese nodo

Si de A te mueves a B con un coste de 3 y luego a C con un coste de 2. G seria igual a 5

Y el coste que se le pone a una arista es arbitrario o hay algún concepto en que basarse?

[Darago_malaga]

El coste es en realidad la distancia que hay entre una arista y la siguiente.

Si se hace con cuadrados de una unidad de distancia, el coste de un cuadrado al los adyacentes es 1 si tambien usas las diagonales es la raiz de 2.

[NullPointerException]

El coste es en realidad la distancia que hay entre una arista y la siguiente.

Si se hace con cuadrados de una unidad de distancia, el coste de un cuadrado al los adyacentes es 1 si tambien usas las diagonales es la raiz de 2.

Vale, ahora me ha quedado mas claro :)

[Hechelion]

El coste es en realidad la distancia que hay entre una arista y la siguiente.

Si se hace con cuadrados de una unidad de distancia, el coste de un cuadrado al los adyacentes es 1 si tambien usas las diagonales es la raiz de 2.

Disculpa, pero hasta donde yo tengo entendido eso no es del todo correcto.

Los costos son arbitrarios y dependen de lo que quieras representar con el movimiento, ya que A* funciona de forma abstracta y sirve para calcular caminos entre nodos independiente de la distribución que tengan. En A* no existen reglas sobre los costos, estás las debes definir tú (o sea, arbitrarias)
Ejemplo de esto lo encuentras en civilization (anteriores al V), donde los movimientos diagonales NO tienen penalización, el costo depende del tipo de terreno al cual te mueves y no de la distancia recorrida (o sea diagonal o no).

Otro ejemplo, sería un mapa hexagonal, todos los nodos adyacentes se encuentran a la misma distancia y no hay penalización extra.

Lo que tu colocaste como coste, es un caso particular, donde te interesa penalizar las diagonales y aunque está perfecto para ese caso en particular no es una verdad universal sobre A*.

[bnl]

Iba a comentar lo mismo que Hechelion.
El coste hay que definirlo dependiendo de cada caso. En algunos se podra mover en diagonal, en otros no, en otros ni siquiera los nodos formaran una cuadricula. Incluso ademas de por el terrerno puede variar en funcion de la unidad que se este moviendo. O por cualquier otro aspecto del juego.

Una caso muy habitual el de los cuadrados que comenta Darago_malaga que se conoce como la distancia manhattan



Donde la distancia mas corta no es la linea recta (linea verde)

[Darago_malaga]

Suponia que quedaba claro que me referia al caso mas simple posible. En el que el coste solo depende de la distancia. Evidentemente se puede complicar el costo teniendo en cuenta el tipo del terreno, la dificultad al avance para una unidad dada, el viento o la maldad de unos programadores demasiado quisquillosos.  ;););)

Enserio...mi consejo es que empieces por el metodo mas simple posible y luego lo compliques segun tus necesidades.

[NullPointerException]

Vale, gracias a vosotros la cosa ya me va quedando mas clara :)

Ahora donde tengo dudas esta en el tema de las listas abiertas y la cerrada. Estoy buscando un ejemplo práctico donde te muestre la evolución del algoritmo paso a paso y que te vaya indicando la lista de abiertos y de cerrados.

[Darago_malaga]

A ver que te parece este tuto:

Esta en español:

http://www.policyalmanac.org/games/articulo1.htm

[blau]

Aquí tienes mis prácticas de IA donde podrás ver visualmente el árbol de búsqueda y puedes aplicar distintos algoritmos y distintas métricas para el coste.

http://www.youtube.com/watch?v=08yo1afSgmc

En la descripción está el enlace al código fuente en C#

[Vicente]

La lista de nodos abiertos y cerrados conceptualmente es bastante simple.

La lista de nodos abiertos es los nodos a los que el algoritmo puede llegar. Es decir, imagínate que comienzas en un punto, y de ese punto te puedes mover a las 8 casillas adyacentes, pues esas 8 casillas adyacentes serían la lista abierta.

La lista de nodos cerrados son los nodos por los que el algoritmo ya ha pasado. Da igual que sean parte de la solución o no, son nodos que el algoritmo ya ha encontrado el camino más corto para llegar a ellos y no va a volver a visitarlos nunca más.

Siguiendo el ejemplo anterior de las 8 casillas adyacentes, cuando el algoritmo elija moverse a una de esas 8 casillas, esa casilla pasará a estar en la lista cerrada, y en la lista abierta se añadirán más casillas adyacentes. Hay que tener en cuenta que una casilla no se añade dos veces a esta lista, si está dos veces te quedas con la que tenga el coste más pequeño.

Un saludo!

Vicente

[NullPointerException]

La lista de nodos abiertos y cerrados conceptualmente es bastante simple.

La lista de nodos abiertos es los nodos a los que el algoritmo puede llegar. Es decir, imagínate que comienzas en un punto, y de ese punto te puedes mover a las 8 casillas adyacentes, pues esas 8 casillas adyacentes serían la lista abierta.

La lista de nodos cerrados son los nodos por los que el algoritmo ya ha pasado. Da igual que sean parte de la solución o no, son nodos que el algoritmo ya ha encontrado el camino más corto para llegar a ellos y no va a volver a visitarlos nunca más.

Siguiendo el ejemplo anterior de las 8 casillas adyacentes, cuando el algoritmo elija moverse a una de esas 8 casillas, esa casilla pasará a estar en la lista cerrada, y en la lista abierta se añadirán más casillas adyacentes. Hay que tener en cuenta que una casilla no se añade dos veces a esta lista, si está dos veces te quedas con la que tenga el coste más pequeño.

Un saludo!

Vicente

Ahora que lo explicas de esta manera me ha quedado más claro el funcionamiento del algoritmo. Se agradece mucho :)

[Vicente]

Me alegro! :) A* es de esos algoritmos que una vez hacen click son triviales, pero que cuesta un poco que hagan click :)

[NullPointerException]

Me alegro! :) A* es de esos algoritmos que una vez hacen click son triviales, pero que cuesta un poco que hagan click :)

Una vez se entiende ya es más sencillo de implementar :)