Navmesh Pathfinding, Prüfung ob Einheit durch Zelle passt
Verfasst: 12.12.2011, 13:06
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
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