L'avantage de l'algorithme du Breadth-First Search (BFS) est justement qu'il ne risque pas de perdre du temps dans une impasse. 

Cependant, l'algorithme consomme plus de mémoire et prendra plus de temps si l'objectif à atteindre est éloigné.

Le choix s'est porté sur le BFS plûtot que Dijkstra, car la grille conçue est un graphe non pondéré. Toutes les cases sont à égale distance les unes des autres et par conséquent, l'information nous intéressant est le voisinage de chaque case.

Dans le programme de base, les voisins de chaque case sont : la case située à gauche (x-1, y) ; la case située à droite (x+1, y) ; la case située en haut (x, y-1) et la case située en bas (x, y+1).

Pour accélérer le temps de calcul, l'utilisateur a également le choix d'inclure les voisins situés en diagonale de chaque case. (x-1, y-1) ; (x+1, y-1) ; (x-1, y+1) ; (x+1, y+1)

CONCLUSION

Ce projet m'a permis d'améliorer ma connaissance des algorithmes de parcours de graphes ainsi que mes compétences en programmation orientée objet avec le langage Python, le tout en réalisant un projet tout aussi amusant qu'intéressant. 

Les paramètres actuels permettent de choisir la taille de la fenêtre, la taille de la grille, l'emplacement de la case départ et d'arrivée, le nombre d'obstacles à répartir aléatoirement ainsi que l'algorithme A* ou le BFS.

Les futures améliorations sont: 

•  Le développement d'une interface graphique (Graphical User Interface) afin de sélectionner les paramètres au lancement du programme.

•  L'ajout de la valeur des cases et l'implémentation de l'algorithme de Dijkstra. 

• La possibilité de sélectionner plusieurs cases de départ et d'arrivée.

Compétences développées lors de ce projet