Given hit probability and number of projectiles, randomly determine number of hits

Question

I'm working on a game where I'd like damage dealt to a target to be randomized, but having troubles working out how to go about it.

N projectiles are fired at a target with probability, p, that each missile will hit the target and damage dealt is based on the number of projectiles that hit.

So, I'd like to randomly generate the number of projectiles that hit. Fractional values would likely be considered as partial hits for this purpose and thus seem acceptable. Specifically, I see say 20.2 hits might some combination of direct hits vs indirect hits that total up to the damage that would come from 20.2 direct hits.

I could simply use the expected value of N*p hits, and fuzz it a bit, but that seems rather less than ideal. I could also simply do the hit calculations for each projectile, but the number of projectiles could be upwards of millions or more, so it would be rather inefficient.

I know how to compute the probabilities of a success after N tires, and R successes after N tries. I'm thinking this is related to probability distributions, but I'm not familiar enough with them to determine which I should use, let alone what the input parameters should be.

Any help, hints, or tips would be appreciated.

A bit more details:

To be more exact, I'm trying to simulate the damaging effects of a single wave of missiles, launched from a fleet of spaceships, against a target, another fleet of spaceships. The fleets have an overall health and damage to that decreases the effectiveness of the fleet during later waves.

For simplicity, I'm simply using a defense rating (DEF) of a target and attack rating, ATK, of the missile to determine probability of hit, PHIT. Specifically, PHIT = ATK / (DEF + ATK), where DEF and ATK are 1 or higher, so it becomes 50:50 if the DEF and ATK ratings are the same. The DEF is intended to summarized all of the reasons why the missile might miss, while the ATK does the same for why the missile might hit.

Yet more details:

Haven't had internet so only now able to check it. I'll answer some questions.

I'm hoping to keep ATK/DEF values fairly close so p should typically be in the 0.25 to 0.75 range, but there'll probably be plenty of cases closer than 0.1 to 0 or 1.

I've had no intention of computing each missile separately, directly. Though, I do want the number of hits to be based on the probability of each missile hitting.

There could be up to millions or even billions of missiles per wave, and as many as 1000 waves (but it's much more likely to be in the single digits). I'll actually probably just put a limit on the number of waves and call it a draw if reached. So looking for an approach that is O(1) or O(log(N)) in time and space. Although, I'm willing to lower the limit on missiles if it's not possible to obtain random numbers from a binomial distribution or a hypergeometric distribution (the Wikipedia on this gave me some interesting ideas to expand the game) efficently. I'm looking at the scipy functions for them, and they seem suitable, though I haven't yet installed scipy to determine how efficent they are.

The game will likely be turn based, though there may be a game-mode that isn't.

The game will basically be similar to the Kenway's Fleet mini-game in Assassin's Creed Black Flag and it's relative in Assassin's Creed Rogue. However, it'll allow more customization and flexibility. The game is intended for web or mobile. It's also inspired by a number of novels that have fleet battles between spaceships, where waves of missiles are exchanged. Therefore the number of ships in the fleet are simply there to help justify increases in ATK, DEF and number of missiles per wave. This is why randomization is required.

I'd rather avoid simply using the mean as I think variance would make things more interesting, as a given scenario doing a specific amount of damage. Although, I tried out the normal with a mean and a bit of tweaking to the variance formula does yield results that seem suitable. As it was, cases where there was only a 60-70% chance of a hit, seemed to result in cases where a wave of 100 missiles had 100 hits (100% hits) quite often. Which is why I'm thinking binomial distribution should work better.

Answer 1

N projectiles are fired at a target with probability, p, that each missile will hit the target and damage dealt is based on the number of projectiles that hit.

I'd like to randomly generate the number of projectiles that hit. Fractional values would likely be considered as partial hits for this purpose and thus seem acceptable.

If the outcome for each missile is independent of all other missiles (not necessarily realistic) and $p$ is the same for all missiles, then the number of missiles that hit is binomial$(N,p)$.

If $X$ is the number of hits then $$P(X=x)={N\choose x} p^x (1-p)^{N-x}\,,\quad x=0,1,2,...,N$$

See Wikipedia on the binomial distribution.

Similarly, under the same assumptions, the probability of at least one hit is 1-P(0 hits), and P(0 hits) is just $P(X=0)$ above.

To randomly generate the number of hits, you can use functions that randomly generate from that binomial distribution (I don't know what you have access to but libraries for this sort of thing are commonplace).

Alternatively, since partial hits are okay, you could randomly generate from a normal with mean $Np$, and variance $Np(1-p)$, and if the answer is below 0 call it 0, and if it's above N call it N. Nearly always you'll get a non-integer number in between.

You could then round to the nearest integer, or you can say "if it's within some distance $d$ of $x+\frac{1}{2}$, call it $x$ hits and one partial hit". So you might say d=0.25, for example, which means if you got a result of 5.2 you'd say 'five hits' but a result of 5.4 would be '5 hits and one partial hit', while 5.9 would be "six hits'. By playing with $d$ you can increase or decrease the frequency with which any partial hits show up. This will never give more than a single partial hit though.

If you don't want to assume independence, you'll have to specify the dependence you want.

Answer 2

The answer to your worries is Monte Carlo simulation. You have two choices to describe how a missile strike is modeled:

1. Probability Distribution: The distribution of probabilities that a missile hits or achieves a partial hit. Design a probability distribution and randomly sample it for each N.
2. Algo: Design an algorithm that incorporates a probability distribution or simply probabilities and run through it for each missile attack. Algo can determine factors such as target speed, target distance etc.

To design an awesome game and see example of this math in action, buy and read Wayne Hughes Fleet Tactics and Coastal Combat. This book is both an excellent strategy book and a great book on modeling missile strikes. Other sources would be RAND papers on missile strikes/naval combat, see their appendixes for detailed modeling.