Path finding visualization with A* algorithm
Modules -
pygame and tkinter
Language -
Python
How Program works?
Run the program(main.py) and after that a box will open up. Choose two points. After that user can draw wall with Mouse and then press Space key to start Algorithm. Path can't pass through wall.
The A* algorithm works on principle of
- F is the total cost of node.
- G is distance between the current node and start node
- H is the heuristic - estimated distance from current node to end node.
Let's assume node(0) is starting position and node(19) is end position. The current node is on node(4).
H
H is estimated distance from current node to end node. node(19) isover 7 spaces and 3 spaces from node(4).
Here, use Pythagorus theorem,
a² + b² = c²
So, for currentnode the value of H is 7² + 3² = 58.
Note -
Even if we don't apply the square root to 58, we will still get same output so skip that calculation.
It's important that the estimated distance is always underestimation of total path or overstimation will lead to A* searching for nodes which are not best in terms of F.
G
G is the distance between current node and start node.
node(4) is 4 spaces away from initial node. So, value of G for currentNode is 4.
F
F is total cost of the node. So, value of F for currentNode is sum of G and H of currentNode which is 4+58 = 62.
Why F?
Why not Djikstra?
Pseudo Code
Check out pseudo code for A* from Patrick Lester's blog.
1. Add the starting square (or node) to the open list.
2. Repeat the following:
A) Look for the lowest F cost square on the open list. We refer to this as the current square.
B). Switch it to the closed list.
C) For each of the 8 squares adjacent to this current square …
!)If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
!!)If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
!!!)If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
D) Stop when you:
Add the target square to the closed list, in which case the path has been found, or
Fail to find the target square, and the open list is empty. In this case, there is no path.
3. Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent