Pathfinding + local-Avoidance

Da mir bei meinem letzten Problem hier schon sehr gut weitergeholfen wurde ( http://www.c-plusplus.net/forum/325559 ), dachte ich mir, da ich mir nun schon zu lange den Kopf darüber zerbreche, dass ich euch nochmals um Rat frage

Mein Projekt macht sehr gute fortschritte und habe nun vor in den Semesterferien eine erste Alpha-Version fertig zu stellen. dafür fehlt jedoch noch eine sehr wichtige Sache: Local-Avoidance.

Wenn eine Einheit von A nach B läuft, wird per Pathfinding auf Grundlage eines Gitters ein Pfad berechnet, der im Anschuss etwas geglättet wird (Komme ich auf direktem Weg auch von A nach C, anstatt von A über B nach C -> B wird entfernt). Das Glätten hat aktuell noch ein paar Macken und werde es auf jeden Fall noch irgentwann überarbeiten, dass hat jedoch erstmal geringere Priorität. Ich erhalte also ein Pfad aus Punkten, welche die Einheit folgen sollte.

Derzeit werden jedoch andere Einheiten in das Pathfinding nicht miteinbezogen, d.h. Einheiten können ungehindert durcheinander durch laufen, was natürlich nicht sein soll

Was vorher noch zu erwähnen ist: Es gibt im prinziep nur 2 Collisionsobjete: Quadrate (das Gitter selbst ...) und Kreise (Einheiten). Ziel soll es sein, dass eine Einheit entlang eines Pfades möglichst "sicher" ans Ziel kommt. Dabei kann die Einheit ruhig mal kurz stehen bleiben, sich um 180° drehen, etc... Es muss nicht schön aussehen! Vergleich: Warcraft 3

Mein aktueller Ansatz sieht wie folgt aus, der bei Einheiten die alle in etwa in die gleiche richtung laufen sehr gut funktioniert:
Mit jeder Frame (ca. 30x pro Sec) werden die neuen positionen der Einheiten bestimmt. Dabei werden die Positionen der Einheiten, die am nächsten an ihrem Ziel sind zuerst bestimmt. Wenn eine Einheit nun mit einer Anderen Collidieren würde, bleibt sie stehen, und hofft dass sie in der nächsten Frame weiter laufen kann wenn vor ihr wieder ein wenig Platz ist.

Wenn nun jedoch zwei Einheiten entgegengesetzt laufen und collidieren, bleiben sie auf ewig zusammen, denn egal welche Einheit nun zuerst laufen würde, sie würde immer wieder mit der anderen collidieren.

Ich suche nun nach einem möglichst schlichten Weg, dieses Problem zu umgehen. Ein Ansatz ist, entlang der Senkrechte der Geraden zwischen den Mittelpunkten der beiden Einheiten laufen zu lassen. Einfach gesagt: Brühren sich zwei Einheiten und laufen in entgegen gesetzter Richtung, dann läuft die eine nach linkt, die andere nach rechts (als Beobachter betrachtet). Bei zwei Einheiten funktioniert das weiterhin einwandfrei, bei mehreren Einheiten wirds jedoch wieder problematisch.

Ein anderer Ansatz wäre um jede Einheit ein feineres Gitter zu nutzen, auf dem dann Teile als nicht begehbar markiert werden, wenn andere Einheiten auf diesen besetzen. So könnte ich dann per A* sehr einfach ein Weg um die Einheiten finden. Ich glaube nur, dass das ganze ein wenig zu rechenintensiv werden könnte. Es sind zwar nur sehr wenige Einheiten im Spiel: mach 10 Spieler mit je ca 5-10 Einheiten, kann mir jedoch vorstellen wenn die alle dann mal aufeinander Treffen könnte meine CPU explodieren. Vorteil ist natürlich dass das ganze sehr einfach zu implementieren ist und locale Minima werden (je nach größe des Gitters) oft vermieden.

Zu meinem Problem: Ich suche einen geeigneten Ansatz und hoffe, dass jemand der mal das gleiche Problem hatte, ein paar Tipps für mich hat

rapso

wie machen es denn andere RTS, z.B. Warcraft 3?

Wenn ich das wüsste...

rapso

wieso vergleichst du das nicht auch, du must doch wenigstens ein RTS haben in dem du das ausprobierst.

das ganze ist kein coding problem, sondern ein konzeptuelles game design problem. zu implementieren was du vor hast ist vermutlich einfach, wenn du erstmal weisst was du vor hast und was gibt es zeitsparendes das zu entscheiden als bei einem existierenden spiel nachzusehen?

Achso, hab vllt die Frage falsch verstanden.

Ich habe versucht zu erkennen, wie das Pathfinding in SC2, WC3 und DotA2 funktioniert. Auf jeden fall scheinen sie eine globale und lokale Phase zu haben. Global wird ein Pfad ohne berücksischtigung auf dynamische Objekte berechnet. Lokal wird dann dynamischen Einheiten ausgewichen. Wie die lokale Phase jedoch bei diesen Spielen funktioniert konnte ich nicht wirklich heraus bekommen.