Horde Pathfinding in Constant Time

Overview - 

The objective of this technique is to use a pathfinding algorithm to calculate the path of n number of entities in constant time. Normally, navigation on one entity would use an A* pathfinding algorithm to compute a path through an environment. However, trying to calculate the path through an environment described as a very large node map for a very large number of entities would be very inefficient and will cause a significant amount of lag. Since it would be impractical to try and reduce the time complexity of the A* algorithm based on map size, the only other way to reduce time complexity would be to create a method which can calculate the path of entities in constant time in relation to the number of entities. We can do this in a number of ways including a leader and follower strategy, calling the pathfinding algorithm for one entity per frame, or, much more effectively, employing a spatial partitioning scheme.

Important Information -

The entities will move using the Unity Physics Engine.  This means that no entries can overlap, entities move by adding a force in a direction, and entities must fit within a section of available space (ie if each entity takes 1m cubed of space, at most 1000 entities will be able to fit within a 1- by 10 by 10 cubic meter space)

Leader / Follower - 

Essentially, the leader/follower strategy works by creating a leader that will run a standard A* algorithm to navigate, then have each follower simply travel towards the leader. The leader/follower strategy initially sounds like an appealing choice. Since each leader could have an indefinite number of followers comprising the horde, you could ostensibly use this strategy to navigate in practically constant time per entity. I say practically because one leader could be the leader for the entire horde, however, if one wants multiple hordes, the time complexity would be O(n) where n is the number of leaders. Also, all entities would have to be part of a horde and no entities would be able to stray from the leader. This creates very predictable movement patterns which are very boring. The nail in the coffin for this strategy, though, is the distance problem. If a horde has a large amount of followers, say 15,000, the followers will undoubtedly take up a lot of space. If the horde reaches a corner, the leader will take the corner and be followed by the followers near the leader, however followers farther back will begin to run into the wall as they try to move towards the leader. This will segment the horde and the leader will leave the majority behind. Creating a strategy to assign a leader to a horde of lost followers would not be a good idea either since that defeats the purpose of the strategy (navigation in constant time), and due to how common this event is to happen, the reassignment of a new leader will occur very frequently. 

Per Frame Pathfinding -

There is nothing outright wrong with this strategy, it just is not very effective by itself. Since the pathfinding happens only once per frame on one entity per frame, the time complexity is constant. For only 120 entities, assuming the game is running at around 60 fps, the path of each entity will be generated once every two seconds. If we have 12,000 though, the path of each entity will be computed every 200 seconds. Since the target is constantly changing position, a path from 200 seconds ago will be far from valid as it will almost certainly no longer point directly to the target. This strategy is a good choice, but it must be combined with another strategy to work well, preferably, one with a low number of paths to compute per frame. 

Spacial Partitioned Pathfinding - 

This technique is a clear winner. It works like this:

1. Separate the node map into square sections.
2. Each frame, check the number of sections which contain entities. 
3. Add those sections to a stack.
4. Each frame calculates the path from the center of the first section on the stack to the target.
1. If the first section no longer contains entities pop and repeat step 4
5. Apply that path to all entities in the section. 
6. Pop the stack and repeat from step 2.

The node map can be broken down into sections at the minimum possible resolution which varies depending on the detail of the movement and environment. This number, in the case I applied it to, was low enough to be able to also implement the per frame pathinding. This strategy has none of the problems of the leader/follower strategy, and a lot more benefits. Firstly, since the navigation happens per section, sections can be given special tags that can denote things such as: This section creates a path to an adjacent section, or this section applies a speed decrease to the entities within it. It enables individual entities to navigate from anywhere on the map while simultaneously allowing hundreds of entities to navigate in unison. There are limitations with this technique though. So that each entity’s section can be found in linear time in relation to the number of sections, the sections must be uniformly rectangular. Imaging a circular room with walls of infinitely thin walls. In this case, no matter the size of the sections, in order to fully cover the room with sections, there must be overlap on the interior space of the room along its edges and the exterior space of the room. Therefore an entity hugging the wall of the room may be classified as if it was within the room, causing a pathfinding error. With small enough sections in practice this is no problem, but when we want to use the minimum number of sections this problem will thwart our plans. Also there are cases where strange geometry of the environment will cause the entities to become stuck on objects while trying to navigate in the path which is directed starting at the center of the section.

Further Research - 

One way to overcome the problems facing my technique is to create a spatial partitioning scheme using triangles of varying sizes instead of uniform rectangles. This means we will be able to handle curved geometry better, but we can also vary the resolution of the sectional map as we please. The primary problem with this non uniform partitioning is as follows. We will no longer, to my knowledge, be able to find which section an entity occupies in constant time. To combat this, we could implement a volumetric bounding hierarchy of the squares encompassing different sections of triangular sections so we can narrow down our list of triangles to check. I would be interested in trying to build an algorithm to procedurally place and bound these triangular sections of varying sizes to match the geometric complexity of the environment, however this sounds like a daunting task.