Navmesh Pathfinding, Prüfung ob Einheit durch Zelle passt

[Brainsmith]

Hallo,
Ich schreibe derzeit an einem Pathfinding-Algorithmus. Ich benutze ein polygonales Navmesh (Zellen sind konvexe Flächen) und suche dann den kürzesten Weg über die Mittelpunkte der Verbindungen via A*-Algorithmus. Ich prüfe dabei, ob eine Einheit durch die jeweile Verbindung passt (Einheiten haben einen Kreis-Kollisionsradius). Jetzt ergibt sich aber ein Problem bei der ganzen Geschichte. Das Navmesh ist dynamisch und erzeugt dementsprechend nicht vorhersehbare Zellen und Verbindungen. Ich hatte gedacht, dass es reichen würde zu prüfen, ob die Einheit in die Zelle reinpasst. Nun kann ein konvexes Polygon aber so gebaut sein, dass die Verbindungen zwar breit sind, aber die Zelle an sich sehr schmal ist. Daraus ergibt sich ein Pfad, der von der Einheit nicht benutzt werden darf.

Habe dazu ein Bild angehangen. Legende:
Schwarz: Edges, die keine Verbindungen sind.
Orange: Verbindungen
Grün: Startpunkt
Rot: Zielpunkt
Dunkelblau: Berechnete Route
Hellblau: "Richtige" Route

Kennt jemand zufällig eine Lösung für dieses Problem? Vielen Dank im Voraus

[joeydee]

Evtl. so: alle (schwarzen) Wände entlang ihrer Normalen um den Radius der Kugel versetzen, dann ein Strahltest ob der Weg frei ist.

[pUnkOuter]

Das Navmesh in Dreiecke zerlegen, und dann gemäss joeydees Ansatz, jeweils die Eingänge und Ausgänge um den Durchmesser der Einheit verkürzen und testen ob sie noch grösser als 0 sind.

[Brainsmith]

Das hab ich schon getestet, funktioniert aber nicht immer. Man stelle sich einfach ein langes, aber schmales Dreieck vor.

Werde das wohl precomputen, wie groß die Einheit sein darf, um von Connection A nach Connection B zu kommen.

[joggel]

Das Navmesh ist dynamisch und erzeugt dementsprechend nicht vorhersehbare Zellen und Verbindungen.

Heißt das, dass die Geometrie, durch die sich der Mesh bewegt, sich wärend der Suche bzw. des Bewegens ändert?
Was Du dir evtl. mal anschauen könntest wäre OpenSteer und diese Demos. Vlt. hilft dir das.

[joeydee]

Das hab ich schon getestet, funktioniert aber nicht immer. Man stelle sich einfach ein langes, aber schmales Dreieck vor.

Wenn du die Hinderniswände entsprechend dem Radius versetzt, solltest du doch genau dann ein degeneriertes Dreieck bekommen (Streckenlänge=0 oder negierter Umlaufsinn), wenn der Kreis nirgends mehr in das Dreieck passt (also es wird tatsächlich flächenmäßig betrachtet, nicht eingangsmäßig). Die Portale müssten dann entsprechend der neuen Schnittpunkte versetzt werden, um das Dreieck richtig prüfen zu können, aber da sehe ich eigentlich keine logischen Probleme.

Oder irre ich mich da für bestimmte Fälle?

[Chromanoid]

Keine Ahnung ob das hier irgendwie nützlich ist, aber vielleicht hilft es/inspiriert es ja:
http://code.google.com/p/recastnavigation/

[pUnkOuter]

Das hab ich schon getestet, funktioniert aber nicht immer. Man stelle sich einfach ein langes, aber schmales Dreieck vor.

Werde das wohl precomputen, wie groß die Einheit sein darf, um von Connection A nach Connection B zu kommen.

Inwiefern bietet ein langes, schmales Dreieck ein Problem? Wenn die langen Seiten die Übergänge darstellen, dann geht es, sonst nicht. Kann mir das Problem gerade nicht vorstellen.

[simbad]

Ne bounding box erzeugen um schonmal eine vorprüfung zu machen. Das hat den Vorteil, das der Test recht einfach läuft, da man dann nur schnittpunkte mit den wänden prüfen muss.
Gibt es die passt die Bounding box nicht dran vorbei.
Man kann auch immer die Box zur Schmalseite ausrichten oder in jede Richtung prüfen. Selbst bei einem Kreis müsste das gehen.