Path Finding
In this project, I created a pathfinding object to test my programming capabilities. The program is capable of performing a breadth-first, Dijkstra's, or A* pathfinding algorithm to consider all viable nodes and form a path to the closest coin on a randomly generated grid. The above left image shows a breadth-first search, and the above right image demonstrates an A* search.
This project is included in its entirely, so feel free to take a look at the code for yourself. Visual Studio to run the project.
Controls:
B - next searches will utilize the Breadth-first algorithm
D- next searches will utilize the Dijkstra's algorithm
A - next searches will utilize the A* algorithm
Key:
Light blue squares are not considered for the current path
Pink squares are considered for the current path
Blue squares are the boundaries of the current search
White squares are the current path
Grey squares are solid walls that cannot be moved through - they are randomly generated every time the program begins
Yellow circles are the coins being sought after; one is added to a random tile every few seconds
The green square is the pathfinding object
Red lines are the potential paths to and from each square, which does not take into consideration solid objects
Design:
Mechanics:
Scripting:
UI:
This project is included in its entirely, so feel free to take a look at the code for yourself. Visual Studio to run the project.
Controls:
B - next searches will utilize the Breadth-first algorithm
D- next searches will utilize the Dijkstra's algorithm
A - next searches will utilize the A* algorithm
Key:
Light blue squares are not considered for the current path
Pink squares are considered for the current path
Blue squares are the boundaries of the current search
White squares are the current path
Grey squares are solid walls that cannot be moved through - they are randomly generated every time the program begins
Yellow circles are the coins being sought after; one is added to a random tile every few seconds
The green square is the pathfinding object
Red lines are the potential paths to and from each square, which does not take into consideration solid objects
Design:
- Developed a grid with nodes to facilitate pathfinding algorithms
- Scripted algorithms for Breadth First, Dijkstra's, and A* pathfinding patterns
Mechanics:
- Coins are spawned randomly on a non-occupied tile every few seconds
- Impassable walls are generated randomly when the project is compiled
Scripting:
- Developed code to find the nearest coin
- Implemented Breadth First, Dijkstra's, and A* pathfinding algorithms utilizing tiles
- AI will move along calculated path to the nearest coin while avoiding obstacles
UI:
- Color-coded tiles according to key provided above for debugging purposes and to demonstrate successful algorithms
- The window not displaying the pathfinding grid indicates which search algorithm is currently being performed
Specifications
Development Time:
Environment: Tools: Language: Platform: Team Size: |
4 weeks
Visual Studio PyGame Python Windows 1 |
© Tobias Wadsworth
All content and trademarks are property of their respective owners
All content and trademarks are property of their respective owners