DOTS pathfinding system [Updated]

Hi all.

This is a pathfinding system I have created which is multithreaded and burst enabled. It can run on hundreds or thousands of units taking maybe 2ms per frame.

I have uploaded the assets with a scene with some visuals aids to play with. Instructions are on the GIT

https://github.com/Tree37/HPA-Theta...em-in-Unity-DOTS-stack./blob/master/README.md

It is a hierarchical-version of a* algorithm with path smoothing as well. It delivers basically perfect paths and is very fast. Try to keep the grid within 10 million nodes big.

It has a queue system which queues jobs and only runs a few per frame meaning you can give thousands of units an order on the same frame and they will all find a path withing a second or two.

It takes big advantage of SIMD by using structure of arrays.

Can you please profile it and post your results with your system specs?
Can you let me know what you think of my code?
How can I optimize it?

Feel free to use for you own projects.

** Here's a tip you may not know. In Visual Studio, if you press ctrl+m, all the functions and regions will collapse, making it much easier to read.

 

The link appears to be broken, but it looks really promising atm!

 

Sry! Fixed.

 

Nice work!

It would be interesting to know how it compares with Unity navmesh pathfinding and could be worth documenting what the pros/cons of using one of the other are.

 

Unity Navmesh has some issues with spherical worlds if i remember correctly

 

Updated code. More elegant, and more performant, and more accurate.

 

I am having trouble with some of the assets, unfortunately if you import the scene it probably won't work. However, you can still use the scripts as a reference. Mainly PathfindingGraph and PathFindingSystem.

 

The link is 404. The closest thing I found is this: https://github.com/Tree37/TempPathfinding

 

Yes, sorry I haven't worked on this for a while, as it uses an older api, and this was kind of a test run. It wasn't really that good either, lol.

 

Well I'd say that anything that can "run on hundreds or thousands of units taking maybe 2ms per frame" is good in my book

 

I think is still worth to keep if public, even it does use old API. That both for reference and educational purposes. And people can forc and upgrade the code. I am curious, did you use flowfield too?

If you can, can you make it public? I am sure, some will appreciate it.

 

No, I didn't use flowfield. I stuck with A* because I use my own navmesh.

 

The performance is good, but the layout of code was bad. I used alot of unnecessary arrays, and you can clearly see the "amatureness" of the code style. I'm hoping to post my new system this year.

It turns out that making a standalone pathfinding system is much quicker and easier than making one integrated with many other systems and your own custom tools

 

Did you use basic A* or some variation like jump point or HPA*?

 

I used a 2 layer HPA* with Line of Sight path smoothing. The reason it's so fast with LOS is because I used a grid, where you can use Dijkras algorithm. I no longer use a grid because it's overkill and a waste of space for large maps. If you use a non-grid graph, LOS would have to be done by raycasting which is slower, but generally you will have much less nodes to search than a grid, so that's the tradeoff.

You can use a coarse grid for fast searching through large empty spaces, and use the graph when needed.