Я переписываю своего бота для Google AI Challenge с Python на C ++ и хочу использовать библиотеку графов boost для обработки поиска, а не просто катать свой собственный граф и поисковый код, как я делал это ранее в Python.
Карта представляет собой простую квадратную сетку, которая оборачивается по краям.
Я раньше не использовал boost или C ++ (я знаю C довольно хорошо) и нахожу повышениедокументацию графика действительно трудно понять, поэтому мне нужна небольшая помощь.
Конкретные документы, с которыми у меня возникают проблемы:
Вот фрагмент рабочего кода 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;
}