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!

@sword013

4 жыл бұрын

Was waiting for this concept ! Thank you !

@Onyhh

4 жыл бұрын

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.

@gm2529

4 жыл бұрын

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?

@CodeMonkeyUnity

4 жыл бұрын

@@gm2529 When checking for neighbours, don't get the diagonals

@maximilianwinter582

3 жыл бұрын

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!

@CodeMonkeyUnity

4 жыл бұрын

Thanks! Glad you found the video helpful!

unity: I will give 3d pathfinding devs: pathfinding for 2d too, right? unity: devs: pathfinding for 2d too, right?

@Ziron2008

8 күн бұрын

truth

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.

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...

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.

@benowen8321

4 жыл бұрын

did you ever find any good resources on pathfinding optimisation?

@liamr6761

4 жыл бұрын

@@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.

@darkotomic943

3 жыл бұрын

@@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.

@rollingsausageltd

2 жыл бұрын

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 kzread.info/dash/bejne/n46a29ZpY6-qeJc.html

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.

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

Nice job with the vid, glad to see you covering A* pathfinding.

@CodeMonkeyUnity

4 жыл бұрын

Thanks! Yeah this one has been a long time coming, now got to get to work on the Unity DOTS version.

Yes, please do a video on the optimizations you talked about!

Thank you for the very clear explanation of how this works. It was dark magic to me like 25 mins ago.

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.

@bipedpotato

2 жыл бұрын

YAY now spam clicking doesnt crash my game!

@user-dl5xl3xj8h

Жыл бұрын

Thank you !!

@andrewhopkins3397

11 ай бұрын

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.

Spent three hours translating this task into 3D spaces, but in the end everything works!

@crump05

3 жыл бұрын

nothing feels better than your code finally working

@Wayloz

3 жыл бұрын

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...

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

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.

@SkyZocktOfficial

3 жыл бұрын

But you found a path

@Yewtewba

5 ай бұрын

People when they say they're 5 minutes away be like...

@Hakermaker

5 ай бұрын

Thx for info, i'll see how i can use your mistake

I literally white listed your channel on my adblock. In impressed with your work

@CodeMonkeyUnity

4 жыл бұрын

Thanks! Glad you like it!

@kalucky0

4 жыл бұрын

How can I do that?

@hole1274

3 жыл бұрын

@@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 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.

Thanks alot for this tutorial Code Monkey. You are a life saver for my project!

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.

Thank you, due to you today I've implemented my first A*

@CodeMonkeyUnity

3 жыл бұрын

That's awesome! Keep it up!

@Agent009neutral

3 жыл бұрын

@@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*

@Agent009neutral

3 жыл бұрын

@@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

nice vid, thanks and gogogo for the optimization one :)

Thank you for this, really helps :)

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.

@CodeMonkeyUnity

4 жыл бұрын

Thanks! I'm glad you found the video useful!

@maxschafer5470

Жыл бұрын

Curious how your Javascript implementation went. I am attempting this in Three.js for a school project.

@WingMaster562

Жыл бұрын

@@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

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.

@CodeMonkeyUnity

Жыл бұрын

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

@DoggletPug

Жыл бұрын

@@CodeMonkeyUnity Thanks Man!

Cool cant wait for DOTS version

@MalikenGD

4 жыл бұрын

SAME!

@danieldahl4585

4 жыл бұрын

Same

@rezaakmal9608

4 жыл бұрын

what is DOTS Version means? sorry i'm a newborn :D

@MalikenGD

4 жыл бұрын

@@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

@rezaakmal9608

4 жыл бұрын

@@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 :)

Thanks for your tutorial.

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 ;)

Very nice tutorial, well explained, even though I had to pause the video many times haha

The tutorial is very clear and helpful

@CodeMonkeyUnity

Жыл бұрын

I'm glad you found it helpful, thanks!

Literly just came to doing that in my game.

Yes I would really want to see a video on optimizing the algo..plz

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?

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.

@CodeMonkeyUnity

4 жыл бұрын

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.

