Algoritmo de búsqueda A* (PathFinding A*) – XNA


Teoría

El algoritmo A* es usado para encontrar la ruta más cercana para ir de un lugar a otro (llamados nodos), es el más usado debido a que es sencillo y rápido.

La representación es la siguiente:

f(n) = g(n) + h(n)

g(n) es la distancia total que se toma de ir de la posición inicial a la posición actual

h(n)  es la distancia estimada desde la posición inicial a la posición de destino de final, en este caso se usa una función heurística para calcular el valor estimado

f(n) es la suma de g(n) y h(n), y es el valor calculado más corto.

En palabras humanas lo que se necesita es:

–          Un nodo o punto inicial

–          Un nodo final que representa el final del algoritmo

–          Un método para identificar que nodos son traspasables y cuales son sólidos

–          Un método para determinar el costo directo (g) de moverse entre los nodos

–          Un método para determinar el costo indirecto (h)

–          Una lista de nodos abiertos, en esta lista se guardaran todos los nodos que se han identificado como posibles movimientos, pero aún no han sido evaluados

–          Una lista de nodos cerrados, donde se guardaran todos los nodos evaluados y descartados, aunque no es necesario una lista, basta con un estado que indique que el nodo se encuentra cerrado

–          Una forma de identificar que nodo procede a otro, para poder retornar la cadena de los nodos

Vamos a continuar con los tutoriales del mapa de tiles, para poder satisfacer la forma de identificar los nodos sólidos y los que son traspasables y cada nodo será representado por un tile.

Si vamos a permitir que los actores del juego puedan moverse diagonalmente, debemos darle un costo directo más bajo al movimiento en diagonal que al movimiento en línea recta de dos nodos, por ejemplo:

En la imagen anterior, la línea amarilla representa el movimiento de ir del nodo azul claro al nodo azul oscuro, pero sin hacer ningún movimiento diagonal, si el costo de moverse de un nodo a otro es de 10, el resultado de la línea amarilla es de 20, en cambio el movimiento de la línea roja, que es diagonal debe ser de 15 o 14, que sería el resultado del teorema de Pitágoras.

Ahora, para el valor indirecto se usa la heurística que es un cálculo aproximado de ir de un nodo actual al nodo final o destino, en la mayoría de casos usan como heurística la distancia de Manhattan o la distancia Euclidiana , en nuestro caso vamos a implementar varias para ver la diferencia de ellas.

Cómo funciona?

El algoritmo es el siguiente:

  1. Si el nodo inicial es igual al nodo final, se retorna el nodo inicial como solución
  2. Si no, se adiciona el nodo inicial a la lista abierta
  3. Mientras la lista abierta no esté vacía, se recorre cada nodo que haya en la lista abierta y se toma el que tenga el costo total más bajo
  4. Si el nodo obtenido es igual al nodo final, se retornan todos los nodos sucesores al nodo encontrado
  5. Si no , se toma el nodo y se elimina de la lista abierta para guardarse en la lista cerrada y se buscan todos los nodos adyacentes al nodo obtenido y se adicionan a la lista abierta a menos que el nodo se encuentre en la lista cerrada o que el nodo sea sólido
  6. Si el nodo adyacente ya se encuentra en la lista abierta se verifica que el costo sea menor, si es menor se cambian los valores de costo, sino se ignora
  7. Se vuelve al paso 3 y se repite hasta que el punto 4 sea verdadero o que la lista abierta quede vacía

Siempre he dicho que una imagen vale más que mil palabras por eso vamos a tomar como ejemplo la siguiente imagen


El nodo inicial es el nodo (2,4) o el que esta de color azul, el nodo final es el nodo (3,2) o nodo rojo, los nodos de color verde son nodos sólidos y no pueden ser traspasados.

