Wegfindung

[Herr Doktor Klöbner]

Hallo,
seit es 3D Spiele gibt ärgere ich mich über schlechte Wegfinderoutinen, ich habe es mir in Spielen wo ich NPCs irgendwohin begleiten muss zur Angewohnheit gemacht alle 20 Sekunden zu speichern da immer noch häufig zu sehen ist das die NPCs in irgendwelche Schluchten stürzen, durchs Feuer laufen, oder irgendwo hängen bleiben, hier sehe ich auch kaum Fortschritte zwischen uralten und allerneuersten Spielen.Wo ist hier das Problem ? Kann man nicht die gesamte Spielewelt mit unsichtbaren Pfaden überziehen denen die NPCs fogen oder sehe ich das zu einfach ?

[InsaneDruid]

Botpfade nutzen die UnrealEngines, hat aber den Nachteil das es sehr aufwendig ist, und das Movement vorhersehbar wird. Grade in Strategiegames will man ja aber meist nicht, das die Einheiten alle den selben Weg nehmen. Am meisten fällt mir bei zb Panzers sehr extrem, an DRvsAK/D-Day/1944 weniger stark auf, das sich Einheiten gegenseitig blocken, das ist wohl das größte Ärgernis.

[Monger]

Also, DAS vollvermaschte Netz zu konstruieren wäre die Hölle!

Vielleicht bin ich nicht auf dem neuesten Stand, aber "Traveling Salesman Problem" ist meines Wissens bis heute unlösbar...

Soll heißen: Man kann nicht zwischen beliebigen mehreren Punkten den kürzesten Weg finden. Deshalb muss z.B. in UT2004 nach wie vor zumindest die Wegknoten von Hand gesetzt werden. Haben sie Sichtkontakt, werden sie miteinander verbunden, aber damit muss man GANZ behutsam umgehen, weil bei großen Netzen rechnen sich die Bots entweder tod, oder verlaufen sich völlig.

Und was Kollisionen angeht: Es wird ja nach wie vor mit Hitboxes gearbeitet, Pixelgenaue Abfrage wäre rechnerisch Overkill. Und da passiert es halt oft, dass entweder die Hitboxes Grenzen zeigen wo keine sind, oder der Bot versucht durch etwas durchzulaufen wo er nicht durch kann.


Es gibt auch Spiele, wo Bots sich wirklich sehr gut verhalten, aber da hat man meistens sehr viel Zeit ins Leveldesign investiert, um den Level "kindersicher" zu machen. Eine allgemeingültige Lösung die immer funktioniert, gibt es afaik bisher einfach nicht.

[Legolas]

Also, DAS vollvermaschte Netz zu konstruieren wäre die Hölle!

Vielleicht bin ich nicht auf dem neuesten Stand, aber "Traveling Salesman Problem" ist meines Wissens bis heute unlösbar...


Na so schlimm ist es nicht. Lösbar ist es auf jedenfall. Allerdings ist das TSP afaik NP-vollständig, also nur mit exponentiell steigendem Aufwand lösbar (für jeden weiteren Knoten, den man zum Problem hinzufügt, verdoppelt sich der Aufwand).

[Trap]

TSP ist aber was ganz anderes als den kürzesten Weg zwischen zwei Punkten suchen. Kürzeste Weg Suche ist polynomiell. Mit A* oder landmark basierter Suche ist es sehr schnell.
Mit landmark basierter Suche kann man in 5 ms auf einem 3 GHz P4 den kürzesten Weg zwischen 2 zufälligen Knoten in einem Graph mit 250.000 Knoten und 650.000 Kanten finden (bei Knoten die näher zusammenliegen natürlich viel schneller). Für die meisten Karten dürfte das reichen ;)
Siehe http://www.avglab.com/andrew/pub/msr-tr-2004-24.ps

Wenn sich Einheiten gegenseitig blockieren dann ist die Wegplanung schlecht, nicht die Wegfindung (sind unterschiedliche Bereiche der KI).

Das Problem beim Wegnetz von Hand erzeugen ist, dass es nicht dicht genug wird und viel Arbeit ist. Wegnetz automatisch erzeugen ist in 3D nicht einfach sauber hinzubekommen, so dass alle benutzbaren Wege gefunden werden und alle unbenutzbaren ignoriert.

[Brillus]

Fr ein Computersystem braucht man aber wohl kaum den TSM, da braucht man wohl nur schnellsten/besten weg von a nach b und das geht in O(n^2).

[Lokadamus]

Fr ein Computersystem braucht man aber wohl kaum den TSM, da braucht man wohl nur schnellsten/besten weg von a nach b und das geht in O(n^2).mmm...

Eine Wegfindung wird auch in Echzeitstrategiespiele benötigt.
Bei Baldurs Gate kann man sehr gut erkennen, dass die NPCs immer wieder versuchen, den kürzesten Weg zu nehmen, welcher gerne in kleine Lücken führt. Das Prob dabei ist, das sie von A (ihr Startpunkt, NPC selber) nach B (das Ziel) über XXX Punkte gehen und dabei der Weg immer wieder neu berechnet wird, ob irgendwie eine Person dazwischen ist oder ähnliches. Sinnvoller wäre es allerdings, den Weg von B (dem Ziel) zum Startpunkt zu berechnen, um die kleinen Lücken zu umgehen, da hierbei "feste" Wegpunkte benutzt werden könnten und diese relativ direkt angegangen werden müssten. Jeder Wegpunkt würde für eine bestimmte Richtungsänderung stehen, damit sich die Einheiten/ NPCs nicht an krummen Wänden verrennen ...

[DocEW]

Also in 2D ist's echt ziemlich einfach, da verstehe ich auch nicht, warum das manchmal nicht richtig funktioniert.
Aber in 3D ist's schon direkt was ganz anderes. Den kürzesten Weg zwischen zwei Punkten in einem Raum mit polygonellen Hindernissen zu finden, ist schon NP-vollständig. Dann wäre die Frage, wie gut und wie einfach zu implementieren irgendwelche Approximationsalgorithmen sind, keine Ahnung. Aber sicher kann man bei Computerspielen auch ein paar Vereinfachungen vornehmen, die das ganze lösbar machen (Diskretisierung der Map z.B.?).

[Trap]

@DocEW:
Diskretisierung ist das übliche Verfahren. Man erzeugt einen Wegegraph (explizit oder implizit) und sucht in dem den kürzesten Weg zwischen 2 Knoten.

Wegeplanung ist schwieriger und in Spielen deutlich schlechter gelöst.