Graphenalgorithmen - Wegfindung

[Nasenbaer]

Hi,
da wir im Studium gerade beim Thema Graphen angelangt sind und uns da auch schon einige interessante Sachen angesehen haben, frage ich mich wie die Wegfindung eigentlich in Spielen z.B. Strategiespielen umgesetzt wird.

Also welche Algorithmen nutzt man da vornehmlich? Ich hab in ner Zeitschrift dazu mal gelesen, dass oft A* zum Einsatz kommt. Aber wie schnell ist sowas und müsste der nicht regelmäßig während der Verfolgung der Route neu ausgeführt werden, weil ja bspw. Einheiten den Weg versperren könnten.

[Trap]

A* ist schon die richtige Richtung. Im Detail gibt es sehr viele Sachen die man davon ausgehend optimieren kann weil man das Einsatzgebiet genau kennt und nicht unbedingt optimale Lösungen braucht (gute reichen). Ein paar Stichworte: landmark-based A*, hierarchical A*

Wegfindung mit mehreren Aktoren die sich gegenseitig blockieren können ist kein klassisches Graphenproblem mehr, das fällt ganz klar in den Bereich KI. Eine primitive Strategie dafür ist so tun als wäre jede Einheit allein und falls sich Einheiten blockieren das erkennen und sie explizit wieder auseinanderbewegen.

[Monger]

Das sieht man bei modernen Strategiespielen auch sehr schön. Die ersten C&C Teile liefen in der Regel nach dem Muster: Geh solange vorwärts bis dir jemand den Weg versperrt. Ausgehend davon wird dann den betroffenen Einheiten signalisiert, dass sie gefälligst aus dem Weg gehen sollen. Das hat dann regelmäßig zu Staus geführt.

Bei C&C Generals ist man da schon viel kleverer: da wird - abhängig von Geschwindigkeit und Entfernung der jeweiligen Einheit - schon lange vorher eine passende Meldung an die betroffene Einheit abgegeben, so dass sie ausreichend Zeit hat aus dem Weg zu gehen.
Ausserdem vermute ich, dass bei bewegten Einheiten die Pfade sozusagen "sortiert" werden. Wenn man mehrere Einheiten in die selbe Richtung schickt, fahren die auch schön parallel, und schneiden sich nicht etwa gegenseitig den Weg ab. Das kann eigentlich nur gehen, wenn die aktiven Pfade auf Überschneidungen geprüft werden, und dementsprechend verschoben werden. Sobald der Platz außenrum eng wird, funktioniert all das natürlich nicht mehr so toll...

Da steckt sicherlich noch deutlich mehr dahinter, sonst würde es bei Spielen nicht so dramatische qualitative Unterschiede in der Wegfindung geben.

[Nasenbaer]

Jo mit den Konvois hast du natürlich recht. Das würde dann ja so ein Chaos geben wie bei Dune2. *gg*
Nagut dann werde ich mir den Algo mal näher ansehen.

Aber wieso berechnen eigentlich manche Map-Editoren Pfade schon selbst. Ist das dann so ne Art Vorlage auf der die Routinen im Spiel zurückgreifen um effizienter zu laufen?

Naja wenigsten wird das Studium langsam interessanter. Vor lauter Bäumen wurd mir schon ganz schlecht. *g*

[Trap]

Nasenbaer[/POST]']
Aber wieso berechnen eigentlich manche Map-Editoren Pfade schon selbst. Ist das dann so ne Art Vorlage auf der die Routinen im Spiel zurückgreifen um effizienter zu laufen?
Welche Map-Editoren meinst du?

Da die Karte sich nach dem Erstellen nicht ändert kann man einige Sachen vorberechnen, die man dann nichtmehr im Spiel berechnen muss. landmark-based A* benutzt vorberechnete statische Daten um schneller den besten Weg zu finden.

Zum Thema mehrere autonome Einheiten sinnvoll bewegen gibt es sicher wahnsinnig viele ad-hoc Algorithmen, wie weit das systematisch analysiert worden ist weiß ich allerdings nicht, ich hab dazu noch nie irgendwas formales/systematisches gesehen.

[darph]

Ja, nun. Wegberechnung kann schon recht kompliziert werden. Der A* ist schon eine deutliche Verbesserung gegenüber zum Haifisch Dijkstra, aber wenn man da was sparen kann - warum nicht?

Insbesondere bei sehr langen Routen, kann man sich ja denken, daß es gewisse Segmente geben wird, die sehr häufig befahren werden. Autobahnen zum Beispiel - bei einer langen Strecke suchen wir uns eine Auffahrt auf die Autobahn, fahren diese ab und dann suchen wir uns eine Strecke von der Autobahn zum Ziel. Die AB entlang brauchen wir keine Route zu berechnen, das kann man speichern.

Wir mußten im Praktikum mal einen Routenplaner implementieren. Wir haben die Deutschlandkarte in Segmente unterteilt und bei diesen vom Zentrum eines jeden Segmentes zum Zentrum eines jeden anderen Segmentes Routen berechnet. Das war reichlich aufwendig, da kann man schonmal mehrere Tage rechnen lassen. Einen Teil dieser Strecke zwischen zwei Zentren (nur ein Teil weil man ja sonst gegebenenfalls erst zurück fahren müßte) wurde dann als vorberechnete Route gespeichert.

