Add flocking to navigation package

[0x6c23]

Is the improvement related to a problem? Please describe.

I am trying to implement avoidance mechanics based on the current ECS-Sample repo by unity. However, I am not very successful. Agents either just drift away or stay on one position.

Describe the solution you'd prefer:

A flocking algorithm. I would like to implement enemy hordes which follow a target but avoid each other. They should continously aim to follow a target but once they bump into each other they should steer away from each other. This could be expanded to maybe play animations when they bump into each other.

Describe what you have tried:

I basically took the example from unity and modified it. I created a new hybrid agent type (NavAgentEnemy) and modified the example accordingly. Initial Jobs:

        `var initialCellAlignmentJobHandle = Entities
            .WithAll<NavEnemy>()
            .WithName("InitialCellAlignmentJob")
            .ForEach((int entityInQueryIndex, in LocalToWorld localToWorld) =>
            {
                cellAlignment[entityInQueryIndex] = localToWorld.Forward;
            })
            .ScheduleParallel(Dependency);

        var initialCellSeparationJobHandle = Entities
            .WithAll<NavEnemy>()
            .WithName("InitialCellSeparationJob")
            .ForEach((int entityInQueryIndex, in LocalToWorld localToWorld) =>
            {
                cellSeparation[entityInQueryIndex] = localToWorld.Position;
            })
            .ScheduleParallel(Dependency);

        var copyTargetPositionsJobHandle = Entities
            .WithName("CopyTargetPositionsJob")
            .WithNone<NavEnemy>()
            .WithAll<NavAgent>()
            .WithStoreEntityQueryInField(ref m_TargetQuery)
            .ForEach((int entityInQueryIndex, in LocalToWorld localToWorld) =>
            {
                copyTargetPositions[entityInQueryIndex] = localToWorld.Position;
            })
            .ScheduleParallel(Dependency);

        var copyObstaclePositionsJobHandle = Entities
            .WithName("CopyObstaclePositionsJob")
            .WithAll<EntityObstacle>()
            .WithStoreEntityQueryInField(ref m_ObstacleQuery)
            .ForEach((int entityInQueryIndex, in LocalToWorld localToWorld) =>
            {
                copyObstaclePositions[entityInQueryIndex] = localToWorld.Position;
            })
            .ScheduleParallel(Dependency);`

In the steer job the calculation basically remains the same I just used

var localToWorldFromEntity = GetComponentDataFromEntity<LocalToWorld>(true);

instead of ref LocalToWorld localToWorld.

The positions/ headings and general values seem to be correct, however I fail to apply it to my agent. I tried

var targetDestination = new float3(entityLocalToWorld.Position + (nextHeading * 6 * deltaTime));

commandBuffer.AddComponent<NavPlanning>(entityInQueryIndex,entity); commandBuffer.AddComponent(entityInQueryIndex, entity, new NavDestination { WorldPoint = targetDestination, Tolerance = 0, CustomLerp = false });

I also tried to set the translation.Value to the targetDestination.

I can not use localToWorldFromEntity[agent.DestinationSurface].Value, since agent.DestinationSurface = Entity.null.

Also setting the translation.Value directly bypasses the nav system so those agents aren't finding valid paths anymore.

If I just add

commandBuffer.AddComponent(entityInQueryIndex, entity, new NavDestination { WorldPoint = nearestTargetPosition, Tolerance = 0, CustomLerp = false });

( nearestTargetPosition is the position (localToWorld.Position) of the nearest player ) the enemies will follow the player. But how can I get them to avoid each other and/ or add different behaviours like cohesion and alignment.

I am new to unity programming and dots especially and would be greatful even for a hint in the right direction.

[reeseschultz]

(I'm assuming you're referring to the boids example.)

With that in mind, I own a book called Artificial Intelligence for Games, 2nd Edition, by Ian Millington and John Funge.

Here's a quote from page 99:

The flocking algorithm relies on blending three simple steering behaviors: move away from boids that are too close (separation), move in the same direction and at the same velocity as the flock (alignment and velocity matching), and move toward the center of mass of the flock (cohesion).

It's relevant, for educational reasons, because I want to stress that this is specifically what flocking means, and furthermore, it's more conceptually palatable than it is technically. In the boids example, neighborhoods are used to cull distant boids. This is the only practical way to achieve flocking as the number of boids scales.

While it is reasonable to lean on Unity's provided example, you should be aware that they're still using IJobNativeMultiHashMapMergedSharedKeyIndices to enforce said neighborhoods, which is deprecated. Copy-pasting that job's implementation for future-proofing may constitute infringement on their licensing terms, which I cannot advise.

Another thing to consider is that, none of the agents in my navigation and pathing packages can match the performance of the boids in Unity's example, because they're defined as ISharedComponentData, whereas mine are IComponentData. I would consider adding boid components specially for flocking, but that requires more thought. The existing agents would still perform subjectively well as they are, but it's something to think about.

Anyway, unfortunately we can't just combine their example with the navigation package. You could try, and it may even work, and I would applaud you, but I wouldn't accept it as a pull request, because I don't want to permit deprecated code, and never anything breaching license terms, in this repository. Reasonably maintainable and performant alternatives, however, I'd gladly accept.

