Implementando um fio de embrulho (como o Worms Ninja Rope) em um mecanismo de física 2D

34

Estive experimentando um pouco de física das cordas recentemente e descobri que a solução "padrão" - fabricar uma corda a partir de uma série de objetos amarrados a molas ou juntas - é insatisfatória. Especialmente quando o balanço da corda é relevante para a jogabilidade. Eu realmente não me importo com a capacidade de uma corda enrolar ou ceder (isso pode ser falsificado para efeitos visuais).

Para a jogabilidade, o importante é a capacidade da corda envolver o ambiente e, posteriormente, desembrulhar. Nem precisa se comportar como uma corda - um "fio" feito de segmentos de linha reta faria. Aqui está uma ilustração:

Corda ninja, envolvendo obstáculos

Isso é muito parecido com o "Ninja Rope" do jogo Worms.

Como estou usando um mecanismo de física 2D - meu ambiente é composto de polígonos 2D convexos. (Especificamente, estou usando o SAT no Farseer.)

Então, minha pergunta é a seguinte: como você implementaria o efeito "quebra automática"?

Parece bastante óbvio que o fio será composto de uma série de segmentos de linha que "se dividem" e "se unem". E o segmento final (ativo) dessa linha, onde o objeto em movimento é anexado, será uma junta de comprimento fixo.

Mas qual é a matemática / algoritmo envolvido para determinar quando e onde o segmento de linha ativo precisa ser dividido? E quando ele precisa ser associado ao segmento anterior?

(Anteriormente, essa pergunta também era feita sobre um ambiente dinâmico - decidi dividir isso em outras perguntas.)

Andrew Russell
fonte

Respostas:

18

Para determinar quando dividir a corda, você deve observar a área em que a corda cobre cada quadro. O que você faz é fazer uma verificação de colisão com a área coberta e sua geometria de nível. A área que um balanço cobre deve ser um arco. Se houver uma colisão, você precisará fazer um novo segmento na corda. Verifique se há cantos que colidem com o arco oscilante. Se houver vários cantos que colidem com o arco oscilante, escolha aquele em que o ângulo entre a corda durante o quadro anterior e o ponto de colisão seja o menor.

Diagrama útil da situação da corda ninja

A maneira como você faz a detecção de colisão é a da raiz do segmento de corda atual, O, a posição final da corda no quadro anterior, A, a posição final da corda no quadro atual, B, e cada ponto de canto P em uma poligonal geometria de nível, você calcula (OA x OP), (OP x OB) e (OA x OB), em que "x" representa a obtenção da coordenada Z do produto cruzado entre os dois vetores. Se todos os três resultados tiverem o mesmo sinal, negativo ou positivo, e o comprimento do OP for menor que o comprimento do segmento do cabo, o ponto P estará dentro da área coberta pelo balanço e você deverá dividir o cabo. Se você tiver vários pontos de canto colidindo, convém usar o primeiro que bate na corda, ou seja, aquele em que o ângulo entre OA e OP é o menor. Use o produto escalar para determinar o ângulo.

Quanto à junção de segmentos, faça uma comparação entre o segmento anterior e o arco do seu segmento atual. Se o segmento atual passou do lado esquerdo para o lado direito ou vice-versa, você deve unir os segmentos.

Para a matemática da junção de segmentos, usaremos o ponto de fixação do segmento de corda anterior, Q, bem como o que tínhamos no caso de divisão. Então agora, você deseja comparar os vetores QO, OA e OB. Se o sinal de (QO x OA) for diferente do sinal de (QO x OB), a corda passou da esquerda para a direita ou vice-versa, e você deve unir os segmentos. É claro que isso também pode acontecer se a corda girar 180 graus; portanto, se você deseja que a corda possa envolver um único ponto no espaço, em vez de uma forma poligonal, adicione um caso especial para isso.

É claro que esse método pressupõe que você esteja detectando colisão com o objeto pendurado na corda, para que ele não termine dentro da geometria do nível.

Pekuja
fonte
11
O problema dessa abordagem é que erros de precisão de ponto flutuante possibilitam que a corda "atravesse" um ponto.
Andrew Russell
16

Faz um tempo desde que joguei Worms, mas pelo que me lembro - quando a corda envolve as coisas, há apenas uma seção (reta) de corda que se move a qualquer momento. O restante da corda se torna estático

Portanto, há muito pouca física real envolvida. A seção ativa pode ser modelada como uma única mola rígida com uma massa no final

O bit interessante será a lógica para dividir / unir seções inativas do cabo de / para a seção ativa.

Eu imagino que haveria duas operações principais:

'Split' - A corda cruzou alguma coisa. Divida-o na interseção em uma seção inativa e a nova seção mais curta e ativa

'Unir' - O cabo ativo foi movido para uma posição em que a interseção mais próxima não existe mais (isso pode ser apenas um simples teste de ângulo / ponto do produto?). Voltar a juntar 2 seções, criando uma nova seção mais longa e ativa

Em uma cena construída a partir de polígonos 2D, todos os pontos de divisão devem estar em um vértice na malha de colisão. A detecção de colisão pode simplificar para algo como 'Se a corda passa por um vértice nesta atualização, divida / junte a corda nesse vértice?

bluescrn
fonte
2
Esse cara estava certo no local ... Na verdade, não evne é uma mola "dura", você só girar alguma linha reta em torno de ...
speeder
Sua resposta está tecnicamente correta. Mas eu meio que assumi que ter segmentos de linha, dividir e juntar-se a eles era óbvio. Estou interessado no algoritmo / matemática real para fazer isso. Eu fiz minha pergunta mais específica.
Andrew Russell
3

Confira como a corda ninja em Gusanos foi implementada:

  • A corda age como uma partícula até se prender a alguma coisa.
  • Uma vez presa, a corda aplica uma força ao verme.
  • Anexar a objetos dinâmicos (como outros worms) ainda é um TODO: neste código.
  • Não me lembro se há suporte para envolver objetos / cantos ...

Trecho relevante de ninjarope.cpp :


void NinjaRope::think()
{
    if ( m_length > game.options.ninja_rope_maxLength )
        m_length = game.options.ninja_rope_maxLength;

    if (!active)
        return;

    if ( justCreated && m_type->creation )
    {
        m_type->creation->run(this);
        justCreated = false;
    }

    for ( int i = 0; !deleteMe && i < m_type->repeat; ++i)
    {
        pos += spd;

        BaseVec<long> ipos(pos);

        // TODO: Try to attach to worms/objects

        Vec diff(m_worm->pos, pos);
        float curLen = diff.length();
        Vec force(diff * game.options.ninja_rope_pullForce);

        if(!game.level.getMaterial( ipos.x, ipos.y ).particle_pass)
        {
            if(!attached)
            {
                m_length = 450.f / 16.f - 1.0f;
                attached = true;
                spd.zero();
                if ( m_type->groundCollision  )
                    m_type->groundCollision->run(this);
            }
        }
        else
            attached = false;

        if(attached)
        {
            if(curLen > m_length)
            {
                m_worm->addSpeed(force / curLen);
            }
        }
        else
        {
            spd.y += m_type->gravity;

            if(curLen > m_length)
            {
                spd -= force / curLen;
            }
        }
    }
}
Leftium
fonte
11
Humm ... isso parece não responder à minha pergunta. O ponto principal da minha pergunta é enrolar uma corda em torno de um mundo feito de polígonos. Gusanos parece não ter um invólucro e um mundo de bitmap.
Andrew Russell
1

Receio não poder lhe dar um algoritmo concreto, mas me ocorre que há apenas duas coisas importantes para detectar uma colisão na corda ninja: todo e qualquer vértice potencialmente colidindo em obstáculos dentro de um raio da última "divisão" igual ao comprimento restante do segmento; e a direção atual do balanço (horário ou anti-horário). Se você criou uma lista temporária de ângulos do vértice "dividido" para cada um dos vértices próximos, seu algoritmo precisaria se preocupar se o seu segmento estava prestes a passar desse ângulo para qualquer vértice. Se for, é necessário executar uma operação de divisão, o que é fácil como torta - é apenas uma linha do último vértice da divisão até a nova divisão e, em seguida, um novo restante é calculado.

Eu acho que apenas os vértices são importantes. Se você corre o risco de atingir um segmento entre os vértices em um obstáculo, sua detecção de colisão normal para o sujeito que está pendurado no final da corda deve ser acionada. Em outras palavras, sua corda só vai "prender" cantos de qualquer maneira, para que os segmentos entre não importem.

Desculpe, não tenho nada de concreto, mas espero que isso te leve aonde você precisa estar, conceitualmente, para que isso aconteça. :)

Pi-3
fonte
1

Aqui está um post que contém links para artigos sobre tipos semelhantes de simulações (em contextos acadêmicos / de engenharia, e não em jogos): https://gamedev.stackexchange.com/a/10350/6398

Eu tentei pelo menos duas abordagens diferentes para detecção de colisão + resposta para esse tipo de simulação de "fio" (como visto no jogo Umihara Kawase); pelo menos, acho que é isso que você procura - não parece haver um termo específico para esse tipo de simulação, apenas o chamo de "fio" em vez de "corda", porque parece que a maioria das pessoas considere "corda" como sinônimo de "uma cadeia de partículas". E, se você deseja o comportamento grudento da corda ninja (ou seja, pode empurrar E puxar), isso é mais como um fio rígido do que uma corda. De qualquer forma..

A resposta de Pekuja é boa: você pode implementar a detecção contínua de colisões resolvendo o tempo em que a área assinada dos três pontos é 0.

