1

我正在开发一个 SFML / C++ 项目，但我在 boost 图形库方面遇到了一些麻烦，特别是在 astar_search 方面。我为一个随机图和一个图生成了一个 Voronoi 图，以使用 Boost Graph Library 的 astar 方法与多边形的每个中心的中间

边缘的建立：

for (Polygon *u : this->_map->_polygons)
{
    if (u->getPolygonType() == u->GROUND)
    {
        WayPointID wpID = boost::add_vertex(graphe); 
        graphe[wpID].pos = u->getCenter();
        for (std::deque<Edge_ *>::iterator it = u->getEdges().begin() ; it != u->getEdges().end() ; ++it)
        {
            std::pair<Polygon *, Polygon *> t = (*it)->_polygonsOwn;
            WayPointID wpID2 = boost::add_vertex(graphe);

            graphe[wpID2].pos = t.second->getCenter();
            if (t.first->getPolygonType() == t.first->GROUND)
            {
                float dx = abs(graphe[wpID].pos.first - graphe[wpID2].pos.first);
                float dy = abs(graphe[wpID].pos.second - graphe[wpID2].pos.second);

                boost::add_edge(wpID, wpID2, WayPointConnection(sqrt(dx * dx + dy * dy)), graphe);              
            }

当我想绘制边缘时，边缘已正确建立：

在此处输入图像描述

所以我需要对这些边缘使用 astar 搜索，但我的代码不起作用:(

struct found_goal {}; 
class astar_goal_visitor : public boost::default_astar_visitor{
private:
typedef boost::adjacency_list<  
    boost::listS,              
    boost::vecS,                
    boost::undirectedS,         
    WayPoint,                   
    WayPointConnection          
> WayPointGraph;
typedef WayPointGraph::vertex_descriptor WayPointID;
typedef WayPointGraph::edge_descriptor   WayPointConnectionID;
WayPointGraph graphe;
WayPointID m_goal;

public:
    astar_goal_visitor(WayPointID goal) : m_goal(goal) {}

void examine_vertex(WayPointID u, const WayPointGraph &amp){ 
    if(u == m_goal)
        throw found_goal(); 
    }

};

和实施：

boost::mt19937 gen(time(0));

std::vector<WayPointID> p(boost::num_vertices(graphe)); 
std::vector<float>      d(boost::num_vertices(graphe)); 
WayPointID start = boost::random_vertex(graphe, gen);
WayPointID goal = boost::random_vertex(graphe, gen);

try {
    boost::astar_search
        (
        graphe, 
        start,  
        boost::astar_heuristic<WayPointGraph, float>(), 
                     boost::predecessor_map(&p[0]).distance_map(&d[0]).visitor(astar_goal_visitor(goal)).weight_map(boost::get(&WayPointConnection::dist, graphe))
        );

} catch(found_goal fg) { 
    std::cout << "is ok" << std::endl; 
}

永远找不到路径...如果您能帮助我了解 astar 的实现，我将不胜感激 :)/ 很抱歉这篇文章的长度 :(，boost astar 需要大量的代码实现。

先感谢您

4

1 回答 1

1

你插入了太多的顶点。比如说，你应该保留一个unordred_map<Polygon*,vertex_descriptor>. 在为给定的多边形 P 调用 add_vertex 之前，您应该首先检查 P 是否已经在地图中。如果是，使用P对应的vertex_descriptor，不要调用add_vertex。否则，调用 v= add_vertex 并将 (P,v) 对添加到地图中。祝你好运！

于 2013-11-06T08:18:06.327 回答