Path Planning - A* (A-Star)

[@eemelilehtonen8628]

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

[@ivandrofly]

Indeed

[@Kuba-eb3jq]

That is because the infallible google artificial intelligence realized that you should try doing your homework on your own.

[@YorktownClass]

Dude the same thing happened to me. Thank God I found this videom

[@kobrarahmani8379]

😂😂 so true @@Kuba-eb3jq

[@kv1293]

@@Kuba-eb3jq Bro I'm trying to implement this for my own project, this stuff has actual applications outside of school lol.

[@ayushkumarsharma7019]

i know i am 7 year late but after watching soo many videos and not understanding this one is the best explanation . Thank you.

[@Gargantupimp]

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.

[@javidx9]

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.

[@70da24]

I have been looking at plenty of resources regarding this topic, AND THIS IS THE BEST ONE

[@EvolutionPCGaming]

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!

[@javidx9]

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

[@nicklansbury3166]

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.

[@javidx9]

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

[@bernardoramirez1759]

I just love this dude so much

[@TheChodex]

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

[@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.

[@AdrianDev90]

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

[@javidx9]

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.

[@theidealisticman]

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

[@jedannooway]

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

[@nicolas90]

Thank you for doing so much valuable work on KZbin!

[@WakeUp4L1fe]

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!

[@charcoalPanda]

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.

[@javidx9]

That's awesome buddy, always pleasing to hear people taking the ideas and running with it for themselves, great stuff!

[@jackhodge517]

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

[@jakegourley6916]

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

[@Jonneq]

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

[@javidx9]

Hi Jonathan, Cheers!

[@alanjaldred]

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

[@javidx9]

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!

[@alanjaldred]

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)

[@parabalani]

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

[@javidx9]

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!

[@deutschWallah]

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

[@FJMadRay]

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.

[@bobdero9883]

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

[@javidx9]

Great stuff Kareshi!

[@sk00sh]

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

[@crazydescent]

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

[@JamesSiggins]

Really like the presentation of these videos. :)

[@chriswinslow]

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

[@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.

[@mariovelez578]

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

[@GiboonCloudSmoker]

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

[@Rob_III]

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.

[@javidx9]

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.

[@AfterHoursEngineering]

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

[@javidx9]

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.

[@weitnow]

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

[@unknownman6833]

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

[@javidx9]

Hey thanks Unknown Man! Good luck with your studies!

[@mateusfelipecota]

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

[@casvanmarcel]

thank you so much, greatly appreciated!!

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.

[@javidx9]

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.

[@classawarrior]

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!

[@CalBart42]

absolutely brilliant javidx9

[@alelmcity]

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?

[@thefoolishgmodcube2644]

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

[@TanjoGalbi]

If only there was a emote for groans. Maybe this one will do instead: 😶

[@DeathAtYourDoorStep]

here’s an emote for groans 😫

[@banditbrah]

Why is it bad?

[@DandragonDe]

@@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"...

[@DandragonDe]

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

[@j.h.jun.2214]

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

[@r1pfake521]

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.

[@classawarrior]

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

[@johncramer9912]

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

[@h.cazador]

Great video, good pacing and explainations.

[@AlejandroCastilloRapper]

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

[@radijsdude]

you my dear sir are a genius

[@javidx9]

Why thank you sir! But it's an established algorithm, I merely present it in a different way.

[@MrPhounet]

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

[@javidx9]

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.

[@jarrettbaugh3015]

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?

[@UmpikLumpik]

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

[@tsraikage]

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

[@javidx9]

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.

[@Xeakerr]

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

[@soutrikmaiti4133]

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.

[@pilzj3263]

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?

[@70da24]

I am curious,why wouldn't you use min heap or RB tree (std::set ) for faster operating

[@therealsuper5828]

bro you explain so damn well

[@EzioOmer]

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

[@Abhay.Bhandari]

Its really a great explanation.

[@FairMaidenGames]

Amazing tutorials, thanks a lot

[@javidx9]

Hey no problem buddy, thanks!

[@jamesking2439]

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

[@MyChemicalBromance.]

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?

[@Kekzmann]

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.

[@NightpireVideos]

Really interesting topic, thanks

[@javidx9]

Yeah, I think its a useful algorithm

[@LeoOno]

very nice as always :) !

[@javidx9]

Thanks Leo!

[@tranlamtruong221]

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!

[@marcinziajkowski3870]

3:39 How do u know at start that "A" is 6 points? The "A" node only see "B", "E" and "F".

[@javidx9]

That is the purpose of the heuristic, it will give you an external metric of distance between nodes. It's a little contrived in my work through example, but is approximately straight line.

[@zainahmed4172]

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

[@BrekMartin]

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.

[@javidx9]

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.

[@BrekMartin]

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.

[@louisez3714]

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 ?

[@faizanamjad2352]

I got the error buddy. Please help me "Cannot open include file: 'olcConsoleGameEngine.h': No such file or directory"

[@javidx9]

Hi Faizan, have you downloaded it from the github repo, link in description.

[@alessandr0ananias]

This video is wonderful.

[@Nguyenthao-oj9ku]

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?

[@AlbertRyanstein]

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

[@justbelieve9754]

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.

[@adarshmishra7113]

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

[@hosseinsaadatzi1673]

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?

[@lilburger4274]

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

[@Chek94]

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.

[@tematoscybersage5626]

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

[@sebabuce]

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

[@dans6889]

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?

[@javidx9]

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.

[@fabiogaluppo2635]

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

[@javidx9]

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.

[@jgcooper]

