 VIDEO

Pathfinding - Understanding A* (A star)

Description:
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: https://github.com/Matthew-J-Spencer/Pathfinding ❤️ Become a Tarobro on Patreon: https://www.patreon.com/tarodev ========= 🔔 SUBSCRIBE: https://bit.ly/3eqG1Z6 🗨️ DISCORD: https://discord.gg/GqeHHnhHpz ✅ MORE TUTORIALS: https://www.youtube.com/tarodev

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.
Hexagonal grid and pathfinding there was rather tricky to implement. Did that 15 years ago in Flash.
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~
Thank you.
@Tarodev Thank you for this clarification.
@Longue Mire 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 Excuse me, but If I understand correctly, we calculate the heuristic with the function GetDisctance(ICoords other) ?
You are most welcome
what if I had trillions of nodes in a grid, your video is a crap video to gain views, don't watch it guys, another asshole thinking teaching us about pathfindings.
Are you okay, sir?
@Tarodev thank bro
Seems to be working for me. Here, I hosted it in another location for you: https://www.dropbox.com/s/yi9d845ffk3rkx3/Tarodev%20Pathfinding.unitypackage?dl=0
Excuse me. It's a Squid Game?
This is exactly what I've been looking for thanks for the video man, really explains it nicely.
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.
Wow, great work! Pure and simple
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
Very good explanation!
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.
@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.
The neighbours are cached at scene load, so you don't need to assign neighbours :)
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!
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!
@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!
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.
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 literally had to code my own A* a few days ago and now you uploaded this :D I'm so sad.
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.
I give this video an A*!! That intro though 🔥🔥🔥
That's cheesy bro
Literal greek god you are, very nice video
Aussie god*

Transcript:

