Algorithmus zur (Formations)wegfindung?
-
Hi,
ich überlege seit ein paar Tagen wie eine Wegfindung aussehen müsste, um eine Formation von bspw. 10 Einheiten an verschiedenen Hindernissen vorbei zum Ziel laufen zu lassen, dass sich am besten noch bewegt und was möglichst zeitsparend und trotzdem möglichst optimal ist. Ich wurde durch Empire Total war dazu angeregt, weil mir nicht so richtig klar werden wollte, wie die KI soviele Einheiten managen kann, ohne viel Rechenzeit zu verschwenden.Also hab ich mich etwas im Netz umgeschaut und belesen und ein paar Algorithmen (A*, Dijkstra und Greedy) gefunden, bzw deren Theorie, allerdings ist mir immernoch nicht ganz klar, wie das direkt funktioniert.
Der A* Algorithmus zum Beispiel berechnet ja jedes Feld mit ein. Wenn die Karte jedoch ziemlich groß ist, geht das ganz doch ziemlich in die Knie, oder nicht?
Hoffe ihr könnt mir das ein bisschen erklären.
-
Der A*-Algorithmus ist meist gut geeignet und performant genug, sofern deine Karte nicht ein gigantisches Labyrinth ist.
Hier wird er gut nachvollziehbar erklärt, wie ich finde.
Die Links am Ende führen dann zu aufbauenden Themen. Für deinen Fall könnte besonders Cooperative Pathfinding (auf dieser Seite verlinkt) interessant sein.
-
Cloppy schrieb:
Der A* Algorithmus zum Beispiel berechnet ja jedes Feld mit ein.
Soweit ich weiß nutzt gerade A* nicht unbedingt jedes Feld zur Berechnung, was im "Standardfall" wohl eine Menge Zeit gutmacht.
Hier kannst Du Dir unter http://www.trtoc.de/develop/tengine/index.htm die TEngine3 V1.400 runterladen und mal laufen lassen (hat ein Bekannter von mir gemacht)... ist schön anschaulich finde ich.
Zu Hause habe ich auf jeden Fall noch einen guten Link zum Cooperative Pathfinding (vielleicht auch zwei), werde nachher nochmal schaun und dann hier posten. Was mir jetzt gerade sonst noch einfällt und Du vielleicht schon beim Durchstöbern des Forums gefunden hast...
http://www.games-net.de/hosted/tggc/index.php?cat=5&page=3EDIT:
Hier noch die beiden Links, falls Du sie nicht schon kennst, kommt ja von einer bekannten Seite..:
http://www.gamasutra.com/view/feature/3313/coordinated_unit_movement.php
http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php
..und eventuell noch ganz generell zur Wegfindung:
http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.phpSpass haben
-
Du machst einen Kreis um deinen Formation und berechnest einen Weg fuer diesen Kreis. Dann steckst du die Formation in den Kreis und bewegst ihn. f'`8k
AutocogitoGruß, TGGC (Was Gamestar sagt...)
