Recursive Flow Fields

I have been struggling with moving large numbers of entities through the world. Unity’s NavMesh Agents was great. but not something that could work with abstracted areas. My custom A* system was great at finding the best path through voxels, but was to expensive over long distances for large number of entities.

Enter Flow fields! I cannot say that I had heard of them before and I ran across some great YouTube videos talking about them for RTS path finding and a great article talking about them for roguelikes. The first generation as pretty easy to implement, the flow was based on World Chunks which are 20x20x20 units. Each node in the field was 20 units square and that would get the entity to the chunk of the target.

Wanting to go deeper, I added a recursive sub flow field to each flow field. With that each chunk would have its own flow field that had nodes that were 1 unit square. You could more than two levels with this and have a larger node that was like 200 units square for more abstract movement.

   public Vector3 GetForce(Vector3 position)
   {
        (int x, int y) = GetGridLocFromTransform(position);
        if (hasSubFields && target.x == x && target.y == y)
        {
            return subfields[x, y].GetForce(position);
        }

        return flowField[x, y].direction;
   }

Combining this with some local obstacle avoidance and the entities move pretty well through the world. This could be layered in with NavMesh or my custom A* to suit the needs of the situation.

protected Vector3 LocalAvoidance(int layerMask, float avoidanceRadius)
{
        Vector3 avoidanceVector = Vector3.zero;
        //int nearCount = 0;

        Vector3 position = transform.position;
        var colliders = Physics.OverlapSphere(position, avoidanceRadius, layerMask);
        foreach (var otherEntity in colliders)
        {
            if (otherEntity.gameObject != gameObject)
            {
                Vector3 otherPosition = otherEntity.transform.position;
                otherPosition.y = transform.position.y;
                avoidanceVector += (position - otherPosition);
            }
        }

        return avoidanceVector.normalized;
 }

In the below video I am running at >120 FPS with 128 entities flowing the character. With the Unity NavMesh Agents I was dropping below 60 FPS with around 80 entities and my custom A* was worse.