Boost Graph Library astar和导航网格

Question

我正在进行一个SFML/C++项目，需要生成一个图形来连接障碍物以便于路径规划，因此我对生成导航网格非常感兴趣，我将应用boost A*算法。就像这样: 但是我在使用Boost Graph Library时遇到了很多问题（如果您有更合适的库，请告诉我）。首先，我创建了一个具有适当结构的adjacency_list:

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;

然后我创建了一个图形，并将我的障碍物的顶点添加到其中（目前仅为简单矩形）：

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

现在变得更加复杂了，我需要浏览所有的顶点，并创建与这些顶点相邻的弧，同时不应穿过障碍物…… 我不知道如何使用Boost来编写此代码，我开始编写以下内容：

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

感谢您提前的支持。

- thegrandwaazoo

Answer 1

我认为使用约束德劳内三角剖分可以解决你的问题。这其实就是一个带有预定义边界条件的德劳内三角剖分。

通过使用边界多边形和障碍物多边形作为固定边集，可以得到一个三角剖分，使其具有完全位于障碍物内或外的三角形。为了使其成为Boost的合适输入，只需删除完全位于障碍物内部的边/三角形即可，因为它们的2/3个顶点是障碍物之一的顶点。另一种方法是对这些边赋予无限权重，以便任何最短路径查找算法都不会选择它们。

我认为Boost 1.54及以下版本没有包含德劳内三角剖分的实现，但可以将其作为Voronoi图的对偶获得。仍然不足够，因为没有办法设置固定边界，但我认为如果在障碍物边界上添加额外的点（足够靠近），可能会得到足够的三角剖分。

有另一个小而好的库poly2tri，能够解决这个问题：用孔洞三角化多边形。其输出可以作为Boost A*算法的输入。但是要注意，它可能不会给出预期的最短路径，因为它会从边界跳到边界，因为输入集中没有其他点。这在视觉上和距离上都很糟糕（考虑真正的最短路径）。您可以通过迭代地细化过大的三角形（例如通过边缘的中点将它们分成4个三角形，直到达到足够小的大小（面积、边长））来解决这个问题。

最终，您可以使用非常功能丰富的CGAL库直接解决您的问题。请参阅this page，了解如何使用它。请查看第29.2.1节中的图表，以确定是否符合您的要求。

虽然我个人没有使用过poly2tri，但我建议从上述方法中选择它作为最简单的解决方案。

- Sigroad

---

谢谢您的回答，我会尝试使用poly2tri解决方案。 - thegrandwaazoo