使用边缘容器提升astar_search

我正在研究SFML/C++项目，并且我在boost图库方面遇到了一些麻烦，特别是astar_search。我生成的Voronoi图用于随机地图和的曲线图使用Boost图库的ASTAR方法与多边形的各中心使用边缘容器提升astar_search

建立边缘的中间：

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

的边缘是正确建立，当我想提请他们：

enter image description here

所以我需要用与这些边缘，但我的代码爱仕达搜索不工作:(

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需要大量的代码实现。

谢谢您提前

来源

2013-11-05 thegrandwaazoo

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

来源

2013-11-06 08:18:06

它的工作原理！非常感谢您的回答！ :) – thegrandwaazoo

使用边缘容器提升astar_search

回答

相关问题