Naves espaciales modulares e IA

elkaoD #1 Feb '11

Hola amigos, he venido con una de mis preguntas extrañas.

Hace un tiempo tuve una idea de un videojuego: a grandes rasgos es un shooter espacial por turnos en el que manejas varias naves para destruir a las del rival, rollo juego de estrategia. Las naves que controlas las crea el propio jugador, que dispone de cierta materia-energía para crear naves al principio de la partida y la energía sobrante se usa durante la partida para propulsar, atacar, realizar habilidades... La forma de la nave debería afectar a su comportamiento, así como la posición de los motores, lásers y demás módulos.

Una de los conceptos clave es el manejo de las naves, y esto me tiene un poco loco. Una de las cosas que he pensado que se pueden manejar las naves a mano, encendiendo y apagando los motores. Por un lado le da un aspecto profundo al juego, al manejar la nave al detalle, pero por otro lado... puede ser un coñazo.

La opción B y que creo más interesante, es que a pesar de influir las características en el comportamiento físico de la nave, el juego tenga algún sistema de inteligencia artificial en el que tú, como comandante, des órdenes simples (mover, orientar, atacar...), y la IA se encargue de realizar el trabajo sucio. El problema radica principalmente en cómo funcionaría esa inteligencia artificial. Mi duda principal viene al pensar en el movimiento: la IA recibe un destino y una orientación como órdenes, ¿pero como puede saber cuál sería la potencia adecuada en cada motor para realizar el giro adecuado, por camino más corto y lograr un comportamiento fluido? Aquí un dibujillo estúpido de a qué me refiero:

Esto es un escenario simple, la nave quiere girar sobre su eje para mirar hacia abajo, por lo que debería activar los dos motores superiores. Pero, ¿con cuánta fuerza? Además hay que tener en cuenta que esa fuerza va a crear una traslación en la dirección de la fuerza, aunque sea mínima, así que tambien hay que tenerla en cuenta. Ahora pensad en naves más complejas, disposiciones de motores más raras, movimientos extraños... todo se complica.

Con que la IA supiera manejar entre dos puntos diferentes y pueda girar a una cierta posición angular usando el camino más corto me valdría. He pensado en precalcular los movimientos y guardarlos en una tabla como incrementos, o en expresar los movimientos como ecuaciones en base a la potencia de los motores, pero aún así siempre hay varias soluciones al problema (se llega desde varios ángulos a la misma posición) y estoy un poco perdido en cómo atacarlo. ¿Ideas?

Lo bueno además es que crear una IA para un jugador a partir de este sistema no es muy difícil, al reaprovechar casi todo el cáculo del movimiento.

Gracias por leer este tocho y bienvenidas sean todas las ideas.

dr_Rouman #2 Feb '11

Buf, creo que estás abordando dos problemas a la vez. Cómo se va a mover la nave según los motores (y cuántos tipos de naves, o disposición de los motores hay) y luego cómo hacer que la nave se mueva sola de forma razonable. Sólo lo primero creo que es bastante jodido, y lo segundo será hacer muchas pruebas sobre un modelo que funcione.

Para seguir un objetivo, por ejemplo, seguir a una nave que huye, puedes usar algo como curvas de persecución: http://es.wikipedia.org/wiki/Curva_de_persecuci%C3%B3n

Si el objetivo no se mueve, supongo que es una línea recta. Viendo el dibujo, la idea es que sea tridimensional, no?

Creo que deberías:
a) Delimitar cómo de complejas van a ser las naves
b) Hacer los cálculos y las pruebas con un modelo sencillo, y avanzar desde ahí, e intentar generalizarlo con otros más complejos.

Matemáticamente habría que estudiarlo, pero creo que la curva de persecución puede ser una buena idea para objetos en movimiento.

Si nos ponemos en el caso en el que le has dicho que vaya a X y en el camino le dices que vaya a Y, entonces sí que hay que ver cómo hacer las rotaciones. En juegos de naves, como el SOASE, normalmente las naves trazan una curva bastante amplia hasta que están en línea con el objetivo y empiezan a acercarse / perseguir. Supongo que en tu caso, dándole más fuerza al motor derecho que al izquierdo, se trazará una curva (según la potencia, más suave o menos) que habría que mantener mientras no estés en un ángulo límite con la otra nave / objetivo.

