Check out that insane speed! How many Units do you think this can support? What kind of stress test would you like to see? 🎮 Play 7 Awesome Games (Action, Strategy, Management) and Help Support the Channel! ✅ Get the Game Bundle 67% off unitycodemonkey.com/gameBundle.php
@Songfugel4 жыл бұрын
I would like to see it (DOTS) used in a pathfinder that calculates routes in a more advanced node-network like finding best/fastest route on map with several different weights and possible routes depending on choice of transportation Or a complex RTS like demo, with an increasing number of agents path-finding around the scene with collision prevention and dynamic obstacles (other units, moving obstacles) Those would be really cool to see, but ofc would be a horrible pain to make
@cyrusnoe67093 жыл бұрын
I guess im asking randomly but does anybody know a trick to log back into an Instagram account? I stupidly lost the account password. I would love any assistance you can offer me!
@abramalvaro93983 жыл бұрын
@Cyrus Noe instablaster =)
@cyrusnoe67093 жыл бұрын
@Abram Alvaro Thanks for your reply. I got to the site through google and Im waiting for the hacking stuff atm. Takes a while so I will get back to you later with my results.
@cyrusnoe67093 жыл бұрын
@Abram Alvaro it worked and I finally got access to my account again. Im so happy:D Thanks so much you saved my account!
@ronsargeant83713 жыл бұрын
I never thought I would see a return to the old coding patterns that I learned when I started mainframe coding in the early 90's. Before OOP became a thing, everything was data oriented and parallel processing was an option for increased throughput. What goes around comes around.
@kken87663 жыл бұрын
That was exactly what I was thinking when they announce ECS... I was like WTF...when I start learning coding for the first time, all the textbooks are like, OOP is the best, the future, the right way to code... and now this...
@dav3562 жыл бұрын
@@kken8766 It's because of the change in technology. As computers got more powerful, OOP with its fast development time took over, since you didn't need to fuss over every little bit of performance. Now, as games get more technically demanding and computers get more cores, game developers once again need to increase performance.
@CodeMonkeyUnity4 жыл бұрын
Here's the follow up video covering Pathfinding in Unity ECS kzbin.info/www/bejne/q5O4gYmrlKmYjM0
@andreicirstea85175 жыл бұрын
Amazing job! Keep continuing with the ECS series because you are the only one who does them right! One question: could you cover animation and sounds(and possibly networking if that exists) in ECS? THANK YOU A LOT FOR YOUR CONTENT
@CodeMonkeyUnity5 жыл бұрын
Yeah the DOTS Animation is something I'd like to look into, haven't touched it at all yet
@Spherous5 жыл бұрын
@@CodeMonkeyUnity I played with it a bit, but there isn't even any documentation on it yet and you need to manually add the package to the package manager.
@SkaiCloud5625 жыл бұрын
I thought I was a good programmer but watching you code made me believe that I still have a lot to learn.
@CodeMonkeyUnity5 жыл бұрын
There's always someone better! If I watch John Carmack coding then I certainly start to feel the same!
@rahulkumarjha24045 жыл бұрын
Awesome as always ! Your knowledge on Unity, C# & Dots far surpasses most of the KZbinrs in the field of game development.
@CodeMonkeyUnity5 жыл бұрын
Thanks!
@justinwhite27255 жыл бұрын
I’ve read that it’s best to use Manhattan Distance (ie no diagonals) for your H. This allows you some leeway for walls etc and doesn’t give you an h that’s consistently too low. Also I recommend setting the square root of 2 as a constant and using that instead of the approximated 1.4 Also, you can run the code switching the destination and the source and then you don’t have a reverse array at the end.
@CodeMonkeyUnity5 жыл бұрын
I'll test ignoring H diagonals when trying to push it to the limit, it should speed up by a tiny percent. That last tip is genius! Hadn't thought of that at all! Just switch start and end and everything should work flawlessly!
@robertdorn40815 жыл бұрын
But without reverse, you can't find the nearest position if the destination is not reachable. Or I miss something?
@gregoryfenn14624 жыл бұрын
Flipping the dest and source works great as an optimization if your map/grip has the same movement cost in and out of every node (e.g. no upwards ledges to climb or one-way roads). Otherwise you have to do it the naive way and manually reverse the array.
@justinwhite27254 жыл бұрын
Gregory Fenn you’d still test the movement cost in the direction of travel. You can still test for cliffs and ledges etc. You’d calculate the values for each move in the direction of the move, you are just searching from end to beginning,
@huyopo4 жыл бұрын
@@CodeMonkeyUnity if you really want to push it to the limit, use a NativeHashSet(You can find the code on Unity answers) for the closed set and a Heap(i pretty much used the code from sebastian lagues partfinding tutorial adapted for structs) for the open set. I got from 40 seconds to 0.15 seconds just by switching out open and closed set with that pretty minor tweak.
@KiwiGalaxyDev4 жыл бұрын
It's awesome you're doing something with Unity DOTS! I would like to see more!
@varnonzero4 жыл бұрын
I appreciate all the different versions you tested here for performance, especially how you showed jobs/burst without ECS. Performance increases from switching to burst jobs can be very, very good. And while ECS is a little crazy, and still seems to be subject to development changes, jobs seems very ready.
@rancorjoy5412 Жыл бұрын
I need to learn to implement my code this well, the burst compiled version of the A* pathfinding you made is >10,000 times faster than the origional one you made! Edit: Thank you Code Monkey for reading this, even after 3 years
@lemurza52365 жыл бұрын
Everytime I see a video on Dots speed increase my jaw still drops to the floor :')
@CodeMonkeyUnity5 жыл бұрын
It's insane!
@supertrooperdk5 жыл бұрын
Thanks for the video! Another optimization for large maps: use a NativeList instead of a NativeArray which currently makes the whole algorithm quadratic due to its initialization. Using the NativeList, you can create the PathNodes only when necessary, and use a NativeHashMap for keeping track of the indexes in the NativeList (I'm simply incrementing the indexes). From my testing this helps for maps around 500 by 500 and larger. With a map of 1000 by 1000, pathing from (0, 0) to (999, 999) with 50 instances, it takes around 730ms with the new method, and 1080ms with the current NativeArray implementation. The most serious optimization would be to implement a NativePriorityQueue to use as the openList to bring down the linear min FCost search to logarithmic.
@CodeMonkeyUnity5 жыл бұрын
Yeah having the Pathfinding grid be generated as its needed is certainly something I'd like to research. Just need to figure out how to access the pathfinding map, maybe a ReadOnly NativeArray passed to all jobs.
@supertrooperdk5 жыл бұрын
@@CodeMonkeyUnity Agreed - I was imagining a passing in a persistent NativeHashMap into the job where Tile would have isWalkable and possibly weight information for the map. I like to use the positions as keys to allow for negative coordinates. I can DM you the code if you'd like.
@supertrooperdk5 жыл бұрын
Another optimization: use a NativeHashMap as a "NativeHashSet" for the closed list
@princata86762 жыл бұрын
@@supertrooperdk I'm interested on how do you implement all these optimizations. Do you still have the code?
@7th_CAV_Trooper2 жыл бұрын
using the index is a nice way around the restriction on recursive structs.
@tomnorc32494 жыл бұрын
Great work cant wait to see how much quicker it is on complex terrain following a moving target
@lawsylawsy65935 жыл бұрын
Awesome, love your DOTS tutorials
@chilldude0003 жыл бұрын
Wonderful! I just started exploring cache friendly layout, DOD, and Unity's ECS and this is one great example of its applications.. Question though, one of the blogs I read mentioned that grid-based data is not recommended for ECS due to the neighboring cells/node that causes jumps in the data that I assume might cause cache misses (most likely because of the vertical and diagonal checks). Question is, how come the neighbor checking doesn't seem to have caused that problem? Thank you in advance :D
@Korn1holio2 жыл бұрын
good question, would bump it
@misogear5 жыл бұрын
Tbh you are really awesome.
@penguin_of_linux37623 жыл бұрын
I dont understand. In this video your code does not use DOTS at 20:00 moment. Seems like you just wrote unoptimized code in previous lesson. I write A* myself with classes only and it works ~3 slower in my machine than your written by sctructures.
@Floyna3 жыл бұрын
At 9:40 if like me you can't access to NativeList : Project Settings --> Package Manager --> Enable Preview Packages Go to Package Manager --> Packages: In Project --> (+) --> Add package from git url --> com.unity.entities --> add
@King-mj2bn2 жыл бұрын
That didn't work for me. I had to enable "Allow unsafe code" in the project settings before Visual Studio would acknowledge it existed.
@c3rion5 жыл бұрын
Great video. Just one note; At 16:42 you never added any code to the positive case. In general, the condition here is unnecessary since you check the condition inside the CalculatePath function.
@CodeMonkeyUnity5 жыл бұрын
Yeah I know I was trying to show the logic step by step, I'll definitely remove the redundancies as I optimize the algorithm.
@zetanhwang4 жыл бұрын
Thanks for the tutorial, after I done it myself, I found it's really a good way to work in small size pathfinding which under 300*300 grids, when I try 1000*1000 even 500*500, it spend a really unimaginable long time, I have no idea about how to optimize it and my game really need that size.Btw, sorry for my English lol.
@CodeMonkeyUnity4 жыл бұрын
At that scale you need to split your world into multiple pathfinding maps and stich the final path together. For example in a game like Skyrim having a single Pathfinding map for the entire world would not be possible.
@TylerButh4 жыл бұрын
@@CodeMonkeyUnity You gonna do a tutorial for that?
@zetanhwang4 жыл бұрын
@@CodeMonkeyUnity Thank you, and that's what I tring now, I consider there's still a problem that when the start node and the goal node are not inside the same grids, I have to tell the player that "it's too far to navigate" lol
@coreytaylor36334 жыл бұрын
Subdivide is the right answer. Larger grids with smaller maps in it. The "world map" might only be 40x40 and each tile can contains 40X40 witch themselves can contain ... you get where I'm going. Similar to the quad tree concept and it applies very well with path finding maps. you only navigate the immediate (or possibly a few) subdivisions and update the maps when you reach the end of the current cell
@gilleswalther59644 жыл бұрын
Thanks for shading some light on this topic
@hasanprakash2 жыл бұрын
It can be even more optimised with priority queue instead of linear search for finding min fCost node
@a_tasja9 ай бұрын
Thank you for the tutorial!!!
@112Nelo4 жыл бұрын
Great video, cheers mate!
@NoirPhoenix4 жыл бұрын
For those who are having the issue with the 'NativeList' not being available, Make sure you have the unity Entities package installed onto your project.
@SoapOff4 жыл бұрын
How you add it ?
@PZMaTTy4 жыл бұрын
@@SoapOff Window/Package Manager, above change Packages to All, click and install it
@ShadowScorp993 жыл бұрын
@@SoapOff If it's still not showing up, under Advanced, click on show preview packages.
@elyr1um Жыл бұрын
Quick update for anyone new that also wants to try out DOTS, in the current LTS Version it will not show up, even when enabling preview packages in the project settings. The same happened to ProGrids, but fear not, there is still an easy way on how to always get the newest versions of these packages: - Open the Package Manager as usual under Window > Package Manager. - On the top left of the Package Manager Window, click on the plus sign and select 'add package by name...' - On the 'Name' field, write 'com.unity.entities' (com.unity.packageName is the naming scheme) - Leave the version field empty unless you want to install a specific version, otherwise it will always install the latest official release - Click on 'Add', and Unity should install the package without any other complications.
@clevereengamingartstudio65273 жыл бұрын
Hi first of all thanks a lot for this great tutorial There is something I am missing I think. F=G+H. And in your example in 2:31 you are saying that the Fcost in constantly decreasing. At first glance it seems that it's the heuristic H that is decreasing . Since F=G+H F will be increasing. (but decreasing from end to start)
@etopowertwon5 жыл бұрын
fCost is initialized incorrectly: int.MaxValue + heuristic will overflow integer and get values around int.MinValue. Though it doesn't look to matter, as fCost is recalculated for nodes before they added to list of nodes to evaluate
@CodeMonkeyUnity5 жыл бұрын
Wow that's correct can't believe I totally missed that. Yeah it doesn't cause an issue since the values are correctly calculated before being added to the open list.
@nandorbacso46254 жыл бұрын
@@CodeMonkeyUnity lol so what should I write instead of int.maxValue?
@charg1nmalaz0r512 жыл бұрын
@@nandorbacso4625 nothing just get rid of the + heuristic part
@totanon20185 жыл бұрын
Question: Could you further increase performance by exporting the lowest path values to an array for every grid square to every other grid square using the a* method. Feasible on fixed map sizes that remain static I would think. Instead of calculating on the fly, you would simply check what square they are on, what square they want to go to, and load up the path stored in a string array that was exported from this a* method that correlates with those to/from squares. At that point the a* method, OOP or DOTS would not be used during gameplay, just to generate new "maps" of pathways for each square whenever you create or change a map.
@totanon20185 жыл бұрын
Or even if the map is not static in-game, you would only run the a* method when a map change occurs during gameplay, rather than every time something moves.
@CodeMonkeyUnity5 жыл бұрын
Yes for static maps or maps that don't change often, caching the paths would possibly be a valid approach. However do keep memory in mind, if you try to cache all the paths in a 100x100 grid you'll have a massive amount of memory being used.
@bro-rubro9 ай бұрын
This is such a great video, love so much
@CodeMonkeyUnity9 ай бұрын
The syntax is quite different nowadays but the core data oriented logic should be the same
@bro-rubro9 ай бұрын
@@CodeMonkeyUnitythanks a lot
@personmuc943 Жыл бұрын
Is collision avoidance a feature that could be added to this code? like forcing the search algorithm to only choose nodes with the lowest traffic?
@lAztechl3 жыл бұрын
Hello, Great Tutorial. It really helps me a lot. Just one question. Can you give me advice on how can I optimize a grid size of more than 500+ size? Thank you in advance
@odo4324 жыл бұрын
Would you be keen on doing a video on flow field navigation (And if possible, DOTS implementation of it). This is particularly handy for RTS games and would fit in nicely with all your other RTS tutorials. I think flow fields have some advantages over A* when it comes to RTS style games with large maps and lots of units as the field only needs to be generated once instead of for every single agent.
@CodeMonkeyUnity4 жыл бұрын
Flow field is definitely a topic I'd love to explore, I know it can have tons of benefits but I've never actually used it.
@andyvickers90214 жыл бұрын
@@CodeMonkeyUnity Flow field video would be interesting.
@457Deniz4575 жыл бұрын
Thats really nice ! :) Thanks !
@KingRecycle695 жыл бұрын
Would like to see your Grid code using DOTS with pathfinding
@xenofrost693 жыл бұрын
This guy's got big C# balls. Hope he can walk normally 😂 Outstanding job.
@peddyjet4 жыл бұрын
What licence is the code under: can i use it in my own project, providing that I credit you?
@treymtz Жыл бұрын
Awesome, now all I need is instead of making a fake grid system have it take in a Unity grid made with tilemaps, and have it actually navigate a gameobject on screen. That and a function that listens to AI calling for pathfinding so that it is able to give those coordinates in grid fashion and queue it up for the scheduler to make it multi threaded still.
@rocksfire43904 жыл бұрын
that. is. magic. the amount of time it would take to complete pathfinding if proper (even simple optimizations) must be actually insane. a simple one would be changing closed list to a hashset, as list.contains is SUPER SUPER SUPER slow compared to hashset.contains.
@kim157424 жыл бұрын
Do you really think so? I would not have a closed set at all and have closed be an attribute or something, but you'd have to think about the particular problem in detail
@rocksfire43904 жыл бұрын
@@kim15742 well i already know that it boosts performance drastically because i already made a multi threaded pathfinding system a few years ago. any comparison between list.contains and hashset.contains proves that's the case and just swapping the list to a hashset is quite easy. also the particular problem is about method complexity or another more common saying is Big O. finding ways to reduce complexity even seemingly simple ones can have massive performance gains for large collections of data. a really cool look at this type of thinking is what Factorio did with their pathfinding. simple idea but it drastically reduced complexity (Big O) and thus increased the speed of finding a path. factorio.com/blog/post/fff-317
@ikelos81905 жыл бұрын
i'm still a begginer so i dont understand pretty much anything here but i just wanted to say that you're the only person i know that uses visual studio's light theme
@aquaarmour49245 жыл бұрын
@@INeatFreak wow, wishing harm on someone because of their preference, real mature. He has stated that the dark theme hurts his eyes.
@INeatFreak5 жыл бұрын
@@aquaarmour4924 that was a joke and you just ruined it for everyone. Now i wanna hit YOU in the face.
@CodeMonkeyUnity5 жыл бұрын
Great! A fellow light user! Based on the comments it seems preferring the light theme is rare, to me the dark one burns my eyes.
@framegrace14 жыл бұрын
Never used unity, but If your implementation of an array list objects using indexes stored on a native array, is 2 orders of magnitude faster than the C# implementation of an array list of objects HW using pointers, something is very wrong with that C# implementation.
@b975010634 жыл бұрын
Should I learn DOTS as a beginner to Unity? Thanks in advance for any reply. :)
@CodeMonkeyUnity4 жыл бұрын
If you're a beginner definitely stick to normal Game Objects. DOTS is great but it's also quite complex, if you're not experienced in Unity or as a programmer it can be tough to start learning it. But if you have extra time then by all means go for it, the more you expose yourself to more complex topics the faster you will learn.
@catthecat62274 жыл бұрын
the Unity is saying "The type or namespace name 'NativeList' could not be found (are you missing a using directive or an assembly reference?" but i already placed the "using Unity.Collections"
@michaelrobison44934 жыл бұрын
I have the same issue
@catthecat62274 жыл бұрын
@@michaelrobison4493 i found how to fix you need to open the asset packager i guess and go in advaced and turn on the preview, and there you can install the collection
@SoapOff4 жыл бұрын
@@catthecat6227 I installed the Package but I still have errors
@SoapOff4 жыл бұрын
ok good i have restart my unity
@Ne0mega4 жыл бұрын
I removed the entire isWalkable related code, and just put the unwalkable nodes in the closed list to start. Seemed to work for me.
@coreytaylor36334 жыл бұрын
Have you profiled the comparison? You might be surprised by what you learn. It may not actually be faster, some things that you think might be quicker are not always. Algorithmic complexity is important, but data structure often drives speed better than fancy tricks.
@ivijulsc4 жыл бұрын
I applied this to enemy pathfinding to enemies. It works perfect, the only problem is that sometimes when they don't find path it seems to take long time and game freeze for few seconds, i think the problem is that the grid size is 100x100. if i change "gridSize" int2 variable to (20,20) it won't work when my player and enemies are on other parts of the map. Could it be possible to modify the code so that my enemies only look for a path on a reduced grid of 20x20 depending on their current position? For example if my enemy position is (40,30) and my player is at position (30,20) the enemy look for a path on a gridSize of (20,20) without having to go thru the whole map.
@alexandreamiel18654 жыл бұрын
Hi ! Do you think switch this algorithm to 3D would be difficult ? At 2:30, why walking cost to start node is passing from +10 to +4 ?
@CodeMonkeyUnity4 жыл бұрын
Switching to 3D is simple if your floor is flat, just swap XY for XZ Moving horizontally is straight so it has a simple cost of 1, moving diagonally has a cost of square root of 2 which is 1.4 So to simplify, horizontal = 10, diagonal = 14
@112Nelo4 жыл бұрын
Just to clarify: What's missing here is actually using the path, right? The job calculates the path but it never gets returned to the main thread where it could be used to actually move a game object
@CodeMonkeyUnity4 жыл бұрын
I applied the path to entities in the following video kzbin.info/www/bejne/q5O4gYmrlKmYjM0
@kim157424 жыл бұрын
Okay, I don't quite understand this. I come from C++ and this is the standard way of doing things there (Mike Acton came from C to Unity, and he started this DOD trend). Anyways, in C++ this is standard code and not particularly data-oriented. In DOD you'd think about cache locality and have something like structs of arrays. I wonder what the "old" Unity C# way was, if this is so much faster. Can someone please tell me?
@CodeMonkeyUnity4 жыл бұрын
Behind the scenes yes everything is handled with structs of arrays and very careful to avoid any cache misses. The old way is using normal objects which can be placed anywhere in memory, so that leads to tons of cache misses as you try to do some work on lots of objects.
@kim157424 жыл бұрын
@@CodeMonkeyUnity I see, thanks for the reply! I
@jacklaplante31843 жыл бұрын
The project download isn't working for me. But great video!
@MrMikpik5 жыл бұрын
Are you planning to do a tutorial on client host multiplayer with DOTS?
@CodeMonkeyUnity5 жыл бұрын
Yup I definitely want to cover DOTS Multiplayer but haven't been following it so not sure what state it's currently in.
@MrMikpik5 жыл бұрын
@@CodeMonkeyUnity oh yeahh, looking forward to it
@wfolloni4 жыл бұрын
🚨🚨🚨 Unfortunately the full video is misleading in terms of performance 🚨🚨🚨 :'( I tried it locally and here are my results: With code from A* Pathfinding in Unity. - by just writing the 5x loop as you did => ~1100ms - now, removing the soldier => ~800ms (should be equivalent to what you have first) - now... removing the *Snapshot* related stuff => ~1ms Here are your huge performance improvement... you kept your debug code inside your pathfinding. In addition to that, I re-do the rest of the computation with the non-snapshot version of Object. In editor mode, grid 100x100 with a vertical wall of height/2 in middle, from 0,0 to 99,0 - Object (1x): ~370ms - Data (1x): ~380ms - Job (1x): ~380ms (of course no boost) - Job (100x): ~10'000ms (I have 4 CPU => 3x perf as only workers receive jobs) - Boost (1x): ~10ms - Boost (100x): ~300ms Now in "production" mode (by builting and executing the exe, in Windows 64bits) (be careful, the 32bits version is slower by a magnitude) - Object (1x): ~100ms - Data (1x): ~25ms - Job (1x): ~25ms (of course no boost) - Job (100x): ~700ms - Boost (1x): ~10ms - Boost (100x): ~280ms Conclusion: BoostCompile provides a ~40x boost in performance in Editor mode and only ~10x in production mode. The Data version is optimized a lot better in 64bits than 32bits and better than regular Object version. Tested with an old i5-3570, 3.4GHz. @R1PFake could be interested ;) /!\ It's really annoying to have such "lie" in a video. I am pretty it was a mistake but anyway, you should correct the title/description and put a comment about this. I spent multiple hours trying to understand how you achieved your 1000x performance boost with a manually written A*. Or it's just a click bait ;) PS: outside the performance mistake, the rest of the video is interesting.
@spektrepinball15964 жыл бұрын
I would like to understand your reply. You are stating the performance increase seen here is not because of ditching OOP for DOTS but instead has to do with debugging and "snapshot", Can you explain what in the original OOP version was running slowly?
@wfolloni4 жыл бұрын
@@spektrepinball1596 The different calls to: PathfindingDebugStepVisual.Instance.ClearSnapshots(); PathfindingDebugStepVisual.Instance.TakeSnapshot(grid, startNode, openList, closedList); If you remove them, you already improve from ~800ms to ~1ms. Try by yourself, you will be suprised :)
@AKU666 Жыл бұрын
Thank you for this commentary. I was pretty sceptical about such insane boost and i seems like i was right.
@peterprins862 Жыл бұрын
what's the difference between int2 and Vector2Int, and why should I use one over the other?
@r1pfake5215 жыл бұрын
Im sure DOTS is awesome, but comparing it to an unoptimized OOP version isn't really fair. And 700ms for 5 runs on a small 20x20 grid seems way too much for A*, either your time measurement is off or it is really very, very unopimized or there is a error in the code, because any decent A* implemention with OOP should be way faster than that.
@CodeMonkeyUnity5 жыл бұрын
I did mention how the OOP version is unoptimized but at the same time so is the Data oriented version I'm showing here so the comparison still works. You can definitely get OOP to run much faster than that but my point was more that no matter how much you optimize it will still be slower than a unoptimized DOTS version.
@RialuCaos4 жыл бұрын
On a 35x20 grid my object-oriented A* pathfinding doesn't take more than 66ms, and that's even without any optimization on Code Monkey's tutorial. Plus that's with a new calculation every frame and within a maze-like environment.
@alicivrilify Жыл бұрын
Good job. So how does this compare to A* package on the Assetstore? Does it work with DOTS?
@CodeMonkeyUnity Жыл бұрын
That package already has super fast multithreading, it has predated DOTS so I don't think it uses it unitycodemonkey.com/video.php?v=46qZgd-T-hk
@alicivrilify Жыл бұрын
@@CodeMonkeyUnity Oh, this is great. Thanks!
@josueccama3035 жыл бұрын
603/5000 HI amazing video, your channel as always looking for optimizations that are very necessary, Quick question, if I had a 1000 x 1000 grid, or even larger, obviously segmented in small 64x64 chunk, the search of the road would have to be done on the 1000 x 1000 grid, or on the chunk, and then gradually joining roads, this principle I still do not understand well about optimization and how you can join roads. If you could recommend me a book or paper on how to optimize search for roads in large worlds I would be grateful. Thank you very much, great video.
@CodeMonkeyUnity5 жыл бұрын
Stiching together various Pathfinding maps is something I've been meaning to research since I've never actually done it. There are lots of optimizations you can apply to the base A* algorithm. After getting this DOTS Pathfinding to work with entities I want to push it to the max with a massive map so hopefully I'll cover that soon.
@AlekseyLoykuts5 жыл бұрын
Never done this but just a thought - make large 64x64 grid, find path in it. Work with selected cells, find path between their centers one by one. Connect. Maybe when making 64x64 grid considering adding weights, depend on how many wall tiles there are... Any ideas?
@andrewshandle5 жыл бұрын
I think pre-optimizing before trying it on a 1000 x 1000 grid with DoTs is a sure fire way to go down a rabbit hole that might not have any value at all.
@josueccama3035 жыл бұрын
thanks, for your answer, i wait the next video :)
@themirlabs4 жыл бұрын
im not sure whats going on iv looked over it many times. my origonal object version takes about 100.00 but the DOTS one iv done along side this video up to 20:03 at this point takes 5000.00 iv looked over it again and again and other then a few name choices i prefer its the same code.
@CodeMonkeyUnity4 жыл бұрын
Do you have Burst enabled? Did you see the log saying Burst compiled successfully
@AdamJankowskiD Жыл бұрын
Hey Code Monkey! I see you have 2 videos about pathfinding one in DOTS and one in ECS... could you say what are the main differences?
@CodeMonkeyUnity Жыл бұрын
This one is building the A* algorithm using a data oriented design The ECS one is a follow up to this one and uses Entities that move along with the calculated path
@AdamJankowskiD Жыл бұрын
@@CodeMonkeyUnity Awesome! Perfectly clear!
@Frenuellcrackser333 жыл бұрын
I am using the Bellman-Ford algorithm for a current project ^^ However when i have the time i will switch to A* :D
@_denzy_63104 жыл бұрын
Crazy speed. Is it possible to make rendering multithreaded?
@CodeMonkeyUnity4 жыл бұрын
Yup, the normal hybrid renderer is already multithreaded but you can push it much further with something custom Here I managed to get up to 100,000 animated sprites kzbin.info/www/bejne/qmLJaY2omqioq7M
@AlissonVieir44 жыл бұрын
Grate video! Thanks, question: Is it possible to project this grid as an isometric grid?
@CodeMonkeyUnity4 жыл бұрын
It requires some math but yes it's doable. However the underlying Pathfinding map doesn't have to match the visual, so it might be simpler to convert the visual Isometric into a flat position and using that for pathfinding.
@miguelmn86023 жыл бұрын
Hello Code Monkey, I'm trying to mix what I've learned in this video with the one about returning values from a Job to the main thread. I don't find the way to return the path (NativeList) to the main thread. I've created a NativeList before creating the job instance and pass it, but when the Job ends the list length is always 0 although the list inside the job contain the path list with its values. Any idea of what I'm missing here? Cheers!
@jeremiemorinderuyter98174 жыл бұрын
Thanks for the videos is was very useful to help me do A* pathfinding inside a node graph. For the neighbors of each node what i did is use a int2x4 for referencing the index of connected nodes(because i'm in a graph not a grid where the offset are not fix) since we cannot use nativeArray inside of ComponentData, Someone have a better solution?
@SkeletonBill2 жыл бұрын
I don't want to allow diagonal movements in my game so I remove any references to that from your example. For some reason, this has a substantial performance impact - specifically removing the diagonals from "neighbourOffsetArray" increases the calculation time by a factor of about almost 1000. Why would this be? Shouldn't it be faster, if anything?
@dreamcatforgotten8435 Жыл бұрын
While it is true that you removed 4 neighbor checks, you now must take 2 steps to reach a diagonal as opposed to 1. And each step you take requires evaluating other things. This means re-evaluating the minimum FCost again on the next iteration, which requires a linear lookup in this version, and also performing another linear lookup by checking if the open list contains a node or not. tl;dr - removing diagonals means it takes more steps to reach the goal. More steps required means a bigger performance hit.
@ofirgeller225 жыл бұрын
Try replacing the open list max priority scan with a priority queue.
@LostConjugate4 жыл бұрын
This is awesome but was thrown off by the use of a Preview function NativeList and was not sure if I could replace with a C# List. I had to scoure google to find out how to get this Preview function added to Unity.
@incutonez4 жыл бұрын
For all of those in search of how to do this, I followed medium.com/@jeffreymlynch/where-are-the-missing-preview-packages-in-unity-2020-3ad0935e4193 and added com.unity.collections... don't forget to reload Visual Studio.
@wzrd55723 жыл бұрын
@@incutonez Cheers man!
@captn_hanky5 жыл бұрын
Before watching the video I always click like
@blusoldier0189 ай бұрын
How do I return the path as a data value? It seems like it can only be accessed within the job.
@masterdragonx4985 Жыл бұрын
How could it be done with a different distance between nodes?
@NoirPhoenix5 жыл бұрын
Hi Code Monkey, I'm new to jobs. I don't suppose you would know how to access the waypoints generated from the pathfinding script into an npc script. At the moment i'm calling the jobs function in the script but i have no idea how i'd go about accessing the waypoints outside of the jobs running statement. Usually i'd just make a variable public and access it that way but with jobs i'm guessing it resets the list and therefore a public variable for the waypoints would be pointless.
@CodeMonkeyUnity5 жыл бұрын
I'm currently researching the best way to use this Pathfinding with the rest of the Entity Component System. One way is to have a DynamicBuffer in an Entity and fill that up inside the job. Trying to get it all working by next weekend.
@NoirPhoenix5 жыл бұрын
@@CodeMonkeyUnity Awesome. I'll be looking forward to seeing them :) Thank you
@davidhuang83144 жыл бұрын
so the ballJumpSystem does not need to be put on a gameObject. But it's not responding to the space key when I run it. Am I missing something?
@СергейВоронин-т2б Жыл бұрын
Hi. Very good video, but i found an issue. On big maps it works very slow even without obstacles and with single seeker and even if distance between points small. Its because each time inside job you initialize full map. But it not needed because map always the same and if we can generate pathNodeArray outside of job and send its copy to job it would be nice boost. Because on map 10x10 2000 units found path for 6ms but on map 1000 x 1000 1 unit found path from 0,0 to 10,10 for 20-30 ms. I tried send this map but always meet errors. Pls help me with this problem.
@Cash_Online4 жыл бұрын
@Code Monkey PLEASE HELP ME I get this error when I write the pathfinding script I try everything I have downloaded the script from your website but is still the same I got this error please help me, Library\PackageCache\com.unity.2d.animation@3.2.3\Runtime\TransformAccessJob.cs(196,62): error CS1061: 'NativeHashMap' does not contain a definition for 'Length' and no accessible extension method 'Length' accepting a first argument of type 'NativeHashMap' could be found (are you missing a using directive or an assembly reference?)
@peddyjet4 жыл бұрын
Go into the package manager and update to 2D animations
@im_sentient36122 жыл бұрын
If anyone is following the tutorial instead of downloading the code and getting stuck in an infinite loop, the function RemoveAtSwapBack() must've changed so instead of accepting the value to be removed its the index of the element to be remove. I made the change below and now it's works correctly. openList.RemoveAtSwapBack(openlIst[i]) => openList.RemoveAtSwapBack(i)
@dribbler81315 жыл бұрын
Would love to see you using this DoTs system with a Animated Entity, I am struggling so much with Animating an Entity in 3D, Would love you to show a tutorial on using 3d models in Entitys with Animator Controllers, Or is this not possible yet?
@CodeMonkeyUnity5 жыл бұрын
The DOTS Animation package is still in development but I'm not sure what state its in
@benayamanuel4 жыл бұрын
When i tried to put FindPath's function content into the Execute() method, all the functions like CalculateIndex, IsInsideGrid and etc throw an error "an object reference is required for the non-static field". Im confused since in the video theres no error. I followed the exact same way as u did. Any idea ?
@clossidev76724 жыл бұрын
How can I send a NativeList for the job without getting an error? I want to send a list of the notWalkable tiles.
@YassinTheDestroyer4 жыл бұрын
Can I apply it for my enemy AI?
@CodeMonkeyUnity4 жыл бұрын
Sure, the pathfinding system doesn't care what its applied to
@NoirPhoenix4 жыл бұрын
Hi Code Monkey, i understand this is asking alot and is quite difficult from the sounds of it but if by any chance you know how to use A* pathfinding in a 3D environment with elevations, Would it be possible to produce a tutorial on how we could adapt the script in order to function with those conditions? Thanks.
@D3ADmanWA1KING1874 жыл бұрын
If you understand A* on a 2D grid then it's pretty much the same in 3D only instead of having X, Y you would have X, Y, Z. The hard part is your implementation and how you calculate the neighbours for various nodes. I would suggest first thinking of something simple like an office building that uses ladders instead of stairs. On the first floor all of your nodes would be X = ?, Y = ?, Z = 0. On the second floor all of your nodes would be X = ?, Y = ?, Z = 1. And if node X = 1, Y =1, Z = 0 has ladder on it, then node X = 1, Y = 1, Z = 1 would be it's neighbour. Once you understand that then you can think about the fact that your pathfinding nodes don't need to have real world positions. You could store logical AND real world positions on your nodes or calculate the real world positions based on some other factors. For example: Say you have a map that has some flat areas and some hills, some buildings and some caves. The path finding nodes for the ground (flats and hills) could all be X = ?, Y = ?, Z = 0 and then store some extra height information for the real world values. All the cave nodes could be X = ?, Y = ?, Z = -1. The cave entrances would be a neighbour from one of the ground nodes to one of the cave nodes. Same for the buildings. They could be X = ?, Y = ?, Z = 1+ floor number where every node that has a staircase or ladder is a neighbour to the floor above.
@NoirPhoenix4 жыл бұрын
@@D3ADmanWA1KING187 Thats quite interesting. I've never thought of doing it like that. Would that be more complicated that developing your own navmesh though?
@D3ADmanWA1KING1874 жыл бұрын
@@NoirPhoenix Im no expert on this (So someone else can correct me if im wrong) but essentially, a grid is a navmesh where every area has a uniform shape and size (A square or hex etc). Think of it like this: Take a 16x16 grid of low level nodes. Now split them into groups of 4x4. Every group becomes a node on a separate graph. Now run A* on all the groups. Then with the path of groups that it gives you run A* again on each individual group to get the paths through each. Then at the end combine the paths that you get from each group and you have your final path. Now if you change your groups of nodes from being 4x4 squares into rectangles and hexs or any other shape each containing various amounts and arrangements of low level nodes then you have a navmesh like your probably thinking of. Remember A* has absolutely no clue what its looking at. It doesn't care about in game height or anything like that. And it doesn't care if your nodes are actually groups of other nodes or just individual nodes themselves. You could give it a graph of elephants but as long as you tell it which elephants are next to each other and how much it costs to move between them then it will work exactly the same.
@D3ADmanWA1KING1874 жыл бұрын
To combine that with your original question, take a 3D map with no buildings or caves. It just has the ground with some hills, mountains and valleys. Now look at that map from a top down view. It becomes a simple X, Y grid. Simply path a unit through the X, Y grid and then set it its height according to the terrain height. (Your nodes could have something like: node.LogicalPosition.X node.LogicalPosition.Y node.RealWorldPosition.X node.RealWorldPosition.Y node.RealWorldPosition.Z) Now if you have a plane flying over aswell, do the same thing as the other unit only set its height as terrain height + flying height. Then looking at the map top down again, split some nodes into groups and put little towns in them. Now each town can become its own node. If your at town A and trying to get to town D then A* might take you through town B etc. When you get to a town, run A* again on that towns group of nodes to path your way through it to the next town. Remember you control everything including the scale. So instead of it being a giant map, it could be the floor to a building, and then the towns could instead be rooms. All you need to do is translate your game world to a graph or various graphs, let A* do its thing, and then translate A*s results back into your game world.
@NoirPhoenix4 жыл бұрын
@@D3ADmanWA1KING187 Hmm interesting. With that in mind though, Wouldn't that be less efficient because A* would have to run on each group?
@rafarodriguez47652 жыл бұрын
Is DOTS TODAY reliable and stable in Unity? To ship a serious project for consoles? Any example of any console shipped game using it? Thanks
@CodeMonkeyUnity2 жыл бұрын
V Rising is a recent game using it, another one is Zenith But Entities is still in experimental, it is scheduled to be fully released next year However the other components of DOTS, the Job system and Burst compiler, those are already production ready
@rafarodriguez47652 жыл бұрын
@@CodeMonkeyUnity very valuable info. Thanks mate dev
@alimorgan14072 жыл бұрын
So... I followed along with this tutorial and the previous on (object oriented), and somehow, the object oriented approach measured 20x - 30x faster than my implementation using value types...
@CodeMonkeyUnity2 жыл бұрын
Do you have Burst enabled? Are you using the Job System? The benefits don't come from just using Value types but rather from those two tools which only work with Value types
@alimorgan14072 жыл бұрын
@@CodeMonkeyUnity I didn't, but I have it now and it is so much faster!
@MasterofFire-sc3yn4 жыл бұрын
I am having an error that gives me no path even though the start and end are in the grid and that the grid is all walk-able. How can I fix it?
@anime4u5685 жыл бұрын
great tutorial sir
@CodeMonkeyUnity5 жыл бұрын
Have you seen the mesh video? The only thing missing after that is just storing quad positions and playing them back kzbin.info/www/bejne/Z2LGaqWNh9SngJo
@Lord22255 жыл бұрын
8:31 You cant create constructor?
@CodeMonkeyUnity5 жыл бұрын
Sure you could make a constructor that takes all parameters. Normally when working with structs I stick with the empty constructor and manually modify the fields, it's another way of remembering that I'm working with a struct and not a class.
@xSoNiCcRaCkErSx7 ай бұрын
Using this code, for some reason no matter what I do, I cannot get the path back from the job. I can see it creates it just fine in the job. But no matter if I use TempJob / Persistent or NativeArray or NativeList it always returns empty. I was able to get this working however with other simple examples. Something in this code is causing it and I cannot figure out what it is. Any ideas on how to solve this?
@xSoNiCcRaCkErSx7 ай бұрын
I found the issue. line 203 (NativeList path = new NativeList(Allocator.Temp);) defines a new local path allocated NativeList which is overwriting the public one defined in the struct. Remove this line to fix it.
@MrTastelessVideos4 жыл бұрын
I wonder if you could use a Unity. AI navmesh and implement this algorithm instead of the Standard Pathfinding... Well, gotta go and find out!
@Spherous5 жыл бұрын
I did a bit of pathfinding in 3d ecs using unity's experimental ai namespace. Its pretty dope. Also please use dark mode in your ide already D: watching your videos sears my eyes
@CodeMonkeyUnity5 жыл бұрын
I would if I could but dark mode burns my eyes
@saadkhurram38414 жыл бұрын
Is there a way to smooth the paths because currently my unit is going point to point whereas i want him to maybe curve or move toward the next appropriate location (human like behaviour)
@Korn1holio2 жыл бұрын
it's called path postprocessing. What I did was breaking up the path into nodes where the direction altered (i.e. 1.0 - 12.0 - 12.5 - 13.6 etc).... once you have those nodes you can do further work on them
@shuashuashua15 жыл бұрын
Its possible to add nodes heap int DOTS to incerase speed even more ?
@CodeMonkeyUnity5 жыл бұрын
There are some ways of building a heap in DOTS but they are pretty complex since you have to stick with value types.
@blakeguyan26624 жыл бұрын
Hey, is there a way around using the function periodic from your utils... not that i have a problem with your code, i just feel likei wont have built it properly if i dont write it myself :/
@CodeMonkeyUnity4 жыл бұрын
Sure, feel free to write a class that achieves the same functionality. Trigger an action every certain amount of time.
@blakeguyan26624 жыл бұрын
@@CodeMonkeyUnity Yeah i went in to the code and looked at what it did :P i should have just done that in the first place! Am now half way though the next path finding video!
@sekker2k4465 жыл бұрын
Would like to see if there are the possibility about mecanim + Dots..
@CodeMonkeyUnity5 жыл бұрын
I haven't been keeping up with the DOTS Animation package but I believe its still being worked on. I think the latest sample uses it
@sekker2k4465 жыл бұрын
@@CodeMonkeyUnity Thank you for the replying. Regards!
@borzonstudios86384 жыл бұрын
Is there is no way to simply convert a NavAgent component to the ECS? Do we actually have to implement A* pathfinding ourselves?
@CodeMonkeyUnity4 жыл бұрын
DOTS is still very much in development so right now yes you need to build it yourself. After they get the core fully stable then they will begin building features on top of it and I'm guessing NavMesh will be one of the priorities.
@borzonstudios86384 жыл бұрын
@@CodeMonkeyUnity Thanks man
@kodman19912 жыл бұрын
Interesting NativeList is no longer inside Unity.Collections. Any way it could be replaced? please help :)
@CodeMonkeyUnity2 жыл бұрын
Do you have the package installed? forum.unity.com/threads/solved-nativelist-is-not-found.865876/ It's still there in the latest version docs.unity3d.com/Packages/com.unity.collections@1.4/api/Unity.Collections.NativeList-1.html
@XxxTheGoldenApplexxX5 жыл бұрын
What did you do to make the pathfinding code use dots instead of oop?
@CodeMonkeyUnity5 жыл бұрын
It's based on structs and value types with no reference types used allowing Burst to be enabled.
@edwinmacias70383 жыл бұрын
hi, nice video as always, i get an error saying "PathNode.isWalkable is not blittable" :(
@WelshGuitarDude3 жыл бұрын
Every time you find a path you have to create all the grids in a double for loop? Why ?
@minecraftermad4 жыл бұрын
wana compare this to a visual script version?
@vicenterusso5 жыл бұрын
Is Node-Based Pathfind doable with DOTS too?
@CodeMonkeyUnity5 жыл бұрын
Hmm it's possible but not sure what the correct way would be, instead of holding a reference to the linked PathNodes you would hold the indexes It would be trivial if you have a limited number of links, but if you want and expandable Link List then maybe holding a NativeArray but not entirely sure that would work. Probably best to hold the Link List outside of the actual PathNode
@biyagames86984 жыл бұрын
I hope if this process applies to fill a texture2D
@kidpog3d1014 жыл бұрын
I am making a race game and the normal ai keeps pushing the car away or intersecting with it. I hope with this I will be able to make a better system than unity pathfinding.