Awesome video. Thank you! Have you started working with this algorithm to improve optimization?

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 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').

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).

@killereks

Жыл бұрын

For closed set you wanna use HashSet and for OpenSet use a Heap

Great Video! I downloaded the stuff off your website and was looking to see how/where you made the character have the complicated model and how you made it move (arms and legs moving)? I was trying to implement this is another game and would like to see where this functionality is implemented. Thanks!

@CodeMonkeyUnity

3 жыл бұрын

It's my custom animation system based on dynamically modifying meshes, I covered it here kzread.info/dash/bejne/Y2WXm9SQgtLaeps.html

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?

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?

@CodeMonkeyUnity

4 жыл бұрын

Yup, you add a int penaltyCost in the PathNode then you add that when calculating the node gCost When calculating the heuristic you can likely ignore the penalty and just do the same, it wont be perfectly sorted but probably not enough to cause issues

Hi 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

3 жыл бұрын

It just records every step in the algorithm and then plays it back one step every second.

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.

@CodeMonkeyUnity

Жыл бұрын

The grid size is easily changeable, you can use whatever unit size makes sense for your assets

How would you alter this for moving targets and/or realtime changing obstacles?

@CodeMonkeyUnity

4 жыл бұрын

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.

Great video! Here's a sugestion: Do a series of videos doing a game like Cadence of Hyrule movement and combat, etc.

@CodeMonkeyUnity

4 жыл бұрын

Yup a Rythm game is definitely something I'd like to look into

@tallesmaziero

4 жыл бұрын

@@CodeMonkeyUnity Excellent! There isn't any toturial on KZread 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!

Awesome videos! thank you so much! did you cover the soldier creation? i would like to know how to start it. Thanks again!

@CodeMonkeyUnity

5 ай бұрын

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

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 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.

@CaptinUnderpants2

Жыл бұрын

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?

Hey thanks for the tutorial! But Im missing one thing @ 10:50 Where did you wrote the function "GetNode" ?

@CodeMonkeyUnity

4 жыл бұрын

It does grid.GetGridObject(x, y); Visible at 13:30

@Jhinez

4 жыл бұрын

@@CodeMonkeyUnity oh wow... im blind sorry haha. tyvm!

@TheMrSnipey

3 жыл бұрын

@@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.

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

@CodeMonkeyUnity

Жыл бұрын

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

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?

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! 👍

@CodeMonkeyUnity

4 жыл бұрын

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.

@KiwiGalaxyDev

4 жыл бұрын

@@CodeMonkeyUnity Okay thnx! I'll try it out!

This video is really good, have a question though how would you save/load the grid?

@CodeMonkeyUnity

3 жыл бұрын

You could use JSON and save an object with all the data kzread.info/dash/bejne/aKmBqKeGXdHHoKg.html

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?

Hey @CodeMonkey, thanks for this gr8 tutorial ! Have a question - where the PNode a & PNode b came from in the CalculateDistanceCost()?

@CodeMonkeyUnity

Жыл бұрын

They are the same as PathNode, that's just the different name that I used while building the prototype before recording the video

@tzvikarediano965

Жыл бұрын

@@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?

@CodeMonkeyUnity

Жыл бұрын

@@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.

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?

@bipedpotato

2 жыл бұрын

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.

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?

@CodeMonkeyUnity

2 жыл бұрын

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 kzread.info/dash/bejne/onhmmbuueqqZfJs.html

@zaibartsanddesign6610

Жыл бұрын

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.

Thanks for this video. I learned so much! I have just one more question. How can I get the second shortest path?

@CodeMonkeyUnity

Ай бұрын

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

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).

@CodeMonkeyUnity

4 жыл бұрын

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.

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!

@tughloksiddiquee1714

Жыл бұрын

A* is the most versatile as you can tailor it to your game's style

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?

@CodeMonkeyUnity

3 жыл бұрын

Instead of a single weight, make it based on the type of object that is requesting the path

Can you make a video about A* algorithm applied to an iso/staggered iso map?

Any Chance that this video would be updated for a Hex tile Pathfinding?

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!!

