Boost.Graph est-il adapté ?

Bonjour à tous, je n'ai jamais utiliser boost.Graph mais je pense qu'il est approprié pour être utiliser dans mon projet.

J'essaie d'expérimenter un nouvel algorithme de Pathfinding. Voici le principe :

En 2D, si l'on considère que le temps est proportionnel à la distance alors, le chemin le plus court sera toujours :

Soit de A vers B.
Soit de A vers un sommet d'un obstacle puis vers un autre sommet et ensuite vers B.

Donc, lors du chargement d'une carte (par exemple), je précalcule toutes les distances et les chemin pour aller d'un sommet à un autre sommet.

Ensuite, quand t-on demande à aller de A vers B, je tente de A vers B directement et s'il y a un obstacle, je tente d'aller à partir de A vers tous les sommets et à partir de B vers tous les sommets. J'obtiens un algorithme en n² une fois un jeu.

Voici mon problème :

Imaginons 2 obstacles :

http://data.imagup.com/4/1108373896.png

Les chemins vert représentent tous les chemins pour aller d'un point à un autre en ligne droite.

Mais il me faut pouvoir charger tous les chemins allant de n'importe quel point à n'importe quel point. Donc par exemple, il me faut calculer le chemin le plus court pour aller de B à H sachant que je fourni une fonction qui calcule le "poids".

Voici ma question : Boost.graph est-il adapté pour, à partir d'un graphe et une fonction calculant le poids entre 2 points du graphe, calculer et conserver le chemin le plus court entre 2 points quelconques du graphes ?
Est-il adapté en performances ?

Mon objectif : pouvoir simplement avec l'aide de boost.graph avoir :

Code:

---

1 2 3 4 5 6 7

struct chemin { std::list<Point> c//Au autre. Poid p; };   std::map<std::pair<Point,Point>, Chemin> Distances;

---

Ensuite, il me suffit de fournir n'importe quelle paire allant d'un point à un autre et j'ai le chemin associé.

Merci, j'espère avoir suffisamment explicité mon problème.

N'ayant jamais utiliser les graphes, si vous pouviez me dire quel type de graphe il s'agit, ce serait apprécié.

boost::graph fourni 3 choses :
- Une définition des concepts de base que doivent fournir des graphes, quelle que soit la manière dont ils sont implémentés, éventuellement à l'aide d'adaptateurs.
- Des algorithmes classiques sur des graphes présentant ces concepts
- Des implémentations de graphes

(on retrouve le triplet itérateurs/algorithmes/conteneurs de la STL).

Si ton but est de définir ton propre algorithme, et rien d'autre, seule la partie implémentation de graphes t'intéresse, et franchement, dans ce cas, j'éviterai la complexité de boost.graph pour me faire ma propre classe à moi.

Par contre, si les algorithmes t'intéressent aussi (éventuellement en tant que brique de base pour implémenter le tien), alors boost.graph devient intéressant.

Je pense que je ne vais pas utiliser boost.Graph :
-l'apprentissage de cette bibliothèque semble long, et, bien que je pourrais mettre cet apprentissage au profit d'autres projets, je ne sais pas si cela en vaut la peine.
-Ne connaissant rien au graphes, l'utilisation de boost.graph me semble extrêmement long.
-L'algorithme, malgré l'utilisation de template chez boost devrais être plus rapide s'il est spécifique.

Cependant, si quelqu'un cerne mon problème et me confirme que boost.graph est la bibliothèque à utiliser, je regarderais plus en détail.

Citation:

---

Envoyé par NoIdea

Voici ma question : Boost.graph est-il adapté pour, à partir d'un graphe et une fonction calculant le poids entre 2 points du graphe, calculer et conserver le chemin le plus court entre 2 points quelconques du graphes ?
Est-il adapté en performances ?

---

Boost.graph pourra te calculer le plus court chemin entre deux points mais ce sera à toi de les stocker et de tous les générer. Il doit y avoir moyen de faire ça intelligemment en adaptant un algo de type Dijkstra.

Au passage, je te propose une structure de graphe tirée de libclaw qui est peut-être plus simple à aborder que les structures de Boost.graph (mais certainement pas aussi complète).