@@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!
@@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.
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!!!
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!
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!
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.
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*
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.
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!
@@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.
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.
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.
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.
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.
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.
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.
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!
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.
This was the first Sebastian Lague video I ever watched. I loved the simple, straight-forward instruction style. So many UA-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.
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!
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.
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
@@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.
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!
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 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!
I just landed on this tutorial from UA-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 😍.
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.)
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!
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
Hats OFF big time! thank you. I implement your pseudocode word-by-word and worked perfectly! I have two versiond Dijkstra (with g cost only) and A* (with both g+h cost) for comparison.
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!
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 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!
I am trying to make snake AI but didn't know what type of AI should I make, googled a lot but still couldn't find an AI that would fit me, then clicked on your video about 10 years of game development and saw this pathfinding algorithm. How did I not find this before?? It's amazing!
A* doesn't work for a snake AI because it assumes a static environment, but the snake's tail is always moving. A dynamic pathfinder variant or a Hamiltonian path would be more practical.
Man, I wish these sort of videos had been around when I started learning coding and modeling back in the day! These videos are so fantastic, also great for refreshing my dusted and aged skillset! Back then in 2005-2012, C# on windows (only) actually had all these tools (jobs [tasks], lambdas, LINQ, Dependency injection, entities, modular approach, native binaries, thread-safe collections etc etc.) and techniques DOTS is based on now, man, I kinda wish I had not changed my field to Japanese culture and language soon after graduation Too bad I never fully realized how they should be properly used in making games
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)
Trivial for the programmer to just decide if they want to allow the algorithm to move like that or not. Its up to you to decide based on your scenario.
To add onto the other responses, the way you decide is by choosing whether two diagonal nodes are truly neighbors. Say you're using this algorithm for a game where your character can only move up, down, left, and right. In this scenario, a diagonal node isn't a neighbor because you can't directly traverse from one node to the other in one movement. So the algorithm will still provide an optimal, accurate solution as long as you provide it an accurate graph to work with.
1:49 G cost is not just this. You are using *G cost = distance from parent node + parent distance from starting node* (if the parent node is the starting node, them G cost = distance from starting node)
Thats add additional lines, parent distance from starting node is 0 in this case. The distance talked in the video is generally saying weight, which will be eventually updated in most algorithms.
Here's my astar function! It works exactly the same as in the video! Just so you know, this is how my tiles are defined: [position, g_cost, h_cost, parent] So a coordinate goes in position, and a coordinate goes in parent, to say where it's parent is. G and H cost are obviously in g_cost and h_cost. My adjacent function only returns tiles which are walkable and within the grid. def astar(self,start,end,walls): def adjacent(a,b): return [(x,y) for x,y in [(a+1,b),(a-1,b),(a,b+1),(a,b-1),(a+1,b+1),(a+1,b-1),(a-1,b+1),(a-1,b-1)] if all([(x,y) not in walls,x>=0,x=0,y
How many software engineering jobs never have this kind of interesting work? Its so challenging and reenforcing traditional computer science, algorithm and really nteresting
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!!!!
exactly 10 years since this video, still useful to a lot of people, good job
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!!!
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
Literally made an entire library in like 2.5 hours with this explanation, the delivery and visuals were perfect.
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!
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.
dont think its possible to explain this algorithm any simpler and clearly, really well explained
amazingly well explained
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*
this is 1 of the best explanation of A* algorithm, thank you so 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.
I think this is the best explanation of the A* I've seen so far.
By comparison to other tutorials/ explanations on this topic which I have seen, this is by far the best
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.
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.
Finally A* explaination that just 10 min, great explaination kudos to you.
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.
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.
the pseudo code walkthrough at 7:35 helped me implement the algorithm from scratch very quickly, thx!
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.
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.
omg THE BEST visualization of A*, soooo clear, so smart, so creative! so gorgeous! thank u so much! this illustration is super genius!💡
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!
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.
Finally a tutorial that's straight to the point and doesn't leave me picking my nose and doubting my intelligence
This was the first Sebastian Lague video I ever watched. I loved the simple, straight-forward instruction style. So many UA-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.
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!
Best tutorial. No nonsense, no stuttering. Just a clean confident depiction of the algorithm.
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.
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 ✨
A very clear and easy to follow example with step by step exlpanations. Thank you.
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!
Great code explanation and I love the visualizations too! Super helpful for someone who just started learning A*
As a programmer who has always been interested in calculating pathfinding solutions like these, I am very happy for your involvement and help.
Wow, this is the first time i understand it .. thank you :D
hi guy from twitter xD
my 5th
I think that the only thing better than this explanation, is that sweet background music.
Best A* explanation I have seen. Very clear and concise - shows a clear understanding of the algorithm. Thank you:
This was a fantastic explanation. Ive watched three videos on this algorithm and this is by far the best explanation.
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!!!
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...
Good explanation! It is said to be a complex algorithm, but here it is explained so well, so it doesn't seem to be complex.
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!
I just landed on this tutorial from UA-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 😍.
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.)
Thanks for the awesome video and pseudo code. I was finally able to understand a practical example of it in motion. Cheers.
Finally a clear and understable explanation on how this works. Great job !
this is above and beyond what I was hoping to find. fantastic.
Thanks! I just wrote my own A* implementation, the pseudocode at 7:50 really helped a lot
Just you going through the the algorithm with a nice little diagram and then the basic pseudo code helped immensely, great video.
It's amazing to me how simple this algorithm is. Many great ideas are simple.
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!
Just wanted to say thanks! You explained how the pathfinding works really well!
One of the best explanation I've ever seen in my life, it's way over the academic level, good job! Keep it up :)
In my opinion the best A* explanation video, bravo!
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 finished my first implementation of A* in Unity today. Tried it years ago, failed miserably so thank you for this great explanation !
Me to I’m in the middle of trying it
Thank you for explaining everything visually like this. It was exactly what I needed to finish wrapping my mind around this algorithm.
Hats OFF big time! thank you. I implement your pseudocode word-by-word and worked perfectly! I have two versiond Dijkstra (with g cost only) and A* (with both g+h cost) for comparison.
Best A star algorithm video in internet by far, love you brother
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!
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!
I am trying to make snake AI but didn't know what type of AI should I make, googled a lot but still couldn't find an AI that would fit me, then clicked on your video about 10 years of game development and saw this pathfinding algorithm. How did I not find this before?? It's amazing!
A* doesn't work for a snake AI because it assumes a static environment, but the snake's tail is always moving. A dynamic pathfinder variant or a Hamiltonian path would be more practical.
Your diagrams in all of your videos are very expertly made and very informative. Best tutorials I've ever seen.
Your videos are the best Unity(+ C#)/Blender on youtube :D
Thanks for sharing!
Man, I wish these sort of videos had been around when I started learning coding and modeling back in the day! These videos are so fantastic, also great for refreshing my dusted and aged skillset!
Back then in 2005-2012, C# on windows (only) actually had all these tools (jobs [tasks], lambdas, LINQ, Dependency injection, entities, modular approach, native binaries, thread-safe collections etc etc.) and techniques DOTS is based on now, man, I kinda wish I had not changed my field to Japanese culture and language soon after graduation
Too bad I never fully realized how they should be properly used in making games
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)
This was really good. Had some graph code laying around so that made it easier to convert the pseudo code to working A*.
One of the best tutorials I've seen, I love the visual examples and the pseudocode approach. The whole series is awesome. Thank you!
u path is the best unity algorithm! So good to see all mind tracking in time that sctipt has been done!!
what happens if you have two unwalkable nodes diagonal from eachother?
□■
■□
will it try to walk between them?
Trivial for the programmer to just decide if they want to allow the algorithm to move like that or not. Its up to you to decide based on your scenario.
yep, it will. other guy gave a non-answer, of course a programmer can change that fact
To add onto the other responses, the way you decide is by choosing whether two diagonal nodes are truly neighbors. Say you're using this algorithm for a game where your character can only move up, down, left, and right. In this scenario, a diagonal node isn't a neighbor because you can't directly traverse from one node to the other in one movement. So the algorithm will still provide an optimal, accurate solution as long as you provide it an accurate graph to work with.
@@contrabass8126 this is youtube not stack exchange
Kelly Flynn hahahaha that got a good laugh out of me
Very intuitive look at the fundamentals of how this works, was thinking it was a LOT more complicated, thanks!
Thanks ! I looked some a* vids, and this one is the one with which I finally understood !
Fantastic tutorial! Clearly explained with great step-by-step visuals. Thanks for posting.
Watched this a few times now and each time I am understanding this more and more thank you
I'm really grateful for the tutorial! It helped me during 12th puzzle of Advent of Code 2022 :D
I'm here for the exact same thing. I hope I get to make it work too!
the quality of these videos is amazing. It just gets better and better thank you!
Very clear explanation. Thanks for teaching us how it works.
this is going to be my sunday project. Always to cool to know how these things work behind the scenes.
You are awesome Sebastian super crystal clear explanation.
Great tutorial and examples. Please make more algorithm videos. You are a great teacher.
finally an A* explanation that makes sense
The best explanation of this algorithm I've seen.
finaly I understand it. the best explanation ever
Very informative tutorial! Perfectly explained the concepts!
1:49 G cost is not just this. You are using *G cost = distance from parent node + parent distance from starting node*
(if the parent node is the starting node, them G cost = distance from starting node)
Thats add additional lines, parent distance from starting node is 0 in this case.
The distance talked in the video is generally saying weight, which will be eventually updated in most algorithms.
@@Nleil If G cost is always distance from starting node, then the cost would not change when he clicks on other positions.
Everything seems complicated, but this tutorial sums it up brilliantly!
Here's my astar function!
It works exactly the same as in the video!
Just so you know, this is how my tiles are defined:
[position, g_cost, h_cost, parent]
So a coordinate goes in position, and a coordinate goes in parent, to say where it's parent is.
G and H cost are obviously in g_cost and h_cost.
My adjacent function only returns tiles which are walkable and within the grid.
def astar(self,start,end,walls):
def adjacent(a,b): return [(x,y) for x,y in [(a+1,b),(a-1,b),(a,b+1),(a,b-1),(a+1,b+1),(a+1,b-1),(a-1,b+1),(a-1,b-1)] if all([(x,y) not in walls,x>=0,x=0,y
Beautifully demonstrated and explained.
Sebastian, you are awesome! I hope your tutorial making will continue for ever!
Amazing explanation and teaching. I understood it first time.
Really nice and logical explanation, this is really the video i had been looking for 👍
Great tutorial mate. Absolutely amazing and easy to understand.
How many software engineering jobs never have this kind of interesting work? Its so challenging and reenforcing traditional computer science, algorithm and really nteresting
Amazing explanation, simple and complete, you're a great teacher!
TYSM!! You actually helped me understand it now, I really needed this for a sort of road pathfinding
Thank you so much Sebastian for all the work you put into your videos. This is awesome, you channel is awesome.
So easy a child could understand. Thanks brother.
Best A* tutorial on the internet by far +1