Embedded Files
Projet réalisé sur mon temps personnel afin de développer mes compétences en programmtion
Projet réalisé sur mon temps personnel afin de développer mes compétences en programmtion
Dans le but de mettre en pratique mes connaissances sur les algorithmes de parcours de graphes renvoyant le plus court chemin entre deux noeuds, j'ai créé ce petit projet en Python.
Le principe est similaire au projet de visualisation de pathfinding. Le graphe est représenté par une grille de cases contenant des obstacles (en noir) et des balles (en bleu) répartis de façon aléatoire. Le robot (en rouge) est placé par l'utilisateur et a pour but de trouver la balle la plus proche et de déterminer le chemin le plus court pour aller la ramasser.
L'algorithme du Breadth-First Search (BFS) a été utilisé car contrairement au A*, il n'est pas gêné par la présence de plusieurs cibles.
Encore une fois, le choix s'est porté sur le BFS et non Dijkstra, car la grille ici présente est un graphe non pondéré. Les cases sont à égale distance les unes par rapport aux autres et par conséquent n'ont pas de "valeurs". La seule information nous intéressant ici est le voisinage de chaque case, à savoir si les voisins existent et ne sont pas des obstacles.
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). Il y a également possibilité de choisir les voisins en diagonale (x-1, y-1) ; (x+1, y-1) ; (x-1, y+1) ; (x+1, y+1).
Robot se servant du Breadth-First Search
Robot se servant du Breadth-First Search
Le robot ne réalise pas le chemin le plus optimisé afin de ramasser toutes les balles. Actuellement, il recherche uniquement la balle la plus proche de lui sans tenir compte de la position des autres balles.
Une possibilité d'évolution serait l'implémentation d'un algorithme de voyageur de commerce afin d'optimiser le chemin en fonction de la position de toutes les balles.
Une seconde perspective d'évolution est d'implémenter plusieurs types de cases, possédant chacune une valeur précise et ainsi utiliser l'algorithme de Dijkstra au lieu du parcours en largeur.
Compétences développées lors de ce projet
Compétences développées lors de ce projet
Ce projet a été réalisé en Python en utilisant les librairies : OpenCV, Numpy, Pygame, Collections (pour le pathfinding) et Time.
Pygame a permis la conversion des pixels de l'image en grille de case pour y implémenter l'algorithme de pathfinding.
Programmation Orientée Objet en créant les classes : Main, Fenêtre, Grille, Case et Robot qui hérite de la classe Case.
Page updated
Google Sites
Report abuse