Bestimmen des Endorts für die KI-Bewegung in Gruppen in einem 2D-RTS

8

Ich habe ein RTS-Spiel geschrieben (eigentlich eine Demo für eine Art Spiel-Engine), in dem der Benutzer in erster Linie mit dem Spiel interagiert und dann mit der rechten Maustaste auf die Karte klickt, um sie an den angegebenen Ort zu verschieben. Dies ist in JavaScript und man kann mit ihr spielen hier ( Code ).

Ich ignoriere das Problem, wie sich die Soldaten von ihrem aktuellen Standort zu ihrem Ziel bewegen, und frage mich, wie ihr tatsächliches Ziel lautet. Folgendes habe ich bisher versucht:

  • Versuch 1: Weisen Sie alle ausgewählten Soldaten an, sich zu den Koordinaten zu bewegen, auf die die Maus geklickt hat. Dies hat das seltsame Verhalten, dass sich dann alle Soldaten unnatürlich um das Ziel sammeln.
  • Versuch 2: Ermitteln Sie die Durchschnittskoordinaten aller ausgewählten Soldaten, ermitteln Sie dann den Versatz von diesem Mittelpunkt für jeden Soldaten und übersetzen Sie diesen Versatz schließlich um die Mauskoordinaten. Dies funktioniert gut, außer dass Ihre ausgewählten Soldaten, wenn sie weit voneinander entfernt sind, nicht in die Nähe des Ziels gelangen.
  • Versuch 3: Erstellen Sie ein Raster um die Mauskoordinaten und platzieren Sie jeden ausgewählten Soldaten in einer Zelle des Rasters. Wenn jeder Soldat es in die ihm zugewiesene Zelle schafft, funktioniert dies hervorragend. Soldaten werden jedoch in der Reihenfolge, in der die Soldaten erzeugt wurden, Gitterzellen zugewiesen, sodass sie manchmal kollidieren (dh alle Soldaten auf der rechten Seite versuchen, auf die linke Seite zu gelangen), was unnatürlich aussieht.
  • Versuch 4: Verwenden Sie ein Gitter wie zuvor, aber sortieren Sie die Soldaten zuerst nach Ort, so dass sie sich sinnvoll ausrichten. Wenn Sie also unter die Gruppe geklickt haben, landen die Soldaten am unteren Rand der Gruppe am unteren Rand des Gitters ihr Ziel erreichen. Das funktioniert ziemlich gut, aber manchmal gibt es Pannen und ich bin mir nicht sicher warum.

Hier ist die Funktion, die die Zielkoordinaten bestimmt:

function moveSelectedSoldiersToMouse() {
  var w = 0, h = 0, selected = [];
  // Get information about the selected soldiers.
  myTeam.soldiers.forEach(function(soldier) {
    if (soldier.selected) {
      selected.push(soldier);
      w += soldier.width;
      h += soldier.height;
    }
  });
  var numSelected = selected.length, k = -1;
  if (!numSelected) return;
  // Build a grid of evenly spaced soldiers.
  var sqrt = Math.sqrt(numSelected),
      rows = Math.ceil(sqrt),
      cols = Math.ceil(sqrt),
      x = Mouse.Coords.worldX(),
      y = Mouse.Coords.worldY(),
      iw = Math.ceil(w / numSelected), // grid cell width
      ih = Math.ceil(h / numSelected), // grid cell height
      wg = iw*1.2, // width of gap between cells
      hg = ih*1.2; // height of gap between cells
  if ((rows-1)*cols >= numSelected) rows--;
  w = iw * cols + wg * (cols-1); // total width of group
  h = ih * rows + hg * (rows-1); // total height of group
  // Sort by location to avoid soldiers getting in each others' way.
  selected.sort(function(a, b) {
    // Round to 10's digit; specific locations can be off by a pixel or so
    var ax = a.x.round(-1), ay = a.y.round(-1), bx = b.x.round(-1), by = b.y.round(-1);
    return ay - by || ax - bx;
  });
  // Place the grid over the mouse and send soldiers there.
  for (var i = 0; i < rows; i++) {
    for (var j = 0; j < cols; j++) {
      var s = selected[++k];
      if (s) {
        var mx = x + j * (iw+wg) - w * 0.5 + s.width * 0.5,
            my = y + i * (ih+hg) - h * 0.5 + s.height * 0.5;
        // Finally, move to the end destination coordinates
        s.moveTo(mx, my);
      }
    }
  }
}

Sie können diese Funktion in die JavaScript-Konsole Ihres Browsers einfügen, wenn Sie die Demo anzeigen, und damit herumspielen, um das Verhalten der Soldaten zu ändern.

Meine Frage ist: Gibt es eine bessere Möglichkeit, den Zielort für jeden Soldaten zu bestimmen?

