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!
@@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
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.
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.
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
@@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
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
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.
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).
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...
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.
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.
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
@@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*
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 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.
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!)
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.
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.
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.
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?
@@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 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.
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.
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 th-cam.com/play/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722.html It's not the built-in Unity Grid, that one is means just for tilemap visuals.
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').
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!
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 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 th-cam.com/video/QDr_pjzedv0/w-d-xo.html
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
Umm can any tell me how to do the PNode in the parameter of CalculateDistanceCost()? Is it a version of PathNode which shows the x and y? if it is how to make that? Edit:- Wow so it was a delay in system and not PNode. here i got my butt whooped for two days cuz my notes said PNode. Sorry for doubting you.
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.
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 ;)
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
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?
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.
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
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.
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
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?
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.
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
I need some help. PathNode.x and PathNode.y are inaccessible due to its protection level. Im pretty sure puting public in the PathNode class supposed to work but it does not. Anyone facing the same problem and found a solution?
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));
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?
Hey I wanted use this script to my project but it is too slow. When enemies chasing player, unity have too many calculations with MOVING player so game crash. I DONT want to use ready internet scripts, i want use my own script created with this tutorial but its too slow. Can i optimize this script without taking too much time? pls help I've been dealing with this problem for a very long time and i dont want to watch more tutorials. I am using unity 2d so nav mesh will dont work.
Making pathfinding performant is a massive undertaking. If you really don't want to use an asset then you have a lot of work ahead of you unitycodemonkey.com/video.php?v=46qZgd-T-hk You need to use the profiler, get rid of garbage generation, maybe use structs instead of classes, maybe cache some values, maybe implement multithreading. There's not simple easy solution to solve that problem.
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.
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!
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)
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
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.
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
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 ?
@@CodeMonkeyUnity Excellent! There isn't any toturial on TH-cam 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!
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.
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.
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?
Code Monkey why do you make this so hard to follow? I downloaded the project files to see what Im doing wrong and its a completely different file names and looks like a complete project.
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 th-cam.com/video/pD27YuJG3L8/w-d-xo.html
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
@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?
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
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.
I got a problem. Both lines Z,X of grids right on the center are not accessible. Error while pointing it as target(to move units) and they are not marked as "unwalkable" while building. Hope your help. I'm new using Unity and learning about RTS.
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?
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
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?
unity: I will give 3d pathfinding
devs: pathfinding for 2d too, right?
unity:
devs: pathfinding for 2d too, right?
truth
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!
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
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 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
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...
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
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.
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 :)
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
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.
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.
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
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...
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.
Yes, please do a video on the optimizations you talked about!
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!
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
I love your content. Keep up the good work
Great Tutorial, i understand how a* pathfinding works now. i hope there are videos about optimizing this. thanks
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
Literly just came to doing that in my game.
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.
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.
Finally. I'm too lazy to read papers.
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!)
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.
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?
Thanks alot for this tutorial Code Monkey. You are a life saver for my project!
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.
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?
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 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!
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
Yes I would really want to see a video on optimizing the algo..plz
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.
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 th-cam.com/play/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722.html
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!
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!
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').
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
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.
nice vid, thanks and gogogo for the optimization one :)
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
is there any way to implement for different tiles to have different move speed?
The tutorial is very clear and helpful
I'm glad you found it helpful, thanks!
Thank you for this, really helps :)
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 th-cam.com/video/QDr_pjzedv0/w-d-xo.html
@@CodeMonkeyUnity Great chance to study. I already had this course, but I didnt made (yet) Lol Thanks for your work in channel =)
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
Umm can any tell me how to do the PNode in the parameter of CalculateDistanceCost()? Is it a version of PathNode which shows the x and y? if it is how to make that?
Edit:- Wow so it was a delay in system and not PNode. here i got my butt whooped for two days cuz my notes said PNode. Sorry for doubting you.
Yo I still don't get it, tf is a PNode?
nvm he changed it to PathNode later lmao
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.
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 ;)
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
Very nice tutorial, well explained, even though I had to pause the video many times haha
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?
As Always is Great, but didn't understand why you put variable Grid grid to the class PathNode. I think it's not necessary.
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
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
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
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.
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!
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
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?
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!
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!
I need some help. PathNode.x and PathNode.y are inaccessible due to its protection level. Im pretty sure puting public in the PathNode class supposed to work but it does not. Anyone facing the same problem and found a solution?
i would like a video about binary tree
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 th-cam.com/play/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722.html
@@CodeMonkeyUnity so the order is
1 4 2 3 5 6 7?
Wow this video is gold
I'm glad you liked it! Thanks!
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));
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 th-cam.com/play/PLzDRvYVwl53uhO8yhqxcyjDImRjO9W722.html
@@CodeMonkeyUnity Ahh thanks, Somehow I missed the generics one.
How would you calculate the distance between two nodes in 3 dimensional space?
Hi, did you figured this out maybe?
Could this work in a 2d platformer? I know I will have to consider gravity, do you have any directions on how to handle this?
Hey
I wanted use this script to my project but it is too slow. When enemies chasing player, unity have too many calculations with MOVING player so game crash. I DONT want to use ready internet scripts, i want use my own script created with this tutorial but its too slow. Can i optimize this script without taking too much time? pls help I've been dealing with this problem for a very long time and i dont want to watch more tutorials. I am using unity 2d so nav mesh will dont work.
Making pathfinding performant is a massive undertaking. If you really don't want to use an asset then you have a lot of work ahead of you unitycodemonkey.com/video.php?v=46qZgd-T-hk
You need to use the profiler, get rid of garbage generation, maybe use structs instead of classes, maybe cache some values, maybe implement multithreading.
There's not simple easy solution to solve that problem.
Awesome video. Thank you! Have you started working with this algorithm to improve optimization?
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.
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 th-cam.com/video/11c9rWRotJ8/w-d-xo.html
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
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
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.
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
in making pathnode class it is not allowing me to make a variable of Grid grid;, help please , in problemmmmmm
What do you mean by not allowing you? Maybe you don't have the Grid class with generics in your project unitycodemonkey.com/video.php?v=8jrAWtI8RXg
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.
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
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 TH-cam 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!
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 th-cam.com/video/0jTPKz3ga4w/w-d-xo.html
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.
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?
Code Monkey why do you make this so hard to follow? I downloaded the project files to see what Im doing wrong and its a completely different file names and looks like a complete project.
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 th-cam.com/video/pD27YuJG3L8/w-d-xo.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.
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 🤝🏻
@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.
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
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.
I got a problem. Both lines Z,X of grids right on the center are not accessible. Error while pointing it as target(to move units) and they are not marked as "unwalkable" while building. Hope your help. I'm new using Unity and learning about RTS.
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?
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
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
can you help? im stuck, and I get this error message:CS0308 C# The non-generic type 'Grid' cannot be used with type arguments
Sounds like you're not using the same Grid class used in the video, it was made to work with Generics here th-cam.com/video/8jrAWtI8RXg/w-d-xo.html