To do "proper" flocking, we need another way to look up entities by neighborhood, then we can worry about steering behaviors. My mind immediately jumps to generating component tags at runtime, representing neighborhoods. Problem solved! Just kidding. Even if that were possible, it would require reflection, which is a big no-no.

That brings me to the NativeMultiHashMap for neighborhood management. It should be possible to use "grid-ified" positions as keys, with entities as values. Then, each key is associated with a so-called flock. The cell size of the grid could even be adjustable in that case.

If I rightly recall, however, modifying the NativeMultiHashMap, for when entities enter or exit a flock, would be tricky. The concurrent flavor of the data structure only supports adding new values, not removing them. So... that's not gonna work.

But all hope is not lost. Why, the UnsafeMultiHashMap's API is promising. It offers this function: Remove<TValueEQ>(TKey, TValueEQ).

According to Unity's docs, that function:

Removes all elements with the specified key and value from the container.

So, looks like some code will need to be wrapped in an unsafe block for this to work. What a surprise :upside_down_face:. So that's where we're at, using a data structure, for which the compiler cannot guarantee safety, to do neighborhood lookup for flocks (in theory, I don't know for a fact that this is tractable, but it appears to be). Given the conclusions I've reached, I'd consider implementing flocking, but I cannot say when. There's a game I'm about to consult on that may need this feature, but I'm not sure yet. If it does, I'd try to implement the flocking as an open source feature, and then "proprietarize" it if needed. In the meantime, if someone else is super excited about implementing features that totally suck to implement (and for free lol), please reply and let us know. I anticipate the soothing melody of crickets, but, hey, prove me wrong.

[reeseschultz]

@0x6c23 and anyone else reading, I forgot to mention an alternative, but it's not technically flocking. You may be interested in it.

For those reading who require rudimentary avoidance, you can add colliders to agents.

At present, this strategy won't work with the navigation without some changes to the NavLerpSystem. None of the interpolation is physical (yet), just simple translation. To reconcile collision with interpolation, #43 or something like it needs to be done. I've sat on that issue for a long time, because I know it will be a pain to reconcile with the numerous use cases it will be subjected to.

One could also build a custom, physical interpolation system atop the new pathing package. That may be easier for troubleshooting issues with physics that will likely arise.

Anyway, I hope those options help. I don't want to be unhelpful, but implementing flocking is a big ask, and I have limited time.

[0x6c23]

I have implemented a flocking prototype with waypoints, quadrants & NativeMultiHashMap, whithout using IJobNativeMultiHashMapMergedSharedKeyIndices.

If I rightly recall, however, modifying the NativeMultiHashMap, for when entities enter or exit a flock, would be tricky. The concurrent flavor of the data structure only supports adding new values, not removing them. So... that's not gonna work.

I created a quadrantsystem with a static NativeMultiHashMap which gets cleared & rebuild every update. A flocking system calculates neighbors & steering vectors. A movement system constantly moves to a given point. The point consists of the waypoints (basically navlerpsystem) and added steering values.

It's crude and a prototype but I could issue a pull request or alternatively add some code here for you to implement?

https://user-images.githubusercontent.com/32392595/122689508-55329a00-d223-11eb-8536-c75e9dd42d88.mp4

/E: This time, no waypoints. Just cohesion, alignment, separation and following.

https://user-images.githubusercontent.com/32392595/122691466-1eaf4c00-d230-11eb-94bf-8ca0aa452136.mp4

[reeseschultz]

@0x6c23 this looks great. Thank you so much for considering my concerns about IJobNativeMultiHashMapMergedSharedKeyIndices. Your rebuilding of a static NativeMultiHashMap is clever; I'm intrigued by what the contents of your QuadrantSystem may contain.

If you would like to contribute this code, which I think everyone would greatly appreciate, we can go about it however you're most comfortable. I encourage pull requests because I want contributors to be credited via GitHub, but I would want to credit you in the docs for this feat anyway.

A pull request wouldn't be too bad, because I highly doubt there will be any changes to master in the meantime, so you don't have to worry about keeping up with changes.

Still, as you put in the cognitive effort already, I don't want to pile more work on you either. So if you don't want to do a pull request, I can plug code snippets into the codebase via a new branch, probably feat/flocking, and merge it when ready.

---

Regardless, it sounds like we need to rename the NavLerpSystem to NavMoveSystem, NavSteerSystem, or whatever makes sense to you, because the NavLerpSystem would then only be taking partial responsibility for the total interpolation.

[0x6c23]

Awesome. I am working on it. I have already integrated everything and it's working properly. I will issue the pull request once I cleaned up the code.

[reeseschultz]

Sounds great. I really appreciate that you're doing this. Please let me know if you have any questions in the meantime.

[0x6c23]

Just a sneak peek, 10.000 agents in the terrain demo with cohesion, alignment, separation and avoidance. Still some issues, but so far so good. I get around 50-60 fps, I think it might be around 5 fps less on average. 17-19ms on both.

https://user-images.githubusercontent.com/32392595/122832626-eff6ab80-d2eb-11eb-95e6-ca85cc7e92fd.mp4

[reeseschultz]

Damn! Fantastic, my friend. I also appreciate what you've done with those debug lines. I'm sure @williamtsoi will appreciate the expansion on his terrain contribution.

[0x6c23]

I issued a pull request #70. Please check the code whenever you're available.

I also added a new demo scene in Scenes > Nav > NavFlockingDemo.