Wie kann ich diesen A * -Such-Pfadfindungsalgorithmus optimieren, um verschiedene Geländebewegungswerte zu verarbeiten?

8

Ich erstelle ein 2D-Karten-basiertes Actionspiel mit einem ähnlichen Interaktionsdesign wie Diablo II. Mit anderen Worten, der Spieler klickt auf eine Karte, um seinen Spieler zu bewegen. Ich habe gerade die Spielerbewegung beendet und gehe zur Wegfindung über.

Im Spiel sollten Feinde den Charakter des Spielers aufladen. Es gibt auch fünf verschiedene Geländetypen, die unterschiedliche Bewegungsboni bieten. Ich möchte, dass die KI diese Geländeboni nutzt, um den Spieler zu erreichen.

Mir wurde gesagt, ich solle den A * -Suchalgorithmus überprüfen (http://en.wikipedia.org/wiki/A*_search_algorithm). Ich mache dieses Spiel in HTML5 und JavaScript und habe eine Version in JavaScript gefunden: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript Ich versuche herauszufinden, wie ich es optimieren kann obwohl.

Nachfolgend sind meine Ideen aufgeführt, was ich ändern muss. Worüber muss ich mich sonst noch sorgen?

  • Wenn ich ein Diagramm erstelle, muss ich das übergebene 2D-Array mit einer Durchquerung einer Karte initialisieren, die den verschiedenen Geländetypen entspricht.
  • in graph.js: Die Definition "GraphNodeType" muss geändert werden, um die 5 Geländetypen zu verarbeiten. Es wird keine Wände geben.
  • in astar.js: Die Punkte g und h müssen geändert werden. Wie soll ich das machen?
  • in astar.js: isWall () sollte wahrscheinlich entfernt werden. Mein Spiel hat keine Wände.
  • in astar.js: Ich bin mir nicht sicher, was das ist. Ich denke, es zeigt einen Knoten an, der nicht gültig ist, um verarbeitet zu werden. Wann würde das allerdings passieren?
  • Wie ändere ich diesen Algorithmus auf hoher Ebene von "Oh, gibt es dort eine Wand?" zu "Wird mich dieses Terrain schneller zum Spieler bringen als das Terrain um mich herum?"

Aus Zeitgründen diskutiere ich auch darüber, meinen Bresenham-Algorithmus für die Feinde wiederzuverwenden. Leider werden die verschiedenen Geländebewegungsboni von der KI nicht verwendet, was das Spiel zum Kotzen bringt. : / Ich hätte das wirklich gerne für den Prototyp, aber ich bin weder ein Entwickler von Beruf noch ein Informatiker. : D.

Wenn Sie einen Code kennen, der das tut, wonach ich suche, teilen Sie ihn bitte mit!

Tipps zur Überprüfung der geistigen Gesundheit sind ebenfalls willkommen.

user422318
quelle
Hey, Autor der Bibliothek hier. Verwenden Sie die neueste Version von Github? github.com/bgrins/javascript-astar/blob/master/astar.js . Es ist viel schneller als die alte listenbasierte Implementierung.
Brian Grinstead

Antworten:

7

Sie müssen auf eine ganz bestimmte Zeile im Algorithmus achten:

// g score is the shortest distance from start to current node, we need to check if
//   the path we have arrived at this neighbor is the shortest one we have seen yet
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor

Dies sind die Kosten für diesen bestimmten Knoten. Sie möchten es zu etwas wie ändern

var gScore = currentNode.g + currentNode.cost

Dies führt dazu, dass der Pfad teures Gelände vermeidet und billiges Gelände bevorzugt. Es liegt in Ihrer Verantwortung, dass 'currentNode.cost' etwas zurückgibt, das für Ihr Gelände geeignet ist. Es ist die Tatsache, dass nicht jedes Gelände Kosten von 1 hat, auf die Sie achten ... einige Gebiete sind billiger als andere. Es gibt andere Überlegungen, aber dieser spezielle Punkt im Code sollte im Mittelpunkt Ihrer Aufmerksamkeit stehen.

Myrddin Emrys
quelle
Danke dafür. Ich habe meinen Code so geändert, dass jeder Knoten das Pixel an seinen Koordinaten nachschlägt und es als Kosten speichert. Leider habe ich einen Testpfad zwischen zwei Punkten in meinem 800x500-Raster gefunden und mein Browser stürzt ab. : / Hierfür gibt es mehrere Faktoren: Der Star-Code muss möglicherweise optimiert werden. meine Leinwandgröße ist riesig; Vielleicht ist meine Diagramminitialisierung falsch. und vielleicht bringen die Farben auf den Avataren der Charaktere die Dinge durcheinander. Was sollte ich tun? :(
user422318
Wenn Sie "speichert das Pixel" sagen, meinen Sie damit, dass es die Geländekosten des Pixels speichert, ja? Weil es unwahrscheinlich ist, dass ein RGB-Wert den tatsächlichen Kosten dieses Geländestücks entspricht. Sie sollten wahrscheinlich etwas zwischen 1 und 10 speichern (1 ist eine Straße, 10 ist ein Sumpf), obwohl die genauen Werte natürlich von Ihrem genauen Spiel abhängen.
Myrddin Emrys
1
Hey, Autor der Bibliothek hier. Verwenden Sie die neueste Version von Github? github.com/bgrins/javascript-astar/blob/master/astar.js . Es ist viel schneller als die alte listenbasierte Implementierung.
Brian Grinstead
2
@Brian Sie sollten diesen Kommentar eher auf die Frage als auf meine Antwort setzen, damit die Person, die die Bibliothek tatsächlich nutzt, die Benachrichtigung in ihrer E-Mail erhält und nicht in meiner.
Myrddin Emrys
2

Genau dafür ist A * gedacht. Sie müssen lediglich die Eckpunkte zwischen den Knotenkosten basierend auf den Geländetypen zuweisen. (Es sieht so aus, als ob in Ihren Beispielen ein Diagramm verwendet wird, in dem alle Eckpunkte Kosten von 1 haben.)

Chaos
quelle
0

Diese Implementierung ist momentan ein wenig spezifisch für das Ein- und Ausschalten. Wie Myrddin Emrys sagt, müssen Sie den g-Wert basierend auf den Kosten ändern (und nicht nur um 1). Hier gab es eine Diskussion darüber: https://github.com/bgrins/javascript-astar/issues/3 .

Ich würde diese Lösung gerne wieder in die Hauptbibliothek portieren, wenn sie funktioniert!

Brian Grinstead
quelle