0
)
파이썬에서 Google AI 챌린지에 대한 봇을 C++로 다시 작성하고 부스트의 그래프 라이브러리를 사용하여 경로 찾기를 처리합니다. 이전에 파이썬에서했던 것처럼 내 자신의 그래프와 검색 코드를 롤백합니다.부스트 그래프 라이브러리가있는 경로 찾기 (
지도는 가장자리를 감싸는 단순한 사각형 격자입니다.
나는 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
- 등의 조각이다 작업 파이썬 코드 :
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++에서는 비슷한 것을 원합니다 (최단 경로를 가진 벡터). 여기에 지금까지 가지고있는 코드는 (난 그냥, 내가 나머지를 할 수는 장애물없이 기본 그리드 작업지고 도움이 필요) : 당신은 ++ BGL을 악용하는 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; }