Wie wird RTS Local Avoidance durchgeführt?

15

Momentan simuliere ich physikalische Aufprallkräfte, um Einheiten lokal zu meiden, aber diese Methode drückt Einheiten manchmal aus der Formation und hat sehr unerwünschte Auswirkungen, wenn sich Einheiten zusammenballen.

Wie erfolgt die lokale Vermeidung bei RTS-Spielen wie Starcraft 2? Wird Physik simuliert oder entscheidet ein leistungsfähiger Controller, wo alles sein soll? Ich weiß, dass diese Frage ein wenig weit gefasst sein könnte, daher frage ich mich speziell, wie das lokale Vermeidungsverhalten von Starcraft 2 erreicht werden kann. obwohl alles, was funktioniert, sehr geschätzt wird.

Ich suche keinen Code - nur nützliche Ressourcen oder Erklärungen, wie Starcraft 2 (oder ähnliche Spiele) mit lokaler Vermeidung umgeht.

Derzeit habe ich Kollisionserkennung (mit Penetrationsvektor), Kollisionskräfte und Bewegung durch Geschwindigkeit implementiert. Jede Einheit wird auf Kollision gegen eine andere geprüft - wenn sie kollidiert, werden die Objekte sofort um den Eindringvektor versetzt, und die Kollisionskraft wird angewendet. Dann bewegt eine weitere Schleife die Objekte um ihre Geschwindigkeiten und wendet Drag auf die Geschwindigkeiten an. Der Versatz mindert das Problem übermäßiger Kollisionskräfte, die auf verklumpte Einheiten einwirken, aber die Einheiten schießen manchmal immer noch aus.

Die von mir gesuchte Lösung muss die folgenden Anforderungen erfüllen (wie in Starcraft 2):

  • Objekte dürfen sich nicht überlappen. oder zumindest Überlappungen müssen eventuell behoben werden.
  • Objekte schieben sich nicht mehr als nötig voneinander weg, damit 2 Einheiten in einer Formation nebeneinander stehen und sich bewegen können.
  • Es sollte keine seltsamen Verhaltensweisen geben, wenn sich Objekte in Richtung des gleichen Ziels zusammenballen.
  • Unterstützt Einheiten unterschiedlicher Größe und sogar unterschiedlicher konvexer Formen.

Bisher habe ich mir überlegt, nicht nach Kollisionen zu suchen, sondern nach zukünftigen Kollisionen zu suchen, damit die Überlappung nie auftritt. Wenden Sie dann die Beschränkung an und achten Sie darauf, dass sich die Geschwindigkeiten der beiden Einheiten nicht überlappen. Ich bastele immer noch an dem Algorithmus, um die Bewegung über die Überlappung hinaus einzuschränken.

JPtheK9
quelle
"Flockverhalten" (google term) ist ein sehr weitreichendes Problem,
Ratschenfreak
Dies wurde in der Warteschlange für enge Abstimmungen als "zu breit" eingestuft. Ich bin geneigt, dem zuzustimmen. Versuch einzugrenzen: Was hast du versucht? Welche "unerwünschten Wirkungen" möchten Sie vermeiden? Habe ich Recht, wenn Sie sagen, dass Einheiten in der Formation bleiben sollen?
Anko,
RTS-Spiele werden häufig von jedem Client ausgeführt, der auf jedem Computer dieselbe deterministische Simulation ausführt. Wenn Sie es also für einen einzelnen Computer lösen können, können Sie dieselbe Lösung auf die Mehrspielersituationen anwenden, unabhängig davon, mit welcher lokalen Vermeidungstechnik Sie am Ende arbeiten.
Alan Wolfe
Vielen Dank für das Feedback zu der Frage. Ich habe die Frage etwas eingegrenzt und erklärt, was ich erreichen möchte.
JPtheK9
Dies ist eine großartige Ressource: red3d.com/cwr/steer
tbkn23

Antworten:

10

Offenbar suchen Sie nach dem Algorithmus zur optimalen Vermeidung gegenseitiger Kollisionen . Das vorstehende Papier ist ebenfalls eine Lektüre wert. Obwohl die Arbeit möglicherweise etwas kompliziert ist, ist die Theorie hinter dem Algorithmus ziemlich einfach:

Angenommen, Sie haben bereits eine Simulation (ein Spiel) mit Agenten (Einheiten), die ein gewisses Begrenzungsvolumen aufweisen. Dieses Begrenzungsvolumen wird wahrscheinlich bereits verwendet, um die Kollisionserkennung und -reaktion durchzuführen. Definieren Sie für jeden Agenten eine bevorzugte Geschwindigkeit v_p, die auf dem Ziel des Agenten basieren kann oder nicht.

Um nun die Simulation durchzuführen:

  1. Berechnen Sie für jeden Agenten unter der Annahme, dass er stationär ist, alle Geschwindigkeiten, die dazu führen würden, dass er zu einem späteren Zeitpunkt mit einem der anderen sich bewegenden Agenten kollidiert. Dies kann im "Geschwindigkeitsraum" als ein Satz von sich schneidenden Halbebenen (auch als Geschwindigkeitshindernis bekannt ) dargestellt werden.
  2. Bestimmen Sie den Punkt in diesem Raum, der am nächsten v_pist. Dies ist die neue Geschwindigkeit der Einheit.

Wenn alle Agenten denselben Algorithmus ausführen, wählen sie Geschwindigkeiten aus, die sich gegenseitig ergänzen, und vermeiden andere Agenten. In manchen Situationen kann es zu solchen unangenehmen Schwingungen kommen, wenn Sie direkt in eine Person in der Halle treten und beide versuchen, sich in die gleiche Richtung aus dem Weg zu räumen.

Zum Berechnen der beiden Stufen des obigen Algorithmus können Sie Minkowski-Summen verwenden, um das Geschwindigkeitshindernis zu bestimmen, und dann ein lineares Programmiermodell (wie den Simplex-Algorithmus ) verwenden, um den nächstgelegenen Punkt zu bestimmen v_p, der das Geschwindigkeitshindernis umgeht. Außerdem steht Ihnen ein Code zur Kollisionsvermeidung zur Verfügung, der zur Verwendung in Spiele-Engines wie Unity nach C # portiert wurde. Diese Technik wurde mindestens in Warhammer 40.000: Space Marine und vielleicht auch in anderen Spielen verwendet .

Mokosha
quelle
Das war ein erstaunlicher Artikel und ich habe das Gefühl, dass ich die Hälfte davon aus Ihrer Erklärung gelesen habe. Danke für diese Information.
JPtheK9
0

Ich weiß nicht, wie Ihre Einheiten funktionieren, aber ich gehe davon aus, dass sie wie eine Zustandsmaschine sind:

Mögliche Zustände

  • Laufen zu (x, y, z)
  • Attaking (enemy_id)
  • Ressource sammeln (ressource_id)

Wenn Sie darauf achten, wie Starcraft dieses Problem angeht, werden Sie feststellen, dass:

  1. Wenn es Raum gibt, sich in eine Richtung zu bewegen, bewegt sich der Charakter in diese Richtung.
  2. Wenn kein Platz vorhanden ist, bewegt sich die Einheit im Weg, um Platz zu schaffen
  3. Wenn die Einheit, die sich bewegen muss, um Platz zu schaffen, bereits einen Befehl hat, behält sie diesen Befehl bei, ändert ihn jedoch geringfügig, um Platz zu schaffen.

Hier Szenario 1:

Bildbeschreibung hier eingeben

Habe ich dort Platz? Ja ? Dann geh

Szenario 2:

Bildbeschreibung hier eingeben

Habe ich Platz, um dorthin zu gehen? Nein ? Hey, kannst du etwas Platz für mich schaffen, du blockierst mich? Ich habe bereits einen Befehl, mich vorwärts zu bewegen, aber ich werde Sie empfangen.

Also, was müssen Sie implementieren:

  • Einheiten müssen sich ihrer Umgebung bewusst sein
  • Einheiten müssen eine Möglichkeit haben, miteinander zu kommunizieren
  • Sie müssen eine Möglichkeit implementieren, um einen Befehl weiterhin auszuführen, während Sie eine andere Einheit steuern
Antoine
quelle
Danke für die Info und Visualisierung. Im Moment nutze ich die Kollisionserkennung, um herauszufinden, ob sich eine Einheit an einen anderen Ort bewegen kann oder ob sie von einer anderen Einheit besetzt wird. Die Hauptsache, die ich herauszufinden versuche, ist ein Algorithmus, der der anderen Einheit mitteilt, um welche Entfernung sie sich bewegen oder mit welcher Geschwindigkeit sie sich einstellen soll. Mit anderen Worten, wie die Blockiereinheit die Einheit aufnehmen wird, die versucht zu passieren.
JPtheK9
Da dieses Verhalten bei jeder Aktualisierung der Physik berechnet wird, müssen Sie die Entfernung nicht wirklich angeben, sie bewegt sich so lange, bis sie nicht mehr im Weg ist. Für die Richtung scannen Sie einfach multiplizieren Sie die Geschwindigkeit der beiden Einheiten, dies gibt Ihnen den Punkt auf halber Strecke, so dass es in Bewegung bleibt, während Sie sich anpassen. Danach können Sie damit herumspielen, damit es mehr in der Reihenfolge bleibt oder schneller aus dem Weg geht.
Antoine
Was meinst du mit "bewegt sich, bis es aus dem Weg ist"? Wie bewegt sich die Einheit überhaupt?
JPtheK9
Entschuldigung, ich habe vergessen zu erwähnen: Einheiten sind keine Zustandsautomaten. Sie haben viele Fähigkeiten in ihrem Schließfach, die in jedem Frame simuliert werden - mit der Ausnahme, dass diese Fähigkeiten nur dann wirksam sind, wenn sie aktiviert sind, wenn das Ziel in X-Entfernung ist oder wenn ein Ziel existiert. Die Bewegung einer Einheit ist das Ergebnis ihrer Geschwindigkeit, die durch eine Fähigkeit geändert werden kann.
JPtheK9
0

Eine Möglichkeit, dies zu tun, besteht darin, die Einheiten automatisch Formationen bilden zu lassen und zu versuchen, in einer Position relativ zur Mitte der Formation zu bleiben . Anstatt jede Einheit einzeln zu bewegen, bewegen Sie die Mitte der Formation.

Hier ist eine grundlegende Methode, um die Einheiten in der richtigen Position zu halten:

// 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
quelle
Vielen Dank! Dies ist eine wirklich interessante und kreative Lösung. Ich habe etwas Ähnliches für Crowd-Verhalten / Formationen implementiert, aber ich habe immer noch das Problem, dass sich Einheiten überlappen. Was soll passieren, wenn 2 Formationen aufeinander treffen?
JPtheK9
Ich denke es kommt auf das Design an. Am einfachsten wäre es, in anderen Formationen wie in diesem Bild eine andere Lenkkraft von Einheiten in der Nähe weg anzuwenden . Sie können Formationen auch zusammenführen, wenn der Spieler sie auswählt, oder sogar "Meta-Formationen" bilden
mklingen
Meta-Formationen klingen wirklich kompliziert und fehlerhaft: C. Das Bild, das Sie verlinkt haben, könnte genau das sein, was ich brauche. Ich werde etwas mehr über das Wegsteuern von Kräften forschen. Haben Sie den Link zum Artikel des Bildes?
JPtheK9
Ich habe ein ähnliches Problem wie Sie, wäre interessant zu wissen, wie Sie es gelöst haben. Nach dem Lesen dieses Artikels fiel mir ein Gedanke ein: Vielleicht kombinieren Sie Pathfinding (A *) für eine Makropfadplanung, während Sie die Reppel-Kraft für die Vermeidung von
Mikrokollisionen verwenden
0

Ich kenne einige Leute, die Link-Dumping nicht mögen, aber ich fand, dass ein potenzieller feldbasierter Ansatz für Echtzeit-Strategiespiel-Bots (ISBN 978-91-7295-160-0) ein sehr aufschlussreiches Papier ist und es offensichtlich vermittelt viel mehr, als ich ausarbeiten konnte. Die Arbeit untersucht künstliche Potentialfelder (ein Konzept, das aus der Robotik stammt), um die lokale Kollisionsvermeidung im Kontext der Spieleentwicklung zu erleichtern.

DanoThom
quelle
Vielen Dank! Recherchen sind für mich genauso hilfreich wie Erklärungen. Ich werde in dieses Papier eintauchen.
JPtheK9
Ich habe bereits eine Influence-Map eingerichtet, aber dies scheint für meinen Geschmack zu kompliziert zu sein. Die Hauptsache ist, potenzielle Felder für verschiedene Einheiten zu erzeugen, um sie zu bewegen, und auch Daten aus dem potenziellen Feld in eine Geschwindigkeit umzuwandeln, mit der sie sich bewegen können. Grundsätzlich glaube ich nicht, dass dies für Einheiten unterschiedlicher Größe funktionieren würde. Es ist eine großartige Lektüre mit vielen interessanten Ideen.
JPtheK9