@CodeMonkeyUnity

3 жыл бұрын

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

@ODYMASTER

3 жыл бұрын

@@CodeMonkeyUnity Thank you very much, I will give it a try. Great content and I'm exited to seeing more from you :)

@nicholaspitti8171

2 жыл бұрын

//Testing.cs void Awake() //changed from Start->Awake { pathfinding=new Pathfinding(10,10); }

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.

@CodeMonkeyUnity

2 жыл бұрын

The method is different depending on if its a 2D or 3D camera kzread.info/dash/bejne/Yp6Isq2zY8rHZNo.html

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.

I tried following along with the code but the Grid code has changed since the previous video. So, I grabbed the unity package and got the code from there. I get an error in Testing.cs in Start() with this line -> pathfindingDebugStepVisual.Setup(pathfinding.GetGrid()); NullReferenceException: Object reference not set to an instance of an object

@CodeMonkeyUnity

9 ай бұрын

Maybe you just forgot to drag a reference in the editor, add a DEbug.Log to find out what is null unitycodemonkey.com/video.php?v=5irv30-bTJw

@DJSikosis

9 ай бұрын

@CodeMonkeyUnity Thanks ... yeh I ended up ripping all the code out, just keeping the new Grid.cs and then following along with the video.

Awesome tutorial! I'm making a clone of binding of isaac and this worked like a charm! Thank you codemonkey!

@CodeMonkeyUnity

11 ай бұрын

Nice! Best of luck with your game!

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.

@CodeMonkeyUnity

2 жыл бұрын

Yeah the thing is this wasn't planned as a series at all, it started by making a simple Grid System, then I built it up bit by bit as I needed it and I added extra features off screen when I needed them. If you watch all the videos and then inspect the code in the project files on the last video you should be able to understand how it all works.

What if you want to restrict the movement to just linear moves ie no diagonal movement across the grid?

@CodeMonkeyUnity

4 жыл бұрын

When getting the neighbour list at 10:39 only grab up, down, left, right

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?

Thanks!

@CodeMonkeyUnity

Жыл бұрын

Thanks for the Super Thanks!

Hello, so something for people who are confused as to why your line isnt showing up. Just in case it happened to anyone else, When you test for the PathFinding, the intructor types very fast, it took me about 10 rewinds of the same frame to realize they were adding a "color" field.

@thenoideaman

2 жыл бұрын

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.

@ericwallhagen3146

9 ай бұрын

@@thenoideaman This comment needs to be higher up. Almost tore my hair out figuring out why the line wasn't appearing!

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?

@CodeMonkeyUnity

4 жыл бұрын

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.

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.

@EpicJokinFail

4 жыл бұрын

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

@karimzarat7715

4 жыл бұрын

@@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.

Please do the optimization videos too

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!

@CodeMonkeyUnity

10 ай бұрын

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.

@j.g.8046

10 ай бұрын

​@@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)

@codeMonkey Hi, thank you very much for the tutorial, one question, how would we calculate Cost Distance in 3D space grid?

@CodeMonkeyUnity

Жыл бұрын

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.

@djub.2953

Жыл бұрын

@@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; }

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

@CodeMonkeyUnity

24 күн бұрын

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

@johnnyu3287

23 күн бұрын

​@@CodeMonkeyUnity I appreciate the response! And great idea, I might just do that 🤝🏻

Wow this video is gold

@CodeMonkeyUnity

Жыл бұрын

I'm glad you liked it! Thanks!

Hello code monkey at 7:20 when calculating the fcost which is gcost +hcost for entire grid you are initializing the gcost to int max but you are using the hcost uninitialized I dont know much about C# whether it iniatilizes it to 0 or is it like in C that according to the standard it may contain garbage values , my question is when calculating the fcost for the entire grid the hcost is zero? Thank you.

@CodeMonkeyUnity

4 ай бұрын

It initializes to 0 which is the correct value in the beginning, then it gets the proper hCost as the algorithm processes each node

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?

@CodeMonkeyUnity

3 жыл бұрын

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.

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 !

