boost圖形庫astar和導航網格

我正在開發一個項目SFML/C++，我需要生成一個圖形來連接它們之間的障礙物以方便尋路，所以我有興趣生成一個導航網格，我將應用boost A *算法。有點像這樣： navmesh boost圖形庫astar和導航網格

但我有Boost圖庫實現此的許多問題（如果你心裏有一個庫，會更適合我的興趣）。首先，我創建具有相應結構的的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::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; 
}

預先感謝您。

來源

2013-10-22 thegrandwaazoo

我認爲使用Constrained Delaunay triangulation可以解決您的問題。這只不過是一個Delaunay triangulation與條件，其中存在一些預定義的邊緣。

使用邊界多邊形的邊界和障礙物的多邊形作爲固定邊集，可以獲得三角形，使其具有完全位於障礙物內部或外部的三角形。爲了使它成爲Boost的正確輸入，只需將障礙物內部的邊緣/三角形完全刪除，因爲它的2/3個頂點是其中一個障礙物的頂點。另一種方法是給這些邊賦予無限的權重，以便沒有最短路徑搜索算法會選擇它。

我認爲提升到1.54不包含Delaunay三角測量的實現，但是您可以獲得一個作爲Voronoi圖的對偶。這還是不夠的，因爲沒有辦法設置固定邊緣，但我認爲如果你在障礙物的邊界上添加額外的點（彼此足夠接近），可能會導致足夠的三角測量。

還有另一個小而漂亮的圖書館poly2tri它是能夠解決這個問題：用孔三角形多邊形。這個輸出可以用作Boost A *算法的輸入。但請注意，它可能不會給出最短路徑，因爲它將從邊界跳到邊界，因爲輸入集中沒有其他點。這在視覺和視距方面都很差（考慮到真正的最短路徑）。你可以通過迭代地改進太大的三角形來解決這個問題（例如，將它們的邊緣中點分成4個三角形，直到達到足夠小的尺寸（面積，邊緣長度））。

最終你可以使用CGAL這個功能非常豐富的庫，可以直接解決你的問題。有關如何使用它，請參閱this page。看一下第29.2.1節中的數字，看看這是你在找什麼。

即使我沒有親自使用poly2tri，我建議從上述方法作爲最簡單的解決方案。

來源

2013-10-23 00:04:04 Sigroad

謝謝你的回答，我會嘗試poly2tri解決方案 – thegrandwaazoo

boost圖形庫astar和導航網格

回答

相關問題