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

[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

[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

Marc LauzonTarodevSemiirsXD CedarLongue MireLongue MireTarodevLongue MireTarodevepic spacesTarodevMrNotPro FortniteMrNotPro FortniteTarodevЕвгений Иващенкоmanar HasanNick TomshoTarodevКонстантин СюзевRandomProductTarodevDer AuaPlínio JoséPlínio JoséTarodevPlínio JoséTarodevPopinguiPopinguiTarodevIst EgalTharkydota2playerTarodevLibberatorTarodevDioTarodev