CodePoke
Propogating Knowledge Engineering
  • facebook
  • twitter
  • Home
  • Games
  • Supported Projects
  • Blog
Select Page ...

Blog

Xenonauts A.I. - Clustering

Gijs-Jan May 7, 2013 AI No Comments

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

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:

  1. We start with N clusters, with each cluster representing a single unit.
  2. We will stop when there are no more clusters left to merge.
  3. Two cluster may be merged if and only if:
    1. The merged clusters score doesn’t exceed some threshold.
    2. The distance function between them is below some threshold.
    3. 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 

← Promoting your App: Flurry Review
Tips ‘n Tricks – Debugging LibGDX & Artemis in Eclipse →
Gijs-Jan

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  • Categories

  • Archives

    • March 2015
    • November 2014
    • September 2014
    • May 2013
    • August 2012
    • June 2012
    • December 2011
    • October 2011
    • September 2011
    • August 2011
    • September 2010
    • August 2010
    • July 2010
    • June 2010
  • Copyright © 2016 CodePoKE.net. All Rights Reserved