IceCreamYou
quelle
Etwas, das als "Beflockung" bezeichnet wird, kann für Sie sehr nützlich sein und Ihnen die Art von Funktionalität bieten, nach der Sie suchen. Versuchen Sie: process.org/examples/flocking.html oder googeln Sie einfach "flocking" oder "Boids". Das könnte Sie in die richtige Richtung bringen.
Dean Knight
2
Siehe auch: gamedev.stackexchange.com/questions/44361 Ich würde sagen, dass die "Pannen", die Sie erleben, von Einheiten stammen, die versuchen, sich in eine Position zu bewegen, die bereits beansprucht wurde. Stellen Sie sicher, dass die Position, in die sie sich bewegen, nicht bereits das Ziel einer anderen Einheit ist, und Sie sollten ziemlich gute Ergebnisse erzielen.
MichaelHouse
@ DeanKnight, ich bin mir bewusst, wie Flockverhalten funktioniert, aber das regelt, wie die Bots von Punkt A nach Punkt B gelangen, nicht was Punkt B ist.
IceCreamYou
@ Byte56: danke für den Link. Ich setze Einheiten nicht buchstäblich in Raster-Slots ein - in der Implementierung gibt es keine Möglichkeit, mehrere Einheiten an denselben Punkt zu lenken. Das Problem scheint eher darin zu liegen, dass die Sortierung manchmal verwirrt wird.
IceCreamYou
1
Eine andere Idee: Swarm Pathfinding . In diesem Fall würden Sie nicht jeder Einheit einen anderen Endpunkt geben. Sie würden sie einfach anhalten lassen, wenn kein Pfad mehr zum Endpunkt vorhanden war (weil alle anderen Einheiten im Weg sind), oder Sie würden überhaupt nicht anhalten und die Kollisionserkennung ihre Aufgabe erledigen lassen.
BlueRaja - Danny Pflughoeft

Antworten:

2

Hier sind meine Vorschläge zu Ihren Ideen:

Versuch 1: Um diese Situation zu beheben, könnten Sie die von Spencer angesprochene Idee "nah genug" umsetzen. Ich würde so etwas wie eine Blase um den Endpunkt ziehen, die basierend auf einem Verhältnis der Anzahl und Größe der bereits darin enthaltenen Einheiten wächst. Angenommen, die Blase hat die Größe einer Einheit. Wenn die erste dort ankommt, verdoppelt sich der Radius für die nächsten zwei Einheiten usw.

Versuch 2: Eine Lösung für dieses Problem wäre, den durchschnittlichen Abstand der Gruppe voneinander zu nehmen und dann den Abstand der Ausreißer zu diesem zu verringern, sodass die Gruppe mehr Bündel aufweist als ursprünglich (die Metrik könnte kürzer sein /). länger als der Durchschnitt, was auch immer es anständig aussehen lässt oder möglicherweise eine maximale Formgröße basierend auf der Anzahl / Größe der Truppen wieder festlegt) Das einzige, worüber Sie sich Sorgen machen müssen, ist, wenn Sie den Pfad eines Ausreißers ändern, Sie ' Ich muss überprüfen und sicherstellen, dass die anderen Pfade nicht beeinträchtigt werden

Versuch 3: Sie haben diesen in Versuch 4 verbessert

Versuch 4: Klingt so, als würde dieser gut funktionieren, wenn Sie feststellen, welche Pannen ihn abwerfen. Ich würde jedoch empfehlen, mit anderen Spahes als nur einer Gitterformation zu spielen, um die Bewegung ein bisschen natürlicher aussehen zu lassen, es sei denn, Sie streben einen realistischen / militärischen Stil an. In diesem Fall könnte es ordentlich sein, sie "bilden" zu lassen "vor dem Umzug, aber das könnte den Spieler nach einer Weile nerven.

Versuch 4 scheint dem Entfernen des Fräsverhaltens in Ihrem Problem am nächsten zu kommen, aber im Hinblick darauf, die Bewegung ohne andere als die erforderlichen Einstellungen fließen zu lassen, wäre mein Favorit wahrscheinlich Versuch 2.

Als völlig andere Lösung können Sie jedoch zwei Arten von Objekten verwenden, wenn es um die Pfadfindung geht. jede Einheit sowie ein unsichtbares "Squad" -Objekt.

Squad - Sie erstellen das Squad-Objekt wie die anderen Lösungen in der Mitte der Gruppe und richten es mithilfe Ihrer Pfadfindung auf das Ziel.

Einheiten - Die Einheiten ignorieren das Ziel vollständig und verwenden stattdessen die Pfadfindung, um einen bestimmten Abstand (oder eine Formation oder eine andere Metrik, die die Bewegung am besten aussehen lässt) zum Gruppenobjekt einzuhalten.

