Un poco perdido en A*

[Vicente]

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.

[blau]

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

Que bueno  lo  de los campos de potencia.. es una aproximación que no conocía... muchas gracias

[blau]

- 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. ;)

[Vicente]

Sip, es ese, si te fijas en su web tiene el link al articulo al final :)

[BitEver]

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:

Código [Seleccionar] Expand


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.

Código [Seleccionar] Expand



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.

[Vicente]

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.

[BitEver]

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í:

Código [Seleccionar] Expand



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:

Código [Seleccionar] Expand



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.




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.

[blau]

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

[Vicente]

Ponte un post o un video blau que siempre mola ver esas cosas :)

[BitEver]

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.

[blau]

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. ;)

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.

[blau]

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

[BitEver]

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:

Código [Seleccionar] Expand



               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:

Código [Seleccionar] Expand



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.

[Vicente]

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 :)

[blau]

                  // 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 :)