4
\$\begingroup\$

I am trying to create random characters in my game. Each character has 33 abilities and one of 6 jobs. For each job you need to skill/increase other abilities. I am calculating an overall skill (from 1 to 99) by using only the important abilities for this job. For example one of the jobs is a healer. Here you need to skill ability1 to ability6, which have also different weights.

Example:

 - Healer 
 - Ability1 has weight 10 (skill 70)
 - Ability2 has weight 5 (skill 60)
 - Ability3 has weight 4 (skill 50)
 - Ability4 has weight 10 (skill 80)
 - Ability5 has weight 5 (skill 40)
 - Ability6 has weight 8 (skill 50)

 Example calculation: 
(70 * 10) + (60 * 5) + (50 * 4) + (80 * 10) + (40 * 5) + (50 * 8) = 2600 /  (10 + 5 +  4+10+ 5+ 8) = 62     

Problem:

I want to create random characters with random skills WITH a specific overall skill in HIS job. Example: CreateHealer(skill: 70). It doesn’t matter which values all the other abilities have. For example if ability7 is 1 or 99 the overall skill of the healer is always 70, but I want them to be random because the user has the opportunity to change the job, if he can see that this char would be a better warrior.

My idea:

Create all 33 abilities randomly and calculate the overall skill in this job.

  • If skill is on the right level —> stop.
  • If skill is too low increase one of the weighted abilities and calculate again.
  • If skill is too high decrease one of the weighted abilities and calculate again.

Is there a better way/algorithm to do this?

\$\endgroup\$
  • \$\begingroup\$ Do your characters have a limited point budget they need to distribute over their skills? Or can any skill be anywhere between 1 and 99? \$\endgroup\$ – Philipp Aug 26 at 9:26
  • \$\begingroup\$ Could you please explain what you mean with the ability weight? Does that mean that one point in Ability 1 with the weight of 10 means that it adds +10 to his job skill? Or is it just preference of distributing values, like highest on the 10s, then lower and so on? \$\endgroup\$ – PSquall Aug 26 at 10:41
  • \$\begingroup\$ It looks like your weights describe a family of hyperplanes in skill space. Using these, you can fix one hyperplane — the one with the total job skill value you want — by choosing one standard solution point on this hyperplane, then adding to it any multiple of a set of tangent vectors in the hyperplane. Restricting to integer solutions makes it a bit tougher though. Remember those math problems like "You have $2.20 in dimes and quarters, and 13 coins in total - how many of each coin do you have?" - this is the 6-dimensional version, with more free variables for your randomizer to play with. \$\endgroup\$ – DMGregory Aug 26 at 11:22
  • \$\begingroup\$ @Philipp Each skill can be between 1 and 99. Its possible that all skills have 99 as value. I have added an example to my post. Short: multiply each skill with its weight and sum them. Divide the result by the sum of the weights. \$\endgroup\$ – basti12354 Aug 26 at 12:39
  • \$\begingroup\$ Let me check if I understood this system correctly: The example you posted has a score of 62. Does that mean that this example character would not qualify as a healer because they need a weighted score of at least 70? \$\endgroup\$ – Philipp Aug 26 at 12:43
10
+100
\$\begingroup\$

Let's start simple and forget the constraint that skill values should be integers for a moment.

If we look at the equation for your job skill:

$$\begin{align} \frac{w_1 s_1 + w_2 s_2 + w_3 s_3 + w_4 s_4 + w_5 s_5 + w_6 s_6} {w_1 + w_2 + w_3 + w_4 + w_5 + w_6} &= j\\ w_1 s_1 + w_2 s_2 + w_3 s_3 + w_4 s_4 + w_5 s_5 + w_6 s_6 &= j \left( w_1 + w_2 + w_3 + w_4 + w_5 + w_6 \right) \end{align}$$

We can think of this as the equation of a 5-dimensional hyperplane in 6-dimensional skill space. Here the plane has a normal vector \$\vec n = \left(w_1,w_2,w_3,w_4,w_5,w_6 \right)\$, so we're looking for points in skill space \$\vec s = \left(s_1, s_2, s_3, s_4, s_5, s_6 \right)\$ such that...

$$\vec s \cdot \vec n = \left(j,j,j,j,j,j \right) \cdot \vec n$$