#1 Quote para Aviso

Debería avisar si te contestan en tus hilos hummm

1 respuesta

elkaoD #3 Feb '11

Wow #2, había perdido la fe de que alguien contestara xDD

En realidad no estoy atacando dos problemas, ya que el movimiento de la nave y demás ya lo tengo resuelto. En un principio iba a implementarlo con alguna biblioteca libre de física 3D, pero necesito alguna que funcione con matemática de coma fija (o directamente aritmética entera), pero no existen en 3D, así que el sistema físico lo voy a acabar haciendo yo. Esto lo necesito para que entre arquitecturas/compiladores no haya diferencias entre los cáculos (malditas FPUs y optimizaciones), y estos sean deterministas y por tanto reproducibles (tanto en replays como para envío por internet) en base sólo a estado inicial+entradas y no a estados intermedios aproximados (que es como funcionan los FPS.) También para evitar errores inherentes de precisión y para portarlo a plataformas sin FPU.

El sistema físico es lo de menos, ya que voy a hacer cientos de aproximaciones... sólo cuerpos rígidos, integración Euleriana semiimplícita, timestep fijo, etc. Los motores entonces aplicarán fuerzas en la posición donde estén anclados a la nave, perpendicularmente, creando una rotación y una translación en el acto. En realidad no sé si usar un sistema basado en inercia (fuerzas) o en energías-muelles, pero bueno.

Respondiendo a tu pregunta... ¿Cuántos tipos de naves y disposición de los motores hay? Infinitas. Ese es el problema. Intento que cada usuario pueda diseñar sus propias naves, con sus ventajas e inconvenientes tanto en disposición de motores (y otros módulos) como en forma, masa... Por ejemplo, una nave que tenga motores en la parte frontal tendrá más fácil frenar, una que tenga un motor en la parte superior derecha ahorrará combustible al no tener que encender el motor derecho e izquierdo a la vez (y si lo hace cogerá más velocidad), etc. etc. Por otro lado, a más motores, más masa, más gasto energético en "construir" la nave, más gasto energético en moverla por el campo de batalla, etc.

No pretendo que estas sigan a un objetivo ni cambiar la dirección en mitad del vuelo. Es para un juego por turnos, así que al principio de cada turno los jugadores dan una dirección o y rotación objetivo a todas las naves, y estas hacen lo que puedan para llegar a esa posición con esa orientación durante la fase de resolución del turno (que dura X timesteps hasta que se vuelve a la fase de órdenes.) Me da igual incluso que haya pequeñas correciones automáticas en mitad del viaje mientras que el resultado sea determinista y reproducible, y se comporte como una nave espacial (como bien comentas en uno de los últimos párrafos de tu post.)

El problema de esto es que no se puede integrar una trayectoria fácilmente, ya que depende de todos los estados intermedios y su continuidad, así que habría que simular la trayectoria entera para todos y cada uno de los timesteps fijos. Ahora hay otro problema, habría que simular todas las trayectorias de todos los diferentes estados de los motores (desde apagado hasta encendido al 100%, pasando por 50% de potencia, etc. etc.)

Lo de las infinitas naves nos lleva a más problemas... ¿qué hay de naves con un sólo motor que no puedan realizar ciertos giros, o los realicen tras MUCHAS revoluciones? ¿Qué hay si entre medias de las trayectoria se choca con algo y se desvía? Porque habría que calcular de nuevo otra vez la trayectoria. ¿Qué hay de trayectorias compuestas por diferentes configuraciones de motores que den más ventaja que una configuración inicial determinada?

Por eso he llegado a la conclusión de que lo mejor es que la nave actúe lo más parecido a un humano posible, recalculando dinamicamente cada ciertos pasos su objetivo y cómo cumplirlo, por lo que solo necesitaría recalcular cada X pasos los motores que necesitas encender o apagar y la propia nave se adecuaría a los pequeños cambios de trayectoria y demás detallitos. Seguimos en el problema inicial: cómo, dado un vector objetivo, hacer que los motores actúen.

