Inteligencia Cooperativa

[Daemon]

 Hola,

Aprovechando que tenemos este foro voy a plantear una discusion para ver si la gente se anima y le damos un poco de vida.

Se que puede haber algunos miembros del foro que pueden estar interesados en una discusion de este tipo, pues o se han tenido que enfrentar con el problema o lo van a tener que afrontar proximamente en algun proyecto: se trata de como plantear la IA de un conjunto grande de unidades en un RTS, tanto desde el punto de vista de estrategias, como de tecnicas a usar para implementarlas.

A ver que tal nos va ;).

Un saludo.

[fiero]

 ¿Inteligencia cooperativa? Nunca he visto ningún RTS en el que los personajes "cooperen" e interactuen entre ellos para cumplir objetivos.

No estoy muy al dia en este tipo de juegos (el ultimo al que jugué fué Age of Empires II), pero no he visto nada demasiado "inteligente" en los RTS que he jugado.

Lo que he podido comprobar, es que cada personaje es una "máquina de estados", según el estado en el que se encuentre se comporta de una manera u otra, y el personaje cambia de estado según ciertos parámetros, que le hacen parecer más o menos "inteligente".

Por ejemplo, en Starcraft, un minero tiene el estado "ir a por mineral", y lo único que hará el personaje es sortear los obstáculos que encuentre en su camino hasta la mina. Sólo cambiará de estado si el mineral se agota, en ese caso pasará al estado de "parado" o si consigue el mineral, en ese caso su estado cambia a "volver a casa". Por ejemplo, si está "parado" solo cambiara a "huir del ataque" cuando sea atacado, y se moverá en la dirección contraria de donde le viene el ataque.

Lo único que hace el programa en cada bucle es comprobar los estados de cada personaje y ver si debe cambiar de estado según los estímulos que recibe cada uno.

Se podrían hacer cosas mucho más complicadas e inteligentes, por ejemplo, que los personajes cooperen entre ellos, etc. En ese caso, se vería a los mineros formando una cadena desde el cuartel general hasta la mina y se pasarían el mineral de uno a otro para ahorrar tiempo  :D

un saludo

[Vicente]

 Yo en los RTS el problema que veo es: ¿como haces todas las comprobaciones de las unidades? Me explico: cuando una unidad enemiga entra en el rango de accion de las nuestras, la empiezan a disparar (o se mueven hacia ella o algo así). Chequeas continuamente todas las unidades? O tienes una entidad como "montón de unidades" y si ese "montón" ve algo ya miras que unidades del grupo en particular son las que empiezan a disparar?  Algo parecido me pasa con el pathfinding para tantisimas cosas...

Un saludo!

Vicente

[dracks]

 Hola,

Para lo que comentas de cuando una unidad entra en el punto de mira de otra unidad enemiga, yo tengo hecho un bucle, a lo mejor es un poco malo en temas eficiencia, pero si funcionara bien, que no se que le passa que ultimamente cada dia me funciona peor, hace su trabajo...

Lo del trabajo coperativo, seria mas bien por passo de mensajes, la unidad cuando es atacada, tendria de informar a las unidades cercanas que es atacada, para que todas ellas atacassen a la vez, si no tienen otro objetivo...

Complicado? no... solo es otro bucle :P

En la practica de ISO (introduccion a los sistemas operativos) la ultima que haremos, necessitamos de este tipo de inteligencia, estamos haciendo un comecocos para shell de linux, con multiples processos, y los fantasmas cuando vean al  comecocos, han de informar a los otros que han visto al comecocos...

Ya os informare, cuando la tenga terminada....

Suerte!
P.D.: si quereis mi juego, enviadme un e-mail, y os hare llegar una version, esta hecho en Fenix, y no se porque se cuelga a los 5 o 6 minutos de juego...  

[fiero]

Chequeas continuamente todas las unidades? O tienes una entidad como "montón de unidades" y si ese "montón" ve algo ya miras que unidades del grupo en particular son las que empiezan a disparar?  Algo parecido me pasa con el pathfinding para tantisimas cosas...

