#algorithme #code
BFS l’algorithme de pathfinding le plus simple. Il utilise une queue pour ajouter les prochaines nodes à visiter, ainsi qu’un set pour marquer les nodes déjà visitées.
Si le graph est “unweighted”, BFS permet de trouver le chemin le plus court vers une node donnée.
L’algorithme de Dijkstra utilise une PriorityQueue plutôt qu’une simple queue. Il faut aussi prendre en compte le fait qu’une même node peut être visitée plusieurs fois: il faut re-visiter la node seulement si cela diminue la distance totale jusqu’à cette node.
L’algorithme A* utilise un “heuristique”, qui est une estimation de distance restante jusqu’à la destination. Dans la priority queue, la priorité d’une node donnée est la distance depuis la départ + l’heuristique.
priority = costSoFar + heuristic(goal, next)
De cette façon, A* se concentre en priorité sur les paths qui se rapprochent de la destination, contrairement à l’algorithme de Dijkstra qui cherche dans toutes les directions.