Pathfinding in Unity DOTS! (Insane Speed!!!)
HTML-код
- Опубликовано: 25 янв 2020
- ✅ Get the Project files and Utilities at unitycodemonkey.com/video.php...
Let's implement Pathfinding in Unity DOTS, we're going to write everything in a Data Oriented way (Structs) in order to benefit from massive performance!
Here's the follow up video covering Pathfinding in Unity ECS
• Pathfinding in Unity E...
A* Pathfinding in Unity
• A* Pathfinding in Unity
What are Value Types and Reference Types in C#?
• What are Value Types a...
If you have any questions post them in the comments and I'll do my best to answer them.
🔔 Subscribe for more Unity Tutorials / @codemonkeyunity
See you next time!
📍 Support on Patreon / unitycodemonkey
🤖 Join the Community Discord / discord
📦 Grab the Game Bundle at unitycodemonkey.com/gameBundl...
📝 Get the Code Monkey Utilities at unitycodemonkey.com/utils.php
#unitytutorial #unity3d #unity2d
--------------------------------------------------------------------
Hello and welcome, I am your Code Monkey and here you will learn everything about Game Development in Unity 2D using C#.
I've been developing games for several years with 7 published games on Steam and now I'm sharing my knowledge to help you on your own game development journey.
You can see my games at www.endlessloopstudios.com
--------------------------------------------------------------------
- Website: unitycodemonkey.com/
- Twitter: / unitycodemonkey
- Facebook: / unitycodemonkey
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
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
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!
@Cyrus Noe instablaster =)
@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.
@Abram Alvaro it worked and I finally got access to my account again. Im so happy:D
Thanks so much you saved my account!
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.
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...
@@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.
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
Yeah the DOTS Animation is something I'd like to look into, haven't touched it at all yet
@@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.
Here's the follow up video covering Pathfinding in Unity ECS
ruclips.net/video/ubUPVu_DeVk/видео.html
Awesome as always ! Your knowledge on Unity, C# & Dots far surpasses most of the RUclipsrs in the field of game development.
Thanks!
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.
It's awesome you're doing something with Unity DOTS! I would like to see more!
I thought I was a good programmer but watching you code made me believe that I still have a lot to learn.
There's always someone better! If I watch John Carmack coding then I certainly start to feel the same!
Great work cant wait to see how much quicker it is on complex terrain following a moving target
Awesome, love your DOTS tutorials
Thanks for shading some light on this topic
using the index is a nice way around the restriction on recursive structs.
Everytime I see a video on Dots speed increase my jaw still drops to the floor :')
It's insane!
Thank you for the tutorial!!!
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.
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!
But without reverse, you can't find the nearest position if the destination is not reachable. Or I miss something?
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.
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,
@@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.
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
Great video, cheers mate!
Tbh you are really awesome.
Would like to see your Grid code using DOTS with pathfinding
Thats really nice ! :)
Thanks !
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
good question, would bump it
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
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.
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.
@@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.
Another optimization: use a NativeHashMap as a "NativeHashSet" for the closed list
@@supertrooperdk I'm interested on how do you implement all these optimizations. Do you still have the code?
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.
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.
@@CodeMonkeyUnity You gonna do a tutorial for that?
@@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
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
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?
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.
It can be even more optimised with priority queue instead of linear search for finding min fCost node
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!
What licence is the code under: can i use it in my own project, providing that I credit you?
I am using the Bellman-Ford algorithm for a current project ^^ However when i have the time i will switch to A* :D
This is such a great video, love so much
The syntax is quite different nowadays but the core data oriented logic should be the same
@@CodeMonkeyUnitythanks a lot
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 ?
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?
Should I learn DOTS as a beginner to Unity?
Thanks in advance for any reply. :)
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.
So is there a reason to not use a getter property on the fCost. Seems much better then just typing calculatefcost() every time.
Grate video! Thanks, question: Is it possible to project this grid as an isometric grid?
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.
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.
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.
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.
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
That didn't work for me. I had to enable "Allow unsafe code" in the project settings before Visual Studio would acknowledge it existed.
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?
what's the difference between int2 and Vector2Int, and why should I use one over the other?
How can I send a NativeList for the job without getting an error? I want to send a list of the notWalkable tiles.
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?
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.
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.
@@CodeMonkeyUnity Flow field video would be interesting.
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 ?
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
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.
Yeah I know I was trying to show the logic step by step, I'll definitely remove the redundancies as I optimize the algorithm.
How do I return the path as a data value? It seems like it can only be accessed within the job.
Try replacing the open list max priority scan with a priority queue.
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)
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.
Before watching the video I always click like
Crazy speed. Is it possible to make rendering multithreaded?
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 ruclips.net/video/t1f8ZreCuuQ/видео.html
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?
The DOTS Animation package is still in development but I'm not sure what state its in
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
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.
@@CodeMonkeyUnity lol so what should I write instead of int.maxValue?
@@nandorbacso4625 nothing just get rid of the + heuristic part
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.
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.
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?
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.
thanks, for your answer, i wait the next video :)
Good job. So how does this compare to A* package on the Assetstore? Does it work with DOTS?
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
@@CodeMonkeyUnity Oh, this is great. Thanks!
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.
How you add it ?
@@SoapOff Window/Package Manager, above change Packages to All, click and install it
@@SoapOff If it's still not showing up, under Advanced, click on show preview packages.
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.
How could it be done with a different distance between nodes?
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.
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"
I have the same issue
@@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
@@catthecat6227
I installed the Package but I still have errors
ok good i have restart my unity
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.
The project download isn't working for me. But great video!
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.
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.
@@CodeMonkeyUnity Awesome. I'll be looking forward to seeing them :) Thank you
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
I applied the path to entities in the following video ruclips.net/video/ubUPVu_DeVk/видео.html
First thing for tommorow. 😀
Are you planning to do a tutorial on client host multiplayer with DOTS?
Yup I definitely want to cover DOTS Multiplayer but haven't been following it so not sure what state it's currently in.
@@CodeMonkeyUnity oh yeahh, looking forward to it
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)
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
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!
I removed the entire isWalkable related code, and just put the unwalkable nodes in the closed list to start. Seemed to work for me.
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.
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?
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.
@@CodeMonkeyUnity I see, thanks for the reply! I
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.
Its possible to add nodes heap int DOTS to incerase speed even more ?
There are some ways of building a heap in DOTS but they are pretty complex since you have to stick with value types.
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?
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.
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?
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
@@CodeMonkeyUnity Awesome! Perfectly clear!
hi, nice video as always, i get an error saying "PathNode.isWalkable is not blittable" :(
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.
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
@@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
Every time you find a path you have to create all the grids in a double for loop? Why ?
I hope if this process applies to fill a texture2D
@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?)
Go into the package manager and update to 2D animations
In unity 2019.3.0f5 when i try to install ECS it installs for forever,how do i fix that,i have deactivated firewall and antivirus
Maybe try installing the dependencies one by one instead of all at once
Can I apply it for my enemy AI?
Sure, the pathfinding system doesn't care what its applied to
This guy's got big C# balls. Hope he can walk normally 😂 Outstanding job.
wana compare this to a visual script version?
What did you do to make the pathfinding code use dots instead of oop?
It's based on structs and value types with no reference types used allowing Burst to be enabled.
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.
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.
@@incutonez Cheers man!
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
@@INeatFreak wow, wishing harm on someone because of their preference, real mature. He has stated that the dark theme hurts his eyes.
@@aquaarmour4924 that was a joke and you just ruined it for everyone. Now i wanna hit YOU in the face.
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.
Interesting NativeList is no longer inside Unity.Collections. Any way it could be replaced? please help :)
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
Could you convert your games to android?
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.
Do you have Burst enabled? Did you see the log saying Burst compiled successfully
Is Node-Based Pathfind doable with DOTS too?
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
Im getting this error: Unity cannot resolve symbol 'Nativelist'. I already import Unity.Collections. Any help?
It's NativeList
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
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
@@CodeMonkeyUnity very valuable info. Thanks mate dev
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
I would if I could but dark mode burns my eyes
Is there is no way to simply convert a NavAgent component to the ECS? Do we actually have to implement A* pathfinding ourselves?
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.
@@CodeMonkeyUnity Thanks man
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 :/
Sure, feel free to write a class that achieves the same functionality. Trigger an action every certain amount of time.
@@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!
great tutorial sir
Have you seen the mesh video?
The only thing missing after that is just storing quad positions and playing them back
ruclips.net/video/11c9rWRotJ8/видео.html
Would like to see if there are the possibility about mecanim + Dots..
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
@@CodeMonkeyUnity Thank you for the replying. Regards!
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.
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.
@@D3ADmanWA1KING187 Thats quite interesting. I've never thought of doing it like that. Would that be more complicated that developing your own navmesh though?
@@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.
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.
@@D3ADmanWA1KING187 Hmm interesting. With that in mind though, Wouldn't that be less efficient because A* would have to run on each group?
When using job struct had to convert all of the used functions to static..
anyway the performance improvement is so stupidly huge, just use native arrays and structs instead of classes and write [BurstCompile]. xd
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.
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.
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.
🚨🚨🚨 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.
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?
@@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 :)
Thank you for this commentary. I was pretty sceptical about such insane boost and i seems like i was right.