Al empezar el algoritmo tendremos el nodo azul como opción y lo agregamos a la lista abierta, luego como no es el nodo final, obtenemos sus nodos adyacentes y luego lo dejaremos en la lista cerrada, calculamos los valores de los nodos de la lista abierta (a menos que ya los hayamos calculado) y tomamos el de menor valor:

La heurística que se ha usado es la distancia de Manhattan:

H = Math.Abs(nodoActual.X – nodoFinal.X) + Math.Abs(nodoActual.Y – nodoFinal.Y)

Como ejemplo tomamos el cuadrado B (1,4) hasta el nodo final (3,2)

H = (1 – 3) + (4 – 2)

H =  2 + 2

H = 4

Lo que hicimos fue contar los cuadrados que hay para llegar del nodo actual al nodo final.

Ahora, el nodo que tiene el menor valor es C, por lo tanto buscamos sus nodos adyacentes, dando como resultado el nodo E y F porque los demás son sólidos y el nodo (4,5) aunque es alcanzable diagonalmente, es inalcanzable porque uno de los nodos cerca es sólido.

Se añade el nodo C a la lista cerrada y los demás nodos a la lista abierta, pero como ya se encuentran, se verifica que el valor calculado no sea menor, los costos nuevos son de los nodos son:

Como el costo no es menor que el que tienen en la lista abierta, se descartan y se vuelve a tomar el menor valor de la lista abierta, lo que da un empate entre B y E, pero si tomamos el nodo E, volveríamos a descartar los demás nodos, volviendo a tomar el valor B porque el E es enviado a la lista cerrada.

Si se sigue con el algoritmo va a dar lo siguiente:

El algoritmo en el código:

Ahora que se ha “explicado” de qué se trata el algoritmo, vamos a crear las clases y métodos necesarios para implementar el algoritmo.

Agregamos una clase al proyecto SceneManager ( Estoy continuando con el proyecto de Motor de Tiles), la clase es llamada nodo y contiene la información del nodo:

public class Nodo
{
#region declaraciones
public Nodo NodoPadre;
public Nodo NodoFinal;
private Vector2 posicion;
public float costoTotal;
public float costoG;
public bool Cerrado = false;
#endregion

#region propiedades
public Vector2 Posicion
{
 get
 {
  return posicion;
 }
 set
 {
  posicion = new Vector2((float)MathHelper.Clamp(value.X, 0f, (float)Camara2D.anchoTile * Camara2D.numXTiles),
  (float)MathHelper.Clamp(value.Y, 0f, (float)Camara2D.anchoTile * Camara2D.numYTiles));
 }
}

public Int32 GrillaX
{
 get { return (Int32)posicion.X; }
}

public Int32 GrillaY
{
 get { return (Int32)posicion.Y; }
}
#endregion

public Nodo(Nodo nodoPadre, Nodo nodoFinal, Vector2 posicion, float costo)
{
 NodoPadre = nodoPadre;
 NodoFinal = nodoFinal;
 Posicion = posicion;
 costoG = costo;
 if (nodoFinal != null)
 {
  costoTotal = costoG + Calcularcosto();
 }
}

public float Calcularcosto()
{
 return Math.Abs(GrillaX - NodoFinal.GrillaX) + Math.Abs(GrillaY - NodoFinal.GrillaY);
}

public Boolean esIgual(Nodo nodo)
{
 return (Posicion == nodo.Posicion);
}
}

La variable NodoPadre sirve para saber que nodo lo precede, y así poder después formar una cadena con el camino más corto, la variable NodoFinal indica el nodo destino al cual hay que llegar, esta variable sirve para calcular el costo indirecto o la heurística.

La variable Posicion representa las coordenadas del nodo en el mapa, las propiedades GrillaX y GrillaY permiten acceder más rápido a las coordenadas.

Cada vez que se crea un nuevo nodo, se calcula su costo total, con el costo directo (g) y su costo indirecto (h), la condición de que el nodo final sea diferente a nulo, es para cuando se crea el nodo final, el método esIgual es útil para comparar dos nodos, verificando sus posiciones.

