Inteligencia artificial para videojuegos/Control de unidades en juego RTS

EnunciadoEditar

Debemos programar un prototipo de IA que planifique la ruta de tres unidades que el jugador puede mover libremente en un tablero de 10x10 de un juego RTS. Los contenidos del tablero pueden ser de diferentes tipos:

  • Casilla normal de tierra.
  • Casilla embarrada
  • Casilla bloqueada por rocas
  • Unidades (roja, verde y azul): no pueden compartir casilla y se bloquean. Además, solo puede haber 1 unidad seleccionada
  • Flechas (roja, verde y azul): pueden compartir casilla y no bloquean y marcan la casilla objetivo de la unidad del color correspondiente.
EFECTOS Casilla normal Casilla embarrada Casilla bloqueada Casilla con unidad X
Sin unidad seleccionada Casilla pasa a embarrada Casilla pasa a bloqueada Casilla pasa a normal Unidad X seleccionada
Con unidad seleccionada A la casilla se añade flecha Y A la casilla se añade flecha Y No hay unidad seleccionada (No afecta)

Cada movimiento cuesta 1 unidad, aunque si pasamos sobre una casilla embarrada éste aumenta a 2. Cuando una unidad tiene un objetivo asignado, esta planifica su ruta y comienza a avanzar hacia él. Además, deja de estar seleccionada cuando se le asigna un objetivo y cuando lo alcanza para y deja de tener ese objetivo asignado.


Restricciones especialesEditar

  • Hay que crear un único resolutor que recibe problemas (rutas a planificar) y devuelve soluciones (secuencia de pasos).
  • Separar claramente el pintado de frames de la interacción que ofrece Unity, del cómputo de la IA que ha de programarse.

Pistas y consejosEditar

Para no congelar Unity, se pueden utilizar corrutinas o ejecutar la IA en otro hilo.

ReferenciasEditar

Implementacion del A* pathfindingEditar

  • Implementacion de la busqueda

Para realizar la busqueda a una casilla objetivo (Ob) desde una casilla inicial (ini) se puede seguir el metodo del Algoritmo A*, este algoritmo nos permitira a traves de una serie de parametros, comprobar la distancia de las casillas vecinas a la nuestra, hasta la casilla Ob y elegir aquella que esta mas cerca del Ob para seguir expandiendose a partir de ahi. Este algoritmo tambien tiene en cuenta el coste de moverse entre los diferentes tipos de casillas y diferenciar entre suelo pisable y muros.

Las casillas se estructuraran por "nodos" cuyas caracteristicas seran:

   * g_Cost -> A que distancia se encuentra el nodo del nodo inicial.
   * h_Cost -> A que distancia se encuentra el nodo del nodo final.
   * f_Cost -> g_Cost + h_Cost.
   * parent -> referencia al nodo del que viene (el anterior para luego poder dar el camino final)
   * Se pueden implementar mas caracteristicas al calcular el coste de los nodos como el coste de atravesar esa casilla sumandolo simplemente al f_Cost.

El algoritmo de A* ira buscando en los nodos vecinos al nodo actual y seleccionara el que tiene el menor f_Cost como el nuevo actual, de esta manera ira progresando a traves del tablero hasta llegar a la casilla objetivo por el camino mas rapido que haya encontrado. Una vez encontrado el nodo objetivo se realizara un RetracePath, desde el objetivo hasta la casilla de inicio, a traves de los parents de los nodos, que devolvera la lista de casillas representando el camino mas rapido.

La estructura en pseudocodigo del algoritmo A* seria:

//--------------

 //conjunto de nodos (casillas) a ser evaluadas
 OPEN 
 //conjunto de nodos ya evaluados (conocemos su f_Cost)
 CLOSED 
  loop
     current = nodo en OPEN con el f_Cost mas bajo
     eliminar current de OPEN
     añadir current a CLOSED
     if(current = casilla objetivo) //se encontro el camino
        RetracePath()**
        return
     foreach(neighbour del nodo actual) //Miramos las casillas vecinas a la que nos encontramos
        if (neighbour es muro o esta en CLOSED)
           saltamos al siguiente neighbour
        if (el camino nuevo al neighbour es mas corto que el camino anterior (el coste de f_Cost es menor) o el neighbour no esta en OPEN)
           set f_Cost de neighbour
           set parent de neighbour al nodo actual
              if(neighbour no esta en OPEN)
                 añadimos neighbour a OPEN
              else
                 actualizamos el valor del nodo neighbour

//---------------

El metodo RetracePath:

    void RetracePath (Nodo startCasilla, Nodo endCasilla) {
         List<Casilla> path = new List<Casilla>();
         currentCasilla = endCasilla;
         while (currrentCasilla != startCasilla){
              path.Add(currentCasilla);
              currentCasilla = currentCasilla.parent;
         }
         path.Reverse();
         //path es el camino a seguir, guardarlo donde se necesite.
    }

Participantes ActivosEditar

  • Andrés Puente Rodriguez
  • María García Raldúa