[Open Source] Node based Path Finding (Eager Dijkstra)

[Antypodish]

Unity DOTS Node based Path Finding

Unity DOTS node based path finding, using Eager Dijkstra modified Shortest Path algorithm.
I have introduced additional git branch (to keep it separate and a bit more complex) ~~ (Weights and Mask) ~~ which introduces nodes ranges, weights and masks.

Video

https://www.youtube.com/watch?v=9GBRigAs2lc

Unity (DOTS): Node Based Path Planning (Open Source)

Scene

Scene represents some terrain with elevations and path nodes. Instead of mesh path, project utilizes nodes, to generate neighbour network of nodes, with possible routes. These become static, as current system do not allow for changing this network at runtime.

• ~~ (Weights and Mask) ~~ Optionally each node can have set range (PathNodeLinkRangeComponent), in which will detect other path nodes, and weights (difficulty) with mask (PathNodeMaskWeightsBuffer). See path node scene inspector for more details. If weighs are used, mask must be set accordingly in path planner entity (PathPlannerWeightsMaskComponent).

Further path planner entities allow for searching best path. Setting are set for 100 entities by default, in OrderNewPathSystem.cs. Tested with 10k path planner entities. But advise to comment out debugging raycast, which is in PathFindingSystem.

Generation

At the scene initialization. all nodes are tested against each other, with grouping per elevation. For example ground path nodes are separate, from upper levels. Raycast from each node in same group are cast to each next neighbor node, on same the level. This is represented by gray color ray lines at initialization. Red lines indicate, that path to next node have been obstructed by wall, or ramp. Green lines inform of correct nodes links. Distances as weights are stored, with relation between nodes.

• ~~ (Weights and Mask) ~~ If range is set (greater than 0), range will be used. Otherwise each node on the same elevation will be checked. Links will be created accordingly. Different elevation checks is ignored by range.

Regarding elevation, like ram, nodes need to be marked manually, via inspector, with which other node link is allowed. That should be done in most cases for both up and down nodes.

That relation is added to network of nodes.

Path Finding

When starting and ending points are selected, path planner entity is marked as ready for path finding. Path Finding System job is executed once, and debugging rays are rendered. White lines indicate tested near routes. Green lines mark best possible route.

• ~~ (Weights and Mask) ~~ If weights with mask are set and its buffer size is greater than 0, path planner entity will be testing own mask, against each node mask. With middle mouse click can cycle through path planners, which each can have optionally own weigh mask set. Cycling starts from -1, which means, each entity will be executing path finding. Otherwise, each individual entity will be executing path finding. See console for details.

Controls

• Left click on the node in the game view, is starting point.
• Right click is the end point of the path.
• ~~ (Weights and Mask) ~~ Middle click, toggle through path planner entities. Be aware, in the example script, if there is a lot entities, it may take many clicks to cycle them through.

Editor Mode Gizmos Debugging (Weights and Mask)

When node is selected in editor mode, it will display path node range (green wired sphere). If range is negative (sphere is small), every node will be tested on the same elevation. Otherwise, nodes within a range on same elevation will be checked. Target nodes render white wired gizmos. Rays link from source to target nodes are purple and always reach target node. Cyan ray links are from target to source. Their length is distance, or range (if smaller than distance) to source node.

Atm different debugging links and gizmos are not functional in edit mode, for changing elevation. Collision are also not tested in edit mode, to validate path.

More will come soon.

Source:

Antypodish/Unity_DOTS_NodePathFinding/blob/main/README.md

~~ (Weights and Mask) ~~
Separate branch

Antypodish/Unity_DOTS_NodePathFinding/blob/Weights-and-mask/README.md

Support

Please let me know, if you have any questions, or finding a bug. Enjoy.
If you appreciate my work, please like my repo on github. Many thanks

[Antypodish]

Debugging raycasts at initialization of the scene and during generation of the nodes network.

All possible casts and valid and invalidated links.

Valid and invalidated links.

All valid links.

~~ (Weights and Mask) ~~
All valid links, with applied range limits.

[Antypodish]

Path finding

Tested possible routes.

The path.

Profiling 10k entities searching for path, at the same frame (see jobs).

Still need figure out, how to remove bits of memoryManager fallbackAllocation.
I removed most of it already.

[tertle]

Not going to really comment on implementation etc but one easy performance improvement you can make is your thread utilization seems very poor

To fix this you should change your PathFindingJob that’s using IJobChunk to IJobEntityBatch.

[Antypodish]

Yeah, you are right @tertle . I have realized that too. But very valid point.
I did expected IJobChunk will be much better. I don’t know why it is utilizing threads so badly.
Sometimes it is better, other times is worse. I only suspect, that it is because, I run it only once at request, whenever mouse clicks are issuesd.
Maybe if job would run continuously, jobs would know how to distribute it across threads…
I implemented it at quick, after replacing IJobForeach. Not impressed however

I saw your some post today, somewhere, mentioning IJobEntityBatch. So I may indeed will look into it.

