Ich arbeite daran, die Wegfindung für die Feinde meines Spiels zu verbessern. Im Moment bewegen sie sich einfach ständig auf die exakte Position des Spielers zu, indem sie den Winkel zwischen sich und den Spielern berechnen und sich in diese Richtung bewegen. Ich habe auch einen Flock-Algorithmus, der verhindert, dass sich die Feinde übereinander stapeln, sodass sie sich zu Gruppen zusammenschließen, anstatt sich gegenseitig zu durchschneiden.
Jetzt, da ich eine kachelbasierte Karte hinzugefügt habe, müssen die Feinde jedoch auch in der Lage sein, beispielsweise um Hindernisse und Mauern herumzulaufen. Anfangs habe ich versucht, "nicht begehbaren" Kacheln einen Trennungswert hinzuzufügen, damit der Beflockungsalgorithmus die Wände und Hindernisse als Objekte ansieht, von denen man sich entfernen kann. Ich muss noch herausfinden, ob dies machbar ist oder nicht, da mein erster Test zeigte, dass die Feinde auf eine unsichtbare "Wand" treffen, an der es keine nicht begehbaren Kacheln gibt.
Ich habe mich gefragt, ob es möglicherweise zu leistungsintensiv ist, einen Pfad zum Spieler mit A * zu berechnen und dann den Flock-Algorithmus zu verwenden, um ein Verklumpen zu verhindern. Ursprünglich sollte mein Spiel ein wellenbasierter Shooter sein, aber ich habe mich dafür entschieden, es in Anlehnung an die Hotline Miami levelbasiert zu machen. Daher werde ich wahrscheinlich weniger Feinde haben, mit einer gelegentlichen Horde, und einfach machen sie stärker.
Ist das eine praktikable Lösung? Ich benutze Java mit Slick2D als meine Spiel-Engine. Oder gibt es eine bessere Lösung / einen besseren Algorithmus, der beide Probleme angeht?
quelle
Antworten:
Dies klingt nach einem Anwendungsfall für Flow Fields.
Bei dieser Technik führen Sie eine einzelne Pfadfindungsabfrage von Ihren Player-Objekten nach außen durch und markieren dabei jede Zelle, auf die Sie stoßen, mit der Zelle, von der aus Sie sie erreicht haben.
Wenn alle Ihre Kacheln / Kanten die gleichen Traversalkosten haben, können Sie eine einfache Breitensuche durchführen. Ansonsten funktioniert der Dijkstra-Algorithmus (wie A * ohne Ziel / Heuristik).
Dadurch wird ein Flussfeld erstellt: Eine Nachschlagetabelle, die jede Zelle dem nächsten Schritt zum nächstgelegenen Spielerobjekt von dieser Position aus zuordnet.
Jetzt können Ihre Feinde ihre aktuelle Position im Flussfeld abrufen, um den nächsten Schritt auf ihrem kürzesten Weg zum nächstgelegenen Spielerobjekt zu finden, ohne dass sie jeweils eine eigene Pfadfindungsabfrage durchführen müssen.
Dies skaliert besser und besser, je mehr Feinde sich in Ihrer Herde befinden. Für einen einzelnen Gegner ist es teurer als A *, weil es die gesamte Karte durchsucht (obwohl Sie frühzeitig aussteigen können, sobald Sie alle Wegbereiter erreicht haben). Wenn Sie jedoch weitere Gegner hinzufügen, können diese mehr und mehr an den Kosten für die Pfadfindung beteiligt werden, indem sie gemeinsam genutzte Pfadsegmente einmal und nicht immer wieder berechnen. Sie profitieren auch von der Tatsache, dass BFS / Dijkdtra einfacher als A * und in der Regel billiger pro untersuchter Zelle zu bewerten sind.
Genau dort, wo die Gewinnschwelle erreicht wird, von einzelnen A *, die billiger sind, bis zu A *, wobei die Speicherung billiger ist (wobei Sie einige der Ergebnisse für eine frühere Wegfindungsabfrage wiederverwenden, um die nächste zu beschleunigen), um Felder zu fließen Dies hängt von Ihrer Implementierung, der Anzahl der Agenten und der Größe Ihrer Karte ab. Wenn Sie jedoch jemals einen großen Schwarm von Feinden planen, der sich aus mehreren Richtungen auf engstem Raum nähert, ist ein Strömungsfeld mit ziemlicher Sicherheit billiger als das iterierte A *.
Als extremes Beispiel sehen Sie hier ein Video mit 20 000 Agenten, die alle gleichzeitig auf einem relativ kleinen Raster nach Wegen suchen .
quelle
Ein * ist nicht leistungslastig. Ich würde mich dieser Situation durch Variation der Algorithmen nähern. Machen Sie von Zeit zu Zeit ein A * und prüfen Sie zwischendurch, ob der nächste Schritt frei ist oder Sie Ausweichen müssen.
Verfolgen Sie beispielsweise die Entfernung des Spielers vom A * -Zielort, wenn dieser über einem Schwellenwert liegt. Berechnen Sie ein * neu und aktualisieren Sie dann einfach die Bewegungen. Die meisten Spiele verwenden eine Kombination von Wegpunkten, z. B. ein vereinfachtes Raster für die Wegfindung und eine Logik, die die Bewegung zwischen Wegpunkten mit Ausweichlenkungsalgorithmen unter Verwendung von Raycasts handhabt. Die Agenten versuchen, durch Manövrieren um Hindernisse in ihrer Nähe zu einem entfernten Wegpunkt zu rennen, was meiner Meinung nach der beste Ansatz ist.
Am besten arbeitet man hier mit endlichen Automaten und liest das Buch "Programming Game AI By Example" von Mat Buckland. Das Buch bietet bewährte Techniken für Ihr Problem und beschreibt die erforderlichen Berechnungen. Der Quellcode aus dem Buch ist im Internet verfügbar. Das Buch ist in C ++, aber einige Übersetzungen (einschließlich Java) sind verfügbar.
quelle
Es ist nicht nur machbar, ich glaube es wurde in einem kommerziellen Spiel in den 90ern gemacht - BattleZone (1998).
Das Spiel hatte 3D-Einheiten mit freien Bewegungen, die nicht auf Kacheln basierten, und eine auf Kacheln basierende Basiskonstruktion.
So schien es zu funktionieren:
Erstens A * oder etwas Ähnliches (wahrscheinlich eine Variation von A * mit strengen Einschränkungen für die Länge eines Pfads, sodass die Ausführung niemals zu viele Ressourcen erfordert, aber nicht immer einen Pfad bis zum Ziel findet) würde verwendet werden, um einen Weg zu finden, über den ein Schwebetank an sein Ziel gelangen kann, ohne in kachelförmigen Hindernissen stecken zu bleiben.
Dann flog der Panzer durch den gesamten Raum, als würde er auf seinem Weg von der Mitte eines nahegelegenen Feldes angezogen und von Hindernissen, anderen nahegelegenen Panzern usw. zurückgestoßen.
quelle