c++ - 使用 The Boost Graph Library 寻路(在网格中)

Question

我正在为 Google AI Challenge 将我的机器人从 Python 重写为 C++，我想使用 boost 的图形库来处理路径查找，而不是像以前在 Python 中那样滚动我自己的图形和搜索代码.

map 是一个简单的方形网格，环绕着边缘。

我之前没有使用过 boost 或 C++(我对 C 非常了解)，我发现 boost graph 文档真的很难理解，所以我需要一点帮助。

我遇到问题的特定文档:

• 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++ 中，我想要类似的东西(具有最短路径的 vector )。这是我目前的代码(我只需要帮助让它在没有任何障碍的情况下在基本网格上运行，我可以完成其余的):

#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 block 中:

try {

    boost::astar_search
    (
      ...
     );


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

然后在 catch block 中检索最佳方法:

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

你将需要大量的适应，但至少这应该足以让 Boost 摆脱你的阻碍。

顺便说一下，Djikstra 并不完全相似。它从每个其他节点返回所有可能的路径。这对速度不利，但对预处理非常有利:如果您的世界是静态的，您可以预先构建一个寻路矩阵，它将返回 O(1) 中的最佳下一个节点。