Tutoriel Boost Graph Library


Boost, c'est le bien, et la BGL ne fait pas exception à la règle. BGL permet d'utiliser des algorithmes de graphes précodés en l'adaptant à nos besoins via les templates, et économise beaucoup de temps de développement et de debug.
C'est bien beau, mais encore faut-il que les puissants concepts utilisés pour faire fonctionner la librairie soient bien documentés. Or, la documentation de la BGL est tout simplement ignoble :

  • Elle est très peu connexe. Par exemple, il y a un unique lien vers la table des matières.
  • Elle est peu explicite. Par exemple, dans l'interface de l'algorithme de dijkstra, on peut trouver un bgl_named_parameters. Il faut se lever de bonne heure pour trouver ce que c'est.
  • Les exemples sont rares et peu explicites. Le seul exemple de l'algorithme A* est peu commenté (et encore moins aux parties les plus dures), démontre deux autres features qui n'ont rien à voir, utilise l'interface obsolète et non recommandée de la lib, et complique le tout avec une autre couche de templates totalement inutile pour un tuto qui se veut simple.

Ce tuto ci se veut simple. Il présente une des milliers de façons de procéder, que je considère comme simple, lisible et maintenable. Tous les membres du namespace boost seront préfixés par boost:: afin de savoir qu'est-ce qui est à nous et qu'est-ce qui est à Boost.

Il est basé sur le cas suivant : on a un graphe de waypoints, et on veut utiliser l'algorithme A* (qui utilise une bonne partie des concepts importants de la lib). Dans un premier temps, dans un souci de simplicité, on va utiliser une heuristique par défaut, qui rend toujours zéro. On verra par la suite comment l'adapter.

On va avoir besoin de deux headers boost:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>

On va maintenant définir les structures nécessaires à définir notre graphe :

// Un waypoint
struct WayPoint{
    Vector3f pos;
    // et éventuellement d'autres informations (crouch, hide, camp, ...)
};
 
// Une liaison entre deux waypoints
struct WayPointConnection{
    float dist;
    // idem
};

On va maintenant déclarer le type de notre graphe. On va utiliser une adjacency_list, qui est un peu un graphe à tout faire. Ce n'est pas le plus optimisé dans tous les cas, mais il est très versatile et convient très bien ici.

typedef boost::adjacency_list<  // adjacency_list est un template qui dépend de :
    boost::listS,               //  le conteneur utilisé pour les arcs partant d'un sommet. Ici, std::list.
    boost::vecS,                //  le conteneur utilisé pour contenir tous les sommets du graphe. Ici, std::vector.
    boost::undirectedS,         //  le type des arcs. Pourrait être boost::directedS.
    WayPoint,                   //  le type qui décrit un sommet.
    WayPointConnection          //  le type qui décrit un arc.
> WayPointGraph;

Les deux premiers paramètres influent grandement sur l'organisation mémoire et les performances de graphe. Selon les applications, une liste, un vecteur, un set, une map, ... sera plus approprié. Pour plus d'information, voir la doc.

On déclare aussi des raccourcis pour les IDs de sommets et d'arcs (en fait, ce sont des unsigned int)

typedef WayPointGraph::vertex_descriptor WayPointID;
typedef WayPointGraph::edge_descriptor   WayPointConnectionID;

On va pouvoir instancier notre graphe.

WayPointGraph graphe;

On commence par rajouter tous les sommets :

for (tous nos sommets S){
    WayPointID wpID = boost::add_vertex(graphe); // wp est l'indice d'un nouveau sommet qui a été ajouté dans graphe
    graphe[wpID].pos = la position du sommet S    // graphe[ un WayPointID ] est un WayPoint. On peut donc régler sa position de cette manière.
}

Maintenant, on peut les relier par des arcs. Là, c'est à vous de savoir où vont les arcs, boost ne va pas le deviner tout seul...

for (tous nos sommets U){ // petit changement de notation, dans boost un arc est souvent décrit entre deux sommets u et v.
    for (tous les voisins V de U){ // C'est à vous de savoir quels sont les voisins de U.
 
        WayPointID u = indice de U; // soit c'est le int du for(), soit il faut y accéder via un autre vector. Cf les notes plus bas.
        WayPointID v = indice de V;
 
        WayPointConnectionID edge;
        bool ok;
        boost::tie(edge, ok) = boost::add_edge(u,v, graphe); // boost::add_edge renvoie une std::pai>WayPointConnectionID,bool>. C'est compliqué à écrire, alors on laisse boost::tie le faire pour nous.
 
        if (ok)  // Si le graphe a bel et bien été ajouté ( pas de doublon, par exemple, sauf si spécifié dans le typedef de WayPointGraph )
        graphe[edge].dist = Distance(graphe[u].pos, graphe[v].pos); // Longueur d'un arc = distance euclidienne entre les deux sommets u et v.
 
    }
}

Plusieurs choses sont à remarquer :

  • Personnellement, j'ai utilisé le fait que WayPointID est en fait un int et que dans mon double for(), j'utilise un int pour accéder au waypoint. C'est pas très propre, mais ça évite l'utilisation d'un vector en plus.
  • graphe[edge] ( edge étant un WayPointConnectionID ) est un WayPointConnection, alors que graphe[u] (u étant un WaypointID) est un WayPoint. On peut donc accéder directement à leurs membres.
  • Cette dernière remarque est très importante. Cette syntaxe est très appréciable, elle évite d'utiliser les incompréhensibles boost::property_map, elle oblige seulement à avoir un compilateur récent. GCC et Visual s'en sortent très bien.

