A* Pathfinding in Unity
ฝัง
- เผยแพร่เมื่อ 17 มิ.ย. 2024
- ✅ Get the Project files and Utilities at unitycodemonkey.com/video.php...
🌍 Get my C# Complete Course! cmonkey.co/csharpcourse
🎮 Play my Steam game! cmonkey.co/dinkyguardians
❤️ Watch my FREE Complete Courses • Learn to make Games wi...
🌍 Get my Complete Courses! ✅ unitycodemonkey.com/courses
Let's implement A* Pathfinding in Unity and visually see the inner workings of the Algorithm in action.
Grid System in Unity
• Grid System in Unity (...
Powerful Generics Added! Grid System in Unity
• Powerful Generics Adde...
Cool Heatmap in Unity
• Cool Heatmap in Unity
If you have any questions post them in the comments and I'll do my best to answer them.
🔔 Subscribe for more Unity Tutorials / @codemonkeyunity
See you next time!
🤖 Join the Community Discord / discord
📦 Grab the game bundle at unitycodemonkey.com/gameBundl...
📝 Get the Code Monkey Utilities at unitycodemonkey.com/utils.php
#unitytutorial #unity3d #unity2d
--------------------------------------------------------------------
Hello and welcome, I am your Code Monkey and here you will learn everything about Game Development in Unity 2D using C#.
I've been developing games for several years with 7 published games on Steam and now I'm sharing my knowledge to help you on your own game development journey.
You can see my games at www.endlessloopstudios.com
--------------------------------------------------------------------
- Website: unitycodemonkey.com/
- Twitter: / unitycodemonkey
- Facebook: / unitycodemonkey
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!
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.
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
th-cam.com/video/mZfyt03LDH4/w-d-xo.html
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...
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
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 love your content. Keep up the good work
Thank you for the very clear explanation of how this works. It was dark magic to me like 25 mins ago.
Great Tutorial, i understand how a* pathfinding works now. i hope there are videos about optimizing this. thanks
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...
Yes, please do a video on the optimizations you talked about!
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.
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
unity: I will give 3d pathfinding
devs: pathfinding for 2d too, right?
unity:
devs: pathfinding for 2d too, right?
truth
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
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 :)
nice vid, thanks and gogogo for the optimization one :)
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.
Thanks alot for this tutorial Code Monkey. You are a life saver for my project!
Thank you for this, really helps :)
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 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
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
Thanks for your tutorial.
The tutorial is very clear and helpful
I'm glad you found it helpful, thanks!
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!
Very nice tutorial, well explained, even though I had to pause the video many times haha
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 ;)
Literly just came to doing that in my game.
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
Yes I would really want to see a video on optimizing the algo..plz
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 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.
Awesome video. Thank you! Have you started working with this algorithm to improve optimization?
Thanks!
Thanks for the Super Thanks!
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
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?
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!
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?
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?
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 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.
Wow this video is gold
I'm glad you liked it! Thanks!
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
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!
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
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!
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.
Changing the openList and closeList from a List to a Dictionary reduced the run time of the pathfinding algorithm in my game from 107 milliseconds down to 3. I think it's because the closed list gets really large and a list.contains search is O(n) but a dictionary.ContainsKey search is O(1).
For closed set you wanna use HashSet and for OpenSet use a Heap
How would you alter this for moving targets and/or realtime changing obstacles?
Run the Pathfinding more than once. If your characters move slowly then maybe every .5 seconds should do it. It all depends on how performant the algorithm is and how much performance you can spare.
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
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.
Thank you for all your work. You're amazing
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.
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?
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 th-cam.com/video/6uMFEM-napE/w-d-xo.html
HI @Code Monkey, your tutorial is very great! May I ask you? I am interest to make a* pathfinding movement, how if I want the enemy walk in your limit area randomly?
Instead of a single weight, make it based on the type of object that is requesting the path
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
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
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
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.
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
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 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.
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!
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?
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!)
Awesome video series! Thanks for everything! And a quick question. I'm getting an error that object reference of the pathNodes are not set to an instance of an object whenever I'm trying to call FindPath() outside of the Testing script. My understanding was that since Pathfinding is a singleton it can be called from anywhere. Any thoughts? Do I have to call Pathfinding's functions through the Testing script because that's where it get's instantiated? Have I misunderstood something regarding singletons? Thanks in advance!!
Maybe you are accessing the singleton before it is actually set? You first need to construct the object and set the singleton variable.
Unity decides the order that scripts are run, so one Awake() will run before another Awake()
You can modify it in the Script Execution Order window
@@CodeMonkeyUnity Thank you very much, I will give it a try. Great content and I'm exited to seeing more from you :)
//Testing.cs
void Awake() //changed from Start->Awake
{
pathfinding=new Pathfinding(10,10);
}
Hey, I downloaded the project zip and I modified the originPosition in the Pathfinding, but somehow the Character does not move around the scene. Is there something I can do to fix it?
Any Chance that this video would be updated for a Hex tile Pathfinding?
I wish I could type as fast as you :P
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
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
Finally. I'm too lazy to read papers.
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
Please do the optimization videos too
I'm trying to give my 2d agents a navigation method while also allowing letting the rigidbody be dynamic. I tried with navmesh plus but it requires that the rigidbody be dynamic. Would A* be the right way to go you think?
Sure you can calculate the path using custom A* just as you can calculate the path using NavMesh without using NavMeshAgent.
Then you have a list of path points and you can move your object in any way you want.
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)
Can you make a video about A* algorithm applied to an iso/staggered iso map?
@codeMonkey Hi, thank you very much for the tutorial, one question, how would we calculate Cost Distance in 3D space grid?
You mean you have like multiple grids on top of one another? The distance would be the same, moving straight up has the same cost as moving straight left/right.
@@CodeMonkeyUnity Hi, thank you for your answer. No, I've just added Z and created 3D grid instead of 2D, it finds path trough obstacles, works fine, but searching closest node on z is not always correct, I think the issue is at function CallculateDistanceCost. here maybe this will paint the picture :D How would you include z axis? int CalculateDistanceCost(Vector3Int _a, Vector3Int _b) {
int xDistance = Mathf.Abs(_a.x - _b.x);
int yDistance = Mathf.Abs(_a.y - _b.y);
int remaining = Mathf.Abs(xDistance - yDistance);
return MOVE_DIAGONAL_COST * Mathf.Min(xDistance, yDistance) + MOVE_STRAIGHT_COST * remaining;
}
Hello, first and foremost, thank you for your awesome, its very useful for my project but eventhough I followed step by step your tutorial on the grid, the generics and this one I can't manged to change the size of cellsize of the grid (eventhough I did mange to do it in the tutorial for the grid) and I want to know how and what parameter should be changed to adapt it to my game like my character my background...
I know I ask for a lot and I'm sorry ...
Anyway keep up the awesome work !
I'm not sure I understand, if you managed to change the Grid then you changed it, the Grid is what stores the size of each grid. What else do you want to change?
@@CodeMonkeyUnity In the tutorial about the grid I mangaged to change the cellsize wich is 32 pixel for my game, but now that I have the pathfinding script, the testing, pathnode etc I don't know how to change the size of each cell of the grid anymore.
I hope I'm understandable, I'm not a native speaker.
Nevermind for the grid, I managed to changed it by re rewatching the videos, thank you for your quick answer.
Have a nice day !
I'm looking to change the character and the background at the moment
Great video, it wa an awesome tutorial. In my game, i'm working in a 3D environment that expands based on player exlporation. So, i spawn a new tileset with quads representing the grid, then i make an Array of tiles based on the return of FindGameObjectsWithTag. With this Array i find neighbors of the tile where the player stand, and calculate the path. But it is very rigid code since i'm in prototype fase, and depends of an always growing array. After i saw your video, a question came to me. Could this path finding system work with near Grids? Maybe it is a crazy idea, but it would be very costly to the machine to instantiate a gigantic grid, since in the begining the game don't know where the player is heading. So, would be possible to with each tileset spawn, instantiate a new grid like 4x4 for exemple, that represents each position in the tileset that is walkable, and when trying to path find, iterate through each instantiated grid?
Yes for super massive worlds you should split your world into multiple grids rather than just one huge one.
However the code you're describing sounds heavy on GameObjects (FindGameObjectsWithTag is extremely slow), there's no reason for your grid to be physically represented in the world.
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 🤝🏻
As Always is Great, but didn't understand why you put variable Grid grid to the class PathNode. I think it's not necessary.
Any tips for having the pathfinding adjust to a wall being created that obstructs the current path the player is taking so that they reroute around it?
You need to recalculate the path whenever the map changes
Awesome tutorial. This runs very slowly on my 50x50 grid when the target node is far away, though. Would trying to optimize it make it more viable? Otherwise I'm gonna try to make the AI use an influence map when far away, and pathfinding while close.
The goal with this video is to teach you how the A* algorithm works but in order to make it performant it still requires tons more work.
The main bottleneck is searching the open list, so a huge upgrade would be to use a Binary Tree.
For simple non-real time use cases you can just add some small improvements like that search tree and it will possibly be fast enough.
However if you're trying to get pathfinding working on your game I would recommend you use a proper asset rather than trying to make it yourself th-cam.com/video/46qZgd-T-hk/w-d-xo.html
@@CodeMonkeyUnity My grid cells are individual objects, so rather than keeping a list I stored an isClosed bool on each one, and rather than searching for neighbors I had the Cells find and store their neighbors when the grid is initialized. Pretty much instant now! I plan to implement a binary heap for open list later on, but right now it seems performant enough to save that for later. Thanks for the response!
Hi, very intersting video. Still I have one question, what if I don't want diagonal move ? Only 4 possible movement (up, down, left, right). Just removing the diagonal neighbour would work ?
thanks.
You should also change the CalculateDistanceCost function to return (xDistance + yDistance) * MOVE_STRAIGHT_COST .
I also added a bool attribute to the pathfinding class to check or not the diagonal movement, in case you can switch between 4 and 8 posible directions
@@EpicJokinFail thanks, I didn't have much time to enter the code, so I've runned the algorithm on paper. The path will be mostly chosen by the code according to what comes first when looking for the Up/Down/Left/Right neighbours.
I did this a long time ago in a galaxy far away in XNA, interesting you avoided a Recursive method
what is the GetNode function, i cannot find where we created her!
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.
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?
How is the heuristic value calculated ?
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 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 =)
Hi I know the video is old but I hope someone can help me, I have a problem with the PathfindingVisual script when painting the walls. It only works if I drag the script when the scene is open, if for some reason I change the scene and go back to the one that makes the functionality stops working, the pathfinding and algorithm are fine but it stops painting the walls.
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?
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