Navmesh Pathfinding, Prüfung ob Einheit durch Zelle passt

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Benutzeravatar
Brainsmith
Establishment
Beiträge: 109
Registriert: 04.09.2009, 13:52
Echter Name: Fabbo

Navmesh Pathfinding, Prüfung ob Einheit durch Zelle passt

Beitrag von 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
Path.png
Kennt jemand zufällig eine Lösung für dieses Problem? Vielen Dank im Voraus
joeydee
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von 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
Establishment
Beiträge: 303
Registriert: 15.04.2002, 15:59

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von 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.
Ein Zeiger ins Blaue ist wie ein Wegweiser nach <SEGFAULT>. Wenn du denkst, mein Name hat was mit abgefuckter Kleidung und bunten Haaren zu tun, dann kehr besser um.
Benutzeravatar
Brainsmith
Establishment
Beiträge: 109
Registriert: 04.09.2009, 13:52
Echter Name: Fabbo

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von 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

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von 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
Establishment
Beiträge: 1039
Registriert: 23.04.2003, 15:29
Kontaktdaten:

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von joeydee »

Brainsmith hat geschrieben: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?
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von Chromanoid »

Keine Ahnung ob das hier irgendwie nützlich ist, aber vielleicht hilft es/inspiriert es ja:
http://code.google.com/p/recastnavigation/
pUnkOuter
Establishment
Beiträge: 303
Registriert: 15.04.2002, 15:59

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von pUnkOuter »

Brainsmith hat geschrieben: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.
Ein Zeiger ins Blaue ist wie ein Wegweiser nach <SEGFAULT>. Wenn du denkst, mein Name hat was mit abgefuckter Kleidung und bunten Haaren zu tun, dann kehr besser um.
simbad
Establishment
Beiträge: 132
Registriert: 14.12.2011, 14:30

Re: Navmesh Pathfinding, Prüfung ob Einheit durch Zelle pass

Beitrag von 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.
Antworten