¿Cómo se hace la evasión local de RTS?

15

Actualmente, estoy simulando las fuerzas de impacto de la física para evitar las unidades localmente, pero este método a veces empuja a las unidades fuera de la formación y tiene efectos muy indeseables cuando las unidades se agrupan.

Para juegos RTS como Starcraft 2, ¿cómo se hace la evasión local? ¿Se simula la física o un controlador omniciente decide dónde debe estar todo? Sé que esta pregunta puede ser un poco amplia, por lo que pregunto específicamente cómo lograr los comportamientos locales de evitación de Starcraft 2; aunque cualquier cosa que funcione será muy apreciada.

No busco ningún código, solo recursos útiles o explicaciones de cómo Starcraft 2 (o juegos similares) maneja la evasión local.

Actualmente, tengo implementada la detección de colisión (con el vector de penetración), las fuerzas de colisión y el movimiento por velocidad. Cada unidad se compara con otra para una colisión: si chocan, los objetos se compensan inmediatamente por el vector de penetración y luego se aplica la fuerza de colisión. Luego, otro bucle mueve los objetos por sus velocidades y aplica resistencia a las velocidades. El desplazamiento mitiga el problema de las fuerzas de colisión excesivas aplicadas en unidades agrupadas, pero las unidades a veces aún disparan.

La solución que busco debe cumplir los siguientes requisitos (como en Starcraft 2):

  • Los objetos no deben superponerse; o al menos las superposiciones deben resolverse finalmente.
  • Los objetos no se alejan más de lo necesario para que 2 unidades puedan pararse y moverse una al lado de la otra en una formación.
  • No debería haber ningún comportamiento extraño cuando los objetos se agrupan hacia el mismo destino.
  • Puede soportar unidades de diferentes tamaños, e incluso diferentes formas convexas.

En lo que he estado pensando hasta ahora es en lugar de detectar colisiones, detectar colisiones futuras para que la superposición nunca ocurra. Luego aplique la restricción, asegurándose de que las velocidades de las 2 unidades no hagan que se superpongan. Todavía estoy jugando con el algoritmo para restringir el movimiento más allá de la superposición.

JPtheK9
fuente
El "comportamiento de congregación" (término de Google) es un problema muy amplio,
Ratchet Freak
Esto estaba en la lista de votos cerrados como "demasiado amplio". Estoy dispuesto a estar de acuerdo. Intentando reducir: ¿Qué has intentado? ¿Qué "efectos indeseables" está buscando evitar? ¿Tengo razón al decir que quieres que las unidades permanezcan en formación?
Anko
Los juegos RTS a menudo funcionan para cada cliente ejecutando la misma simulación determinista en cada máquina. Básicamente, si puede resolverlo para una sola máquina, puede aplicar la misma solución a las situaciones de multijugador, cualquiera sea la técnica de evasión local con la que termine.
Alan Wolfe el
Gracias por los comentarios sobre la pregunta. Reduje un poco la pregunta y expliqué específicamente lo que estoy tratando de lograr.
JPtheK9
Este es un gran recurso: red3d.com/cwr/steer
tbkn23

Respuestas:

11

Parece que lo que está buscando es el algoritmo de prevención de colisión recíproca óptima . El artículo anterior también merece una lectura. Aunque el artículo puede estar un poco involucrado, la teoría detrás del algoritmo es bastante sencilla:

Suponga que ya tiene una simulación (juego) con agentes (unidades) que tienen algún tipo de volumen límite a su alrededor. Es probable que este volumen límite sea lo que ya está utilizando para realizar la detección y respuesta de colisión. Para cada agente, defina una velocidad preferida v_pque pueda o no basarse en la meta del agente.

Ahora, para realizar la simulación:

  1. Para cada agente, suponiendo que sea estacionario, calcule todas las velocidades que podrían hacer que colisionen en cualquier momento en el futuro con cualquiera de los otros agentes en movimiento. Esto se puede representar en el "espacio de velocidad" como un conjunto de semiplanos que se cruzan (también conocido como obstáculo de velocidad ).
  2. Determine el punto en este espacio más cercano a v_p, esta es la nueva velocidad de la unidad.

Si todos los agentes están ejecutando el mismo algoritmo, elegirán velocidades que se complementen entre sí y evitarán otros agentes. En algunas situaciones, puede causar oscilaciones como esa cosa incómoda que ocurre cuando camina directamente hacia alguien en el pasillo y ambos intentan apartarse en la misma dirección, pero los documentos cubren cómo evitar eso.

Para calcular las dos etapas del algoritmo anterior, puede usar las sumas de Minkowski para determinar cuál es el obstáculo de velocidad, y luego usar un modelo de programación lineal (como el Algoritmo Simplex ) para determinar el punto más cercano al v_pque evita el obstáculo de velocidad. Además, el código para evitar colisiones está disponible para su lectura y se ha transferido a C # para usarse en motores de juegos como Unity. Esta técnica se ha utilizado al menos en Warhammer 40,000: Space Marine y quizás en otros juegos .

Mokosha
fuente
Ese fue un artículo increíble y siento que leí la mitad de tu explicación. Gracias por esta información.
JPtheK9
0

No sé cómo funcionan sus unidades, pero supongo que son como una máquina de estado:

Estados posibles

  • Corriendo a (x, y, z)
  • Atacar (enemigo_id)
  • Recopilación de recursos (ressource_id)

Si prestas atención a cómo Starcraft aborda este problema, encontrarás que:

  1. Si hay espacio para moverse en una dirección, el personaje se mueve en esa dirección.
  2. Si no hay espacio, la unidad en el camino se moverá para hacer espacio
  3. Si la unidad que necesita moverse para hacer espacio ya tiene un comando, mantendrá el comando, pero lo modificará ligeramente para eventualmente hacer lugar.

