Share
Eine anständige NPC-Navigation erfordert häufig die Fähigkeit, Hindernisse zu umgehen. Dieses Tutorial behandelt die Kollisionsvermeidung Lenkverhalten, mit dem Charaktere beliebig viele Hindernisse in der Umgebung ausweichen können.
Hinweis: Obwohl dieses Tutorial mit AS3 und Flash geschrieben wurde, sollten Sie in der Lage sein, in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte anzuwenden. Sie müssen ein grundlegendes Verständnis von mathematischen Vektoren haben.
Die Grundidee hinter der Vermeidung von Kollisionen ist die Erzeugung einer Lenkkraft, um Hindernissen auszuweichen, sobald sich ein Hindernis in der Nähe befindet, um die Passage zu blockieren. Selbst wenn die Umgebung mehrere Hindernisse aufweist, verwendet dieses Verhalten jeweils eines davon, um die Vermeidungskraft zu berechnen.
Es werden nur die Hindernisse analysiert, die sich vor dem Charakter befinden. der nächste, der als am bedrohlichsten gilt, wird für die Bewertung ausgewählt. Infolgedessen ist der Charakter in der Lage, allen Hindernissen in der Umgebung auszuweichen, und geht nahtlos und nahtlos von einem zum anderen über.
Das Kollisionsvermeidungsverhalten ist kein Pfadfindungsalgorithmus. Die Charaktere bewegen sich durch die Umgebung, vermeiden Hindernisse und finden schließlich einen Weg, um durch die Blöcke zu gehen - aber sie funktionieren beispielsweise mit "L" - oder "T" -Hindernissen nicht wirklich gut.
Spitze: Dieses Verhalten bei Kollisionsvermeidung mag dem Fliehverhalten ähnlich sein, aber es gibt einen wichtigen Unterschied zwischen ihnen. Ein Charakter, der sich in der Nähe einer Wand bewegt, kann dies nur vermeiden, wenn er den Weg versperrt, aber das Fluchtverhalten drückt den Charakter immer von der Wand weg.Um Hindernisse in der Umgebung zu vermeiden, müssen Sie sie zunächst wahrnehmen. Die einzigen Hindernisse, die der Charakter befürchten muss, sind die, die sich davor befinden und die aktuelle Route direkt blockieren.
Wie zuvor erläutert, beschreibt der Geschwindigkeitsvektor die Richtung des Zeichens. Es wird verwendet, um einen neuen Vektor zu erzeugen voraus, Das ist eine Kopie des Geschwindigkeitsvektors, jedoch mit einer anderen Länge:
Accentsconagua
voraus Vektor ist die Sichtlinie des Charakters. Dieser Vektor wird wie folgt berechnet:
Ahead = Position + Normalisieren (Geschwindigkeit) * MAX_SEE_AHEAD
Das voraus Vektorlänge (eingestellt mit MAX_SEE_AHEAD) legt fest, wie weit der Charakter "sehen" wird.
Desto größer MAX_SEE_AHEAD Je früher beginnt der Charakter zu handeln, um einem Hindernis auszuweichen, weil er es selbst als Bedrohung wahrnimmt, selbst wenn es weit weg ist:
Um eine Kollision zu überprüfen, muss jedes Hindernis (oder sein Begrenzungsrahmen) als geometrische Form bezeichnet werden. Die Verwendung einer Kugel (Kreis in zwei Dimensins) führt zu den besten Ergebnissen, sodass jedes Hindernis in der Umgebung als solches beschrieben wird.
Eine mögliche Lösung zur Überprüfung auf Kollision ist der Schnittpunkt der Linie-Kugel - die Linie ist die voraus Vektor und die Kugel ist das Hindernis. Dieser Ansatz funktioniert, aber ich werde eine Vereinfachung des leichteren Verständnisses verwenden und ähnliche Ergebnisse erzielen (manchmal sogar bessere)..
Das voraus Der Vektor wird verwendet, um einen anderen Vektor mit der Hälfte seiner Länge zu erzeugen:
Das ahead2 Vektor wird genau wie berechnet voraus, aber seine Länge ist in zwei Hälften geschnitten:
Ahead = Position + Normalisierung (Geschwindigkeit) * MAX_SEE_AHEAD Ahead2 = Position + Normalisierung (Geschwindigkeit) * MAX_SEE_AHEAD * 0.5
Wir möchten eine Kollisionsprüfung durchführen, um zu testen, ob sich einer dieser beiden Vektoren innerhalb der Hindernissphäre befindet. Dies wird leicht durch den Vergleich des Abstands zwischen dem Ende des Vektors und dem Mittelpunkt der Kugel erreicht.
Wenn der Abstand kleiner oder gleich dem Kugelradius ist, befindet sich der Vektor innerhalb der Kugel und es wurde eine Kollision gefunden:
Ob entweder von den beiden Vorausvektoren befinden sich innerhalb der Hindernissphäre, dann blockiert dieses Hindernis den Weg. Der euklidische Abstand zwischen zwei Punkten kann verwendet werden:
private Funktionsentfernung (a: Object, b: Object): Number return Math.sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); private Funktion lineIntersectsCircle (Ahead: Vector3D, Ahead2: Vector3D, Hindernis: Circle): Boolean // Die Eigenschaft "Mitte" des Hindernisses ist ein Vector3D. Rückweg (Hindernis.Mitte, voraus) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius;
Wenn mehr als ein Hindernis den Weg blockiert, wird das nächstgelegene (das "bedrohlichste") zur Berechnung ausgewählt:
Die Ausweichkraft muss den Charakter vom Hindernis wegdrücken, damit er der Kugel ausweichen kann. Dies kann unter Verwendung eines Vektors erfolgen, der unter Verwendung des Mittelpunkts der Kugel (der ein Positionsvektor ist) und des Vektors gebildet wird voraus Vektor. Wir berechnen diese Vermeidungskraft wie folgt:
avoidance_force = ahead - obstacle_center avoidance_force = normalize (avoidance_force) * MAX_AVOID_FORCE
Nach dem avoidance_force berechnet wird, wird es normalisiert und skaliert mit MAX_AVOID_FORCE, Dies ist eine Zahl, die zur Definition der avoidance_force Länge. Desto größer MAX_AVOID_FORCE ist, desto stärker ist die Ausweichkraft, die den Charakter vom Hindernis wegdrückt.
Die endgültige Implementierung für die collisionAvoidance () Die Methode, die die Ausweichkraft zurückgibt, lautet:
private function collisionAvoidance (): Vector3D ahead =…; // Berechne den Ahead-Vektor ahead2 =…; // Berechne den ahead2-Vektor var mostThreatening: Obstacle = findMostThreateningObstacle (); Var vermeidung: Vector3D = new Vector3D (0, 0, 0); if (mostThreatening! = null) avoidance.x = voraus.x - mostThreatening.center.x; avoidance.y = ahead.y - mostThreatening.center.y; avoidance.normalize (); avoidance.scaleBy (MAX_AVOID_FORCE); else avoidance.scaleBy (0); // die Ausweichkraft aufheben return avoidance; private Funktion findMostThreateningObstacle (): Obstacle var mostThreatening: Obstacle = null; für (var i: int = 0; i < Game.instance.obstacles.length; i++) var obstacle :Obstacle = Game.instance.obstacles[i]; var collision :Boolean = lineIntersecsCircle(ahead, ahead2, obstacle); // "position" is the character's current position if (collision && (mostThreatening == null || distance(position, obstacle) < distance(position, mostThreatening))) mostThreatening = obstacle; return mostThreatening;
Die Ausweichkraft muss zum Geschwindigkeitsvektor des Charakters addiert werden. Wie zuvor erläutert, können alle Lenkkräfte zu einer Einheit kombiniert werden, die eine Kraft erzeugt, die das gesamte aktive Verhalten darstellt, das auf den Charakter wirkt.
Abhängig von Winkel und Richtung der Ausweichkraft werden andere Lenkkräfte wie Suchen oder Wandern nicht unterbrochen. Die Ausweichkraft wird wie üblich zur Spielergeschwindigkeit addiert:
lenkung = nichts (); // der Nullvektor, was "Zero-Force-Betrag" bedeutet Lenkung = Lenkung + Suchvorgang (); // Angenommen, der Charakter sucht etwas Lenkung = Lenkung + KollisionAvoidance (); Lenkung = verkürzt (Lenkung, max_force) Lenkung = Lenkung / Massengeschwindigkeit = verkürzt (Geschwindigkeit + Lenkung, max_speed) Position = Position + Geschwindigkeit
Da bei jedem Spielupdate alle Lenkverhalten neu berechnet werden, bleibt die Vermeidungskraft aktiv, solange das Hindernis den Weg blockiert.
Sobald das Hindernis nicht abfängt voraus Vektorlinie wird die Vermeidungskraft zu Null (keine Wirkung) oder sie wird neu berechnet, um das neue Bedrohungshindernis zu vermeiden. Das Ergebnis ist ein Charakter, der Hindernisse vermeiden kann:
Die aktuelle Implementierung weist zwei Probleme auf, die beide mit der Kollisionserkennung zusammenhängen. Der erste passiert, wenn die voraus Vektoren befinden sich außerhalb der Hindernissphäre, aber der Charakter ist zu nahe am Hindernis (oder innerhalb des Hindernisses).
In diesem Fall berührt (oder betritt) der Charakter das Hindernis und überspringt den Ausweichprozess, da keine Kollision erkannt wurde:
voraus Vektoren befinden sich außerhalb des Hindernisses, aber der Charakter ist innerhalb. Dieses Problem kann behoben werden, indem der Kollisionsprüfung ein dritter Vektor hinzugefügt wird: der Positionsvektor des Charakters. Die Verwendung von drei Vektoren verbessert die Kollisionserkennung erheblich.
Das zweite Problem tritt auf, wenn sich der Charakter in der Nähe des Hindernisses befindet und von ihm weglenkt. Manchmal führt das Manövrieren zu einer Kollision, obwohl sich der Charakter gerade in eine andere Richtung dreht:
Dieses Problem kann durch Skalieren des behoben werden voraus Vektoren entsprechend der aktuellen Geschwindigkeit des Charakters. Der Code zur Berechnung des voraus Vektor beispielsweise wird geändert in:
dynamic_length = Länge (Geschwindigkeit) / MAX_VELOCITY ahead = Position + Normalisierung (Geschwindigkeit) * Dynamic_length
Die Variable dynamische Länge reicht von 0 bis 1. Wenn sich der Charakter mit voller Geschwindigkeit bewegt, dynamische Länge ist 1; wenn der Charakter langsamer wird oder beschleunigt, dynamische Länge ist 0 oder größer (z. B. 0,5).
Als Konsequenz, wenn der Charakter nur bewegt, ohne sich zu bewegen, dynamische Länge neigt zu Null und erzeugt eine Null voraus Vektor, der keine Kollisionen hat.
Hier ist das Ergebnis mit diesen Verbesserungen:
Um das Verhalten bei Kollisionsvermeidung in Aktion zu demonstrieren, halte ich eine Horde Zombies für perfekt. Nachfolgend sehen Sie eine Demo, die mehrere Zombies (mit unterschiedlichen Geschwindigkeiten) zeigt, die den Mauszeiger suchen. Kunst von SpicyPixel und Clint Bellanger, von OpenGameArt.
Das Kollisionsvermeidungsverhalten erlaubt jedem Charakter, Hindernissen in der Umgebung auszuweichen. Da alle Lenkkräfte bei jedem Spiel-Update neu berechnet werden, interagieren die Charaktere nahtlos mit verschiedenen Hindernissen, wobei immer das bedrohlichste (das nächste) analysiert wird..
Obwohl dieses Verhalten kein Wegfindungsalgorithmus ist, sind die erzielten Ergebnisse für überfüllte Karten durchaus überzeugend.
