使用邊緣容器提升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

回答

相關問題