Why didn't KZfaq recommend this video for me, when I was searching for good A* implementation tutorial. This is the best one I've seen.

I just love this dude so much

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.

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!

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.

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

This is really good and building this in C++ makes it look like a charm. Thanks man for this!

I've been trying to get this down for a few days... this is the only one that made me understand! Thanks!

I really like the way you explained the algorithm. Thank you!

Thanks once again Javidx9. I've been trying to get my head round A* for a while.

Love the format and and structure of the videos. Keep'em coming!

Thanks! I was finally able to understand this algorithm and implement it into a Java application without needing to debug much.

Thank you for doing so much valuable work on KZfaq!

Best youtuber 100% :D Now i can test / compare other graph algorithms like this and see it visually! I love you javidx9!

Really like the presentation of these videos. :)

Thank you so much for this tutorial!!! You are awesome!

This vid saved me from failing my AI course, really good explanation of AStar!

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! :)

So glad i found your channel....its super well done...thanks a lot

Great vid, implemented your code in LUA, works like a charm.

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.

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

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!

absolutely brilliant javidx9

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

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

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.

Such an awesome dude with awesome pedagogy. He doesn't even force you to subscribe. He is like, "Have a think about subscribing".

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

Once again another video that is going to help me a lot

thank you so much, greatly appreciated!!

Great video, good pacing and explainations.

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! 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!😉👍🏻

My god the exact thing I needed thank you so much man

GREAT - Thanks for sharing! I've learned a lot from it!

Cool. I was always curious about the A* algorithm.

Excellent video short and sweet …now I’ll do a similar in JavaScript.

Its really a great explanation.

Amazing tutorials, thanks a lot

bro you explain so damn well

very nice as always :) !

AWESOME! you are the BEST!

This video is wonderful.

Really interesting topic, thanks

you my dear sir are a genius

Best channel

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?

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.

13:25 is so epic :D :D :D It's like the exact picture of all of us 🤣🤣

You're so wonderful ❤

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.

Really hooking channel. Using PGE in linux to port this one. Really, really Thanks... Muchas gracias

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

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.

Amazing!

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.

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

My datastructures and algoritms course project says thanks!

If your heuristic doesn't overestimate, you can exit as soon as you visit the end node. It will be the shortest path.

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.

Wow, thanks dude

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?

Very good. I only would change the list to priority_queue to avoid sort.

Nice one :D

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!

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?

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.

This video is really helpful but Can you please add a video for Hybrid A* algorithm for pathfinding

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.

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 ?

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 :)

You know this is bad when the node in the center is called ‘E A’

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

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?

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?

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 :(

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!

hello, is there possibility to add terrain movement penalty cost to this algorytm?

Great video but the time complexity of this is of the charts mate xD

thanks a lot

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.

The first path A* finds is always the shortest

This code will be very usefull for the police cars from your big proyect of GTA 1. When will you finish the proyect?

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

i made the similarcode as you did, but the end node cant refer its parent... in the a* function

Great Video! I think it could be improved if you included more on admissible heuristics and how to choose better ones, for example using Manhattan distance when there are no diagonals is a good choice; since we know this is the global cost when there are no obstacles. Same with L infinity distance with diagonals

Thanks

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

can you please teach how to make travel planner using dijkstra algo

Godsend

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.

Theory of graphs !!!

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

Hi I am new to all this, where do I put the code and how to apply it on a robot.

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?

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