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.
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
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.
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.
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!
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.
Cita de: blau en 20 de Abril de 2011, 09:28:48 AM
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 :)
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.
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.
Cita de: Vicente en 20 de Abril de 2011, 05:16:54 PM
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?
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.
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... :)
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
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. :)
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/ (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 (http://www.asawicki.info/Download/Misc/GameProgrammingGemsTOC.html)
Los AI Game Programing Wisdom estan bastante bien la verdad. Mirando los libros:
- En el 1 tienes una seccion entera llamada "Tactical Issues and Intelligent Group Movement". Unas 70 paginas con 6 articulos (uno de ello llamado Formations).
- En el 2 hay una seccion llamada "Group Movement, Tactics, and Planning". Hay varios articulos de Jeff Orkin (el tio que hizo la IA del FEAR, que usa GOAP como comentaba TrOnTxU).
- En el 3 hay una seccion llamada "Movement" y otra llamada "Tactics and Planning" que tienen otro monton de articulos interesantes (aunque la de "Movement" no trata mucho movimiento en grupo.
- Y el 4 es parecido al 3, aunque en "Movement" hay un articulo sobre el movimiento de las escuadras en el Company of Heroes de Relic. Y un articulo especifico de utilizar objetivos para un RTS.
Cita de: TrOnTxU en 21 de Abril de 2011, 05:34:37 PM
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/ (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 (http://www.asawicki.info/Download/Misc/GameProgrammingGemsTOC.html)
Que bueno lo de los campos de potencia.. es una aproximación que no conocía... muchas gracias
Cita de: Vicente en 21 de Abril de 2011, 07:35:39 PM
- Y el 4 es parecido al 3, aunque en "Movement" hay un articulo sobre el movimiento de las escuadras en el Company of Heroes de Relic. Y un articulo especifico de utilizar objetivos para un RTS.
A ese le estuve echando un vistazo hace tiempo... y es muy bueno.. no se si lo escribio el mismo desarrollador
pero esta es la web de un programador de relic, http://gdc.chrisjurney.com/, que estuvo trabajando en el Dawn of war y dio algunas charlas en la gdc.
Muy buen material. ;)
Sip, es ese, si te fijas en su web tiene el link al articulo al final :)
Bueno, aquí estoy de nuevo, la verdad es que es muy interesante toda la información que habéis dado.
He seguido trabajando en el Algoritmo, y casi que lo tengo, pero algo me falla. Cuando el camino es directo y no tiene que buscar alternativas, lo hace bien, pero cuando encuentra más de un camino, a veces me falla.
A ver si sabéis en que estoy fallando, la verdad es que no paro de intentarlo, he escrito ya varias veces comenzando desde 0, pero al aprender todo por mi cuenta, es posible que algunas cosas las haga mal.
Esta hecho en C#:
Esta es el proceso:
if(activo)
{
if(nodo[inicioX,inicioY] != nodo[finalX,finalY])
{
VecinosYCalculoF(nodo[inicioX,inicioY], nodo[finalX,finalY]);
ListaOrdenarF();
inicioX = listaAbierta[0].x;
inicioY = listaAbierta[0].y;
listaCerrada.Add(nodo[inicioX,inicioY]);
}
if(nodo[inicioX,inicioY] == nodo[finalX,finalY])
{
Debug.Log("son iguales");
}
}
Para situarnos y no poner todo el código, tengo un mapa creado con distintos cuadros, cada uno almacenado con su posición, y valores G, H, F. Lo que hago es comprobar que el nodo de inicio que le paso no es igual al nodo final, y mientras me va creando el algoritmo, creo que aquí debería ir un while, pero no me encuentra nunca el final, y hace que el programa se bloquee.
public void VecinosYCalculoF(Nodos nodoRecorrido, Nodos nodoFinal)
{
int ix = nodoRecorrido.x;
int iy = nodoRecorrido.y;
int fx = nodoFinal.x;
int fy = nodoFinal.y;
//Izquierda
if((ix - 1) >= 0)
{
if(listaAbierta.Contains(nodo[ix - 1, iy]))
{
if(nodo[ix - 1,iy].valorG < nodo[ix,iy].valorG)
{
nodo[ix - 1,iy].padre = nodo[ix,iy];
nodo[ix - 1,iy].CalcularG();
nodo[ix - 1,iy].CalcularF();
}
}
else if(nodo[ix - 1, iy].pared == false)
{
if(listaCerrada.Contains(nodo[ix - 1, iy]) == false)
{
nodo[ix - 1, iy].padre = nodo[ix,iy];
nodo[ix - 1, iy].valorH = 10*(Mathf.Abs((ix - 1) - fx) + Mathf.Abs(iy - fy));
nodo[ix - 1, iy].CalcularG();
nodo[ix - 1, iy].CalcularF();
listaAbierta.Add(nodo[ix - 1, iy]);
}
}
}
//Derecha
if((ix + 1) <= 5)
{
Debug.Log("comprueba si es menor de 5");
if(listaAbierta.Contains(nodo[ix + 1, iy]))
{
Debug.Log("Comprueba que no esta en la lista abierta");
if(nodo[ix + 1,iy].valorG < nodo[ix,iy].valorG)
{
Debug.Log("G es menor");
nodo[ix + 1,iy].padre = nodo[ix,iy];
nodo[ix + 1,iy].CalcularG();
nodo[ix + 1,iy].CalcularF();
}
}
else if(nodo[ix + 1, iy].pared == false)
{
Debug.Log("B = no es pared");
if(listaCerrada.Contains(nodo[ix + 1, iy]) == false)
{
Debug.Log("B = No esta en la lista cerrada");
nodo[ix + 1, iy].padre = nodo[ix,iy];
nodo[ix + 1, iy].valorH = 10*(Mathf.Abs((ix + 1) - fx) + Mathf.Abs(iy - fy));
nodo[ix + 1, iy].CalcularG();
nodo[ix + 1, iy].CalcularF();
listaAbierta.Add(nodo[ix + 1, iy]);
}
}
}
//Arriba
if((iy + 1) <= 5)
{
if(listaAbierta.Contains(nodo[ix,iy + 1]))
{
if(nodo[ix,iy + 1].valorG < nodo[ix,iy].valorG)
{
nodo[ix,iy + 1].padre = nodo[ix,iy];
nodo[ix,iy + 1].CalcularG();
nodo[ix,iy + 1].CalcularF();
}
}
else if(nodo[ix,iy + 1].pared == false)
{
if(listaCerrada.Contains(nodo[ix,iy + 1]) == false)
{
nodo[ix,iy + 1].padre = nodo[ix,iy];
nodo[ix,iy + 1].valorH = 10*(Mathf.Abs(ix - fx) + Mathf.Abs((iy + 1) - fy));
nodo[ix,iy + 1].CalcularG();
nodo[ix,iy + 1].CalcularF();
listaAbierta.Add(nodo[ix, iy + 1]);
}
}
}
//Abajo
if((iy - 1) >= 0)
{
if(listaAbierta.Contains(nodo[ix,iy - 1]))
{
if(nodo[ix,iy - 1].valorG < nodo[ix,iy].valorG)
{
nodo[ix,iy - 1].padre = nodo[ix,iy];
nodo[ix,iy - 1].CalcularG();
nodo[ix,iy - 1].CalcularF();
}
}
else if(nodo[ix,iy - 1].pared == false)
{
if(listaCerrada.Contains(nodo[ix,iy + 1]) == false)
{
nodo[ix,iy - 1].padre = nodo[ix,iy];
nodo[ix,iy - 1].valorH = 10*(Mathf.Abs(ix - fx) + Mathf.Abs((iy - 1) - fy));
nodo[ix,iy - 1].CalcularG();
nodo[ix,iy - 1].CalcularF();
listaAbierta.Add(nodo[ix, iy - 1]);
}
}
}
Este es el método que llamo al principio, y que me selecciona todos los vecinos(solo me calcula el los laterales, superiores e inferiores, porque necesito que sea así, ya que solo quiero movimientos rectos, no diagonales.
La primera comprobación que hace para cada vecino, es para saber que no me paso en la matriz, y no me devuelva una objeto de la matriz del mapa vacío (es decir que no hay mapa).
Después compruebo si el vecino esta en la lista abierta, si es así compruebo si su valor G es menor al nodo analizado, y si es así, le cambio el padre del vecino al nodo analizado. Si no es así entonces compruebo que no sea pared o este en la lista cerrada, y calculo F y lo meto en la lista abierta.
Después el proceso comenzaría de nuevo, ordena la lista abierta, coge el valor F más bajo y lo mete en la lista cerrada, coge a los vecinos de este ultimo, etc... hasta encontrar el ultimo nodo.
____________________
No se donde puedo fallar, estaría super agradecido si me ayudarais un poco, o que al menos me guiaseis con alguna pista de lo que pueda estar haciendo mal.
Gracias, un saludo.
Tengo un problema con esto, lo mismo estoy un poco espeso, pero no entiendo como estas inicializando todo esto. Me explico: un grafo tiene nodos y tiene aristas. En tu caso no veo nada que represente una arista por ningun sitio, pero las aristas son importantes porque son lo que indica que cuesta llegar de un nodo a otro.
Cuando te vas moviendo por las aristas, vas guardando esos costes como los "G" de cada nodo, pero no puede estar precalculado porque depende de donde comiences. El coste de F es simplemente G mas lo que te diga la heuristica. Que por cierto tampoco entiendo tu heuristica. Es decir, parece la distancia de manhattan, pero no se muy bien porque la multiplicas por 10.
Hola Vicente,
a ver si se explicarme, que seguro que es más eso a que tu estes espeso jeje.
La manera de inicializarlo, es, tengo una clase Nodos, en las que almaceno sus coordenadas en el mapa, sus valores F, etc tal como así:
public class Nodos
{
public int x;
public int y;
public int valorG;
public int valorH;
public int valorF;
public GameObject objeto;
public Nodos padre = null;
public bool pared = false;
public Nodos()
{
if(padre == null)
{
valorG = 10;
}
}
public void CrearNodo(int XX, int YY, GameObject obj)
{
x = XX;
y = YY;
objeto = obj;
}
public void CalcularF()
{
valorF = valorG + valorH;
}
public void CalcularG()
{
if(padre != null)
{
valorG = 10 + padre.valorG;
}
else
{
valorG = 10;
}
}
}
Después inicializo esta clase con un for, creando tantas filas y columnas como necesite, de esta manera:
nodo = new Nodos[numeroCeldas, numeroCeldas];
listaAbierta = new List<Nodos>();
listaCerrada = new List<Nodos>();
for (int i = 0; i < numeroCeldas; i++)
{
for (int j = 0; j < numeroCeldas; j++)
{
GameObject pl = GameObject.CreatePrimitive(PrimitiveType.Plane);
nodo[i,j] = new Nodos();
nodo[i,j].CrearNodo(i,j,pl);
nodo[i,j].objeto.transform.localScale = new Vector3(.097f,.097f,.097f);
nodo[i,j].objeto.transform.position = new Vector3(i,0,j);
nodo[i,j].objeto.renderer.material = matCelda;
nodo[i,j].objeto.name = "Nodo" + i + "_" + j;
En cuanto a la heurística, si que es manhattan, lo multiplico por 10 por que el valor me iba mejor para calcular otras cosas que tenia en mente, pero en principio eso tiene que dar igual, por que todos los nodos es el mismo valor, no??
Pongo una imagen, de como lo tengo ahora, los nodos resaltados, son los nodos que se van metiendo en la lista cerrada.
(http://img822.imageshack.us/img822/609/screencapturertn.png) (http://img822.imageshack.us/i/screencapturertn.png/)
En este caso, estoy intentando ir desde la casilla 1,1 a la casilla 5,5. Siendo 0,0 esquina inferior izquierda y 5,5 esquina superior derecha.
El G lo calculo en cada vecino, lo que hago es sumar 10 (al ser todo movimientos sin diagonal) a la G de su padre.
Yo tb ando algo espeso... mañana le echare un vistazo mas en profundidad
acabo de terminar una simplemente de los campos de potencia, y me ha sorprendido lo bien que va, y lo fácil que es, aunque solo haya metido cargas negativas para los componentes estáticos y una carga positiva para indicar donde quiero que vayan los soldados.
Y se puede optimizar un montón, porque ahora mismo calculo para cada celda del mapa, pero simplemente necesitaría calcular las celdas que hay alrededor de las unidades y tendría el mismo efecto.
Supongo que ahora mismo no me salen los problemas que tiene la técnica, y ya saldrán, pero de momento me ha abierto otra vía para ir considerando como tratar los caminos.
Muchas gracias por la aportacion, trontxu
Ponte un post o un video blau que siempre mola ver esas cosas :)
Puede que el problema sea que no calculo las diagonales??
Yo pensaba que al no tener que usarlas, no hace falta calcularlas, pero estoy equivocado??
Es que he visto que videos donde se utiliza Manhattan que el camino se forma sin utilizar diagonales, pero en cambio he visto algunos que dicen ser Manhattan tambien, que utilizan diagonales en algunos sitios, pero por ejemplo donde hay Pared/NoTransitable la hace sin diagonal, cual es el metodo Manhattan correcto? O son los dos, y están adaptados de distinta forma?
Por cierto, no es que esten espesos, estoy seguro que es problema mio y mi forma de programar, soy un poco mayor ya y esto la verdad es que cuesta, cuando toda tu vida te has dedicado al diseño, aunque intento no rendirme nunca, e intentar aprender cada día un poco más.
Gracias, saludos.
Cita de: Vicente en 25 de Abril de 2011, 12:42:22 AM
Ponte un post o un video blau que siempre mola ver esas cosas :)
Ahora esta en pañales, pero cuando lo tenga mas bonico pongo un video. ;)
Cita de: BitEver en 25 de Abril de 2011, 02:46:49 AM
Puede que el problema sea que no calculo las diagonales??
Yo pensaba que al no tener que usarlas, no hace falta calcularlas, pero estoy equivocado??
Lo de las diagonales da igual. Al final son aristas del grafo por las que pasar.
Estoy por ponerte un código mio que lo hace, pero no se si te liare mas, porque uso algunas optimizaciones y no es "ortodoxo".
Voy a echarle 5 minutos a tu codigo antes a ver si veo el problema.
Cita de: BitEver en 24 de Abril de 2011, 05:09:22 PM
He seguido trabajando en el Algoritmo, y casi que lo tengo, pero algo me falla. Cuando el camino es directo y no tiene que buscar alternativas, lo hace bien, pero cuando encuentra más de un camino, a veces me falla.
Umm... ¿en que consiste el fallo? ¿No encuentra el camino? ¿es muy largo el camino que encuentra?
por cierto el codigo para calculcar los vecinos se podria mejorar para iterar:
public void VecinosYCalculoF(Nodos nodoRecorrido, Nodos nodoFinal)
{
int fx = nodoFinal.x;
int fy = nodoFinal.y;
int[] ox = new int[] {0,0,1,-1}
int[] oy = new int[] {-1,1,0,0}
for (int k=0; k<4;k++)
{
int ix = nodoRecorrido.x + ox[k];
int iy = nodoRecorrido.y + oy[k];
// Descartes
if (ix<0 || iy<0 || ix>width.1 || iy>height-1) continue; // No es un nodo valido
if (nodo[ix,iy].pared == true) continue; // No se puede pasar
if (ListaCerrada.Contains(nodo[ix,iy]) continue; // Esta en la lista cerrada, luego ya no se vuelve a tratar, este creo que era tu problema
if(listaAbierta.Contains(nodo[ix, iy]))
{
if(nodo[ix,iy].valorG < nodoRecorrido.valorG)
{
nodo[ix,iy].padre = nodoRecorrido;
nodo[ix,iy].CalcularG();
nodo[ix,iy].CalcularF();
}
}
else {
nodo[ix, iy].padre = nodoRecorrido;
nodo[ix, iy].valorH = 10*(Mathf.Abs(ix - fx) + Mathf.Abs(iy - fy));
nodo[ix1, iy].CalcularG();
nodo[ix, iy].CalcularF();
listaAbierta.Add(nodo[ix, iy]);
}
}
Espero que te sirva de algo
Hola blau,
he seguido probando, he probado tu código, y me sigue fallando, aunque los padres escogidos son diferentes. Estoy probando por ejemplo el camino de 1,1 a 5,5, y haciendo un poco de pruebas, veo que se me meten en la listaCerrada los siguientes cuadros:
1,1 -- 1,2 -- 2,1 -- 2,2 -- 3,1 -- 4,1
Después he visto que se me queda comprobando todo el rato los cuadros 1,2 y 3,1 y de ahi no sale el bucle.
Puede que el problema este en la forma de hacer esas comprobaciones?? el código es el siguiente:
if(activo)
{
if(nodo[inicioX,inicioY] != nodo[finalX,finalY])
{
VecinosYCalculoFFF(nodo[inicioX,inicioY], nodo[finalX,finalY]);
ListaOrdenarF();
inicioX = listaAbierta[0].x;
inicioY = listaAbierta[0].y;
listaCerrada.Add(nodo[inicioX,inicioY]);
}
if(nodo[inicioX,inicioY] == nodo[finalX,finalY])
{
Debug.Log("son iguales");
}
}
O en la forma de calcular la G?? en la clase Nodos:
public void CalcularG()
{
if(padre != null)
{
valorG = 10 + padre.valorG;
}
else
{
valorG = 10;
}
}
Creo que la cosa tiene que andar por ahí no?? Ya que se me queda todo el rato comprobando dos cuadros, que supongo que no encuentra un F menor y siempre va comprobando los mismos??
Por cierto, que manera de optimizar el código, lo que yo tenia en un tocho, los ha optimizado a 4 lineas, la verdad he aprendido bastante solo mirando tu código, lo fácil que lo has hecho.
Y muchas gracias por la ayuda, no me canso de decirlo, pero es que me siento pesado al preguntar tanto y no poder conseguirlo.
Un saludo.
Si un nodo esta en la lista cerrada no se vuelve a comprobar nunca mas. Si te esta comprobando todo el rato los mismo cuadros es que no estas teniendo en cuenta ese caso :)
Cita de: blau en 25 de Abril de 2011, 09:49:25 AM
// Descartes
if (ix<0 || iy<0 || ix>width.1 || iy>height-1) continue; // No es un nodo valido
if (nodo[ix,iy].pared == true) continue; // No se puede pasar
if (ListaCerrada.Contains(nodo[ix,iy]) continue; // Esta en la lista cerrada, luego ya no se vuelve a tratar, este creo que era tu problema
Estoy con vicente :)
Jejeje, no me di cuenta que ya lo habias puesto tu blau en tu codigo :)
Bueno, he conseguido un pasito más, ahora ya llego al final de camino, pero ahora el problema lo tengo al volver hacia atrás, pasando de hijo a padre.
El problema que tenía lo solucione como decíais, me buscaba la F más baja, pero a veces esa F ya estaba en la lista cerrada, con lo que al comprobar vecinos, siempre daba los mismos, y se quedaba en bucle. Lo que he hecho, ha sido una vez cogido el valor F más bajo, comprobar que no esta en la listaCerrada, y si es así coger el segundo valor más bajo F, el tercero, etc...
No creo que sea la mejor solución, pero de esta forma llego al final del camino, comprobando todos los posibles caminos.
Ahora tengo el problema, como decía en volver hacia atrás, voy pasando de hijo a padre, pero llega un momento, que se queda en bucle en dos cuadros, pasando entre ellos de hijo a padre. Esto es supongo, por que a la hora de crear el camino, tengo que tener al conflicto a la hora de asignar o cambiar el padre de cada nodo vecino.
Este es el código para ir hacia atrás, que creo que esta bien:
if(!listaPadres.Contains(nodo[inicioX,inicioY]))
{
int aux;
int auy;
aux = inicioX;
auy = inicioY;
listaPadres.Add(nodo[aux,auy]);
inicioX = nodo[aux,auy].padre.x;
inicioY = nodo[aux,auy].padre.y;
}
Aunque el fallo, pienso que tiene que estar como digo, a la hora de asignar o comprobar el padre (si tiene un valor G más bajo):
if(listaAbierta.Contains(nodo[ix, iy]))
{
if(nodo[ix,iy].valorG <= nodoRecorrido.valorG)
{
nodo[ix,iy].padre = nodoRecorrido;
nodo[ix,iy].CalcularG();
nodo[ix,iy].CalcularF();
}
}
else {
nodo[ix, iy].padre = nodoRecorrido;
nodo[ix, iy].valorH = 10*(Mathf.Abs(ix - fx) + Mathf.Abs(iy - fy));
nodo[ix, iy].CalcularG();
nodo[ix, iy].CalcularF();
listaAbierta.Add(nodo[ix, iy]);
}
También es posible que siga calculando mal la G?? y cuando compruebo si un nodo que ya esta en la lista abierta tiene un valor G más bajo, y le cambio el padre por el nodo comprobado, y que de esta manera tambien me falle al asignar el padre, no??
Bueno, gracias a vosotros, poquito a poquito parece que lo voy consiguiendo, también es verdad que cada vez me canso más, llevo ya varios días dedicandole muchas horas a este código, y frusta no conseguir algo, y aunque no suelo rendirme, esta casi a punto de superarme, jeje.
Saludos.
Cita de: BitEver en 26 de Abril de 2011, 03:05:41 PM
if(listaAbierta.Contains(nodo[ix, iy]))
{
if(nodo[ix,iy].valorG <= nodoRecorrido.valorG)
{
Vamos a ver, sin verme el algoritmo y por lo que yo entiendo que debe hacer:
Si el nodo (V) que esta en la lista abierta, previamente calculado e introducido en ella, tiene un coste real (Gv) mayor que el coste de llegar al nodo que estamos evaluando como padre (N) + el coste de llegar de N a V, significa que a traves de N se llega con menor coste, o sea que se llega con menor coste que a traves del nodo Padre (Pv) de V que introdujo a V en la lista abierta. Luego hay que actualizar el coste de V y su padre,Pv, para que pasen a traves de N.
Quedaria algo asi:
if(nodo[ix,iy].G > nodoRecorrido.G + 10) {
nodo[[ix,iy].G = nodoRecorrido.G+10;
nodo[ix,iy].H = manahtan; // Esto no cambi, no es necesario
nodo[ix,iy].F = G + H; // Hay que reordenar la lista
nodo[ix,iy].Padre = nodoRecorrido;
}
Por otra, parte yo no llamaría a funciones tipo calcularG o calcularF desde el bucle principal, creo que para unos cálculos tan simples merece la pena ir viéndolos sobre el algoritmo y evita que te pierdas con lo que se esta haciendo en cada momento.
Por otro lado deberías poner mas enfoque en entender el algoritmo antes de liarte a programar. ;)
Conseguido!!! :D :D :D
Era eso que calculaba mal la G. Bueno, mi máximo agradecimiento, es todo un logro para mi, haber conseguido y entendido realizar esto, con toda vuestra ayuda, que no ha sido poca. Aunque lo importante es que ahora lo entiendo, a parte de saber hacerlo, y el subidon que te pega cuando realizas algo en lo que llevas tanto esforzandote, estoy muy contento en este momento.
Se que para muchos es fácil, pero para mi es todo un logro, lograr aplicar algo así cuando nunca antes he programado.
Lo dicho que muchas gracias por vuestra ayuda, seguro que sin ella no habría podido lograrlo, o entenderlo, y que siento haber sido tan pesado.
Saludos.