Custom Clustering Algorithm Defining Deadly Areas For NPC in Unreal Engine Game

In this post I will demonstrate my custom implementation of a clustering algorithm in Unreal Engine C++.

I used this clustering in my game to determine the deadly areas for NPC to enhance its AI so that NPC could avoid or consider these areas in some other way (e.g. proactively attack the area in a preventive manner or be ready for the ambush in such areas area). You can read this article for more details.

In other words, during a game, NPC can be killed in some areas more often than in others. This makes dangerous areas for NPC. As a game progresses NPC should learn and consider such areas in their behavior.

This article does not present NPC reaction or behavior regarding such dangerous areas (clusters). This article focuses on clustering method and implementation in Unreal Engine C++.

 

Clustering visualization

Here is a video with a test level in Unreal Engine that visualizes the clustering progress as new cluster entries are added. Note that this is a visualization of the clustering functionality only, it is not not the in-game implementation of the clustering.

The visualization is focusing on clustering in 2D (on a plain surface), although the clustering model works in 3D as well (e.g. on slopes or on a wall, or in the 3D space in general).

 

My custom clustering method overview

There is a number of well-documented clustering models, but in each practical case the implementation may be custom because of specific requirements and local constraints.

My custom clustering method combines elements of centroid-based and density-based approaches, operating in 3D space. Unlike traditional methods, it doesn’t require a pre-defined number of clusters. Instead, it uses a fixed cluster shape and size – specifically, spheres with a predefined radius.

Here goes a description for this clustering implementation in the context of my game.

 

Some key definitions for the custom clustering

• Cluster Entry – an element of a cluster which represent NPC’s death location (the location where NPC was killed).
• Cluster Candidate – an element before it is assigned to a cluster
• Cluster – a set of cluster entries united by cluster rules (see below). A cluster can be visually represented as a round-shaped (technically, sphere-shaped) figure with a pre-define radius. In the game context this is a volume (or simply, area) that represent a dangerous area for NPC. The more deaths are in the area the more powerful the cluster is (i.e.e the more dangerous this area is).

 

Cluster and cluster entry rules

• Cluster is defined by center and radius.
• Cluster center is the mean location of the cluster location entries.
• Cluster must contain at least one cluster entry. A cluster without cluster entries is eliminated.
• Number of clusters and their locations is not pre-defined, it can change depending on the number and location of the included cluster entries.
• A cluster candidate is assigned to the cluster in which radius the candidate falls into. And if there are multiple clusters satisfy this condition, then the candidate is assigned to the most powerful (dangerous) cluster. Function that determines how powerful (dangerous) a cluster is resembles gravity force (i.e. the more cluster entries are in the cluster, the more powerful the cluster is; and the closer a cluster entry to the cluster center the more chances the cluster entry will be assigned to this cluster).
• During assignment of a cluster entry into a cluster, the cluster properties change: the location and its gravity. Since the radius of any cluster is pre-defined, it may result into releasing (setting free) some cluster entries. These released cluster entries must be assigned to other cluster(s) or form new cluster(s). These changes have recursive nature.
• A Cluster fully located inside another cluster (child cluster inside parent cluster) is not allowed. Child cluster entries must be assigned to the parent cluster or new clusters should be formed so that no child clusters are left. These changes are also recursive in their nature because it causes a chain of re-assignements of cluster entries and creating new clusters or elimination of existing clusters.

 

Handling challenges

A key challenge in my case was managing the recursive nature of the changes that occur when adding new NPC death locations (cluster entries candidates). It may trigger a chain reaction of cluster modifications described above.

Also, to prevent potentially deep recursive cascades, I simply added a recursion limiter with a reasonable threshold (MaxRecursionDepth) that I set to 100. By the way, random testing revealed for my game context that the recursion depth has been always below four.

Besides, theoretically, even in case of deeper recursion, my game does not require a super high precision of clustering (after several iterations the changes are expected to be negligible). So the recursion limiter is a valid approach in this case even if to assume that the recursion depth could ever exceed the large MaxRecursionDepth value.

 

C++ code for clustering subsystem

You can find the repository here. The main class responsible for clustering is UMBCG_AttackClusteringSubsystem (See MBCG_AttackClusteringSubsystem.h).

 

Integration of clustering subsystem into the game

As mentioned above, clustering subsystem is integrated into a game to affect the NPC behavior as NPC gets killed. NPC behavior changes as Navigation Mesh is modified according to the clustering results.

Here is how it is done:

• UMBCG_NPCAmbushAvaisionComponent class (UPawnComponent) expands LyraCharacter (NPC). It allows to listen to NPC health changes (Death) and calls UMBCG_NPCAmbushAvaisionSubsystem‘s methods which use the UMBCG_AttackClusteringSubsystem (clustering subsystem) and UMBCG_NavSubsystem (the subsystem that modifies navigation mesh). See MBCG_NPCAmbushAvaisionComponent.h.
• UMBCG_NPCAmbushAvaisionSubsystem class is a mediator class that organizes communication between NPC and the subsystems responsible for NPC behavior in context of avoiding deadly zones (ambushes). See MBCG_NPCAmbushAvaisionSubsystem.h.

• UMBCG_AttackClusteringSubsystem class is a clustering subsystem that is explained in this article above. See MBCG_AttackClusteringSubsystem.h.
• UMBCG_NavSubsystem class is a subsystem responsible for NavMesh modification. See MBCG_NavSubsystem.h. Also, I’ve got a post about this subsystem here.

 

Simple example of using Clustering Subsystem in blueprints

The main purpose of the clustering I use in my game is in-game modification of the navigation mesh which affects NPC’s behavior (I mentioned it in the beginning of the article).

Apart from that, the video that I posted in this article above demonstrates clustering visualization. I used a UE blueprint for this clustering demonstration. There I call UMBCG_NPCAmbushAvaisionSubsystem::RegisterNewAttack function which is also called in my game when NPC gets killed.

RegisterNewAttack function calls the clustering subsystem’s functionality of adding a new cluster entry (UMBCG_AttackClusteringSubsystem::RegisterNewClusterEntry).