Saturday, 5 May 2012

Dynamic Clustering

The centre of mass of a finite number of point masses is easy to calculate, especially when they all have the same mass: sum their position vectors and divide by their number. In a discrete setting we can avoid floating-point operations altogether by simply summing their positions, and remembering that the resulting value is N times the actual value.
This makes dynamically updating the centre of mass of a cluster completely trivial - when an actor in the cluster moves, update the cluster's centre of mass with the same delta as was applied to the actor. Checking if an actor is within R tiles of the centre can be done by multiplying the actor's position and R by N, and comparing to the stored value of the centre as normal.

Before I implement the dynamic updating, I need to figure out how to assign these clusters in the first place. Ideally they should be as large as possible within the constraints of the cluster_join_range constant that I set. Ignoring all the times when I tried to dereference null pointers, here's what happened:

Attempt 1

 I had the foresight early on to place the actors on the battlefield in random order, so if I iterate over the list of actors I get a random sequence of locations in the army. For each actor, check if there's someone adjacent who's in a cluster and try to join their cluster. If that doesn't work, make a new cluster and tell everyone adjacent to join it.
 The result, obviously, was tiny clusters. About 700 are needed to hold all 16,000 actors, or about 23 actors per cluster. Considering the value of cluster_join_radius allows clusters to contain up to 169 actors (yes, my "radius" applies to a square), that's pretty poor.

Attempt 2

Iterate over all the actors 10 times. The first time, after checking for adjacent people with a cluster to be joined, have only a 10% chance to make a new cluster. The second time, 20%, etc.
The result was a big improvement. I won't post it here, but it needed around 470 clusters or so. That's 34 actors per cluster. Still not ideal...

Attempt 3

If a change brings some benefit but not as much as you want, what do you do? Make the numbers bigger. So the first iteration there was a 1 in 40 chance of making a new cluster, and that went up to 14/40 before it jumped to 100%.
This needed about 340 clusters to hold everyone, or 47 actors per cluster. Not bad. But what happens when I let them move before I implement the dynamic joining/exiting of the clusters?

What I should be doing

Reading bioinformatics.


Oh, With the initial cluster assignment? By starting with maximal clusters, of course. Check everyone in a 13x13 square centred on the first listed actor, then the second (if they're not already in a cluster), etc. Much quicker and simpler to draw 169-square boxes around a small number of actors than to iterate over 16000 actors 40 times. Depending on the splitting/merging routines the number of clusters will obviously increase as they advance, but as long as they're sensible this shouldn't be a big problem.


Also, these random colours obviously won't appear in the actual game to let people to complain about bad libtcod colour schemes.

No comments:

Post a Comment