Boost Graph Library astar and navigation mesh

Question

I'm working on a project SFML/C++, I need to generate a graph to connect the obstacles between them to facilitate pathfinding, so I am interested in generating a navigation mesh, which I will apply the boost A* algorithm. A little bit like this:

But I have many problems implementing this with the Boost Graph Library (if you have a library in mind that would be more appropriate I'm interested). First I create an adjacency_list with the appropriate structures:

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;

Then I create my graph and I add to it the vertices of my obstacles (which are simple rectangles for the moment):

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++;
}

It is now that it gets complicated, I have to browse through all my vertices and create the arcs to the neighbors of these vertices, knowing that the arcs should not go inside the obstacles... I do not see how I could do to code this with Boost, I started coding this:

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;
}

Thank you in advance.

Answer 1

I think that the use of Constrained Delaunay triangulation would solve your problem. This is nothing else than a Delaunay triangulation with the condition that some predefined edges are present in it.

Using the edges of your boundary polygon and the polygons of your obstacles as the fixed edge set one would obtain a triangulation such that it has triangles which are either completely inside an obstacle or outside. To make this a proper input for Boost only delete the edges/triangles completely inside an obstacle which is straightforward since its 2/3 vertices are vertices of one of the obstacles. Another way would be to give infinite weight for these edges such that no shortest path finding algorithm would choose it.

I think that Boost up to 1.54 does not contain an implementation for Delaunay triangulation however you could obtain one as the dual of a Voronoi diagram. This is still not enough since there is no way to set the fixed edges but I think if you add extra points to the boundary of your obstacles (close enough to each other) it might result in a triangulation which is sufficient.

There is another small and nice library poly2tri which is capable of solving exactly this problem: triangulating a polygon with holes. The output of this could be used as an input for the Boost A* algorithm. However be aware that it might not give the expected shortest path because it will jump from boundary to boundary since there were no other points in the input set. This is bad visually as well as distance wise (considering the true shortest path). You could solve this by iteratively refining the too big triangles (e.g. dividing them by the midpoints of the edges into 4 triangles until you reach some small enough size(area, edge length)).

Ultimately you could use the CGAL library which is very feature rich and could solve your problem directly. See this page on how to use it. Take a look at the figures in the Section 29.2.1 to see if this is what you are looking for.

Even though I have not personally used poly2tri, I would suggest that from the above approaches as the easiest solution.