Como é feita a prevenção local do RTS?

Atualmente, estou simulando forças de impacto físico para evitar unidades locais, mas esse método às vezes empurra as unidades para fora de formação e tem efeitos muito indesejáveis ​​quando as unidades se aglomeram.

Para jogos RTS como Starcraft 2, como é feita a prevenção local? A física é simulada ou um controlador onipotente decide onde tudo deve estar? Sei que essa pergunta pode ser um pouco ampla, estou perguntando especificamente como obter os comportamentos locais de prevenção de Starcraft 2; embora qualquer coisa que funcione será muito apreciada.

Não estou procurando nenhum código - apenas recursos úteis ou explicações sobre como o Starcraft 2 (ou jogos similares) lida com a prevenção local.

Atualmente, tenho detecção de colisão (com vetor de penetração), forças de colisão e movimento por velocidade implementados. Cada unidade é comparada com outra em busca de uma colisão - se elas colidem, os objetos são imediatamente deslocados pelo vetor de penetração e a força de colisão é aplicada. Em seguida, outro loop move os objetos de acordo com suas velocidades e aplica um arrasto às velocidades. A compensação mitiga o problema de forças de colisão excessivas aplicadas em unidades agrupadas, mas as unidades ainda às vezes disparam.

A solução que estou procurando precisa atender aos seguintes requisitos (como no Starcraft 2):

• Objetos não devem se sobrepor; ou pelo menos as sobreposições devem ser eventualmente resolvidas.
• Os objetos não se afastam mais do que o necessário, para que duas unidades possam ficar em pé e se moverem juntas em uma formação.
• Não deve haver comportamentos estranhos quando os objetos se aproximam do mesmo destino.
• Pode suportar unidades de tamanhos diferentes e até formas convexas diferentes.

O que eu tenho pensado até agora é, em vez de detectar colisões, detectar colisões futuras para que a sobreposição nunca aconteça. Aplique a restrição, certificando-se de que as velocidades das duas unidades não as sobreponham. Ainda estou mexendo no algoritmo para restringir o movimento além da sobreposição.

Parece que o que você está procurando é o algoritmo ideal para evitar colisões recíprocas . O artigo anterior também merece uma leitura. Embora o artigo possa estar um pouco envolvido, a teoria por trás do algoritmo é bastante direta:

Suponha que você já tenha uma simulação (jogo) com agentes (unidades) que tenham algum tipo de volume delimitador ao seu redor. Esse volume limite provavelmente é o que você já está usando para executar a detecção e resposta de colisão. Para cada agente, defina uma velocidade preferida v_pque pode ou não ser baseada no objetivo do agente.

Agora, para executar a simulação:

1. Para cada agente, supondo que seja estacionário, calcule todas as velocidades que causariam a colisão em qualquer ponto no futuro com qualquer outro agente em movimento. Isso pode ser representado no "espaço da velocidade" como um conjunto de semiplanos que se cruzam (também conhecido como obstáculo à velocidade ).
2. Determine o ponto neste espaço mais próximo v_p, esta é a nova velocidade da unidade.

Se todos os agentes estiverem executando o mesmo algoritmo, eles escolherão velocidades que se complementam mutuamente e evitarão outros agentes. Em algumas situações, você pode causar oscilações como aquela coisa estranha que acontece quando você entra diretamente em alguém no corredor e os dois tentam sair do caminho na mesma direção, mas os documentos cobrem como evitar isso.

Para calcular os dois estágios do algoritmo acima, você pode usar Minkowski Sums para determinar qual é o obstáculo de velocidade e, em seguida, usar um modelo de programação linear (como o Simplex Algorithm ) para determinar o ponto mais próximo ao v_pque evita o obstáculo de velocidade. Além disso, o código para evitar colisões está disponível para sua leitura e foi portado para C # para ser usado em mecanismos de jogos como o Unity. Essa técnica foi usada pelo menos no Warhammer 40.000: Space Marine , e talvez em outros jogos .

Não sei como suas unidades funcionam, mas presumo que sejam como uma máquina de estado:

Estados possíveis

• Correndo para (x, y, z)
• Ataque (inimigo_id)
• Coletando recursos (ressource_id)

Se você prestar atenção em como a starcraft aborda esse problema, você verá que:

1. Se houver espaço para se mover em uma direção, o caractere se moverá nessa direção.
2. Se não houver espaço, a unidade se moverá para abrir espaço
3. Se a unidade que precisa se mover para liberar espaço já tiver um comando, ela manterá o comando, mas modifique-o levemente para, eventualmente, substituí-lo.

Aqui cenário 1:

Eu tenho espaço para ir para lá? Sim ? Então vá

Cenário 2:

Eu tenho espaço para ir para lá? Não ? Ei, você pode dar algum espaço para mim, você está me bloqueando. Eu já tenho uma ordem para avançar, mas eu o acolherei.

Então, o que você precisará implementar:

• As unidades devem estar cientes de seus arredores
• As unidades devem ter um meio de comunicação entre si
• Você deve implementar uma maneira de continuar executando um comando enquanto acomoda uma outra unidade

Uma maneira de fazer isso é fazer com que as unidades formem automaticamente formações e tentem permanecer em uma posição relativa ao centro da formação . Em vez de mover cada unidade, mova o centro da formação individualmente.

Aqui está uma maneira básica de fazer isso usando uma formação de caixa e molas simples para manter as unidades em suas posições apropriadas:

// 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;

Conheço algumas pessoas que desaprovam o despejo de links, no entanto, achei uma abordagem baseada em campo potencial para vários agentes para robôs de jogos de estratégia em tempo real (ISBN 978-91-7295-160-0) como um documento muito esclarecedor, e obviamente transmite muito mais do que eu poderia elaborar. O artigo explora o uso de campos potenciais artificiais (um conceito originário da robótica), para facilitar a prevenção de colisões locais em um contexto de desenvolvimento de jogos.