Path Finding Algorithm [A* Algorithm]
ฝัง
- เผยแพร่เมื่อ 30 พ.ค. 2024
- I demonstrate how the A* algorithm works, how I implemented it, and show some interesting findings that I discovered along the way!
----------------------------------------------------------------------------------------------------------------
Thanks for watching! Please leave your comments below, I'd love to hear them! I should have my next video up next week!
----------------------------------------------------------------------------------------------------------------
Music: www.bensound.com - วิทยาศาสตร์และเทคโนโลยี
![[TH] VCT Masters Shanghai Playoffs DAY 1 // 100T vs FUT | FNC vs GEN](http://i.ytimg.com/vi/erQ7pGChzxA/mqdefault.jpg)
Thank you! You broke down something complex into something simple. I have been struggling with A*. But after your explanation, I'm going to try again : )
this is the best video explaining a *
What you have failed to mention, which is very important, is:
1. H(v) is a an *estimation* of distance between the current node and the target node.
2. There is a set of requirements for H(v) function to ensure it is finding the correct (optimal) path in the graph. These are:
a) H(v) is a (and this is a term I had to make up, cause I dont know the translation from polish - excuse me) is a low threshold estimate of the distance (which basically means, that for every node in the graph, H(v) is smaller or equal to the G'(v) - where G' stand for the summary cost of shortest path between the node v and target node)
b) H(v) is monotonous - for each edge H(u)
PLEASE !Would please recommend ME a BOOK ? I WANT LEARN YOUR EXPLANATION BUT GRAPH IS SO HARD ! THANKS IN ADVANCE
Awesome video dude. The visualization of the algorithm is amazing, and you gave just the right of information about how the algorithm works. Bravo.
Thanks! That's exactly what I was going for! I wanted to give enough detail without rambling on for 30 minutes.
I am working on humans evacuation dynamics.
Your explanation is quite helpful. Thanks
Awesome work!
How do current nodes and previous nodes change throughout the pathfinding?
Hi take a look at recent grid based optimizations of a* like Jump point search and Rectangular Symmetry Reduction. also compare your changes to the cost functions to Bredth first search and Depth first search.
this is great ! thanks
This is soo cool. Thanks for the video.
Amazing video concise and comprehend. Looking forward to see more from you!
Any chance your algorithm is on github or something, including the interactiveness?
Sorry, I have chosen to keep my IP private.
What software do you use to test the algorithm or refine it (like in your example)? Do you build it from scratch on something using python or use something like matlab or others to get it?
The algorithm and animation was written entirely in matlab.
Alright thanks
hi man, awsome video, btw what software do you use to visualize the algorithm's behavior like that, its pretty helpful. Could you tell us? :p
I wrote my visualization code using a program called Matlab. If you are at a university, your school probably offers licenses for free. www.mathworks.com
My other diagrams and animations were created using various animation software.
How does the algorithm get the H-cost? I mean we dont know the way from the current Position to the end..
I also see you have calculated the F-Cost. What algo did you use for that. As there might be various paths to calculate that.
Herotruth, thanks for both of your questions. I will try to answer both of them here. In my example, the f-cost is simply a linear combination of the g and h costs. Formally written: f(g, h) = ag + bh, where a and b are constants. For most of the video, I make a = b = 1. At the end of the video, I talk about making the costs more expensive. Basically, I was changing the constants in the f-cost formula. If I set a = 1000 and b = 1, the g-cost gets expensive, and simulates the BFS approach. Alternatively, if I set a= 1 and b = 1000, the h-cost gets expensive and simulates the DPS approach. Optimizing between the two approaches to find the best and fastest solution is an interesting problem worth pursuing.
I dont know when and why it reach the end, or juat run forrever ?
It reaches the end as soon as the goal node is added to the "closed" list (meaning it's been found). At that point, the path is created by tracking the lineage of parents from the goal node all the way back to the start (like following a trail of breadcrumbs).
Great video! Can you kindly share the MATLAB code for this?
Finding the shortest distance between two paths... Wouldn't that be like finding the displacement verses the finding the distance? Very good video, by the way.
Soldier ofYHVH what do you mean? Do you mean shortest distance between two points? The objective of this algorithm is to minimize the number of nodes in a path between two points.
I realize the objective of the algorithm. When you said "my algorithm will be finding the shortest path" and then you referred to that as distance later in the video, it threw me off. The algorithm is not intended to find the shortest path, it is intended to find the lowest f-cost. When you used the right triangle as an example, the hypotenuse would seem to be the displacement, and the 1 on the x axis and the 1 on the y axis would seem to be the distance. Displacement is the shortest distance between two points, and distance is the amount of space between those two points (and is longer than the path of displacement). But after watching the video several times, the shortest path isn't always possible, otherwise your object wouldn't need to calculate the lowest f-cost and could just move directly towards the target and through any obstacles. So in this instance, you are calculating the distance verses the displacement, or so it would seem. Thanks for responding, and nice video any way it goes.
Soldier ofYHVH You are correct. The purpose of this algorithm is not to calculate the displacement between two points, but rather approach a shortest path and distance through the A* algorithm process.
Could you please share your matlab code?
Are you using DFS or BFS?
I love you (no homo)
so whats the parent node!
Hey your visual graph which shows the propagation of the graph is amazing ..Can u please tell me how I can visualize this kind of propagation..? If not can you please provide me with the code..Thanks a lot :)
I created a basic animation to visualize the solutions of the algorithm. Instead of running ALL the calculations and showing the best solution, I chose to render each step of the solution. Every time a node is visited, I update the path, and then put that frame into the animation. After each step, I wait a fraction of a second so that the animation isn't too fast. You can make this kind of animation really easily. I made this animation in a couple hours having not made an animation ever before. I created mine directly in my matlab code. Good luck!
I have chosen not to share my code, as I wish to keep my IP private.
@@justindietel6127 Do you draw with the mouse all the obstacles ? How?
can you upload this code??
If there is no path, what happens?
The algorithm simply runs until there are no more nodes to visit (the "open" list is empty; every valid node has been evaluated). If the goal hasn't been found at that point, it stops and no path is ever created.
Wow
there are not 100 nodes in this example.. there are 81. you skipped over 0-10 and multiples of 10
Radu Simionescu The nodes are the intersections, not the boxes. Look at 1:38, the nodes are numbered 1-100. The corresponding node is to the lower right of each number. Hope this clears up the confusion.
I have no idea what’s going on
'your algorithm'?