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

15

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.

JPtheK9
fonte
"O comportamento reunindo" (google prazo) é uma ampla problema,
catraca aberração
Isso estava na fila de votos próximos como "muito amplo" - estou inclinado a concordar. Tentando restringir: O que você tentou? Quais "efeitos indesejáveis" você deseja evitar? Estou certo ao dizer que você deseja que as unidades permaneçam em formação?
Anko
Os jogos RTS geralmente funcionam por cada cliente executando a mesma simulação determinística em cada máquina. Então, basicamente, se você puder resolvê-lo para uma única máquina, poderá aplicar a mesma solução às situações multijogador, qualquer que seja a técnica de prevenção local que você usa.
Alan Wolfe
Obrigado pelo feedback sobre a questão. Eu estreitei a pergunta um pouco e expliquei especificamente o que estou tentando realizar.
precisa saber é o seguinte
Este é um ótimo recurso: red3d.com/cwr/steer
tbkn23

Respostas:

11

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 .

Mokosha
fonte
Esse foi um artigo incrível e eu sinto que li metade dele na sua explicação. Obrigado por esta informação.
precisa saber é o seguinte
0

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:

insira a descrição da imagem aqui

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

Cenário 2:

insira a descrição da imagem aqui

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
Antoine
fonte
Obrigado pela informação e visualização. No momento, estou usando a detecção de colisão para descobrir se uma unidade pode se mover para outro lugar ou se outra unidade está ocupando-a. A principal coisa que estou tentando descobrir é um algoritmo de algum tipo para dizer à outra unidade qual distância mover ou qual velocidade ajustar. Em outras palavras, como a unidade de bloqueio acomodará a unidade que está tentando passar.
precisa saber é o seguinte
Como esse comportamento é calculado a cada atualização física, você realmente não precisa dizer a distância, ele se moverá até ficar fora do caminho. Para a direção, você digitaliza simplesmente multiplicar a velocidade das duas unidades, o que lhe dará o ponto até a metade, para que ele continue se movendo enquanto estiver acomodando. Depois disso, você pode brincar com isso para torná-lo mais adequado à ordem ou sair do caminho mais rapidamente.
Antoine
O que você quer dizer com "se move até sair do caminho"? Como a unidade se move em primeiro lugar?
precisa saber é o seguinte
Desculpe, esqueci de mencionar: as unidades não são máquinas de estado. Eles têm muitas habilidades no armário que são simuladas em todos os quadros - exceto que essas habilidades só têm efeito quando ativadas, seja pelo destino que está a X distância ou com a existência de um alvo. O movimento de uma unidade é resultado de sua velocidade que pode ser alterada por uma habilidade.
precisa saber é o seguinte
0

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;
mklingen
fonte
Obrigado! Esta é uma solução realmente interessante e criativa. Eu implementei algo semelhante a isso para o comportamento / formações de multidões, mas ainda tenho o problema de sobreposição de unidades. O que deve acontecer se duas formações se colidirem?
JPtheK9
Eu acho que depende do design. O mais fácil seria aplicar outra força de direção longe de unidades próximas em outras formações, como nesta imagem . Outra coisa que você poderia fazer é formações se fundem quando são selecionados pelo jogador, ou mesmo formar "meta-formações"
mklingen
Meta-formações parecem realmente complicadas e com erros: C. A imagem que você vinculou pode ser exatamente o que eu preciso. Vou fazer mais algumas pesquisas sobre as forças de direção. Você tem o link para o artigo da imagem?
precisa saber é o seguinte
Eu tenho um problema semelhante ao seu, seria interessante saber como você o resolveu. Depois de ler este artigo, surgiu uma idéia: talvez combinando o Pathfinding (A *) para um planejamento de macro trajetos, usando a força de repelência para evitar a colisão:
ColdSteel 29/17/17
0

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.

DanoThom
fonte
Obrigado! A pesquisa é tão útil quanto a explicação para mim. Eu vou mergulhar neste papel.
precisa saber é o seguinte
Já tenho um mapa de influência, mas isso parece complicado demais para o meu gosto. O principal é gerar campos potenciais para diferentes unidades para movê-los e também converter dados do campo potencial em uma velocidade para se mover. Basicamente, não acho que isso funcionaria para unidades de tamanhos diferentes. É uma ótima leitura, embora com muitas idéias interessantes.
JPtheK9