Embedded Files
Project done on my free time to develop my programming skills
Project done on my free time to develop my programming skills
In order to put into practice my knowledge on graph traversal algorithms returning the shortest path between two nodes, I created this small project in python.
The principle is similar to the Pathfinding_visualization project. The graph is represented by a grid of boxes containing obstacles (in black) and balls (in blue) distributed randomly. The robot (in red) is placed by the user and its goal is to find the nearest ball and determine the shortest path to pick it up.
The Breadth-First Search (BFS) algorithm was used because unlike the A*, it is not generated by the presence of several targets.Â
Once again, the choice was made for the BFS and not Dijkstra, because the grid here is an unweighted graph. The cells are at equal distance from each other and therefore have no "values". The only information we are interested in is the neighborhood of each cell, i.e. whether the neighbors exist and are not obstacles.
In the basic program, the neighbors of each square are: the square on the left (x-1, y); the square on the right (x+1, y); the square on top (x, y-1) and the square on the bottom (x, y+1). There is also the possibility to choose the neighbors diagonally (x-1, y-1); (x+1, y-1); (x-1, y+1); (x+1, y+1).
Robot using Breadth-First Search
Robot using Breadth-First Search
The robot does not make the most optimized path to pick up all balls. Currently, it only searches for the ball closest to it without taking into account the position of the other balls.
A possible evolution would be the implementation of a traveling salesman algorithm, in order to optimize the path according to the position of all the balls.
A second perspective of evolution is to implement several types of boxes, each one having a precise value, and thus use the Dijkstra algorithm instead of using BFS.
Skills developed during this project
Skills developed during this project
This project was realized in Python using the : OpenCV, Numpy, Pygame, Collections (for the pathfinding) and Time.
Pygame allowed the conversion of the pixels of the image into a grid of boxes to implement the pathfinding algorithm.
Object Oriented Programming by creating the classes: Main, Window, Grid, Case and Robot which inherits from the Case class.
Page updated
Google Sites
Report abuse