Dies trennt die verschiedenen Aspekte der Pfadfindung und ermöglicht es Ihnen, beide Seiten isoliert zu optimieren, um mehr Kontrolle über das Aussehen zu erhalten.

David M.
quelle
Gute Antwort. Danke für die neuen Ideen. Der Squad + Unit-Ansatz ist interessant und erfordert wahrscheinlich, dass sich Einheiten im "
Aufhol
Ja, eine Lösung besteht darin, die Bewegungsgeschwindigkeit des "Squad" -Objekts auf etwas unter dem Maximum einzustellen, das die einzelnen Einheiten bewegen können, damit sie sich bei Bedarf verschieben können, ohne zurückzufallen.
David M
2

Versuch 3 könnte funktionieren, muss aber etwas verfeinert werden.

Denken Sie über das Konzept einer Formation nach (Ihr Gitter ist ein Anfang). Eine Formation sollte einen Ort (dh die Klickkoordinaten oder den Zielsoldaten / das Zielgebäude) und eine Rotation haben (dies kann fest, zufällig oder deterministisch sein). Die Formation muss die gleiche Anzahl von Positionen haben wie die Anzahl der ausgewählten Soldaten.

Eine einfache Beispielformation kann ein Kreis um das Ziel sein. Platzieren Sie den Raum gleichmäßig und vergrößern Sie den Kreisradius, damit alle Soldaten ohne Kollision passen.

Das nächste Problem besteht darin, zu entscheiden, welcher Soldat zu welcher Position in der Formation geht. Eine einfache Lösung könnte darin bestehen, jeden Soldaten an die Position zu bringen, die ihm am nächsten liegt. Wenn dieser bereits von einem anderen Soldaten "ausgewählt" wurde, nehmen Sie die nächstgelegene Position usw. ein.

Formationen können sehr interessant werden. Unten sehen Sie ein Bild der 'Bullenhornformation', die Shaka der Zulu mit großem Erfolg verwendet hat . (Das Bild stammt aus dem TotalWar Formation Mod )

Bullenhornformation

Willem
quelle
"Das nächste Problem ist zu entscheiden, welcher Soldat zu welcher Position in der Formation geht." Eigentlich ist das das ganze Problem dieser Frage. :) Upvoted für den Vorschlag einer Kreisbildung anstelle eines Gitters, aber das ist für mehr als ein paar Soldaten unwirksam, und das Bewegen von Soldaten an den ihnen am nächsten gelegenen Ort verursacht mehr Konflikte als meine obige Lösung, die Einheiten nach Ort zu sortieren.
IceCreamYou
0

Zeichnen Sie beim Klicken des Benutzers von jedem Soldaten einen Vektor an die angeklickte Stelle. Ermitteln Sie den durchschnittlichen Vektorwinkel aus den für jeden Soldaten gezeichneten Vektoren und bewegen Sie jeden Soldaten mit demselben Winkel um die Länge seines einzelnen Vektors in diese Richtung. Dies sollte das Aussehen der Einheiten geben, die sich in Formation auf den Punkt bewegen, und sollte verhindern, dass sich die Einheiten verklumpen.

Wenn Sie möchten, dass sich die Einheiten aus der Formation bewegen, können Sie den Winkel jedes Soldaten direkt auf die angeklickte Stelle richten. Ohne Kollision beginnen die Einheiten jedoch zu konvergieren. Um dem entgegenzuwirken, fügen Sie eine Kollision hinzu und zwingen Sie die Einheiten, sich nicht mehr zu bewegen, sobald sie "nah genug" an dem angeklickten Punkt sind. Die ersten Einheiten, die ankommen, sind genau auf dem Punkt und die letzten, die ankommen, sollten angewiesen werden, sich nicht mehr zu bewegen, sobald sie entweder nahe genug sind oder eine bestimmte Zeit verstrichen ist.

Sie können die Länge des Pfades und die Geschwindigkeit der Einheit berechnen, um zu bestimmen, wann eine einzelne Einheit ankommen soll, und dann die Einheit zwingen, sich nicht mehr zu bewegen, wenn sie diese Zeit um einen bestimmten Betrag überschreitet. Sie müssen ein wenig mit dieser Nummer spielen.

Spencer
quelle
Die von Ihnen vorgeschlagene Vektorlösung ist dieselbe wie mein Versuch 2 oben. Eine der Anforderungen dieser Frage ist, dass ausgewählte Einheiten möglicherweise nicht in einer Formation sind.
IceCreamYou
Und ich schrieb über eine Lösung, bei der sie sich nicht in Formation bewegen würden. (2. Absatz)
Spencer