cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 24 févr. 2006 à 09:39
L'algo de Dijkstra impose que les poids entre les noeuds ne soient pas négatifs, mais ils peuvent être nuls. Tu devrais donc associer une valeur négative (par exemple, -1) aux poids des connexions absentes. Tu ne te priverais alors pas de la liberté de faire des connexions "gratuites", ce qui peut arriver (téléporteur par exemple).
Aussi, je ne pense pas que ta structure de données pour sauvegarder les poids soit appropriée. Ton graphe est "sparse" (en anglais): il y a beaucoup de -1 (enfin, de 0) dans ton tableau, en réalité, il y a relativement peu de connexions par rapport au maximum possible (tout le monde connecté à tout le monde dans les deux sens: n*(n-1) ~n² beaucoup. Pour ce genre de graphe, on préfèrera des "adjacency lists" plutôt qu'une "adjacency matrix" comme tu as fait ici. C'est plus performant point de vue mémoire (mais de fait (un peu) plus lent et (bcp) plus chiant à gérer). Ton tableau ne tiendra plus la route au-delà de 10000 noeuds, et on y est vite: regarde une carte de jeu de 100 x 100 cases. Ca ferait 10000 * 9999 * sizeof(int) octets = 400 Mo réservés à ton graphe, alors que de façon évidente, il y aurait, ds un jeu en cases, un nombre borné de cases attachées à une autre. Mais la remarque ne se limite pas aux jeux sur grilles: c'est vrai pour tous les graphes "sparses" (je sais pas le dire en français, dsl :().
Tu trouveras très facilement bcp d'infos sur les adjacency lists sur internet. Pour le reste, si je peux te donner un conseil si tu désires approfondir le pathfinding,
- cherche des infos sur l'usage des files à priorité (priority queue) dans l'algo de dijkstra: ça te booste cet algo, un truc de malade :D
- essaye d'écrire ton algo de façon générique, et pour chaque type d'implémentation, fournit un lot de fonctions différentes: get_next_node(), get_cout(n, m) etc etc. Là, tu gères le fait que ce soit une matrice, ou des listes, ou encore le fait que tu as une file à priorités. Ca te permettra de facilement essayer des améliorations (comme le A* aussi) et de les comparer aux versions précédentes sans devoir récrire tout l'algo: le noyau de base sera toujours le même.
Le meilleur pour ça, c'est d'utiliser une méthode virtuel dijkstra(...) avec des méthodes virtuelles pures get_next_node() etc qui sont implémentées différemment dans différentes classes héritées de celle-ci.
24 févr. 2006 à 12:23
24 févr. 2006 à 10:34
http://www.cppfrance.com/code.aspx?ID=33092
24 févr. 2006 à 09:39
Aussi, je ne pense pas que ta structure de données pour sauvegarder les poids soit appropriée. Ton graphe est "sparse" (en anglais): il y a beaucoup de -1 (enfin, de 0) dans ton tableau, en réalité, il y a relativement peu de connexions par rapport au maximum possible (tout le monde connecté à tout le monde dans les deux sens: n*(n-1) ~n² beaucoup. Pour ce genre de graphe, on préfèrera des "adjacency lists" plutôt qu'une "adjacency matrix" comme tu as fait ici. C'est plus performant point de vue mémoire (mais de fait (un peu) plus lent et (bcp) plus chiant à gérer). Ton tableau ne tiendra plus la route au-delà de 10000 noeuds, et on y est vite: regarde une carte de jeu de 100 x 100 cases. Ca ferait 10000 * 9999 * sizeof(int) octets = 400 Mo réservés à ton graphe, alors que de façon évidente, il y aurait, ds un jeu en cases, un nombre borné de cases attachées à une autre. Mais la remarque ne se limite pas aux jeux sur grilles: c'est vrai pour tous les graphes "sparses" (je sais pas le dire en français, dsl :().
Tu trouveras très facilement bcp d'infos sur les adjacency lists sur internet. Pour le reste, si je peux te donner un conseil si tu désires approfondir le pathfinding,
- cherche des infos sur l'usage des files à priorité (priority queue) dans l'algo de dijkstra: ça te booste cet algo, un truc de malade :D
- essaye d'écrire ton algo de façon générique, et pour chaque type d'implémentation, fournit un lot de fonctions différentes: get_next_node(), get_cout(n, m) etc etc. Là, tu gères le fait que ce soit une matrice, ou des listes, ou encore le fait que tu as une file à priorités. Ca te permettra de facilement essayer des améliorations (comme le A* aussi) et de les comparer aux versions précédentes sans devoir récrire tout l'algo: le noyau de base sera toujours le même.
Le meilleur pour ça, c'est d'utiliser une méthode virtuel dijkstra(...) avec des méthodes virtuelles pures get_next_node() etc qui sont implémentées différemment dans différentes classes héritées de celle-ci.