# Large Armies fight : Looping through a million elements

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.

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 ?

• I'm not super familiar with Ogame or Travian, but as long as the results don't have to be real time (60 fps or more) then millions of units shouldn't be a problem as long as you're doing simple calculations and are keeping your cpu cache in mind. Use structs over classes, and arrays of dictionaries, prefer iterations over random accesses. Look into the Unity JOBS system. As long as you do these things, and these calculations aren't performed on a per frame basis in a real-time environment, performance shouldn't ever become an issue. Mar 27, 2022 at 21:11
• Thanks. I'll look into that !
– Alta
Mar 27, 2022 at 22:04
• You even have more time considering that an army of millions in units would not be defeated in one frame. If you need more time, you could start the dmg result calculations as well shortly before the army arrives (ogame had quite some travel time) Mar 28, 2022 at 8:35
• I won't have long travel time like Ogame. In fact I won't have travel time at all. Unless I really need to make something like a fake 10s or 1m time for calculation purpose.bjt otherwise, I can always have a 1 or 2s animation that makes the illusion;)
– Alta
Mar 28, 2022 at 14:37
• Point to consider: Matching every unit to an enemy provides very different results from summing the stats - e.g. if army A has 100 "goblins" (damage: 2, hp: 1 each), and army B has 2 "knights" (damage: 10, hp:100) - summing the stats gives A: (damage: 200, hp: 100) and B: (damage: 20, hp: 200). In this case A will win in one round with 20 casualties, but if instead you match every goblin to one of the knights, then each knight will get to attack 50 goblins before losing, so now side A will have 100 casualties and the fight is a draw. So try out some combinations to see what suits your game. Mar 28, 2022 at 16:50

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.

• Thanks for the answer. I'm not trying to make things real time. Even a 1s calculation would be fine (I can always have an animation somewhere for 1 or 2 sec in the meantime)... But as you said for yourself, I like to be efficient too ;)
– Alta
Mar 28, 2022 at 14:34
• I've read something here about the composite pattern model, and I'm willing to try to implement something like that. In the first place because I never did it and like the challenge. And also because it could bring interesting results. Thanks for the suggestion!!
– Alta
Mar 28, 2022 at 14:36
• One quick question about that though. Very technical. Do I have to create a class or something for every level (squad, platoon, battalion, etc). Or can I kind of "dynamically" create an object that kind of encapsulate the lower ones, and stop when it can't anymore ? Not sure if I'm very clear here.
– Alta
Mar 28, 2022 at 14:40
• That would probably depend on your choice of language, but I don't know for sure. I'm actually not a game developer, and I only know Haskell, C, and a bit of COBOL, none of which are OO. :) I answered from what I know about batch processing large collections of discreet items. You could try something like a ring that, when it gets to a certain size, splits into two or more smaller rings associated with the original ring. I hope I'm being clear here. So you have a "level 0" ring, and once it reaches, say, 100 items, it creates two "smaller" rings of 50 items each and tracks those instead. Apr 11, 2022 at 22:09