A* Pathfinding (E01: algorithm explanation)
ฝัง
- เผยแพร่เมื่อ 15 ธ.ค. 2014
- Welcome to the first part in a series teaching pathfinding for video games. In this episode we take a look at the A* algorithm and how it works.
Some great A* learning resources:
theory.stanford.edu/~amitp/Gam...
www.policyalmanac.org/games/aS...
Source code: github.com/SebLague/Pathfinding
If you'd like to support the creation of more programming videos, I'd greatly appreciate your support on patreon:
/ sebastianlague
Background music is 32. The Hidden Path by longzijun.
![พรากรัก - เต้ย อภิวัฒน์ [ Official MV ]](http://i.ytimg.com/vi/ShT2ltn8GBE/mqdefault.jpg)
I wish more programming tutorials explained things like this, the concept itself instead of the steps to create it. It's so spectacularly simple.
the problem is that I have no idea how to program something like this
@@ammyvl1 That's not true. Here's a tip from a pro who has been programming for over 30 years:
You DO know how to program A* even if you don't think that you do. You see, you are thinking too complicated. You envision a result that is fully optimized. Forget about that. You are probably right in that you have no idea how to program that. Yet.
But you are 100% capable of programming a working A* algorithm, even if it's the most awkward version humanly possible.
Just do it.
Just follow the steps in the video (completely disregard the pseudo-code) by any means necessary to complete the task. You DO know how to make a node class with the three cost properties, you DO know how to make a 2D array (map) of such nodes and you DO know how to search for a node on this map with specific valued properties. For example, you DO know how to find the lowest valued f_cost node currently on the map, even if you have to scan through the whole map and checking each node.
You can do optimizations later. For example, you don't really need to scan the whole map again and again if you maintain lists of any relevant nodes, adding or deleting or updating nodes as they are being processed. The pseudo-code at the end of the video is just showing a version that has been optimized (just the bare minimum to avoid repeatedly scanning the map) by maintaining two such lists.
Once you start "brute-forcing" yourself through the algorithm to at least have a working version, you'll discover any number of such shortcuts and tricks to avoid doing unnecessary processing.
Happy coding!
@@Kenjuudo oh ok
@@Kenjuudo that is the most wholesome motivation coding speech I've heard, happy coding to you too
@@ImposterBraum You're welcome! Like in most areas of life, confidence plays a huge role in programming too. I hereby introduce the concept of "developer confidence";
Nobody are born with knowledge. Nobody automatically knows an algorithm until they've actually learned the algorithm. (duh!)
However, typically no new programming concepts are being introduced. If you know the language, you'll be able to express your way to the finish line.
All optimized versions of an algorithm started unoptimized.
i give this tutorial an A* , good job!
I give you A* for that response
fuck all of you
@A very rude person I give you an A* for the observation!
@@utpalsavaliya761 I give you an A* for your judgement skills
I give A* to this thread
8 years later still one of the best resources out there, THANKS!
ikr
for sure!!!!
Just wanted to say thank you for this video. The extremely clear demonstrations coupled with the pseudo code at the end made the algorithm clearer to me than any other explanation I have watched or read. I was actually able to write my own A* pathfinding algorithm from scratch after watching this video several times. Thank you, thank you, thank you!!!
dont think its possible to explain this algorithm any simpler and clearly, really well explained
amazingly well explained
After watching other tutorials I thought that pathfinding is hell, but this one is perfectly simple, took less than 2 hours to implement it for my game
How the fuck did you do it with the pseudo code that doesn't accurately represent the code?
Does that mean I'm dumb? Cause i didn't understand quite well!
@@ashutosh_tiwari if you are not familiar with graphs and graph traversals, maybe this can be difficult. If that's the case, learning the basics of graphs and graph traversals (depth-first search and breadth-first search) should help you with fundamentals. Then you can learn Dijkstra's Algorithm, which also finds the shortest path and very similar to A* algorithm with one subtle difference that you'll notice when you learn both of them. I recommend Abdul Bari's videos for anything algorithms related. They are especially good for fundamentals.
@@ardnys35 ohh thankyou very much ✨
This is WONDERFULLY informative, thank you so damn much for these videos - pathfinding has always been something I struggled with because I hadn't the slightest idea as to how it really worked, but this explained it in a super easy to understand manner.
Liked, subbed.
One of the best tutorials I've seen, I love the visual examples and the pseudocode approach. The whole series is awesome. Thank you!
Thanks for the awesome video and pseudo code. I was finally able to understand a practical example of it in motion. Cheers.
Finally A* explaination that just 10 min, great explaination kudos to you.
I only recently found this channel and I'm so glad I did. Sabastian goes into the perfect level of detail needed to fully understand the concept he is teaching. Rated A*
I have not seen an educational youtube video of this quality and clarity in quite some time.
I only coded as a little hobby years ago, but this actually makes me want to start again.
I've been watching your videos for years. Any topic I research, when you have made a video on it, yours is always explained with the most detail and somehow remains the easiest to follow and listen to. You truly are one of the best.
Your diagrams in all of your videos are very expertly made and very informative. Best tutorials I've ever seen.
THANK YOU. Your step by step graphical explanation FINALLY made this click for me. I've been stuck on this problem for three weeks now, can't wait to dig in when I get home tonight!!
the quality of these videos is amazing. It just gets better and better thank you!
this is 1 of the best explanation of A* algorithm, thank you so much.
One of the best explanation I've ever seen in my life, it's way over the academic level, good job! Keep it up :)
Fantastic tutorial! Clearly explained with great step-by-step visuals. Thanks for posting.
Thanks a lot, Sebastian from 7 years ago. I've watched all of your videos, and the second I saw you had one explaining A* I went immediately for it. Love your content!
Just you going through the the algorithm with a nice little diagram and then the basic pseudo code helped immensely, great video.
Finally a clear and understable explanation on how this works. Great job !
your explanation just made my day! i understand A* now, really happy that find out your channel is very helpful for me, thank you so much!!!
this video is 8 years old and just gave me the idea to a game i will now start to plan and later make. this is finally the projectidea i needed to get myself into programming. thank you sir for your inspiration!
how is your game coming along? Did you manage to implement the A* mechanic succefully?
@@rickbeniers667 He probably got overly inspired and realized that making games is much harder than he thought so he gave up
Great video! Me and my friend are using a* in a c++ data structures course to traverse a 2d array maze, thanks for the upload, it made this really clear to me
I just landed on this tutorial from TH-cam recommendation as i was studying how A* algorithm works and it really helped me, easy and cool explanation.Thanks i just subscribed and liked your channel 😍.
This was a fantastic explanation. Ive watched three videos on this algorithm and this is by far the best explanation.
Sebastian, you are awesome! I hope your tutorial making will continue for ever!
nice formula for calculating heuristics :
h = min(dx, dy) * 14 + abs(dx - dy) * 10
where
val dx = abs(goalXcoord - nodeXcoordinate)
val dy = abs(goalYcoord - nodeYcoordinate)
where abs(x) returns the absolute value and min(x, y) returns the smaller value of the two inputs.
THANK YOU
I'd say this is the only thing he missed that should have been in the video.
Thanks
Thank you... i actually tried to calculate the real distance instead of this and somehow it didnt work ;D
why the constant 14 and 10 though?
14 because of the 1.414... from sqrt(2) and the 10 comes from the same 10 that Sebastian said he'd multiply all the calculations by just so that they can deal with integers rather than floats.
Best A* explanation I have seen. Very clear and concise - shows a clear understanding of the algorithm. Thank you:
this is going to be my sunday project. Always to cool to know how these things work behind the scenes.
By comparison to other tutorials/ explanations on this topic which I have seen, this is by far the best
You are the BEST. I struggled a bit at breaking down the "set f_cost of neighbor" bit because I didn't think it meant calculating the new f_cost of the neighbor based on the new current node, but I eventually figured it out. The visualization goes a long way. Thanks very much!
Thank you for explaining everything visually like this. It was exactly what I needed to finish wrapping my mind around this algorithm.
Best A* tutorial from a person who knows what he is doing and not like other tutorials that read something from a textbook without any reasoning behind it. Thank you!
This feels like minesweeper when you were clicking on the nodes.
Well, Minesweeper is based on the concept of cumulative information where, if you look at things from a real overall perspective, the actual chance you loose any game is equal to (number of mines / number of available cases) + the low chance of having a full pack of at least 2 or more bombs completely surrounding a safe spot.
So, Minesweeper only includes chances to loose during 2 possible parts of the games :
1) During the first roll as there's no way of knowing where the mines initially are. If you click on a mines right off the bat, it's bad luck and there's nothing you can do about it.
2) When a safe spot is surrounded by at least 2 rows of bombs... so a square pack of 25 spot with 1 safe spot right in the middle of it. (so, whenever you look around the safe spot, there's 2 bombs in all directions)
@@creationsmaxo hey, 1 isn't a possible loosing way. The game will only generate the bombs after the first click. So click and lose is impossible (at least with all the minesweepers I've played)
@@matheuscirillo36 you're absolutely right
@@matheuscirillo36 there's so many versions that one could have that lose in the first tap. I certainly feel like I had it happen before. Could be Mandela effect too
@@matheuscirillo36 Probably you haven't played the one that came pre-installed in windows XP or windows 7. There were a lot of bad lucks on the first click with me!
It's amazing to me how simple this algorithm is. Many great ideas are simple.
Thank you so much for taking the time to do this tutorial. Great stuff.
the pseudo code walkthrough at 7:35 helped me implement the algorithm from scratch very quickly, thx!
Thank you so much Sebastian for all the work you put into your videos. This is awesome, you channel is awesome.
Thanks a lot for the information (and the detailled tutorial) about the A* path finding.
The cool thing is that I have upgraded the algorithm in my own way (though it's still a work-in-progress...)
I added something you rarely see inside an algorithm such as A* : the ability for the AI to do mistakes!
I know this might sound counter productive because the goal of the algorithm is to find the right path... but I added 3 layers in the behavior that can overtake the suggested path.
The first thing I added is the ability to the AI to be distracted.
So it has :
• A "MainObjectifAttention_Value" float + "MainObjectifAttention_V3" vector3,
• A "SubObjectifAttention_Value" float + "SubObjectifAttention_V3" vector3,
• Everything that can be a source of attention has an Attention multiplier.
For example, an AI spot the player which has an attention multiplier of 2.0 which quickly raise MainObjectifAttention_Value to 100. Once above 50, It starts following the player around, but loose track of it around a corner. The NPC move toward the corner where the player was last spotted then, the value starts dropping slowly. I also added "Points of interests" with a type category which, if compatible with the AI points of interest, raise the AI' "SubObjectifAttention_Value" while dropping "MainObjectifAttention_Value" and if the "SubObjectifAttention_Value" become higher than the "MainObjectifAttention_Value, there's a switch and the Main become Sub and vise versa. When "SubObjectifAttention_Value" is below 1, its vector 3 become the "point of origine" (or spawn point) of the AI and its value raise back toward 50 (not 100). As the previous statement... when the MainObjectifAttention_Value drop below 50 while the Sub is the point of origine, there's a switch and the AI return to his own spot.
The opposite is also possible as if the AI move close to a node that contains something it doesn't like, a multiplier will be added onto the node's value. With this, it's possible for example, to make an AI only move close to something like a trap or a pit of lava or acid or whatever harmful if they actually have an objective near it... It also remove the context where you see some guarding monster stationed right next to some lava pit without any kind of safeguard.
For example, if you have a game with vampires and werewolves moving around, you could put a 1.5 multiplier onto nodes with crosses, 1.2 multiplier onto nodes with garlics and 2.0 onto nodes with sunlight... So if it's "right" next to its target within sunlight, 2.0 multiplier would ensure it never wants to move there... yet the werewolf wouldn't be affected so for it, the block is 1.0 of value. You could also put point of interest (so lower multiplier) which makes an AI to do a small detour of 1 node when passing close to something... Like a dog passing next to a juicy piece of meat... which would have value multiplier of 0.5 (meaning the value would half so 2x more attractive to pass through.)
Finally, I added the effect that whenever a attracting or a unwanted thing come close to the AI, there's a chance that its MainObjectifAttention_Value drops 2x faster. or even alter the target destination a bit by cutting a couple of the last nodes from the path found.
So... Yeah, thanks a lot!
+Creations Maxo (Maxime Bolduc) Awesome :)
My processor is crying in a corner though... 😂😂😂 that's the coolest algorithm concept I've read hope to see it in action soon.
Great concept, love it!
@@yoowon-hye9270 I know you replied 1 year ago, but I would point out that a way to optimize the A* pathfinder for the CPU is to make use of an adjustable time length between the refreshes of the path finding process. If you're using the process in an engine like Unity, there are methods (such as IEnumerators) where you can allow the process to wait for an amount of frames before refreshing. Otherwise, there's always the possibility of using a tick system where the process is calculated only at every X frames. When you use a priority system within the A* pathfinder, you don't need to update the priority at every frame, but simply build up a list during (X - 1) frames and update it on the X'th frame. (X being a number of frames you feel comfortable with.) At the same time, you can add a sort of prediction system which, during the movement of an AI towards its closest target, pre-calculate most of the data at the goal, with a few exceptions. This way, you're not throwing everything at your CPU right away, but instead feed it bytes by bytes along a longer (and less stressful filled) way.
The one thing to consider, overall, which is engine-dependent, is the garbage collector (GC). Each engines have their own pro and cons around their GC. The bottleneck of most A* Pathfinder variations is the GC because of the wasted calculations and parameters created on the fly and rendered useless quickly after. When the GC's data to handle exceed a certain threshold, it start using more of the CPU and even RAM to recover its "late data" and that's usually where you see an huge spike in the memory usage of the A* Pathfinder.
This video was so well-explained that I was able to get A* in my game from the explanations and pesudocode alone. I'll definitely still watch the rest of the series, especially for anything I might have missed or further optimizations.
Literally made an entire library in like 2.5 hours with this explanation, the delivery and visuals were perfect.
you've blown my mind! I use an engine which has a movement algorithm built in but it's clunky and annoying to use. It's great to see how one can be programmed from scratch!
Thank you for this tutorial, it was very helpful, it took me a while to understand it but now I have fully implemented it in a program for a school project. Greetings from Mexico
Thanks a lot for take the time to create these awesome tutorials! I think these are the best I've seen on this topic! Very well done!
A very clear and easy to follow example with step by step exlpanations. Thank you.
Just wanted to say thanks! You explained how the pathfinding works really well!
Amazing explanation, simple and complete, you're a great teacher!
This was an extremely good way to explain it! I actually understand it now :) (also, your new videos are amazing and I'm so happy you're almost at 1 million subs)
Great tutorial mate. Absolutely amazing and easy to understand.
This is so cool. i had to figure this stuff by myself out as a 13-14 year old programming pascal back in '95 where there wasnt much of an internet. i wanted to build c&c like strategy game. i got it the alrythm working wich i am proud of. now 20 years later im getting back into programming. i forgot how much fun it is. and its so much easier nowadays to get help... cheers.
Very informative tutorial! Perfectly explained the concepts!
Watched this a few times now and each time I am understanding this more and more thank you
thank you sir, looking forward to this series
Wow, this is the first time i understand it .. thank you :D
hi guy from twitter xD
my 5th
Great tutorial and examples. Please make more algorithm videos. You are a great teacher.
omg THE BEST visualization of A*, soooo clear, so smart, so creative! so gorgeous! thank u so much! this illustration is super genius!💡
This was the first Sebastian Lague video I ever watched. I loved the simple, straight-forward instruction style. So many TH-camrs could learn from this guy. Just get to the point, if I like your content I'll do all the engagement shit without being asked.
After many tries, I finally got my own A* algorithm working in my rust engine! This video is literally the _best_ video on YT for learning this. THANK YOU!
Thanks! I just wrote my own A* implementation, the pseudocode at 7:50 really helped a lot
Exactly the explanation needed I needed. Thank you bro!
Very intuitive look at the fundamentals of how this works, was thinking it was a LOT more complicated, thanks!
The best explanation of this algorithm I've seen.
I think I finally got it. Thank you for this great and awesome tutorial!
I think I've watched this tutorial like 3 times already. 4th time's the charm because I finally understand A*, it's so satisfying when things just *click* in your head. Now I just need to actually implement the graphs for my game...
I'd just like to take a moment to sing Sebastian's praises.
I have only just begun coding pathfinding and first implemented Dijsktra's algorithm.
I was suffering lag spikes from a single unit on larger graphs.
Using the method supplied in this tutorial allows me to have 1000 units (and beyond) pathfinding simultaneously on a 50x50 grid while still maintaining 60-fps and above.
So, thanks for some very useful code. Going to have to rip it apart again now, sadly to fit it in with my intentions, but the core of it will surely remain the same as I doubt I could improve on this neat coding.
Keep it up Lague. These videos are amazing.
this is above and beyond what I was hoping to find. fantastic.
Best tutorial. No nonsense, no stuttering. Just a clean confident depiction of the algorithm.
Excellent, intuitive description. Thank you!
Great clip, very informativ and well explained in a calm and understandable way. Thanks!
Very clear explanation. Thanks for teaching us how it works.
You are using a square grid. THANK YOU ! So many people are trying to explain this using rounded bubbles and diagonal movement. I need this JUST for the computer. Just for the video games I'm writing. Hopefully your tutorial will finally explain how this method works.
@@darkstar3116😂😂😂😂😭😭😭😭
The way the others explain it is more abstract. You should also understand that.
Your videos are the best Unity(+ C#)/Blender on youtube :D
Thanks for sharing!
Everything seems complicated, but this tutorial sums it up brilliantly!
You have my respect sir. Thank you very much for such a magnificent work!
I read and saw about 5 pieces of material, including wikipedia and was still oblivious, this video explains the things I was struggling with from the get go. Amazing work!
Beautifully demonstrated and explained.
Thanks ! I looked some a* vids, and this one is the one with which I finally understood !
awesome explanation, yet again. Thanks, Sebastian
This was extremely helpful, that demo program was great! Thanks!
I feel like this is going to take a while to get my head around but this was an excellent introduction - thank you!
In my opinion the best A* explanation video, bravo!
Best A star algorithm video in internet by far, love you brother
Amazing explanation and teaching. I understood it first time.
Man, this is beautiful. Thank you!
Absolutely cracking video. Thanks! Really made it clear.
This is such great quality with the presentation and explanation keep it up man :)
I sat through so many bad vids that didn't explain this at all, including a useless hour-long one of a guy trying to decipher his own Git code in real time. Then I watched this and wow. Your explanations are so clear. I even translated your pseudo-code into javascript for a game I'm coding and it works beautifully. Thank you for this.
Finally a tutorial that's straight to the point and doesn't leave me picking my nose and doubting my intelligence
i know im 8 years late.. (love all of ur new vids btw!!!) but that pseudocode and explanation was exactly what i needed!! thank you for your great videos a decade later!
You are awesome Sebastian super crystal clear explanation.
TYSM!! You actually helped me understand it now, I really needed this for a sort of road pathfinding
This is an amazing tutorial. Saved me a lot of time! Thank you :)
Thank you so much for uploading these tutorials. They are amazing. :)
I don't understand all of it, especially the part about how it "updates". BUT this is the closest I've ever come to understanding it, and that's saying something. No other explanation has come close to making sense to me. So well done, and thank you! (Maybe if I watch it a few more times.)
Gonna work on my thesis, truly appreciate it!
Very well explained. Thank you so much!
Great video, thanks for taking the time