Como ves se me va mucho la pinza xD Porque esto que estoy comentando es sólo una de las muchas locuras que estoy teniendo en cuenta para el diseño del juego. No quieres conocer el resto xDD

1 respuesta

BLZKZ #4 Feb '11

yo pondria para el movimiento una velocidad constante por motor, y una direccion lineal (si parte desde 0 deberias poner una acceleracion hasta alcanzar dicha velocidad) y que si hay dos motores que dirigen la nave hacia el mismo lugar que por ejemplo la veloc maxima fuera 1.5 veces la de un motor y asi. La fuerza (según donde programes) lo haria por pixels/frame, al menos asi he hecho fisicas sencillas en opengl y tambien para wp7

1 respuesta

elkaoD #5 Feb '11

#4, lo que comentas para el movimiento de las naves, que ya lo tengo solucionado. Mi duda entra en la aproximación/predicción/loquesea de esas naves por la IA, para simplificar la entrada del usuario a un simple destino-rotación, y no fuerzas aplicadas por los motores individualmente.

Lo de la aceleración (creo que te refieres a aceleración, no velocidad) constante por motor ya lo he pensado, y la verdad me lo plantearía seriamente si simplifica los cálculos, pero realmente dudo que ayude mucho (el gran problema está en el path-finding aplicado a giros, y no rutas.)

La aceleración obviamente se aplica de forma lineal, pero el problema viene en que una aplicación de una aceleración lineal en un cuerpo rígido no regular crea giros a partir de un punto central, el centro de masas, por lo que a tomar p.c. la linearidad de todo xDD Esto no estoy dispuesto a sacrificarlo, porque no habría una ventaja real en la posición de los motores aparte de la estética y la lineal (que es la que no supone problema) y entonces pierde la gracia el diseño exhaustivo de las naves.

Lo que pretendo es que cada jugador, dados unos puntos iniciales de energía, se construya su propia flota gastando esos puntos de energía en crear masa (el esqueleto de la nave), módulos (campos tractores, lásers, misiles...) y otra parte de energia que dejará para consumir durante la partida. Habrá gente que prefiera tener una nave-máquina-de-matar-gigantesca acompañada de una pequeña flotillas. Otros preferirán tener un montón de naves muy rápidas con poca potencia de ataque. Otro se hará su flotilla con naves rápidas linealmente para la exploración, y naves rápidas en giros sobre sí mismas para el combate cercano... A su vez, al entrar la energía "sobrante" en juego, las naves pequeñas necesitarán de poca energía para moverse (por su poca masa), mientras que las naves nodrizas se moveran o muy lento, o muy caro energéticamente (y necesitarán más motores si quieren gastar más energía en crear energía cinética, lo cuál restará también energía al global.) Ahí es donde radica la gracia del planteamiento y balanceo de mi juego, creo.

Por cierto, pixels/frame no es una fuerza, sino una velocidad! No me interesa aplicar velocidades, más que nada porque acaba explotando el motor físico por todos lados, y porque pretendo usar un integrador a partir de fuerzas aplicadas en puntos, para intentar conservar la energía y esas cosas. Para simulaciones ultra-simples está bien, pero pretendo algo de interacción real.

1 respuesta

dr_Rouman #6 Feb '11

#3

Efectivamente, es una movida enorme.

<inciso>
Lo de que sea un sistema determinista también lo "necesito" yo. Tengo una práctica de procesadores del lenguaje, y estamos pensando en hacer un clon muy sencillo del Frozen Synapse, en el que definiríamos un lenguaje de scripting para los movimientos de cada turno. Y claro, tiene que ser reproducible IGUAL en todos los clientes. Una historia xD

Para solventarlo había pensado o bien que uno de los dos clientes hiciera los cálculos y le de el resultado al otro, o que haya un servidor que lo haga.
</inciso>

