path-finding (in a grid) with The Boost Graph Library

0
votes

I'm rewriting my bot for the Google AI Challenge from Python into C++, and I want to use boost's graph library to handle the path-finding, rather than just rolling my own graph and search code like I did before in Python.

The map is a simple square grid that wraps around the edges.

I haven't used boost or C++ before (I do know C quite well) and I'm finding the boost graph documentation really hard to understand so I need a little help.

Specific docs that I'm having trouble with:

Here's a snippet of the working python code:

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))

I then use shortest_path(self.graph, loc, dest) later on (a* search with a Manhattan heuristic) to get a list containing the shortest path to somewhere else. In C++, I'd like something similar (a vector with the shortest path). Here's the code I have so far (I just need help getting it working on a basic grid without any obstacles, I can do the rest):

#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;
}
2
c++boostgraphpath-findingboost-graph

2 Answers

5
votes

Should help :

    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))
    );

This function takes a distance heuristic, which is a functor that you have to create yourself : 

// 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;
};

You also need a visitor : 

// 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 can be a simple struct or something more complex, depending on what you want to return : 

struct found_goal {};

Such an object is thrown in the visitor, so you have to wrap boost::astar_search() in a try/catch block : 

try {

    boost::astar_search
    (
      ...
     );


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

The best way is then retrieved in the catch block : 

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

You will need heavy adapting, but at least this should be enough to get Boost out ouf your way.

By the way, Djikstra is not completely similar. It returns all the possible paths from every other node. This is bad for speed, but excellent for pre-processing : it your world is static, you can pre-build a pathfinding matrix which will return the best next node in O(1).

3
votes

You don't need to switch to C++ to exploit BGL; there is a really nice wrapping of it for python in the form of graph_tool. Includes shortest path of course.