Grundlegende Wegfindung mit Vermeidung von Hindernissen in einem kontinuierlichen 2D-Raum

Question

Ich schreibe eine Simulation, in der ein Kreaturobjekt sich auf ein beliebiges anderes Objekt in der Umgebung bewegen und Hindernisse umgehen kann, anstatt eine intelligente Wegfindung durchzuführen. Ich versuche nicht, es Plan einen Weg zu haben - nur um in eine allgemeine Richtung zu bewegen, und hüpfe um Hindernisse herum.

Es ist eine 2D-Umgebung (Overhead-Ansicht), und jedes Objekt hat ein begrenzendes Rechteck für die Kollisionserkennung. Es gibt kein Raster und ich suche keine A * -Lösung.

Ich konnte keine Tutorials zu dieser Art von "dummer" kollisionsgestützter Pfadfindung finden, daher beschreibe ich das vielleicht nicht mit den gebräuchlichsten Begriffen.

Irgendwelche Empfehlungen zur Implementierung (oder Links zu Tutorials)?

Answer 1

Erweitern, was Guillaume über Hindernisvermeidung sagte, eine Technik, die gut für Sie arbeiten würde, ist anti-gravity movement. Sie behandeln lokale Hindernisse als Punktquellen der Antigravitation, das Ziel als Schwerkraft, und Ihr computergesteuerter Charakter rutscht (wie Seife!) Um die Hindernisse herum, um zum Ziel zu gelangen.

Answer 2

gab ich eine Wegfindung Algorithmus in C# eine Weile zurück

Here's the link

Sie versuchen, es als Ausgangspunkt verwenden können, das heißt, könnten Sie die Funktion ändern, die die nächste Zelle überprüft, um zu sehen, ob es Es ist möglich, auf die Hindernisse zu prüfen, und Sie könnten es in kleine Intervalle anstatt der Start- und Endpunkte einspeisen, ähnlich wie mehrere Mini-Routen.

(Der Text ist in Spanisch, aber Sie können die Anwendung aus dem Link oben downloaden)

Answer 3

Vielleicht könnten Sie Pledge's algorithm

Answer 4

Jedes Mal, wenn Sie Ihre Kreatur, in Vektorrichtung reisen v, mit einem kollidiert Wand, deren Richtung durch den Vektor w dargestellt wird, ist die Richtung, die Sie "schieben" müssen, durch den Vektor gegeben, der die Projektion von v auf w ist. Dies kann ermittelt werden unter Verwendung von

v . w 
--------- w 
|w|*|w| 

wo . ist die vector dot product|w| und ist die Größe des Vektors w (= sqrt(w . w)). Wenn w ein Einheitsvektor ist, wird dies einfach

(v . w) w 

Unter Verwendung des resultierenden Vektors als die Geschwindigkeit der Kreatur bedeutet, deine Kreatur schnell bewegt, wenn es nur „grast“ die Wand, und langsam, wenn er trifft die Wand fast Fristen auf. (Dies ist, wie die meisten First-Person-Shooter-Kollisionen für den menschlichen Spieler verwalten.)

Wenn Sie stattdessen möchten, dass Ihre Kreatur immer mit voller Geschwindigkeit reisen, benötigen Sie nur das Zeichen v . w - Sie werden immer entweder reisen in die Richtung, in die die Wand zeigt (w) oder in die entgegengesetzte Richtung (-w).

Das Problem, das Sie haben werden, ist, wenn Ihre Kreatur die Dead-On-Wand trifft. In diesem Fall ist Ihr projizierter Vektor (0, 0), und Sie benötigen eine andere Technik, um zu entscheiden, in welcher Richtung (w oder -w) Sie gehen sollen. Der übliche Ansatz hier ist A *, obwohl dies unnötig sein kann, wenn Ihre Umgebung genügend Struktur besitzt.

Answer 5

können zwei Lenk Algorithmus kombinieren:

suchen: Sie eine Lenkkraft in Richtung anzuwenden, die die Differenz zwischen der aktuellen Geschwindigkeit und der gewünschten Geschwindigkeit in Richtung des Ziel

Hindernisvermeidungs ​​ : Sie antizipieren die Zukunft des Fahrzeugs mit einer Box, deren Länge eine konstante Zeit multipliziert mit der aktuellen Geschwindigkeit des Fahrzeugs ist. Jedes Hindernis, das diese Box schneidet, ist eine potenzielle Kollisionsgefahr. Die nächste solche Bedrohung wird zur Vermeidung ausgewählt. Um ein Hindernis zu vermeiden, wird eine seitliche Lenkkraft entgegen der Mitte des Hindernisses aufgebracht. Zusätzlich wird eine Brems- (Verzögerungs-) Kraft aufgebracht. Diese Kräfte variieren mit der Dringlichkeit (der Abstand von der Spitze der Box bis zum Punkt der möglichen Kollision). Lenkung variiert linear, Bremsung variiert quadratisch.

Sie können

PS mehr auf der Website "Steering Behaviors For Autonomous Characters"

Grüße

Guillaume finden: dies annehmen, dass Sie für die Objektbewegung einen Punkt/Geschwindigkeit/Beschleunigung Methode verwenden.