Graph Data Structure 6. The A* Pathfinding Algorithm

[@ComputerScienceLessons]

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

[@julianelischer]

i think still wrong, or at least "not right". Closed verteces should not be processed again. you can't combine them in the IF.

[@nefdulin7988]

@@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

[@Justajawnie]

@@nefdulin7988 I dont think you need to recalculate the G value. Nothing has changed.

[@potatocoder5090]

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!

[@ComputerScienceLessons]

Thanks for the lovely comment. :)KD

[@ComputerScienceLessons]

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.

[@triangle4studios]

No one gives an explanation like this. Works Finally.

[@ComputerScienceLessons]

Delighted to help :)KD

[@jibran6635]

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*!

[@ComputerScienceLessons]

Excellent. Delighted to be of service :)KD

[@nguyenluan2603]

Best explanation! Your narrative sounds like a BBC documentary haha

[@jackalrd2209]

Yes he showed us false shortest path. Those J instead of K. He does not understand the algo or makes intentional mistakes. 🇬🇧

[@cameronarnold2811]

Best explanation of A* I've found anywhere online! You're amazing :)

[@ComputerScienceLessons]

Thank you :)KD

[@MrChisnok]

You are doing amazing guides with your videos about Pathfinding, your explanation is always so clear. Thank You !

[@adis6603]

Agreed. Best explanation of A* so far on KZbin ;) Thank you!

[@paulmag91]

Daniel, I am glad to see that you found yourself an interesting occupation after escaping from Alexander's castle and the Shadow.

[@yuriyanisimov4482]

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.

[@ComputerScienceLessons]

You are most welcome. Thanks for commenting :)KD

[@Hdrien]

Thank you so much for releasing such a well-made video. It is very clear and to the point. Loved it.

[@ComputerScienceLessons]

Thank YOU :)KD You are most welcome.

[@matthewevett3191]

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.

[@MagnusVortex]

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.

[@justforfun4680]

Thank you so much for explaining this so clearly! Really appreciate that this is open source information!

[@X.A.N.A..]

Best and simplest vid on this topic

[@ComputerScienceLessons]

Thank you :)KD

[@yackawaytube]

Best explanation! A star is born!

[@ComputerScienceLessons]

Thanks a million. :)KD

[@Adityakumar-ez8ud]

I'm happy, I got you! This was awesome

[@eejain]

Very clear and detailed explanation, thank you!

[@ComputerScienceLessons]

You are welcome. Thanks for the feedback.

[@yendrrek6703]

High quality content. Thank you.

[@ComputerScienceLessons]

You are most welcome :)KD

[@pushkarjain2494]

Dry run really cleared the concepts

[@_aibeats]

It all makes sense now, I was doing it wrong the whole time :')

[@toomanysymbols]

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

[@ComputerScienceLessons]

The basic principle of A* is covered here, but there must be dozens of variations, especially when it comes to application. :)KD

[@emenikeanigbogu9368]

this is quite marvelous sir

[@Ðogecoin]

Thank you so much for this explanation.

[@ComputerScienceLessons]

You are very welcome :)KD

[@auran_vesdranor]

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.

[@AngrejKumar]

Thank you very much man for the explanation. I really needed it.

[@ComputerScienceLessons]

You're welcome. Happy to help :)KD

[@The__Leo69]

Nicely explained. Thanks a lot!

[@ComputerScienceLessons]

And thank you for the comment :)KD

[@SombreroMan716]

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.

[@Raymond13557]

i must learn this magic for my game development.. :D

[@gpsewtohul7652]

Best video on this topic

[@ComputerScienceLessons]

Thank you :)KD

[@mireazma]

Thanks. Clear and concise. I recommend not using a too dynamic speech, it becomes a bit too hard to follow.

[@sathiyanathan1318]

Much clear and wonderful way of explanation. Good work.

[@sathiyanathan1318]

Please make video for Jump point Search as well

[@ComputerScienceLessons]

Thanks for the kind comment. :)

[@Moonz97]

Thank you very much! I finally understood the algorithm :)

[@ComputerScienceLessons]

