Comment s'effectue l'évitement local RTS?

Actuellement, je simule des forces d'impact physiques pour éviter localement les unités, mais cette méthode pousse parfois les unités hors de la formation et a des effets très indésirables lorsque les unités se regroupent.

Pour les jeux RTS comme Starcraft 2, comment l'évitement local se fait-il? La physique est-elle simulée ou un contrôleur omnicient décide où tout devrait être? Je sais que cette question pourrait être un peu large, donc je demande spécifiquement comment obtenir les comportements d'évitement locaux de Starcraft 2; bien que tout ce qui fonctionne sera très apprécié.

Je ne cherche pas de code - juste des ressources utiles ou des explications sur la façon dont Starcraft 2 (ou des jeux similaires) gère l'évitement local.

Actuellement, j'ai la détection de collision (avec vecteur de pénétration), les forces de collision et le mouvement par vitesse implémentés. Chaque unité est comparée à une autre pour une collision - si elles entrent en collision, les objets sont immédiatement décalés par le vecteur de pénétration, puis la force de collision est appliquée. Ensuite, une autre boucle déplace les objets par leurs vitesses et applique un glissement aux vitesses. Le décalage atténue le problème des forces de collision excessives appliquées aux unités regroupées, mais les unités tirent parfois encore.

La solution que je recherche doit répondre aux exigences suivantes (comme dans Starcraft 2):

• Les objets ne doivent pas se chevaucher; ou au moins les chevauchements doivent être finalement résolus.
• Les objets ne s'écartent pas plus que nécessaire, donc 2 unités peuvent se tenir debout et se déplacer l'une à côté de l'autre dans une formation.
• Il ne devrait pas y avoir de comportements étranges lorsque des objets s'agglutinent vers la même destination.
• Peut supporter des unités de différentes tailles et même de différentes formes convexes.

Ce à quoi j'ai pensé jusqu'à présent, c'est au lieu de détecter les collisions, de détecter les collisions futures afin que le chevauchement ne se produise jamais. Ensuite, appliquez la contrainte, en vous assurant que les vitesses des 2 unités ne les font pas se chevaucher. Je bricole toujours l'algorithme pour restreindre le mouvement au-delà du chevauchement.

Il semble que ce que vous recherchez soit l' algorithme d' évitement de collision réciproque optimal . L' article précédent mérite également d'être lu. Bien que l'article puisse être un peu impliqué, la théorie derrière l'algorithme est assez simple:

Supposons que vous avez déjà une simulation (jeu) avec des agents (unités) qui ont une sorte de volume englobant autour d'eux. Ce volume englobant est probablement ce que vous utilisez déjà pour effectuer la détection et la réponse aux collisions. Pour chaque agent, définissez une vitesse préférée v_pqui peut ou non être basée sur l'objectif de l'agent.

Maintenant, pour effectuer la simulation:

1. Pour chaque agent, en supposant qu'il est stationnaire, calculez toutes les vitesses qui le feraient entrer en collision à tout moment dans l'avenir avec l'un des autres agents en mouvement. Cela peut être représenté dans "l'espace de vitesse" comme un ensemble de demi-plans qui se croisent (également connu sous le nom d' obstacle de vitesse ).
2. Déterminez le point dans cet espace le plus proche v_p, c'est la nouvelle vitesse de l'unité.

Si tous les agents exécutent le même algorithme, ils choisiront des vitesses qui se complètent mutuellement et éviteront d'autres agents. Dans certaines situations, vous pouvez provoquer des oscillations comme cette chose gênante qui se produit lorsque vous entrez directement dans quelqu'un dans le hall et que vous essayez toutes les deux de vous éloigner dans le même sens, mais les documents expliquent comment éviter cela.

Pour calculer les deux étapes de l'algorithme ci-dessus, vous pouvez utiliser les sommes de Minkowski pour déterminer ce qu'est l'obstacle de vitesse, puis utiliser un modèle de programmation linéaire (tel que l' algorithme Simplex ) pour déterminer le point le plus proche v_pqui évite l'obstacle de vitesse. De plus, un code pour éviter les collisions est disponible pour votre lecture et a été porté en C # pour être utilisé dans des moteurs de jeu comme Unity. Cette technique a été utilisée au moins dans Warhammer 40,000: Space Marine , et peut - être dans d'autres jeux .

Je ne sais pas comment fonctionnent vos unités mais je suppose qu'elles sont comme une machine d'état:

États possibles

• Courir jusqu'à (x, y, z)
• Attaque (ennemi_id)
• Collecte de ressource (ressource_id)

Si vous faites attention à la façon dont Starcraft aborde ce problème, vous constaterez que:

1. S'il y a de l'espace pour se déplacer dans une direction, le personnage se déplace dans cette direction.
2. S'il n'y a pas d'espace, l'unité sur le chemin se déplacera pour faire de l'espace
3. Si l'unité qui doit se déplacer pour faire de la place possède déjà une commande, elle la gardera, mais la modifiera légèrement pour finalement faire place.

Voici le scénario 1:

Ai-je de la place pour y aller? Oui ? Alors vas y

Scénario 2:

Ai-je de la place pour y aller? Non ? Hé, tu peux me faire de la place, tu me bloque. J'ai déjà un ordre d'avancer mais je vais vous accueillir.

Donc, ce dont vous aurez besoin pour mettre en œuvre:

• Les unités doivent être conscientes de leur environnement
• Les unités doivent avoir un moyen de communiquer entre elles
• Vous devez implémenter un moyen de continuer à exécuter une commande tout en hébergeant une autre unité

Une façon de le faire est de faire en sorte que les unités forment automatiquement les formations et de les faire essayer de rester dans une position par rapport au centre de la formation. . Ensuite, au lieu de déplacer chaque unité individuellement, déplacez le centre de la formation.

Voici une façon de base de le faire en utilisant une formation en forme de boîte et des ressorts simples pour maintenir les unités à leurs positions appropriées:

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

Je sais que certaines personnes désapprouvent le dumping de liens, mais j'ai trouvé une approche potentielle basée sur le champ multi-agents pour les robots de jeux de stratégie en temps réel (ISBN 978-91-7295-160-0) pour être un document très instructif, et il transmet évidemment bien plus que je ne pourrais en dire plus. L'article explore l'utilisation de champs de potentiel artificiel (un concept issu de la robotique) pour faciliter l'évitement des collisions locales dans un contexte de développement de jeux.