Boost Graph Library astar et navigation mesh
Salut !
Je travaille sur un projet de jeu en SFML qui nécessite l'utilisation d'un algorithme de pathfinding pour éviter des obstacles (dans le jeu on clique gauche sur le perso pour le sélectionner et clique droit pour le faire bouger n'importe où sur la map). J'ai donc besoin de générer un graph pour relier les obstacles entre eux pour faciliter le pathfinding, je me suis donc intéreresser à générer un navigation mesh, auquel j'appliquerai un algorithme A* présent dans boost.
L'idée au final c'est d'avoir un truc de ce style :
http://theory.stanford.edu/~amitp/Ga...d-vertices.png
Que je puisse faire mon pathfinding par rapport aux côtés et milieux des polygones.
Mais j'ai beaucoup de problèmes pour appliquer ceci avec Boost Graph Library (si vous avez une librairie en tête qui serait plus adapté je suis preneur). Je crée du coup une adjacency_list avec ses structures adaptées :
Code:
1
2
3
4
5
6
7
| struct WayPoint{
sf::Vector2f pos;
};
struct WayPointConnection{
float dist;
}; |
Code:
1
2
3
4
5
6
7
8
9
| typedef boost::adjacency_list<
boost::listS,
boost::vecS,
boost::undirectedS,
WayPoint,
WayPointConnection
> WayPointGraph;
typedef WayPointGraph::vertex_descriptor WayPointID;
typedef WayPointGraph::edge_descriptor WayPointConnectionID; |
Je crée ensuite mon graph et je lui rajoute les sommets de mes obstacles (qui sont de simples rectangles pour le moment) :
Code:
1
2
3
4
5
6
7
8
| while (i != rectangle.getPointCount())
{
sf::Vector2f pt1 (sf::Vector2f(rectangle.getPoint(i).x + mouseEvent.x, rectangle.getPoint(i).y + mouseEvent.y));
WayPointID wpID = boost::add_vertex(graph);
graph[wpID].pos = pt1;
i++;
} |
C'est maintenant que ça se complique, je dois parcourir tous mes sommets et créé des arcs avec les voisins de ces sommets, sachant que les arcs ne doivent pas passer à l'intérieur des obstacles ... Je ne vois pas comment je pourrais faire avec boost pour prendre justement les bons voisins, j'ai commencé à coder ceci :
Code:
1
2
3
4
5
6
7
| boost::graph_traits<WayPointGraph>::vertex_iterator vi, vi_end, next;
boost::tie(vi, vi_end) = vertices(graph);
for (next = vi; vi != vi_end; vi = next)
{
//je dois trouver tous les bons voisins des sommets ici ...
++next;
} |
Mais je n'arrive pas à faire quelque chose de fonctionnel ... La documentation de la Boost Graph Library n'est pas très accessible et je galère à trouver des exemples compréhensible pour générer mon graph sachant que je débute sur l'utilisation de cette lib, si vous pouviez m'aider à éclaircir je vous en serais très reconnaissant.
Merci d'avance.
