title: Boost Graph Library astar and navigation mesh
body: <p>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:
  <img src="https://i.stack.imgur.com/fEgLf.png" alt="navmesh"></p>
  
  <p>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:</p>
  
  <pre><code>struct WayPoint{
      sf::Vector2f pos;
  };
  
  struct WayPointConnection{
      float dist;
  };
  
  typedef boost::adjacency_list&lt;
      boost::listS,
      boost::vecS,
      boost::undirectedS,
      WayPoint,
      WayPointConnection
      &gt; WayPointGraph;
  
  typedef WayPointGraph::vertex_descriptor WayPointID;
  typedef WayPointGraph::edge_descriptor   WayPointConnectionID;
  </code></pre>
  
  <p>Then I create my graph and I add to it the vertices of my obstacles (which are simple rectangles for the moment):</p>
  
  <pre><code>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++;
  }
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>boost::graph_traits&lt;WayPointGraph&gt;::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;
  }
  </code></pre>
  
  <p>Thank you in advance.</p>