Tweet
Ich habe gerade ein kleines Testprojekt angefangen in dem ich versuche ein TowerDefense Game zu basteln. Damit das ganze nicht all zu trivial ist, versuche ich etwas in der Art von Desktop-Tower-Defense zu bauen, sprich die Creeps sollen den Weg durch ein vom Spieler erbautes Labyrinth finden.
Meine bisherige Lösung besteht darin, den Boden mit Kachel zu modellieren. in diesem Movieclip steckt ein Array welches die "Nachbarn" enthält, jede Bodenkachel kann somit als Knoten in einem Graphen behandelt werden.
Vorteile:
Mit eine einfachen Breitensuche über die Knoten (bzw Kacheln) kann man effizient kürzeste Wege finden, ich schreibe einfach in jede Kachel einen Verweis auf den Vater im Spannbaum.
Die Creeps finden ihren Weg einfach, indem sie "auf den Boden gucken", also bei erreichen des Feldmittelpunktes den Zeiger abrufen und zum nächsten Feld laufen. Somit ist der Aufwand im Creep minimal.
Trotzdem habe ich mit dieser Modellierung große Performanceprobleme wenn schnell hintereinander felder aktiviert und deaktiviert werden, sprich die Suche über den Graphen neu gestartet werden muss.
Hat jemand eine Idee wie eine solche Wegfindung effizienter zu gestalten ist?
Vor allem wenn für verschiedene Creep-Sorten verschiedene Wege gefunden werden sollen (shortest Path, Weg mit geringstem Schaden, ...) befürchte ich einen heftigen Einbruch der Framerate sobald Türme gesetzt oder geupgraded werden und die Suchen neu loslaufen.
(Der Interessierte sollte sich mal Desktop TD und Nanowars anschauen, bei den beiden Spielen vermute ich ganz stark Graphalgorithmen im Hintergrund)
Meine bisherige Lösung besteht darin, den Boden mit Kachel zu modellieren. in diesem Movieclip steckt ein Array welches die "Nachbarn" enthält, jede Bodenkachel kann somit als Knoten in einem Graphen behandelt werden.
Vorteile:
Mit eine einfachen Breitensuche über die Knoten (bzw Kacheln) kann man effizient kürzeste Wege finden, ich schreibe einfach in jede Kachel einen Verweis auf den Vater im Spannbaum.
Die Creeps finden ihren Weg einfach, indem sie "auf den Boden gucken", also bei erreichen des Feldmittelpunktes den Zeiger abrufen und zum nächsten Feld laufen. Somit ist der Aufwand im Creep minimal.
Trotzdem habe ich mit dieser Modellierung große Performanceprobleme wenn schnell hintereinander felder aktiviert und deaktiviert werden, sprich die Suche über den Graphen neu gestartet werden muss.
Hat jemand eine Idee wie eine solche Wegfindung effizienter zu gestalten ist?
Vor allem wenn für verschiedene Creep-Sorten verschiedene Wege gefunden werden sollen (shortest Path, Weg mit geringstem Schaden, ...) befürchte ich einen heftigen Einbruch der Framerate sobald Türme gesetzt oder geupgraded werden und die Suchen neu loslaufen.
(Der Interessierte sollte sich mal Desktop TD und Nanowars anschauen, bei den beiden Spielen vermute ich ganz stark Graphalgorithmen im Hintergrund)