A Python implementation of the A* (A-star) pathfinding algorithm for finding the shortest path between two points on a 2D grid with obstacles, using the Manhattan distance heuristic.
The A* algorithm combines the cost-based approach of Dijkstra's algorithm with a heuristic function to guide the search more efficiently. This implementation solves maze-style grid problems where the goal is to find the optimal path from a start node to an end node while avoiding obstacles.
The algorithm maintains two sets:
- Open Set: a priority queue of nodes sorted by their f-score (g-score + h-score)
- Closed Set: nodes already evaluated
At each step, the node with the lowest f-score is selected, its neighbors are evaluated, and scores are updated. This continues until the end node is reached or no path exists.
| Score | Description |
|---|---|
| g-score | Actual cost from start node to current node |
| h-score | Estimated cost from current node to end node (Manhattan distance) |
| f-score | g-score + h-score |
- Initialize start and end nodes; set all g-scores and f-scores to infinity except the start node
- Add the start node to the open set
- Select the node with the lowest f-score from the open set
- Evaluate each neighbor, update scores if a better path is found
- Repeat until the end node is reached or the open set is empty
- Reconstruct the path by backtracking from end node to start node
If the open set is exhausted without reaching the goal, the algorithm returns FAILURE.
| Type | Complexity |
|---|---|
| Time | O(b^d) where b is branching factor, d is solution depth |
| Space | O(b^d) for open and closed sets |
a_star(): main function implementing the algorithm, manages open/closed sets and score computationreconstruct_path(): backtracks from end node to start node to build the final path
- Navigation systems: finding shortest driving or walking routes
- Game development: AI character pathfinding through environments
- Robotics: path planning around physical obstacles
- Network analysis: shortest path through data networks
- Bidirectional A*: search from both ends simultaneously to reduce time complexity
- Jump Point Search (JPS): skip unnecessary nodes for faster traversal on uniform grids
- Euclidean heuristic: more accurate for diagonal movement
- Dynamic pathfinding: handle moving or changing obstacles in real time
- Parallel processing: speed up large-scale grid searches
# Clone the repo
git clone https://github.com/Uththara15/a-star-pathfinding.git
cd a-star-pathfinding
# Install dependencies
pip install pygame # if visualization is included
# Run
python main.py- Python 3.x
- Priority queue (heapq)
- 2D grid representation
GitHub: https://github.com/Uththara15 LinkedIn: https://linkedin.com/in/uththara15