Pour information, mon code à moi ressemble à ça :

for (int i=0; i<indices.size()/3; i++){
    ConnectiviteTriangle connectivity;
    fillconnectivityinfo(i, connectivity, indices);
    for (int c=0; c!=3; c++){
        if (connectivity.connexe[c]!=-1){
        TriangleDescriptor u = i;
        TriangleDescriptor v = connectivity.connexe[c];

La syntaxe est moyennement cool, mais j'espère que ça vous aidera à mieux comprendre.

Ok, donc maintenant notre graphe a des sommets et des arcs. On va pouvoir faire du pathfinding !

Pour ça, on va avoir besoin de quelques structures :

// Une instance de cette structure sera lancée en exception quand on aura trouvé un chemin
struct found_goal {};
 
// Le visiteur, dont le but est de définir une fonction examine_vertex qui dit si on est arrivé au but.
// Le but est spécifié via le constructeur.
class astar_goal_visitor : public boost::default_astar_visitor{
public:
    astar_goal_visitor(WayPointID goal) : m_goal(goal) {}
 
    void examine_vertex(WayPointID u, const Graph &amp; g){ // Le const est important.
        if(u == m_goal)
            throw found_goal(); // On sort en lancant une exception. C'est moche mais c'est comme ça.
        }
private:
    WayPointID m_goal;
};

Il faut maintenant trouver notre point de départ et notre point d'arrivée. C'est votre problème, mais il faut arriver à quelque chose du style :

TriangleDescriptor goal = ...
TriangleDescriptor start = ...

Ok, on y va :

// Deux vecteurs qui vont servir à sauvegarder le résultat de la recherche
vector<WayPointID> p(boost::num_vertices(graphe)); // Les prédécesseurs
vector<float>      d(boost::num_vertices(graphe)); // Les distances
 
try { // Encore une fois, la découverte d'un chemin est signalée par une exception, donc il faut un try/catch.
    boost::astar_search
    (
        graphe, // notre graphe
        start,  // notre point de départ
        boost::astar_heuristic<NavMeshGraph, float>(), // Une heuristique bidon qui renvoie toujours 0
        boost::predecessor_map(&p[0]).distance_map(&d[0]).visitor(astar_goal_visitor(goal)).weight_map(boost::get(&WayPointConnection::dist, graphe)) // Voir plus bas
    );
 
} catch(found_goal fg) { // On a trouvé un chemin
    // On suit le chemin trouvé dans le sens inverse
    std::list<WayPointID> shortest_path;
    for(WayPointID v = goal;; v = p[v]) {
        shortest_path.push_front(v);
        if(p[v] == v)
            break;
    }
 
    // et on l'affiche.
    std::list<WayPointID>::iterator spi = shortest_path.begin();
    for(++spi; spi != shortest_path.end(); ++spi)
        Log(*spi);
    Log("Total travel time: " , d[goal] );
}

Remarque sur la ligne bizarre:

    - Ce ne sont pas des virgules, ce sont des points ! Il s'agit d'un seul objet auquel on rajoute plein de propriétés. Cette syntaxe est par exemple utilisée dans la création d'interfaces graphiques : monmenu.addoption("option1").addoption("option2") etc
    - A* a besoin de ces quatre propriétés : une map de prédécesseurs, une map de distances, une map de poids, et un visiteur.
    - La map de poids est intrisèque au graphe : elle est stockée dans le champ dist des arcs. Mais Boost ne peut pas deviner tout seul que c'est cette variable qu'il faut lire, donc on le lui dit avec boost::get(&WayPointConnection::dist, graphe)

  • Le visiteur est initialisé avec le goal pour pouvoir lancer son exception si il y a réussite.

Vous avez économisé 4 heures de prise de tête avec la doc de BGL, autant d'implémentation de l'A* si vous l'aviez codé vous même, et autant de débug que vous n'aurez jamais à faire : un des grands intérêts des templates, c'est que comme en OCaml, quand ça compile, ça marche (souvent) ^^.

Voyons maintenant comment améliorer un peu notre heuristique : pour l'instant, on n'a fait qu'un parcours brutal de l'arbre, ça ne valait pas trop le coup.
Cela va bien sûr passer par une nouvelle structure :

class distance_heuristic : public boost::astar_heuristic <WayPointGraph, float>{
public:
    // De la même manière que tout à l'heure, on passe les données dont il aura besoin dans son foncteur à la construction.
    distance_heuristic(const WayPointGraph & l, WayPointID goal)
    : m_graph(l), m_goal(goal) {}
 
    float operator()(WayPointID u)
    {
        const WayPoint & U = m_graph[u];
        const WayPoint & 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 WayPointGraph & m_graph;
    TriangleDescriptor m_goal;
}

m_graph peut être remplacé ( en changeant le constructeur et l'opérateur ) par n'importe quoi qui vous permette d'obtenir la position d'un vertex à partir de son identifiant. Cela peut être comme ici le graphe lui-même, mais aussi les données à partir duquel il a été construit, etc.

Il suffit maintenant de remplacer boost::astar_heuristic() par distance_heuristic(graphe, goal) dans l'appel au A*.

Oh, et au fait : les waypoints ça pue, utilisez des navmeshes.

Discussion sur le forum

, , ,

  1. #1 by Alp Mestan - septembre 28th, 2009 at 00:35

    Chapeau, billet très intéressant, et effectivement la doc sur BGL est à la fois rare et de qualité... criticable.

  2. #2 by nicolas66 - décembre 2nd, 2009 at 00:37

    @Alp > critiquable* ;)

(will not be published)