gun dispersion causing systematic error from use of "rng_normal"

[phaethonfire]

Describe the bug

After reading Issue #29293, I spent a number of hours parsing the shooting mechanics of CDDA. There are several thousand lines of relevant code, a bunch of TODO statements, and I suspect few people have comprehensively looked at it. So I think I've found an unlikely bug that may have slipped under the radar or at least needs discussion. Here is my "trace" of the code:

ballistics.cpp#131 "projectile_attack_roll"

I think this function is responsible for deciding if a shot hits. It rolls random numbers based on all sources of dispersion on line 142:

aim.dispersion = dispersion.roll();

The units here are arcminutes of deviation from the target. It then does some trigonometry to see if it hit the target. Importantly, returning a "0.0" here would mean a bulls eye hit. The bigger the number, the further the shot was from the target. But how does dispersion.roll() work?

dispersion.cpp#5 "dispersion_sources::roll()"

This function loops over all sources of dispersion one by one and uses a random number generator to pick where this specific projectile will go. It keeps a running total of how far off the mark the shot was from all the variables including dexterity, hand encumbrance, CBMs, and of course, the weapon stats. I won't write out the code, but this list of dispersion sources is compiled in the "fire_gun" function in ranged.cpp line 306 and then in the "get_weapon_dispersion" function on line 1834. The weapon_dispersion itself invokes the "dispersion_sources" object in a way that makes it follow a normal distribution (unless I'm greatly mistaken). All other sources of dispersion use .add_range or .multiplier, which is outside the scope of this issue and looks fine to me. So the important thing is that "weapon_dispersion" on line 1837 of ranged.cpp is an integer with units of arcminutes. When the RNG rolls a value for a specific projectile, this is the code in dispersion.cpp:

    for( const double &source : normal_sources ) {
        this_roll += rng_normal( source );

Great! So what does rng_normal do?

Well, that depends on how many arguments are passed in. rng_normal is an overloaded function. It really wants 2 inputs, but if you just give it one, it does this in rng.h:27

inline double rng_normal( double hi )
{
    return rng_normal( 0.0, hi );
}

That function is so simple and harmless that it lives in the header file. Cool, so those two inputs are the mean and standard deviation, right? RIGHT!?!?! Oh no...

Here it is worth pasting in all the code from rng.cpp:#L81-L100

double rng_normal( double lo, double hi )
{
    if( lo > hi ) {
        std::swap( lo, hi );
    }

    const double range = ( hi - lo ) / 4;
    if( range == 0.0 ) {
        return hi;
    }
    double val = normal_roll( ( hi + lo ) / 2, range );
    return std::max( std::min( val, hi ), lo );
}

double normal_roll( double mean, double stddev )
{
    static std::default_random_engine eng(
        std::chrono::system_clock::now().time_since_epoch().count() );
    return std::normal_distribution<double>( mean, stddev )( eng );
}

If you are reading what I'm reading, rng_normal wants the lowest and highest value that you expect. Since normal distributions have a long, unlikely tail at the end, it approximates a good max and min value to be 4 standard deviations from the mean. For some reason it calls that "range", but it is really the stdev. It sets the mean as (hi + lo)/2. Then it calls the standard library function "normal_distribution" powered by the usual random number generator and we're done.

Did you see the same problem I see? dispersion.cpp wanted a normal distribution centered around 0 with limits at +/- dispersion. Instead, it got a normal distribution centered at 1/2 dispersion with limits roughly between 0 and dispersion. So on average, every shot will be off target by 1/2 weapon dispersion. Disastrous, right? Why hasn't this broken the game? In our super realistic aiming simulator we have an error of 1/2 dispersion right out of the gate. We should be missing all the time.

Let's confirm this by checking how CDDA detects a hit. Back to ballistics.cpp line 132

    // an isosceles triangle is formed by the intended and actual target tiles
    aim.missed_by_tiles = iso_tangent( range, aim.dispersion );

    // fraction we missed a monster target by (0.0 = perfect hit, 1.0 = miss)
    if( target_size > 0.0 ) {
        aim.missed_by = std::min( 1.0, aim.missed_by_tiles / target_size );

For reference, target_size comes from ranged.cpp. For a normal sized monster, it is 0.5. In the end, aim.missed_by is in normalized units. aim.missed_by_tiles tells us how far we were from an ideal shot in units of tiles, and we divide by target_size, which is in units of tiles. The result is a unitless number. If that number is less than 1, it was a hit. It is the job of iso_tangent to convert the dispersion of this specific projectile and the distance to the enemy into a measure of how many tiles off we are from the mark. The units for all this are "tiles". Let's take a closer look.

line.h:31 "iso_tangent"

Another function so harmless it didn't even make it out of the header file.

inline double iso_tangent( double distance, double vertex )
{
    // we can use the cosine formula (a² = b² + c² - 2bc⋅cosθ) to calculate the tangent
    return sqrt( 2 * pow( distance, 2 ) * ( 1 - cos( ARCMIN( vertex ) ) ) );
}

Okay, that is a lot of dense math, but let me try to explain. The two inputs are the distance between us and our target and the "vertex", which is the angle represented by the dispersion of this specific shot (in units of arcminutes). Every piece of code up until now makes dispersion a positive integer, so we would expect symmetry here. It doesn't distinguish between missing to the left or missing to the right. 0 means dead on, negative angles don't happen, and we only get positive angles here.

So the math here sets things up as an isosceles triangle, where "distance" is length of the two "long" side of the triangle, and dispersion is the angle between them. When dispersion is low, this is fine. When dispersion is high, this isn't the best. Modeling a right triangle with symmetry is almost certainly better, but this isn't the major flaw here. I think the way recoil works, "vertex" can't be more than 50 degrees (or 3000 arcminutes), so it is close enough.

The real problem is this: If the enemy we are shooting at is a normal enemy (0.5 tiles wide), and @ is aiming at the middle of them, if the projectile goes more than 0.25 tiles to the left or 0.25 tiles to the right, it would be a miss. Based on all the code up to this point, symmetry is being used, and this is the physical model represented. At the very end, though, it doesn't scale by half of target_size, it scales by the whole thing! This means that for every single monster in the game, it is twice as easy to hit as it should be.

Conclusion

If you have gotten this far, please confirm my observations or explain where my code dive went wrong.

The way weapon_dispersion invokes a normal distribution appears to be broken in a way that undermines the entire aiming system. This should have broken the game in a noticeable way, except that a second bug made all monsters twice as easy to hit. These don't balance out. The dispersion system must be broken, unless I'm missing something. But they offset each other in a way that makes the game playable. As long as typical gun dispersion values result in a "missed_by_tile" value less than 1, it would require some intensive data mining to see that the statistics aren't working out.

The code governing these systems is spread out across at least 6 files and is opaque enough that I think it is possible for such a fundamental bug to have persisted underneath the skilled watchfulness of so many capable contributors. I think I spent 6 hours or so trying to understand everything.

Possible Solutions

Given how many systems this touches, I wanted to post an issue for discussion before proposing a "fix". The lightest touch to fixing things may be to change dispersion_sources::roll() from:

    for( const double &source : normal_sources ) {
        this_roll += rng_normal( source );

To:

    for( const double &source : normal_sources ) {
        this_roll += abs(rng_normal( -source, source ));

And then also change ballistics.cpp around #149 from:

 aim.missed_by = std::min( 1.0, aim.missed_by_tiles / target_size );

to

 aim.missed_by = std::min( 1.0, aim.missed_by_tiles * 2 / target_size );

to properly account for symmetry.

But this will suddenly make guns as accurate as they were supposed to be, probably breaking game balance even with "missed_by" scaled down to what it should be. The "range_with_even_chance_of_good_hit" is a precomputed table based on empirical statistics, so fixing the code would mess with that. There are a bunch of places where dispersion is scaled arbitrarily too (like all of data/game_balance.json).

I would propose that any fix needs to become a feature branch, and it also needs the careful attention of more than one contributor. For some players, much of their game experience is built around guns, and they would be crushed if their game experience suddenly broke. At the same time, even though the current implementation is "working" from a gameplay experience, letting it persist forever would be a bad thing. I wouldn't be surprised if many of the several thousands of lines of code around shooting was added to compensate for the error and to try to make guns a playable option.

On a less light touch approach, this could be an opportunity to radically simplify the mechanics of shooting accuracy. I originally dove into this code with just that goal. The statistical outcomes achieved by the current code could be recreated more simply, and the complex variables (how many casual players have a feel for how "dispersion" works?) could be translated to something more intuitive.

Please give feedback. Hopefully I'm not ringing a false alarm. The code is hard enough that I can't rule out just a plain misunderstanding on my part.

Thanks for reading!
-Phaethon

Edit: Haha, just watched a Vormithrax vod where he talks about dispersion (hopefully links aren't frowned upon): https://www.twitch.tv/videos/411723974?t=00h57m12s

[kevingranade]

I haven't worked through all the relevant code yet, but quick feedback.

dispersion_sources::roll() does not accumulate a 0-centered distribution, it accumulates "error", which is "magnitude of deviation from target point in arcminutes". These values are always intended to be positive, and weapon dispersion is doing what it is intended by choosing a number between 0 and the max dispersion value for the weapon.

For the target width evaluation, I'm less certain it's doing the right thing, but I am pretty certain that it washes out in the end and the game is as accurate as is intended, because that is checked by end-to-end tests that incorporate shooter, weapon and target. If it does turn out to be erroneous, then the fix would probably be to fix the code and incorporate that same scaling factor elsewhere.

this could be an opportunity to radically simplify the mechanics of shooting accuracy. The statistical outcomes achieved by the current code could be recreated more simply, and the complex variables (how many casual players have a feel for how "dispersion" works?) could be translated to something more intuitive.

You don't give much to go on here, so it's hard to give feedback. If you mean doing the same calculations in a simpler way, great. If you mean discarding the physical model of how gun accuracy works, I'm not interested.

[phaethonfire]

A small update: I found another reason this issue hasn't caused gameplay problems. In item.cpp#L5266, the "gun_dispersion" function currently divides weapon dispersion by an arbitrary 18 (it says 15 in the code comments, but it is 18 in game_balance.json)! So a gun with 500 dispersion really only has 27 dispersion... less than half a degree, and the way that propagates into roll() means on average it shifts things only 13.5 MoA. Thus, gun dispersion has almost no gameplay effect. The accuracy of a shot is dominated by skill level, encumbrance, and recoil. This also validates some of the qualitative sentiment that gun mods that modify dispersion don't really do anything.

Agreed that dispersion is supposed to accumulate error and that it is always a positive number. Error is represented as a scalar instead of a vector, and that is fine. Whether the shot misses left or right is decided in ballistics.cpp line 216 by randomly choosing positive or negative. But a perfect shot is 0.0, and dispersion in real life looks like a normal distribution centered around the bulls eye. Weapon dispersion is currently choosing a number that is weighted against a normal distribution centered at dispersion/2, and that simply cannot be what was originally intended. It doesn't mimic reality. The current implementation mimics a shooter that doesn't aim directly at its target, but instead aims to one side by dispersion/2. I bet this problem is why the game_balance.json divides gun dispersion down to such a tiny number. As long as the value of gun_dispersion/2 is much smaller than the size of the target, the bias isn't too bad.

So the real effect here is that gun dispersion and gun mods have very little impact on shooting accuracy. Fixing this problem is a prerequisite for making gun dispersion values meaningful again.

I think I can setup a reproducible demo of what I'm talking about by:

** Steps to Reproduce**

1. change "GUN_DISPERSION_DIVIDER" from 18 to 1 in game_balance.json
2. I also changed "DISPERSION_PER_GUN_DAMAGE" to 0 for consistency
3. start a new game with a 20 dex 20 perception character with 10s in all shooting skills. Remove all arm encumbrance. This zeros out other sources of dispersion.
4. wish for a high dispersion gun (e.g. 1911 handgun with reloaded ammo).
5. turn on debug logger
6. Use the construction menu to "Mark practice target" and stand ~10 tiles away.
7. only take precise shots (so RECOIL is 0) at the target and observe the "missed_by_tiles" values in the debug log.

Expected Results

What is expected is that numbers near zero are much more common that numbers further from zero. In other words, bullets cluster around the target. Like in this image: http://www.the-long-family.com/group_size_analysis_files/image014.jpg What will be observed is that the random numbers are clustered around some other number (10 tiles away with weapon dispersion of 500, that number is around 0.72). A few shots will be close to zero and a few will be as high as 1.4 tiles away, but 68% of the shots will be between ~0.36 and ~1.08. It would be like aiming at a target and shooting a donut shape around the bulls eye while very rarely hitting close to the middle.

[phaethonfire]

Just a quick status update: I have made a branch on my fork of the repo and am working on a pull request that fixes this issue. Obviously fixing this kind of thing will end up altering the game balance to some extent. I am going to do some initial testing to try to get the balance close to the existing setup. Once it isn't terrible, I will post the WIP PR.

Just to reiterate, the goal is not to rebalance ranged combat. The goal is to fix an error that (I believe) has caused weapon dispersion values to stay near zero. Fixing this paves the way for making different guns actually result in different accuracy and make weapon mods that adjust dispersion do something. It should also let us rip out some of the needlessly complex (and arbitrary) modifiers that were used to get the game into a playable state.

[kevingranade]

Recentering the normal distribution on 0 sounds great 👍
Longer term I wanted to have each contributor apply a 2D vector and sum them, but that can wait.

For balance you pretty much just want to get the balance tests working again and then do some 'live-fire' sanity tests to make sure they correlate.

[phaethonfire]

Well, I have hit a snag. It turns out that the ranged_balance.cpp tests will always fail for a dispersion mechanic that follows a normal distribution.

In the first test, for example, of an "unskilled shooter" with an inaccurate pistol, test_shooting_scenario ensures that the chances of hitting a medium sized monster at 5 tiles away is > 50%, and under identical conditions at 15 tiles away, it must be < 10%.

At 5 tiles away, a medium size target corresponds to 172 minutes of arc (MoA) (or double that without symmetry, but the conclusions are the same). If we shave the margin as thin as possible, a normal distribution with a standard deviation of up to 250 MoA could satisfy that constraint. Any higher and it would fail the test.

At 15 tiles away, a medium size target corresponds to 57 MoA (15 is 3 times as far as 5, so 1/3 the angle). The standard deviation of the normal distribution must be at least 440 to satisfy that. Not possible to satisfy both.

It makes real world sense that the tests shouldn't be satisfied. If I shoot at a target 5 meters away and another target at 15 meters away, I would expect my "spread" to be about 3x wider, not a 5x difference or more. These tests were passing before (sometimes narrowly I noticed) because modeling dispersion as a sum of linear variables does the "donut" thing I mentioned before.

I'm going to write up some brief documentation and then post a WIP pull request so that you can see what I am doing and it can be discussed. The other thing I have found is that the contributions to dispersion of the various sources (encumbrance, dexterity, skill, weapon, and recoil) vary a ton. Dexterity and encumbrance have almost no effect on shot accuracy. They could either be safely removed or scaled up to actually matter. The current skill penalties are mostly a multiplier of the gun dispersion, so they are huge.

[kevingranade]

The tests as written are not holy writ, that distribution can be adjusted as needed to make it work. I would prefer not to throw everything up in the air again simultaneously, so if possible I'd like to get the normal distribution thing fixed and then follow up by redistributing the influence from different sources.