A* Pathfinding (E03: algorithm implementation)
Vložit
- čas přidán 25. 08. 2024
- Welcome to the third part in a series on pathfinding in Unity. In this episode we implement the A* search algorithm
(explained in detail in part one: • A* Pathfinding (E01: a... )
Source code: github.com/Seb...
If you'd like to support these videos, you can do so with a recurring pledge on Patreon, or a one-time donation through PayPal. / sebastianlague
www.paypal.me/...
I went through so many videos on A star pathfinding before I found this one, and it was perfect. thanks!
Exceptional Tutorial! I was personally learning to code this algorithm in Java not Unity, however, your tutorial was still able to guide me through the process!
An easy optimization is to create a list of neighbors for each Node when creating the grid. You can get rid of the entire loop of finding neighbors. This is especially useful if you want to increase your neighbor search for a smoother path.
and how can I implement that? sorry I'm dumb af...
Hey thanks!
Great idea, thank you!
But, wouldn't it be bad for the memory? Because sometimes we don't need to access some nodes, and they don't need to have neighbors.
@@ibrahimaslan2165 It's the clasic exchange of processing time for memory: you occupy more memory, but in exchange once it's set up it runs faster. For small maps this may be a good optimization, but for bigger maps the program may be better off as it is.
Very cool. I don't fully comprehend the logic behind this, but it's great to see this come to life and hopefully eventually I'll be able to implement this into my own game.
Update??
Update???
it has been five years since this video release but its still the best tutorial.Huge thanks!
Thank you SOOO much!
Finally, a proper tutorial on A*. I have gone through so much BS-tutorials before arriving here. Thanks a ton!
Thanks so much! I've been struggling with how to make my dijkstra's algorithm into A*; this showed me how to create the heuristic that brings the magic, and furthered my understanding of the algorithm. Also, those hash sets look pretty cool too.
Cheers
+TheRensRens You change this behaviour in the GetNeighbours method from the Grid class. Simply change this bit of code: if (x == 0 && y == 0)
to this: if (x == 0 && y == 0 || Mathf.Abs(x) + Mathf.Abs(y) == 2)
+Sebastian Lague
Hey Sebastian.
I really appreciate the tutorial, very comprehensive! However, the question you replied to seems to involve a different problem. Looking at the image TheRensRens suplied, the goal didn't seem to be to eliminate the diagonals alltogether, but rather to stop a jump toward node (1,1) from node (0,0) if (1,0) and(0,1) are occupied (i.e. the seeker jumping through the corner of an object).
For anyone runing into the same problem, here's an adjustment to the code that should help.
beneath the neighbours list in the getnaighbours function of your grid classadd:
List xRows = new List();
List yRows = new List();
xRows.Add(0);
yRows.Add(0);
for (int x = -1; x = 0 && crossX < gridSizeX && crossY >= 0 && crossY < gridSizeY && grid[crossX, crossY].walkarea)
{
xRows.Add(x);
}
}
for (int y = -1; y = 0 && crossX < gridSizeX && crossY >= 0 && crossY < gridSizeY && grid[crossX, crossY].walkarea)
{
yRows.Add(y);
}
}
Then change your for loops iterating over the nodes surrounding your seeker to for each loops using intergers in xRows and Yrows. Now your pathfinder excludes any row when the node directly in front/behind or next to your seeker during that single step is occupied. The next call on get neighbours will deliver thesel nodes on that row. causing the seeker to neatly avoid corners.
One little side note, I haven't checked this solution for performance, so be mindfull to check whether this adjustment is realy worthwhile in your own project.
Regards
+Sebastian Lague My path only works when the target is exactly southwest to the seeker. How to fix this
+Sebastian Lague How would I implement this to use 'Manhattan' pathfinding (not using diagonal movement) ?
+ZeroD I need to know too, did you find out? :v
+Sebastian Lague
## in Pathfinding.cs
bool allowDiagonalPaths;
public List GetNeighbours( Node node ){
List neighbours = new List ();
for (int x = -1; x = 0 && checkY < gridSizeY) {
neighbours.Add (grid [checkX, checkY]);
}
}
}
return neighbours;
}
After implementing this and adapting it for a X-COM style project (and possibly finally understanding it) I'm fairly certain it makes sense to zero the gCost of the startNode initially in FindPath() otherwise the movement costs will just keep increasing infinitely and sooner or later you'll end up with an overflow error. The same is still true for the final version of this tutorial code from what I can tell.
I made a grid and found neighbors in a totally different way and the rest of the code worked just the same. Thanks for all your masterclass tutorials!
Applied this for my Unreal game and worked amazingly well. Thanks for to the point explanation without any bs.
there was tears, swearing, terror and finally joy as I finally got this working thanks Sebastian Lague
May I ask how did you succeed to fit the grid to the plane aera ?
I know it's a dumb question but I'm about to slap my keyboard on the ground, I must have an error on my bottomleftpoint positions because my nodes are created +.5f y(z) and x that they should be placed at.
This is AMAZING. The best explanation of A* so far
Great job with these tutorials. High quality work. I'm just now getting my head into some game design, and these kinds of algorithms are great to learn about!
Thank you so much for this tutorial, i had a lot of trouble getting Astar to work in my game. It was very easy to follow, despite not using unity myself.
I think there is a minor bug. In RetracePath function after while loop we should write path.Add(currentNode), because startNode will not be included into the list and with non-diagonal grid movement first step can be diagonal or twice as big as intended.
This is perfect
I can now draw lines between skills on my skill tree! ^-^
Just wanted to say this helped me immensely.
Since the game I'm creating uses only orthogonal movement, I made a little ajustment on the find neighbour code so it doesn't use the diagonals and removed the "14" cost part of the code for diagonals on the distance code. It's working nicely. Thank you so much!
How did you remove the diagonals?
Sebastian that was some solid teaching! Exactly what I need in the most concise little package. Level up!
I really appreciate your Tutorials, your one of my favorite Tutor for Unity!
Amazing, finally i understand A*, Cheers bro
Very good video, finally got A* working in BP in Unreal :P
Thank you!
OMG thanks Sebastian! First video where I actually understand A* after watching it.
You are awesome, a very good teacher. I have multiple deathmatch NPCs building a height map for damage in a grid like yours so they can modify a custom navmesh and alter future pathing preferences for my final project at university and.. well I would not have been able to do it half as quickly without this. I've had to warp it quite a bit to fit but you definitely helped so thank you.
Fantastic job Sebastian ... very well done in all respects ... it is clear and professional ... thank you.
Perfect tutorial, thank you for sharing this series with the community.
Thanks so much i had no idea how to do this. I didn't even know about Lists, my mind is blown.
You could also use a min/max equation: 14*min(x,y) + 10* abs(x-y)
After viewing this piece from 16:35 or so, that somehow makes sense because with distX > distY being the if statement, they help ensure there are no negative numbers allowed for final result. I'll take the more elegant approach from you.
Please, someone, help me
I actually implementing this for a 2d game but I want only to move in four Directions (no diagonal) so how can I calculate the Distance?
@@footbx-live5965 Use the Manhattan Distance Formula to calculate the Distance when using the Cardinal Directions Only. The Manhattan Distance Formula using Unity should be Mathf.Abs(nodeA.gridX - NodeB.gridX) + Mathf.Abs(NodeA.gridY - NodeB.gridY).
@@GardenHenWalk when you say to use Manhattan Distance Formula while calculating the Distance.. In the methode GetDistance, it should be applied at the return?
For anyone still trying to use the other distance calculation just read this www.geeksforgeeks.org/a-search-algorithm/ . Read the part where they show how to calculate the distance for the other types. Hope it helps.
I'm just glad you said "Fewer" corners/edges instead of "less".
Thank you, man. Seriously. Thank you. Thank you. Thank you.
so now Im sure i understand it (after watch ep 1-10 i do it alone to this episode and I did it! :D but to this episode ;-; now only optimization, units, weights, smooth weights, path smoothing and threading ;-; ) Thank you so much for all ep.
These are amazing Sebastian! I can't wait for the rest!
What a quality Tutorial! I give my highest recommendations!
Thank you very much Sebastian. You published a perfect tutorial. Congratulations and keep on programming! ;)
Greetings from Barcelona
amazing tutorial! very indepth, great pace, very readable.
One of my favorite things about coding is things like
Grid grid;
This has been a nice series so far, very good tutorial and very nice explanations
Thank you so much for this video series! All of your videos are very helpful and inspiring :)
Thank you for the great tutorial!
I just found this code works a heck of a lot faster (300ms down to 15ms) if you use a two dimensional bool array to mark items for the closedSet, rather than closedSet being a list that is being searched through each time to test if a node is already closed.
Makes sense, if I understand. Instead of having to check the whole list, you can just feed it the exact index you need.
His voice is so calm
Greate tutorial, it was really simple to follow and adapt to my case. Thank you for your work !
Great explanation thank you !
Fucking genious!
I know this is an old comment but he didn't make this algorithm, its been a thing for over 50 years now.
*****
Yeah, but I couldn't find a good tutorial for this specific thing at the time
algorithm yes but the code itself seems pretty original
Very good job!! With subtitles would have been perfect for my poor english, but it's a nice explanation of the algorithm. Thanks so much!
You can do some more optimization by caching the startNode and targetNode in FindPath. Just create 2 global Node variables and check in FindPath after creating the nodes if they equal the cache, if so break, else assign the cache to the new nodes and continue.
Obviously your units will take time to move from one node to the next, so whats the point of recalculating the path every frame if its gonna be the same outcome, this way u just do it once on switching between the nodes.
thank you this was very clear and easy to follow :)
Amazing tutorial, so well explained that not even using Unity I was still able to make my own A* pathfinding method for my game.
Extremely helpful, thank you
Thanks very much for this video.
What a great tutorial. I'm learning so much. I was wondering how to make this so it only goes linear and not diagonal? I'm trying to make a boardgame of square rooms and not sure how to make the pathfinding for the enemies. I also found a tut on using Action Points which I'm trying to incorporate into as well. Any help would be awesome and I'd totally give credit if I ever finish and publish it.
make it so the algoritm only checks the horizontal and vertical neigbours I would say
I ported this algorithm over to C++ exactly as you have it stated here. I made my own classes to mimic what you do in C#. It works in finding a route, but it's often not the fastest route. The path often has spikes where it just wanders then gets back on course. As far as I know, my code is exactly the same, if just in C++, yet it doesn't work.
Yeah I made it in Java and it works fine but is also not always the shortest route. It goes off course in certain circumstances. My code is also the same as far as I can tell.
The perfect pathfinding video!
Awesome Tutorial, and btw the way u draw X it looks like a butterfly xD
Amazing tutorial as always
If anyone is watching (after 5 years) 12:20 should get corrected this iteration is pretty expensive for computing so you are far better getting it just from returning(x is meant as thisnodesX and y as thisnodesY) grid[x-1,y-1], grid[x,y-1], grid[x+1,y+1],grid[x-1,y], grid[x+1,y], grid[x-1,y+1], grid[x,y+1], grid[x+1,y+1], only if they exist obviously.
Could you explain showing code? I dont think I undestand what you mean
I know this video is old, but I just hade to mention that the way you switch between using braces and not using them for if statements is anxiety inducing
Great tutorials. Thanks!
Thanks for your tutorial,very helpfull!!!
You could use this to make a line to follow in a 3D game such as the Division where the player is the Seeker and the Target is wherever you click on in the map. At least in theory.
you are awesome! Thank you very much!
you need to calculate the distance when x and y both are equal. In this case you return either x or y * 14 as if the distance is the same in both x and y, then you have only diagonal movements available.
Hello Sebastian,
For some reason the "if (currentNode == targetNode)" is never testing true in my code. I've checked and double checked my code and it is the same as yours. It looks as though the openSet is only ever being passed the starting node and not the rest of the nodes in the grid, which would be necessary to create the path and find the node corresponding to the target node.
Further tests indicate that only 3 nodes are actually being evaluated for their fCost, gCost, etc. Any advice? Since your next tutorial is revising the section of code that searches the grid, can I potentially skip this step, move on to the heap optimization, and possibly see success there? Thanks for your help and thank you for your well made videos.
Same issue. Is this fixed ?
Thanks for amazing tutorial
@Sebastian Lague Two questions .
How does he compare gCosts before setting them?
If he uses hashsets, shouldn't he override GetHashCode() and Equals()?
Thanks!
He close them afterwrds.
The parent node of the neighbour should be the crurent node.
Great tutorial! But one question. If I change the nodeRadius in the inspector in Unity and start it seems, that it will not be properly scaled from the center of the grid. The attached object is centered.
I would recommend to use this function instead of the CalculateDistance function, because it makes the path look more natural.
private int function(Node Start, Node Destination) {
int Distance_X = (int)Mathf.Abs(Start.Grid_X - Destination.Grid_X);
int Distance_Y = (int)Mathf.Abs(Start.Grid_Y - Destination.Grid_Y);
return (int)Mathf.Sqrt(Distance_X * Distance_X + Distance_Y * Distance_Y);
}
It doesn't seems so. Maybe in some situations? But just calculating hypotenuse like you suggest makes pathfinder choose diagonals over straight lines some times. Like instead of straight path in will curl in one place which doesn't make sense in terms of efficiency.
ok I see. It looks better over big distances but still needs tweaking to be universal.
I really like this explanation of a*, it is easy to understand, but I am a bit confused about the gcost. You never initialized a nodes gcost, it only gets set by the a* algorithm. Does c# automatically initialize ints to 0 or did I miss something in the video?
Yeah, zero is the default value for ints.
I dont know since when did we set the h_cost and g_cost to compare, especially for the first element of openset (openset[0]) and it's neighbour nodes
so beautiful man..
thanks
"One does not simply set the f_cost" xD nice meme
XD so underrated haha nice one
uhm i dont know if anyone noticed but the g-cost, h-cost and f-cost isnt updated everytime the object steps on a particular node
NullReferenceException: Object reference not set to an instance of an object
Grid.NodeFromWorldPoint (Vector3 worldPosition) (at Assets/Script/Grid.cs:72)
Pathfinding.FindPath (Vector3 startPos, Vector3 targetPos) (at Assets/Script/Pathfinding.cs:19)
Pathfinding.Update () (at Assets/Script/Pathfinding.cs:15)
i think algorithm can work bit faster if you skip closedSet and use boolean "closed"/"checked" in the grid node itself. So it will allow to skip looping through closedSet to check if it contains an item or not, instead you just check flag in node itself.
If you did this can you please show me the modifications you did? For some reason this code is crashing my game and I am looking for ways to fix it
@@MolnarSPeter i'm not doing it, did many years ago, just rewached it few days ago as i was looking for different pathfinding alghoritms.
Try check some links Sebastian leave under the video, in description. There are usually link to the project video is about.
@@nightyonetwothree Nvm I just miswrote one single letter and created an infinite loop, that's what caused the issue. Thank you for the help however
surely an optimization would be at 16:36 to simplify and say 4dstX+ 10dstY
hello sebastian I follow the tutorial you do, I make your project from part 1, and in part 3 i have a trouble, the black grid is stuck, the grid does not move to follow the target and seeker but nothing error in this project, can you help me to fix them? thank u
yeah, me too. have you fix that??
16:27, I highly suggest using parenthesis in this case, I can see people getting super confused. In fact I highly recommend always using them just to delineate scope, my biggest pet peeve is when people try to Pythonize C#. I don't even know why that's allowed.
I haven't seen this anywhere else in the comments but I found that it wouldn't set the correct node for the player or seeker positions unless the gameobject with the grid generator was at 0,0,0. The fix was, in the NodeToWorldPoint method, deduct the transform.position from the world position value. So instead of:
float percentX = (worldPosition.x + GridWorldSize.x / 2) / GridWorldSize.x;
do (for both x and y):
float percentX = (worldPosition.x - transform.position.x + GridWorldSize.x / 2) / GridWorldSize.x;
Thanks for the tutorial! Gonna need to watch a few times to really get it but I was able to follow and convert it to 3D and got it working without much trouble
Did you find a solution for the fact that it wasn't always going at the node you pressed but was instead stopping before it sometimes?
Great video. I really like your explanations. Its simple and understandable. But I got a problem. I can't use g score and h score inside of property of nodes. Because my game includes more than one seeker.And I'm using virtual tile prefabs as nodes. F score is relative to the seeker. What do you think? What should I do?
Hi Sebastian, fantastic tutorial! Both visually and in content your A* videos are a delight, it is a pleasure to watch them. May I ask what Syntax-Highlighting template you are using inside MonoDevelop? Is the template available somewhere?
Thank you! You can find the theme here: pastebin.com/24Db752x
Fantastic! Thank you very much.
Gracias por el tutorial sos un capo
16:07 . Does anybody know, how to convert the heuristic / GetDistance function into using Euclidian Distaince?
just return sqrt(x-x + y-y)
Even if your nodes are spaces arbitrarily apart and you have no resemblance to a grid you can still just use actual world distance, or if you have some sort of grid and don't know/have a distance function for it.
Thanks for this
Hi sebastian. i was watching your tutorial and there is a problem i dont know where i tried to write it from you r tutorial copied it from code yo provided but still there is and error. index array out of bound :( i hope you will sort it out please.
+Asad Shabbir Same, did you find a soloution?
If anyone is interested I've extended this by also including movement, so that the "seeker" actually moves all the way towards the "target", by following the black path. I used coroutines to achieve this, and here is the modified code (note that the find path can not be called while the animation is running):
rivate Grid grid;
private bool move = false, canStart = true;
void Awake()
{
grid = GetComponent ();
}
void Start()
{
cachedSeekerPos = seeker.position;
cachedTargetPos = target.position;
FindPath (seeker.position, target.position);
}
void Update()
{
if(Input.GetKeyDown(KeyCode.Space))
move = true;
if (!move && canStart) {
if (cachedSeekerPos != seeker.position) {
cachedSeekerPos = seeker.position;
FindPath (seeker.position, target.position);
}
if (cachedTargetPos != target.position) {
cachedTargetPos = target.position;
FindPath (seeker.position, target.position);
}
} else
{
AnimatePath();
}
}
void AnimatePath()
{
move = false;
canStart = false;
Vector3 currentPos = seeker.position;
if (grid.Path != null)
{
//Debug.Log("ANIMATING PATH");
StartCoroutine(UpdatePosition(currentPos, grid.Path[0], 0));
}
}
IEnumerator UpdatePosition(Vector3 currentPos, Node n, int index)
{
//Debug.Log ("Started Coroutine...");
float t = 0.0f;
Vector3 correctedPathPos = new Vector3 (n.GetWorldPos().x, 1, n.GetWorldPos().z);
while (t < 1.0f) {
t += Time.deltaTime;
seeker.position = Vector3.Lerp(currentPos, correctedPathPos, t);
yield return null;
}
//Debug.Log ("Finished updating...");
seeker.position = correctedPathPos;
currentPos = correctedPathPos;
index++;
if (index < grid.Path.Count)
StartCoroutine(UpdatePosition(currentPos, grid.Path[index], index));
else
canStart = true;
}
The animation starts if you press "SPACE".
Dude, THANKS! I followed this tutorial and read your comment but I didn't understand much of it and didn't get it to work. Then I spent like 10 h trying to implement it myself failing miserably, finally I gave your code another chance and this time I managed to make it work(e.g. there are some undeclared variables in your code example) and boy does it look smooth! Thanks once again, much appreciated!
hi, which part of code should i modify if i want the enemy move few grids after my character move?
so the enemy not finish its pathfinding by one key press, but few turns
*i already have the code for grid movement
Dude, how did you fix it?
thank you veryyyyyyyyyyyy much :)
How I would stop the pathfinding from cutting corners on obstacles? I can't have the player cut diagonally on a corner, it needs to go around. I understand the next episodes allow for smoother pathfinding, but I'm going for a RuneScape type movement, where there is no smoothing.
Yeah I also wanted to know the most optimised way to achieve this.
First thanks for making this tutorial, i was looking for a* a lot and finally i found this. But i have a problem, when i put the target in a nearly closed path (but still there is a way to reaching the target and of course not one node, many nodes are there which are walkable ) my seeker can't find the target.
if you saw this comment, can you please tel me what is the problem?
thanks again.
perfect
A couple years late, but if anyone is trying to make an orthogonal pathfinding the approach that I took and helped me was to add this
if(Mathf.Abs(x) == Mathf.Abs(z)){
continue;
}
inside the GetNeighbours method, so on the diagonals the method is skipped just like in the 0,0 field
but will this work if you have multiple enemies which want to path find to a player? If i understand it correctly every enemy would have to have its own grid with its own path finding data so it doesnt overwrite the other enemies path finding data.
Great tutorial :D
Im very confused because you never actually set any node's gcost before running the loop, and in order to actually set gcosts in the loop, it checks by comparing gcosts, which are all null since they were never set. Maybe i missed a part of the video but it isnt working for me(then at the same time i didnt do yuor whole grid thing im trying to implement my own thing...
)
It is 0 by default. The startingNode gCost should be 0
EDIT: I've fixed it by adding an OR operator to the if statement "|| neighbor.gCost == 0". It seems to work perfectly fine.
@@pablokalemba2924 the problem that OP is having, and I am too, is that yes, the initial node is 0. HOWEVER, it compares each subsequent node's cost to the "newMovementCost".
int newMovementCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
if(newMovementCostToNeighbor < neighbor.gCost)
however, with the way this is setup, the newMovementCost will ALWAYS be bigger since it's adding 0 to literally any number bigger than 0 and then checking if it's smaller than 0.
@@dreadflint but did the algorithm not work before your changed it? sebastian lague already checked "if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))" which handles exactly the problem of not initialized gCost values, because after setting the gCost for the first time the node is added to the openSet.
@@Vishinho17 But where is neighbour.gCost set?
@@loky2111 In the next line. By default it is 0, when the node is being created (my statement of "not initialized values" might be technically wrong). So you either set a new value for gCost if the neighbor isn't in the openSet (which means it hasnt been examined yet) or you update the gCost, if the new value is better than the previous one.
Very cool! I am only wondering, what is the significance of the choice for a hash set for the closed set? I only very vaguely understand the concept of a hash, but mostly I'm curious, what is its advantage in this context?
Sebastian if I'm not wrong you are not allowing for reopening of the closed nodes if the updated fcost to them is lower.
one idea for a tutorial series is a neural network for some sort of game AI.
Good Job.
(Scuse my poor english, my natural born language is french)
Hi ! First I want to congratulate you for this tutorial series which is (in my case) really helpful !
I was wondering, if I wanted to use a similar script in a tower defense game, how would it be possible to know if building an obstacle on a certain node would make the target unreachable ? The first idea that came to me was to create a temporary obstacle, run the pathfinding again and if the target is unreachable, declare the node unbuildable and remove the temporary obstacle but I think this solution would lead to a performance drop and I'm sure there's another solution.
Thanks alot Sebastian! How much planning goes into these videos? Do you mostly make everyhing up on the spot, do you have a cheatsheet? I would love to know!
You're welcome Lethal Jam :) I always code everything before recording so I can figure out any problems beforehand and so that there are not any looong pauses while I think what to do next! After that, I usually spend a couple of minutes trying to get an idea of what order I'm going to go through things in the video (when I'm not teaching I tend to jump all over the script and it would be very confusing to learn from)
Of course videos like the first episode of this series involve tons more preparation as I've got to spend time creating all the little interactive diagrams and thinking how best to explain A*. That episode was a pain honestly haha ^^
Sebastian Lague Cool. I was wondering if you came up with all the code on the fly and I was just stupid in comparison, haha. Anyway, great videos!
+Sebastian Lague Much appreciated fella - really tidy work
Question: would it be possible to use something else instead of Gizmos. Because I would like to display the path on the final build of the project. BTW amazing tutorials you are saving people's lives.
EDIT: I managed to recreate the path by using primitive cubes, and then deleting the cube after 0.5 seconds so that the environment will keep runnibg smoothly