Group Path Finding

Group pathfinding is a method of grouping NPCs together to avoid increasing the number of pathfinding calls with the increase of NPCs. The problem is split into a few different sections:

  1. Detect obstacles

  2. Group NPCs

  3. Find the path for each group

  4. Move groups in an efficient manner along the computed path

The utility of this method shines when map size and NPC count increases exponentially. This method is ideal for games using hordes of enemies. An example of a good use case is a game with hordes of zombies.

Detection Map

The detection map both finds the obstacles in the map and checks the line of sight of NPCs to see if there is anything in front of them.

The detection map displays green for obstacles, red for NPCs, dark blue for the NPCs’ line of sight, and the light blue is the reflection of the NPCs’ line of sight when colliding with an obstacle, NPC, or another NPC’s line of sight.

NPC Probing Map

The NPC probing map is a form of mean shift clustering with probes starting in a NxN grid and grouping together when they are in range to each other. The last probe any NPC was near is the probe that they are grouped with as well. This results in NPCs being grouped with one of the N-squared probes and then the probes being grouped together to form larger and more reasonable groups.

The black marks are probes, the small colorful marks are NPCs, and the red marks are the center of groups. Probes are at the center of groups when all probes move to one point or there is only one probe. Otherwise, the red center of groups is the average of all probes that are part of the larger group.

Group Heat Map

The group heat map is the heat map showing the influence of groups. This is simply a measure of how far each point is from the nearest group.

NPC Grouping Map

The NPC grouping map shows which group an NPC would be grouped into based on their location on the map. The different colors denote different groups.