From this we can see one obvious solution \$\vec s = \left(j,j,j,j,j,j \right)\$ - ie. if you want a job skill of 70, set all the component skills to 70, then any weighted average of them will still give the desired output of 70.

But since it's a plane, once we have one solution, we can slide that solution along the plane to get other solutions. Since we're in 6-dimensional space, and we've locked down one degree of freedom by fixing the value of our weighted average, we still have 5 different directions we can slide the solution while staying on the plane.

We can use the Gram-Schmidt process to take our normal vector and augment it with a set of mutually-perpendicular tangent vectors in the plane, to form a new basis for our skill space:

Vector6[] basisVector = new Vector6[6];

basisVector[0] = Normalize(
    new Vector6(weight[0], weight[1], weight[2], weight[3], weight[4], weight[5])
);

for (int i = 1; i < 6; i++) {
    basisVector[i] = Vector6.Zero;
    basisVectot[i][i] = 1f;

    for(int j = 0; j < i; i++)
       basisVector[i] -= Dot(basisVector[i], basisVector[j]) * basisVector[j];

    basisVector[i] = Normalize(basisVector[i]);
}

At the end of this process, basisVector[0] is your unit normal direction, and basisVector[1] to [5] are unit tangent directions along the solution plane in skill space.

With these in hand, you can pick a range of variation and then generate skill combinations with your desired sum like so:

Vector6 skills = new Vector6(jobValue, jobValue, jobValue, jobValue, jobValue, jobValue);

for(int i = 1; i < 6; i++) {
    float deviation = Random.Range(-variation, variation);
    skills += deviation * basisVectors[i];
}

Here we slide ± variation along each of our tangent directions, mixing up the skill values while preserving their weighted sum.

The trouble is, this can give us fractional skill values! And when we round them to integers, we might no longer have exactly the job skill value we want.

You could take this and apply a fix-up step, where you choose a skill to raise or lower to restore the desired sum.


Or we can solve the equation for integer solutions in the first place, which makes this a Linear Diophantine Equation in six unknowns.

