2
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This seems rather good. I'm using Python for prototyping the mechanics before I switch to another language for building the final game. So something in Python's Random Module would be nice. That's Normal(mean, standard deviation) yes, if so seems like it could work rather well. I'll wait a bit, and if I don't have a better answer I'll mark this one, as it seems like what I'm after. P.S. Added more details to question. $\endgroup$
    – Nuclearman
    Jun 4, 2015 at 5:51
  • $\begingroup$ if you want random binomials, you can always use numpy.random.binomial. but the normal thing will probably do well enough for your purposes. The additional details relate to your internal mapping from attack/defense to a probability, which doesn't change my answer in terms of that probability. $\endgroup$
    – Glen_b
    Jun 4, 2015 at 6:00
  • $\begingroup$ If your game is turn based or grid based, like a strategy game, iid is not unreasonable. If the game is a pilot simulation, it might be best to simply measure if the projectile does or does not collide with the intended target and forgo random chance altogether. You also mention millions/billions of missles. Do you really need to determine each separately? It may be wise just to use the mean and concede the law of large numbers applies. Popular strategy games like starcraft have no random number generation for many many mechanics. $\endgroup$ Jun 5, 2015 at 18:12
  • $\begingroup$ True, while there may be a lot of projectiles. I'd like it to be fairly realistic in how many hits there will be. It's rather unlikely that 100 projectiles with an expected/average 70% hit rate for that situation, would achieve a 100% hit rate by chance. Although, you may have a point if I end up actually allowing for millions or billions of missiles. The number of hits would typically end up being pretty much N*p with a small margin of error, that I might just limit the number of missiles per wave to prevent this. $\endgroup$
    – Nuclearman
    Jun 11, 2015 at 2:37
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I planned to use Monte Carlo for testing the game, but it seems inefficient for determining number of hits. I'd like the algorithm to be O(1) per wave, with the number of waves should be less than 1000. The issue is that each wave could have upwards of millions, perhaps even billions of missiles, depending on how large the attacking fleet is. $\endgroup$
    – Nuclearman
    Jun 4, 2015 at 5:29
  • 1
    $\begingroup$ @Nuclearman This information from your comment should be in your question. It could alter suggested approaches. For example, it probably doesn't make much sense to generate binomials (you might do a Poisson if p is small enough or you could round a normal approximation to integer), but the variation about the mean may be very small in percentage terms. What are typical values for $p$? $\endgroup$
    – Glen_b
    Jun 6, 2015 at 0:36
  • $\begingroup$ I'm hoping for p to vary a fair bit. Players will probably try to ensure that they have high hit probabilities while the enemy has low ones, while the game tries to keep them somewhat even. So they should vary quite a bit. Although, I would expect them to generally be in the .25 to 0.75 range. Also, updated question. $\endgroup$
    – Nuclearman
    Jun 11, 2015 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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