Ahora, agregamos otra clase que servirá para encontrar la ruta, la llamaremos gestorBusqueda:

public class gestorBusqueda
{
 private const Int32 costoIrDerecho = 10;
 private const Int32 costoIrDiagonal = 15;
 private List<Nodo> listaAbierta = new List<Nodo>();
 private List<Vector2> listaCerrada = new List<Vector2>();
 public TileEngine motor;

 public gestorBusqueda(TileEngine motor)
 {
  this.motor = motor;
 }

/// <summary>
/// Adiciona un Nodo a la lista abierta, ordenadamente
/// </summary>
/// <param name="nodo"></param>
private void adicionarNodoAListaAbierta(Nodo nodo)
{
 Int32 indice = 0;
 float costo = nodo.costoTotal;
 while ((listaAbierta.Count() > indice) &&
 (costo < listaAbierta[indice].costoTotal))
 {
  indice++;
 }
 listaAbierta.Insert(indice, nodo);
}

public List<Vector2> encontrarCamino(Vector2 posTileInicial, Vector2 posTileFinal)
{
 if (motor == null)
 {
  return null;
 }
 Tile tileInicial = motor.Mapa.tileMapLayers[0].obtenerTile((int)posTileInicial.X, (int)posTileInicial.Y);
 Tile tileFinal = motor.Mapa.tileMapLayers[0].obtenerTile((int)posTileFinal.X, (int)posTileFinal.Y);

 if (tileInicial.Colision || tileFinal.Colision)
 {
  return null;
 }

 listaAbierta.Clear();
 listaCerrada.Clear();

 Nodo nodoInicial;
 Nodo nodoFinal;

 nodoFinal = new Nodo(null, null, posTileFinal, 0);
 nodoInicial = new Nodo(null, nodoFinal, posTileInicial, 0);

 // se adiciona el nodo inicial
 adicionarNodoAListaAbierta(nodoInicial);
 while (listaAbierta.Count > 0)
 {
  Nodo nodoActual = listaAbierta[listaAbierta.Count - 1];
  // si es el nodo Final
  if (nodoActual.esIgual(nodoFinal))
  {
   List<Vector2> mejorCamino = new List<Vector2>();
   while (nodoActual != null)
   {
    mejorCamino.Insert(0, nodoActual.Posicion);
    nodoActual = nodoActual.NodoPadre;
   }
  return mejorCamino;
 }
 listaAbierta.Remove(nodoActual);

 foreach (Nodo posibleNodo in encontrarNodosAdyacentes(nodoActual, nodoFinal))
 {
  // si el nodo no se encuentra en la lista cerrada
  if (!listaCerrada.Contains(posibleNodo.Posicion))
  {
   // si ya se encuentra en la lista abierta
   if (listaAbierta.Contains(posibleNodo))
   {
    if (posibleNodo.costoG >= posibleNodo.costoTotal)
    {
     continue;
    }
   }
   adicionarNodoAListaAbierta(posibleNodo);
  }
 }
 // se cierra el nodo actual
 listaCerrada.Add(nodoActual.Posicion);
 }
return null;
}

private List<Nodo> encontrarNodosAdyacentes(Nodo nodoActual, Nodo nodoFinal)
{
List<Nodo> nodosAdyacentes = new List<Nodo>();
Int32 X = nodoActual.GrillaX;
Int32 Y = nodoActual.GrillaY;
Boolean arribaIzquierda = true;
Boolean arribaDerecha = true;
Boolean abajoIzquierda = true;
Boolean abajoDerecha = true;

//Izquierda
if ((X > 0) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X - 1, Y).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal, new Vector2(X - 1, Y), costoIrDerecho + nodoActual.costoG));
}
else
{
 arribaIzquierda = false;
 abajoIzquierda = false;
}

