Hallo liebe Community,
für einen kleinen Wettbewerb an meiner Uni programmiere ich derzeit ein kleines RTS Spiel. Dies soll in2D sein und Multiplayer unterstützen. Einen Teil des Spieles habe ich auch schon fertig und getestet, allerdings ist dies alles statisch und nun kommt die Bewegung ins Spiel.
Die Map besteht aus Tiles und kann bis zu 800x800 Felder groß werden. Die Bewegung kann sowohl horizontal/vertikal als auch diagonal verlaufen. Außer man würde diagonal durch eine Wand laufen.
Ich habe nun erstmal den A* Algorithmus zum Testen implementiert, damit ich vorerst überhaupt Agenten bewegen kann. Bei großen Karten bzw. bei ungünstigen Fällen kann der Aufwand von A* bekanntlich extrem anwachsen. Was dann spätestens bei Gruppen von Agenten dazu führt, dass sie sich nach einer Stunde mal in Bewegung versetzen.
Nun wollte ich als erstes den HPA* Algorithmus benutzen, damit ich erst einen groben Pfad finden kann und dann nach und nach den Pfad durch Tiefensuche zu verfeinern. Dadurch können sich meine Agenten schneller in Bewegung versetzen. Allerdings finde ich damit nicht immer den kürzesten Pfad. Und ich werde möglicherweise Probleme bei der Graphenkorrektur bekommen. Falls Gebäude gebaut oder Bäume abgerissen werden.
Zum weiteren Beschleunigen des Algorithmus dachte ich daran den A* durch den JPS (Jump Search) zu ersetzen, sodass die Anzahl der zu untersuchenden Knoten weiter sinkt.
Somit wäre meine Alternative eine Kombination aus hierarchie und JPS. Dabei würde ich den A* Teil des HPA durch den JPS ersetzen.
Allerdings ist das ein fester Graph, und die Knoten haben keinerlei Daten über ihre Umwelt. Da mir der Alg. aber nicht immer den kürzesten Pfad findet und ich keine Daten über die Umgebung der Knoten habe, kann ich außerdem keine Pfadglättung machen. Da ich sonst relativ schnell in einem Gebäude o.Ä. landen könnte.
Das hat mich dann zu den Navmeshes geführt, bei denen ich dann die Polygone mit dem JPS oder A* durchsuchen würde. Dabei wäre dann auch wirder eine Pfadglättung möglich, da ich die Stellen der Map durch die Polygone ja kenne durch die sich meine Agenten problemlos bewegen können.
Das einzige Problem das ich dabei dann haben werde, dass man bei einem NavMesh nur die begehbaren Flächen kennt und in einem RTS unbegehbare Flächen begehbar gemacht werden können oder umgekehrt, was dann wiederum sehr intensive Korrekturen an den Polygonen führen würde.
Bei all den Algorithmen, Meinungen in Foren und so weiter, bin ich wenig verwirrt um ehrlich zu sein :bloed: Nun meine eigentliche Frage, was würdet ihr verwenden? Und vor allem warum.
Freue mich auf eure Antworten :toll:
PS : Ja ich weis, dass ich für das Spiel gar keinen so ausgereiften Algorithmus brauche, allerdings ist meine Devise, je schneller der Algorthmus, desto höher kann ich meine Agentenbeschränkung anlegen. :applaus:
für einen kleinen Wettbewerb an meiner Uni programmiere ich derzeit ein kleines RTS Spiel. Dies soll in2D sein und Multiplayer unterstützen. Einen Teil des Spieles habe ich auch schon fertig und getestet, allerdings ist dies alles statisch und nun kommt die Bewegung ins Spiel.
Die Map besteht aus Tiles und kann bis zu 800x800 Felder groß werden. Die Bewegung kann sowohl horizontal/vertikal als auch diagonal verlaufen. Außer man würde diagonal durch eine Wand laufen.
Ich habe nun erstmal den A* Algorithmus zum Testen implementiert, damit ich vorerst überhaupt Agenten bewegen kann. Bei großen Karten bzw. bei ungünstigen Fällen kann der Aufwand von A* bekanntlich extrem anwachsen. Was dann spätestens bei Gruppen von Agenten dazu führt, dass sie sich nach einer Stunde mal in Bewegung versetzen.
Nun wollte ich als erstes den HPA* Algorithmus benutzen, damit ich erst einen groben Pfad finden kann und dann nach und nach den Pfad durch Tiefensuche zu verfeinern. Dadurch können sich meine Agenten schneller in Bewegung versetzen. Allerdings finde ich damit nicht immer den kürzesten Pfad. Und ich werde möglicherweise Probleme bei der Graphenkorrektur bekommen. Falls Gebäude gebaut oder Bäume abgerissen werden.
Zum weiteren Beschleunigen des Algorithmus dachte ich daran den A* durch den JPS (Jump Search) zu ersetzen, sodass die Anzahl der zu untersuchenden Knoten weiter sinkt.
Somit wäre meine Alternative eine Kombination aus hierarchie und JPS. Dabei würde ich den A* Teil des HPA durch den JPS ersetzen.
Allerdings ist das ein fester Graph, und die Knoten haben keinerlei Daten über ihre Umwelt. Da mir der Alg. aber nicht immer den kürzesten Pfad findet und ich keine Daten über die Umgebung der Knoten habe, kann ich außerdem keine Pfadglättung machen. Da ich sonst relativ schnell in einem Gebäude o.Ä. landen könnte.
Das hat mich dann zu den Navmeshes geführt, bei denen ich dann die Polygone mit dem JPS oder A* durchsuchen würde. Dabei wäre dann auch wirder eine Pfadglättung möglich, da ich die Stellen der Map durch die Polygone ja kenne durch die sich meine Agenten problemlos bewegen können.
Das einzige Problem das ich dabei dann haben werde, dass man bei einem NavMesh nur die begehbaren Flächen kennt und in einem RTS unbegehbare Flächen begehbar gemacht werden können oder umgekehrt, was dann wiederum sehr intensive Korrekturen an den Polygonen führen würde.
Bei all den Algorithmen, Meinungen in Foren und so weiter, bin ich wenig verwirrt um ehrlich zu sein :bloed: Nun meine eigentliche Frage, was würdet ihr verwenden? Und vor allem warum.
Freue mich auf eure Antworten :toll:
PS : Ja ich weis, dass ich für das Spiel gar keinen so ausgereiften Algorithmus brauche, allerdings ist meine Devise, je schneller der Algorthmus, desto höher kann ich meine Agentenbeschränkung anlegen. :applaus:
Zuletzt bearbeitet:
