Boost Graph Library astar和导航网格-Java 学习之路

我正在研究SFML / C项目，我需要生成一个图形来连接它们之间的障碍以方便寻路，所以我有兴趣生成一个导航网格，我将应用boost A *算法 . 有点像这样：
navmesh

但是我在使用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;
}

先感谢您 .

1 回答

3

我认为使用Constrained Delaunay triangulation可以解决您的问题 . 这只不过是Delaunay triangulation，条件是它中存在一些预定义的边 .

使用边界多边形的边缘和障碍物的多边形作为固定边缘集，可以获得三角剖分，使得它具有完全位于障碍物内部或外部的三角形 . 为了使其成为Boost的正确输入，仅在障碍物内完全删除边缘/三角形，这是直截了当的，因为其2/3顶点是其中一个障碍物的顶点 . 另一种方法是为这些边缘赋予无限权重，使得没有最短路径寻找算法会选择它 .

我认为Boost高达1.54并不包含Delaunay三角测量的实现，但是你可以获得一个作为Voronoi图的对偶 . 这仍然是不够的，因为没有办法设置固定的边缘，但我认为如果你在障碍物的边界上添加额外的点（彼此足够接近），它可能会导致三角测量足够 .

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

最终你可以使用功能丰富的CGAL库，可以直接解决你的问题 . 有关如何使用它，请参阅this page . 看看第29.2.1节中的数字，看看这是否是您正在寻找的 .

即使我没有亲自使用poly2tri，我建议从上述方法作为最简单的解决方案 .

回复于 2024-04-25T20:48:46+08:00

Boost Graph Library astar和导航网格

1 回答

相关问题