Inteligencia artificial para videojuegos/Control de unidades en juego RTS
Enunciado
editarDebemos 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 especiales
editar- 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 consejos
editarPara no congelar Unity, se pueden utilizar corrutinas o ejecutar la IA en otro hilo.
Referencias
editar- Proyecto y juego web basado en A*: http://buildnewgames.com/astar/
Implementacion del A* pathfinding
editar- 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 Activos
editar- Andrés Puente Rodriguez
- María García Raldúa