Boost Graph Bibliothek Astar und Navigation Mesh

Question

Ich arbeite an einem Projekt SFML/C++, ich muss ein Diagramm erstellen, um die Hindernisse zwischen ihnen zu verbinden, um die Pfadfindung zu erleichtern, also bin ich daran interessiert, ein Navigationsnetz zu generieren, was ich werde Wenden Sie den Boost A * -Algorithmus an. Ein bisschen wie folgt aus:

Aber ich habe viele Probleme dies mit der Boost-Graph-Bibliothek Implementierung (wenn Sie eine Bibliothek im Auge haben, die besser geeignet wäre, die mich interessieren). Zuerst habe ich eine adjacency_list mit den entsprechenden Strukturen schaffen:

struct WayPoint{ 
    sf::Vector2f pos; 
}; 

struct WayPointConnection{ 
    float dist; 
}; 

typedef boost::adjacency_list< 
    boost::listS, 
    boost::vecS, 
    boost::undirectedS, 
    WayPoint, 
    WayPointConnection 
    > WayPointGraph; 

typedef WayPointGraph::vertex_descriptor WayPointID; 
typedef WayPointGraph::edge_descriptor WayPointConnectionID; 

Dann erstelle ich meine Graph und ich füge hinzu, um es die Eckpunkte meiner Hindernisse (die für den Moment einfach Rechtecke):

while (i != rectangle.getPointCount()) { 
    sf::Vector2f pt1 (sf::Vector2f(rectangle.getPoint(i).x + mouseEvent.x, rectangle.getPoint(i).y + mouseEvent.y)); 
    WayPointID wpID = boost::add_vertex(graph); 
    graph[wpID].pos = pt1; 
    i++; 
} 

Es Jetzt, wo es kompliziert wird, muss ich durch alle meine Eckpunkte blättern und die Bögen zu den Nachbarn dieser Eckpunkte erstellen, in dem Wissen, dass die Bögen nicht in die Hindernisse gehen sollten ... Ich sehe nicht, wie ich das tun könnte Mit Boost habe ich begonnen, dies zu programmieren:

boost::graph_traits<WayPointGraph>::vertex_iterator vi, vi_end, next; 
boost::tie(vi, vi_end) = vertices(graph); 
for (next = vi; vi != vi_end; vi = next) { 
    //I need to create the good arcs ... 
    ++next; 
} 

Vielen Dank im Voraus.

Answer 1

Ich denke, dass die Verwendung von Constrained Delaunay triangulation Ihr Problem lösen würde. Dies ist nichts anderes als ein Delaunay triangulation mit der Bedingung, dass einige vordefinierte Kanten in ihm vorhanden sind.

Wenn Sie die Kanten Ihres Begrenzungspolygons und die Polygone Ihrer Hindernisse als festen Kantensatz verwenden, erhält man eine Triangulation, so dass es sich um Dreiecke handelt, die entweder vollständig innerhalb eines Hindernisses oder außerhalb liegen. Um dies zu einer richtigen Eingabe für Boost zu machen, löschen Sie die Kanten/Dreiecke vollständig innerhalb eines Hindernisses, was einfach ist, da seine 2/3 Eckpunkte Eckpunkte eines der Hindernisse sind. Ein anderer Weg wäre, diesen Kanten eine unendliche Gewichtung zu geben, so dass kein Algorithmus für die Suche nach dem kürzesten Weg sie wählen würde.

Ich denke, dass Boost bis 1.54 keine Implementierung für Delaunay-Triangulation enthält, aber Sie könnten eins als das Doppelte eines Voronoi-Diagramms erhalten. Dies ist immer noch nicht genug, da es keine Möglichkeit gibt, die festen Kanten zu setzen, aber ich denke, wenn Sie zusätzliche Punkte zur Grenze Ihrer Hindernisse hinzufügen (nahe beieinander), könnte dies zu einer Triangulation führen, die ausreichend ist.

Es gibt eine andere kleine und schöne Bibliothek poly2tri, die genau dieses Problem lösen kann: Triangulieren eines Polygons mit Löchern. Die Ausgabe davon könnte als Eingabe für den Boost A * -Algorithmus verwendet werden. Beachten Sie jedoch, dass es den erwarteten kürzesten Pfad nicht geben kann, da es von Grenze zu Grenze springen wird, da keine anderen Punkte in der Eingabe festgelegt waren. Dies ist sowohl visuell als auch in Bezug auf die Entfernung schlecht (unter Berücksichtigung des kürzesten Weges). Sie könnten dies lösen, indem Sie die zu großen Dreiecke iterativ verfeinern (z. B. indem Sie sie durch die Mittelpunkte der Kanten in 4 Dreiecke aufteilen, bis Sie eine ausreichend kleine Größe (Fläche, Kantenlänge) erreichen).

Letztendlich können Sie die CGAL Bibliothek verwenden, die sehr funktionsreich ist und Ihr Problem direkt lösen könnte. Siehe this page, wie man es benutzt. Schauen Sie sich die Zahlen in Abschnitt 29.2.1 an, um zu sehen, ob Sie danach suchen.

Obwohl ich Poly2tri nicht persönlich verwendet habe, würde ich vorschlagen, dass von den oben genannten Ansätze als die einfachste Lösung.