Implémentation d'un fil de banderolage (comme la corde Worms Ninja Rope) dans un moteur physique 2D

34

J'ai récemment essayé la physique des cordes et j'ai découvert que la solution "standard" - fabriquer une corde à partir d'une série d'objets attachés avec des ressorts ou des articulations - n'était pas satisfaisante. Surtout lorsque le balancement de la corde est pertinent pour le jeu. Je ne m'inquiète pas vraiment de la capacité d'une corde à s'enrouler ou à s'affaisser (cela peut être simulé pour des effets visuels).

Pour le jeu, l’important est la capacité de la corde à s’enrouler dans l’environnement puis à se dérouler par la suite. Il ne doit même pas se comporter comme une corde - un "fil" composé de segments de droite ferait l'affaire. Voici une illustration:

Corde Ninja, entourant les obstacles

Ceci est très similaire à la "corde Ninja" du jeu Worms.

Comme j'utilise un moteur physique 2D, mon environnement est constitué de polygones convexes 2D. (Plus précisément, j'utilise SAT dans Farseer.)

Ma question est donc la suivante: comment implémenteriez-vous l’effet "wrapping"?

Il semble assez évident que le fil sera constitué d’une série de segments de ligne qui se "scindent" et "se joignent". Et le dernier segment (actif) de cette ligne, où l'objet en mouvement se fixe, sera un joint de longueur fixe.

Mais quels sont les calculs / algorithmes utilisés pour déterminer quand et où le segment de ligne actif doit être fractionné? Et quand doit-il être rejoint avec le segment précédent?

(Auparavant, cette question concernait également le fait de procéder de la sorte dans un environnement dynamique - j'ai décidé de scinder cette question en d'autres questions.)

Andrew Russell
la source

Réponses:

18

Pour déterminer quand diviser la corde, vous devez regarder la zone que la corde recouvre chaque cadre. Ce que vous faites est de faire une vérification de collision avec la zone couverte et votre géométrie de niveau. La zone couverte par une balançoire devrait être un arc. En cas de collision, vous devez créer un nouveau segment sur la corde. Vérifiez les coins qui entrent en collision avec l'arc oscillant. Si plusieurs angles entrent en collision avec l'arc de swing, vous devez choisir celui où l'angle entre la corde au cours de la trame précédente et le point de collision est le plus petit.

Schéma utile de la situation de la corde ninja

La détection de collision s'effectue de la manière suivante pour la racine du segment de corde actuel, O, la position finale de la corde sur la trame précédente, A, la position finale de la corde sur la trame actuelle, B, et chaque coin P dans une zone polygonale. niveau géométrie, vous calculez (OA x OP), (OP x OB) et (OA x OB), où "x" représente la coordonnée Z du produit croisé entre les deux vecteurs. Si les trois résultats ont le même signe, négatif ou positif, et que la longueur de OP est inférieure à la longueur du segment de corde, le point P se situe dans la zone couverte par la balançoire et vous devez séparer la corde. Si vous avez plusieurs angles en collision, utilisez le premier point qui heurte la corde, c’est-à-dire celui où l’angle entre OA et OP est le plus petit. Utilisez le produit scalaire pour déterminer l'angle.

Pour ce qui est de joindre des segments, faites une comparaison entre le segment précédent et l’arc de votre segment actuel. Si le segment en cours a basculé de gauche à droite ou inversement, vous devez joindre les segments.

Pour le calcul mathématique de la jonction de segments, nous utiliserons le point de fixation du segment de câble précédent, Q, ainsi que ceux que nous avions pour le cas de fractionnement. Alors maintenant, vous voudrez comparer les vecteurs QO, OA et OB. Si le signe de (QO x OA) est différent du signe de (QO x OB), la corde s'est croisée de gauche à droite ou inversement et vous devez joindre les segments. Bien sûr, cela peut également arriver si la corde pivote à 180 degrés. Si vous voulez que la corde puisse envelopper un seul point dans l’espace au lieu d’une forme polygonale, vous pouvez ajouter un cas spécial pour cela.

Bien sûr, cette méthode suppose que vous effectuez une détection de collision pour l’objet suspendu à la corde, de sorte qu’il ne se retrouve pas dans la géométrie de niveau.

Pekuja
la source
1
Le problème avec cette approche est que les erreurs de précision en virgule flottante permettent au câble de passer "à travers" un point.
Andrew Russell
16

Cela fait longtemps que je n’ai pas joué à Worms, mais si je me souviens bien, lorsque la corde s'enroule autour de lui, il n’ya qu’une section de corde (droite) en mouvement à la fois. Le reste de la corde devient statique

Donc, il y a très peu de physique réelle impliquée. La section active peut être modélisée comme un seul ressort rigide avec une masse à l'extrémité

