Pathfinding - Understanding A* (A star)
HTML-код
- Опубликовано: 10 май 2024
- Pathfinding can be a fundamental component of your game. Truly understanding how it works gives you fine-grained control of how units interact with the environment.
Learn how A* pathfinding truly works by diving deep into the mechanics. We'll go step by step through each process as well as cover the edge cases not often talked about.
Repo: github.com/Matthew-J-Spencer/...
❤️ Become a Tarobro on Patreon: / tarodev
=========
🔔 SUBSCRIBE: bit.ly/3eqG1Z6
🗨️ DISCORD: / discord
✅ MORE TUTORIALS: / tarodev
I have a degree in Computer Science. I taught algorithm analysis in college. I've been a developer for more than 10 years. This is hands down the best introduction and demonstration to A* I've seen on youtube. Concise, comes with visual examples, comes with code, and comes wiht references to other videos. WELL DONE DUDE. You just made my day.
there aren't enough tutorials (in general) that just look at code and explain it. it feels like a better use of my time than watching someone type. ty for that. i'm also always surprised how your videos are about something commonly needed but that i've rarely seen covered
This is a topic I constantly flip back and forth on (explaining typed code, or typing live). I did a poll months ago and most people said they prefer it being typed live, as it shows the thought process better, but obviously more advanced devs prefer pre-typed. So I do a bit of both.
Glad you liked it!
The time you took to make it so visual, I really appreciate it. I've never tried pathfinding and I am delaying its implementation in my own game just cuz it looked very difficult. But your explanation and way of showing so graphically for every step made it really helpful.
Thanks and I hope this channel keeps growing.
Thanks for saying that! It makes the large time investment worth while.
@@Tarodev Clear thinking, clear explanation, and clear visuals. Top notch! Had me subscribe right away.
Thank you kindly for the download. I followed both yours and Code Monkeys tutorials on grids and pathfinding. I learned a lot, but a lot is also way over my head. The download works seamlessly and I am excited to dive into the code! Thanks for all that you do :)
What a timely upload! I was just finishing writing some work and reviewing A* was one of the things I had left to finish it. Thanks for the great explanation and presentation!
I can't thank you enough for this video. No one has ever made a video that made me fully understand the algorithm like this one. Simple and to the point. Thank you greatly.
This is exactly what I've been looking for thanks for the video man, really explains it nicely.
Thanks very much for this tutorial, its straightforward and explains things well!
I came across your videos a few weeks ago and ever since I was hooked. you explain concepts so well and so clearly. Keep up the great work!
Thank you so much! Glad to have you on board
Wow, great work! Pure and simple
Wow really good explanation of the algorithm! Very informative and to the point. No unneccessary talking but still all the information needed! Great video! Thanks to you I understood simply how to implement this algorithm in just 20 minutes (stopping your video when coding myself)! Great video! Thank you very much!
I went from day 1 feeling like this was impossible, to day 3 creating my entirely own method of implementing A* pathfinding because of how you explained the rules so in depth. It's much better to have a video like this where it explains the concept and rules / fundamentals rather than just doing it and saying to copy it. Thank you very much for your work on this. Saved my life!
That's amazing man, well done!
That was such a great explanation. Thank you 😊
its either the viewer is smart enough to understand your video or your way of teaching is so good that even i can understand the A* pathfinding. but the most importantly, u give us the code :D I hope you all have a fun and great days, Thx!
Hey, wanted to say that I enjoy your simple format of these videos.
Even tho I already understand topics you present it's still enjoyable.
And these eye-candy effects and graphics do a lot!
Glad they are still entertaining even if you know the topic! Thanks mate
amazingly done & thanks i' have never done any algorithm myself but think this would be the first one, subscribed for more.
amazing, simply so good that it was enough for me to learn and also enjoy...
This was an extremely good video and the apps look REALLY educative and fresh! I have to learn and try to spread these programs for you! It is amazing how such simple applications can explain so much! MUCH LOVE FROM SWEDEN!
Thanks Jonas from sweden!
Amazing as Always!Keep it up!
Legendary A* walk through. A hero the people need!
Thinking about re releasing this with a few editing fixes
You are SPETACULAR!
Most simple/complete A* video I've ever seen.
It just works as magic!
Ah, why thank you 😊
Nicely explained and a great presentation, subbed!
Top tier/very professional, in both production and subject matter explanation.
Thanks buddy
I thought it was way more complicated, but it's pretty straightforward.
btw i would like a video on optimization
Same would love a video on optimization. Sebastian has done something with Binary Trees apparently, but I couldn't get my head wrapped around it haha
@@gadgetboyplaysmc His implementation is very good (obviously, it's Sebastian), but I could certainly do it in the next video in a more beginner-friendly way.
Or maybe I could just do a general binary tree video explaining how it works and mention at the end "By the way, you could use this to replace the F cost calculation in A*". I'll have a think
@@Tarodev One quick win is to change the processed list to be a HashSet, for quicker .Contains checks. And then yeah, a min heap tree for the search list, which takes a fair bit more work. It's also possible to convert everything to Burst and C# Jobs, including the heap - I've done it, but it sure took a lot of head-scratching and probably wouldn't make for an easily explainable YT video. Anyway, great job on this one making the general A* principles easy to understand.
@@shannonrowe9402 Ohhhh, the hashset is something I didn't think about! Very interesting.
I will just say but i don't recommend go into it without learning and playing alot, but implementing A* with JOBS (ECS) have an huge performance impact.
I tested it and it's faster and can utilize all the threads your CPU may offer decreasing the amount of work for a result. Specially in bigger maps.
Thank you. I still have troubles understanding how it works but it does. My implementation on pygame does indeed find the shortest path after watching this video.
man this is amazing. Previous video I watched on A* was going above from my head and I couldn't understand the meaning of G and H cost, from this everything is clear from the first minute of the video. Thank you for creating amazing content. I can imagine where your youtube channel gonna be in near future!
Thank you so much! This is exactly what I set out to provide in this video, so that makes me happy 😊
@@Tarodev Hope to see some small game tutorial series (with intermediate concepts) on your channel in parts soon 😍
It's probably because the other tutorial said "H Cost". Here it's careful explained as Haych Cast. Much easier to comprehend.
Very good explanation!
Very interesting!
Thank you!
Mark my words this video is about to blowup
Bless you
Excellent stuff as always!
Love you blobby
Hello, I would be very interested in the optimization follow up, and also in a fix for units moving through gaps vertically. I don’t really know how to explain it, but basically if two blocks are diagonal to each other the unit can pass between them, assuming you allow diagonal movement on a square grid
I swear to God, your videos are the best. I always loved watching Sebastian Lague's videos on these. You go into them with so much detail and I really appreciate it. What's the secret?
Even mentioning Sebastian in the same sentence as me is an honor. The secret is I get fueled by comments like this and seeing how I help people, so thank you!
You are a genius Sir, Salute!!!
Wow thanks you now I understand how A* works!
Mission accomplished :)
I had to shave and finesse in order to get this to work in my project, but extremely helpful overall, thank you very much.
Shaving and finessing is the perfect way to learn
Nice, will be sure to watch this on lunch later!
Awesome stuff and well explained - I actually prefer this method of not doing it the most optimised way at first, just to get your head around the concept, a lot of other tutorials out there set off to be the most highly efficient way of doing it but then it just gets confusing about what actually is the core basics of the algorithm. I'll have to check out the code monkey video on the job system version out of curiosity.
@@DanPos I started out with pure optimization and then when I went to explain it, it was way too convoluted. I'm glad I dumbed it way down. Code monkeys tutorial for example is hyper-optimized (the jobs one, not his first one), but very hard to follow for new devs.
I give this video an A*!!
That intro though 🔥🔥🔥
That's cheesy bro
One epic music on an epic video! well done.
Intro wasn't too dramatic? 😂
@@Tarodev that was awsome :))
Thankyou so much, I'm recreating a game in Roblox that uses A* path finding, this helped me to create my second version ever, (my first was technically by chat gpt)
Although yes this is another language for code, my brain somehow translated it! THANK YOU FOR THE VISUALS TOO!!!! You deserve every subscriber and likes
That's awesome 😂
Jessussssssssss man FINALLY a video I understand
Hey amazing tutorial! One small piece of constructive criticism, I think reading the code would be much more clear if instead of using the var keyword you used the variable type, other than that, stunning tutorial!
Very good explanation!
You should think about adding a video for advanced users to turn your example/tutorial into JOBS as it can gain alot of performance.
It will certainly be in part 2, along with a few other tid bits :) Glad you enjoyed it!
I was always scared about A* algorithm, but this video explanation really makes me feel it's easy as f
Hexagonal grid and pathfinding there was rather tricky to implement. Did that 15 years ago in Flash.
This is great! Are you gonna be doing other pathfinding algorithims?
Yes I think I may. Or at least a quick comparison of a few popular ones
I literally had to code my own A* a few days ago and now you uploaded this :D I'm so sad.
Great Tutorial and great visuals, made it really easy to understand. Just one thing around 6:30 the bg music was a bit to epic/loud.
Yeah... you're right >< I'll keep an eye on that for the next videos
Ah. Other videos only used a basic 2D grid, so this feels more understandable for practical usecases.
I know it's supposed to be a literal target, but all I can think is "oh man that octopus really needs to go to Target, what's he getting?"
He's getting a nice wall plant and bedside lamp
Imma steal that "subscribe immediately" trick i didnt' realize I wasn't subbed
YT really is a place where you need to prod people to subscribe. I watch content all the time which I enjoy and would totally subscribe, but I just don't think about it until they ask me.
We are simple creatures and need guidance 😅
Hey I have a question and its very important for my study, I would like to ask if theres any other way to get the heuristic value without calculating distance? Lets say by sound? Like if a grid is emitting a sound or a signal then is it possible to use that grid as the heuristic without calculating the distance from the starting node to that signal?
Great video, but i have 1 last question: what a *current.Neighbors* array we have see in *foreach* loop on 4:38 ? How did you found the neighbors?
What would be the best way to implement this into the Game Grid Tutorial project?
Thank you for awesome guides! Started learning Unity with your videos on 2D Game Grid. Always wanted to make a puzzle-tactics game. One important noob question: is this a good idea to learn Bolt system? Or basic scripting is more efficient and better in the long run? It is quite tempting to learn visual system of Bolt but I am afraid it can lead a novice off track. It is also a bit confusing and timeconsuming to grasp both systems. Would appreciate your advice!
Learning Bolt will pigeon hole you into only being a visual scripting game dev. Learning to code means not only can you work on games, you can also get employment as a programmer anywhere. Strongly recommend learning to program my guy.
@@Tarodev Yeah, thanks. "There is no easy way out. There is no shortcut home!". A clean code also looks much better than those spaghetti-like arrows of Bolt!
Super curious if this can be converted to C++ to improve performance and smoothly match with Unreal Engine. I'm working on gathering the foundation pieces for an rts game and I need a pathfinding algorithm for it. So far I've discovered flowfields, deterministic lockstepping and this. In your opinion which of these would work best and why?
For context, the game is supposed to have 2 to 8 players in a game at a time, with approximately 2000 actors assuming everything goes overboard and everybody maxes out on population count.
Also looking for resources on rendering engines that handle lots of entities better than the current replication system.
Sorry if this was long winded and thanks for the awesome video!
been working on A* for a couple of days now so your video gave me a great boost in the right direction!
still have one problem tho,
my algorithm (which looks exactly like yours)
always gives me a path, but it's rarely the most efficient one,
the path traced back from the end always seems to bump into a wall and then change direction instead of opting to go around it from the start. any tips as to how to debug my code?
cheers
I'd say setup some debug lines (like I did) indicating the last few path calculations. It'll help you see what your silly unit it thinking. Also, ensure your distance calculation is correct as that can throw off the best path. For example if I just swap out my distance for vector2.distance it'll be way off. Maybe check out the package I provided for what I do.
Not updating the G cost when it's more favorable can also give less-than-ideal paths. I know you said your code is the same, but I've seen a lot of attempts leave that out.
Thank you.
You are most welcome
@@Tarodev Excuse me, but If I understand correctly, we calculate the heuristic with the function GetDisctance(ICoords other) ?
@@longuemire748 That is where I do the distance calculation, yes. It's an interface method so that I can re-use the same pathfinding logic for all 3 tile types.
H cost will be the estimated cost to the target, without taking into account obstacles.
@@Tarodev Thank you for this clarification.
I have a question, how is the cost to neighbor and the cost to defined? the "G" and "H" do they stay stored or they are reprocessed everytime we run the code with a new origin and target?
I know A*, but the way you explained it is an ART! Even my cat would understand it and start to code :D BUT - the background music is probably unnecessary.
Since then I've learned what volume levels voiceover/music/sfx should be. Wish I could go back and change it :D
Yes
So if I was trying to implement a system where there are different terrain types with varying traversal difficulties, would I want to have a multiplier assigned to the tile that would modify the G/H value calculated? How would you recommend doing that?
That's exactly how I'd recommend it!
i wasnt comparing H if F were same, lol the improvement in time
What do i do about the Neighbors, Walkable and GetDistance() red squiggly lines?
Claro que funciona asi pero la duda es como calcula si la cuadricula es valida o no
I know this is old but i cant figure out how to use the iCoords interface. Or more accurately I think i am failing to set the Icoords. I am trying to pass it a vector2 but it doesnt like that, video doesnt really cover this bit, any where i can see something that does?
Came for the pathfinding. Stayed for the multiple pronunciations of "H" :D
For real tho, fantastic tutorial.
This video was enlightening as I never knew I did that...
Hey! I've been tinkering with optimizations for the heuristic cost function (the one that returns your G and H costs) and I've found out that using Manhattan algorithm yields significantly faster results, here's the function in case someone want's to try it.
float Manhattan()
{
var dist = new Vector2Int((int)Math.Abs(from.transform.position.x - to.transform.position.x), (int)Mathf.Abs(from.position.z - to.position.z));
return dist.x + dist.y;
}
float Manhattan3D()
{
var dist = new Vector3Int((int)Math.Abs(from.transform.position.x - to.transform.position.x), (int)Mathf.Abs(from.position.z - to.position.z), (int)Mathf.Abs(from.position.y - to.position.y));
return dist.x + dist.y + dist.z;
}
The nested `if` statement at 7:10 confused me a little bit since `!inSearch` appears twice there..
How about splitting it into two parts? like this:
```
if (!toSearch.Contains(neighbor)) {
// set G and Connection
// set H and Add Node
}
else if (costToNeighbor < neighbor.G) {
// only set H and Add Node
}
```
It seems clearer to me ;)
Oh wait..I come up with a better idea..Just pull the inner `if` statement out of the outer one:
```
if (!inSearch || costToNeighbor < neighbor.G) {
// set G and Connection
}
if (!inSearch) {
// set H and Add Node
}
```
It works in the same way, but now there is no duplicate code or nested statement anymore~♪(´▽｀) Easier to understand~
And how would you do something that is dealing with many floors? Like Stairs?
You add modifiers to the different types. Sand might have a modifier of 1.5, so the F cost would come out as more expensive. It would make your units favor roads and dirt etc
in 6:55 where do you first set the neighbor for the "startNode"?
Reading the logic of it. it will never enter the first iteraction of the foreach, because "current.Neighbors" is empty. Unless before calling "FindPath", you already filled the neighbors of startNode.
The neighbours are cached at scene load, so you don't need to assign neighbours :)
@@Tarodev on the grid build right?
In my thinking process:
1. Construct the grid
2. Define the Node data by working on their neighbors.
Therefore when calling "FindPath", it is already there.
Thanks.
How did you know I was going to look into A* this week as a simple pathfinding system for networked play?
I was looking through your window
Looks a lot like Dijkstra's Algorithm. Do you know why this is preferred over that algorithm in the gamedev space?
A* is an upgraded dijkstra. It adds the heuristic value to predict the best path available. It's not accurate every time but it certainly gives it a boost.
What if i need every possible path not the closest path?
Literal greek god you are, very nice video
Aussie god*
Hi, is the Grid created with the Unity TileMap?
It is not, but you can still use this algorithm on a tile map
@@Tarodev Thanks for the reply :)
How would you do it within a 3D space? For like flying agents?
Just swap the y plane for the z plane to convert it to 3D. Flying agents can generally skip walls, so that's easy :)
One thing that often annoys me in how A* (or pathfinding in general) is presented is how it is always presented on an hex or square grid. I'm sure you could use coordinates 10² per 1m² to make it work over any terrain, but somehow it wouldn't be natural or efficient, would it? I wonder if a supersampling method (Poisson Disk, Quasi-Monte Carlo, N-Rook) would make it a good alternative to classic grid.
A* should work on any node based grid as long as you can comfortably calculate the heuristic. Even using completely variable node distances.
Where does the intial music in this video come from?
a year late, but hey
better late than never
Bonkers Beat Club - Ney Flute Type Beat
Here is something i always wonder, lets say you have 3 different tyles, water, road and dirt. You can drive over road and dirt, but dirt would be 3x slower. How would you calculate the fastest path to the target?
My guess is that you add another variable, lets call it S. The road would have an S value of 3 and the dirt would be 1.
With this the F variable would be G + H + S. Do you think this is a good way of calculating it? Or would you prefer another way?
Yes this is exactly how you'd do it. I've always called them modifiers, standard is 1. I multiply the cost by the modifier.
It's quick and easy and has never given me troubles.
But what if I have a big units, like 2x2? Let it be square grid.
Keep up the amazing work
Comment for RUclips algorithm
Thank you for your offering
the package and code link are not working. please reply me
Seems to be working for me. Here, I hosted it in another location for you: www.dropbox.com/s/yi9d845ffk3rkx3/Tarodev%20Pathfinding.unitypackage?dl=0
@@Tarodev thank bro
Man I just spent 2 days writing my own path finding system. It's nothing like this lmao. Not sure if its a good or bad thing... probably bad hahha
Did you say class or cast?
I have no idea babe
@@Tarodev oh you said “cost”. Of course 🙄 to early in the morning for pathfinding algorithms 🤣
@@seppukun208 did my Aussie accent throw you off? 😂
@@Tarodev I’m Australian too so super lame that I couldn’t understand you 🤣
@@seppukun208 haha, no excuse then brother 😂
I am too stupid to get this. Fuck!
It's a lot. Although the code is simple, grasping it all can take time. Just take it bit by bit.
Excuse me. It's a Squid Game?
Terrible. Didn't even show pseudocode.