[Music] [Music]
[Applause] [Music]
pathfinding is the concept of finding the shortest route between two points
the most popular pathfinding algorithm found in games today is the a-star
pathfinding algorithm the idea of this video is to help you truly understand
how the a-star pathfinding algorithm works by showing you a bare-bones
implementation saying that i will give you a few tips
to further optimize as well as point you to some pre-built solutions
by the way all the code will be provided in the description
alright let's get into it a-star utilizes three main numbers to
calculate the best path the g cost signifies the travel distance from the
node to the start node the h cost is the opposite in that it
represents the estimated travel cost from the node to the target node
the h cost is optimistic in nature so it will either be spot on or it will
underestimate the cost it will never give a cheaper than
possible value take this grid for example the h cost of
this node is three because it is three nodes from the target but if we put an
obstacle in the way making three moves to the target impossible the h cost
remains the same as it was only an optimistic assignment
so to iterate the actual steps required from any node will always be equal or
more than the estimated h cost the f cost is equal to the g cost plus
the h cost the lower the f cost the more attractive
it is as a pathfinding option the goal is to simply choose the lowest
f cost over and over until we reach the target node
okay let's look at a few examples of a star in action
all right so i'll begin by placing my target here
and we'll begin path finding so as you can see all the nodes have a g
cost of one as we are just one node away from our start but the h costs vary
depending on how far away they are from the target
so first we'll find our lowest f cost so
this will be four and we'll choose this so we will now move to this node and we
will check our surrounding targets again and we'll choose the lowest f cost again
and as you can see our g cost is getting larger as we're moving away from our
start position but our h cost is getting lower as we're getting closer to our
target and our f cost will stay the same as we are just raising one number and
lowering the other until we find our target okay so another
example i'll put my target here so we choose our lowest f cost
and now we have three nodes with an f cost of five so what we do is we then
turn to our h cost and we find the lowest h cost so
the closest uh estimation to our target wins so we'll choose this one and now
we've got three nodes with five as the f cost so we'll keep
choosing the lowest h cost and we'll get to our target
the reason i'm using hex grids in my examples is because every direction from
the node has a movement cost of one whereas in a square or isometric grid
the horizontal and vertical cost is 1 while the diagonal cost is 1.4
we usually multiply these numbers by 10 giving us the integers 10 and 14.
i actually use the exact same pathfinding code across all three grid
types the only difference is the distance calculations from node to node
i won't be covering how to calculate the distance for all three grid types in
this video as that falls onto general grid logic but the code for all three
will be provided in the link below okay let's dive into the code
so here is roughly what the node class looks like i've redacted a lot of
miscellaneous functionality to keep you focused on what's required
but as you can see we have a g and h floats with corresponding functions
which update them as well as an f getter which just adds j and h together we also
have a connection variable but we'll get into that a bit later
alright so we begin by taking in two arguments the start node and the target
node we create a list of our nodes that we
need to search and as we're starting obviously from the start node we will
add it to the list and we'll also create a list for our
nodes that we have already processed so that we don't double up
by the way the search nodes are green on the map and the process nodes are blue
on the map so we begin by looping over our search nodes and we will do that for
as long as there are nodes to search
or until we've found a path now that we're in the context of one of our
search nodes what we're going to do is find the current best f cost node so
first we'll just set our current to the first index in the search list then
we'll loop over all of our other search nodes to see if this new search node has
a better f score than our current one and if so we'll set it
or if it has the same f cost as our current
one we'll check to see if it's got a lower h cost uh and if so we will make
it the current but by the end of this four inch loop we will have our best
choice to set as our current node so now that we've got our node and we're about
to process it let's add it to the process list and then we'll remove it
out of the to search list so that we don't uh process it again
and now it's where it actually gets interesting
so now that we've got our best f cost uh
node we will loop over all of that node's
neighbors uh to perform some logic here so
the neighbors that we care about are the ones that are walkable
and also that we haven't actually processed them yet
so uh if they're walkable and we haven't
processed them let's uh iterate over them
so first i just cashed this boolean here just whether or not it's uh already in
the search list because we're going to use that a few times and here is
arguably the most complex part of the algorithm to actually get
your head around so if you think about it our current node here is what we have
chosen as the best node of the bunch right
which means any neighboring node that we find here
should technically come through our current node right because because as
far as we know our current node is the best node so far
so the cost to this new neighbor will be at least what it has cost to get to this
tile plus whatever it takes to get to the
next node which in uh hex grid is one so now that we've got this g cost we need
to determine if we want to actually do anything with it if it's worthwhile to
actually update uh the values in this neighbor
so we do two checks here we say is it already in the search list
and if it's not then yes we will be updating these because we haven't done
it yet or
if this new cost is actually more favorable than the one
that the node already has set okay so i'm just going to explain to you
how a node can get a new g cost so i'll set my target here and we'll begin
pathfinding and we'll come up here now take note of
this node here with a g cost of four now it has a g cluster four because it took
one two three four trips to get here so now we need to look for the next node to
process and it looks like this one will be it so just keep track of this node
here so as you can see the g cost is now
three and that is because we have uh found a better route to that tile which
is one two three so that's how a j-class can change just when the tile gets
re-evaluated for a better route
so now we can head up and finish our path
and now we have our route all right back to the code
okay so now hopefully you know why we do this check and how this can occur
just from the beginning we make this g cost we determine this new neighbor's g
cost and then we say if it's not already in the search list or if this g cost is
better than the current one that it's got
let's action it and set its values
so we'll set the g cost so basically in this function it's just saying neighbor
dot equals this new cost
we'll connect this neighbor to the current node
this is what allows us to retrace our path once we're done it's all well in
good processing until we get to our target node but if we don't know how to
recharge our path we've really done nothing at all
think of this like drawing a line from the current node to the new neighbor
this connection may change in the future but for now it's accurate
okay so just to show you how the connection hierarchy works i'm going to
put my target there and we'll begin building our path
and you can see one solid line there and then
we thought that was a better path here so we have broken it
and now our best path is here and straight down so there will always
only ever be one solid path back to the start node
okay so i hope that made sense so we set our connection and then we check to see
if this block is in the search list so in this conditional obviously we checked
to see if it wasn't in the search list but it may have actually already been in
the search list and got through on this condition
so we'll check if it's in the search list if it's not we'll set its h cost
now i set the h cost in here a lot of the times i see this actually
set here but the h cost is just heuristic and it
never changes so uh i'll just set it the one time and then we'll add this
neighbor into the search list because if you remember up here at the start of
this while loop here we determine which node in our search list is the best node
so who knows this neighbor may actually be the best node
now there's actually one last thing we need to do and that is to
check to see if our current node is actually our target node
because if that's the case then we have reached our our goal and we can return
the path so we can just slot this part in here
so after we select our best node which if if the target node is available
it will definitely be the best node so if the current node is indeed the target
node we will set our current path tile to the target node create a new list to
return we will start our while loop while this
current node does not equal the start node and we will add
the node into a list and then we will set the current path tile to the
connection if you remember we were setting the connections throughout it so
there will be a connection from all the way from the target node to the start
node once we get back to the start node we
will just return the path [Music]
so there you have it that is the entire a-star algorithm so as i mentioned
earlier this code was written for readability to ease the explanation and
there's a few things you can do to optimize the algorithm so this part here
is the slowest part of the algorithm finding the best fcos node and obviously
the more nodes you have the longer it takes to iterate through them all so
this could be replaced by a simple binary tree or
otherwise known as a heap and that way you won't have to process every single
node you'll just have to process a handful at a time alternatively instead
of directly using the class here we could extract the pathfinding data out
to a struct and then we could off load that to the job system codemonkey has a
video detailing a very efficient a-star pathfinding algorithm using the burst
compiler so check that out alternatively the a-star pathfinding project by aaron
grauberg on the asset store is a fantastic paid solution with many
different grid types and customization or if you'd just like to study the code
that i have in this project i've included the link down below it has some
regeneration and distance logic for all the three different grid types that i've
shown in this video so that might be handy for you so if you
enjoyed this video on pathfinding subscribe to the channel and i'll see
you in the next one bye