1
\$\begingroup\$

I'm working on a battle algorithm for a text-based game and I stumble when it comes to randomly distributing attacks on a set of units.

E.G, 100 archers shoot 100 targets at the same time. I thought of doing like this :

  1. The 100 targets are considered as a single block
  2. The arrows are distributed inside
  3. The units hit the same number of times are grouped together.
  4. I manage the life of each new group
  5. Repeat on each new group if necessary

I can distribute the arrows (step 2) and get the result (step 3) through a loop, but with many armies composed of millions archers, computing time & memory consumption becomes a problem.

// Step 2
const targets = new Array( 1000000000 ); 
targets.fill( 0, 0, 1000000000 );
const arrows = 1000000000;
for( let i = 0; i < arrows; i++ ){  
    const index = Math.floor( ( Math.random() * arrows ) );  
    targets[ index ] += 1  
}
//Step 3
const result = []
targets.forEach( value => {
    if( value ){
        if( result[ value ] ) result[ value ] += 1
        else result[ value ] = 1
    }
} )

Is there another way to solve this problem ? I believe that with large numbers, directly calculating the most likely scenario may be a good option. Unfortunately, I do not know anything about probabilities.

\$\endgroup\$
  • \$\begingroup\$ Are the enemies in units? Like 100 soldiers gathered into one attackable unit? Attacked by a unit of 100 archers? Or are there 100 Soldiers, each an own entity with own health and indipendent Movement from the rest of the soldiers? \$\endgroup\$ – PSquall Sep 17 '18 at 10:59
  • \$\begingroup\$ Ideally, each soldier is an independent entity with his own life. To make calculations easier, I wanted to do like this: 1. First, the 100 soldiers are considered as a single block. 2. Then, the arrows are distributed inside. 3. Which give X blocks of units hit X times. 4. Finally, I manage the life of the units. It would take a way to get the result of step 3 without using a loop. \$\endgroup\$ – Stubbs Sep 17 '18 at 11:29
  • 1
    \$\begingroup\$ @Stubbs Welcome to game dev stack exchange. It's not clear to me why this wouldn't scale to a million. How are you looping & how are often are you running these calculations? Are you allowing each archer to make an random attack against each target? Consider including some pseudocode. \$\endgroup\$ – Pikalek Sep 17 '18 at 13:55
  • \$\begingroup\$ Millions of archers? If you draw millions of archers shooting 1 arrow, on a different direction, and calculate its curve, its already resource-intensive. I don't see how the random distribution would affect computing time by itself. \$\endgroup\$ – TomTsagk Sep 17 '18 at 14:30
  • \$\begingroup\$ @Pikalek Thanks. For a text-based game, I would like to use very large numbers and that the game instantly responds to player inputs. A million was an example, it can also be ten billion or more. It's exactly that. Naively and in JS, it could give this : const array = new Array( 100 ); array.fill( 0, 0, 100 ); let i; for( i = 0; i < 100; i++ ){ const index = Math.floor( ( Math.random() * 100 ) array[ index ] += 1 } \$\endgroup\$ – Stubbs Sep 17 '18 at 14:45
1
\$\begingroup\$

You need to set each archer with a random target. You could set it to any of the enemies but it would probably work better if they can only see a number of them. For the sake of simplicity, I'm going to use 10, not 100.

Archers:
0123456789

0123456789
Enemies:

Now, let's say each archer can only reach the enemy in front of him and two either side for his range so archer 0 can hit enemy 0, 1 and 2. Archer 1, can hit 0, 1, 2, 3. Archer 2 can hit 0, 1, 2, 3, 4 and so on until archer 9 who can only hit enemies 7, 8, 9.

Looping each archer, choose a random enemy then move onto the next archer to do the same.

Personally speaking, I'd also loop all archers before they fire which will add a bit of realism to the game by making some archers aim for enemies who are already dead by the time their arrow gets to their individual target.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer ! The problem is that I really wish that the distribution of the arrows are in gaussian curve. For the second proposal, it's a good idea, I was going to do that :) \$\endgroup\$ – Stubbs Sep 17 '18 at 15:13
  • \$\begingroup\$ @Stubbs because you're adding up the effects of many independent arrow shots, the probability distribution of damage to a single target will naturally approach a Gaussian distribution. Just like how, when you move from summing two dice, to three dice, to four, the distribution gets more bell-shaped: here, each arrow is a die with many zero sides and a single one (from the perspective of any one target unit) and you're rolling gobs of them. So their sum will converge toward a Gaussian distribution "for free" without needing to bake that into each individual roll. \$\endgroup\$ – DMGregory Sep 17 '18 at 15:39
  • \$\begingroup\$ @DMGregory Thanks for the explanation. So, Stephen's proposal is valid. Remains to solve the problem of computing time. \$\endgroup\$ – Stubbs Sep 17 '18 at 16:03
  • \$\begingroup\$ @Stubbs is that a problem? I just fired a million arrows at a million targets in ~80 ms on a mid-range tablet, without any optimization at all. We can cut that in half if we limit the range of randomization to improve locality. Too slow for a realtime 3D game, but still practically instant for a text-based game. \$\endgroup\$ – DMGregory Sep 17 '18 at 16:34
  • \$\begingroup\$ @DMGregory Yes, but with a billion it's not the same story. These are stupid numbers, that's for sure, but that's what I need. \$\endgroup\$ – Stubbs Sep 17 '18 at 18:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.