Obviando todas las complicaciones que entraña el diseño, activar o desactivar un motor en función de un vector objetivo puedes hacerlo con algo de búsqueda.
La IA, antes de hacer nada, simula en cada momento distintas combinaciones de motores, y se queda con la que le acerque más al objetivo.

Por ejemplo, si tiene dos motores a los lados y uno delante para frenar, puede probar con varias combinaciones. Puedes evaluar lo bueno o lo malo de una solución viendo la distancia a la que te deja esa combinación de tu objetivo (a la inversa).

Esto tiene el problema de que si lo quieres hacer muy muy muy complejo (que haya una aceleración de 0 a 1000) las posibilidades son demasiadas para evaluar así.

Siempre puedes hacer otra cosa, y es usar una IA así en el desarrollo, y con las salidas que te de, intentar sacar un modelo que no necesite un algoritmo de búsqueda. No sé si me explico xD

1 respuesta

BLZKZ #7 Feb '11

#5 un cuerpo no creo que acelere continuamente y si son naves espaciales a no ser que choquen alcanzaran una velocidad máxima (constante) y la aceleración será 0.

He vuelto a leer lo que quieres hacer y es bastante complicado, pero lo de calcular la dirección lo puedes hacer sobre un plano 2D que te soluciona muchas cosas. Solo tendras en cuenta en ese caso la velocidad angular y la dirección inicial de cada instante, imagino que hallando las componentes del plano (usando sen o cos) sacaras con facilidad la dirección final. Asi lo hacia yo para calcular trayectorias, son calculos bastante sencillos, y siguen siempre el mismo patron.

Lo del reparto de energia es arbitrario creo que no deberias complicarte en principio demasiado con eso.

La aceleración es una fuerza aplicada a una masa (esto es fisica muy simple) y la velocidad es el resultado, no creo que me equivocara tanto xD

1 respuesta

elkaoD #8 Feb '11

#6 <respuesta al inciso>
Pues por lo que veo lo que yo quiero hacer es parecido a lo tuyo. Te recomiendo Box2D porque veo que vas a trabajar en el plano para mover los objetos. A mí no me vale porque es 2D, pero a ti te va a salvar el culo probablemente xDD Como se tuvo que portar a la DS para nosequé juego homebrew, se hizo el parche para que use aritmética de coma fija, y se acabó integrando en la rama principal de la librería, así que lo puedes compilar como coma fija o flotante. Si lo usas como coma fija, el resultado es determinista al 100% dado unas condiciones iniciales y entradas (o al menos así debería ser.)

Por eso mismo yo necesito la reproducibilidad también. Los clientes sólo conocen un estado inicial y comparten, al final del turno, unas entradas para cada entidad, resolviéndola cada una en su PC. Se puede sincronizar el estado final, pero paaaaaso xD No me parece elegante para un juego que no es real-time, y además, aunque la arquitectura que tengo pensada es cliente-servidor, probablemente también implemente un modelo P2P que creo que es lo que quieres hacer tú, y no quiero que ninguno de los dos clientes sea autoritativo.

Mi idea inicial cuando aún pensaba en el modelo p2p exclusivo era que cada cliente, al dar el botón de "finalizar turno", mandase un hash de las entradas que ha definido al resto de clientes. Cuando todos los clientes finalizan turno, estos intercambian sus respectivas entradas y verifican que no difiere el hash de lo que han recibido del resto con los hashes que recibieron previamente (para evitar cheating.)

Procesadores del lenguaje yo doy el año que viene, a ver qué tal, porque ya me comí mucho la cabeza en su día implementando scripting (y acabé bindeando LUA por desespración.)
</inciso>

Por ejemplo, si tiene dos motores a los lados y uno delante para frenar, puede probar con varias combinaciones. Puedes evaluar lo bueno o lo malo de una solución viendo la distancia a la que te deja esa combinación de tu objetivo (a la inversa).
Es más o menos lo que tenía pensado, hacer esto todo el rato según va siguiendo el camino, pero es taaaaan hacky que me da miedo. Además como tú mismo dices, cuantos más motores y estados intermedios, más complejo todo, pero creo que se acerca un poco más a la solución que cualquier otra cosa.

