Ich versuche, ein Tower Defense Spiel in Javascript zu erstellen.Masse Astar Wegfindung
Es ist alles gut abgesehen von der Wegfindung gehen ..
Ich verwende den astar Code von dieser Website: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript, die einen binären Heap verwendet (was ich glaube ziemlich optimal ist)
Das Problem i Werde ich wollen, dass Menschen den Weg der "Angreifer" blockieren können. Dies bedeutet, dass jeder "Angreifer" in der Lage sein muss, seinen Weg zum Ausgang selbst zu finden (da jemand einfach einen einzelnen "Angreifer" abschneiden könnte und er seinen eigenen Weg zum Ausgang finden müsste). Jetzt können 5/6 Angreifer jederzeit ohne Probleme den Pfad finden. Aber sagen wir, der Pfad ist für 10+ Angreifer blockiert, alle 10 müssen gleichzeitig ihr Wegsuchskript abfeuern, was den FPS auf ungefähr 1/2 pro Sekunde reduziert.
Dies muss ein häufiges Problem für jeden sein, der viele Entitäten zu jeder Zeit Pfadfindung hat, also stelle ich mir vor, es muss einen besseren Weg als mein Ansatz geben.
Meine Frage ist also: Was ist der beste Weg, Massenpfadfindungsalgorithmus zu mehreren "Bots" auf die effizienteste Weise zu implementieren.
Danke,
James
es ist wie der 'findGraphNode' in diesem Code sieht nimmt linear Zeit, während es konstante Zeit (mit einer Hash-Tabelle nehmen sollten), so dass die Implementierung bei weitem nicht optimal ist. –
Ich werde nachsehen, ob ich es ein wenig beschleunigen kann. Aber ich denke, selbst mit einer effizienteren Pfadsuche werde ich immer noch mit den langsamen Frameraten enden, wenn ich versuche, die Bots zu finden. Ich fange an zu glauben, dass meine beste Idee tatsächlich ist, die gesamte Map einmal pro Frame zu bestimmen und dann eine Richtung festzulegen auf jedem passierbaren Block für die Bots zu folgen. – james
@james, wenn dies etwas wie die meisten Tower Defense ist, mit etwa einem Bildschirm im Wert von Karte und keine komplexen Collisons (dh Bots kollidieren nicht miteinander oder andere bewegliche Objekte oder Du handhabt das separat), dann würde ich denken, Rechenpfade für die gesamte Karte wären am besten.In der Tat, Sie sollten wahrscheinlich nicht die gesamte Karte jedes Bild neu berechnen. Wenn Sie beim Erstellen eines Algorithmus vorsichtig sind, sollten Sie in der Lage sein zu bestimmen, welche Knoten von einer Benutzeränderung betroffen sind, und nur 'Upstream' von diesen Knoten neu berechnen. Hört sich interessant an! – Tim