You are welcome. Tnx for the feedback. K:D

[@M_Can45]

Thank you very much for, mind clarifying explanation

[@louise1021]

Love your enthusiasm!!! 8D

[@ComputerScienceLessons]

Thank you :)KD

[@mischa7823]

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.

[@nefdulin7988]

This is very important. Thanks for pointing this out.

[@nefdulin7988]

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

[@ComputerScienceLessons]

Nice :)KD

[@jasontudor-then2796]

Love your lessons SET 5 FOR THE WITH

[@perixgames5603]

172 likes vs 0 dislikes, that is insane, but very deserved!

[@dushanrathnayake5007]

Excellent video from someone who knows his stuff. Thank you! Your voice is very familiar though :)

[@evy2710]

loved it! great job.

[@duressajemal1235]

nice explanation

[@mgeorgescu]

8:39 actually, because the H value is lower and makes sense to decide on that one.

[@LucasHartmann]

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.

[@faraday6521]

how can i like this twice👏

[@r1pfake521]

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.

[@araldjean-charles3924]

Fantastic! Can you do RRT* ?

[@ComputerScienceLessons]

Thank you. RRT is on my list :)KD

[@Technogrammer]

Thank you very much! Helped me for my test!

[@GTX4747]

brilliant explanation. thank you

[@Lancer009100]

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.

[@ubbrok]

Thank you so much! Great explanation.

[@ComputerScienceLessons]

Thanks for saying so :)

[@atreidesson]

But if the |KP| was 3, the algorithm would've chosen the wrong path, because K's f value doesn't rely on |KP|

[@Fromikimo]

B is already in openlist, but you still check, whether to update its value. Error in pseudocode?

[@ComputerScienceLessons]

Hi Fro mik Are you referring to kzbin.info/www/bejne/m4Sye2Z3h7NofK8?

[@Fromikimo]

"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.

[@Fromikimo]

Yes, I am referring to that.

[@ComputerScienceLessons]

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.

[@ComputerScienceLessons]

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.

[@haithamalnasrawi9224]

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.

[@ScorpioneOrzion]

mostly A* takes the node with the lowest h value if f is equil and random if both are equil

[@ShampooWow]

Awesome video! I like it

[@ComputerScienceLessons]

TNX

[@SusaraThenuwara]

what happen when equal f value come front . which should choose ?

[@МихайлоСєльський]

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.

[@ComputerScienceLessons]

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

[@simonmuthee1318]

@@ComputerScienceLessons share the code

[@BibekSubedi-ue7hk]

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!

[@NeymarJr-uj1wf]

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?.

[@ComputerScienceLessons]

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.

[@stefanosamaxopoulos5285]

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

[@ComputerScienceLessons]

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. kzbin.info/www/bejne/m4Sye2Z3h7NofK8

[@palashrathore6277]

Can A star work in unknown environment ?

[@ComputerScienceLessons]

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

[@palashrathore6277]

@@ComputerScienceLessons Thanks!

[@linzhu5178]

BEST. Why ranked so low when I search?

[@ComputerScienceLessons]

TY. I probably need to work on my marketing :)KD

[@_BWKC]

@@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

[@kittytangsze]

how to know the destination is reachable ?

[@ComputerScienceLessons]

Strictly speaking, you don't know until you try to get there. :)KD

[@magaliecaouette8895]

Thanks a lot !!

[@roamingcelt]

There's missing edges in the graph.

[@ComputerScienceLessons]

If you say so :)KD

[@ChrisFotosMusic]

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 }

[@kennich2012]

5:51 how did you get the 16 for f and h please

[@quanghong3922]

that is the heuristic value, estimate the remaining distance from A to P. in this case, it is delta x + delta y.

[@Daver2212]

I wish you were my lecture

[@jirkadolezal8127]

👍👍👍👍👍👍👍👍👍👍👍

[@haltarys]

Sorry, I find your algorithm way too hard to implement :-/

[@ComputerScienceLessons]

If it's any help, I have included a talk-through of a VB.NET implementation in the following video. kzbin.info/www/bejne/jHmYZHqjbsyXrac. Good luck.