3
\$\begingroup\$

We wanted to create a quick spreadsheet to rapidly adjust enemies' Attack and Defense from players' estimated values of Attack and Defense.

One of the key values to adjust is the "hits until dead", and to derive this we need an average of the damage.

A basic calculation of the damage is done as following. Both players and enemies have minimum and maximum values for attack and defense. Two random values are generated between these and the difference is the damage received. Note that the minimum damage is zero (or miss).

attack = random(attack_min, attack_max);
defense = random(defense_min, defense_max);
damage = max(attack - defense, 0);

When attack_min > defense_max, a simple formula like this can be used to obtain the average damage:

attack_mean = (attack_min + attack_max) / 2;
defense_mean = (defense_min + defense_max) / 2;
damage_mean = attack_mean - defense_mean;

But in the other case, there is a chance of missing, and this formula is not accurate.


Let this be an example where the initial formula works:

attack_min = 10; attack_max = 20;
defense_min = 0; defense_max = 5;

attack_mean = (10 + 20) / 2 = 15;
defense_mean = (0 + 5) / 2 = 2.5;
damage_mean = 15 - 2.5 = 12.5;

And, this is an example where it does not:

attack_min = 10; attack_max = 20;
defense_min = 5; defense_max = 35;

attack_mean = (10 + 20) / 2 = 15;
defense_mean = (5 + 35) / 2 = 20;
damage_mean = 15 - 20 = -5;

There is low chance, but there is damage between 5 and 15! Empirical values suggest an average of around 2.


So, the request is the following: we need a formula that gives us the average damage regardless of whether defense is higher than attack or not. (We need a formula, not a procedure, so RNG is off the table).

Can anyone enlighten us on this? Thank you!!


Thanks to @DMGregory's answer, a reader may find the Excel VBA custom formula below, in case it can suit they.

Function TriangleSum(n)

TriangleSum = WorksheetFunction.Max(n ^ 3 + 3 * n ^ 2 + 2 * n, 0) / 6

End Function

Function GetMeanDamage(attackMin, attackMax, defenseMin, defenseMax)

GetMeanDamage = ( _
                TriangleSum(attackMax - defenseMin) _
                - TriangleSum(attackMax - defenseMax - 1) _
                - TriangleSum(attackMin - defenseMin - 1) _
                + TriangleSum(attackMin - defenseMax - 2) _
            ) / ( _
                (attackMax - attackMin + 1) * (defenseMax - defenseMin + 1) _
            )

End Function
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Well structured, good language, and nicely presented. But what is your actual question? \$\endgroup\$
    – Peter
    Commented Jun 5, 2017 at 21:58
  • \$\begingroup\$ Oh, yes. We need a formula that gives us an average damage correctly, without generating random numbers. \$\endgroup\$
    – nerestaren
    Commented Jun 5, 2017 at 22:18

1 Answer 1

6
\$\begingroup\$

We can construct a table of damage values, for each possible attack and defense roll. Then the expected damage is the sum of all the cells in this table, divided by its area (so long as your attack & defense rolls are evenly weighted).

The zeros for attack < defense make it a bit complicated though, potentially chopping the area we need to sum over into three different shapes:

Diagrams showing how different attack & defense ranges might need to be summed in 3 different ways

We can sum over this by adding up each shape in turn, skipping over it for the cases where it's empty. The procedure gets a bit involved though:

float ExpectedDamage(int attackMin, int attackMax, int defenseMin, int defenseMax)
{
    int damageMax = Mathf.Max(attackMax - defenseMin, 0);
    int damageMin = Mathf.Max(attackMin - defenseMax, 0);

    // Early-out when attack & defense are constant,
    // or defense completely dominates the attack.
    if (damageMin == damageMax)
        return damageMax;

    // From here on in, we don't care if it's attack or defense that has greater
    // range - we just want to distinguish the narrow side of the table.
    int broad = attackMax - attackMin + 1;
    int narrow = defenseMax - defenseMin + 1;
    if (narrow > broad)
    {
        int swap = broad;
        broad = narrow;
        narrow = swap;
    }

    int result = 0;              

    // Upper Triangle
    {
        int depth = Mathf.Min(narrow, damageMax);
        result += (depth * (3 * damageMax * (depth + 1) - 2 * (depth * depth - 1)))/6;
    }

    // Middle Parallelogram
    if (damageMax > narrow && broad > narrow)
    {            
        int peak = damageMax - narrow;
        int depth = Mathf.Min(broad - narrow, peak);

        result += narrow * depth * (2 * peak - (depth - 1))/2;
    }

    // Lower Trapezoid
    if (damageMax > broad && narrow > 1)
    {
        int peak = damageMax - broad;
        int depth = peak - damageMin;

        // Fill bottom triangle with the minimum value.
        result += damageMin * (narrow) * (narrow - 1) / 2;

        // Add the diagonals that exceed that minimum.
        result += (narrow * depth * (depth + 1) - (depth * (depth + 1) * (depth + 2)) / 3) /2;
    }

    return result/((float)(broad * narrow);
}

...so that's ugly as sin and full of magic algebra formulas with no obvious reason why they're correct. It took a lot of figuring and debugging to get it working, and if an accidental change breaks it, it would be hard to track down the problem.

There's a neat trick we can use to make this more uniform, based on summed area tables.

Diagram showing a table broken into sums and differences of triangular regions

If we imagine the values carried on past the bottom & right edges of the table, we could take the sum of the full triangle starting at our upper-left corner, then subtract the sums of the triangles past the bottom & right edges, and add back the sum of the triangle off the bottom-right corner (since otherwise we'd have subtracted it twice, in the overlap of the right & bottom triangles)

And there's a closed-form formula for the sum of a triangle peaking at some value n:

TriangleSum(n) = max(n * (n + 1) * (n + 2), 0)/6

Still a magic formula, but at least it's just one this time!

So then our expected damage is:

( TriangleSum(attackMax - defenseMin)
- TriangleSum(attackMax - defenseMax - 1)
- TriangleSum(attackMin - defenseMin - 1)
+ TriangleSum(attackMin - defenseMax - 2)
)/((attackMax - attackMin + 1) * (defenseMax - defenseMin + 1))

Rewriting this a bit with A = attackMax a = attackMin - 1 D = defenseMax + 1 d = defenseMin helps it look a bit neater:

( TriangleSum(A - d)
- TriangleSum(A - D)
- TriangleSum(a - d)
+ TriangleSum(a - D)
)/((A - a) * (D - d))
\$\endgroup\$
2
  • \$\begingroup\$ Brilliant. I've just tested it and it works perfectly. I hoped it wouldn't be so complicated. I'll read it again (for the 4th or 5th time) and try to completely understand the logic behind :p \$\endgroup\$
    – nerestaren
    Commented Jun 6, 2017 at 8:52
  • 1
    \$\begingroup\$ Yeah, I feel it can be simplified still. Without those maxes in there it boils down to just a few additions and multiplications, but unfortunately that's only valid when all four taps land at or above the first lines of zeroes — otherwise some of the negative terms get zero'd out and aren't there to cancel against. The 3-case version would technically be less computation, but it's less uniform because it uses a different formula in each shaped chunk. \$\endgroup\$
    – DMGregory
    Commented Jun 6, 2017 at 12:32

You must log in to answer this question.

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