Okay, ich kenne A* und den ganzen Kram, finde allerdings keine brauchbaren Informationen bezüglich Pathfinding für Navigation Meshes.
Im Prinzip will ich nur folgendes Problem möglichst Effizient und vor allen Dingen richtig lösen:

Hab mir schon Wochen Gedanken drüber gemacht, aber immer noch kein brauchbares Ergebnis. Wie kann ich sowas machen?

Siehe Anhang:

Bau dir einen Graphen (grün) mit allen möglichen Wegpunkten. Startpunkt des Pfades ist der Wegpunkt, der dem eigentlichen Startpunkt am nächsten ist und Endpunkt des Graphen ist der, der dem eigentlichen Zielpunkt am nächsten ist. Die Kantenlänge beschreibt die Kosten einer Kante. Damit kannst du nun direkt a* und ähnliches anwenden.
Rot sind in der Grafik die Wegteile, die zum Graphen dann führen, auf dem du den Pfad dann hast. Weg wäre also Rot -> Gefundener Pfad -> Rot

Vielen Dank für deine Antwort.
Leider ist diese Methode unmöglich für mich. Die Mesh ist in einem RTS relativ dynamisch und bei ~10.000 Hindernissen auf der Map müsste ich auf zu viele Nodes prüfen (scheinen insgesamt mehrere Gigabyte zu sein, die ich letztendlich dafür lesen/schreiben müsste, was perfomance technisch einfach nicht geht).
Der Weg muss perfekt sein, ich kann also keine Kompromisse wie "Einfach nur nodes in bestimmtem Radius verbinden" machen :S
Mit anderen Worten: Waypoints sind mir einfach zu ungenau

Den Navigationsgraphen könnte man bestimmt irgendwie generieren. Letztendlich wirst du nicht drumrum kommen, irgendwelche Bezugspunkte zu nehmen.
Ist der da, dann ist der Weg auch perfekt. Die Umkreisgeschichte dient nur dazu, auf möglichst kurzem Wege zum Graphen zu kommen. Wobei du da auch lieber die nächste Kante und nicht den nächsten Knoten suchen solltest, fällt mir gerade auf.

// Edit:
Tausende von Hindernissen: Wenn du Speicherprobleme bekommst, schau dir mal "Memory Bounded a*" an.

// Edit 2:
Lauter Hindernisse, die sich ändern und du kennst die Umgebung beim Loslaufen noch nicht komplett? Evtl. ist das dann etwas für dich: http://www.frc.ri.cmu.edu/~axs/doc/icra94.pdf

Das erste Problem mit Waypoints/Nodes ist, dass ich wenn ich 20.000 Nodes habe, ich alleine um das Netzwerk zu generieren, alle 20.000 Nodes gegeneinander prüfen müsste. Also 0,5 * 20.000 * 20.000 = 200.000.000 Berechnungen durchführen müsste. Der Speicherdurchsatz (ich meine die Gesamtmenge an Speicher, die ich dafür Lesen müsste) wäre allein bei 8 bytes pro node bereits bei über 1,6 GB. Dazu kommt, dass ich für die Verbindung vom Startpunkt und Zielpunkt auch jeweils nochmal gegen alle 20,000 Nodes einmal testen müsste. Würde ich das nicht machen, sondern nur "regional" testen, hätte ich am Ende nicht die Tatsächlichen Distanzen und bei einer Optimierung/Nachkorrigierung des Pfades z.B. via Raytracing würden sich die Verhältnisse zwischen den Weglängen komplett ändern und der kürzeste Pfad wäre auf einmal ein anderer. So wie in dem Bild von dir die roten Linien. Zeichnest du sie zu einem anderen Punkt auf dem Graphen, würde auf einmal ein ganz anderer Weg der kürzeste werden.

Das zweite Problem mit Waypoints ist, dass es offenbar unmöglich ist, Einheiten mit verschiedenen größen zu verwenden, ohne für jede größe ein neues Netzwerk aufbauen zu müssen.



Hm, ich hatte nicht die Menge des Speichers gemeint, sondern in erster Linie die Menge des Speichers den ich auslesen müsste. Selbst wenn ich nur 1 KB letztendlich verbrauchen würde, müsste ich doch alle 20,000 Ecken/Kanten jedes mal lesen wenn ich testen will, ob sie im Weg liegen oder nicht (um den Graphen zu bauen).



Ich schau's mir an, aber von den Bildern her sieht es mir nach Raster aus...

Du könntest ein Multi-Level Graphen nehmen. Also zunächst hast du ein grobes Nav-Mesh welches benutzt wird um die großen Hindernisse zum umfahren. Kleine Hindernisse werden hier einfach ignoriert. Ein feineres Nav-Mesh wird nur im Nahbereich benutzt, sagen wir innerhalb von 100m.

Das Verfahren wäre dann also ca. so:
Suche im feinen Nav-Mesh einen Knoten des groben Meshes der innerhalb von 100m liegt. Sobald du einmal im groben Mesh bist, bleibe da und benutze nur noch dessen Knoten bis zum Ziel. Ca. alle 50m (oder alle paar Sekunden) wiederholst du die Wegsuche und bekommst so einen neuen Pfad, der dann wieder die lokalen Hindernisse berücksichtigt.

Dieses Verfahren erlaubt es dir auch das feine Nav-Mesh dynamisch anzupassen, etwa um andere bewegliche Objekte (Fahrzeuge) zum umfahren. Wenn Speicher ein Problem sein sollte, kannst du das feine Mesh in Teile teilen und nur die gerade benötigten im Speicher halten.
Aber ich glaube das Nav-Mesh muss nicht notwendigerweise im Gigabyte-Bereich liegen. Das lässt sich sicher noch komprimieren. Z.B. würden mir da Nodes mit einem Radius einfallen. Innerhalb des Radius ist einfach alles befahrbar.

_________________
Yeah!

Mehrere Detailstufen werden das sinnvollste sein. In die gröbste würde ich nur semi-statische Objekte (Gebäude und das Terrain) reinrechnen. Damit bekommst du eine gute Heuristik für den Pfad. Dann eine weitere, wo man eventuell Einheitencluster mit einbezieht (falls du diese Daten hast) und halt die feinste, die du nur on-demand in der Nähe der zu bewegenden Einheit berechnest.

Du musst bei solchen Datenmengen die optimistische Annahme treffen, dass kleine Hindernisse in naher Umgebung auch umfahrbar sind. Dann kannst du nämlich die berechnung des Pfades sogar auf mehrere Frames verteilen und so die Last breitschmieren. So macht das nach allem was ich weiß z.B. die Spring-Engine, und die fährt damit Performance-Technisch sehr gut und vom gameplay her mindestens gut (ist halt kein Fluidsimulationspathfinder oder Flowfield, die sind das geilste).

grüße

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb