path-finding (dans une grille) avec la bibliothèque de graphes Boost

Question

Je suis en train de réécrire mon bot pour le Google AI Challenge de Python en C++, et je veux utiliser la bibliothèque de graphes de boost pour gérer le chemin, plutôt que rouler mon propre graphique et chercher le code comme je l'ai fait auparavant en Python.

La carte est une simple grille carrée qui entoure les bords.

Je n'ai jamais utilisé boost ou C++ auparavant (je connais assez bien C) et je trouve la documentation du graphe boost très difficile à comprendre, j'ai donc besoin d'un peu d'aide.

docs spécifiques que j'ai des problèmes avec:

• 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
• etc., limité à deux liens au moment :)

Voici un extrait de le code python de travail:

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

J'utilise ensuite shortest_path(self.graph, loc, dest) plus tard (une recherche * avec une heuristique de Manhattan) pour obtenir une liste contenant le chemin le plus court vers un autre emplacement. En C++, j'aimerais quelque chose de similaire (un vecteur avec le chemin le plus court). Voici le code que j'ai à ce jour (j'ai juste besoin d'aide pour fonctionner sur une grille de base, sans aucun obstacle, je peux faire le reste):

#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

Vous n'avez pas besoin de passer à C++ pour exploiter BGL; il ya un vraiment joli enveloppant de lui pour python sous la forme de graph_tool. Comprend shortest path bien sûr.

Answer 2

devrait aider:

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

Cette fonction prend une heuristique de distance, ce qui est un foncteur que vous devez vous créer:

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

Vous devez également un visiteur:

// 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 peut être une structure simple ou quelque chose de plus complexe, selon ce que vous voulez retourner :

struct found_goal {}; 

Un tel objet est jeté dans le visiteur, donc vous devez envelopper boost :: astar_search() dans un bloc try/catch:

try { 

    boost::astar_search 
    (
     ... 
    ); 


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

La meilleure façon est ensuite récupéré dans la bloc catch:

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

Vous aurez besoin lourd adaptation, mais au moins cela devrait être suffisant pour obtenir Boost sur votre chemin ouf. Par ailleurs, Djikstra n'est pas complètement similaire. Il renvoie tous les chemins possibles de tous les autres nœuds.Ceci est mauvais pour la vitesse, mais excellent pour le pré-traitement: si votre monde est statique, vous pouvez pré-construire une matrice de pathfinding qui retournera le meilleur nœud suivant dans O (1).