[tertle]

@Antypodish

Yeah, you are right @tertle . I have realized that too. But very valid point.
I did expected IJobChunk will be much better. I don’t know why it is utilizing threads so badly.
Sometimes it is better, other times is worse. I only suspect, that it is because, I run it only once at request, whenever mouse clicks are issuesd.
Maybe if job would run continuously, jobs would know how to distribute it across threads…
I implemented it at quick, after replacing IJobForeach. Not impressed however

I saw your some post today, somewhere, mentioning IJobEntityBatch. So I may indeed will look into it.

IJobEntityBatch is basically a replacement for IJobChunk (you should always use it instead now)
If you feed a value of 1 in it’s exactly the same as IJobChunk, but if you feed a higher value it can break chunks up into parts and spread them across threads (i.e. what you are looking for.)

[Antypodish]

@tertle

IJobEntityBatch is basically a replacement for IJobChunk (you should always use it instead now)
If you feed a value of 1 in it’s exactly the same as IJobChunk, but if you feed a higher value it can break chunks up into parts and spread them across threads (i.e. what you are looking for.)

Thx @tertle . I just replaced it and set for now batch of 256, to see how it goes. Much better in terms of threads utilization.

But memory Fallback is now killing me

I know, that is because of NativeArrays in job. I wonder, if should I offload NativeArrays to DynamicBuffers instead.

I got something like that in that job, of execute. Anty thoughts to improve / rid of NativeArrays?

 public void Execute ( ArchetypeChunk batchInChunk, int batchIndex )
            {

                NativeArray <float> na_netNodesBestDistance2Node            = new NativeArray <float> ( na_netNodes.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory ) ;
                NativeArray <bool> na_isNetNodesAlreadyVisited              = new NativeArray <bool> ( na_netNodes.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory ) ;
                NativeArray <int> na_previouslyVisitedByNodeIndex           = new NativeArray <int> ( na_netNodes.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory ) ;

…
}

[tertle]

256 way higher than you need. I would have suggested like 4.

Also there is a trick with memory management for things like this. You don’t need to allocate it per execute, you can do it once per job thread.

[NativeDisableContainerSafetyRestriction] private NativeArray <float> na_netNodesBestDistance2Node;
[NativeDisableContainerSafetyRestriction] private NativeArray <bool> na_isNetNodesAlreadyVisited;
[NativeDisableContainerSafetyRestriction] private NativeArray <int> na_previouslyVisitedByNodeIndex;

