Boost Graph Library Astar и навигационная сетка
Я работаю над проектом SFML / C ++, мне нужно сгенерировать граф, чтобы связать препятствия между ними, чтобы облегчить поиск пути, поэтому я заинтересован в создании навигационной сетки, в которой я буду применять алгоритм A * boost.
Немного так:
Но у меня много проблем с реализацией этого с помощью 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;
}
Заранее спасибо.
Решение
Я думаю, что использование Ограниченная триангуляция Делоне решит вашу проблему Это не что иное, как Триангуляция Делоне с условием, что некоторые предопределенные ребра присутствуют в нем.
Используя ребра граничного полигона и полигоны препятствий в качестве набора фиксированных ребер, вы получите триангуляцию, в которой есть треугольники, которые либо полностью находятся внутри препятствия, либо снаружи. Чтобы сделать это правильным вводом для Boost, удалите только ребра / треугольники полностью внутри препятствия, что является прямым, поскольку его 2/3 вершины являются вершинами одного из препятствий. Другим способом было бы придать бесконечный вес этим ребрам так, чтобы его не выбрал ни один алгоритм поиска кратчайшего пути.
Я думаю, что Повышение до 1.54 не содержит реализацию триангуляции Делоне, однако вы можете получить ее как двойственную диаграмму Вороного. Этого по-прежнему недостаточно, поскольку нет возможности установить фиксированные ребра, но я думаю, что если вы добавите дополнительные точки к границе ваших препятствий (достаточно близко друг к другу), это может привести к триангуляции, которая является достаточной.
Есть еще одна маленькая и приятная библиотека poly2tri который способен решить именно эту проблему: триангуляция многоугольника с отверстиями. Выходные данные этого могут использоваться в качестве входных данных для алгоритма Boost A *. Однако имейте в виду, что это может не дать ожидаемый кратчайший путь, потому что он будет перескакивать с границы на границу, поскольку во входном наборе не было других точек. Это плохо как визуально, так и с точки зрения расстояния (учитывая истинный кратчайший путь). Вы можете решить эту проблему путем многократного уточнения слишком больших треугольников (например, разделив их на середины ребер на 4 треугольника, пока не достигнете достаточно малого размера (площадь, длина ребра)).
В конечном итоге вы могли бы использовать CGAL библиотека, которая очень многофункциональна и может решить вашу проблему напрямую. Увидеть эта страница о том, как его использовать. Посмотрите на цифры в Разделе 29.2.1, чтобы увидеть, если это то, что вы ищете.
Несмотря на то, что я лично не использовал poly2tri, я бы посоветовал использовать вышеуказанные подходы как простейшее решение.
Другие решения
Других решений пока нет …