SHOUTING LOUDLY

OK, clustering is unnecessary for now; it's pretty easy to propagate information at the speed of sound without the need for artificial groups of actors. Here follows a video of the normal 16,000-actor gorefest, combined with an argument about which random colour best matches the rusty iron of a 5-decade-old pitchfork.

The main problem here is that the competitive nature of "ideas" in this setup and the actors' undiminished sensitivity to old ideas makes it pretty difficult for new ideas to take hold in large, densely packed groups. I'll keep in mind the need to overcome this issue when I modify the system to convey useful information.

Things I should be able to accomplish just using shouting:

1. Sharing visual information
2. Relaying orders
3. Detecting when a group is surrounded
4. Facing outwards to counter flank/rear attacks
5. Getting into box formation
6. Moving in box formation
7. Morale, giving up, tactically withdrawing
8. Probably more

Getting the shouting system to do these things is my next priority. After that I'll probably add some depth to the combat system, which at the moment consists of "if you hit, you have a one-in-four chance to kill".

Excess

Am I worried that this is overly ambitious?

No. I did a 14DRL, a 7DRL, then made a 1DRLL out of the 7DRL, and now I'm getting tired of projects with excessively limited time and scope. ASCII graphics and lack of economic system take out a lot of the work that would be required for a typical strategy game, and I just checked that Shogun 2 can handle 14,100 people at 4x speed (with animated 3d graphics and occlusion culling and experience tracking for everyone, though not with a capable AI), so there's no doubt that doing all the stuff I want to do in a game second 4 times per real second is possible, at least on two cores. I won't be bothered if single-core users have to make to with just 2 game seconds per second. Boo hoo.

What do I definitely not want to do?

Some people might have thought I had gone crazy and wanted a procedurally generated plot with procedurally generated characters and relationships and socio-economic modelling and a few years worth of coding a plot generator. Actually someone *did* think that.

Definitely not. The overall plot, which would only be strictly relevant at the start and end of the game, would be constant. Ideally I'd have around 15 "types" of battle, each with an introductory/closing snippet of prewritten prose and procedurally generated maps/enemy forces. Of these, something like 8 would appear in a given game, preceded by the opening bloodbath (which would need some heavy narrative) and followed by the climactic whatever-the-win-condition-is that the player does at the end (also narrative-heavy). This wouldn't be difficult at all, with a writer on board to do the prose, and would produce around 260 million possible sequences. Between battles would be a summary of what was lost/gained in the battle, the group/equipment assignment interface (see Intentions), and not much else. Some kind of choice about where to go (probably not free movement) on a world map might not hurt but would be nonessential.

Quests, side-quests, side-anything: nope. Considering the total absence of reinforcements and friendly faces, there's no-one to give you quests, and there's no reason to go way off course and lose 5% of the army rescuing a kitten from barbarian wolf-riders. Not unless you're desperate for mounts.

Next time: either the procrastination-born macguffin plot that's just about coherent enough to excuse the intended gameplay, or the local shouting system that probably makes clusters unnecessary.

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.

Intentions

These are the things that Command (or whatever it ends up being called) will have when I consider it complete.

1. A sequence of battles on a Total War scale, and a player character commanding one side.
2. Player's sight limited to their own field of vision, and not including their soldiers' vision.
3. Player's ability to command limited to earshot (and nearby combat noise).
4. Individually and reasonably intelligently acting troops who can take the initiative.
5. Mounts, probably multi-tile, including at least horses, possibly elephants. Maybe some more unusual real-world ones. Perhaps non-flying dragons, if the plot is fantasy enough to allow them and if the lore/game mechanics can allow them to be captured from the enemy and work for the player.
6. Player initially commanding a very large force of people with no battle experience and no relevant equipment, who must learn to fight and scavenge equipment/mounts from fallen enemies.
7. No possibility of reinforcement between battles (at least not nearly enough to replace losses).
8. A variety of battlefields and circumstances: fields, hills, forests, buildings; attacking or defending a position; ambushes; storming a castle for the final battle.
9. Difficulty. Losing any one of the battles should be a possibility, winning the first few battles shouldn't require complete mastery, getting to the final battle and winning the game should require a great deal of skill.
10. A plot, preferably with randomised elements, quite possibly excluding fantasy elements, which allows for all this. I don't plan to write this plot.
11. As little micromanagement as possible, despite the individual nature of the troops and their skills/equipment.
1. It must be possible to direct commands at groups of units, refer to groups of enemies in orders, and to divide/merge/reshuffle groups according to need during the battle.
2. During the assignment of equipment, it must be possible to assign groups/equipment/mounts based on groups, troops' skills, etc. For instance: giving all the horses to the most skilled of the current sword wielders and making a new group from the new horse riders, then dividing the heavy armour equally between the group of axe wielders and the new horse riders.
3. Doing this should be trivially easy and not require any dealings with individual troops. This will require some careful interface design.
12. Since much of the battlefield might be out of sight of the player, messengers should go to the player with status reports if/when appropriate.
13. The whole thing should run at 2-4 game seconds per second at the minimum on a reasonable computer (someone said they had a single-core 1.8GHz machine, so I'm aiming for that).

What does the game currently do?

1. Runs at over 15 game seconds per second at 2.6 GHz, with 8000 troops per side. Obviously this will go down as the individual actor AI becomes more complex, and as battle calculations become more involved. Because of the stipulation that there are no reinforcements, it will take a large number of troops in the first battle to make victory attainable in the final one. So, ensuring good performance with large numbers is essential.
2. Troops walk around friendly troops.
3. Troops kill enemy troops.
4. Dead troops leave bloodstains.
5. Not much else.

What would be nice features that would add to the game but don't necessarily have to be in the complete game?

1. People with appropriate skills automatically fixing damaged equipment after combat.
2. Very small quantities of random reinforcements, or caches of weapons and armour, or stables of horses found between battles, if the plot allows.
3. Lieutenants who can give reasonably sensible commands while the player is too far away to do so. The enemy should probably have these anyway.
4. Some kind of decision from the player about where to go for the next battle, perhaps something along the lines of the travel map in The Last Stand 2 (minus the supplies and the day counts).

What am I working on/thinking about right now?

Dynamic clustering, vision, and hearing. While all this stuff about troops behaving/thinking individually is all very nice, making every single troop look over the whole map to find enemies and making every soldier process every sound by themself is completely infeasible.

The solution is to have them form into communication groups (not the command groups the player will be assigning later, which could get spread out too much), which are formed and bounded by distance from their centre of mass (anyone too far from the centre gets thrown out of the group).

These groups can ration the use of their eyes so that every group on the map gets a chance to look for enemies, and can simulate the spread of information between nearby comrades... by simply making the group's information available to every member of the group (maybe with some delay for realism/performance. Maybe not). So if one group member sees a thing or hears a sound, all of them see/hear it.

I'll need to find a sensible method of inter-group communication too, and make sure that the way group members deal with nearby directional cues in a way that will allow them to make non-stupid decisions in situations such as being surrounded, or being on the flank of an enemy group but having a group centre further back on the front line.

No screenshot today, you got your nice screenshot last time.