Thư viện đồ thị Boost astar và lưới điều hướng

Question

Tôi đang làm việc trên dự án SFML/C++, tôi cần tạo biểu đồ để kết nối các chướng ngại vật giữa chúng để tạo điều kiện thuận lợi cho đường dẫn, vì vậy tôi quan tâm đến việc tạo lưới điều hướng áp dụng thuật toán tăng A *. Một chút giống như sau:

Nhưng tôi có nhiều vấn đề khi triển khai thư viện đồ thị tăng cường này (nếu bạn thích thư viện). Trước tiên tôi tạo ra một adjacency_list với các cấu trúc thích hợp:

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; 

Sau đó, tôi có thể tạo biểu đồ của tôi và tôi thêm vào đó các đỉnh của chướng ngại vật của tôi (mà là hình chữ nhật đơn giản cho thời điểm này):

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

Nó bây giờ là nó trở nên phức tạp, tôi phải duyệt qua tất cả các đỉnh của tôi và tạo ra vòng cung cho những người hàng xóm của những đỉnh này, biết rằng các vòng cung không nên đi vào trong chướng ngại vật ... Tôi không thấy làm thế nào tôi có thể làm mã này với Boost, tôi bắt đầu viết mã này:

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

Cảm ơn bạn trước.

Answer 1

Tôi nghĩ rằng việc sử dụng Constrained Delaunay triangulation sẽ giải quyết được sự cố của bạn. Đây là không có gì khác hơn là một Delaunay triangulation với điều kiện là một số cạnh được xác định trước có mặt trong nó.

Sử dụng các cạnh của đa giác ranh giới và đa giác của các chướng ngại vật của bạn vì cạnh cố định đặt một hình tam giác sao cho nó có hình tam giác nằm bên trong một chướng ngại vật hoặc bên ngoài. Để thực hiện điều này một đầu vào thích hợp cho Boost chỉ xóa các cạnh/hình tam giác hoàn toàn bên trong một chướng ngại vật đơn giản vì 2/3 đỉnh của nó là đỉnh của một trong các chướng ngại vật. Một cách khác là để cung cấp cho trọng lượng vô hạn cho các cạnh như vậy mà không có thuật toán tìm đường dẫn ngắn nhất sẽ chọn nó.

Tôi nghĩ rằng Tăng lên đến 1,54 không chứa một triển khai cho tam giác Delaunay tuy nhiên bạn có thể có được một như là hai của một sơ đồ Voronoi. Điều này vẫn chưa đủ vì không có cách nào để thiết lập các cạnh cố định nhưng tôi nghĩ nếu bạn thêm các điểm phụ vào ranh giới của các chướng ngại vật của bạn (đủ gần nhau) có thể dẫn đến một tam giác đủ.

Có một thư viện nhỏ và đẹp khác poly2tri có khả năng giải quyết chính xác vấn đề này: triangulating một đa giác có lỗ. Đầu ra của điều này có thể được sử dụng làm đầu vào cho thuật toán Boost A *. Tuy nhiên, lưu ý rằng nó có thể không cung cấp cho đường dẫn ngắn nhất được mong đợi vì nó sẽ nhảy từ biên này sang ranh giới vì không có điểm nào khác trong tập hợp đầu vào. Điều này là xấu trực quan cũng như khoảng cách khôn ngoan (xem xét con đường ngắn nhất thực sự). Bạn có thể giải quyết điều này bằng cách tinh chỉnh lại các hình tam giác quá lớn (ví dụ: chia chúng bằng các điểm giữa của các cạnh thành 4 hình tam giác cho đến khi bạn đạt đến một kích thước đủ nhỏ (diện tích, độ dài cạnh)).

Cuối cùng, bạn có thể sử dụng thư viện CGAL rất giàu tính năng và có thể giải quyết trực tiếp vấn đề của bạn. Xem this page về cách sử dụng. Hãy xem các số liệu trong Phần 29.2.1 để xem đây có phải là những gì bạn đang tìm kiếm hay không.

Mặc dù tôi đã không sử dụng cá nhân poly2tri, tôi sẽ gợi ý rằng từ các phương pháp trên là giải pháp đơn giản nhất.