Se pueden chequear contínuamente todas las unidades en cada bucle. No hay ningún problema con eso, a nivel de eficiencia. Sólo hay que tener un par de rutinas rápidas de cálculo de distancias, búsqueda de caminos, etc. En los RTS los cálculos se hacen en 2D, y por ejemplo no hace falta hacer raices cuadradas, se pueden utilizar todas las distancias al cuadrado para ahorrar. Además, después se pueden emplear todos los trucos que se te ocurran para optimizar, como quadtrees, etc. Por ejemplo, para el cálculo de visibilidad de un enemigo, un personaje sólo comprobaría los que están en su mismo cuadrante y los que están más lejos ni siguiera se comprueban, etc.

Por eso los RTS presumen de todos los personajes que pueden manejar a la vez, porque la cosa se complica cuando hay que comprobar muchos personajes en cada bucle. Se trata de comprobar lo extrictamente necesario en cada bucle, lo mismo que con las rutinas de visivilidad de las funciones de render, dibujar lo extrictamente necesario.

un saludo

[AgeR]

 Un tema interesante, y válido también para otros tipos de juego.
Para mí, lo primero que debería hacer un grupo de unidades es organizarse de la forma más eficiente. Un ejemplo típico, infantería delante, arqueros detrás, caballería a los flancos. Y si se adaptaran ellos solos ya sería perfecto. Suponiendo que el grupo sea atacado por varios puntos, lo lógico sería que la infantería rodeara a los arqueros, que estarían protegidos en el centro del grupo, mientras la caballería hace cargas contra los enemigos, centrándose en sus arqueros, por ejemplo.
Esto que puede parecer complejo, no sé hasta qué punto lo sería, supongo que podría funcionar por estados.

Luego para rizar el rizo, se podría hacer que varios grupos distintos se coordinaran entre ellos para lanzar un ataque o proteger una zona. Imaginad que te viene la IA a atacarte con infantería y arqueros. Sales a defenderte y los arqueros te empiezan a disparar a distancia, cuando te acercas la infantería avanza y sale a tu encuentro. En medio de la lucha aparece la caballería enemiga y divide tu grupo en dos, mientras un nuevo grupo hace su aparición y te destroza  :ph34r: .

(uoh)  

[fiero]

 

Luego para rizar el rizo, se podría hacer que varios grupos distintos se coordinaran entre ellos para lanzar un ataque o proteger una zona. Imaginad que te viene la IA a atacarte con infantería y arqueros. Sales a defenderte y los arqueros te empiezan a disparar a distancia, cuando te acercas la infantería avanza y sale a tu encuentro. En medio de la lucha aparece la caballería enemiga y divide tu grupo en dos, mientras un nuevo grupo hace su aparición y te destroza  :ph34r: .

Esto se podría hacer con un nivel superior de IA. Más acorde con la librería que ha hecho vicente para Haddd (creo recordar). Es decir, en un nivel básico de IA, todos los personajes serían máquinas de estados mas o menos simples o complicadas. Y en otro nivel superior, se encontraría el "cerebro" del enemigo, es decir, una inteligencia un poco más avanzada que daría las directrices principales a todas la unidades bajo su mando. Esta IA seria más como un jugador virtual, y podría plantear estrategias como describe Ager, o incluso aprender de sus errores  :)

[seryu]

 que sepa, el starcraft (juego la mar de simple) la maquina atacaba con tropas y escuadron, y seguia un ritmo de construccion, por lo que no debe tener solamente una maquina de estados individual por mob.

[senior wapo]

 Si no recuerdo mal, en Starcraft la IA eran scripts.

Un script (ficticio) era algo asi:
"
Estrategia Ofensiva:
Construye soldados (15), medicos (4) y motos (3). Cuando tengas 15 soldados, 4 medicos y 3 motos mandalos al punto de encuentro P1 (en la entrada de tu propia base). Cuando todos esten alli, mandalos a la base enemiga y ataca contra el jugador si este no tiene aun factoria. Si la tiene, no mandes nada y ponte a construir un puerto espacial. Cuando tengas pueto espacial construye 2 transportes, mete las tropas y ataca el comand center.

Estrategia económica:
- Si hay suministros suficientes (y material) construye soldado, minero, tanque, y repetir.
- Construye barraca cuando tengas dinero, al menos 8 mineros, y ninguna barraca.
- Construye factorias siempre que tengas barraca, 8 mineros, 10 soldados y no tengas puerto espacial.
- Construye puerto espacial siempre que tengas factoria, 5 soldados, 3 tanques y el enemigo tenga mas tropas de tierra que de aire
- Si han pasado 5 minutos de partida y el jugador tiene menos de 20 tropas ofensivas, expandete a otro punto de mineral y haz centro de mando.

etc..."



"

[Vicente]

 Hola,

los genéticos como dice fiero se podrían usar para controlar los parámetros de otra estrategia de alto nivel que decida que tipo de decisiones tomar a nivel global, aunque normalmente cuando los he visto en juegos los he visto tuneando parámetros de más bajo nivel, pero vamos, nada impediria que controle algo de más alto nivel (podría ser un ejercicio curioso para probar ;)). Si se quiere que aprenda de sus errores un genético si que puede ser mu buena idea (pa eso son ideales), pero habría que darle tiempo. Además, igual que aprende de sus errores podría aprender del estilo de juego.

Un saludo!

Vicente

[Daemon]

 Hola a todos,

Lo de tunear los algoritmos y reducir las computaciones al minimo esta muy bien y siempre es aplicable, sin embargo depende a que nivel se haga puede quedarse corto. Con un numero de unidades suficientemente grande (¿en starcraft el limite eran 200?) ir comprobando unidad por unidad puede que no te de suficiente para mantener la apariencia de tiempo real y el mundo necesita seguir girando aunque tu no lo veas (es una forma de hablar :P).
Sin embargo si se puede aprovechar que tu no lo ves para simular el comportamiento de esas unidades que quedan fuera de la pantalla de juego en base a un estado global (por ejemplo grupo A luchando con grupo B) y a una tirada de dados con modificadores quizas mediante la fuerza relativa de cada grupo, nivel de vida global, bonificaciones defensivas, etc, (benditos juegos de rol, jeje...  :D) para de esta manera realizar los calculos mas pesados sobre aquellas unidades que necesiten dar un comportamiento real y mas fiable.

Es solo una idea. De hecho para implementar esto quizas se pudiesen usar automatas celulares (¿conoceis el juego de la vida?).

Otra de las cosas que a mi particularmente me raya bastante son lo complejas que se vuelven las maquinas de estados cuando realmente se esta usando inteligencia cooperativa, por ejemplo cuando para cumplir un objetivo hemos de tener en cuenta el estado del resto de unidades que nos acompañan. Se produce una autentica explosion de estados y casos posibles que hay que contemplar  (grrr). Ejemplo-problema: enfrentamiento de un grupo de unidades de un bando contra otro. En cada bando hay tres tipos de fichas 1, 2, 3, donde 1->2->3->1  (-> es come a). Cada ficha  tiene un radio de vision y se situan en los nodos de un grafo (o para simplificar de una cuadricula) y solo se pueden comer si estan adyacentes. Intentad hacer una inteligencia que para cada ficha tenga en cuenta el tipo de fichas con las que se encuentra en su grupo y las del grupo enemigo al que se enfrenta.

Por cierto que eso seria inteligencia de unidad, no de nivel superior.

Un saludo.

[fiero]

 En juegos como Starcraft no se pueden emplear lógicas de grupo, cada unidad tiene un comportamiento individual. Aunque haya un montón de unidades luchando entre sí fuera de la pantalla, hay que evaluarlas de forma separada, ya que dentro del grupo, algunas recibirán ataques de varios enemigos, otras de un solo enemigo, otras atacan pero no reciben, etc. Por eso hay un límite de unidades en este tipo de juegos.

