Large Armies fight : Looping through a million elements

Question

I'm currently developing my first game. I had the idea to do something similar to the old browser games like Ogame, Travian, etc (with some differences though), and I'm kind of unsure about how to calculate the output of two armies fighting. There are for now no multiplayer aspect in the game, but that's something I would like to do in the future, si I'd like to plan with that in mind, if possible.

Each unit has an attack, HP and armor value. The armor is regenerated between each round (in my idea). There are different unit types, with strength/weaknesses against other units.

I had two ideas about how I could calculate the outcome of a fight :

1. Loop through each unit

In this scenario, I would basically loop through two dictionary<Unit, Int[]>) where each int[] would be the HP remaining on each single unit. One dictionary per army.

I would assign a random target to each unit, apply the modifiers (either a simple attacker multiplier or a chance to hit a new target depending on a value), and store back the HP values.

Rinse and repeat for either a fixed number of rounds or until one army is out.

I love the idea behind this solution, but I'm afraid it could take too much time to loop through big numbers of units. At some points, armies could reach over 1M units (not more than 10M though I think), and even though my operations inside the loop are quite simple, I'm a bit afraid of performance issues, especially with multiplayer in mind.

2. Have a global value

In this scenario, I would just calculate the total Atk/Armor/HP of each unit type, spread the attack value amongst ennemy army (if I have 100 units attacking 50 units of type 1 and 50 units of type 2, half of the damage would be applied to each ennemy), apply my damage multipliers, and get a global remaining HP for each unit type. Then I would divide by an individual unit HP to display the remaining units number. Rinse and Repeat.

This solution is obviously much faster, as I have at max to loop through 4 to 6 different unit type. The issue would be when dealing with smaller amounts of units, I did some tests and I didn't like the results. Also I'm not too sure about how to implement a bit of RNG in this system.

3. A mix of both ?

I had other ideas such as dividing the army in groups of units (let's say an army is always divided in 100 groups), and then apply method 1 to each group. Then I would have some RNG still, but each group would have its global HP. You could then never lose an amount of units smaller than a group.

I'm not too sure about this one :/

My main concern overall is about the method 1 and the possible performance issues. Do you think it's doable to loop through arrays containing millions of values or is it just stupid performance wise ? Any other idea ?

Thanks in advance !

Answer 1

Before I begin, I apologize if it seems like I'm breaking this down Barney-style; I do so for the benefit of other readers, and I promise I mean no offense.

I would say go with option 3; the reason is that armies are, in fact, divided into smaller groups to deal with a similar problem, which is that managing 1M units all at once is a right pain in the bum. You could even take this further by mimicking reality and having multiple levels of units, and then you can defer certain processing until later.

Let's suppose that you have an army of 100,000 units, each unit having an attack, HP, armor, etc. Well first, let's combine them into small squads, let's say 10 units per squad, so now instead of dealing with 100,000 objects directly, on the surface-level we're only dealing with 10,000. Each squad now has the sum of each of the attributes of its individual units. When a squad takes a hit, the damage is applied to the squad immediately, but not to any individual units within until later when that information is actually needed (at the end of the battle, for instance). Your RNG could be applied at this time to apply damage to individual units, for example in a "damage pool" where the RNG chooses how much to take out of the pool and apply to an individual unit (or subgroup).

Now let's take those 10,000 squads and organize them further. We'll organize them into platoons(?) and we'll say 10 squads per platoon. Now we're only dealing with 1,000 objects, and we can apply the same methods even faster. Extrapolate this concept until you reach your top-level unit; what you can do then, is track how much damage each army is taking at the top level and only apply damage processing to subgroups when needed, and then you're only applying it to a subset of the army rather than having to process the entire army at once.

Another option is to account for the notion of space. If you have two massive armies fighting on a field, "Total War" style, more than likely only a very small subset of those units are going to be actively fighting and taking damage because only the units at the very front are able to reach the enemy. You could determine how "wide" an army is, and then in general you only need to process for the frontline units, not necessarily everyone else.

Like others have said, it may be a moot point because you're not trying to do things in real time; but personally I like to be efficient, so I know I would go to the effort regardless, and I hope my answer helps you to this end.