@CodeMonkeyUnity

4 жыл бұрын

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?

@randomdudeidk5160

4 жыл бұрын

@@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.

@randomdudeidk5160

4 жыл бұрын

Nevermind for the grid, I managed to changed it by re rewatching the videos, thank you for your quick answer. Have a nice day !

@randomdudeidk5160

4 жыл бұрын

I'm looking to change the character and the background at the moment

As Always is Great, but didn't understand why you put variable Grid grid to the class PathNode. I think it's not necessary.

Hi Code Monkey! Thanks for the great tutorial. Is there a way to implement Pathfinding with Grid instead of the specific Grid?

@CodeMonkeyUnity

2 жыл бұрын

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.

@ilparola

2 жыл бұрын

@@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

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.

@CodeMonkeyUnity

2 жыл бұрын

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 kzread.info/dash/bejne/ZmqlvMmdXbeTmM4.html

@elementz301

2 жыл бұрын

@@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!

Can this be used on a 3d object like a plane to divide it into a grid? I'm trying to do it from your grid video but can't seem to get it to display on the plane surface

@CodeMonkeyUnity

5 ай бұрын

Sure, you can make a 3D grid by stacking multiple grids on top of one another, that's sort of what I did in my House Building System which has multiple grid heights using the same underlying Grid System unitycodemonkey.com/video.php?v=Cdcn6uK9gPo

I want to limit the movement range of a given unit and visualize that range (like a fire emblem game) will limiting the F cost (using it as the movement rate) will help?

@CodeMonkeyUnity

4 жыл бұрын

You would limit it based on the G cost since thats the cost from the start node to the current node. So if gCost > MAX_MOVE_AMOUNT you would skip that node like the unwalkable ones.

@nerdydrow

4 жыл бұрын

@@CodeMonkeyUnity thank you

Hi. Given a position in the world space (that can be not on the grid), how can I find the closest path node to that point? Do I have to iterate every node on the grid and calculate the distance for each one of them or is there a simpler solution? Thank you in advance for your answer.

@CodeMonkeyUnity

5 ай бұрын

If it's not on the grid then you just need to clamp the world XY against the grid min/max. So if your grid is 10x10 and you clicked on what would be 15x5, you would clamp that 15 down to 10 and get the position 10x5

@danielebassano7635

5 ай бұрын

@@CodeMonkeyUnity Thank you a lot. Have a good day.

Hi. So, I couldn't figure out why you initialized the PathNodes to int MaxValue. Could you tell me why?

@charg1nmalaz0r51

2 жыл бұрын

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.

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.

@CodeMonkeyUnity

4 жыл бұрын

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.

@gazelle4204

4 жыл бұрын

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!)

@williamleebuckley

4 жыл бұрын

@@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.

@XavierDC

3 жыл бұрын

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.

@Matt-zx5jj

3 жыл бұрын

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

Any tips for having the pathfinding adjust to a wall being created that obstructs the current path the player is taking so that they reroute around it?

@CodeMonkeyUnity

2 жыл бұрын

You need to recalculate the path whenever the map changes

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.

@CodeMonkeyUnity

4 жыл бұрын

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)

@twobits7310

4 жыл бұрын

@@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?

I did this a long time ago in a galaxy far away in XNA, interesting you avoided a Recursive method

I wish I could type as fast as you :P

what is the benefit of this over unitys nav mesh?

Do u make hunter assasin? 😅 this is the 3th video of it 😊

hey, i was wondering how do i implement this system with height/jump system for AI? Great tutorial btw !

@CodeMonkeyUnity

3 жыл бұрын

You would need to add something like a linkNode to each grid position that defines jump points and modify the algorithm to take those into consideration when searching for the neighbours.

@nyan512

3 жыл бұрын

@@CodeMonkeyUnity i see, how about for a slope?

Thank you for all your work. You're amazing

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?

@CodeMonkeyUnity

Жыл бұрын

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

@ttuesday1

Жыл бұрын

@@CodeMonkeyUnity Damn, really didn’t think of that haha…. Thanks man!