Wenn der User nun eine sehr lange Route hat berechnen wollen, konnte man die Zeit massiv verkürzen, indem man nur zwei Routensegmente berechnen mußte: Vom Start zum Aufsprungpunkt und dann vom Absprungpunkt im Zielsegment zum Ziel. Das waren kurze Routen, weil nur zwei Mal innerhalb eines, im schlimmsten Fall von zwei Segmenten gesucht werden mußte, man also nicht halb Deutschland abgrasen mußte. Die Berechnung der Strecke zwischen den Segmenten wurde dann, sie war ja schon vorberechnet, einfach dazwischen geschaltet. Das waren dann, auf einer Straßenkarte, in der Regel eben diese Autobahnabschnitte.

[Demirug]

Monger[/POST]']Bei C&C Generals ist man da schon viel kleverer: da wird - abhängig von Geschwindigkeit und Entfernung der jeweiligen Einheit - schon lange vorher eine passende Meldung an die betroffene Einheit abgegeben, so dass sie ausreichend Zeit hat aus dem Weg zu gehen.
Ausserdem vermute ich, dass bei bewegten Einheiten die Pfade sozusagen "sortiert" werden. Wenn man mehrere Einheiten in die selbe Richtung schickt, fahren die auch schön parallel, und schneiden sich nicht etwa gegenseitig den Weg ab. Das kann eigentlich nur gehen, wenn die aktiven Pfade auf Überschneidungen geprüft werden, und dementsprechend verschoben werden. Sobald der Platz außenrum eng wird, funktioniert all das natürlich nicht mehr so toll...

Ich weis zwar jetzt nicht ob C&C das so macht aber bei solchen Fällen setzt man häufig auf dynamische Gruppenbildung. Aus allen Einheiten die zum gleichen Punkt wollen wird eine Gruppe erzeugt und dann wird nur für die gesammte Gruppe ein Weg gesucht.

[Trap]

darph[/POST]']
Insbesondere bei sehr langen Routen, kann man sich ja denken, daß es gewisse Segmente geben wird, die sehr häufig befahren werden. Autobahnen zum Beispiel - bei einer langen Strecke suchen wir uns eine Auffahrt auf die Autobahn, fahren diese ab und dann suchen wir uns eine Strecke von der Autobahn zum Ziel. Die AB entlang brauchen wir keine Route zu berechnen, das kann man speichern.
Ja, das geht, ist in der Form aber eher schlecht auf RTS übertragbar. Das was du da beschreibst ist eine Variante von hierarchical A* und damit nur eine Näherungslösung für den tatsächlichen kürzesten Weg.

Andere Varianten mit vorberechneten Daten können optimale Wege garantieren und trotzdem auch sehr flott arbeiten. Siehe http://www.avglab.com/andrew/pub/reach.pdf

[Nasenbaer]

Trap[/POST]']Welche Map-Editoren meinst du?

Puuhhh weiß ich nicht mehr genau ob dass auch bei RTS Editoren gemacht wurde. Bei einigen 3D-Shootern aber auf jeden Fall obwohl das da IMO wohl nen anderen Sinn hat als das Finden kürzester Wege.

[Monger]

Demirug[/POST]']Ich weis zwar jetzt nicht ob C&C das so macht aber bei solchen Fällen setzt man häufig auf dynamische Gruppenbildung. Aus allen Einheiten die zum gleichen Punkt wollen wird eine Gruppe erzeugt und dann wird nur für die gesammte Gruppe ein Weg gesucht.
Afaik funktioniert das auch, wenn man Einheiten nacheinander auswählt und an verschiedene Orte schickt, und sie sich nur über Teilstrecken auf dem selben Weg befinden. Ich weiß nicht, ob C&C Generals da so klever ist, nur für Teilstrecken solche dynamischen Gruppen zu bilden.

Das absolute Anti-Beispiel ist ja Earth 2160. Wenn man da eine größere Gruppe nimmt und von A nach B schickt, ist es ziemlich wahrscheinlich dass die entweder gar nicht oder nur zur Hälfte ankommt. Der Rest verkeilt sich hoffnungslos.

Das Thema ist wirklich megakomplex. Der Pfad muss ja nicht nur möglichst kurz und einfach sein, sondern auch möglichst schnell und sicher. Dazu müssen die unterschiedlichen Größen, Geschwindigkeiten (und mitunter auch Wendigkeit) der einzelnen Einheiten berücksichtigt werden. Sonst passiert genau das was auf der Autobahn immer passiert, dass nämlich zwei langsame, dicke Brummer alles ausbremsen. Nur mit dem Unterschied, dass man in einem RTS in aller Regel durchaus links oder rechts vorbei könnte.

[Trap]

Nasenbaer[/POST]']Puuhhh weiß ich nicht mehr genau ob dass auch bei RTS Editoren gemacht wurde. Bei einigen 3D-Shootern aber auf jeden Fall obwohl das da IMO wohl nen anderen Sinn hat als das Finden kürzester Wege.
Das liegt zu einem großen Teil daran, dass es nicht ganz so einfach ist algorithmisch den Wegegraph aus der 3d-Geometrie zu erzeugen. Von Hand plazieren ist eine pragmatische Lösung die nicht allzu viel Arbeit macht.

[DocEW]

Seh ich das richtig, daß dieser "A*" (nie gehört) im Grunde ein Dijkstra mit Future Costs ist?
Oder postet mal bitte einen Link, da kann man so blöd bei Google nach suchen...

[Trap]

http://en.wikipedia.org/wiki/A%2A

[DocEW]

Danke für den Link, ich hatte nur in der deutschen Wikipedia über das FF-Suchfeld gesucht, und da wurde komischerweise nix gefunden.

P.S.: Der deutsche Artikel (http://de.wikipedia.org/wiki/A%2A) scheint sogar besser zu sein! ;)