Effiziente Wegfindung im freien Raum

Ich habe ein Spiel im Weltraum und möchte Bewegungsbefehle erteilen, für die eine Wegfindung erforderlich ist. Ich verstehe jetzt, dass A * und so etwas hauptsächlich für Bäume gilt und nicht für leeren Raum ohne Pfaderkennungsknoten. Ich habe einige Hindernisse, die derzeit als feste AABB ausgedrückt werden - das heißt, es gibt kein unbegrenztes "Gelände" -Hindernis. Außerdem erwarte ich, dass sich die meisten Hindernisse als Würfel oder Kugeln annähern lassen.

Daher habe ich mir überlegt, einen viel einfacheren Pfadfindungsalgorithmus anzuwenden: Wirf einfach einen Strahl von der aktuellen Position zur Zielposition, und dann kann ich relativ schnell eine Liste von Hindernissen mithilfe der räumlichen Partitionierung abrufen. Was ich nicht so sicher bin, ist, wie man den Teil bestimmt, an dem die bestellte Einheit um die Hindernisse manövriert.

Was ich bisher gedacht habe, ist, dass ich einfach potenzielle Felder benutze - das heißt, dass alle Einheiten eine starke Abstoßungskraft voneinander und eine moderate Kraft zum gewünschten Punkt hin spüren. Dies hat auch den Vorteil, dass ich zur Erteilung von Gruppenbefehlen einfach eine mittlere Streitmacht gegen eine andere Einheit befehlen kann. Dies führt jedoch offensichtlich nicht zu einer optimalen Lösung.

Erzielen potenzielle Felder aufgrund meiner Parameter eine angemessene Annäherung, oder benötige ich eine andere Lösung?

c++ path-finding DeadMG
quelle

Antworten:

Während potenzielle Felder funktionieren können, stoßen Sie vermutlich auf Probleme mit suboptimalen Pfaden und "lokalen Minima", bei denen Ihre Einheiten von umgebenden Hindernissen eingeschlossen werden. A * eignet sich für 3D-Open-Space-Umgebungen. Es wird einfach zum Problem, ein Navigationsnetz zu generieren, das Ihren Anforderungen entspricht. Sie können sogar Strukturen wie Octrees für Navigationsknoten verwenden. Je kleiner die maximale Größe jedes Oktanten ist, desto glatter ist der Pfad. Schauen Sie sich diesen Artikel von Face to Face-Spielen an (nicht mehr vorhanden, Wayback-Link hinzugefügt). A * in Kombination mit der Pfadoptimierung (wie bei Kurzbefehlen für die Sichtlinie) und dem Steuerverhalten, und Sie können loslegen! In der folgenden Abbildung sehen Sie ein Beispiel für die Verwendung eines Octrees für Pfadknoten:

MichaelHouse
quelle

Wie wird dies auf größere Karten skaliert? Wenn ich eine Karte hätte, die in jeder Dimension doppelt so groß wäre, bräuchte ich die achtfache Anzahl von Knoten, was problematisch wäre.

DeadMG

Nicht unbedingt. Sie können den Knoten so lange vergrößern, bis sich Ihre Suche dem nähert. Auf diese Weise können Sie die Knoten, an denen Sie nicht interessiert sind, relativ groß und in geringer Anzahl halten.

MichaelHouse

Eine schöne Eigenschaft von Navigationsnetzen im leeren Raum ist die Gleichheit der Reisekosten. Möglicherweise können Sie A * JPS

Will

@ Will: Ich habe ein bisschen gegoogelt, aber ich habe den einzigen Pfadfindungsalgorithmus, der aufgetaucht ist, nicht wirklich verstanden. Möchtest du eine Antwort darauf posten?

DeadMG

@DeadMG Dies ist die endgültige Erklärung: harablog.wordpress.com/2011/09/07/jump-point-search <br/> Wenn Sie A * implementieren können, können Sie JPS relativ einfach nachrüsten. Machen Sie zuerst A * und fügen Sie JPS als Optimierung hinzu.

Wird