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 1I 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.
Attempt 2Iterate 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 3If 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%.
What I should be doingReading 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.