Siempre puedes hacer otra cosa, y es usar una IA así en el desarrollo, y con las salidas que te de, intentar sacar un modelo que no necesite un algoritmo de búsqueda. No sé si me explico xD
¿Te refieres a una IA que aprenda? Yo esto también lo había pensado, que las naves cuanto más las utilices más "aprendan", y vayan guardando esos datos para ir aprendiendo cada vez más de sus errores (o aciertos) con una red neural o algo así. Un poco locura igualmente, no me quiero meter en movidas de IA taaaaaan complejas si no es necesario.

De todas formas me acabo de dar cuenta de una cosa según escribía esto que puede simplificar mucho el tema, así que lo desarrollo un poco, hago una imagen explicativa y edito el post en cuanto pueda.

#7 un cuerpo no creo que acelere continuamente y si son naves espaciales a no ser que choquen alcanzaran una velocidad máxima (constante) y la aceleración será 0.
Eso lo manejo no con velocidad máximas, sino con pérdidas de energía (damping en inglés, ni idea en castellano.) El resultado es el mismo y cuadra con el modelo físico que quiero implementar.

Lo del reparto de energia es arbitrario creo que no deberias complicarte en principio demasiado con eso.
¿Te refieres a lo que he explicado del sistema de balanceo en base a energías y tal? Eso no me como la cabeza, fue lo primero que pensé y en lo que se basa toda la dinámica del juego, pero hasta que no esté hecho no puedo empezar a balancear este aspecto. Si te refieres a que el sistema conserve la energía, es esencial. Estos sistemas tienden a explotar al intentar discretizar cosas que son continuas. Te puedes imaginar lo que le pasa a un sistema cerrado que va acumulando cada vez más energía...

Lo de la velocidad-fuerza y tal, no es un gran fallo, pero en estos casos importa más de lo que parece. Ya tengo muchas horas de física de juegos a mis espaldas, es una puta locura por cosas como que no puedes considerar la velocidad como un efecto de una fuerza. Para que no explote, la velocidad debe integrar a partir de la aceleración, y esta a su vez desde el momento, y este a su vez desde impulsos. En esas integraciones los sistemas tienden a acumular energía al estar tratando cosas continuas como discretas, y sobre todo si se unen efectos como rozamiento y demás, que modifican los diferentes valores en mitad del procesado (obligando a re-integrar y, si no tienes cuidado, te salen constantes donde no las hay.)

Por ejemplo, integración euleriana básica:
v += at
s += vt

Ahí ya ha habido un error enorme, puesto que la velocidad ¡no es constante!

Si se realiza la integración euleriana de forma semiimplícita:
s = s0 + v0t + 0.5at*t

Se medio-arregla el efecto, pero al ser un método de integración de primer orden se cometen errores igualmente. El primero no funciona bien nunca, a no ser que la velocidad sea constante. El segundo, si la aceleración es constante (que en el caso de un juego de naves espaciales, no lo es.)

Hay formas mejores de integrar los valores para eliminar esos efecto (Euler es un método de integración de primer grado solo), pero sigue siendo importante la diferenciación entre velocidades, aceleraciones, fuerzas, etc.

EDIT: #6, esto era lo que había pensado en mitad de escribir el post. Si tú tienes un motor (definido por un vector perpendicular al plano donde está anclado, y un punto de anclaje) y un destino (formando un vector con el punto de anclaje), cuanto más parecido a 180º sea el ángulo que forman ambos vectores, menos hay que acelerar ese motor, y cuando llegan a 0º el motor hay que darlo a tope (¡línea recta!) y funciona igual en 3D que en 2D. Esto es mucho más factible de realizarse en cada paso, y así a primera vista no le veo ningún fallo, incluso aunque genere rotación, ya que no se consideran trayectorias sino la posición actual en cada timestep.

Creo que saldrá algo poco óptimo, pero al fin y al cabo bastante humano. En nuestro cerebro creo que haríamos algo parecido al manejar una nave con propulsores.

Creo que por aquí van los tiros. Ah, ¡y gracias a ambos por las respuestas!

Usuarios habituales