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.
@@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.
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
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.
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.
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.
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!
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.
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!
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 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.
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.
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.
+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 ## 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; }
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.
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.
@Sebastian Lague Two questions . How does he compare gCosts before setting them? If he uses hashsets, shouldn't he override GetHashCode() and Equals()? Thanks!
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.
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.
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?
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
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?
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?
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?
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.
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.
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
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
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.
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.
(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.
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.
@@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.
This series of tutorials is great! I implemented the approach in Java for the rover I'm developing. I do have a question, most likely related to some misunderstanding on my part. The algorithm as described allows for diagonal movement as well as orthogonal movement. Diagonal movement of course results from encountering an obstacle "corner". In a physical world, a real rover moving diagonally would seem likely to bump into the physical corner. There must be something about 'node radius' or logical buffering of physical obstacles via the "unworkable" layer that I fail to understand. Can you elaborate? Thanks.
Hello, super awesome explanation. How would I do, if the obstacles are not an entire node, but the obstacle is walls between the nodes? I guess it has something to do with not using a LayerMask, but instead doing it in another way. I just cannot figure it out.
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.
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
Great Tutorial, really sweet stuff - loved the heap usage for speed. ?Which code would be allowing the path to take the diagonal step(s) [ Im sure its in Pathfinding algs ], and is there an adjustment that would force only horiz/vert movement? ppl seem to call in Manhatten, but you know what i mean Id hope. Thanks again, great stuff
+Kusa Cubari actually think I got it, seems to work well : so to change to Manhatten style neighbour path, (as in path wont allow diagonal steps/movement), adjust this code in your Pathfinding.cs ** add this 'allowDiagonalPaths' variable to switch between diagonal or Manhatten style. 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; }
Hi Sebastian.Thank u for teaching us! But I have a big problem which I cant solve it out In slowmotion mode I realized that if I count the paths in 23:32 and 23:33 ,The path is not the shortest path. Is this happened becouse of the heuroistics ? I have the same problem in my paths but could find a solution.What if I need to guarentee the shortest path?Which alghortim should I use ? Sorry for my broken English.
This is great stuff! I'm trying to make this in a simplified 2D setup, which means changing a lot of Vector3 to Vector2. I think I've mostly got it figured out, but the Gizmos function only works with Vector3s. Is there a 2D way to show the path there instead? When it calls RetracePath / OnDrawGizmos.
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 I'm too implementing it for a 2d game.... I haven't started thou... For the four directions i guess, you should not give the 14 cost for dx dy... and also not consider diagonal neighbors... where x==y or x==-y along with x=0 and y=0
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 ^^
Why do you check if the node is in the open list twice in a row? If it's not in the open list wouldn't the first if check prevent it from reaching that second check anyway? Or if the first condition fails is the second condition ignored?
Hello Sebastian, Very nice tutorial. When I use this with your GRID, is perfect, but with my grid, it search only the neighbour (in a loop). Can I send you the script to tell me what is wrong?
im getting an error: The namespace `global::' already contains a definition for `Node' probably bcz both Grid.cs and Node.cs contains definiation for Node class. Why are there two classes definition?
I noticed that the tutorial is written in c# and unity and I am using c++ and openGl will the code still work? Thank you for making this I love your projects and I think this is the best a* tutorial around.
james duston Hi James, as long as you have a fairly good understanding of both c# and c++, converting the code here shouldn't be too much of a headache.
Well I do not, but I think I can learn how to. Also can you do a tutorial on S.T.R.I.P.S. planning that would be my dream come true (if it is not to much). Thank you so much.
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.
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.
I'm having difficulty understanding, where do you actually set the costs of g and f? like the values for going straight and th values for going diagonal. Help will be greatly appreciated, thanks.
The fcost is the gcost+hcost. The gcost is the distance from the endnode to the crurent node. The hcost is the distance from the start node to the crurent node. He changes them before switching from the current node to the neighbour node. Look carefully line 58~ newMovementCostToNeighbor's condition.
If anyone is implementing it in other language, g cost is autamtically set to 0 for ints in C#, so just set it to 0 in constructor, f cost is calculated in code, and set there. You only need to set the g cost to 0 and the rest will work :)
I know this is an old video but i will ask anyway. When i press play and it calculates the path, it's taking a path that is OBVIOUSLY LONGER than it could take. By this i mean sometimes after he took some turns to avoid obstacles, all the seeker would have to do is go DOWN and instead it goes diagonally until it gets in line horizontally with the target, then goes towards it. why is this? have i followed something wrong?
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
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.
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???
Thank you SOOO much!
Finally, a proper tutorial on A*. I have gone through so much BS-tutorials before arriving here. Thanks a ton!
it has been five years since this video release but its still the best tutorial.Huge thanks!
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.
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
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.
This is AMAZING. The best explanation of A* so far
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.
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.
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.
Fantastic job Sebastian ... very well done in all respects ... it is clear and professional ... thank you.
Sebastian that was some solid teaching! Exactly what I need in the most concise little package. Level up!
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?
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.
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!
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 really appreciate your Tutorials, your one of my favorite Tutor for Unity!
Amazing, finally i understand A*, Cheers bro
Thanks so much i had no idea how to do this. I didn't even know about Lists, my mind is blown.
I'm just glad you said "Fewer" corners/edges instead of "less".
This is perfect
I can now draw lines between skills on my skill tree! ^-^
Perfect tutorial, thank you for sharing this series with the community.
Very good video, finally got A* working in BP in Unreal :P
Thank you!
What a quality Tutorial! I give my highest recommendations!
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.
amazing tutorial! very indepth, great pace, very readable.
This has been a nice series so far, very good tutorial and very nice explanations
Thank you very much Sebastian. You published a perfect tutorial. Congratulations and keep on programming! ;)
Greetings from Barcelona
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.
One of my favorite things about coding is things like
Grid grid;
These are amazing Sebastian! I can't wait for the rest!
His voice is so calm
Thank you so much for this video series! All of your videos are very helpful and inspiring :)
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
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!
+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;
}
Thank you, man. Seriously. Thank you. Thank you. Thank you.
Greate tutorial, it was really simple to follow and adapt to my case. Thank you for your work !
Amazing tutorial, so well explained that not even using Unity I was still able to make my own A* pathfinding method for my game.
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 ?
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.
@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.
Thank you for the great tutorial!
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.
Thanks very much for this video.
Awesome Tutorial, and btw the way u draw X it looks like a butterfly xD
Extremely helpful, thank you
Great explanation thank you !
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.
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?
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?
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.
The perfect pathfinding video!
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.
thank you this was very clear and easy to follow :)
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?
Amazing tutorial as always
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.
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.
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??
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?
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
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.
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.
(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.
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
This series of tutorials is great! I implemented the approach in Java for the rover I'm developing. I do have a question, most likely related to some misunderstanding on my part. The algorithm as described allows for diagonal movement as well as orthogonal movement. Diagonal movement of course results from encountering an obstacle "corner". In a physical world, a real rover moving diagonally would seem likely to bump into the physical corner. There must be something about 'node radius' or logical buffering of physical obstacles via the "unworkable" layer that I fail to understand. Can you elaborate? Thanks.
Hello, super awesome explanation.
How would I do, if the obstacles are not an entire node, but the obstacle is walls between the nodes? I guess it has something to do with not using a LayerMask, but instead doing it in another way. I just cannot figure it out.
Thank you, but why calculate the neighbors tiles at each pathfinding? Once would not be enough?
Great tutorials. Thanks!
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
you are awesome! Thank you very much!
Sebastian if I'm not wrong you are not allowing for reopening of the closed nodes if the updated fcost to them is lower.
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
Great Tutorial, really sweet stuff - loved the heap usage for speed. ?Which code would be allowing the path to take the diagonal step(s) [ Im sure its in Pathfinding algs ], and is there an adjustment that would force only horiz/vert movement? ppl seem to call in Manhatten, but you know what i mean Id hope. Thanks again, great stuff
+Kusa Cubari
actually think I got it, seems to work well : so to change to Manhatten style neighbour path, (as in path wont allow diagonal steps/movement), adjust this code in your Pathfinding.cs
** add this 'allowDiagonalPaths' variable to switch between diagonal or Manhatten style.
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;
}
@@kusacubari1867 te mereses mas de 1000 likes, grande! xd
Thanks for amazing tutorial
Hi Sebastian.Thank u for teaching us! But I have a big problem which I cant solve it out
In slowmotion mode I realized that if I count the paths in 23:32 and 23:33 ,The path is not the shortest path. Is this happened becouse of the heuroistics ? I have the same problem in my paths but could find a solution.What if I need to guarentee the shortest path?Which alghortim should I use ? Sorry for my broken English.
Thanks for your tutorial,very helpfull!!!
This is great stuff! I'm trying to make this in a simplified 2D setup, which means changing a lot of Vector3 to Vector2. I think I've mostly got it figured out, but the Gizmos function only works with Vector3s. Is there a 2D way to show the path there instead? When it calls RetracePath / OnDrawGizmos.
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 I'm too implementing it for a 2d game.... I haven't started thou... For the four directions i guess, you should not give the 14 cost for dx dy... and also not consider diagonal neighbors... where x==y or x==-y along with x=0 and y=0
"One does not simply set the f_cost" xD nice meme
XD so underrated haha nice one
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
surely an optimization would be at 16:36 to simplify and say 4dstX+ 10dstY
Why do you check if the node is in the open list twice in a row? If it's not in the open list wouldn't the first if check prevent it from reaching that second check anyway? Or if the first condition fails is the second condition ignored?
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
Hello Sebastian,
Very nice tutorial. When I use this with your GRID, is perfect, but with my grid, it search only the neighbour (in a loop). Can I send you the script to tell me what is wrong?
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
im getting an error: The namespace `global::' already contains a definition for `Node'
probably bcz both Grid.cs and Node.cs contains definiation for Node class. Why are there two classes definition?
I noticed that the tutorial is written in c# and unity and I am using c++ and openGl will the code still work? Thank you for making this I love your projects and I think this is the best a* tutorial around.
james duston Hi James, as long as you have a fairly good understanding of both c# and c++, converting the code here shouldn't be too much of a headache.
Well I do not, but I think I can learn how to. Also can you do a tutorial on S.T.R.I.P.S. planning that would be my dream come true (if it is not to much). Thank you so much.
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.
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.
I'm having difficulty understanding, where do you actually set the costs of g and f? like the values for going straight and th values for going diagonal.
Help will be greatly appreciated, thanks.
The fcost is the gcost+hcost.
The gcost is the distance from the endnode to the crurent node.
The hcost is the distance from the start node to the crurent node.
He changes them before switching from the current node to the neighbour node.
Look carefully line 58~ newMovementCostToNeighbor's condition.
If anyone is implementing it in other language, g cost is autamtically set to 0 for ints in C#, so just set it to 0 in constructor, f cost is calculated in code, and set there. You only need to set the g cost to 0 and the rest will work :)
I know this is an old video but i will ask anyway. When i press play and it calculates the path, it's taking a path that is OBVIOUSLY LONGER than it could take. By this i mean sometimes after he took some turns to avoid obstacles, all the seeker would have to do is go DOWN and instead it goes diagonally until it gets in line horizontally with the target, then goes towards it. why is this? have i followed something wrong?
Sebastian what heuristic to get the distance are you using?
Manhattan ,Diagonal or Euclidean ?
Can someone tell me? Thanks :)
+Zain Ul-Abdeen Manhattan and Euclidean :)
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
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?