I had to teach myself how to solve these to answer this question, and the math's still a little unfamiliar so I might not be doing it in the most elegant/rigorous way. But here's the outline of the solution:

  • If we have a linear Diophantine equation in two unknowns, \$a x + b y = r\$...

    • We can use Euclid's algorithm to find the greatest common divisor of \$a\$ and \$b\$, \$d\$

    • The equation has a solution if and only if \$d | r\$ (ie. r % d == 0)

    • We can backtrack through the steps of Euclid's algorithm to find a solution \$(x_*, y_*)\$ to the equation \$a x + b y = d\$

    • We can use this to find a solution to our original equation, \$a x + b y = d\$ by just scaling the whole thing up by \$\frac r d\$: \$\left(x_* \frac r d, y_* \frac r d\right)\$

    • Once we have one solution, we can navigate to any other by adding a multiple of \$\left(\frac b d, \frac a d \right)\$ to our \$(x, y)\$ pair, without changing the value of the right-hand side

      (we'll use this to apply randomization to our stats without changing the total job value)

  • If we have an equation with more unknowns, we can lump all but the last term together into one (so now we're back to just two unknowns), solve for the last term, then chip it off and repeat:

    $$a_0 x_0 + a_1 x_1 + a_2 x_2 + ... + a_n x_n = r$$

    Is equivalent to...

    $$gcd(a_0 ... a_{n - 1}) y_{n-1} + a_n x_n = r$$

    Once we solve this for \$x_n\$, we can subtract \$a_n x_n\$ from both sides and continue with the remaining \$n - 1\$ unknowns...

    $$gcd(a_0 ... a_{n - 2}) y_{n-2} + a_{n - 1} x_{n - 1} = r - a_n x_n\\ ...\\ gcd(a_0, a_1) y_1 + a_2 x_2 = r - \sum_{i = 3}^n a_i x_i\\ a_0 x_0 + a_1 x_1 = r - \sum_{i = 2}^n a_i x_i$$

    (Note we never really solve for the \$y_i\$ terms, they're just standing-in for the rest of the equations we haven't solved yet)

So, what that can look like in code: first, let's make a workhorse to handle solving the two-unknown case, giving us the triplet \$\left(x_*, y_*, d\right)\$

public struct DiophantineSolution {
    public readonly int x;
    public readonly int y;
    public readonly int gcd;       

    DiophantineSolution(int x, int y, int gcd) {
        this.x = x;
        this.y = y;
        this.gcd = gcd;
    }

    public static implicit operator bool(DiophantineSolution s) { 
        return s.gcd > 0; 
    }
    public static DiophantineSolution invalid { 
        get { return new DiophantineSolution(-1, -1, -1); }
    }        

    static Stack<int> quotients = new Stack<int>();
    public static DiophantineSolution Solve(int a, int b) {

        // Assume a > b - if not, flip it, solve it, then flip back.
        if (a < b) {
            var flip = Solve(b, a);
            return new DiophantineSolution(flip.y, flip.x, flip.gcd);
        }

        // For now, we'll handle only cases with non-negative coefficients.
        if (a <= 0 || b < 0)
            return invalid;

        // Trivial solution if we have only one unknown with a nonzero coefficient:
        if (b == 0)
            return new DiophantineSolution(1, 0, a);

        // Euclidean Algorithm to find the greatest common divisor:
        int x = a, y = b;
        int remainder = -1;
        do {
            int quotient = System.Math.DivRem(x, y, out remainder);
            // Save the quotients along the way to use in building the initial solution.
            quotients.Push(quotient); 

            x = y;
            y = remainder;
        } while (remainder > 0);

        // If b exactly divides a, we have a trivial solution.
        if (quotients.Count == 1)
            return new DiophantineSolution(1, 1 - quotients.Pop(), b);

        // Otherwise, rewind to the last step with a non-zero remainder.
        remainder = x;
        quotients.Pop();

        // Form the equation   remainder = dividend * (1) + divisor * (- quotient)
        // Where x & y are coefficients:               x                   y
        x = 1;            
        y = -quotients.Pop();

        // Reverse the steps of the Euclidean algorithm to get a solution to
        // remainder = a * x + b * y
        while (quotients.Count > 0) {
            x -= y * quotients.Pop();     // 1 + 4 * 1
            Swap(ref x, ref y);
        }

        // Now we have our initial solution.
        return new DiophantineSolution(x, y, remainder);
    }        
}

Now we're ready to use this to randomize our stats:

Stack<int> sums = new Stack<int>();
Stack<DiophantineSolution> intermediates = new Stack<DiophantineSolution>();

void GenerateSkills(int[] weights, int targetValue, int randomnessRange) {
    // Build up our table of greatest common divisors of the first i weights,
    // storing the solution information for re-use later.
    // We'll also store the sum of the first i weights for evening-out the stats.
    intermediates.Push(DiophantineSolution.Solve(weights[0], 0));
    sums.Push(weights[0]);
    for (int i = 1; i < weights.Length; i++) {
        intermediates.Push(DiophantineSolution.Solve(intermediates.Peek().gcd, weights[i]));
        sums.Push(sums.Peek() + weights[i]);
    }

    // Compute the right-hand side of our equation.
    int rhs = sums.Peek() * goalValue;

    // Solve the stats one at a time, from the last down to the second...
    for(int i = weights.Length - 1; i > 0; --i) {

        var solution = intermediates.Pop;
        var precedent = intermediates.Peek();

        // Initial solution to (... + a_i x_i = rhs)
        int baseline = solution.y * rhs / solution.gcd;

        // Spacing between possible solution values.
        int step = precedent.gcd / solution.gcd;

        // Which solution comes closest to giving all remaining stats an equal value?
        int closest = Mathf.RoundToInt((myShare - baseline) / (float)step);

        // How far can we stray from this evenly-distributed solution?
        int range = randomnessRange / step;

        // Apply random deviation within this range.
        int deviation = Random.Range(-range, range + 1);

        // Shift our baseline solution by our chosen multiple of the solution spacing.
        skills[i] = baseline + step * (closest + deviation);

        // Deduct the value we've accounted for from the right side of the equation.        
        int contribution = skills[i] * weights[i];
        rhs -= contribution;
    }

    // The first skill handles whatever is left over.
    skills[0] = rhs / weights[0];

    // Clean up after ourselves.
    intermediates.Pop();
    sums.Pop();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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