私は、PythonからCへのGoogleのAIチャレンジ++のための私のボットを書き換えるよ、と私はちょうどではなく、経路探索を処理するために、ブーストのグラフライブラリを使用したいと(グリッド内の)以前のようにPythonで独自のグラフと検索コードをローリングしていました。経路探索ブーストグラフライブラリ
マップは、エッジの周りにラップする単純な正方形グリッドです。
私は前にブーストまたはC++を使用していない(私は非常によくCを知っている)と私は、私は少しの助けを必要と理解することは本当に難しいブーストグラフのドキュメントを見つけることです。私はとのトラブルを抱えている
特定のドキュメント:など
- 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)
(マンハッタンのヒューリスティックとの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;
}