Aquí escenario 1:

ingrese la descripción de la imagen aquí

¿Tengo espacio para ir allí? Si ? Entonces vete

Escenario 2:

ingrese la descripción de la imagen aquí

¿Tengo espacio para ir allí? No ? Oye, ¿puedes hacerme un espacio? Me estás bloqueando. Ya tengo una orden para moverme hacia adelante, pero lo acomodaré.

Entonces, qué necesitará implementar:

  • Las unidades deben ser conscientes de su entorno.
  • Las unidades deben tener una forma de comunicarse entre sí
  • Debe implementar una forma de seguir ejecutando un comando mientras acomoda otra unidad
Antoine
fuente
Gracias por la información y visualización. En este momento estoy usando la detección de colisión para averiguar si una unidad puede moverse a otro lugar o si otra unidad la está ocupando. Lo principal que estoy tratando de descifrar es un algoritmo de algún tipo para decirle a la otra unidad qué distancia mover o qué velocidad ajustar. En otras palabras, cómo la unidad de bloqueo acomodará a la unidad que intenta pasar.
JPtheK9
Dado que este comportamiento se calcula en cada actualización de física, no es necesario que sepa la distancia, se moverá hasta que esté fuera del camino. Para la dirección, escanea simplemente multiplica la velocidad de las dos unidades, esto te dará el punto a la mitad para que siga moviéndose mientras acomodas. Después de eso, puedes jugar con eso para que se adhiera más al orden o salga del camino más rápido.
Antoine
¿Qué quieres decir con "movimientos hasta que esté fuera del camino"? ¿Cómo se mueve la unidad en primer lugar?
JPtheK9
Lo siento, olvidé mencionar: las unidades no son máquinas de estado. Tienen muchas habilidades en su casillero que se simulan en cada cuadro, excepto que estas habilidades solo tienen efecto cuando se activan, ya sea que el destino esté a una distancia de X o con la existencia de un objetivo. El movimiento de una unidad es el resultado de su velocidad que puede ser cambiada por una habilidad.
JPtheK9
0

Una forma de hacerlo es hacer que las unidades formen auto formaciones y hacer que intenten permanecer en una posición relativa al centro de la formación . Luego, en lugar de mover cada unidad individualmente, mueva el centro de la formación.

Aquí hay una forma básica de hacerlo usando una formación de caja y resortes simples para mantener las unidades en sus posiciones apropiadas:

// Defines a phalanx (box) formation
class Formation
    // Center of the box in the world
    Position center;
    // Width in # of units
    int width;
    // Height in # of units
    int height;
    // Space between units
    float scale;
    // How much force units will apply to stay near
    // their assigned spot.
    float springforce;

    // Return a position of a unit at the given row and column
    // Todo: add a rotation to this formation so it can rotate when moving.
    Position GetUnitPhalanxPosition(int row, int column)
        return new Position(center.X + column * scale - width * scale /2, 
                            center.Y + row * scale    - height* scale / 2);

// Represents a simple point object with a velocity and position;
// it belongs to a formation.
class Unit
    Position pos;
    Velocity vel;
    Formation formation;
    // What's our assigned spot in the formation?
    int row;
    int column;

    void Update(float dt)
        // Get the desired target position in the formation
        Position target = formation.GetUnitPhalanxPosition(row, column);
        // Apply a spring force toward the position (todo: you might want to damp this)
        vel += (target - position) * dt * formation.springforce;
        // Move along the velocity vector.
        pos += vel * dt;
mklingen
fuente
¡Gracias! Esta es una solución realmente interesante y creativa. He implementado algo similar a esto para el comportamiento / formaciones de multitudes, pero todavía tengo el problema de la superposición de unidades. ¿Qué debería pasar si 2 formaciones se topan?
JPtheK9
Creo que depende del diseño. Lo más fácil sería aplicar otra fuerza de dirección lejos de las unidades cercanas en otras formaciones como en esta imagen . Otra cosa que puedes hacer es fusionar formaciones cuando el jugador las selecciona, o incluso formar "
metaformaciones
Las metaformaciones suenan realmente complicadas y con errores: C. Sin embargo, la imagen que vinculaste podría ser exactamente lo que necesito. Voy a investigar un poco más sobre las fuerzas de dirección. ¿Tienes el enlace al artículo de la imagen?
JPtheK9
Tengo un problema similar al tuyo, sería interesante saber cómo lo resolviste. Una idea se me ocurrió después de leer este artículo: quizás combinando Pathfinding (A *) para una planificación de macro ruta mientras se usa la fuerza de repulsión para evitar la micro colisión:
ColdSteel
0

Sé que algunas personas fruncen el ceño ante la descarga de enlaces, sin embargo, encontré que un enfoque basado en el campo potencial de múltiples agentes para bots de juego de estrategia en tiempo real (ISBN 978-91-7295-160-0) es un documento muy esclarecedor, y obviamente transmite mucho más de lo que podría explicar. El documento explora el uso de campos de potencial artificial (un concepto que se origina en la robótica), para facilitar la prevención de colisiones locales dentro de un contexto de desarrollo de juegos.

DanoThom
fuente
¡Gracias! La investigación es tan útil como la explicación para mí. Me sumergiré en este papel.
JPtheK9
Ya tengo configurado un mapa de influencia, pero esto parece demasiado complicado para mis gustos. Lo principal es generar campos potenciales para diferentes unidades para moverlos, y también convertir los datos del campo potencial en una velocidad para moverse. Básicamente, no creo que esto funcione para unidades de diferentes tamaños. Sin embargo, es una gran lectura con muchas ideas interesantes.
JPtheK9