用Boost图形库查找路径(在网格中)

Question

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

这张地图是一个简单的方形网格，环绕着边缘。

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

我遇到麻烦的具体文档：

• paths.html
• 0/libs/图/例/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;
    }

你将需要大量的适应，但至少这应该是足够的，从你的方式得到推动。

顺便说一句，贾克斯特拉并不完全相似。它从每个其他节点返回所有可能的路径。这对速度不好，但对于预处理很好:您的世界是静态的，您可以预先构建一个路径查找矩阵，它将返回O(1)中最好的下一个节点。

Answer 2

您不需要切换到C++来利用BGL；有一个，真正的，，很好的包装，用于python，以graph_tool的形式。当然包括最短路径。