//Derecha
if ((X < motor.Mapa.NumXTiles - 1) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X + 1, Y).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X + 1, Y), costoIrDerecho + nodoActual.costoG));
}
else
{
 arribaDerecha = false;
 abajoDerecha = false;
}

//Arriba
if ((Y > 0) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X, Y - 1).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X, Y - 1), costoIrDerecho + nodoActual.costoG));
}
else
{
 arribaIzquierda = false;
 arribaDerecha = false;
}

// Abajo
if ((Y < motor.Mapa.NumYTiles - 1) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X, Y + 1).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X, Y + 1), costoIrDerecho + nodoActual.costoG));
}
else
{
 abajoIzquierda = false;
 abajoDerecha = false;
}

// Dirección Diagonal
if ((arribaIzquierda) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X - 1, Y - 1).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X - 1, Y - 1), costoIrDiagonal + nodoActual.costoG));
}

if ((arribaDerecha) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X + 1, Y - 1).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X + 1, Y - 1), costoIrDiagonal + nodoActual.costoG));
}

if ((abajoIzquierda) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X - 1, Y + 1).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X - 1, Y + 1), costoIrDiagonal + nodoActual.costoG));
}

if ((abajoDerecha) && (!motor.Mapa.tileMapLayers[0].obtenerTile(X + 1, Y + 1).Colision))
{
 nodosAdyacentes.Add(new Nodo(nodoActual, nodoFinal,
 new Vector2(X + 1, Y + 1), costoIrDiagonal + nodoActual.costoG));
}

 return nodosAdyacentes;
 }
}

Primero declaramos dos constantes, que indicarán el valor directo de moverse linealmente y moverse diagonalmente, también se tiene la lista abierta, la lista cerrada que guarda la posición y no el nodo, debido a que con la lista no podemos usar el método Contains con la clase Nodo, también se tiene una referencia a la clase TileEngine para poder identificar los nodos traspasables y los que no.

En el constructor de la clase enviamos la referencia a la clase TileEngine.

Tenemos un método que adiciona un nodo a la lista abierta, pero ordenadamente (adicionarNodoAListaAbierta).

El método encontrarCamino recibe como parámetro dos vectores, uno con la posición inicial y otro con la posición final y devuelve una lista de las posiciones o el camino más corto, apenas empieza se verifica que la referencia al motor no esté nula, si lo es se retorna nulo.

Los vectores recibidos en el método, se convierte en Tiles y luego se verifican que ninguno de los dos sea sólido, si lo son se retorna nulo.

Si no son sólidos, entonces se crean los Nodos inicial y final,  luego se implementa el algoritmo, el método encontrarNodosAdyacentes busca todos los nodos cercanos al nodo actual y se verifican los posibles movimientos, también que el nodo no se sobrepase de los límites del mapa.

Ahora para verificar el algoritmo, haremos unos pequeños cambios al código

–          Adicionamos una propiedad a la clase Tile que indicará el color del tinte:

public Color Color { get; set; }
public Tile(Int32 tipo)
{
 Tipo = tipo;
 Colision = false;
 Color = Color.White;
}

En la clase game1 del proyecto ColisionMapa, declaramos una variable para el gestor de búsqueda:

gestorBusqueda GestorBusqueda;

En el método LoadContent, justo después de inicializar la variable mapa, inicializamos la variable:

GestorBusqueda = new gestorBusqueda(mapa);

En el método Initialize mostramos el Mouse:

IsMouseVisible = true;

Y en el método Draw, después del Spritebatch.Begin() creamos un código temporal que tomará el Tile donde se haga clic como posición inicial del algoritmo y la posición del tanque como posición final, si el método encontrarCamino devuelve la lista con los nodos del camino, pintaremos cada Tile para indicar el camino:


