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\$
10
  • \$\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, 2018 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, 2018 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, 2018 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\$ Sep 17, 2018 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, 2018 at 14:45

1 Answer 1

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\$
11
  • \$\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .