GoogleAIチャレンジ用のボットをPythonからC++に書き直しています。以前のPythonのように自分のグラフと検索コードをロールするのではなく、Boostのグラフライブラリを使用してパスファインディングを処理したいと考えています。
マップは、エッジを囲む単純な正方形のグリッドです。
私はこれまでブーストや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
- など、現時点では2つのリンクに制限されています:)
動作する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;
}