// Código Temporal
MouseState ms = Mouse.GetState();
if ((ms.X > 0) && (ms.Y > 0) &&
 (ms.X < Camara2D.TamanoPantalla.X) && (ms.Y < Camara2D.TamanoPantalla.Y))
 {
  Vector2 mouseLoc = Camara2D.ScreenToWorld(new Vector2(ms.X, ms.Y));
  if (ms.LeftButton == ButtonState.Pressed)
  {
   mouseLoc = mapa.Mapa.GetSquareAtPixel(mouseLoc);
   posTile = mapa.Mapa.GetSquareAtPixel(new Vector2(tanque.Posicion.X + (distancia.X * (tanque.AnchoFrame / 2)),        tanque.Posicion.Y + (distancia.Y * tanque.AltoFrame / 2)) + distancia);

   List<Vector2> camino = GestorBusqueda.encontrarCamino(mouseLoc, posTile);
   if (camino != null)
   {
    foreach (Vector2 nodo in camino)
    {
     Tile tile = mapa.Mapa.tileMapLayers[0].obtenerTile((int)nodo.X, (int)nodo.Y);
     tile.Color = new Color(128, 0, 0, 80);
    }
   }
 }
}
// fin codigo temporal

Y para finalizar, en la clase TileMap antes de dibujarlo:

if (debug)
{
 if (tile.Colision)
 {
  tile.Color = Color.Red;
 }
 else
 {
  tile.Color = Color.White;
 }
}
else
{
 if (tile.Color == Color.Transparent)
 {
  tile.Color = Color.White;
 }
}

spriteBatch.Draw(layer.sheet.Textura, Vector2.Zero, sourceRect, tile.Color,
0, position, scale, SpriteEffects.None, 0.0f);

Y al ejecutar el proyecto podemos ver lo siguiente:

He modificado el código, para mostrar el tiempo que transcurre desde que se llama el método de encontrar el camino hasta que retorna un resultado, además del total de nodos abiertos y cerrados, y la opción de cambiar la heurística:

Código Fuente:

Aquí para Descargar

Referencias:

http://www.edenwaith.com/products/pige/tutorials/a-star.php

http://en.wikipedia.org/wiki/A*_search_algorithm

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

Libro XNA 4.0 Game Development by Example  por Kurts Jaegers

Anuncios