(Não consigo me lembrar totalmente do OTOH, mas você pode abordá-lo da seguinte forma: encontre o tempo t quando o ponto a está contido na linha que passa por b, c (acho que fiz isso resolvendo quando ponto (ab, cb) = 0 para encontrar valores de t) e, em seguida, dado um tempo válido 0 <= t <1, encontre a posição paramétrica s de a no segmento bc, ou seja, a = (1-s) b + s c e se a estiver entre bec (ou seja, se 0 <= s <= 1) é uma colisão válida.

No AFAICR, você também pode abordá-lo de outra maneira (ou seja, resolver s e depois conectar isso para encontrar t), mas é muito menos intuitivo. (Desculpe se isso não faz sentido, não tenho tempo para desenterrar minhas anotações e já faz alguns anos!)

Portanto, agora você pode calcular todos os horários em que os eventos ocorrem (ou seja, nós de corda devem ser inseridos ou removidos); processe o evento mais antigo (insira ou remova um nó) e repita / recorra até que não haja mais eventos entre t = 0 e t = 1.

Um aviso sobre essa abordagem: se os objetos que a corda pode envolver são dinâmicos (especialmente se você os estiver simulando E seus efeitos na corda e vice-versa), pode haver problemas se esses objetos passarem por cada um deles. outro - o fio pode ficar embaraçado. Definitivamente, será desafiador impedir esse tipo de interação / movimento (os cantos dos objetos deslizando um pelo outro) em uma simulação física no estilo box2d. Pequenas quantidades de penetração entre objetos são comportamentos normais nesse contexto.

(Pelo menos .. este foi um problema com uma das minhas implementações de "wire".)

Uma solução diferente, que é muito mais estável, mas que perde algumas colisões em determinadas condições, é usar apenas testes estáticos (ou seja, não se preocupe em ordenar por tempo, apenas subdividir recursivamente cada segmento em colisão conforme você os encontrar), que pode ser muito mais robusto - o fio não se enrosca nos cantos e pequenas quantidades de penetração são boas.

Eu acho que a abordagem de Pekuja também funciona para isso, no entanto, existem abordagens alternativas. Uma abordagem que usei é adicionar dados de colisão auxiliar: em cada vértice convexo v do mundo (ou seja, nos cantos das formas pelas quais a corda pode envolver), adicione um ponto u formando o segmento de linha direcionada uv, onde u é aponte "dentro do canto" (ou seja, dentro do mundo, "atrás" v; para calcular u, você pode lançar um raio para dentro de v ao longo de seu normal interpolado e parar uma distância depois de v ou antes que o raio se cruze com uma extremidade do mundo e sai da região sólida ou você pode pintar manualmente os segmentos no mundo usando uma ferramenta visual / editor de níveis).

De qualquer forma, agora você tem um conjunto de "corner linesegs" uv; para cada uv e cada segmento ab na conexão, verifique se ab e uv se cruzam (ou seja, estática, consulta booleana de linhas e linhas); se for o caso, recursione (divida a linha seg ab em av e vb, ou seja, insira v), registrando em que direção o cabo dobrou em v. Em seguida, para cada par de linhas vizinhas ab, bc no fio, teste se a direção atual da curva em b é o mesmo de quando b foi gerado (todos esses testes de "direção da dobra" são apenas testes de área assinada); caso contrário, mescle os dois segmentos em ac (ou seja, remova b).

Ou talvez eu tenha me fundido e depois dividido, eu esqueço - mas definitivamente funciona em pelo menos uma das duas ordens possíveis! :)

Dado todos os segmentos de fios calculados para o quadro atual, você pode simular uma restrição de distância entre os dois pontos finais do fio (e pode até envolver os pontos internos, ou seja, os pontos de contato entre o fio e o mundo, mas isso é um pouco mais envolvido )

De qualquer forma, espero que isso tenha alguma utilidade ... os artigos no post que eu vinculei também devem lhe dar algumas idéias.

Raigan
fonte
0

Uma abordagem para isso é modelar a corda como partículas colidíveis, conectadas por molas. (bastante rígidos, possivelmente até como osso). As partículas colidem com o ambiente, certificando-se de que a corda envolve os itens.

Aqui está uma demonstração com a fonte: http://www.ewjordan.com/rgbDemo/

(Mover para a direita no primeiro nível, há uma corda vermelha com a qual você pode interagir)

Rachel Blum
fonte
2
Uh - isso é especificamente o que eu não quero (veja a pergunta).
Andrew Russell
Ah Isso não ficou claro na pergunta original. Obrigado por reservar um tempo para esclarecer isso. (Ótimo diagrama!) Eu continuaria com uma série de juntas fixas muito pequenas, em vez de fazer divisões dinâmicas - a menos que seja um grande problema de desempenho em seu ambiente, é muito mais fácil codificar.
Rachel Blum