This Python script implements the A* pathfinding algorithm using the Pygame library. A* is a widely used algorithm in robotics and game development for finding the shortest path between two points on a grid while avoiding obstacles. Pygame is utilized to create a graphical representation of the grid and visualize the pathfinding process.
-
Grid Visualization: The script generates a grid with customizable dimensions where each cell can represent different states (start, end, barrier, etc.).
-
A Algorithm*: The main A* algorithm efficiently searches through the grid to find the shortest path from the start node to the end node while considering obstacles and applying heuristics. The algorithm is further modified to make use of replanning, a technique used in pathfinding algorithms to handle dynamic environments and dynamic obstacles.
-
Continuous Maze Generation: A separate thread continuously generates mazes within the grid to provide varying obstacle configurations for pathfinding.
-
Success Rate Calculation: After a specified duration, the script calculates the success rate of finding a path from start to end within the allotted time.
-
Installation: Ensure you have Python installed on your system along with the required libraries (Pygame).
-
Running the Script: Execute the Python script
python pathfinding.py. This will open a Pygame window displaying the grid and pathfinding process. It runs for 70 seconds before displaying the success rate in the terminal. -
Interaction:
- Left-click on cells to toggle them between empty spaces and barriers.
- Press the 'Space' key to start the A* algorithm.
- Press the 'Escape' key to quit the application.
-
Customization: You can customize parameters such as grid size, maze generation frequency, and algorithm execution duration within the script.
- Python 3.x
- Pygame
- This script is inspired by the A* pathfinding algorithm and its application in various fields.
- Thanks to the Pygame community for providing a powerful tool for creating interactive visualizations.
- https://youtu.be/JtiK0DOeI4A?si=yP696jBy6uxJB7JE Code provided by this tutorial was used as a template for the visualization using pygame. Additions we made included changes to the main loop that starts automatically, maze generation, maze updates, and implementation of the A* algorithm modfied to make use of Replanning