This project implements the A* (A-star) algorithm to find the optimal path from a starting point to a goal on a board with obstacles. Here’s a brief overview of the project:
- Project Goal: Create a program that automatically finds the shortest path from a given starting point to a goal on a grid-based board, taking obstacles into account.
- Assumptions:
- The board is a square grid with dimensions of 100x100 cells.
- Obstacles are randomly placed on the board.
- The player starts at position (0, 0).
- The coin (goal) is placed randomly on the board.
- Implementation:
- The Pygame library is used for visualizing the board.
- The A* algorithm calculates the optimal path based on heuristics and movement cost.
- Movement is allowed in four directions: up, down, left, and right.
- Obstacles are considered during path calculations.
- Visualization:
- The board is drawn in a Pygame window.
- The path is marked on the board.
- Insights:
- This project provides an understanding of how the A* algorithm works and its application in finding optimal paths.
- It can be extended with additional features, such as dynamically generated obstacles or different heuristics.
- Python libraries used:
- Pygame
- Pytest
- time
- heapq
A* is a graph traversal and pathfinding algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal. One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as by memory-bounded approaches; however, A* is still the best solution in many cases.
More informations here:
wikipedia
geeksforgeeks