shouldn't you update the list if you update once of the neighbors?

[@itaysadeh7828]

Everytime I run this it marks all of my nodes as visited and takes a lot of time, did you write something wrong or is that how it's suppose to be in the way he implemented it?

[@javidx9]

It sounds to me like your condition for stopping is not working properly, so it just keeps on going until all nodes and possible paths are tried.

[@itaysadeh7828]

@@javidx9 Yeah it was just a syntax error on my part. thanks for answering!

[@itaysadeh7828]

@@javidx9 also why did you use a list instead of a vector, or even a priority queue? if you sort it every iteration then maybe inserting logarithmically would be faster?

[@javidx9]

Yeah an insertion sort would be quicker

[@perceptoshmegington3371]

Having used "auto" to determined the return type in the heuristic and distance lambda functions, the compiler returns an error saying that a value of type "void" cannot be assigned to an entity of type "float", do you have any idea why it would resolve the type to void automatically? Thanks for any input

[@javidx9]

What is your lambda returning?

[@perceptoshmegington3371]

@@javidx9 The functions themselves seem fine but in this line: startNode->globalDist = heuristic(startNode, endNode); The issue is with the assignment so I can only assume the "auto" keyword has resolved the heuristic to be void instead of float. I'm not sure why this is since the global and local distance members are both defined as float. When both lambda functions are explicitly called later the compiler confirms both have been determined to return void!

[@javidx9]

Do you have "return" in your lambda functions?

[@perceptoshmegington3371]

Only in the first one. Well that's pretty embarrassing, thanks for your help! I'm gonna go drown myself in public now :D

[@javidx9]

Lol, we've all been there buddy!

[@prabhjeetsingharora7738]

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

[@rovshik4782]

AWESOME! you are the BEST!

[@lilburger4274]

How do you implement this on a robot

[@galbalandroid]

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!

[@PinkeySuavo]

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.

[@VoidloniXaarii]

You're so wonderful ❤

[@Farreach]

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

[@joshlengel3743]

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!

[@lephobix]

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

[@justbelieve9754]

Sir i am getting this error. Kindly resolve it. 6 34 PATH FINDING..cpp [Error] olcConsoleGameEngine.h: No such file or directory.

[@javidx9]

Did you download it?

[@justbelieve9754]

@@javidx9 Yes. But when did I run it. I got this error, that I mentioned. Sir please help me.

[@javidx9]

Well make sure it's in the same folder as all your other source files for your project.

[@justbelieve9754]

@@javidx9 Sir I just have only one source file to run that I downloaded. If there are multiple files then kindly send me the link of those files. I will be very thankful to you for this kindness.

[@justbelieve9754]

@@javidx9 Waiting for your response. Please help me.

[@terjeoseberg990]

“Guaranteed to be the shortest, under normal circumstances.” What are some examples of abnormal circumstances?

[@javidx9]

Non Euclidian spaces, heuristics where the goal isn't shortest straight line

[@haithamalnasrawi9224]

Hello sir. What is the best way to open and run this code?. I'm using the VS 2017, but I couldn't run it. I tried many time when I open this file (OneLoneCoder_PathFinding_AStar.cpp) with VS 2017. The green triangular button for running (Local Windows Debugger) is converted to (Attach).

[@javidx9]

You need to create a windows console project first and then add the cpp file to it.

[@haithamalnasrawi9224]

@@javidx9 Dear Sir. Thank you for reply. I don't why VS can't see the cpp files and .h files?. When I try to open them, it can't see them and even I put them in the same directory.

[@javidx9]

You need to add them to the project. Ie tell the compiler which files you are using

[@haithamalnasrawi9224]

@@javidx9 Ok dear sir. Now when I try to run it. It gave me a small window in front of this line in the header file (m_bufScreen[y * m_nScreenWidth + x].Char.UnicodeChar=c;). This small window called Exception Thrown, inside this window is written (Exception Thrown: write access violation. this->m_bufScreen was 0x11110112) and the Error list gave me: code C4244 and the description: 'argument' conversion from 'int' to 'float', possible loss of data. What should I do here sir?

[@haithamalnasrawi9224]

@@javidx9 By the way, I created windows console project and I add the code manually and then I add the header file from Solution Explorer. The files, am dealing with are (OneLoneCoder_PathFinding_AStar.cpp and olcConsoleGameEngine.h).

[@makhosingobe2162]

Thanks for the video, I am using code blocks and trying to run your code, unfortunately I am not able to get olcConsoleGameEngine.h file that is working, all the ones I get have got bugs. Can you post the link for the working olcConsoleEngine.h file please.

[@javidx9]

Its actually code blocks at fault in this instance. The compiler it ships with is very out of date and needs to be replaced with a modern mingw or msys2 install. In my olcPixelGameEngine.h wiki there are guides on how to do this, and i would recommend you use PixelGameEngine going forward anyway. Its very very similar to ConsoleGameEngine and so you can still follow along, but its maintained, cross platform and works with many up to date compilers.

[@MassivaRiot]

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

[@javidx9]

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

[@MassivaRiot]

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

[@javidx9]

Oh I completely agree, a priority queue is the right approach

[@a2pha]

I wish in your chart you hadn't used diagonal lines. I'm trying to understand ASTAR with only horizontal and vertical movements.

[@javidx9]

Then don't link the nodes diagonally...

[@a2pha]

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

[@a2pha]

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

[@albertopatino7244]

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

[@smartito_97]

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

[@greenpixel556]

Sadly 99.9% of people are too stupid to enjoy videos like that, but i personally enjoy these videos.