[graph] comment faire un AStar?
Bonsoir,
je ne parviens pas à achever mon A* avec boost.
Je me suis insipiré de la doc officielle sur boost:a_star, de celle sur boost::graph et du tuto de Matthieu, mais je bloque sur le remplissage du graphe :oops:
Voici où j'en suis:
J'ai un type Sommet et un vecteur qui contient tous mes sommets:
Code:
vector<Sommet*> sommets; // ce sont des pointeurs car en plus il y a une histoire de polymorphisme
Ensuite j'ai un vecteur d'arcs (Edge) qui représente tous les arcs de mon graphes (un arc relie deux sommets):
Code:
1
2
| typedef std::pair<Sommet*, Sommet*> Edge;
vector<Edge> edges; |
Ensuite j'ai un vecteur de coûts (le coût qu'il faut dépenser pour aller d'un sommet à un autre). Un coût est représenté par un entier:
Ensuite, je créé un graphe ainsi:
Code:
1
2
3
4
5
| // déclaration du type de mon graphe
typedef adjacency_list<listS, vecS, undirectedS, no_property, property<edge_weight_t, int> > mygraph_t;
// construction du graphe:
mygraph_t g( edges.size() ); |
Ca semble fonctionner. Ca compile et ça ne plante pas.
Mais maintenant, je ne parviens pas à le remplir. J'ai tenté plusieurs choses du style:
Code:
1
2
3
4
5
6
7
8
9
10
| // déclaration de edge_descriptor
typedef mygraph_t::edge_descriptor edge_descriptor;
// remplissage du graphe
for( size_t j = 0; j < edges.size(); ++j )
{
edge_descriptor e;
bool inserted;
tie( e, inserted ) = add_edge( edges[j].first, edges[j].second, g );
} |
Mais ça ne fonctionne pas et je ne comprends pas les erreurs affichées :oops:
Par exemple je ne comprends pas à quel endroit je dois lui dire que les sommets du graphe sont de type Sommet*.
Je ne comprends pas non plus ce que c'est que ce edge_descriptor. Et cette fonction tie() ?
Si quelqu'un a une idée, une piste, une explication ou un lien à me fournir, toute aide sera la bienvenue :D
merci.