public void Execute ( ArchetypeChunk batchInChunk, int batchIndex )
{
    if (!na_netNodesBestDistance2Node.IsCreated)
    {
        na_netNodesBestDistance2Node = new NativeArray <float> ( na_netNodes.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory ) ;
        na_isNetNodesAlreadyVisited = new NativeArray <bool> ( na_netNodes.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory ) ;
        na_previouslyVisitedByNodeIndex = new NativeArray <int> ( na_netNodes.Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory ) ;
    }
    else
    {
        // memclear if required
    }

Keep your value at 256 and change your allocations to that and see the difference (that said don’t keep it at 256 except for this test)

[Antypodish]

@tertle , this is completely nuts. I mean, I am totally baffled over batching size. I wouldn’t though, it will make so much difference, for 10k entities. But here is what I got.

It looks like, bigger the batch is, the worse performance it is.

Batch size 1

Batch size 4

Batch size 50

Batch size 256

This is case of 1 batch, without moving NativeArrays outside Execute. It seems is more less the same, as if I move and add [NativeDisableContainerSafetyRestriction].

[Sarkahn_1]

You should disable safety checks and leak detection when profiling. That’s what the pink bars are, thats time wasted on editor only safety checks

[Antypodish]

@Sarkahn_1

You should disable safety checks and leak detection when profiling.

I got them off in all examples above.
But maybe it is indeed something which comes strictly from the editor. Too many of these across different jobs.
I would need build and profile, to test for these falback allocations.

[tertle]

@Antypodish

@tertle , this is completely nuts. I mean, I am totally baffled over batching size. I wouldn’t though, it will make so much difference, for 10k entities. But here is what I got.

It looks like, bigger the batch is, the worse performance it is.

I think you misunderstand what this batch field does.

A value of 1 means each chunk is separated as normal like IJobChunk so now execute is called up to 1 times per chunk
A value of 2 means each chunk is broken into 2 separate batches so now execute is called up to 2 times per chunk
A value of 256 means each chunk is broken into 256 separate batches so now execute is called up to 256 per chunk

Why you might want to use this is if you have a really slow job (i.e. pathfinding).
If you had all your entities in 1 chunk, you would only execute on a single thread and all your other threads would be empty.
If you set a value of 4 this would break the chunk up over 4 separate groups letting it spread over multiple cores.

You don’t want huge values for this.

Because of these extra calls to execute, you have to avoid allocating per execute and instead re-use it.

[Antypodish]

@tertle ah that is good. To know,
I thought batch means numbers of entities per job. Somehow similar, as IJobParallelFor. Hence I wanted to keep it higher.
But that explains now such behaviour.

[Antypodish]

@tertle , @Sarkahn_1 , I just run profiler in build. This looks now much better.
No mem allocations.
Many thanks guys for a feedback.

Just a side note, the visible spike in fact is realated to previous frame of other (example) system, which is just updating 10k entities not in job. So ignore that part.

[jasons-novaleaf]

@tertle

256 way higher than you need. I would have suggested like 4.

Also there is a trick with memory management for things like this. You don’t need to allocate it per execute, you can do it once per job thread.

@Antypodish If you are still having problems with the above quote, FYI I created a nice pattern for Mapping a temp object per thread with ability to aggregate results on the main thread. Kind of a Map-Reduce, but you don’t need to reduce. Can also be used to allocate per-thread resources like a Random class.

I would post it here but it’s spread over a few files. If you want I can either put it on a git repo or explain it technically or both. Basically some abstractions over using the [Unity.Collections.LowLevel.Unsafe.NativeSetThreadIndex] attribute. I plan to share it with the community but I haven’t had time to do any Unity in the last few weeks due to work-work. (I want to convert it to a NativeCollection before sharing)

[Antypodish]

@jasons-novaleaf thank you for your input.

As of current it appears, that setting batch count to low, or even one, resolves threading distribution issue.
It is a big improvement already.

If you believe you can further improve performance, please feel free to drop git link preferably. If not git, files with further instructions would be appreciated.

[jasons-novaleaf]

okay, if you dont mind running it single thread then no problem, my abstraction is only helpful for multithread processing. I will run your project when I get a chance, and check performance and see if there’s anything I know how to speed up.

[Antypodish]

@jasons-novaleaf

okay, if you dont mind running it single thread then no problem, my abstraction is only helpful for multithread processing.

I don’t mind, as long it is suitable for given scenario. Surely that can be flexy and adjusted to needs. However, when is possible, I prefer offload to threads.

@jasons-novaleaf

I will run your project when I get a chance, and check performance and see if there’s anything I know how to speed up.

I am looking forward to your results, whenever you will get a chance. And if the result would be better, or worse, please post your findings.

[Antypodish]

In fact I meant to record vid, but been a bit lazy, so I decided to stick a bit more with coding for time being and add following useless features, while I a bit carried on myself

I spent quite a bit of time debugging it. I hope, no more seeking in.

I have introduced secondary seprate branch
~~ (Weights and Mask) ~~

Antypodish/Unity_DOTS_NodePathFinding/blob/Weights-and-mask/README.md

Which is a bit more advanced and a little more complex.

It allows to set ranges for each path nodes, so you can limit, how far (see gizmo) each node can check other nodes, as long they are on the same elevation. Elevation links are ignored by range.

Also, I have made weights and mask for each node. Each node now can be “harder” for path finding than others, besides only distance. Whats more, each weighs can be assigned to mask (using DynamicBuffer on the nodes).
Matching mask on path planner entity, allows to get weighs accordingly. Matching more than one weigh per node, will be accumulated.

As the result, multiple path planner entities can run, with different paths, starting and ending at same points.
Imagine for example a terrain, which is more friendly for one team than other team.
Or having car, which want to avoid rough terrain, while tank can pass through at ease.
Or consider adding water and boats

My marvelous art on top of screenie

There is snag atm. to it however, which I need deal with. You don’t want to boat go through desert, even path is very difficult. So I need introduce “ignore node” feature, or just set certain value, above which node will be ignored. Lets say 65535, or something like that.

One more screene also, with all valid (green) links and applied some limit ranges.

Updated first post too.

Enjoy repo
~~ (Weights and Mask) ~~
Separate branch

Antypodish/Unity_DOTS_NodePathFinding/blob/Weights-and-mask/README.md

And of course, let me know, if you acing any issues, or want comment about anything.

Edit:
Side note, but does anyone knows, how to add inspector attributes to a buffer authoring? Just like I did with component authoring.

[Antypodish]

Editor Mode Gizmos Debugging

I have improved in Editor mode, debugging tools, using gizmos.
And added some additional explanations, regarding mask and weights in the inspector.

When node is selected in editor mode, it will display path node range (green wired sphere).
If range is negative (sphere is small), every node will be tested on the same elevation.
Otherwise, nodes within a range on same elevation will be checked.
Target nodes render white wired gizmos.
Rays link from source to target nodes are purple and always reach target node.
Cyan ray links are from target to source. Their length is distance, or range (if smaller than distance) to source node.

Atm different debugging links and gizmos are not functional in edit mode, for changing elevation.
Collision are also not tested in edit mode, to validate path.

Updated repo,

~~ (Weights and Mask) ~~
Separate branch

Antypodish/Unity_DOTS_NodePathFinding/blob/Weights-and-mask/README.md