Le bit intéressant sera la logique pour séparer / joindre des sections inactives de la corde à / de la section active.

J'imagine qu'il y aurait 2 opérations principales:

'Split' - La corde a coupé quelque chose. Divisez-le à l'intersection en une section inactive et la nouvelle section active plus courte

«Rejoindre» - La corde active s'est déplacée dans une position où l'intersection la plus proche n'existe plus (il peut s'agir simplement d'un simple test de produit angle / point?). Rejoin 2 sections, créant une nouvelle section plus longue et active

Dans une scène construite à partir de polygones 2D, tous les points de partage doivent se situer à un sommet du maillage de collision. La détection de collision peut simplifier les choses: «Si la corde passe au-dessus d'un sommet lors de cette mise à jour, divisez / joignez la corde à ce sommet?

bluescrn
la source
2
Ce mec était juste sur place ... En fait, ce n'est pas toujours un ressort "raide", vous faites seulement pivoter une ligne droite autour de vous ...
speeder
Votre réponse est techniquement correcte. Mais j'ai en quelque sorte supposé qu'avoir des segments de ligne, des séparer et les joindre était évident. Je suis intéressé par l'algorithme / maths pour le faire. J'ai rendu ma question plus précise.
Andrew Russell
3

Découvrez comment la corde de ninja à Gusanos a été mise en œuvre:

  • La corde agit comme une particule jusqu'à ce qu'elle s'attache à quelque chose.
  • Une fois attaché, la corde applique simplement une force sur le ver.
  • L'attachement à des objets dynamiques (comme d'autres vers) reste un TODO: dans ce code.
  • Je ne me souviens pas si l'encapsulation autour des objets / coins est prise en charge ...

Extrait pertinent 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
la source
1
Uhmn ... cela ne semble pas répondre à ma question du tout. Le but de ma question est d’enrouler une corde autour d’un monde composé de polygones. Gusanos semble n'avoir aucun emballage et un monde bitmap.
Andrew Russell
1

Je crains de ne pas pouvoir vous donner un algorithme concret, mais je me rends compte qu'il n'y a que deux choses qui importent pour détecter une collision avec la corde ninja: tous les sommets potentiellement en collision sur des obstacles. dans un rayon de la dernière "division" égal à la longueur restante du segment; et le sens de rotation actuel (dans le sens des aiguilles d'une montre ou dans le sens inverse). Si vous avez créé une liste temporaire d'angles du sommet "divisé" vers chacun des sommets voisins, votre algorithme doit simplement se soucier de savoir si votre segment est sur le point de dépasser cet angle pour un sommet donné. Si c'est le cas, vous devez effectuer une opération de division, ce qui est simple comme bonjour. Il s'agit simplement d'une ligne allant du dernier sommet fractionné à la nouvelle division, puis un nouveau reste est calculé.

Je pense que seuls les sommets comptent. Si vous êtes sur le point de frapper un segment entre des sommets sur un obstacle, alors votre détection de collision normale pour le gars accroché au bout de la corde devrait se déclencher. En d'autres termes, votre corde ne va jamais "accrocher" coins de toute façon, donc les segments entre peu importe.

Désolé, je n'ai rien de concret, mais j'espère que cela vous mènera là où vous devez être, conceptuellement, pour que cela se produise. :)

Pi-3
la source
1

