Here's the long awaited A* Pathfinding tutorial! Learn all about the theory and then lets implement it in Unity. Play Awesome Games and help support the channel, get the Game Bundle 67% off - unitycodemonkey.com/gameBundle.php Stay tuned for a Unity DOTS implementation in the future!
Code can u do a part 2 on this same video implementing flocking and obstacle avoidance in the units that follow the leader? i just found your channel u teach better than my teachers lol. Like and sub! thanks for sharing.
Great Tutorial! Is there a way to avoid the character cutting Corners? How can we implement a logic which tells the character to move in orthogonal fashion when around a corner tile?
This video was exactly what I was looking for. You're understanding of OO design and data structures is very impressive. This video is not only a great resource for implementing A*, it also serves as a guide to writing clean OO code. Thanks for your work!
Another optimization tip is to use the generic Hashset instead of List for the closed node list, since you only need to check whether it contains a given node or not.
@@kalucky0 If you have your ad block as a google chrome extention, you can click it's icon in your list of extentions to the right of your url bar, and then it should have an option to whitelist a website
@@benowen8321 Unity have some interesting things with NavMeshes, but that's not really the functionality I'm looking for because of the need to bake them. I also haven't had the time to really put my mind to it what with trying to keep up with my engineering course during this outbreak, but I'll probably be able to focus on it this summer. If you like, I can let you know how it goes or give you a copy of what I did. My plan is to make an A* Pathfinding system that can be placed over any created map and with settings to allow it to be used to track atmospheric changes, heat, sound propagation, AI movement and detection.
@@liamr6761 Check out my tool unity-optimized-grid on GitHub and it will show you how to optimize the grid. The issue with this tutorial is that it is using game objects or gizmos to display the grid, and if you do it too many times then the game will lag. My node can display up to 10.000 nodes, though it can show up to million triangles, unity can only render up to 50.000. I am thinking of solving the issue with recursion, but it will be added in the next update.
For those looking for an optimised A*, checkout Sebastian Lague's pathfinding youtube series. Episodes 03 & 04 is what you will need. 03 is pretty much the same as this video, meanwhile 04 is main optimisation with Heap structure ruclips.net/video/mZfyt03LDH4/видео.html
I messed something up somewhere and now my pathfinding is always in a spiral going counter clockwise. Seconds later I relized I was ordering in a descending way so the highest FCost was always on top... making it the most inefficient pathfinding I could make.
Maybe a little Bit of a Suggestion at 11:00: You could make two Nested for loops both iterating from -1 to one. The Outer loop represents the cange on the y axis and the inner loop the change on the x axis. You Now have two add those offsets to the current Position and check if the New position go oder the boarder of the grid. This just saves a lot of writing
This is one of the decent video tutorials about A* algorithm I've found so far. It has great editing and pacing. It starts with the concept, then the pseudocode, then the application to the target platform/programming language, rather than explaining the concept while coding which majority of video tutorials do and fail. Then you also incorporate fantastic visuals. . However, and take this with a grain of salt, It would have been nice if there were explanations such as at 1:58 , getting the 1.4 for the diagonal is because of the Pythagorean theorem ( a^2 + b^2 = c^2, 1^2+1^2 = c^2, 1+1 = c^2, 2 = c^2, c = sqrt(2), c = 1.4) where the a and b are 1 unit. This small detail is something that is missing in every tutorial, even here, and this is the best of them all. And it's okay when you have an idea with A* and reviewing, but there's a reason why newbs like me are in this video in the first place. This small detail is but one of many pitfalls of tutorials and classes, free or not. The detail where you explicitly mentioned that we multiply the values by 10 so that it is expressed in integers and not float for the sake of having to see the values clearly, is great. Others just brush it off and don't bother explaining, which leads to confusion. . As mentioned by someone, showing optimization would indeed be awesome. But I think that's like asking for a dessert when you already had a free lunch from your buddy. It's not necessary, but a welcome addition if ever. . More power to you, and while I am not using Unity (i'm trying this one on Java and Javascript) I find this useful.
@@maxschafer5470 it worked at the time, I even managed it with multiple entities with multiple targets/waypoints. However, every update of Google Chrome made everything borked there and even in Mozilla (dunno how). I got tired of having to cater to different inplementations of JS on each web browser so I scrapped the whole project and charged what I did to experience. Good look to ye and yer project
Coming back here to rewatch for the 5th time. Definitely voting for another A* Pathfinding for increase performance since ECS is still not coming out soon. I really wish I could just use ECS to improve performance. Thank you for creating this video. Best explanation ever...
These videos are great man, I've only been using unity for 3 days and I'm already trying to do something that took me 4 years to work up to with python.
Thanks for a great tutorial! I tried to implement A* myself a while back in C#, and did it badly (it worked 80% of the time, all the time!), but saw this and it enabled me to implement it properly, and customise it to my project, which isn't as simple as a grid with some walls.
Admittably, this entire grid system tutorial is incredibly frustrating to follow I've come here to learn grid-based pathfinding, only to find a code that's made in "Grid System" which is then modified in "Heatmap" and updated in "Generics" The information dump was too big for me to follow specifically as i have to process all the information in all 3 videos before i can even begin to learn pathfinding. It would be alot more helpful if you have a base tutorial that shows a code that can be built upon for different mechanics rather than a code that is being constantly modified throughout different tutorials. PS: I have no problems with learning more from different tutorials, however, it is difficult to learn codes for something you're not looking for and have no uses for just to learn the code you need for a project. It can kill motivation especially if the code you need to learn is complex and mind-boggling.
Pathfinding is a complex topic so I can't really simplify it any further. If you start from the beginning rather than the end they are quite easy to follow. First you make the grid, then you make it work with generics, then you add the A* algorithm on top. Can't really do it in any other simpler way.
While i understand that Pathfinding is not meant to be simple, it's hard to follow since, as far as i can tell, i need to follow the tutorials in this sequence: Grid System in Unity (Heatmap, Pathfinding, Building Area) - As this is the base, where all the grids are built upon Cool Heatmap in Unity - Modifies the code in Grid System Powerful Generics Added! Grid System in Unity (Terraria, Minesweeper, Tilemap) - Uses certain functions and from the Heatmap code A* Pathfinding. However, even when following from Grid System to Cool Heatmap, at the very beginning, i'm seeing new lines of codes , specifically: public event EventHandler OnGridValueChanged; public class OnGridValueChangedEventArgs: EventArgs { public int x; puublic int y; } While i do not know what purpose they serve, hard copying them into the code does not work, and i do not know how to 'Make it work'. Am i still missing out on another tutorial to follow? Edit: I forgot to add Using System; (I'll slowly figure things out, but i'll take your advice to heart, thanks!)
@@gazelle4204 You'll probably just want to download the project files from this section and replace your code. Not great for learning, as you'll never find out what you missed, but there were a couple of things I had to find/sort to fill in the gaps between these videos. In general, they're not at all newbie friendly. If you're just looking for A*, check out Sebastian Lague (sp?). He has a video series that only pursue's that goal and I find to be much easier to follow. This is a more complete system than his, but if all you want is A*, his will be easier.
I have to agree with Merium. There are a lot of frustrating and seemingly pointless hoops to get through to finally get to the important stuff that we are here for. While I understand that the purpose of these videos is to introduce people to how grids work, it becomes MORE confusing because we are creating heatmaps and adding numbers only to scrap most of that code and then create something completely different right after. I'm assuming there is a reason that you had us make these scripts but it would make more sense if it came up naturally instead of all in the beginning only to have us erase and rewrite a bunch of code. I (personally) would much rather have these videos be in parts and not fast forwarded or as heavily edited because there are many times where I'm trying to pause and copy what you're writing and I end up missing something important or something is not addressed. For example, in 13:57 you can see that the list "FindPath" is private but then in 14:58 you access it without any problems, but I get an error unless I change "FindPath" to public. It would be nice if something like this was addressed so that new people don't get confused instead of editing and fast-forwarding through it.
Judging by the comments, people with little to no experience in coding and/or unity want a step by step guide on how to do this without first grasping the basics. It’s an advanced topic that you should pick up after you are comfortable with the basics, because you are going to need to adapt it to what you need and fill in the blanks. I also don’t mind that the videos are edited and leave out certain things, as it forces you to really look at the code and fix things yourself, which is actually an essential skill if you want to make your own games
@@rezaakmal9608 DOTS is the new way Unity wants you to program, it's still in beta/preview so people aren't making tutorials for it yet. But soon you'll have to learn a whole new way of programming in Unity, through DOTS tutorials. Google UNITY DOTS
@@CodeMonkeyUnity the weird thing is that my Dijkstra works 10 times faster than my A* which is super weird :) I will try to improve my implementation of the A*
Hello, so something for people who are confused as to why your line isnt showing up. Just in case it happened to anyone else, When you test for the PathFinding, the intructor types very fast, it took me about 10 rewinds of the same frame to realize they were adding a "color" field.
Not only that, but he also adds duration (it's 4th param for Debug.DrawLine method). So after color add also like .5f so your line won't flicker for milisecond, but stay visible for some time.
At 15:18 anytime I try clicking in the grid I get the error "NullReferenceException: Object reference not set to an instance of an object" and I'm not sure why.
As long as it ends up in the same place it doesn't really matter if it goes diagonal first or at the end You probably switched the order on the Neighbours test or something, but as long as the end result is the same I wouldn't worry about it
Hello, video very interesting, and that I wish to see supplemented by a session of performance improvement. Thank you for this wonderful work and good luck.
Changing the openList and closeList from a List to a Dictionary reduced the run time of the pathfinding algorithm in my game from 107 milliseconds down to 3. I think it's because the closed list gets really large and a list.contains search is O(n) but a dictionary.ContainsKey search is O(1).
Run the Pathfinding more than once. If your characters move slowly then maybe every .5 seconds should do it. It all depends on how performant the algorithm is and how much performance you can spare.
where does the "Pnode" object class come from? You have a pathnode which I created and a "P.cs" file open but i don't know what that is and I also don't know when and where you made this PNode object that has exposed X and Y values.... (around 8 minutes into your video).
hi, at 3:55 you show the code for the grid class from your previous video (which I watched and coded along with) but there is new code now in there and I don't know where it came from or what it does. I'm referring to the in the class name as well as lines 21-25, and line 31 where the grid array changed from an int array to a 'TGridObject' array to which I don't know what that is either. If you read & respond to this comment then thank you
The videos in this "series" weren't really planned ahead of time, I just started making a basic grid system and kept building things on top of it, so the order is indeed a bit tricky, I covered generics on this one unitycodemonkey.com/video.php?v=8jrAWtI8RXg
@@Beru96 He didn't show the creation of this function. It's got to be his worst coding tutorial ever. Missing functions, random entities (PNode). Utter crap.
When the origin isnt 0,0 , than the shown drawn line is showing the correct path, but starting from 0,0 still. How can I make it start from the new origin point?
I tried to follow the series, "code together" and it started super well. But then chunks of code started to appear and disappear, so I couldn't follow anymore and just downloaded the project from the site. Well, it's a completely different code, without configured scene and I have not idea how to use it. There are few compile errors and even side-projects inside the project (top-down shooter?) leading to code duplication. I believe many folks would really appreciate a solid clear working project. Thanks for the effort making these series anyway.
Yeah the thing is this wasn't planned as a series at all, it started by making a simple Grid System, then I built it up bit by bit as I needed it and I added extra features off screen when I needed them. If you watch all the videos and then inspect the code in the project files on the last video you should be able to understand how it all works.
This is really helpful video, thanks for it! But at the end of the video you are talking about the performance and "GetLowestFCoastPathNode" method. But the list we used in the method is not sorted and if we want to use "binary search" we must to sort each time the list than we can use the "binary search". Am I wrong or missing some things? Or should we use SortedList instead of regular List.
There seems to be something slightly off with the algorithm. At 15:30 you are doing initial testing with the green drawn line and it seems like it's fine. In my case, when I click around as you did, it also seems to work. Yet, when I click on a node above 0,0 on the Y-axis (e.g. 0,7) it draws a zig-zag path to the destination as opposed to a straight line as would be expected. This does not happen when clicking on a node on the X-axis (e.g. 7,0)
Did anybody else have the problem where we did test at 15:30. No matter where i clicked i just got a diagonal line from 0,0 to near the number i clicked. No path line.
Sounds like your Path just has one element on the target, sounds like it's not really calculating the pathfinding Add some Debug.Log to verify that the logic is correct
@@CodeMonkeyUnity I went through code it turns out I just had to change a value. Now works. Another question i have is any idea why my grid in the Game view starts in the middle of my camera view? Both scene and Game view? If i debug it does say mouseworldposition is 0,0.
It is a great tutorial but im having issues. i am getting error that says cannot implicitily convert type Grid to UnityEngine.Grid at the Pathfinding class 😭
This is using my custom Grid class made in the previous videos in this series ruclips.net/p/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722 It's not the built-in Unity Grid, that one is means just for tilemap visuals.
at 5:20 u said, that we have to watch into another video to see how we made the grid. but i watched the other video and i still have problems with that line of code... is there another PathNode class i missed that u created?? it always says in the error "grid does not contain a constructor, which takes 5 arguments" (poorly translated from german)
Sounds like you're missing the last parameter which creates the grid object Did you watch the video with Grid Generics? This one unitycodemonkey.com/video.php?v=8jrAWtI8RXg
Hmm interesting question, I'm not sure A* has a way to get the second best result. Maybe you could find the shortest path and add a tiny penalty to all those nodes and recalculate again, it will probably find a different path, but not necessarily the 2nd shortest
Is the GridObject which you implemented in the Grid tutorial, the same as the PathNode Object? Or do i have to use the GridObject and the PathNode Object parallel, to implement the pathfinding?
Have you tried click-spamming the same tile? The player bugs and returns to the first tile before starting to move through the path again, because it detects the first tile as the closest one to the player position, it happens to you?
@@CodeMonkeyUnity Yeah, I tried it too, but then the player can "unsnap" from the grid sometimes, by doing a not "well done" diagonal, like going between the tiles. I hope to explain well hahaha Do you have a solution for this? If not, if I find a solution I will tell you
@@CodeMonkeyUnity Okay, I've found a solution... a bit dirty, maybe, but it works xD I just wait until the next waypoint is reached, and then I start the path from that waypoint position, instead from the closest waypoint position. It works to solve both problems, but the player has to wait until it reaches the next waypoint, before starting to walk towards the next target tile again. But it's a minor problem, at least for me. I've found it because it seems to be the technique that Habbo uses.
@CodeMonkey I'm hitting an error with the line of code at 5:18, it gives me the error Delegate 'Func' does not take three arguments. Any idea on how to fix?
Is there a way to use an existing Unity Grid insead of creating your own? And also be able pull in tilemaps so you can avoid objects on tilemaps rather than having to manually black out certain squares?
Awesome tutorial man. I've been trying to set up some pathfinding in my game for a while now. The only thing I'm having trouble with is setting it up to fit a certain area/screen coverage. I know I probably have to do some stuff with the Grid or the camera, but my grid is always partially off screen to the far right unless I make it really small.
Any tips for having the pathfinding adjust to a wall being created that obstructs the current path the player is taking so that they reroute around it?
@@CodeMonkeyUnity But there is no GridSystem as in the gridSystem video, im doing this in a function passing a new Width and Height public void changeGrid(int W, int H) { pathfinding = new Pathfinding(W, H); pathfindingDebugStepVisual.Setup(pathfinding.GetGrid()); pathfindingVisual.SetGrid(pathfinding.GetGrid()); } But, this does no clean the visual of the grid created on the start. (thanks for answer!)
Hi Code Monkey, I have a problem in understanding CalculateDistanceCost(a, b) function on line 43 >> 9:16, as far as i know the Manhattan Distance formula is |a.x - b.x| + |a.y - b.y|. But i didn't get what you did on line 46 and 47, what is remaining = |xDistance - yDistance| and min(xDistance, yDistance), why remaining is multiply with Straight_Cost and min(xDistance, yDistance) is multiply with Diagonal_Cost.
It's to calculate the cost with diagonals. Calculate how many positions are straight (horizontal or vertical) and how many are diagonals. If your game doesnt use diagonals then yes you would use (a.x - b.x) + (a.y - b.y)
@@CodeMonkeyUnity hey thank you for replying, i encounter another problem... When the grid origin is (0, 0), the algorithm works fine but when i change it to (-30, -50) and click on a position(endNode), the starting position is not (-30, -50), its (0, 0). So is it must the origin to be (0, 0) only?
@@CodeMonkeyUnity Hey man, four years later, I benefited greatly from this comment. Thanks, I wanted the AI to move in straight lines when not using diagonals, not in the stepwise manner it would have done otherwise. Thanks again, great videos, I'm subscribing.
This character is using my custom animation system which is based on dynamically modifying meshes, I covered the basics of how it works here unitycodemonkey.com/video.php?v=11c9rWRotJ8
I made some mistakes in > < :D but i did it. It works well. I made random map generator with houses and they just make/connect path to each doors. Thank you.
Code Monkey i mean when i start game in unity is this function will continue while playing game not like navigating in unity navigation need bale before play and to make my question simple if I added cbe or something in the game will this function will work probably yes i mean is it will this function calculate new objects while playing game
What is the crash reason? Out of memory? All the time or only when calculating the path? The code in the video is the absolute basics, it is not optimized, you could improve it massively by using less Lists and reusing arrays which would improve memory consumption For really huge maps you need to stich them together, you can't build a single pathfinding map on a scale like Skyrim
I’ve been trying to combine this tutorial together with the ‘Grid Building System’ tutorial, but I can’t get it to work. It seems that the pathfinding requires the grid to be initiated through the ‘Pathfinding’ function and the building system requires the grid to be initiated in that specific script. Any thoughts on how to combine the two?
You shouldn't combine both grid systems, you should keep them separate, one for the building and one for the pathfinding. Then handle the interacts between them separate, when you place down a building in the building grid, get the grid position and make that on the pathfinding grid unwalkable. You can see how I made it in my XCOM game unitycodemonkey.com/video.php?v=ezlkGhFBrmg
If you are lost or confused go watch the heatmap video it appears the videos are out of order and a little is added off camera in that as well. It's all there just pause and update. (ALSO READ THE COMMENTS THEY HELP!)
If you don't have overhangs, none. You can convert a terrain into a simple 2D grid. For overhangs yes you need multiple grid systems like I did in my TBS game unitycodemonkey.com/video.php?v=y8v6Ht3rh70
This was super helpful and easy to follow, even with my different implementation via custom tiles on an isometric tilemap! Thank you so much!! Can't wait to see the DOTS version as well ;)
2:00 Why is diagonal movement associated with higher cost? These are perfect squares so the distance from the center of one square to the center of an adjacent square should be equal regardless of direction. right? So shouldn't they all have equal cost?
A diagonal is further away than a straight movement. According to the Pythagorean theorem you calculate the hypotenuse as sqrt(a^2+b^2) which in this case the sqrt(2) is 1.4
Great video and tutorial! However, is it possible to use this algorithm to walk multiple characters at the same time? I'm planning to make one character walk to the target node and the other characters to the nearby nodes. But from what I understood it's only possible to retrace the path from the target node
You can find empty positions on the grid near your target, then send character 1 to the exact target position, character 2 to one square to the side, character 3 to another nearby position, etc. Then calculate the pathfinding for all of those individually. Alternatively you can look into Flow Field Pathfinding which is a slightly different way of doing pathfinding that works great when you have lots of units you want to move from A to B
The calculate distance cost, what do you mean with go left as far as I can and go right as far as I can. If checking distance between this and next node center, why are you subtracting Xdistance and Y distance and not using pythagoras? Maybe Im missing something on this calculation
That's just a heuristic, it's a guess as to how far the target is. You can use something simple like horizontal and then vertical, or a diagonal, or any more complex algorithm, it's just a guess.
hi at 5:20 i am getting the error (CS0308: The non-generic type 'Grid' cannot be used with type arguments) wherever there is "Grid" in the Pathfinding and PathNode script
Sounds like you don't have the Grid class with generics in your project so it's attempting to use the built-in grid unitycodemonkey.com/video.php?v=8jrAWtI8RXg
Hi. Given a position in the world space (that can be not on the grid), how can I find the closest path node to that point? Do I have to iterate every node on the grid and calculate the distance for each one of them or is there a simpler solution? Thank you in advance for your answer.
If it's not on the grid then you just need to clamp the world XY against the grid min/max. So if your grid is 10x10 and you clicked on what would be 15x5, you would clamp that 15 down to 10 and get the position 10x5
yes, you need to calculate the centre to centre line lengths for the adjacent tiles , like 1.4 being a line from 0,0, to 1,1 for a square, the f value is just the addition of g and h. The h value is only a "best" guess length, you could just use a simple line length from current to final as a good guide, the path will still complete and should still give a good path.
If you’re referring to the player, simply set the player and enemy to separate layers (called “Player” and “Enemies” for example) and then under Project Settings go to Physics 2D and disable collision between these two layers in the layer collision matrix. Hope that helps!
Hi!, I'm stuck at 5:00 trying to create a new Grid inside the PathFinder class... I honestly don't know why but when I try to add the las parameter for the Grid constructor (Func) *like this* : *The problem* (GridU g,int x, int y) => new PathNode(g, x, y) The compiler throws an exception saying that Func doesn't/can't take 3 arguments ( *code exception :CS1593* ) *-----------------------* And I honestly don't know what have I done to mess this up Thanks in advance!
Func is a delegate type that takes 0 parameters and returns a PathNode Check out this video where I covered delegates in detail ruclips.net/video/3ZfwqWl-YI0/видео.html
@Fedor Russel @Ondra Maceska watch this video ( ruclips.net/video/8jrAWtI8RXg/видео.html ) at 15:05. I had the same problem cuz I just 2x:ed the generics video and missed this part. You dont need to have watched anything before if you already have the "Func do not take 3 arguments". Hope it helped, found this comment whilst trying to find a solution myself.
Not sure what you mean by "benefit", it's the actual cost of moving from the start node to the current node. The HCost is just a heuristic, the GCost is the real cost.
The "shape" depends on how you convert World Position into Grid Position on the Grid System, so if you change that math for some hex logic the shape changes
The pathfinding works great on a 20x10 grid but for some reason the character takes a while to think and then move on a 30x30 grid. Any reasons why, how can I alter the code for it to work normally on a 30x30 grid?
Yes the algorithm shown here is just the basics for how the algorithm works, it is not optimized at all. In order to make it performant on complex maps you need to add tons of optimizations, if you want to learn then yup go ahead and add them yourself, but if you just want somethin that works I would encourage you to use an asset unitycodemonkey.com/video.php?v=46qZgd-T-hk
I dont know where PNode came from but I was getting errors. I added public int GetX(){ return x; } public int GetY(){ return y; } to my PathNopde.cs and in PAthfionding.cs I added: int xDistance = Mathf.Abs(a.GetX() - b.GetX()); int yDistance = Mathf.Abs(a.GetY() - b.GetY());
@@CodeMonkeyUnity farther down in the comments you meantion not adjusting values directly like x and y. Should we just set them to public or use the helper function I posted above?
Hello code monkey at 7:20 when calculating the fcost which is gcost +hcost for entire grid you are initializing the gcost to int max but you are using the hcost uninitialized I dont know much about C# whether it iniatilizes it to 0 or is it like in C that according to the standard it may contain garbage values , my question is when calculating the fcost for the entire grid the hcost is zero? Thank you.
Can this be used on a 3d object like a plane to divide it into a grid? I'm trying to do it from your grid video but can't seem to get it to display on the plane surface
Sure, you can make a 3D grid by stacking multiple grids on top of one another, that's sort of what I did in my House Building System which has multiple grid heights using the same underlying Grid System unitycodemonkey.com/video.php?v=Cdcn6uK9gPo
Thanks for the tutorial! Im using pathfinding for many different objects, so I have the issue that I would need to clone the main grid to a var inside the object each time it has to pathfind, since if two objects are pathfinding at the same time one might overwrite the values of a tile like the F cost, then the other uses that wrong value. Im debating whether I should clone the grid or change the tile object so that it contains a list of H/G/F costs and assign an index to an object. The grid is 90x90, so cloning is quite expensive!
You should probably just keep one Pathfinding and use multithreading for the complex tasks like resetting the grid and cache the neighbour list, making clones of the grid seems like overkill Although you could make a few clones, maybe just 5 and run each in its own thread, if 5 units request a path at the exact same time just make them wait one frame.
@@CodeMonkeyUnity thanks for the reply! yeah thats exactly what I ended up doing, queue pathfinding requests and do them 1 by 1 so they dont overlap. To speed up the process I also used a binary search tree that keeps track of the minimum f and h cost node when adding/removing nodes, since you only remove the smallest node its quite easy and makes the GetLowestFCostNode() have a time complexity of O(1)! (at the cost of the open_list.Add() being slower)
@@CodeMonkeyUnity Another q - how did you added the colours and the costs to the squares after pressing the space button? Is there a tutorial i can look in to?
@@tzvikarediano965 I basically made a script that took a snapshot of the algorithm at every step of the way, I did that just to show it in the video so I'm not sure if that code is included in the project files.
If I have multiple agents exploring the grid, won't they interfere with each other as the pathfinding object writes to the grid? Should each agent have their own grid, because then I need to synchronise the walkable areas
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Here's the long awaited A* Pathfinding tutorial! Learn all about the theory and then lets implement it in Unity.
Play Awesome Games and help support the channel, get the Game Bundle 67% off - unitycodemonkey.com/gameBundle.php
Stay tuned for a Unity DOTS implementation in the future!
Was waiting for this concept ! Thank you !
Code can u do a part 2 on this same video implementing flocking and obstacle avoidance in the units that follow the leader? i just found your channel u teach better than my teachers lol. Like and sub! thanks for sharing.
Great Tutorial! Is there a way to avoid the character cutting Corners? How can we implement a logic which tells the character to move in orthogonal fashion when around a corner tile?
@@gm2529 When checking for neighbours, don't get the diagonals
Are there any news on the DOTS implementation?
This video was exactly what I was looking for. You're understanding of OO design and data structures is very impressive. This video is not only a great resource for implementing A*, it also serves as a guide to writing clean OO code. Thanks for your work!
Thanks! Glad you found the video helpful!
Spent three hours translating this task into 3D spaces, but in the end everything works!
nothing feels better than your code finally working
I'm trying to flip this on its side and apply it to platforming since noone seems to make a tutorial for it, they all just use Aron G's plugin...
unity: I will give 3d pathfinding
devs: pathfinding for 2d too, right?
unity:
devs: pathfinding for 2d too, right?
truth
Another optimization tip is to use the generic Hashset instead of List for the closed node list, since you only need to check whether it contains a given node or not.
YAY now spam clicking doesnt crash my game!
Thank you !!
I'm so used to programming in Matlab, I expected an m*n matrix of true/false for whether it was included, so you could just do a direct lookup.
I literally white listed your channel on my adblock. In impressed with your work
Thanks! Glad you like it!
How can I do that?
@@kalucky0 If you have your ad block as a google chrome extention, you can click it's icon in your list of extentions to the right of your url bar, and then it should have an option to whitelist a website
Getting this working is the happiest I've been in forever
It does feel like magic the first time you get A* working!
A video showing optimisation would be awesome. I'm thinking of having a lot of pathfinding in my game. Thanks for the tutorial. It's been very useful.
did you ever find any good resources on pathfinding optimisation?
@@benowen8321 Unity have some interesting things with NavMeshes, but that's not really the functionality I'm looking for because of the need to bake them. I also haven't had the time to really put my mind to it what with trying to keep up with my engineering course during this outbreak, but I'll probably be able to focus on it this summer. If you like, I can let you know how it goes or give you a copy of what I did. My plan is to make an A* Pathfinding system that can be placed over any created map and with settings to allow it to be used to track atmospheric changes, heat, sound propagation, AI movement and detection.
@@liamr6761 Check out my tool unity-optimized-grid on GitHub and it will show you how to optimize the grid. The issue with this tutorial is that it is using game objects or gizmos to display the grid, and if you do it too many times then the game will lag. My node can display up to 10.000 nodes, though it can show up to million triangles, unity can only render up to 50.000. I am thinking of solving the issue with recursion, but it will be added in the next update.
For those looking for an optimised A*, checkout Sebastian Lague's pathfinding youtube series. Episodes 03 & 04 is what you will need. 03 is pretty much the same as this video, meanwhile 04 is main optimisation with Heap structure
ruclips.net/video/mZfyt03LDH4/видео.html
I messed something up somewhere and now my pathfinding is always in a spiral going counter clockwise. Seconds later I relized I was ordering in a descending way so the highest FCost was always on top... making it the most inefficient pathfinding I could make.
But you found a path
People when they say they're 5 minutes away be like...
Thx for info, i'll see how i can use your mistake
Maybe a little Bit of a Suggestion at 11:00: You could make two Nested for loops both iterating from -1 to one. The Outer loop represents the cange on the y axis and the inner loop the change on the x axis. You Now have two add those offsets to the current Position and check if the New position go oder the boarder of the grid. This just saves a lot of writing
Thank you for the very clear explanation of how this works. It was dark magic to me like 25 mins ago.
Managed to utilize this in my C++ project using this video. Thank you for the detailed explaination!
That's awesome! Great job on converting to another language!
This is one of the decent video tutorials about A* algorithm I've found so far. It has great editing and pacing. It starts with the concept, then the pseudocode, then the application to the target platform/programming language, rather than explaining the concept while coding which majority of video tutorials do and fail. Then you also incorporate fantastic visuals.
.
However, and take this with a grain of salt, It would have been nice if there were explanations such as at 1:58 , getting the 1.4 for the diagonal is because of the Pythagorean theorem ( a^2 + b^2 = c^2, 1^2+1^2 = c^2, 1+1 = c^2, 2 = c^2, c = sqrt(2), c = 1.4) where the a and b are 1 unit.
This small detail is something that is missing in every tutorial, even here, and this is the best of them all. And it's okay when you have an idea with A* and reviewing, but there's a reason why newbs like me are in this video in the first place. This small detail is but one of many pitfalls of tutorials and classes, free or not.
The detail where you explicitly mentioned that we multiply the values by 10 so that it is expressed in integers and not float for the sake of having to see the values clearly, is great. Others just brush it off and don't bother explaining, which leads to confusion.
.
As mentioned by someone, showing optimization would indeed be awesome. But I think that's like asking for a dessert when you already had a free lunch from your buddy. It's not necessary, but a welcome addition if ever.
.
More power to you, and while I am not using Unity (i'm trying this one on Java and Javascript) I find this useful.
Thanks! I'm glad you found the video useful!
Curious how your Javascript implementation went. I am attempting this in Three.js for a school project.
@@maxschafer5470 it worked at the time, I even managed it with multiple entities with multiple targets/waypoints.
However, every update of Google Chrome made everything borked there and even in Mozilla (dunno how). I got tired of having to cater to different inplementations of JS on each web browser so I scrapped the whole project and charged what I did to experience.
Good look to ye and yer project
Yes, please do a video on the optimizations you talked about!
Coming back here to rewatch for the 5th time.
Definitely voting for another A* Pathfinding for increase performance since ECS is still not coming out soon. I really wish I could just use ECS to improve performance.
Thank you for creating this video.
Best explanation ever...
These videos are great man, I've only been using unity for 3 days and I'm already trying to do something that took me 4 years to work up to with python.
Thanks for a great tutorial! I tried to implement A* myself a while back in C#, and did it badly (it worked 80% of the time, all the time!), but saw this and it enabled me to implement it properly, and customise it to my project, which isn't as simple as a grid with some walls.
Admittably, this entire grid system tutorial is incredibly frustrating to follow
I've come here to learn grid-based pathfinding, only to find a code that's made in "Grid System" which is then modified in "Heatmap" and updated in "Generics"
The information dump was too big for me to follow specifically as i have to process all the information in all 3 videos before i can even begin to learn pathfinding.
It would be alot more helpful if you have a base tutorial that shows a code that can be built upon for different mechanics rather than a code that is being constantly modified throughout different tutorials.
PS: I have no problems with learning more from different tutorials, however, it is difficult to learn codes for something you're not looking for and have no uses for just to learn the code you need for a project. It can kill motivation especially if the code you need to learn is complex and mind-boggling.
Pathfinding is a complex topic so I can't really simplify it any further.
If you start from the beginning rather than the end they are quite easy to follow. First you make the grid, then you make it work with generics, then you add the A* algorithm on top. Can't really do it in any other simpler way.
While i understand that Pathfinding is not meant to be simple, it's hard to follow since, as far as i can tell, i need to follow the tutorials in this sequence:
Grid System in Unity (Heatmap, Pathfinding, Building Area) - As this is the base, where all the grids are built upon
Cool Heatmap in Unity
- Modifies the code in Grid System
Powerful Generics Added! Grid System in Unity (Terraria, Minesweeper, Tilemap)
- Uses certain functions and from the Heatmap code
A* Pathfinding.
However, even when following from Grid System to Cool Heatmap, at the very beginning, i'm seeing new lines of codes , specifically:
public event EventHandler OnGridValueChanged;
public class OnGridValueChangedEventArgs: EventArgs
{
public int x;
puublic int y;
}
While i do not know what purpose they serve, hard copying them into the code does not work, and i do not know how to 'Make it work'.
Am i still missing out on another tutorial to follow?
Edit: I forgot to add Using System;
(I'll slowly figure things out, but i'll take your advice to heart, thanks!)
@@gazelle4204 You'll probably just want to download the project files from this section and replace your code. Not great for learning, as you'll never find out what you missed, but there were a couple of things I had to find/sort to fill in the gaps between these videos. In general, they're not at all newbie friendly.
If you're just looking for A*, check out Sebastian Lague (sp?). He has a video series that only pursue's that goal and I find to be much easier to follow. This is a more complete system than his, but if all you want is A*, his will be easier.
I have to agree with Merium. There are a lot of frustrating and seemingly pointless hoops to get through to finally get to the important stuff that we are here for. While I understand that the purpose of these videos is to introduce people to how grids work, it becomes MORE confusing because we are creating heatmaps and adding numbers only to scrap most of that code and then create something completely different right after. I'm assuming there is a reason that you had us make these scripts but it would make more sense if it came up naturally instead of all in the beginning only to have us erase and rewrite a bunch of code.
I (personally) would much rather have these videos be in parts and not fast forwarded or as heavily edited because there are many times where I'm trying to pause and copy what you're writing and I end up missing something important or something is not addressed. For example, in 13:57 you can see that the list "FindPath" is private but then in 14:58 you access it without any problems, but I get an error unless I change "FindPath" to public. It would be nice if something like this was addressed so that new people don't get confused instead of editing and fast-forwarding through it.
Judging by the comments, people with little to no experience in coding and/or unity want a step by step guide on how to do this without first grasping the basics. It’s an advanced topic that you should pick up after you are comfortable with the basics, because you are going to need to adapt it to what you need and fill in the blanks. I also don’t mind that the videos are edited and leave out certain things, as it forces you to really look at the code and fix things yourself, which is actually an essential skill if you want to make your own games
Thanks!
Thanks for the Super Thanks!
Nice job with the vid, glad to see you covering A* pathfinding.
Thanks! Yeah this one has been a long time coming, now got to get to work on the Unity DOTS version.
Cool cant wait for DOTS version
SAME!
Same
what is DOTS Version means? sorry i'm a newborn :D
@@rezaakmal9608 DOTS is the new way Unity wants you to program, it's still in beta/preview so people aren't making tutorials for it yet. But soon you'll have to learn a whole new way of programming in Unity, through DOTS tutorials. Google UNITY DOTS
@@MalikenGD Gee...cooool, thanks bro/man/dude/genks/or whatever u are:D,
tats very kind of u to answer. Looooking forwards to it to then :)
Thank you, due to you today I've implemented my first A*
That's awesome! Keep it up!
@@CodeMonkeyUnity the weird thing is that my Dijkstra works 10 times faster than my A* which is super weird :) I will try to improve my implementation of the A*
@@CodeMonkeyUnity now I optimized it hardly, my Dijkstra takes 4 ms where A* takes 0 ms or 1 ms, thank you a lot, you're great
can someone tell me why we pass a referece to the grid to every node?
Just in case you need some logic from the node to know which grid it belongs to
@@CodeMonkeyUnity I was scratching my head about exactly this and was beginning to worry that I missed something essential. Thanks for clarifying!
Great Tutorial, i understand how a* pathfinding works now. i hope there are videos about optimizing this. thanks
Thanks alot for this tutorial Code Monkey. You are a life saver for my project!
Hello, so something for people who are confused as to why your line isnt showing up. Just in case it happened to anyone else, When you test for the PathFinding, the intructor types very fast, it took me about 10 rewinds of the same frame to realize they were adding a "color" field.
Not only that, but he also adds duration (it's 4th param for Debug.DrawLine method). So after color add also like .5f so your line won't flicker for milisecond, but stay visible for some time.
@@thenoideaman This comment needs to be higher up. Almost tore my hair out figuring out why the line wasn't appearing!
@@thenoideaman OMG thank you!! i was sooo confused
I love your content. Keep up the good work
is there any way to implement for different tiles to have different move speed?
At 15:18 anytime I try clicking in the grid I get the error "NullReferenceException: Object reference not set to an instance of an object" and I'm not sure why.
Use Debug.Log to find what is null unitycodemonkey.com/video.php?v=5irv30-bTJw
i tried to follow along , but for some reason it happens that the unit walks along the digonal nodes first then the horizontal ones
As long as it ends up in the same place it doesn't really matter if it goes diagonal first or at the end
You probably switched the order on the Neighbours test or something, but as long as the end result is the same I wouldn't worry about it
Hello,
video very interesting, and that I wish to see supplemented by a session of performance improvement.
Thank you for this wonderful work and good luck.
Changing the openList and closeList from a List to a Dictionary reduced the run time of the pathfinding algorithm in my game from 107 milliseconds down to 3. I think it's because the closed list gets really large and a list.contains search is O(n) but a dictionary.ContainsKey search is O(1).
For closed set you wanna use HashSet and for OpenSet use a Heap
How would you alter this for moving targets and/or realtime changing obstacles?
Run the Pathfinding more than once. If your characters move slowly then maybe every .5 seconds should do it. It all depends on how performant the algorithm is and how much performance you can spare.
@@CodeMonkeyUnity But the PNode values for x and y are accessed publicly whilst the PathNode has them private.. which should we do?
where does the "Pnode" object class come from? You have a pathnode which I created and a "P.cs" file open but i don't know what that is and I also don't know when and where you made this PNode object that has exposed X and Y values.... (around 8 minutes into your video).
It's the PathNode, I just made it previously for testing and in order to avoid duplicate class names I named it PNode during testing.
Yes I would really want to see a video on optimizing the algo..plz
hi, at 3:55 you show the code for the grid class from your previous video (which I watched and coded along with) but there is new code now in there and I don't know where it came from or what it does. I'm referring to the in the class name as well as lines 21-25, and line 31 where the grid array changed from an int array to a 'TGridObject' array to which I don't know what that is either. If you read & respond to this comment then thank you
as a disclaimer, I haven't watched the rest of the video yet, so please excuse me if these questions are already answered later on
The videos in this "series" weren't really planned ahead of time, I just started making a basic grid system and kept building things on top of it, so the order is indeed a bit tricky, I covered generics on this one unitycodemonkey.com/video.php?v=8jrAWtI8RXg
Hey thanks for the tutorial!
But Im missing one thing @ 10:50
Where did you wrote the function "GetNode" ?
It does grid.GetGridObject(x, y);
Visible at 13:30
@@CodeMonkeyUnity oh wow... im blind sorry haha. tyvm!
@@Beru96 He didn't show the creation of this function. It's got to be his worst coding tutorial ever. Missing functions, random entities (PNode). Utter crap.
When the origin isnt 0,0 , than the shown drawn line is showing the correct path, but starting from 0,0 still. How can I make it start from the new origin point?
I am getting a ton of errors because "GetNode" does not exist, what is the code for "GetNode"?
Pretty sure its this
private PathNode GetNode(int x, int y)
{
return grid.GetGridObject(x, y);
}
same dawg
I tried to follow the series, "code together" and it started super well. But then chunks of code started to appear and disappear, so I couldn't follow anymore and just downloaded the project from the site. Well, it's a completely different code, without configured scene and I have not idea how to use it. There are few compile errors and even side-projects inside the project (top-down shooter?) leading to code duplication. I believe many folks would really appreciate a solid clear working project. Thanks for the effort making these series anyway.
Yeah the thing is this wasn't planned as a series at all, it started by making a simple Grid System, then I built it up bit by bit as I needed it and I added extra features off screen when I needed them.
If you watch all the videos and then inspect the code in the project files on the last video you should be able to understand how it all works.
What if you want to restrict the movement to just linear moves ie no diagonal movement across the grid?
When getting the neighbour list at 10:39 only grab up, down, left, right
This is really helpful video, thanks for it!
But at the end of the video you are talking about the performance and "GetLowestFCoastPathNode" method. But the list we used in the method is not sorted and if we want to use "binary search" we must to sort each time the list than we can use the "binary search".
Am I wrong or missing some things?
Or should we use SortedList instead of regular List.
There seems to be something slightly off with the algorithm. At 15:30 you are doing initial testing with the green drawn line and it seems like it's fine. In my case, when I click around as you did, it also seems to work. Yet, when I click on a node above 0,0 on the Y-axis (e.g. 0,7) it draws a zig-zag path to the destination as opposed to a straight line as would be expected. This does not happen when clicking on a node on the X-axis (e.g. 7,0)
Maybe you accidentally didn't add the reference to the neighbour directly above?
Or maybe you use the wrong cost for diagonals?
I'm not getting a green line at all.. double checked all the code and have no errors or messages in the console
@@fish9388 try to set delay argument in the DrawLine() method, it helped me
@@KyryloVesna thanks will try
Did anybody else have the problem where we did test at 15:30. No matter where i clicked i just got a diagonal line from 0,0 to near the number i clicked. No path line.
Sounds like your Path just has one element on the target, sounds like it's not really calculating the pathfinding
Add some Debug.Log to verify that the logic is correct
@@CodeMonkeyUnity I went through code it turns out I just had to change a value. Now works. Another question i have is any idea why my grid in the Game view starts in the middle of my camera view? Both scene and Game view? If i debug it does say mouseworldposition is 0,0.
Very nice tutorial, well explained, even though I had to pause the video many times haha
It is a great tutorial but im having issues. i am getting error that says cannot implicitily convert type Grid to UnityEngine.Grid at the Pathfinding class 😭
This is using my custom Grid class made in the previous videos in this series ruclips.net/p/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722
It's not the built-in Unity Grid, that one is means just for tilemap visuals.
@@CodeMonkeyUnity Took me a while to realize that, appreciate your help!
at 5:20 u said, that we have to watch into another video to see how we made the grid.
but i watched the other video and i still have problems with that line of code...
is there another PathNode class i missed that u created??
it always says in the error "grid does not contain a constructor, which takes 5 arguments"
(poorly translated from german)
Sounds like you're missing the last parameter which creates the grid object
Did you watch the video with Grid Generics? This one unitycodemonkey.com/video.php?v=8jrAWtI8RXg
Fuckkkk I've been looking for this, Thank you so much@@CodeMonkeyUnity
Thanks for this video. I learned so much! I have just one more question. How can I get the second shortest path?
Hmm interesting question, I'm not sure A* has a way to get the second best result. Maybe you could find the shortest path and add a tiny penalty to all those nodes and recalculate again, it will probably find a different path, but not necessarily the 2nd shortest
Is the GridObject which you implemented in the Grid tutorial, the same as the PathNode Object? Or do i have to use the GridObject and the PathNode Object parallel, to implement the pathfinding?
Any Chance that this video would be updated for a Hex tile Pathfinding?
Have you tried click-spamming the same tile? The player bugs and returns to the first tile before starting to move through the path again, because it detects the first tile as the closest one to the player position, it happens to you?
Yes, a simple solution is to just ignore the very first path position and start from index 1
@@CodeMonkeyUnity Yeah, I tried it too, but then the player can "unsnap" from the grid sometimes, by doing a not "well done" diagonal, like going between the tiles. I hope to explain well hahaha
Do you have a solution for this? If not, if I find a solution I will tell you
@@CodeMonkeyUnity Okay, I've found a solution... a bit dirty, maybe, but it works xD I just wait until the next waypoint is reached, and then I start the path from that waypoint position, instead from the closest waypoint position. It works to solve both problems, but the player has to wait until it reaches the next waypoint, before starting to walk towards the next target tile again. But it's a minor problem, at least for me.
I've found it because it seems to be the technique that Habbo uses.
@CodeMonkey I'm hitting an error with the line of code at 5:18, it gives me the error Delegate 'Func' does not take three arguments. Any idea on how to fix?
Sounds like you have either a > or a , in the wrong place
Did you manage to fix this? I am having the same problem. Looked at what @CodeMonkeyUnity said and I don't see my problem.
nice vid, thanks and gogogo for the optimization one :)
The tutorial is very clear and helpful
I'm glad you found it helpful, thanks!
Thank you for this, really helps :)
Is there a way to use an existing Unity Grid insead of creating your own? And also be able pull in tilemaps so you can avoid objects on tilemaps rather than having to manually black out certain squares?
I just got all the positions of my tiles checked if they were null and set them to non walkable if they were not null.
How would you calculate the distance between two nodes in 3 dimensional space?
Hi, did you figured this out maybe?
Awesome tutorial man. I've been trying to set up some pathfinding in my game for a while now.
The only thing I'm having trouble with is setting it up to fit a certain area/screen coverage. I know I probably have to do some stuff with the Grid or the camera, but my grid is always partially off screen to the far right unless I make it really small.
The grid has an origin which you can modify. Or the simpler approach might just be to move the camera or change the FOV/Orthographic size
@@CodeMonkeyUnity Thanks Man!
Any tips for having the pathfinding adjust to a wall being created that obstructs the current path the player is taking so that they reroute around it?
You need to recalculate the path whenever the map changes
How could i clean the grid in order to create a new one? I want to create a dynamic size grid to this.
You can just do new GridSystem(); to create a new object. Cleaning up will depend on what data you're storing in each GridPosition
@@CodeMonkeyUnity But there is no GridSystem as in the gridSystem video, im doing this in a function passing a new Width and Height
public void changeGrid(int W, int H) {
pathfinding = new Pathfinding(W, H);
pathfindingDebugStepVisual.Setup(pathfinding.GetGrid());
pathfindingVisual.SetGrid(pathfinding.GetGrid());
}
But, this does no clean the visual of the grid created on the start.
(thanks for answer!)
Hi Code Monkey, I have a problem in understanding CalculateDistanceCost(a, b) function on line 43 >> 9:16, as far as i know the Manhattan Distance formula is |a.x - b.x| + |a.y - b.y|. But i didn't get what you did on line 46 and 47, what is remaining = |xDistance - yDistance| and min(xDistance, yDistance), why remaining is multiply with Straight_Cost and min(xDistance, yDistance) is multiply with Diagonal_Cost.
It's to calculate the cost with diagonals. Calculate how many positions are straight (horizontal or vertical) and how many are diagonals.
If your game doesnt use diagonals then yes you would use (a.x - b.x) + (a.y - b.y)
@@CodeMonkeyUnity hey thank you for replying, i encounter another problem... When the grid origin is (0, 0), the algorithm works fine but when i change it to (-30, -50) and click on a position(endNode), the starting position is not (-30, -50), its (0, 0). So is it must the origin to be (0, 0) only?
@@CodeMonkeyUnity Hey man, four years later, I benefited greatly from this comment. Thanks, I wanted the AI to move in straight lines when not using diagonals, not in the stepwise manner it would have done otherwise. Thanks again, great videos, I'm subscribing.
Awesome videos! thank you so much! did you cover the soldier creation? i would like to know how to start it. Thanks again!
This character is using my custom animation system which is based on dynamically modifying meshes, I covered the basics of how it works here unitycodemonkey.com/video.php?v=11c9rWRotJ8
I made some mistakes in > < :D but i did it. It works well. I made random map generator with houses and they just make/connect path to each doors. Thank you.
How do i make the unit not move diagonally? i tried to cheat by making the diagonal cost be 99999 but is there a proper way to do it?
On the function to GetNeighbours(); don't include the diagonal neighbours
This path finding is better than Unity nav mesh but I ask for something is this caluclation works while playing mode
What do you mean while playing mode? If you call the function it will calculate the path
Code Monkey i mean when i start game in unity is this function will continue while playing game not like navigating in unity navigation need bale before play and to make my question simple if I added cbe or something in the game will this function will work probably yes i mean is it will this function calculate new objects while playing game
As Always is Great, but didn't understand why you put variable Grid grid to the class PathNode. I think it's not necessary.
how would you change the code in order to make it not to crash on huge/difficult maps?
What is the crash reason? Out of memory? All the time or only when calculating the path?
The code in the video is the absolute basics, it is not optimized, you could improve it massively by using less Lists and reusing arrays which would improve memory consumption
For really huge maps you need to stich them together, you can't build a single pathfinding map on a scale like Skyrim
I’ve been trying to combine this tutorial together with the ‘Grid Building System’ tutorial, but I can’t get it to work. It seems that the pathfinding requires the grid to be initiated through the ‘Pathfinding’ function and the building system requires the grid to be initiated in that specific script. Any thoughts on how to combine the two?
You shouldn't combine both grid systems, you should keep them separate, one for the building and one for the pathfinding. Then handle the interacts between them separate, when you place down a building in the building grid, get the grid position and make that on the pathfinding grid unwalkable.
You can see how I made it in my XCOM game unitycodemonkey.com/video.php?v=ezlkGhFBrmg
@@CodeMonkeyUnity Damn, really didn’t think of that haha…. Thanks man!
If you are lost or confused go watch the heatmap video it appears the videos are out of order and a little is added off camera in that as well. It's all there just pause and update. (ALSO READ THE COMMENTS THEY HELP!)
What changes will be needed to apply this to 3D?
If you don't have overhangs, none. You can convert a terrain into a simple 2D grid. For overhangs yes you need multiple grid systems like I did in my TBS game unitycodemonkey.com/video.php?v=y8v6Ht3rh70
This was super helpful and easy to follow, even with my different implementation via custom tiles on an isometric tilemap!
Thank you so much!! Can't wait to see the DOTS version as well ;)
2:00 Why is diagonal movement associated with higher cost?
These are perfect squares so the distance from the center of one square to the center of an adjacent square should be equal regardless of direction. right? So shouldn't they all have equal cost?
A diagonal is further away than a straight movement. According to the Pythagorean theorem you calculate the hypotenuse as sqrt(a^2+b^2) which in this case the sqrt(2) is 1.4
@@CodeMonkeyUnity Thanks man, I'm thinking of radius.. been too many years since math class and actually visualizing these things
Literly just came to doing that in my game.
Great video and tutorial! However, is it possible to use this algorithm to walk multiple characters at the same time? I'm planning to make one character walk to the target node and the other characters to the nearby nodes. But from what I understood it's only possible to retrace the path from the target node
You can find empty positions on the grid near your target, then send character 1 to the exact target position, character 2 to one square to the side, character 3 to another nearby position, etc. Then calculate the pathfinding for all of those individually.
Alternatively you can look into Flow Field Pathfinding which is a slightly different way of doing pathfinding that works great when you have lots of units you want to move from A to B
@@CodeMonkeyUnity I appreciate the response! And great idea, I might just do that 🤝🏻
The calculate distance cost, what do you mean with go left as far as I can and go right as far as I can. If checking distance between this and next node center, why are you subtracting Xdistance and Y distance and not using pythagoras? Maybe Im missing something on this calculation
both his method and yours work.
That's just a heuristic, it's a guess as to how far the target is. You can use something simple like horizontal and then vertical, or a diagonal, or any more complex algorithm, it's just a guess.
@@CodeMonkeyUnity i see. I have looked at the code and figured it out. Cheers.
Finally. I'm too lazy to read papers.
Wow this video is gold
I'm glad you liked it! Thanks!
hi at 5:20 i am getting the error (CS0308: The non-generic type 'Grid' cannot be used with type arguments) wherever there is "Grid" in the Pathfinding and PathNode script
Sounds like you don't have the Grid class with generics in your project so it's attempting to use the built-in grid unitycodemonkey.com/video.php?v=8jrAWtI8RXg
@@CodeMonkeyUnity you were completely right thank you
How would you do this for moving on a moving object like AI on a ship?
You would anchor the pathfinding to the moving ship, instead of having a fixed origin make it linked to a certain transform.position
Working fine! Thanks for a great tutorial. Only thing is my game size is much smaller than yours, and the grid boxes are way too big for me.
The grid size is easily changeable, you can use whatever unit size makes sense for your assets
Hi. Given a position in the world space (that can be not on the grid), how can I find the closest path node to that point? Do I have to iterate every node on the grid and calculate the distance for each one of them or is there a simpler solution? Thank you in advance for your answer.
If it's not on the grid then you just need to clamp the world XY against the grid min/max. So if your grid is 10x10 and you clicked on what would be 15x5, you would clamp that 15 down to 10 and get the position 10x5
@@CodeMonkeyUnity Thank you a lot. Have a good day.
Hey can i use it for hexagonal tiles if yes what would be f and g costs??
yes, you need to calculate the centre to centre line lengths for the adjacent tiles , like 1.4 being a line from 0,0, to 1,1 for a square, the f value is just the addition of g and h. The h value is only a "best" guess length, you could just use a simple line length from current to final as a good guide, the path will still complete and should still give a good path.
Any idea why it doesnt work in the HDRP?
Pathfinding has nothing to do with rendering so whatever issue you have is not related to your render pipeline
Any tips how to avoid collision with other moving objects?
If you’re referring to the player, simply set the player and enemy to separate layers (called “Player” and “Enemies” for example) and then under Project Settings go to Physics 2D and disable collision between these two layers in the layer collision matrix. Hope that helps!
Hi!,
I'm stuck at 5:00 trying to create a new Grid inside the PathFinder class... I honestly don't know why but when I try to add the las parameter for the Grid constructor (Func) *like this* :
*The problem*
(GridU g,int x, int y) => new PathNode(g, x, y)
The compiler throws an exception saying that Func doesn't/can't take 3 arguments ( *code exception :CS1593* )
*-----------------------*
And I honestly don't know what have I done to mess this up
Thanks in advance!
Func is a delegate type that takes 0 parameters and returns a PathNode
Check out this video where I covered delegates in detail ruclips.net/video/3ZfwqWl-YI0/видео.html
@@CodeMonkeyUnity Thanks mate!
@@fedorrussel3810 So how did you manage to solve it?
@@ondrejmaceska6196 I haven't!
@Fedor Russel @Ondra Maceska watch this video ( ruclips.net/video/8jrAWtI8RXg/видео.html ) at 15:05. I had the same problem cuz I just 2x:ed the generics video and missed this part. You dont need to have watched anything before if you already have the "Func do not take 3 arguments". Hope it helped, found this comment whilst trying to find a solution myself.
HI!
I did not understand the benefit of GCost?
Not sure what you mean by "benefit", it's the actual cost of moving from the start node to the current node. The HCost is just a heuristic, the GCost is the real cost.
How do I transform the tiles to use hexagons instead of rectangles?
The "shape" depends on how you convert World Position into Grid Position on the Grid System, so if you change that math for some hex logic the shape changes
Thank you!!
The pathfinding works great on a 20x10 grid but for some reason the character takes a while to think and then move on a 30x30 grid. Any reasons why, how can I alter the code for it to work normally on a 30x30 grid?
Yes the algorithm shown here is just the basics for how the algorithm works, it is not optimized at all. In order to make it performant on complex maps you need to add tons of optimizations, if you want to learn then yup go ahead and add them yourself, but if you just want somethin that works I would encourage you to use an asset unitycodemonkey.com/video.php?v=46qZgd-T-hk
So if I were to increase the diagonal cost to something absurd, would it pathfind in 4 directions exclusivley?
If you don't want diagonals then you can just remove the diagonals from the neighbour check
I dont know where PNode came from but I was getting errors. I added
public int GetX(){
return x;
}
public int GetY(){
return y;
}
to my PathNopde.cs and in PAthfionding.cs I added:
int xDistance = Mathf.Abs(a.GetX() - b.GetX());
int yDistance = Mathf.Abs(a.GetY() - b.GetY());
The PNode is the same as the PathNode so just use PathNode insted of PNode
PNode is the same a PathNode, it's the class I was using while testing the code for the video.
@@CodeMonkeyUnity farther down in the comments you meantion not adjusting values directly like x and y. Should we just set them to public or use the helper function I posted above?
@@RonnieMcDee Both methods work, but yes using helper functions will make the code cleaner unitycodemonkey.com/video.php?v=pD27YuJG3L8
Im so confuse by the order of the videos... every I open the grid and there is something different and I have to retrack everything
me too
Here's the complete playlist ruclips.net/p/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722
@@CodeMonkeyUnity so the order is
1 4 2 3 5 6 7?
Hello code monkey at 7:20 when calculating the fcost which is gcost +hcost for entire grid you are initializing the gcost to int max but you are using the hcost uninitialized I dont know much about C# whether it iniatilizes it to 0 or is it like in C that according to the standard it may contain garbage values , my question is when calculating the fcost for the entire grid the hcost is zero? Thank you.
It initializes to 0 which is the correct value in the beginning, then it gets the proper hCost as the algorithm processes each node
what is the GetNode function, i cannot find where we created her!
Can this be used on a 3d object like a plane to divide it into a grid?
I'm trying to do it from your grid video but can't seem to get it to display on the plane surface
Sure, you can make a 3D grid by stacking multiple grids on top of one another, that's sort of what I did in my House Building System which has multiple grid heights using the same underlying Grid System unitycodemonkey.com/video.php?v=Cdcn6uK9gPo
To make A* pathfinding script do you need to make firstly Grid script(Just it?)?
The Grid is the underlying structure for the Pathfinding script so yes
For example, instead of "!isWalkable" there will be a jump zone and the jump can be ONE cell long. How can this be integrated into this algorithm?
Thanks for the tutorial! Im using pathfinding for many different objects, so I have the issue that I would need to clone the main grid to a var inside the object each time it has to pathfind, since if two objects are pathfinding at the same time one might overwrite the values of a tile like the F cost, then the other uses that wrong value. Im debating whether I should clone the grid or change the tile object so that it contains a list of H/G/F costs and assign an index to an object. The grid is 90x90, so cloning is quite expensive!
You should probably just keep one Pathfinding and use multithreading for the complex tasks like resetting the grid and cache the neighbour list, making clones of the grid seems like overkill
Although you could make a few clones, maybe just 5 and run each in its own thread, if 5 units request a path at the exact same time just make them wait one frame.
@@CodeMonkeyUnity thanks for the reply! yeah thats exactly what I ended up doing, queue pathfinding requests and do them 1 by 1 so they dont overlap. To speed up the process I also used a binary search tree that keeps track of the minimum f and h cost node when adding/removing nodes, since you only remove the smallest node its quite easy and makes the GetLowestFCostNode() have a time complexity of O(1)! (at the cost of the open_list.Add() being slower)
Hey @CodeMonkey, thanks for this gr8 tutorial !
Have a question - where the PNode a & PNode b came from in the CalculateDistanceCost()?
They are the same as PathNode, that's just the different name that I used while building the prototype before recording the video
@@CodeMonkeyUnity Another q - how did you added the colours and the costs to the squares after pressing the space button? Is there a tutorial i can look in to?
@@tzvikarediano965 I basically made a script that took a snapshot of the algorithm at every step of the way, I did that just to show it in the video so I'm not sure if that code is included in the project files.
If I have multiple agents exploring the grid, won't they interfere with each other as the pathfinding object writes to the grid? Should each agent have their own grid, because then I need to synchronise the walkable areas
Great Tutorial! Quick question is there a downside to using a 2d array such as i did, or is the grid implementation just for readability
It's easier to read the code with a 2D array but sure you can just use a 1D array and use basic math to calculate a X,Y into a single Index