25k Castle Siege(Improvement In AI Pathfinding)

[Robert]

Bin gerade über dieses Video auf Youtube gestoßen: 25k Castle Siege(Improvement In AI Pathfinding) - Ultimate Epic Battle Simulator - wo mir erstmal die Kinnlade runtergefallen ist. Hier die Notes unter dem Video, weil ich zu lazy bin:

Much of my hair has been pulled out over this problem since the start, but I have finally done it. Complex path-finding and navigation on a scale like no other. Each individual can now plan their own path regardless of the scenes complexity. Paths are NOT restricted/shared to groups like other games. This opens doors to infinite possibilities, with mesmerizing displays of tens of thousands of individuals taking unique approach's to complex situations. The algorithm is a highly optimized version of A*. The memory is shared, but the paths are not. This is a huge leap forward, and many doors which were closed, are now open.

[Raptor 2101]

Ich weiß nicht, was an dem Video so "kinnlade runtergefallen" sein soll. Ok sie haben einen weg gefunden A* auf >10k Agents zu scalen aber wirklich überzeugend wirkt das nicht. So wie das wirkt, haben die die nur ein voll expandiertes A* Abbild (mit einem Ziel) und jede Unit ermittelt sich die beste mögliche Route zum Ziel. Das ist nett und (bei >10k Agents) sicher eine Leistung den Algorithmus da hin zu trimmen. Aber es geht um A*, ein SPF Algorithmus bei dem "alles" expandiert wird, aus dem Jahre 1968. Dieser Algorithmus ist in der SpieleIndustrie auch nicht "unbekannt", Unreal verwendet ihn wohl schon eine geraume zeit.

Interessant wird es, wenn die Entwickler zeigen, wie sie ihre 25k in mehrere Groups aufteilen die unterschiedliche Ziele (unterschiedliche A* Instanzen) verfolgen oder gar mit "veränderlichen Karten" umgehen müssen. Dann skaliert A* extrem schlecht....

[vicsbier]

Ich weiß nicht, was an dem Video so "kinnlade runtergefallen" sein soll. Ok sie haben einen weg gefunden A* auf >10k Agents zu scalen aber wirklich überzeugend wirkt das nicht. So wie das wirkt, haben die die nur ein voll expandiertes A* Abbild (mit einem Ziel) und jede Unit ermittelt sich die beste mögliche Route zum Ziel. Das ist nett und (bei >10k Agents) sicher eine Leistung den Algorithmus da hin zu trimmen. Aber es geht um A*, ein SPF Algorithmus bei dem "alles" expandiert wird, aus dem Jahre 1968. Dieser Algorithmus ist in der SpieleIndustrie auch nicht "unbekannt", Unreal verwendet ihn wohl schon eine geraume zeit.

Interessant wird es, wenn die Entwickler zeigen, wie sie ihre 25k in mehrere Groups aufteilen die unterschiedliche Ziele (unterschiedliche A* Instanzen) verfolgen oder gar mit "veränderlichen Karten" umgehen müssen. Dann skaliert A* extrem schlecht....

So sehe ich das auch. Man kann ja recht eindeutig sehen, dass ein bestimmter Pfad gebildet und von allen eingehalten wird. Eine Koordination von einzelnen Gruppen erfolgt nicht.

[DaEmpty]

Ich sehe da schon eine gewissen Implementierungs- und Optimierungsleistung. Es diverse Methoden, um A* entsprechend zu beschleunigen. Wobei die gewählten Szenerien schon recht optimal für A* sind. Trotzdem bleibt es eine klassische Kombination von globaler Pfadsuche mit schlechter Local Avoidance. Imo ist das langfristig eine Sackgasse, die Spiele schlechter aussehen lässt als notwendig.

[lolaldanee]

also wenn man das mit Total War vergleicht, möchte man Creative Assembly sofort befehlen die Typen anzustellen

[Raptor 2101]

also wenn man das mit Total War vergleicht, möchte man Creative Assembly sofort befehlen die Typen anzustellen

gewagte These. Die KI in Total war hat (zumindestens) in meiner Wahrnehmung kein großes Problem mit Wegfindung. Die KI in TotalWar ist halt schlicht nicht sonderlich intelligent.

Wie gesagt ich spreche den Leuten nicht ihre "Implementierungsleistung", aber wir reden hier von einem Algorithmus der den "ShortestPath" wählt. Das ist weder Revolutionär, noch macht es das I in KI aus. Gut aus Sicht einiger C&C Spieler vielleicht schon...

Interessant wird es, wenn die KI entscheiden muss wohin sie ihre 25K Mannen schicken muss. Wenn sie eine Entscheidung treffen muss warum sie das macht und wann es klever ist, nicht den "Shortest path first" zu wählen.

Ein Video das ein bisschen Einblicke gibt in was ich meine: https://www.youtube.com/watch?v=d79BI890nao" onclick="window.open(this.href);return false;

[lolaldanee]

also wenn man das mit Total War vergleicht, möchte man Creative Assembly sofort befehlen die Typen anzustellen

gewagte These. Die KI in Total war hat (zumindestens) in meiner Wahrnehmung kein großes Problem mit Wegfindung. Die KI in TotalWar ist halt schlicht nicht sonderlich intelligent.

also in meiner wahrnehmung ist die KI bei allem was nicht dem Typ "offener Feldschlacht auf Ebene" entspricht heillos überfordert - vor allem auf meine Erfahrungen mit Medieval 2 begründet, die Regimenter kommen schon irgendwie durch Burgen und Städte, aber Sinnvoll sind ihre gewählten Wege meist nicht

[Raptor 2101]

also in meiner wahrnehmung ist die KI bei allem was nicht dem Typ "offener Feldschlacht auf Ebene" entspricht heillos überfordert - vor allem auf meine Erfahrungen mit Medieval 2 begründet, die Regimenter kommen schon irgendwie durch Burgen und Städte, aber Sinnvoll sind ihre gewählten Wege meist nicht

Das mein ich ich ja. Die Regimenter (Agents/Groups) finden ihren weg zum Ziel. Das ist ein seit spätestens 1970 gelöstes Problem. Jetzt muss nur noch das Clipping/Collission-Detection passen (Wegfindung "ermittelt" sie kommt um die Ecke, PhysikEngine ist da anderer Meinung...) und jede Einheit kommt ans Ziel.

KI wie sie der Spieler versteht, versteht das Schlachtfeld, hat einen "Plan"/übergeordnetes Ziel und trifft Aufgrund dessen Entscheidungen. Bei Total War merkt man gut, das die KI auf dem offenen Schlachtfeld eine Handvoll regeln beherrscht, die "erfolgversprechend" sind. Die spult sie runter. Das war bestimmt schon kompliziert genug das zu implementieren, aber wirklich Konkurenzfähig ist die KI nicht. Im Letzten Teil den ich gespielt habe (Rome2/attila), hat sie immer noch nicht, das Gelände ihn ihre Überlegungen einbezogen. Spätestens wenn Engstellen hinzukommen, war es ganz aus. Die KI kommt mit der komplexen Spielmechanik nicht klar...