0 c++ boost graph path-finding boost-graph
我正在将用于Google AI挑战的机器人从Python重写为C++,我想使用boost的图形库来处理路径查找,而不是像以前在Python中那样滚动我自己的图形和搜索代码.
地图是一个简单的方形网格,包裹着边缘.
我之前没有使用过boost或C++(我非常了解C)而且我发现boost图文档真的很难理解,所以我需要一些帮助.
我遇到问题的具体文档:
这是工作python代码的片段:
def do_turn(self, ants):
# update path-finding graph
for row in range(ants.rows):
for col in range(ants.cols):
key = (row, col)
self.graph[key] = []
def append_if_unoccupied(coord):
if ants.passable(coord) and coord not in ants.my_hills():
self.graph[key].append(coord)
if row - 1 >= 0:
append_if_unoccupied((row - 1, col))
else:
append_if_unoccupied((ants.rows + (row - 1), col))
if col - 1 >= 0:
append_if_unoccupied((row, col - 1))
else:
append_if_unoccupied((row, ants.cols + (col - 1)))
if row + 1 < ants.rows:
append_if_unoccupied((row + 1, col))
else:
append_if_unoccupied((row + 1 - ants.rows, col))
if col + 1 < ants.cols:
append_if_unoccupied((row, col + 1))
else:
append_if_unoccupied((row, col + 1 - ants.cols))
然后,我稍后使用shortest_path(self.graph, loc, dest)(a*使用曼哈顿启发式搜索)来获取包含到达其他地方的最短路径的列表.在C++中,我想要类似的东西(具有最短路径的向量).这是我到目前为止的代码(我只需要帮助它在没有任何障碍的情况下在基本网格上工作,我可以做其余的事情):
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
//#include <boost/graph/astar_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
// struct with .row and .col
#include "Location.h"
// might not be necessary
struct Edge {};
typedef boost::adjacency_list<
boost::listS, // container for edges
boost::vecS, // container for vertices
boost::undirectedS, // directed or undirected edges
Location, // vertex type
Edge // edge type
> Graph;
typedef Graph::vertex_descriptor VertexID;
typedef Graph::edge_descriptor EdgeID;
const int rows = 100;
const int cols = 100;
int main() {
Graph graph;
// this is probably useless since the graph stores everything
// haven't looked for a way around it yet
std::vector<std::vector<VertexID>> grid;
// create the grid/graph
for (int row = 0; row < rows; row++) {
grid.resize(rows);
for (int col = 0; col < cols; col++) {
grid[row].resize(cols);
VertexID vID = boost::add_vertex(graph);
graph[vID].row = row;
graph[vID].col = col;
grid[row][col] = vID;
}
}
// add the edges
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// add edges for the squares in the grid (it wraps around)
// right now all the squares are traversable but that won't always
// be the case
int c_row, c_col;
if (row - 1 >= 0) {
c_row = row - 1;
c_col = col;
} else {
c_row = rows + (row - 1);
c_col = col;
}
boost::add_edge(grid[c_row][c_col], grid[row][col], graph);
if (col - 1 >= 0) {
c_row = row;
c_col = col - 1;
} else {
c_row = row;
c_col = cols + (col - 1);
}
boost::add_edge(grid[c_row][c_col], grid[row][col], graph);
if (row + 1 < rows) {
c_row = row + 1;
c_col = col;
} else {
c_row = row + 1 - rows;
c_col = col;
}
boost::add_edge(grid[c_row][c_col], grid[row][col], graph);
if (col + 1 < cols) {
c_row = row;
c_col = col + 1;
} else {
c_row = row;
c_col = col + 1 - cols;
}
boost::add_edge(grid[c_row][c_col], grid[row][col], graph);
}
// having trouble figuring out use these
//boost::astar_search(graph, grid[c]
//auto indexmap = get(vertex_index, graph);
//dijkstra_shortest_paths(graph, grid[0][0], &p[0], &d[0], weightmap, indexmap,
//std::less<int>(), closed_plus<int>(),
//(std::numeric_limits<int>::max)(), 0,
//default_dijkstra_visitor());
}
return 0;
}
应该帮助:
boost::astar_search
(
m_navmesh, start,
distance_heuristic(m_navmesh, goal),
boost::predecessor_map(&p[0])
.distance_map(&d[0])
.visitor(astar_goal_visitor(goal))
.weight_map(get(&NavMeshConnection::dist, m_navmesh))
);
这个函数需要一个距离启发式,这是一个你必须自己创建的仿函数:
// euclidean distance heuristic
class distance_heuristic : public boost::astar_heuristic <NavMeshGraph, float> {
public:
distance_heuristic(const NavMeshGraph & l, TriangleDescriptor goal)
: m_graph(l), m_goal(goal)
{}
float operator()(TriangleDescriptor u) {
const NavMeshTriangle & U = m_graph[u];
const NavMeshTriangle & V = m_graph[m_goal];
float dx = U.pos.x - V.pos.x;
float dy = U.pos.y - V.pos.y;
return ::sqrt(dx * dx + dy * dy);
}
private:
const NavMeshGraph & m_graph;
TriangleDescriptor m_goal;
};
你还需要一个访客:
// visitor that terminates when we find the goal
class astar_goal_visitor : public boost::default_astar_visitor {
public:
astar_goal_visitor(TriangleDescriptor goal) : m_goal(goal)
{}
void examine_vertex(TriangleDescriptor u, const NavMeshGraph & g)
{
if (u == m_goal)
throw found_goal();
}
private:
TriangleDescriptor m_goal;
};
found_gloal可以是一个简单的结构或更复杂的东西,具体取决于你想要返回的内容:
struct found_goal {};
这样的对象被抛出访问者,所以你必须在try/catch块中包含boost :: astar_search():
try {
boost::astar_search
(
...
);
} catch (found_goal fg) { // found a path to the goal
然后在catch块中检索最佳方法:
std::list<TriangleDescriptor> shortest_path;
for (TriangleDescriptor v = goal;; v = p[v]) {
shortest_path.push_front(v);
if (p[v] == v)
break;
}
你将需要大量适应,但至少这应该足以让你的方式得到提升.
顺便说一句,Djikstra并不完全相似.它返回每个其他节点的所有可能路径.这对速度有害,但对于预处理非常好:它你的世界是静态的,你可以预先建立一个路径寻找矩阵,它将返回O(1)中最好的下一个节点.