19 pensamientos en “Algoritmo de búsqueda A* (PathFinding A*) – XNA

  1. Muy bueno… me viene de 10, soy nuevo en la programacion y empece con XNA hace unos meses, todo me fue biien en la programacion de mi juego hasta llegar a la IA -.-” Esto me Hiso entender como funciona el pathfinding que realmente no lo entendia

  2. Hola, antes de nada darte las gracias por este aporte que nos ayuda tanto a algunos =).

    Tras estar viendo, intentando y entendiendo tu codigo hay una parte que no consigo comprender, en el metodo “encontrarCamino”, el if que comprueba si el siguiente nodo tiene un coste mayor de G, que de coste total, en otras palabras, el if que se encarga de ver si un camino es mas optimo que otro, no lo termino de ver. Es esta parte:

    if (posibleNodo.costoG >= posibleNodo.costoTotal)
    {
    continue;
    }

    Para ver el coste de G, no habria que coger el nodo de la lista?, ya que si cogemos el nodo adyacente que genera el for ( “posibleNodo.costoG”), ese nodo podria tener una G distinta segun se haya generado a partir de los adyacentes de un nodo, o cogiendo el de la lista de abiertos inicial que ya se genero y que vendria de la lista con los adyacentes al nodo anterior. Me explico fatal 😄 pero asi es como lo entiendo, si podrias aclararme mi duda te lo agradeceria.

    • Hola, creo que sí tengo un error, ya que el algoritmo dice que si el nodo ya se encuentra en la lista abierta, se verifica el costo G, un costo G menor significa que es un mejor camino,
      Lo correcto sería:
      if (posibleNodo.costoG >= nodoActual.costoG)
      {
      continue;
      }
      Así, si el costoG del nodo que ya esta en la lista abierta es mayor o igual al nodo actual, se ignora el posibleNodo, pero si es menor se recalculan los costos o se ordena la lista.

  3. Pingback: Dividir pantalla (Split Screen) – XNA 2D « Escarbando Código

  4. Excepción no controlada del tipo ‘System.IO.DirectoryNotFoundException’ en mscorlib.dll

    Información adicional: No se puede encontrar una parte de la ruta de acceso ‘C:\Mapa\ColisionMapa20.xml’.

    no se cual sea el error o como corregir?

  5. Hola y felicitaciones por el tutorial, tengo una pregunta, a mi tambien me da problemas con lo del colisionmapa20.xml, pero en este caso si yo cambio el mapa por ejemplo por un mapa de una ciudada, este mapa afecta al codigo de la colision??? si tendria que cambiar la colision en donde se haria??

  6. Hola que tal excelente programa..lo que pasa es que recien estoy entrando en lo que es la programacion con xna y la verdad que lo instale todo y al momento que abro el programa me salen ciertos errores..:::

    C:\Users\Miguel\Desktop\JUego_IA\TileEditor\TileEditor\TileEditor.csproj : error : No se puede leer el archivo de proyecto ‘TileEditor.csproj’.
    C:\Users\Miguel\Desktop\JUego_IA\TileEditor\TileEditor\TileEditor.csproj: No se pudo cargar el archivo del proyecto. No se puede encontrar una parte de la ruta de acceso ‘C:\Users\Miguel\Desktop\JUego_IA\TileEditor\TileEditor\TileEditor.csproj’.

    C:\Users\Miguel\Desktop\JUego_IA\TileEditor\TileEditorContent\TileEditorContent.contentproj : error : No se puede leer el archivo de proyecto ‘TileEditorContent.contentproj’.
    C:\Users\Miguel\Desktop\JUego_IA\TileEditor\TileEditorContent\TileEditorContent.contentproj: No se pudo cargar el archivo del proyecto. No se puede encontrar una parte de la ruta de acceso ‘C:\Users\Miguel\Desktop\JUego_IA\TileEditor\TileEditorContent\TileEditorContent.contentproj’.

    • Hola, el costo es dado por uno, yo podría decir que el costo de moverse de un cuadro a otro cuadro es de 5, 6, 40, 25 o lo que quiera, pero para moverse diagonalmente hay que tener en cuenta el teorema de pitágoras, en el ejemplo como el costo de moverse de un cuadro a otro cuadro es de 10, el de moverse diagonalmente es 14, aplicando el teorema de pitágoras, pero se aproxima a 15.

  7. Hola, recien estoy entrando en este tipo de programacion, siempre he estado desarrollando ejercicios sencillos o del tipo comercial, pero ahora entoy incursionando en este tipo de programas como lo son la heuristica y/o programas de busqueda. He tratado de bajarme el codigo para revisarlo y comprender la forma de programacion, pero me ha sido imposible debido que pide que se registre uno. Mi prgunta, hay alguien que puedo subir el proyecto completo a algun lugar donde sea realmente libre el descargarlo, sin tener que validarse en una cuenta, o registrarse. Un lugar libre de verdad?. Gracias de antemano por su ayuda, o al creador de este blog si me puede ayudar. De antemano, infinitas gracias.

  8. hola, muchas gracias por el ejemplo, me ayudo en algunos puntos, pero me acabo d descargar tu codigo y e instalado XNA Game Studio 4.0.4 para visual studio 2012, pero no se puede abrir el archivo del proyecto TileEditor y TileEditorContent, necesito instalar un programa adicional?

    • Hola, lo que sucede es que el proyecto lo realicé con visual studio 2010 y posiblemente por las versiones no te deja abrir bien el proyecto, tendrías que crear uno nuevo, y comenzar a adicionar las clases y las referencias manualmente

Deseas comentar o sugerir algo?

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s