Bonjour à tous.
 
Je travaille actuellement sur un (ridicule) projet de pathfinding (chemin le plus court pour ceux qui ne connaissent pas) et j'ai un petit problème au niveau de calcul des "coûts".
 
Ma matrice d'entrée est faite de 1 et de 0 (1 signifie que le passage est possible) 0 signifie qu'il y a un obstacle. Les déplacements sont possibles dans les 8directions connexes a une case (sauf en diagonale s'il faut traverser un coin qui présente un obstacle)
 
J'ai pensé à une solution : Calculer pour chaque case le "coût" en déplacement qu'elle coute pour rejoindre le départ (déplacement depart-case)
 
Cette méthode est "simple" a dire puisqu'une fois que la matrice de coût est calculée, il sufift de refaire le chemin à l'envers (en partant de l'arrivée) en prenant a chaque fois la case 8connexe ayant le plus faible coût jusqu'au départ.
 
Cependant il me pose le problème de la facon dont calculer cette matrice de coûts. Pour la case de départ, pas de problème, dans la mesure du possible (obstables ou non) on calcule le cout dans les 8 directions (+ 1 pour un déplacement horonzontal ou vertical, +1,4 pour un déplacement diagonal)
 
Mais une fois que ce premier calcul est fait, comment parcouris l'ensemble du tableau sans repasser sur une case des calculer etc (puisqu'il est possible qu'un chemin soit calculer a partir d'un point source mais qu'un autre chemin soit plus court par un autre)
 
Je ne sais pas si j'ai été très clair, au cas ou, je pourrais tenter d'eclaircir mon problème.
 
Quelqu'un voit-il comment éclairer ma lanterne ?
 
Merci d'avance
 
Alexis

si tu n'écrases le cout que quand il est plus faible que celui déjà présent, ca devrait rouler, non ?

L algo que tu cherches s appelle algo de Dijkstra.
Rapidement implémenté il s execute en O(S*S*S) pour tout couple de sommets, mais il existe une version plus élaborée en O(S*A*lg(S)) pour graphes peu denses. (S=nbre de sommets, A=nbre d arcs=densité). Il utilise O(S*S) en mémoire.