Graph Data Structure 6. The A* Pathfinding Algorithm
ฝัง
- เผยแพร่เมื่อ 5 ม.ค. 2017
- This is the sixth in a series of videos about the graph data structure. It includes a step by step walkthrough of the A* pathfinding algorithm (pronounced A Star) for a weighted, undirected graph. The A* pathfinding algorithm, and its numerous variations, is widely used in applications such as games programming, natural language processing, financial trading systems, town planning and even space exploration. This video demonstrates why the A* pathfinding algorithm may be more appropriate and more efficient than Dijkstra’s shortest path algorithm for many applications, because it is focussed on finding the shortest path between only two particular vertices. The video explains the need for an admissible heuristic, that is, a suitable estimate of the distance between each vertex in the graph and the destination vertex; the example shown here makes use of Manhattan distances for this purpose, calculated on the basis of the grid co-ordinates of each vertex. A description of the pseudocode that leads to an implementation of the A* pathfinding algorithm is also included.
When you watch this example, you will see there are occasions when the f values of some open vertices are the same, so the next current vertex is selected from these “for no particular reason”. As pointed out, making one choice or another could have a profound effect on the course of events that follow, but that very much depends on how the algorithm is implemented, and the anatomy of the graph being searched. The search described in this video concludes when the destination vertex is a neighbour of the current vertex - and it shares the lowest f value. Conceivably, another open vertex could have had a lower f value than the destination at this stage, so the search for a shorter path would continue. Again, exactly how the algorithm finishes is a matter of implementation. If you investigate this subject further, you will discover there are lots of ways the algorithm can be adapted. Using a priority queue for the open vertices is one way, pre-processing the graph data to calculate the h values is another. The basic A* pathfinding algorithm descried here is really just a starting point.
Thanks to one of my viewers, Fro mik, for spotting an error in the pseudocode I included in my video about the A* pathfinding algorithm. The algorithm as I described it is correct. It points out the importance of calculating the f values of ALL the neighbours of the current vertex, including those neighbours that are already in the open list.
In my pseudocode, I add a neighbour of the current vertex to the open list if it’s not closed AND if it’s not already open. This is also a condition of calculating the f value, which is not correct. When vertex C is current, we need to recalculate the f value of vertex B, but my pseudocode would not do this because B is already open.
The pseudocode would work fine with the graph in my example, but if it was quicker to get from A to C via B, my pseudocode would not find the shortest path.
Below, you can see what the pseudocode should look like.
Needless to say, I will need to fix my VB.NET implementation code, which is based on my original pseudocode.
I you do spot any issues with any of my videos, do let me know and will try to put things right. I understand that even the smallest error can lead to big misunderstandings.
Please keep watching and keep sharing.
***** A* pseudocode*****
Initialise open and closed lists
Make the start vertex current
Calculate heuristic distance of start vertex to destination (h)
Calculate f value for start vertex (f = g + h, where g = 0)
WHILE current vertex is not the destination
FOR each vertex adjacent to current
IF vertex not in closed list and not in open list THEN
Add vertex to open list
END IF
Calculate distance from start (g)
Calculate heuristic distance to destination (h)
Calculate f value (f = g + h)
IF new f value < existing f value or there is no existing f value THEN
Update f value
Set parent to be the current vertex
END IF
NEXT adjacent vertex
Add current vertex to closed list
Remove vertex with lowest f value from open list and make it current
END WHILE
i think still wrong, or at least "not right". Closed verteces should not be processed again. you can't combine them in the IF.
@@julianelischer Yes and you need to update the g value here:
IF new f value < existing f value or there is no existing f value THEN
Update f value
update existing g value for vertex
Set parent to be the current vertex
END IF
@@nefdulin7988 I dont think you need to recalculate the G value. Nothing has changed.
Best explanation! Your narrative sounds like a BBC documentary haha
You are doing amazing guides with your videos about Pathfinding, your explanation is always so clear. Thank You !
This is an updated version of the original video which corrects one of the g and f value calculations that was in error. I believe the calculations are all accurate now. I've added some additional comments to the description which you may find useful.
Agreed. Best explanation of A* so far on TH-cam ;) Thank you!
Thank you for this explanation! Its the most thorough one that I've come across :) Really appreciate people like you putting so much effort into providing quality education for free!
Thanks for the lovely comment. :)KD
Thank you so much for explaining this so clearly! Really appreciate that this is open source information!
No one gives an explanation like this. Works Finally.
Delighted to help :)KD
Best explanation of A* I've found anywhere online! You're amazing :)
Thank you :)KD
Your explanations are really very concise and clear! I was able to implement adjacency list, BFS, DFS and Dijkstra so far purely based on your videos and without even looking at the pseudo-code you provided! Now about to implement A*!
Excellent. Delighted to be of service :)KD
Daniel, I am glad to see that you found yourself an interesting occupation after escaping from Alexander's castle and the Shadow.
I'm happy, I got you! This was awesome
Thank you so much for releasing such a well-made video. It is very clear and to the point. Loved it.
Thank YOU :)KD You are most welcome.
Thanks a lot for such an amazing explanation. Many other videos taking heuristic from thin air and not explaining the importance of it. This video on the other hand explains all pros and cons and edge cases if you choose the right heuristic value or wrong and what the outcome would be.
You are most welcome. Thanks for commenting :)KD
Very clear and detailed explanation, thank you!
You are welcome. Thanks for the feedback.
High quality content. Thank you.
You are most welcome :)KD
A slight correction is needed to the end of the execution. The algorithm does not terminate when a goal node (P, in this case) is placed into Open, but only when that node is selected as the "current node". Thus, a goal node might be added to Open while there are still other nodes in Open with an equal or lower f-value. Those will need to be expanded before our goal node is finally selected for expansion, at which point the goal state will be detected and the algorithm will terminate.
Yes. To give a concrete example, if (13, 5), (14,5), and (15, 7) were walls, then the shortest path would not have been from J but instead from K, and the result would have been incorrect. You have to keep evaluating a bit further to make sure you've considered all possible paths to know you've actually found the shortest one.
Best explanation! A star is born!
Thanks a million. :)KD
loved it! great job.
Thank you so much for this explanation.
You are very welcome :)KD
Thank you very much for, mind clarifying explanation
Thank you very much man for the explanation. I really needed it.
You're welcome. Happy to help :)KD
Much clear and wonderful way of explanation. Good work.
Please make video for Jump point Search as well
Thanks for the kind comment. :)
Thank you very much! I finally understood the algorithm :)
You are welcome. Tnx for the feedback. K:D
brilliant explanation. thank you
Thank you very much! Helped me for my test!
Best and simplest vid on this topic
Thank you :)KD
Nicely explained. Thanks a lot!
And thank you for the comment :)KD
Thank you so much! Great explanation.
Thanks for saying so :)
How did you calculate g score of the nodes? I'm trying to write a function to calculate g_score for a node with x,y values given.
this is quite marvelous sir
Dry run really cleared the concepts
i must learn this magic for my game development.. :D
Love your enthusiasm!!! 8D
Thank you :)KD
Best video on this topic
Thank you :)KD
It all makes sense now, I was doing it wrong the whole time :')
8:33 In another video on A* it was said the reason for choosing H over D in this case is that H happens to have a lower h value than D. Don't know if that applies here as well but it seems logical. Then at 10:18 the next current node would have to be K instead of J
The basic principle of A* is covered here, but there must be dozens of variations, especially when it comes to application. :)KD
Is there a good algorithm to create the pathfinding graph (navmesh?) from a grid based "environment"? I mean usually you can just map each grid cell to a path node, which works fine for small grids, but if you have a bigger grid (many nodes) it starts to get slow, so it should be optimized to reduce the nodes and only handle "important" nodes, I have read many things about this, I think it's called "navmesh", but I can't find any algorithm which describes a good way to actually generate such a graph/navmesh.
Love your lessons SET 5 FOR THE WITH
Awesome video! I like it
TNX
Correct me if I’m wrong, but in a nutshell, you just calculate the adjacent vertices distance to the current vertice you are on and the adjacent verticies distance from the destination. Then you travel the shortest option.
Thank you for this great walkthrough!
You said "h()" is used for no particular reason if f has the same value. I think this is wrong. If f has the same value it makes sense to take the path that has the least distance to the goal (h) since it's more probable to lead faster to the goal node.
Thanks. Clear and concise. I recommend not using a too dynamic speech, it becomes a bit too hard to follow.
172 likes vs 0 dislikes, that is insane, but very deserved!
what happen when equal f value come front . which should choose ?
Thanks a lot !!
nice explanation
I am wondering how did you get heuristic distance table? and once we reach our destination vertex, we stop calculating but there may be another path that sums lower than that we have found?.
You are quite right. I calculated all of he heuristics in advance (using the grid co-ordinates) but could have calculated each one as and when needed. A* is far from perfect. If the heuristics are poor, the result may not be the best. The more you know to start with, the better the result will be. Arguably Dijkstra's is better, because it will find the shortest path from the start node to all of the others and it doesn't need any prior information. But A* does a lot less work. In an A Level exam, you may get asked to compare the two algorithms.
8:39 actually, because the H value is lower and makes sense to decide on that one.
Excellent video from someone who knows his stuff. Thank you! Your voice is very familiar though :)
My dear. Thank you so much for your great video, but if we get two nodes with the same value, I mean in your example H=D=24. You got H, but according to A* algorithm we denpend the alphabetic order as I have read. Is it true to take randomly or continue with what I know?. According to the alphabetic order I get A-B-D-K-P the shortest way.
mostly A* takes the node with the lowest h value if f is equil
and random if both are equil
how can i like this twice👏
I would like to ask you how you calculate the heuristic distance, and what is it. If it is the actual distance of each letter to destination(P) then why A has 16 and B has 17 while B is closer to P than A?
Thank you
Hi Stefanos
The heuristic distance (h value) is an estimate of the distance from a node to the destination. I can be calculated in various ways. The example in the video uses the Manhattan distance (the horizontal distance plus the vertical distance). This the Manhattan distance is larger than the Euclidean distance (as the crow flies).
In terms of Manhattan distance, A is closer than B. If it was a map of New York, it would be quicker to get to P from A.
th-cam.com/video/eSOJ3ARN5FM/w-d-xo.html
When there are multiple Vertices with the same f cost, it would be better to decide based on the h cost instead of choosing random. Otherwise you MIGHT not find the shortest path.
This is very important. Thanks for pointing this out.
Fantastic! Can you do RRT* ?
Thank you. RRT is on my list :)KD
I think you messed up the end... A* should end only when P is expanded, i.e., when it has the lowest f value in the table.
5:51 how did you get the 16 for f and h please
that is the heuristic value, estimate the remaining distance from A to P. in this case, it is delta x + delta y.
B is already in openlist, but you still check, whether to update its value. Error in pseudocode?
Hi Fro mik
Are you referring to th-cam.com/video/eSOJ3ARN5FM/w-d-xo.html?
"We calculate a new g value for B, even though it already has one" - I think that's correct, but the pseudocode is wrong. Because of this condition: "if vertex not in open list THEN" the new value wont be calculated.
Yes, I am referring to that.
You are absolutely right. Thanks for spotting this. I need to fix my implementation code too. I get away with it using the graph in my video, but it does not work for any graph.
You are absolutely right. Thanks for spotting this. I need to fix my implementation code too. I get away with it using the graph in my video, but it does not work for any graph.
Here is the new algorithm with some fixes. It is mostly same but fixes some issues that are not that vital but still issues regardless.
Initialise open and closed lists
Make the start vertex current
Calculate heuristic distance of start vertex to destination (h)
Calculate f value for start vertex (f = g + h, where g = 0)
WHILE current vertex is not the destination
FOR each vertex adjacent to current
IF vertex in closed list THEN
skip this vertex and go to the next adjacent vertex
END IF
IF vertex not in open list THEN
Add vertex to open list
END IF
Calculate distance from start (g)
Calculate heuristic distance to destination (h)
Calculate f value (f = g + h)
IF new f value < existing f value or there is no existing f value THEN
Update f value
Update existing g value for vertex
Set parent to be the current vertex
END IF
NEXT adjacent vertex
Add current vertex to closed list
Remove vertex with lowest f value from open list and make it current, if there are more than one f value with the lowest value choose the one with the lowest heuristic value
END WHILE
Nice :)KD
how to know the destination is reachable ?
Strictly speaking, you don't know until you try to get there. :)KD
Can A star work in unknown environment ?
That's an interesting question! The algorithm should work with almost any graph that is encoded in the way it expects. But if I understand your question correctly, getting a generic A* program to work in any number of different environments would come down to the plumbing - and I imagine there would be a lot of it. :)KD
@@ComputerScienceLessons Thanks!
But if the |KP| was 3, the algorithm would've chosen the wrong path, because K's f value doesn't rely on |KP|
BEST. Why ranked so low when I search?
TY. I probably need to work on my marketing :)KD
@@ComputerScienceLessons No you don't need marketing, you need to put some attractiveness to your videos, for example put in the intro a short video showing the algorithm working to find a path and by the way some people done this in there videos, your channel lacks an important aspect of succssful channels and it is attractiveness
👍👍👍👍👍👍👍👍👍👍👍
While implementing this algorithm, I found it necessary to track the nodes which node I came from while calculating the G score for a given . Below is the javascript function I wrote for calculating gScore. I'm using an object oriented approach and storing the 'cameFrom' and 'parent' nodes in the node's state object. Hope this helps somebody, feel free to reach out with further questions.
function calculateG(node, intitialG){
let g
= initialG //set G to the cost from the last node to the one we're checking
let cameFrom = node.state.cameFrom
while(cameFrom){
g += cameFrom.gScore
if(cameFrom.state.parent){
cameFrom = cameFrom.state.parent
} else {cameFrom = false}
}
return g
}
There's missing edges in the graph.
If you say so :)KD
I wish you were my lecture
Ok, heuristic is a big one.
But aside of that can just wondering can A* be improved upon?
For instance, it seems g-distances are much more reliable than h-estimations. Could it be better (more efficient/competititve) if we move simultaneously in both directions - from start to end and vice versa? This way supposedly we may get better information, estimating distances not from frontier to end but rather between two frontiers.
Good thinking. Dijkstra's was the Model T of pathfinding algorithms and A* was the Thunderbird. Algorithms like these can be enhanced and adapted in all kinds of ways to solve specific problems (as long as adaptations are not too expensive computationally) :)KD
@@ComputerScienceLessons share the code
To be honest, all these other comments are saying great video and great explanation, I agree with the video content it is good but the explanation is not so great, as a person who is completely new to this algorithm I lost you at 04:17 when you said the heuristic distance is pre-calculated based on information that we already have. I don't understand which information we already had and how to calculate the heuristic distance value? If it is calculated using pythagors theorem then it should have been shown in the UI on how to calculate the heuristic distance, I really got confused on that part, others were kind of okay!
Sorry, I find your algorithm way too hard to implement :-/
If it's any help, I have included a talk-through of a VB.NET implementation in the following video. th-cam.com/video/VH53Gm9gdwE/w-d-xo.html. Good luck.