Поиск пути (в сетке) с помощью библиотеки графов ускорения

Question

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

Вот фрагмент рабочего кода 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;
}

Answer 1

Должно помочь:

    boost::astar_search
    (
        m_navmesh, start,
        distance_heuristic(m_navmesh, goal),
        boost::predecessor_map(&p[0])
        .distance_map(&d[0])
        .visitor(astar_goal_visitor(goal))
        .weight_map(get(&NavMeshConnection::dist, m_navmesh))
    );

Эта функция использует эвристику расстояния, которая является функтором, который вы должны создать самостоятельно:

// euclidean distance heuristic
class distance_heuristic : public boost::astar_heuristic <NavMeshGraph, float> {
public:
    distance_heuristic(const NavMeshGraph & l, TriangleDescriptor goal)
    : m_graph(l), m_goal(goal)
    {}

    float operator()(TriangleDescriptor u) {
        const NavMeshTriangle & U = m_graph[u];
        const NavMeshTriangle & V = m_graph[m_goal];
        float dx = U.pos.x - V.pos.x;
        float dy = U.pos.y - V.pos.y;
        return ::sqrt(dx * dx + dy * dy);
    }

private:
    const NavMeshGraph & m_graph;
    TriangleDescriptor m_goal;
};

Вам также нужен посетитель:

// visitor that terminates when we find the goal
class astar_goal_visitor : public boost::default_astar_visitor {
public:
    astar_goal_visitor(TriangleDescriptor goal) : m_goal(goal)
    {}

    void examine_vertex(TriangleDescriptor u, const NavMeshGraph & g)
    {
        if (u == m_goal)
            throw found_goal();
    }

private:
    TriangleDescriptor m_goal;
};

found_gloal может быть простой структурой или чем-то более сложным, в зависимости от того, что вы хотите вернуть:

struct found_goal {};

Такой объект добавляется в посетителя, поэтому вы должны обернуть boost::astar_search() в блок try/catch:

try {

    boost::astar_search
    (
      ...
     );


} catch (found_goal fg) { // found a path to the goal

Наилучший способ затем извлекается в блоке catch:

    std::list<TriangleDescriptor> shortest_path;
    for (TriangleDescriptor v = goal;; v = p[v]) {
        shortest_path.push_front(v);
        if (p[v] == v)
            break;
    }

Вам понадобится серьезная адаптация, но, по крайней мере, этого должно быть достаточно, чтобы получить Boost от вашего пути.

Кстати, Джикстра не совсем похожа. Он возвращает все возможные пути от каждого другого узла. Это плохо для скорости, но отлично для предварительной обработки: если ваш мир статичен, вы можете предварительно построить матрицу поиска пути, которая будет возвращать лучший следующий узел в O(1).

Answer 2

Вам не нужно переключаться на C++, чтобы использовать BGL; есть действительно хорошая упаковка для Python в виде graph_tool, Включает кратчайший путь, конечно.