我正在将我的 Google AI Challenge 机器人从 Python 重写为 C++，我想使用 boost 的图形库来处理路径查找，而不是像以前在 Python 中那样滚动我自己的图形和搜索代码。
该地图是一个简单的方形网格，围绕着边缘。
我以前没有使用过 boost 或 C++（我确实非常了解 C），而且我发现 boost graph 文档真的很难理解，所以我需要一点帮助。
我遇到问题的特定文档：
- http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/dijkstra_shortest_paths.html
- http://www.boost.org/doc/libs/1_47_0/libs/graph/example/dijkstra-example.cpp
- 等等，目前仅限于两个链接:)
这是工作 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)稍后会使用（使用曼哈顿启发式的*搜索）来获取包含到其他地方的最短路径的列表。在 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;
}