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!
@@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
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
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
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
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.
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.
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.
@@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
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...
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
@@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*
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.
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).
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.
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.
Another great video, thanks. I'd be very interested in the optimisation however as I'm hoping to use this for a lot of game objects and still struggling to understand Dots! So sticking to the normal unity game objects for now.
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.
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.
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!)
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 ;)
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?
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).
I dont know if is to ask too much, but if its possible, try make grid playlist organized by date published. It automac, and keep order. some code depending from the previous video, and sometimes its not easy o track =)
The issue is this "series" wasn't planned ahead of time, I just started building a grid and then built more and more things on top of it. Some videos, like this Pathfinding or the House Building System, are not direct-sequels to a specific video but rather different spin-offs that use the same core. Even on things that are direct sequels, like the Grid Generics video, since it wasn't planned ahead of time it still has a bit of code written of screen. If you want a complete step by step guide I actually remade this from scratch step by step in my TBS course ruclips.net/video/QDr_pjzedv0/видео.html
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.
I really enjoyed seeing the pathfinding algorithm work. When it came to debugging at the end, watching the algorithm working on your video was very satisfying. I got my own green line to show up correctly (with some adjustments for worldposition to work with my tilemaps), but you chose not to show how you adapted the HeatMapVisual to show the three values gCost, fCost, and hCost. I guess it isn't important to making the pathfinding work, but it looked so good. Did you create three different debug arrays and populate them separately, or did you somehow find an easy way to format different parts of the ToString() override, maybe using ToString().PadLeft(); But then I couldn't figure out how you achieved different font sizes if you just used the ToString() override.
How did you manage this? I'm trying to make a small pixel game, with the MainCamera zoomed in and a custom tilemap for visuals. Do you know how to adapt the code to make the grid fit alongside?
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
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.
it would be nice to also allow go diagonal only if there it's not around a corner(s). Like you can go NW only if both N and W are walkable. Or at least one of them (cant go through diagonal 'wall').
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)
@@Jhinez 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.
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 may just be too tired but I got this algorithm implemented into my game and it works perfectly but only once. any subsequent generations return null. The first generation is a full valid pathway. I am going crazy over here. EDIT: I got it. I just had to set the g and h and current node values back to the default on the affected nodes. I just did a simple foreach loop on the pathway nodes before returning it.
Hi Codemonkey, as always, you're great. Just wondering whats the alogrithm concept behind the visual like in 20:07 ? Did you put the code together with the real algorithm or creating another separate pathfinding process ?
Hey! This looks really interesting! I really like to try it out. But how does it work on mobile? Are there any performance issues with little maps? Keep up the amazing work! 👍
Depends on how complex your game is. The code in the video is a great starting point, if you have more demanding needs you can greatly improve performance in many ways, I talk about it at the end of the video.
love the videos codemonkey. In the calculate distance cost function, I get the x & y values on the pathnodes not being accessible. I noted in your code they're private but to get it to work I had to change them to public. Will this be an issue or is it a change you made off screen?
If you make them public you are enabling read/write access from everywhere else in your code. If you accidentally modify the values you could end up with some very nasty bugs ruclips.net/video/pD27YuJG3L8/видео.html
21:55 - much more cleaner way (i was using x and z for grid x and y) using System.Linq; List VectorPath = path.ConvertAll((path) => new Vector3(path.x * grid.CellSize + grid.Origin.x, grid.Origin.y, path.y * grid.CellSize + grid.Origin.z));
Great Video! I downloaded the stuff off your website and was looking to see how/where you made the character have the complicated model and how you made it move (arms and legs moving)? I was trying to implement this is another game and would like to see where this functionality is implemented. Thanks!
@@CodeMonkeyUnity Excellent! There isn't any toturial on RUclips that explain to make a game like Cadence of Hyrule or Crypt of the Necrodancer. We can get only generic grid movement or make a grid. Nothing passing from it. You will be the first!
@@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.
Thanks for this suite of tutorials- really informative. Would you happen to have any pointers for adapting this grid & pathfinding system to an isometric view? I've been going in circles trying to figure it out. I assume once the grid itself is set up then the pathfinding should be the same, but getting the grid to fit an iso view is stumping me.
The simplest way would be to simply to use a 3D camera and rotate it. That way visually it would look isometric but it would still follow along the axis. Doing it perfect isometric is possible but does require quite a bit of math.
So I've been playing around with this and have one question: How would you do terrain that had different movement costs? For example, you have 10 for horizontal movement and 14 for diagonal, but what if you had a "swamp" tile that you wanted double movement cost just threw those squares? I played around and it's easy enough to move the terrain costs to the PathNode, but the Pathfinding Class' "FindPath" method uses the constant when figuring out distance between the Start and End Node by just calculating how many grid spaces the target is away. I'm not actually sure that matters since it's possible to have an "unwalkable" tiles in between the Start and End Nodes which will be ignored by that initial calculation, so maybe it's just a matter of the "Neighbor" calculation later in the method has the increased cost and that's good enough. Is it just a matter of attaching costs to the PostNode and pulling from there during the Find Path "Neighbor" calculation?
Yup, you add a int penaltyCost in the PathNode then you add that when calculating the node gCost When calculating the heuristic you can likely ignore the penalty and just do the same, it wont be perfectly sorted but probably not enough to cause issues
Hi! I have been watching many videos on different methods of pathfinding (A*, Flowfield, Navmesh) but I'm not sure which is the best. It seems like Navmesh is the easiest but not a lot of people are using it. Does anyone have a ranking of which is best based on the following components: Efficiency (Performance), Cleanliness (Organisation and performance) and Difficulty (How hard or easy it is to implement). I really appreciate it if anyone could help!
Depends on how you set up your character controller. Force is meant to be added constantly over time, think like pushing a car going faster and faster. Impulse just adds the velocity instantly, kind of like a spring
@@CodeMonkeyUnity I agree however for simple character movement (with added mass too) I think would be a simple fix for those that still can't get force to work. :) There are better options out there though I agree
openList should be implemented as a binary tree to get best performance out of this! also if you intend to reset the grid every time, just use the closed list and it works pretty much~
only if it's a self balancing tree like a red black or AVL tree- a vanilla unbalanced binary tree has a worst case search of linear time. a min heap sorted on fscore would be better
I ended up trying to use a SortedSet which is apparently a self sorting binary tree implementation and I use the fCost as my comparison to build out the tree, the problem is that fCost is not unique and so when I go to remove items it can't simply traverse the tree to find my object to remove because the nodes are set up to fCost. Any pointers on how to set up the binary tree to work well for finding lowest fCost and then being able to remove the node? Do I need 2 structures? Like a Binary tree and some sort of dictionary of items that hold a reference and can remove them?
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
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?
Just a comment. You changed your grid class from the videos where you developed it. It now uses generics. Could you do an in between video for those following along to show how you got from there to here?
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)
For people doing this in 2023, do the grid video, then do this video, but you'll have to suffer for a bit with errors and not be able to test. Eventually he shows the code required to test. I can't remember if the generics video was needed, he updates some of the code in that one as well, but I think he eventually shows it here as well. It's very hard to follow. Thank god for chatGPT. Edit - Actually I ran into more issues. Probably should just download the files through the website or move along to another tutorial.
Uh? There's nothing here that depends on a specific package or Unity version. I use this exact same code nowadays, everything here can be done in 2023. It sounds like you're looking for a guided step by step course rather than video tutorials, if so I build this exact system step by step in my TBS course unitycodemonkey.com/courses.php?c=turnbasedstrategy
@@CodeMonkeyUnity Ya, let me clarify, the video is awful no matter the year. I mentioned 2023 just because that's the year I attempted this, and it was a disaster. You couldn't pay me to follow your tutorials. And I'll break it down to give specifics. 1. Even after watching this full video, the grid full video, and part of generics, I'm not sure which other videos are required to actually have the code run. I still have to go back and figure out why multiple methods referenced don't exist. Go ahead and do the grid video and then come back to this, all the code between that video, and what you have, doesn't match and won't compile. 2. You seem to be ashamed to show your own code. You write the code off screen, you talk about methods while only showing part of them and then switching away so we never get to see them, you fast forward making it hard to follow, and when it comes time to test you fast forward so much I have to use frame by frame buttons just to see what's going on. I don't understand why the testing code is so shameful that it can't be shown. 3. On another video, I think it was generics, someone else pointed out that following these is a nightmare and you just blew them off. Which pretty much means you're stubborn and nothing will change so I have no hope for further videos. The comment section is basically trying to patch broken code and they are met with a wall. And then to top it off, you say, actually this code runs like trash so you actually need another video to fix it, but you put it up to a vote so I don't even know if that video exists. So now we need like 5 videos to end up with one algorithm to test, and who knows if that 5th video even exists. It's madness. I will use chatGPT to sort out this madness personally. I had to download the project files just to finish this because if you just follow along with the videos it ain't happening. And hey, maybe in video 6 you mentioned that the project files are required, idk. I also don't understand your comment about step by step. I mean ya, if you're saying hey this method is needed I'd like to see the method. What I wanted was a tutorial on a pathing system that I'd then apply. After downloading the files I finally got that, so many hours later, I finally succeeded. And ya I'll need to update the code to meet my needs but that's expected. What wasn't expected was this madness.
I'm not sure what you mean, the Grid uses generics, you can name that type whatever you want and have whatever data you want in it. The PathNode class simply has the structure that the algorithm needs.
Great tutorial. The only annoying thing is that i have to watch 4 videos because the are to much external reference in order to understand 1 single video.
@@CodeMonkeyUnity Totally true. It's just that i wanted review AStart Pathfinding and i wasn't expecting so much information connected in one video. Actually i learned a lot from all the video! Thanks a lot
I'm not sure it makes sense to have the pathfinding algorithm instantiate a grid inside of it. I feel like using dependency injection would result in more understandable and modular code. I also think it would make more sense to have showdebug passed in as a variable.
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
A* Pathfinding Many of the Pathfinding tutorials were cut, especially at 15.40 minutes, there immediately was a visual of Pathfinding and I don't understand how to write the manual, even though I've learned headmaps with generic grids
Is there any way where we can tweak A* search by prioritizing the longest possible X and Y movements? I'm working on a tank enemy that only moves parallel to the X and Y axis and while modifying findneighbours was pretty easy (just getting rid of top/bottom right/left) The tank currently finds the shortest path by going up-right-up-right-up-right where I want it to go up------right-------. Would changing it so that for a current node, the neighbor node going in the same direction as the previous node has a higher score be a good idea?
Hello Sir, I have a question. You use Grid here to create map with pathfinding, but what if I want to use Grid to build a map, do I just new another Grid map?
its just to reset the values when you start a new path. the pathing works by comparing costs so if some outlieing nodes still had small costs from a previous search it would think those nodes were the best match. so instead when you search a new path it makes them all bad spots then the algorithm goes through them 1 by one calculating their correct value.
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
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 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.
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.
Hi there, great tutorial series, however I'm having problems with the Mouse functions, wherever I click, Input.Mouseposition z-coordinate is always 0, so GetMouseWorldPosition always returns the camera position. Can you give me a hint how to fix that? Is there anything specific I need to configure in the main camera? Thanks.
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
![Kodak Black - Catch Fire [Official Music Video]](http://i.ytimg.com/vi/A4ch-olIuZo/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!
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
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...
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.
unity: I will give 3d pathfinding
devs: pathfinding for 2d too, right?
unity:
devs: pathfinding for 2d too, right?
truth
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
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
Thank you for the very clear explanation of how this works. It was dark magic to me like 25 mins ago.
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
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.
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
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.
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 :)
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...
Great Tutorial, i understand how a* pathfinding works now. i hope there are videos about optimizing this. thanks
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
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
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!
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
Thanks alot for this tutorial Code Monkey. You are a life saver for my project!
I love your content. Keep up the good work
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.
Yes I would really want to see a video on optimizing the algo..plz
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.
Another great video, thanks. I'd be very interested in the optimisation however as I'm hoping to use this for a lot of game objects and still struggling to understand Dots! So sticking to the normal unity game objects for now.
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.
The tutorial is very clear and helpful
I'm glad you found it helpful, thanks!
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
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!)
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 ;)
Thank you for this, really helps :)
Literly just came to doing that in my 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.
nice vid, thanks and gogogo for the optimization one :)
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?
Very nice tutorial, well explained, even though I had to pause the video many times haha
Thanks for your tutorial.
Thanks!
Thanks for the Super Thanks!
Wow this video is gold
I'm glad you liked it! Thanks!
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?
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.
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
I dont know if is to ask too much, but if its possible, try make grid playlist organized by date published. It automac, and keep order. some code depending from the previous video, and sometimes its not easy o track =)
The issue is this "series" wasn't planned ahead of time, I just started building a grid and then built more and more things on top of it.
Some videos, like this Pathfinding or the House Building System, are not direct-sequels to a specific video but rather different spin-offs that use the same core.
Even on things that are direct sequels, like the Grid Generics video, since it wasn't planned ahead of time it still has a bit of code written of screen.
If you want a complete step by step guide I actually remade this from scratch step by step in my TBS course ruclips.net/video/QDr_pjzedv0/видео.html
@@CodeMonkeyUnity Great chance to study. I already had this course, but I didnt made (yet) Lol Thanks for your work in channel =)
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!
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
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.
I really enjoyed seeing the pathfinding algorithm work. When it came to debugging at the end, watching the algorithm working on your video was very satisfying. I got my own green line to show up correctly (with some adjustments for worldposition to work with my tilemaps), but you chose not to show how you adapted the HeatMapVisual to show the three values gCost, fCost, and hCost. I guess it isn't important to making the pathfinding work, but it looked so good.
Did you create three different debug arrays and populate them separately, or did you somehow find an easy way to format different parts of the ToString() override, maybe using ToString().PadLeft(); But then I couldn't figure out how you achieved different font sizes if you just used the ToString() override.
How did you manage this? I'm trying to make a small pixel game, with the MainCamera zoomed in and a custom tilemap for visuals. Do you know how to adapt the code to make the grid fit alongside?
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
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?
it would be nice to also allow go diagonal only if there it's not around a corner(s). Like you can go NW only if both N and W are walkable. Or at least one of them (cant go through diagonal 'wall').
Finally. I'm too lazy to read papers.
Awesome video. Thank you! Have you started working with this algorithm to improve optimization?
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
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!
@@Jhinez 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.
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 may just be too tired but I got this algorithm implemented into my game and it works perfectly but only once. any subsequent generations return null. The first generation is a full valid pathway. I am going crazy over here.
EDIT: I got it. I just had to set the g and h and current node values back to the default on the affected nodes. I just did a simple foreach loop on the pathway nodes before returning it.
Hi Codemonkey, as always, you're great.
Just wondering whats the alogrithm concept behind the visual like in 20:07 ?
Did you put the code together with the real algorithm or creating another separate pathfinding process ?
It just records every step in the algorithm and then plays it back one step every second.
Hey! This looks really interesting! I really like to try it out. But how does it work on mobile? Are there any performance issues with little maps? Keep up the amazing work! 👍
Depends on how complex your game is. The code in the video is a great starting point, if you have more demanding needs you can greatly improve performance in many ways, I talk about it at the end of the video.
@@CodeMonkeyUnity Okay thnx! I'll try it out!
Thank you for all your work. You're amazing
love the videos codemonkey. In the calculate distance cost function, I get the x & y values on the pathnodes not being accessible. I noted in your code they're private but to get it to work I had to change them to public. Will this be an issue or is it a change you made off screen?
If you make them public you are enabling read/write access from everywhere else in your code. If you accidentally modify the values you could end up with some very nasty bugs ruclips.net/video/pD27YuJG3L8/видео.html
So the question remains. I've checked many times but still cannot find why they look accessible in your code while I have red underlines.
21:55 - much more cleaner way (i was using x and z for grid x and y)
using System.Linq;
List VectorPath = path.ConvertAll((path) => new Vector3(path.x * grid.CellSize + grid.Origin.x, grid.Origin.y, path.y * grid.CellSize + grid.Origin.z));
Great Video! I downloaded the stuff off your website and was looking to see how/where you made the character have the complicated model and how you made it move (arms and legs moving)? I was trying to implement this is another game and would like to see where this functionality is implemented. Thanks!
It's my custom animation system based on dynamically modifying meshes, I covered it here ruclips.net/video/11c9rWRotJ8/видео.html
Awesome tutorial! I'm making a clone of binding of isaac and this worked like a charm! Thank you codemonkey!
Nice! Best of luck with your game!
Great video! Here's a sugestion: Do a series of videos doing a game like Cadence of Hyrule movement and combat, etc.
Yup a Rythm game is definitely something I'd like to look into
@@CodeMonkeyUnity Excellent! There isn't any toturial on RUclips that explain to make a game like Cadence of Hyrule or Crypt of the Necrodancer. We can get only generic grid movement or make a grid. Nothing passing from it. You will be the first!
This video is really good, have a question though how would you save/load the grid?
You could use JSON and save an object with all the data ruclips.net/video/6uMFEM-napE/видео.html
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.
Thanks for this suite of tutorials- really informative. Would you happen to have any pointers for adapting this grid & pathfinding system to an isometric view? I've been going in circles trying to figure it out. I assume once the grid itself is set up then the pathfinding should be the same, but getting the grid to fit an iso view is stumping me.
The simplest way would be to simply to use a 3D camera and rotate it. That way visually it would look isometric but it would still follow along the axis.
Doing it perfect isometric is possible but does require quite a bit of math.
I did this a long time ago in a galaxy far away in XNA, interesting you avoided a Recursive method
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
So I've been playing around with this and have one question: How would you do terrain that had different movement costs? For example, you have 10 for horizontal movement and 14 for diagonal, but what if you had a "swamp" tile that you wanted double movement cost just threw those squares?
I played around and it's easy enough to move the terrain costs to the PathNode, but the Pathfinding Class' "FindPath" method uses the constant when figuring out distance between the Start and End Node by just calculating how many grid spaces the target is away. I'm not actually sure that matters since it's possible to have an "unwalkable" tiles in between the Start and End Nodes which will be ignored by that initial calculation, so maybe it's just a matter of the "Neighbor" calculation later in the method has the increased cost and that's good enough.
Is it just a matter of attaching costs to the PostNode and pulling from there during the Find Path "Neighbor" calculation?
Yup, you add a int penaltyCost in the PathNode then you add that when calculating the node gCost
When calculating the heuristic you can likely ignore the penalty and just do the same, it wont be perfectly sorted but probably not enough to cause issues
Hi! I have been watching many videos on different methods of pathfinding (A*, Flowfield, Navmesh) but I'm not sure which is the best. It seems like Navmesh is the easiest but not a lot of people are using it. Does anyone have a ranking of which is best based on the following components: Efficiency (Performance), Cleanliness (Organisation and performance) and Difficulty (How hard or easy it is to implement). I really appreciate it if anyone could help!
A* is the most versatile as you can tailor it to your game's style
For those struggling with AI movement still(I know this is an old video) try changing your Fmode from Force to impulse
Depends on how you set up your character controller. Force is meant to be added constantly over time, think like pushing a car going faster and faster.
Impulse just adds the velocity instantly, kind of like a spring
@@CodeMonkeyUnity I agree however for simple character movement (with added mass too) I think would be a simple fix for those that still can't get force to work. :) There are better options out there though I agree
openList should be implemented as a binary tree to get best performance out of this!
also if you intend to reset the grid every time, just use the closed list and it works pretty much~
Yup a binary tree is exactly what I use in my implementation working on Battle Royale Tycoon. It speeds up significantly.
only if it's a self balancing tree like a red black or AVL tree- a vanilla unbalanced binary tree has a worst case search of linear time. a min heap sorted on fscore would be better
@@CodeMonkeyUnity Would I be building this tree using the fCost as the node comparison?
I ended up trying to use a SortedSet which is apparently a self sorting binary tree implementation and I use the fCost as my comparison to build out the tree, the problem is that fCost is not unique and so when I go to remove items it can't simply traverse the tree to find my object to remove because the nodes are set up to fCost. Any pointers on how to set up the binary tree to work well for finding lowest fCost and then being able to remove the node? Do I need 2 structures? Like a Binary tree and some sort of dictionary of items that hold a reference and can remove them?
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
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.
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
Just a comment. You changed your grid class from the videos where you developed it. It now uses generics. Could you do an in between video for those following along to show how you got from there to here?
All the videos related to the Grid System are on this playlist ruclips.net/p/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722
@@CodeMonkeyUnity Ahh thanks, Somehow I missed the generics one.
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)
For people doing this in 2023, do the grid video, then do this video, but you'll have to suffer for a bit with errors and not be able to test. Eventually he shows the code required to test. I can't remember if the generics video was needed, he updates some of the code in that one as well, but I think he eventually shows it here as well. It's very hard to follow. Thank god for chatGPT. Edit - Actually I ran into more issues. Probably should just download the files through the website or move along to another tutorial.
Uh? There's nothing here that depends on a specific package or Unity version. I use this exact same code nowadays, everything here can be done in 2023.
It sounds like you're looking for a guided step by step course rather than video tutorials, if so I build this exact system step by step in my TBS course unitycodemonkey.com/courses.php?c=turnbasedstrategy
@@CodeMonkeyUnity Ya, let me clarify, the video is awful no matter the year. I mentioned 2023 just because that's the year I attempted this, and it was a disaster. You couldn't pay me to follow your tutorials. And I'll break it down to give specifics. 1. Even after watching this full video, the grid full video, and part of generics, I'm not sure which other videos are required to actually have the code run. I still have to go back and figure out why multiple methods referenced don't exist. Go ahead and do the grid video and then come back to this, all the code between that video, and what you have, doesn't match and won't compile. 2. You seem to be ashamed to show your own code. You write the code off screen, you talk about methods while only showing part of them and then switching away so we never get to see them, you fast forward making it hard to follow, and when it comes time to test you fast forward so much I have to use frame by frame buttons just to see what's going on. I don't understand why the testing code is so shameful that it can't be shown. 3. On another video, I think it was generics, someone else pointed out that following these is a nightmare and you just blew them off. Which pretty much means you're stubborn and nothing will change so I have no hope for further videos. The comment section is basically trying to patch broken code and they are met with a wall. And then to top it off, you say, actually this code runs like trash so you actually need another video to fix it, but you put it up to a vote so I don't even know if that video exists. So now we need like 5 videos to end up with one algorithm to test, and who knows if that 5th video even exists. It's madness. I will use chatGPT to sort out this madness personally. I had to download the project files just to finish this because if you just follow along with the videos it ain't happening. And hey, maybe in video 6 you mentioned that the project files are required, idk. I also don't understand your comment about step by step. I mean ya, if you're saying hey this method is needed I'd like to see the method. What I wanted was a tutorial on a pathing system that I'd then apply. After downloading the files I finally got that, so many hours later, I finally succeeded. And ya I'll need to update the code to meet my needs but that's expected. What wasn't expected was this madness.
Hi Code Monkey! Thanks for the great tutorial. Is there a way to implement Pathfinding with Grid instead of the specific Grid?
I'm not sure what you mean, the Grid uses generics, you can name that type whatever you want and have whatever data you want in it. The PathNode class simply has the structure that the algorithm needs.
@@CodeMonkeyUnity i ment that i had different kind of grid in my game but only a pathfinding class. I think i shloud use some covariant interface
is there any way to implement for different tiles to have different move speed?
Great tutorial. The only annoying thing is that i have to watch 4 videos because the are to much external reference in order to understand 1 single video.
That's just how game development works, you build systems upon systems.
@@CodeMonkeyUnity Totally true. It's just that i wanted review AStart Pathfinding and i wasn't expecting so much information connected in one video. Actually i learned a lot from all the video! Thanks a lot
I'm not sure it makes sense to have the pathfinding algorithm instantiate a grid inside of it. I feel like using dependency injection would result in more understandable and modular code. I also think it would make more sense to have showdebug passed in as a variable.
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!
Any Chance that this video would be updated for a Hex tile Pathfinding?
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
A* Pathfinding Many of the Pathfinding tutorials were cut, especially at 15.40 minutes, there immediately was a visual of Pathfinding and I don't understand how to write the manual, even though I've learned headmaps with generic grids
Is there any way where we can tweak A* search by prioritizing the longest possible X and Y movements? I'm working on a tank enemy that only moves parallel to the X and Y axis and while modifying findneighbours was pretty easy (just getting rid of top/bottom right/left) The tank currently finds the shortest path by going up-right-up-right-up-right where I want it to go up------right-------.
Would changing it so that for a current node, the neighbor node going in the same direction as the previous node has a higher score be a good idea?
Hello Sir, I have a question. You use Grid here to create map with pathfinding, but what if I want to use Grid to build a map, do I just new another Grid map?
Are you trying to make a Tilemap? I did something like that here unitycodemonkey.com/video.php?v=gD5EQyt7VPk
Hi. So, I couldn't figure out why you initialized the PathNodes to int MaxValue. Could you tell me why?
its just to reset the values when you start a new path. the pathing works by comparing costs so if some outlieing nodes still had small costs from a previous search it would think those nodes were the best match. so instead when you search a new path it makes them all bad spots then the algorithm goes through them 1 by one calculating their correct value.
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 🤝🏻
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 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
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.
Hi there, great tutorial series, however I'm having problems with the Mouse functions, wherever I click, Input.Mouseposition z-coordinate is always 0, so GetMouseWorldPosition always returns the camera position. Can you give me a hint how to fix that? Is there anything specific I need to configure in the main camera? Thanks.
The method is different depending on if its a 2D or 3D camera ruclips.net/video/0jTPKz3ga4w/видео.html
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
i would like a video about binary tree