- Binary Heap: A custom binary heap implementation is used to efficiently store nodes in a priority queue-like structure, ensuring nodes with lower total cost (f) are given higher priority.
- Node Representation: Each cell in the grid is represented as a node containing information about its position, cost from the start (g), heuristic cost to the goal (h), and parent node.
- Heuristic: Euclidean distance is used as the heuristic function to estimate the cost from each node to the goal, guiding the search towards the target efficiently.
- Valid Movement: The algorithm considers four possible movements - up, down, left, and right, with diagonal movements omitted for simplicity.
- Obstacle Avoidance: Obstacles in the grid are represented as blocked cells, and the algorithm avoids expanding nodes that correspond to obstacles.
- Path Reconstruction: Once the goal node is reached, the algorithm reconstructs the shortest path by tracing back through the parent nodes from the goal to the start.
The algorithm takes as input a grid representing the environment, start and end points, and returns a list of coordinates representing the shortest path from the start to the end. It employs a systematic exploration strategy, expanding nodes with the lowest estimated total cost until the goal is reached or all possible paths are explored.
- Efficiently finds the shortest path in a grid-based environment.
- Suitable for applications requiring path planning in robotics, video games, and navigation systems.
- Assumes movement is restricted to four cardinal directions.
- Performance may degrade in large-scale grids or environments with complex obstacles.
- Robotic navigation in warehouses, factories, and outdoor environments.
- Video game AI for character movement and navigation.
- Routing algorithms in transportation and logistics systems.
Test Case 1
Test Case 2
Test Case 3
Test Case 4
Test Case 5