Yo jugaba al Starcraft con un K6 200MHz. O sea, ahora on 3000 MHz se podrían manejar unas 3000 unidades en un juego del mismo estilo. Calculando por lo bajo claro, porque un ordenador actual tiene HyperThreading, miles de cachés, etc, con lo que si lo comparas con un K6 200, facilmente podrías manejar 5000 unidades. Y no digamos si pintas los sprites con la aceleradora, entonces te queda casi toda la CPU para IA (el Starcraft era todo por soft).

un saludo

[ethernet]

 SIempre se puede mirar el código del glest para saber como lo hace o que jare nos explique como lo hacen en praetorians  

[marcode]

 Yo haría diferentes grupos y subgrupos de unidades y mandos virtuales. Cada grupo de unidades tendría un mando virtual y estos a su vez formarían un árbol con más mandos virtuales hasta llegar al mando superior que sería el jugador.

Las decisiones de cada mando estarían determinadas por las ordenes recibidas del mando inmediatamente superior y por la información de los mandos inferiores. La actuación final de la unidad estaría determinada por las decisiones del mando inmediatamente superior y las decisiones propias de cada una.

Creo que de esta forma los mandos al ser pocos podrían tener una IA compleja y estructurada, mientras que cada unidad se ocuparía de cosas sencillas para luchar y moverse lo mejor posible.

No estoy seguro de que sirva, es solo una intuición :rolleyes:  

[senior wapo]

 A mi modo de ver:

1) Ha de haber una IA básica para el control autónomo de cada unidad.  Estos estados no hay que reevaluarlos en cada frame, sino solo cuando se dan las circunstancias que los pueden hacer cambiar de estado (mediante mensajes). Es una IA REACTIVA.
La unidad busca su propio camino y cobertura. No necesita evaluar a sus compañeros porque la IA de grupo ya le enviará el evento adecuado.

En Starcraft era:
- Si estado es MOVE: moverse a la casilla destino ignorando ataques y enemigos.
- Si estado es ATTACKMOVE: moverse al objetivo, atacando las unidades enemigas por el camino (hasta que mueran).
- Si estado es REPAIR: Reparar unidad y pasar a IDLE si no hay más ordenes encoladas.
- Si estado es RECOLECT: Recoger recursos, llevar al centro de mando, repetir y pasar a IDLE cuando no queden más.
- Si estado es IDLE: No hacer nada salvo estar siendo atacado, en cuyo caso moverse fuera de alcance.

Notese que una unidad que se está moviendo jamas reacciona ni cambia su estado hasta llegar, mientras que una en IDLE procesará el evento EVENTO_RECIBIRATAQUE y descartará los otros.


2) IA de grupo (IA intermedia) (IA REACTIVA):
Recoloca las unidades de su grupo para hacer frente al enemigo de la mejor manera posible. El número de tácticas suele ser finito. Es la que transmite las ordenes a las unidades.
- Catapultas y arqueros detrás, melee delante, etc...
- Moveos a la casilla P2 en modo ATTACKMOVE, donde P2 es, por ejemplo, el centro de masas del grupo G7 que está cerca y está siendo atacado (o la unidad más atacada, etc..). Orden recibida de la IA superior.
Recibe mensajes de la IA superior (moveos a la casilla P3) y de la IA de unidades de los miembros de su grupo (enemigo avistado, me atacan, etc..)


3) IA superior:
La que sigue los scripts u objetivos globales. Es la única cuyo estado cambia no solo por eventos sino también por scripts, objetivos etc... Es una IA PROACTIVA.
Como sabe que y donde atacar, selecciona y agrupa unidades en grupos equilibrados y a partir de ahí da ordenes a la IA de grupo (no a las unidades).
- Detecta si un grupo necesita refuerzos (tal vez mediante notificación de la IA de grupo) y
ordena a los grupo más próximos que acudan y ayuden (si procede).
- Envia grupos en misiones (por ejemplo ataque frontal para atraer unidades enemigas y a otro grupo le ordena un desembarco aereo por la otra punta de la base).
- Construcción de instalaciones, expansiones, etc...