Voici un article qui contient des liens vers des articles sur des types de simulations similaires (dans des contextes d'ingénierie / universitaires plutôt que pour des jeux): https://gamedev.stackexchange.com/a/10350/6398

J'ai essayé au moins deux approches différentes de détection de collision + réponse pour ce type de simulation "en fil" (comme dans le jeu Umihara Kawase); du moins, je pense que c'est ce que vous recherchez - il ne semble pas exister de terme spécifique pour ce type de simulation, j'ai plutôt tendance à l'appeler "fil" plutôt que "corde" car il semble que la plupart des gens Considérons que "corde" est synonyme de "chaîne de particules". Et, si vous voulez le comportement insaisissable de la corde ninja (c’est-à-dire qu’elle peut pousser ET tirer), il s’agit plus d’un fil rigide que d’une corde. En tous cas..

La réponse de Pekuja est bonne, vous pouvez implémenter la détection de collision continue en résolvant le moment où la zone signée des trois points est 0.

(Je ne peux pas me rappeler complètement OTOH mais vous pouvez l’approcher comme suit: trouvez le temps t où le point a est contenu dans la ligne passant par b, c, (je pense que j’ai fait cela en résolvant pour quand dot (ab, cb) = 0 pour trouver les valeurs de t), puis avec un temps valide 0 <= t <1, trouve la position paramétrique s de a sur le segment bc, c'est-à-dire a = (1-s) b + s c et si a est compris entre b et c (c'est-à-dire si 0 <= s <= 1) c'est une collision valide.

AFAICR, vous pouvez aussi l’approcher dans l’inverse (c’est-à-dire résoudre le problème et ensuite le brancher pour le trouver), mais c’est beaucoup moins intuitif. (Je suis désolé si cela n’a aucun sens, je n’ai pas le temps de fouiller dans mes notes et cela fait quelques années!)

Ainsi, vous pouvez maintenant calculer toutes les heures auxquelles des événements se produisent (par exemple, les nœuds de corde doivent être insérés ou supprimés); traiter l'événement le plus ancien (insérer ou supprimer un nœud), puis répéter / recurse jusqu'à ce qu'il n'y ait plus d'événements entre t = 0 et t = 1.

Un avertissement à propos de cette approche: si les objets que la corde peut enrouler sont dynamiques (surtout si vous les simulez ET leurs effets sur la corde, et inversement), il peut y avoir des problèmes si ces objets se coupent ou passent entre eux. autre - le fil peut devenir emmêlé. Et il sera certainement difficile d’empêcher ce type d’interaction / mouvement (les coins d’objets se glissant les uns dans les autres) dans une simulation physique de style box2d. Dans ce contexte, une faible pénétration entre les objets constitue un comportement normal.

(Du moins .. c'était un problème avec l'une de mes implémentations de "wire".)

Une solution différente, beaucoup plus stable mais qui omet certaines collisions dans certaines conditions, consiste simplement à utiliser des tests statiques (c’est-à-dire, ne vous préoccupez pas de la chronologie, divisez simplement chaque segment en collision au fur et à mesure que vous les trouvez), ce qui peut être beaucoup plus robuste - le fil ne s'emmêlera pas dans les coins et une petite pénétration suffira.

Je pense que l'approche de Pekuja fonctionne pour cela aussi, cependant il existe des approches alternatives. Une approche que j’ai utilisée consiste à ajouter des données de collision auxiliaires: à chaque sommet convexe v du monde (c.-à-d. Les coins des formes que la corde peut enrouler), ajoutez un point u formant le segment de droite dirigé uv, où u est un pointez "dans le coin" (c'est-à-dire dans le monde, "derrière" v; pour calculer u, vous pouvez projeter un rayon vers l'intérieur à partir de v le long de sa normale interpolée et vous arrêter quelque part après v ou avant que le rayon ne se croise avec une arête du monde et quitte la région solide ou vous pouvez simplement peindre manuellement les segments dans le monde à l’aide d’un éditeur / outil visuel).

Quoi qu'il en soit, vous avez maintenant un ensemble de "linesegs de coin" uv; pour chaque uv et chaque segment ab du fil, vérifiez si les intersections ab et uv (par exemple, une requête d'intersection linéaire, booléenne lineseg-lineseg); si c'est le cas, recurse (divise le lineseg ab en av et vb, c.-à-d. insère v), en enregistrant dans quelle direction la corde est courbée en v. est le même que lorsque b a été généré (tous ces tests de "direction de pliage" ne sont que des tests de zone signée); sinon, fusionnez les deux segments en un courant alternatif (c.-à-d. supprimez b).

Ou peut-être que j'ai fusionné et que je me suis séparé, j'oublie - mais cela fonctionne définitivement dans au moins un des deux ordres possibles! :)

Avec tous les segments de fil calculés pour le cadre actuel, vous pouvez alors simuler une contrainte de distance entre les deux extrémités du fil (et vous pouvez même impliquer les points intérieurs, c'est-à-dire les points de contact entre le fil et le monde, mais c'est un peu plus compliqué. )

Quoi qu'il en soit, j'espère que cela vous sera utile ... les articles de l'article que je vous ai lié devraient également vous donner quelques idées.

raigan
la source
0

Une approche consiste à modéliser la corde en particules collables, reliées par des ressorts. (assez raides, peut-être même comme un os à la place). Les particules entrent en collision avec l'environnement, s'assurant que la corde s'enroule autour des objets.

Voici une démo avec source: http://www.ewjordan.com/rgbDemo/

(Déplacez-vous vers la droite au premier niveau, il y a une corde rouge avec laquelle vous pouvez interagir)

Rachel Blum
la source
2
Euh - c'est précisément ce que je ne veux pas (voir la question).
Andrew Russell
Ah Ce n'était pas clair de la question initiale. Merci d'avoir pris le temps de le clarifier autant. (Grand diagramme!) J'utiliserais quand même une série de très petites articulations fixes, par opposition à la division dynamique - à moins que ce ne soit un problème de performances énorme dans votre environnement, il est beaucoup plus facile de coder.
Rachel Blum