Wie finde ich die "Natürlich" direkte Route mit A-Stern (A *)

Question

Ich habe den A * -Algorithmus in AS3 implementiert und es funktioniert gut bis auf eine Sache. Oft der resultierende Pfad nicht am meisten "Natürliche" oder glatte Route zum Ziel. In meiner Umgebung kann sich das Objekt diagonal so günstig bewegen, wie es horizontal oder vertikal bewegen kann. Hier ist ein sehr einfaches Beispiel; der Startpunkt ist durch das S markiert, und das Ende (oder Finish) Punkt von der F.

| | | | | | | | | | 
|S| | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
|F| | | | | | | | | 
| | | | | | | | | | 
| | | | | | | | | | 

Wie Sie während der ersten Runde der Erkenntnis sehen können, Knoten [0,2], [1,2], [2,2] werden alle hinzugefügt werden die Liste der möglichen Knoten wie sie alle ha ve eine Punktzahl von N. Das Problem, das ich habe, kommt am nächsten Punkt, wenn ich versuche, zu entscheiden, mit welchem ​​Knoten fortzufahren. Im obigen Beispiel benutze ich mapsNodes [0], um den nächsten Knoten zu wählen. Wenn ich dies in possibleNodes [possibleNodes.length-1] ändere, erhalte ich den folgenden Pfad.

| | | | | | | | | | 
|S| | | | | | | | | 
| |x| | | | | | | | 
| | |x| | | | | | | 
| | | |x| | | | | | 
| | |x| | | | | | | 
| |x| | | | | | | | 
|F| | | | | | | | | 
| | | | | | | | | | 
| | | | | | | | | | 

Und dann mit possibleNextNodes [Math.round (possibleNextNodes.length/2) -1]

| | | | | | | | | | 
|S| | | | | | | | | 
|x| | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
x| | | | | | | | | | 
|F| | | | | | | | | 
| | | | | | | | | | 
| | | | | | | | | | 

Alle diese Wege haben die gleichen Kosten wie sie alle die gleiche Anzahl von Schritten enthalten aber, in dieser Situation wäre der vernünftigste Weg wie folgt ...

| | | | | | | | | | 
|S| | | | | | | | | 
|x| | | | | | | | | 
|x| | | | | | | | | 
|x| | | | | | | | | 
|x| | | | | | | | | 
|x| | | | | | | | | 
|F| | | | | | | | | 
| | | | | | | | | | 
| | | | | | | | | | 

gibt es eine formal anerkannte Methode den Weg zu machen scheint vernünftige und nicht nur mathematisch korrekt?

Answer 1

Sie müssen Ihrer heuristischen Funktion einen Tie-Breaker hinzufügen. Das Problem hierbei ist, dass es viele Wege mit den gleichen Kosten gibt.

Für einen einfachen Tie-Breaker, der den direkten Weg bevorzugt, können Sie das Cross-Produkt verwenden. I.e. Wenn S der Anfang und E das Ende ist und X die aktuelle Position im Algorithmus ist, könnten Sie die Kreuzprodukte von SE und XE berechnen und der Heuristik einen weiteren Wert hinzufügen, je weiter sie von 0 abweicht (= die direkte Route)).

In Code:

dx1 = current.x - goal.x 
dy1 = current.y - goal.y 
dx2 = start.x - goal.x 
dy2 = start.y - goal.y 
cross = abs(dx1*dy2 - dx2*dy1) 
heuristic += cross*0.001 

Siehe auch http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12, die eine hervorragende Tutorial über A * im Allgemeinen.

Answer 2

Wenn Sie Pfade suchen, die natürlich aussehen, müssen Sie sicherstellen, dass Ihre Kosten der Länge eines kartesischen Koordinatensystems entsprechen. Das bedeutet, dass die Kosten der diagonalen Bewegung das 2-fache der Kosten für die vertikale oder horizontale Bewegung betragen.

Answer 3

Was ist "sinnvoller"? Gerader? Sie müssen es richtig quantifizieren, wenn der Algorithmus etwas dagegen tun wird.

Da die diagonale Bewegung genauso kostengünstig ist wie die horizontale/vertikale Bewegung, sind alle Pfade äquivalent zu allen verfügbaren Kriterien für A *. Wenn Sie einen "vernünftigeren" Pfad wünschen, müssen Sie dem Algorithmus mitteilen, dass einige Pfade wünschenswerter sind als andere, und Sie können horizontal/vertikal als "besser" als diagonal bewerten. Soweit ich das sehe, würde das die Parameter Ihrer Umgebung verändern.

Answer 4

Wenn ich mich richtig erinnere, der Trick, um dies einen zusätzlichen Parameter an die Kostenfunktion (für jeden Schritt zwischen benachbarten Knoten oder Quadraten in Ihrem Fall) hinzufügen, dass Windungen bestraft etwas mehr als normal (zum Beispiel, mit relativen Kosten von mehr als sqrt(2) für digonale Bewegungen). Jetzt gibt es wahrscheinlich eine feine Linie zwischen dem Pfad zu glätten und tatsächlich der Optimalität der Route abnimmt (verlängernden es), aber, und Sie nicht gehen zu können, dies in irgendeiner Weise zu vermeiden. Es gibt eine bestimmte Trade-off Sie Ihre eigene Anwendung zu entdecken spezifische benötigen, und dies auch nur wirklich kann durch Tests erreicht werden.

Es gab einen Artikel auf einem Spiel Entwickler-Website, ich glaube, dass detaillierte genau, wie dies geschehen könnte, aber ich kann nicht scheinen, um es im Moment zu finden. Haben Sie ein Spiel mit Ihrer Kostenfunktion sowieso und welche Ergebnisse Sie bekommen - ich bin mir ziemlich sicher, dass die Art und Weise ist zu gehen.

Answer 5

Sie können für jedes Quadrat ‚Steueraufwand‘ die Kostenberechnungen hinzufügen. Der Schauspieler wird nicht versuchen, zu drehen oder die Richtung ändern zu viel wie die Kosten für den Pfad hinzufügen wird:

http://angryee.blogspot.com/2009/03/better-pathfinding.html