Video není dostupné.
Omlouváme se.
Path Planning - A* (A-Star)
Vložit
- čas přidán 16. 08. 2024
- A tricky one to do a video about this, but here is an tutorial implementation of the A* path finding algorithm, programmed in C++, running at the command prompt.
Lol, forgot the source: github.com/One...
Blog: www.onelonecoder.com
Why didn't CZcams recommend this video for me, when I was searching for good A* implementation tutorial. This is the best one I've seen.
Indeed
That is because the infallible google artificial intelligence realized that you should try doing your homework on your own.
Dude the same thing happened to me. Thank God I found this videom
😂😂 so true @@Kuba-eb3jq
@@Kuba-eb3jq Bro I'm trying to implement this for my own project, this stuff has actual applications outside of school lol.
I have been looking at plenty of resources regarding this topic, AND THIS IS THE BEST ONE
thanks this was the best algorithm tutorial I've ever seen. I wish you would do every commonly used algorithm (especially for games) that would be great.You're teaching style is so slow, calm, and kind. Very easy to learn.
Hi Apricot (again lol) I appreciate the feedback. I have tended this year to include algorithms in the bigger project videos rather than just being stand alone, but I'm going to mix it up a bit next year I think.
Marvellous presentation. I shall watch it until I understand it. Ironically just as my eyes glazed over in awe at around the 6-minute point, you stated you were going to get rid of the dotted lines because you were already confused. That made me feel much better.
Hi Nick, Thanks! Admittedly a little dry the first half of this video, but I believe you should always run algorithms by hand if you need to understand them. "Become one with the algorithm" :D
Sir, I would just like to say thank you ever so much for your insight into A* and the accompanying tutorial! This has helped me out a lot, I made an attempt to implement this into my SDL2/C++ engine and it worked like a charm! Keep up the great work!
Thanks buddy, I'm pleased you found it useful! I'd love to feature it in my next community showcase video, so feel free to drop a link or a video or something
I would've used vector based priority queue instead of list and have removed sort.
You won't have any visited nodes (line 115) because you check if node was visited before adding it to the list (line 129).
You may use negation (operator exclamation mark) instead of equals to zero when dealing with boolean values (line 129).
At the start of your loop you check if list is not empty. We've figured out that there won't be any visited cells or walls, so we can safely take the top value as our current node, do the pop on queue and go on (line 114-121).
I like the visuals though and the explanation is great! Thanks!
Thanks once again Javidx9. I've been trying to get my head round A* for a while.
Hi Adrian, you're welcome! I thought it was going to be a lot more complicated than it is. Then again, I suppose a lot of algorithms can look complicated until you try them. Perhaps this reflects how inaccessible algorithmic notation is across computer science, and it needn't be this way.
I just love this dude so much
Best youtuber 100% :D Now i can test / compare other graph algorithms like this and see it visually! I love you javidx9!
Hi Danilo, lol Thanks! Yes, the display for this algorithm has uses other than just A*. If you think of anything it would be great to see some pictures or code - I could feature them in my next community showcase video.
Thank you for doing so much valuable work on CZcams!
I had a map 15*25 and my path calculations were taking up to 0.8 seconds with my version. Watching how he calculates the path instantly is truly amazing.... I will try to implement this into my program
That does seem like a long time Parabalani, which suggests you might be doing some redundant searching in your code. If needed, swing by the discord and show your stuff!
Thanks, man. I have no programming background but with your tutorial, I`ve managed to write a_star in Gamemaker on GML. Watched it like 5 times, made a shitload of debugging, but it works. I thought I was unable to do such things.
That's awesome buddy, always pleasing to hear people taking the ideas and running with it for themselves, great stuff!
Such an awesome dude with awesome pedagogy. He doesn't even force you to subscribe. He is like, "Have a think about subscribing".
I rarely comment anything but your explanation of the algorithm was pretty neat, I released immediately what I need to do. Thanks a lot :D
You could have skipped the sorting of all the nodes and just searched for the smallest one, it would be a major optimization.
love your videos man.
Wow this is a very interesting video. The A-Star algo you demonstrated could be used in a racing game where the CPU would need to calculate how to reach the finish line and to-do recalculations due to sudden objects in its path like in say Mario Kart.
Thanks again for another excellent contribution javidx9
Cheers Chris, yes A* can be very adaptable, and quick too, if you dont think of everything in terms of grids, and instead consider connected waypoints.
This vid saved me from failing my AI course, really good explanation of AStar!
I like your video's and have created a similar "olcgameconsole" class for C# (I'm sure I'll put it up on GitHub soon). One thing I noticed in this video is that at 2:18 you say "And I've marked my ending point which is node E", which should be D. Keep 'em coming though! Even as an experienced programmer I enjoy them and your way of presenting.
Hi Rob, Thanks for your support and oops yeah, I'm sure after the first 5 minutes all the nodes blur into one anyway :D. A C# version would be quite novel. I'm hoping to collect all the ports and alternative implementations for a video towards the end of the year, so definitely let me know if you go live with it, and feel free to drop a link to the source somewhere on the channel.
Thank you so much for this video!
I've finally managed to implement path proper path finding in to my airport sim game, using this video as a reference! :)
Hi Alanjaldred, That's Great! It would be good to feature a demo/video or prototype of your game for my next community showcase video!
Sure thing! If you like, once I've tidied up the code a little bit, I could upload to Github. It's a UE4 C++ project which can be opened in visual studio (y)
I've been trying to get this down for a few days... this is the only one that made me understand! Thanks!
Love the format and and structure of the videos. Keep'em coming!
Hi Jonathan, Cheers!
This is really good and building this in C++ makes it look like a charm. Thanks man for this!
Thank you so much for this tutorial!!! You are awesome!
Thanks! I was finally able to understand this algorithm and implement it into a Java application without needing to debug much.
Hi! I really appreciate your videos. You're really great! I'm to the 3rd year of the secondary school and I'm studying programation; I'd really like to know everything you know about language programs now. You're too cool. Like!😉👍🏻
Hey thanks Unknown Man! Good luck with your studies!
Loving you content more and more with each new video I watch. Keep up the good work!
I just wanted to comment on the fact that your example of A* involves nodes with arbitrary weights beween them.
This isn't the way A* works because, to be able to calculate the heuristics, you need some kind of a structure between the nodes and the weights. In your example, there is no way of calculating the "remaining distance" to the target node, because the nodes and the weights are arbitrary. You can't have a heuristic without solving the shortest path algoritm itself. So your heuristic must be 0 always and that's what Dijkstra's algorithm does. Dijkstra's algorithm is A* when the heuristic function is equals to 0.
You keep saying that the fact that the nodes are arranged in a grid is unimportant but, in fact, is quite the oposite. The fact that they are arranged in that way enables the use of Pythagora's theorem to calculate the heuristic fuction.
I'm sorry for pointing that out in your videos because I really like them and are very informative, but I think it's fair.
Thanks Javier, and I will! In principle you are correct, my heuristic is indeed Pythagoras for this demonstration. But if I chose not to use Pythagoras then I maintain my assertion, the arrangement of the nodes is unimportant for the functioning of the algorithm, albeit the complexity/meaning of the heuristic becomes more interesting! Pythagoras is useful because it is relate-able in N dimensional space, though any non-linear or arbitrary spatial mapping function could also be used. For example, one could modify Pythagoras to include spatial collisions to implement slower or faster zones, or even block off entire regions of the space.
The only real requirement is that the heuristic should provide a "best case" estimate for the distance to the end node. In order to find the shortest path you just need need to provide a heuristic which doesn't *over-estimate* (because that would cause the algorithm to ignore potential paths which might be faster).
So while a graph with totally arbitrary weights (especially zero weights) poses a problem, as long as there is *some kind* of relationship, then you can pick an optimistic heuristic which will find the shortest path, while being more efficient than "heuristic=0". And usually there's *some kind* of minimum cost based on distance when the nodes represent something with some underlying spatial relationship (speed of light etc!).
Of course you're right that you have to fall back to Dijkstra's when you have a truly arbitrary graph. But in many applications (especially in games), you can do at least a little bit better!
Excellent video short and sweet …now I’ll do a similar in JavaScript.
Thought the A* was a harder algorithm but looks like is a enhanced djikistra algorithm(where it doesn't check every field and have a basic heuristics). Great video
I really like the way you explained the algorithm. Thank you!
Cool. I was always curious about the A* algorithm.
Hey William, yeah so was I - its one of those algorithms that once you have made it, you'll use it all over the place I think.
Really like the presentation of these videos. :)
Once again another video that is going to help me a lot
Great stuff Kareshi!
Hi @javidx9,
I like your video but I have a remark. I think it is more correct to say
" if (node.local + distance to neighbor < neighbor.local) then update ...
Do you agree?
thank you so much, greatly appreciated!!
Great vid, implemented your code in LUA, works like a charm.
13:25 is so epic :D :D :D It's like the exact picture of all of us 🤣🤣
So glad i found your channel....its super well done...thanks a lot
absolutely brilliant javidx9
I'm astonished that nobody has noticed the mistake in this video so far.
If you look at the graph, the shortest distance is clearly A-E-F-D with a distance of 3.
You were doing the algorithm correctly, but your heuristic was not a consistent metric and failed to meet the assumption of never overestimating the distance left to the goal. You estimated the distance from E to D to be 5, which is more than it actually is -- 2 through F.
As a result E's large key delayed it's processing until after F was already processed and the cost of the shortest path could no longer be relaxed below 4.
If your heuristic doesn't overestimate, you can exit as soon as you visit the end node. It will be the shortest path.
You know this is bad when the node in the center is called ‘E A’
If only there was a emote for groans. Maybe this one will do instead: 😶
here’s an emote for groans 😫
Why is it bad?
@@banditbrah cause EA makes bad games - hurr hurr :D bad pun detected. Comes 2 month late, but i had to scratch my head for almost a minute too to get it. You could say
"It's in the game"...
@Dr. M. H. Everyone starts out enthusiastic, its that much more tragic when they go corporate and start pumping out AAA stuff no one really wants instead of something so nieche and different like those adventures.
GREAT - Thanks for sharing! I've learned a lot from it!
Great video, good pacing and explainations.
Awesome video.
I have 2 question:
1, Sorting the nodes can take long (depending on how many nodes you have of course). I heard that you can use a priority queue or "heap" data structure to optimize this step, because they will put the node with the lowest cost to the top. Do you have a video about these data structures or can you make one?
2, Setting the whole grid to their default value before you search can also take long (again, it depends on how many nodes you have), is there any way to optimize this part? I tried to research a little, but I couldn't find any decent way. I saw some videos which ignored this and didn't reset the nodes (cost) at all (they only had cost variables in their node class, they handled the visited state in an additional hash set) and their pathfinding still worked somehow but I don't understand why, because in theory the check for the node with the lowest cost should be wrong, because the node could still have a cost value of the previous run, maybe it only worked "randomly" in their videos and they didn't notice the bug yet? I tried to ask them in their videos but they didn't answer.
There is a way! You can add a "counter" variable - each time you run the algorithm you increase the counter, and you update a copy of the counter value inside each node as you touch it. If a node still has an old counter value, you can assume it hasn't been looked at during this run of the algorithm, and treat it as if it still has the default values (infinite cost, not visited, etc).
I am curious,why wouldn't you use min heap or RB tree (std::set ) for faster operating
This seems very obvious but couldn't you just replace distance with distance squared? You're only comparing the distances right? That would reduce the computation by a lot. Great video, keep it up!
My god the exact thing I needed thank you so much man
Also I think there is another mistake, when you comparing nodes, at the right side you show comparing condition, and did different thing. You added 2+1 and compare does that less then infinity, but you show that addition operation should be done at the left side. So I assume that value 1 should be added to infinity and than compared to local 2.
It is really confusing, and make learning this algorithm harder.
But owerall idea is explained correctly, so thx u a lot. I wasn't able to find detailed explanation as here before.
Got a question : I have an entity, let's say, a circle, with a radius of 5.f. The map size is 2000.f width, 2000.f height. To move the entity, I use the A* algorithm, as nicely teached in your video. The node (which is a square) has a size of 40.f. My program properly runs, meaning that the entity can move within the map, from a node to another, on long distance and taking obstacles into consideration. The issue is the following : when the entity reaches the "end node", it cannot precisely move to the precise mouse click coordinates. In fact, it just reaches the node and stops there, without taking into account the fact that I clicked on the top left corner of the node, or on the bottom right of the node. There is thus a lack of precision. I tried using smaller nodes (square of 5.f or even smaller) to increase the precision of my entity movement, but then I have "computation time" issue (for info, my laptop processor is an i5 8250). How can you thus combine the use of A* algorithm with high precision, please ? (Note that I still qualify myself as a beginner, since I learn programming by myself and am doing it on my free-time. Thx in advance for the help.)
Well the nodes represent obstacle or not. So once you hit your target node, simply move to your precise location since you know there is no obstacle there.
Best channel
you my dear sir are a genius
Why thank you sir! But it's an established algorithm, I merely present it in a different way.
bro you explain so damn well
I discovered your channel some time ago, you create interesting things and after I saw them I was motivated to learn some programming from your videos, but I gave up as soon as I started, because it was too much.
At the moment I have some (very basic) programming skills, but I still feel like such videos are too much for a noob like me. I mean, if I knew all of that syntax you use, I would just write it by myself.
I can get the idea of A*, but the programming is hard part for me. I would love if the code was simpler or just explained step-by-step. When I see dozens of &s, *s, some virtual bools I just give up. Don't get me wrong, your videos are interesting and probably people get it, but for such noobs like me it's just too hard to follow and understand. Or maybe I just suck at programming which also has high probability.
Really interesting topic, thanks
Yeah, I think its a useful algorithm
Amazing tutorials, thanks a lot
Hey no problem buddy, thanks!
Its really a great explanation.
Thanks for the great video. The A* and its implementation are very well explained.
In the code, I wonder how do we check that a neighbor node is not already in the NotTestedList?
once again thanks for the brilliant explanation. with your help i was able to implement the code in an hour (different language). but i have one question that i cant wrap my head around. how do you put "must visit" nodes? basically what i'm working on is, i want to go to Paris and have multiple places to visit as well as my start location and end location. so algorithm needs to arrange in which order should i visit the places and what route. is there some simple method to add in A* that will make this happen (like barriers are pretty easy to do) or do i need to do it the hard way and combine travelling salesman with A*?
You could use the heuristic I think. Find the shortest path to any node on your must visit list, once you reach it, bias your heuristic function to make that node undesirable, so the algorithm will naturally then travel to the next desirable node. It's a bit hacky and I don't guarantee bit will work all the time (if at all) but it's what I'd try.
Great video and well explained!
I've made it without usage of pointers, can you maybe explain about why would one choose to use pointers here? I've looked at your code but my knowledge and understanding of pointers is still at beginner level.
Cheers!
Hi David,
Thanks for this awesome video but I am not able to run this on my windows machine. I am using VS 2019. I just copied the olcConsoleGameEngine.h and AStarPathFinding.cpp. I am not sure how to add the relay server and sprite editor as per your video. I would really appreciate some help to figure out the missing bits.
Thank you so much man.
You saved my life. Hab to implement it for a job aplication. Now lets just hope they take me haha.
very nice as always :) !
Thanks Leo!
Very good. I only would change the list to priority_queue to avoid sort.
Hi Fabio, Thanks! You're absolutely right of course. Not that it matters now but I did implement it that way first time round, but came to the decision it was too much new stuff for one video. Perhaps I will modify the source in the github to reflect both options.
I always run around my neighbourhood across the blocks. I’m looking for a solution to run on all the streets within a predefined zone and back to where I start, in the shortest time, with minimum path overlap. Is there a logic I can plan on the map?
What if I have units on the battlefield which are themselv obstacles so Astar can't find a path through them.
But then the start and End Node is a Unit which is a obstacle so AStar can't find a path :(
Still something I want to implement for a hiking GPS because I already have the length and grade for every leg of hiking trail. Next "big memory" Platform I suppose.
Big memory I presume means >7 bits in your world huh? :-D You're right though - no clever hacks can make this algorithm memory transient.
dsPic is 16 bit wide, but more the 128k program memory that’s now almost full of other programs. I think I could have got it for a National park with limited hiking track nodes (rather than street intersections for a city map), but wouldn’t want to implement something like that only to have to cut it out. This would be the go to video when the time comes though. It was easy to understand what you were conveying.
You're so wonderful ❤
This video is wonderful.
First off, when you introduced the diagram (graph as you called it!) you said your start point was A and the end point was E but as you progressed through the explanation you seemed to change the end point to D when you said the shortest path was found as A to F to D which does not include E at all!
Given the changed end point of D you then later ruled out C as part of the shortest path. C can be included in one of 2 possible paths of the same distance between A and D! A to E is distance 1, E to C is distance 1 and then C to D is 2 according to your diagram. 1+1+2=4 which is the same distance as A to F to D (3+1=4). So I can only assume from your discounting C that there is a rule to use the least number of nodes, why wasn't this mentioned?
Hi Galbi, yeah a verbal slip up at the start, the nodes are labelled start and end though. Regarding the exclusion of C, it is mentioned that the algorithm is primed to search for the shortest path of the world it is already aware of, by virtue of the priority queue, which is sorted based upon the heuristic. Following through the algorithm shows that F is discovered before C, and in fact, the shortest path is discovered before C is, so it becomes irrelevant whether or not there are secondary valid paths, and further still, the global heuristic of C is already a worse choice for the algorithm. So no need for a rule that searches for the least number of nodes, the ordering of the search does this intrinsically. Also, I will direct you to en.wikipedia.org/wiki/Graph_(discrete_mathematics) for the nomenclature.
@@javidx9 So technically the rule is not there but functionally it behaves as though it is. By your explanation both routes are of equal length and so both are the shortest therefore, for A-F-D to be the correct route it must be because of the number of node or alternatively it's first come first served, I.E. because that route was found first it has priority over any subsequent routes of equal length and it's only by a quirk of the layout that the first one found also has the least nodes. Easier to think there is a rule for the least nodes. Think of it as bus routes with nodes as stops. A-F-D is not shorter than A-E-C-D but because there are more stops in the latter route it takes longer so the first is the shortest route measured by time :)
@@javidx9 You've probably noticed I've done a bit of binge watching your videos as you have found 2 comments of mine at the same time lol
Very interesting videos. I have already played around with a couple of the programs from the collection of videos you shared on GitHub. Maybe they can re-inspire my old love of programming and get me going again :)
Really hooking channel. Using PGE in linux to port this one. Really, really Thanks... Muchas gracias
Didn't you mistakenly said that the end point is E instead of D? from 2:17 timeline
P.S. oh, I find in comments that it was discussed already, but will left my comment, so it will be more recognizible
Javid, you said combining two different descrirptions in one struct wasn't good practice. What would you recommend be done differently, so I can use it in my 2d engine implementation for an mmo :)
At the end of the algorithm, from F to D is 3 after we get updated F with E to 2 but we did not calculated with updated value of F why ??
Nice explanation! I am using this algorithm for an Arduino robot with 3 ultrasonic sensors to understand it's location within a grid maze and then make a plan to exit the maze. What are the changes that i have to pay attention to?
At ~13:30, wouldn't you need to re-check nodes C and F? They were both updated, but you didn't re-check to see if they influenced D's parent?
My datastructures and algoritms course project says thanks!
AWESOME! you are the BEST!
for cost function lambda, why did you use 2-norm in place of 1-norm or taxi cab norm..wouldn't 1-norm be more accurate option.for this type of grid system??
edit - more accurate in the sense that, no diagonal movement was involved so 1-norm would make calculations faster etc
The first path A* finds is always the shortest
“Guaranteed to be the shortest, under normal circumstances.”
What are some examples of abnormal circumstances?
Non Euclidian spaces, heuristics where the goal isn't shortest straight line
i was looking away when you came back from code and the echo made me think for a split second you were in a bathtub.. That might be a good bit, if you're in a different place each time you come back from code
PATH FINDING..cpp [Error] olcConsoleGameEngine.h: No such file or directory.
Someone please help me to fix this error. I am running it in dev c++. Please help me.
Hello, may I ask about why didn't you set up a destructor for this class ? Won't it cause memory leak ? BTW, if we set up a destructor, will it clean up the allocated memory automatically when we close the console window ?
Excuse me! Anyone can help me with this problem? When I run code, there are some errors: "Invalid narrowing conversion from int to short" in line 414 and Exception Thrown "Write access violation" in line 434. All of them are in file ConsoleGame.h. I'm a newbie starting with the A* algorithm. Thanks a lot!
there is an issue here.. C got updated but C could have been the the lowest cost to D afterwards but it never got checked again
I got the error buddy. Please help me "Cannot open include file: 'olcConsoleGameEngine.h': No such file or directory"
Hi Faizan, have you downloaded it from the github repo, link in description.
This video is really helpful but Can you please add a video for Hybrid A* algorithm for pathfinding
Hey thanks mate. This was again a greate tutorial and I really did learn a lot about the A* algorithm!
It also fairly interesting how damn simple this method is...
I thought it might be way more complicated than this. 😄
Great video but the time complexity of this is of the charts mate xD
Thanks! You are quite right though, search algos take a lot of time. You can help reduce time by constraining the nature of the area being searched. Whats worse, is the time is not consistent, so you can get huge variability depending on the available paths
@@javidx9 i m also refering to the implementation. for example using a priority queue instead of a list would be much more effecient
but i get that the point of the video was to graphically demonstrate the algorithm
Oh I completely agree, a priority queue is the right approach
Hope someone can help: Hi I see your code, thank you for sharing but I would like to ask a question: where should I delete the nodes pointer? Because you used the new operator. or can we use a smart pointer to delete itself automatically?
can you please teach how to make travel planner using dijkstra algo
I wish in your chart you hadn't used diagonal lines. I'm trying to understand ASTAR with only horizontal and vertical movements.
Then don't link the nodes diagonally...
@@javidx9 But your chart does use diagonal slopes ... I'm really trying to understand this at a gamer's perspective where diagonal movements are forbidden ... I'm browsing around.
@@javidx9 I was successful. Somehow I developed my own custom AStar (Mystar?). It is considerably simpler than this, works the same, yet does it without doing comparisons for dead-ends.
It can work diagonally or UDLR with a single flag. Sometimes the brain figures out new things. I appreciate your attempt to teach me this though.
i made the similarcode as you did, but the end node cant refer its parent... in the a* function
Amazing!
Can anyone explain why he chose to use the Euclidean distance (L2 norm) and not the Manhattan distance (L1 norm)? I thought using the L1 norm (abs(p1 - p2) + abs(q1 - q2)) gives a more accurate calculation of distance on a taxicab metric (grid discretization) like he used?
The algorithm only requires a global heuristic to bias the path towards the end result and makes no assumptions about the nature or viability of the path. Thats why its a neat algorithm. Your approach suggests the algorithm relies upon a discrete grid, it does not, and in fact is not even constructed a such. The code shown works for arbitrary nodes in n dimensional space, as long as the heuristic makes sense. Rendering as a grid is more about making a convenient user interface and simplification of the algorithmic generation of a base graph and presents utterly no foundation to the A* algorithm.
Wow, thanks dude
Cheers traktor!
Theory of graphs !!!
This code will be very usefull for the police cars from your big proyect of GTA 1. When will you finish the proyect?
Sadly 99.9% of people are too stupid to enjoy videos like that, but i personally enjoy these videos.
Hi I am new to all this, where do I put the code and how to apply it on a robot.