Xenonauts A.I. - Clustering
One of the problems presented with Xenonauts is that the A.I. needs to construct squads of units ad-hoc. Besides the obvious examples where squads may split up or merge up to perform a task, we have the case where we do not want to define squads in the level definition. The A.I. should just be given a list of units, and deal with how squads are defined itself.
Why deal with squads in the A.I, why deal with this extra problem?
Why not just command units directly and emulate the squad behavior without defining them explicitely?
One big benefit we get is that defining squads will give us another layer of abstraction. More importantly, it will give another layer on which we can filter for actions which will allows us reduce the space complexity of the search problem for our planner.
Now, how would we define a squad?
- A squad ideally consists of around 2-3 units.
- A squad consists of an ideal combination of units
- These units are, at most, some maximum distance from each other.
So, the problem becomes that we need an algorithm that will give us a list of squads, given a list of units.
One technique we can use for this is a clustering approach, more precisely agglomerative clustering.
Hierarchical Clustering, courtesy Wikipedia
Agglomerative clustering starts with N clusters, and each iteration merges all clusters which best match some criteria together. This continues until you have a single cluster left.
We can easily adapt this to our problem by altering the base problem in the following ways:
- We start with N clusters, with each cluster representing a single unit.
- We will stop when there are no more clusters left to merge.
- Two cluster may be merged if and only if:
- The merged clusters score doesn’t exceed some threshold.
- The distance function between them is below some threshold.
- The resulting merged cluster is the best merge, in terms of score.
The score function will allow us to restrict the size of the clusters and is defined as a function which gives back a score, given a squad of units.
By choosing to use a score instead of just using the unit count, we can influence which units get assigned to which squad.
If we were to define this score to be 1.0 for each unit, the result would be that we limit the amount of units in a squad.
But we could also give certain types of units a higher score; or combinations of units a higher score. This would result in squads being formed of units who “prefer” each other.
The distance function will allow us to define the boundary on which we will merge clusters. Normally this function influences the resulting clusters the most, but in our case, the scoring function will serve this purpose. For now we will use the maximal distance between the clusters as our distance function, as it serves the purpose of keeping our squad together best.
That’s it for theory, join us in part 2 where I present the implementation and the results.
P.S.
To be exact, from an algorithmic perspective, the score function and distance function are actually one.
I.e. only a single function is used to score the merge; which is just the combination of the score and distance function.
However, for illustration, I separated both functions.
Feature image courtesy of ShackTac Platoon
