1
\$\begingroup\$

XP tables are common, but level tables are unfeasible and formulas are also possible. Are principles known that can help implement a defined progression through relationships between level, total xp, xp to the next level, and others?

No need to consider gross innovations like non-integer levels and XP.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ There are infinite possible functions to map XP to level and vice versa. To choose one for your game, you'll need to tell us more about your game's particular rules, needs, and goals. Otherwise we might share a formula that puts out reasonable-looking numbers that do not support the kind of gameplay you want. \$\endgroup\$
    – DMGregory
    Sep 23, 2022 at 17:59
  • 1
    \$\begingroup\$ Hi! Yup, I know. I don't want an Xp(Lv) formula, it sets the xp demand, therefore specifies progression. The problem is allow extracting (or calculating) the data associated with whatever already defined progression. I want to know viable ways to get these numbers and better than the ones I know, without necks and, if possible, saving space (but "tables O(Lv)" are options). \$\endgroup\$
    – RHER WOLF
    Sep 23, 2022 at 21:42
  • 1
    \$\begingroup\$ "Without necks"? The options are basically make a formula, or use a table, so I think you've covered the bases here. What new information are you looking for from answers? \$\endgroup\$
    – DMGregory
    Sep 23, 2022 at 21:45
  • 1
    \$\begingroup\$ Did you see it here gamedev.stackexchange.com/questions/186081? I open question about choice of progression trying to be fair and, while waiting for a better answer, I wrote mine calmly. Now I'm talking about progression implementing to complete the pack, rs. \$\endgroup\$
    – RHER WOLF
    Sep 23, 2022 at 21:49
  • 1
    \$\begingroup\$ I think everything is easy with the XP table except get level and I want to look how people does it. \$\endgroup\$
    – RHER WOLF
    Sep 23, 2022 at 21:52

2 Answers 2

1
\$\begingroup\$

I understand that when the progression is defined consequently the XP table is too, even using an algorithm. Most common is to store the values initial character level Lv and initial character total XP TotalXp to update and calculate other things using the elementary "conversion from level to total XP" algorithm/formula/table (you called it Xp(Lv)).

We may have means of at least

  1. convert Lv into minimum total amount of XP to have at least the level Lv (you called "Xp tables" but I'm calling it Xp(Lv), right?)
  2. and have (or calculate) the level that corresponds to the current total XP, that is, Lv such that Xp(Lv) ≤ TotalXp < Xp(Lv+1) (you called Lv(Xp))

because with these you can get more data, like

  1. \$Xp_{_{ToNextLv}}(Lv)=Xp(Lv+1)-Xp(Lv)\$,
  2. \$Xp_{_{RemToNextLv}}(TotalXp)=Xp(Lv(TotalXp)+1)-TotalXp\$ and
  3. \$Xp_{_{OwnToNextLv}}(TotalXp)=\frac{100\%*Xp_{_{RemToNextLv}}(TotalXp)}{Xp_{_{ToNextLv}}(Lv(TotalXp))}\$.

I think it's convenient to divide this question in two types of Lv(Xp) finding problems, the more conveniently expressed by tables and the more by formulas (finding Xp(Lv) formula too). Let's look at some algorithms options that do this.

Solving with tables

If you have a table of minimum Xp per level, you have Xp(Lv) and the points are expected to increase with level, so a mere binary lookup algorithm solves the Xp(Lv) ≤ TotalXp < Xp(Lv+1) problem. On the other hand, if the problem is that you think it will be a waste of processing, you can take advantage of the fact that the table is fixed and this allows for some simplifications.

For example, if you have a total, non-negative amount of experience points called Xp and the five levels Xp table [ Lv1⟼0 , Lv2⟼10 , Lv3⟼70 , Lv4⟼250 , Lv5⟼700 ], you know that

if Xp<10:
    Lv = 1
elif Xp<70:
    Lv = 2
elif Xp<250:
    Lv = 3
elif Xp<700:
    Lv = 4
else:
    Lv = 5

but can compare up to four times (for dozens of levels can do dozens of times) and binary do it this way (for many dozens doesn't eight times).

if Xp<250:
    if Xp<70:
        if Xp<10:
            Lv = 1
        else:
            Lv = 2
    else:
        Lv = 3
else:
    if Xp<700:
        Lv = 4
    else:
        Lv = 5

Also, if we assume that an integer access of a table, a constant power-of-two division and some other arithmetic operations are faster than a comparison with a flow control, we can take advantage of reading the cache at later positions in what will work as a short "level table" that will guide binary search steps with more agile operations.

Using the example again and assuming Xp doesn't exceed 700, so not 999, not 1024... but the variables can hold more than ten thousand, then setting the limitation 1024 to make 0 ≤ Xp < 1024, 0 ≤ X ≤ 1024 and i ∈ ℤ we can enjoy the implication

\$ Xp<X \implies \$

\$ Xp+(1024*i-X)<1024*i \implies \$

\$ \frac{Xp+(1024*i-X)}{1024} < i \implies \$

\$ t = \lfloor \frac{Xp+(1024*i-X)}{1024} \rfloor < i \$

and we have t=i-1 when Xp<X and t=i when Xp≥X. Using table constants with 1024*i-X to simulate comparison and i as greater "next table index" or "level in the end", why not do it?

T = [ 2*1024-250 , 4*1024-70 , 6*1024-700 , 2*1024-10 , 3*1024-70 , 4*1024-250 , 5*1024-700 ]
t = 0

// if Xp<250: t = 1
// else:      t = 2
t = ( Xp+T[t] )/1024

// if Xp<250:
//     if Xp<70:  t = 3
//     else:      t = 4
// else:
//     if Xp<700: t = 5
//     else:      t = 6
t = ( Xp+T[t] )/1024

// if Xp<250:
//     if Xp<70:
//         if Xp<10:  Lv = 1
//         else:      Lv = 2
//     else:          Lv = 3
// else:
//     if Xp<700:     Lv = 4
//     else:          Lv = 5
Lv = ( Xp+T[t] )/1024

I see that it is even possible to do with one cell less, unifying the four and five indices (the two distinguish levels 3 and 4) and decreasing the following indexes. Also, the variable t can be used instead of Lv itself and starts at zero.

T = [ 2*1024-250 , 4*1024-70 , 5*1024-700 , 2*1024-10 , 4*1024-250 , 5*1024-700 ]

// if Xp<250: Lv = 1
// else:      Lv = 2
Lv = ( Xp+T[0] )/1024

// if Xp<250:
//     if Xp<70:  Lv = 3
//     else:      Lv = 4
// else:
//     if Xp<700: Lv = 4
//     else:      Lv = 5
Lv = ( Xp+T[Lv] )/1024

// if Xp<250:
//     if Xp<70:
//         if Xp<10:  Lv = 1
//         else:      Lv = 2
//     else:          Lv = 3
// else:
//     if Xp<700:     Lv = 4
//     else:          Lv = 5
Lv = ( Xp+T[Lv] )/1024

The greater is T[2]=5444. When the case is overflow, you can subtract an index proportion from the cells affected by a formula and add the index correction to it or even apply it to the formula below. For example, the first formula uses [ 2*1024-250 ] (why not subtract 1024, will be lower than thousand), second uses [ 4*1024-70 , 5*1024-700 ] (why not -3*1024) and third [ 2*1024-10 , 4*1024-250 , 5*1024-700 ] (why not -1024), then...

T = [ 1024-250 , 1024-70 , 2*1024-700 , 1024-10 , 3*1024-250 , 4*1024-700 ]
Lv = ( Xp+T[0] )/1024
Lv = ( Xp+T[1+Lv] )/1024
Lv = 1+( Xp+T[3+Lv] )/1024

So we have from an Xp table an extracted Lv table and a calculation procedure. It would be interesting to make an algorithm that assembles the table and possibly the sequence of constants per instruction from the restriction.

Questioner edit: taking the idea, one more option is to use Xp<X ⟹ Xp-X<0 assuming an unsigned overflow/carry subtraction when the index/level is lower (otherwise higher) or Xp<X ⟹ Xp+( 2³²-X )<2³² ⟹ Xp+uint(-X)<0 assuming an unsigned overflow/carry addition when the index/level is higher (if not lower). We should handle indices differently and maybe it supports billions of points. It can be ushort & 2^16, ulong & 2^64, etc.

T = [ uint(-700) , uint(-70) , uint(0) , uint(-10) , uint(-250) , uint(0) ]
Lv = AddWithCarry(0,0, AddWithCarry(Xp,T[0],0).carry ).sum
Lv = AddWithCarry(Lv,Lv, AddWithCarry(Xp,T[1+Lv],0).carry ).sum
Lv = 1+AddWithCarry(Lv,Lv, AddWithCarry(Xp,T[3+Lv],0).carry ).sum

The first "flow control" (index=0) isolates

  • Lv∈{1,2,3,4} (index=(1)+0) and
  • Lv∈{5} (index=(1)+1, it would support Lv∈{5,6,7,8} with one more slot in the table),

the second (index∈{1,2}) isolates

  • Lv∈{1,2} (index=(3)+0) and
  • Lv∈{3,4} (index=(3)+1) and
  • Lv∈{5} (index=(3)+2, would Lv∈{5,6} with no larger table)

and the last (index∈{3,4,5}) get the level. It considers the processors standard instructions optimized using (like add with carry and mov with offset).

Note that to keep the indices doubling and thus branching using parity (carry) on each descent we have to separate as many lower levels as possible (power-of-two) in the first indices and the others in the last ones so that they don't grow more than necessary, otherwise it requires more operations (to result adjusting). It builds a table that looks like a -Xp full search tree except uint(0) is like -∞ and its slots spreads like "unary tree" (because don't need to branch off, only have same depth).

Solving with formulas

Tables can structure progression exactly but they take up space and formulas can be fast and accurate enough, so they are options too.

The XP table [ Lv1⟼0 , Lv2⟼10 , Lv3⟼70 , Lv4⟼250 , Lv5⟼700 ] example has Lv(-∞)=...=Lv(8)=Lv(9)=1, Lv(10)=Lv(11)=...=Lv(68)=Lv(69)=2, Lv(70)=Lv(71)=...=Lv(248)=Lv(249)=3, Lv(250)=Lv(251)=...=Lv(698)=Lv(699)=4 and Lv(700)=Lv(701)=...=Lv(∞)=5. It happens when

\$ Lv(Xp)=\lfloor f( clamp( 9 , Xp , 700 ) ) \rfloor \$,

\$ 1 \le f(9) < 2 \$,

\$\left\{ \begin{aligned} 2 \le f(10) < 3 \\ 2 \le f(11) < 3 \\ ... \\ 2 \le f(68) < 3 \\ 2 \le f(69) < 3 \end{aligned}\right.\$

\$\left\{ \begin{aligned} 3 \le f(70) < 4 \\ 3 \le f(71) < 4 \\ ... \\ 3 \le f(248) < 4 \\ 3 \le f(249) < 4 \end{aligned}\right.\$

\$\left\{ \begin{aligned} 4 \le f(250) < 5 \\ 4 \le f(251) < 5 \\ ... \\ 4 \le f(698) < 5 \\ 4 \le f(699) < 5 \end{aligned}\right.\$

\$ 5 \le f(700) < 6 \$

or something like it, so generically rounding is necessary to omit progress between level numbers, f must map to values that make correctly Lv formula (for each valid Xp we have Lv(Xp)≤f(Xp)<Lv(Xp)+1 ⟹ Lv(Xp)=⌊f(Xp)⌋ or Lv(Xp)-0.5<f(Xp)<Lv(Xp)+0.5 ⟹ Lv(Xp)=⌊f(Xp)⌉ or something like) and can clamp.

Watch out for rounding errors. If you make Lv(Xp)=⌊f(Xp)⌋ and try f(10)=2 but code result is f(10)=1.999999999999999778 (minus one bit) then Lv(10)≠2. Since Lv(9)=1 and Lv(10)=2, is better to assume that the level transition experience points is between 9 and 10 (possibly f(9.5)=2 or (f(9)+f(10))/2=2).

The most common is to use easily invertible functions and truncation (the same as rounding down for non-negatives), because defining one formula like this makes the other one obvious. For example, if you decided that Xp(Lv)=10*(Lv-1)³ then Lv(Xp)=uint( cbrt(0.1*Xp) )+1 (or better yet Lv(Xp)=uint( cbrt(0.1*Xp+0.05) )+1 to avoid rounding error).

Another more usual thing is to set a formula and accept the consequent progression, but you can set progression and try to find some sufficiently precise formula with curve fitting, regression, etc. If you want Lv(9.5)=2, Lv(69.5)=3, Lv(249.5)=4 and Lv(699.5)=5 then can find

\$ Lv(Xp) = \lfloor f(clamp(9,Xp,700)) \rfloor \$

such that, for example,

\$ f(Xp) = c_0+^3\sqrt{c_1+(c_2+c_3 Xp)^3} \$

\$\left\{ \begin{aligned} f(9.5) = 2 \\ f(69.5) = 3 \\ f(249.5) = 4 \\ f(699.5) = 5 \end{aligned}\right.\$

because

\$ f^{-1}(Lv) = k_0+^3\sqrt{k_1+(k_2+k_3 Lv)^3} \$

\$\left\{ \begin{aligned} k_0 &= -c_2/c_3 \\ k_1 &= -c_1/c_3^3 \\ k_2 &= -c_0/c_3 \\ k_3 &= 1/c_3 \end{aligned}\right.\$

and the solution is { c0≈-4.18488 , c1≈562.35163 , c2≈-7.05762 , c3≈1/53.70418 , k0≈379.02365 , k1≈-87102824.71339 , k2≈224.74532, k3≈53.70418 }. Assuming just that, we have

\$f(0) = 1.76669\$
\$f(9) = 1.98843\$
\$f(10) = 2.01148\$
\$f(69) = 2.99399\$
\$f(70) = 3.00597\$
\$f(249) = 3.99918\$
\$f(250) = 4.00080\$
\$f(699) = 4.99607\$
\$f(700) = 5.00393\$
\$f(\infty) = \infty\$

and the graph of Lv(Xp) and f(Xp) is below.

enter image description here

Don't need to restrict Xp≥9 in level formula, you can see, but we must to take a look at the XP formula and inverse of f.

\$f^{-1}(1) = -24.10491\$
\$f^{-1}(2) = 9.50000\$
\$f^{-1}(3) = 69.50000\$
\$f^{-1}(4) = 249.49997\$
\$f^{-1}(5) = 699.49999\$
\$f^{-1}(\infty) = \infty\$

To get the correctly result, the rounding is up or k0 must plus one (i.e. one is added to the function result) to use truncation. Even so, f(1) is very wrong. We can use

\$ Xp(Lv) = clamp(0, \lfloor 1+f^{-1}(Lv) \rfloor ,700)\$

and the plotting of Xp(Lv) and f⁻¹(Lv) is below.

enter image description here

Since Xp(Lv) is multiple of 10 we can use

\$ Xp(Lv) = 10*trunc(f^{-1}(Lv)) \$

with domain {1,2,3,4,5} and constants { k0=37.5 , k1=-64156.5 , k2=13.3 , k3=6.6 }.

\$f^{-1}(1) = -0.82135\$
\$f^{-1}(2) = 1.78756\$
\$f^{-1}(3) = 7.17327\$
\$f^{-1}(4) = 25.83881\$
\$f^{-1}(5) = 70.24065\$
\$f^{-1}(\infty) = \infty\$

Finally, if we don't get sufficiently accurate results we can adjust to make Lv(Xp(Lv))=Lv (and using some root-finding algorithms, possibly) if level function is exact. For example, if inverse of f is such that

\$f^{-1}(1) = -1.2\$
\$f^{-1}(2) = 1.8\$
\$f^{-1}(3) = 6.8\$
\$f^{-1}(4) = 25.2\$
\$f^{-1}(5) = 69.8\$
\$f^{-1}(\infty) = \infty\$

then truncation can be the correct value or its predecessor, so we can see if current Xp(Lv) result is such that Lv(Xp(Lv))=Lv, otherwise (Lv(Xp(Lv))<Lv) we threat as if truncation value is incremented.

\$ Tmp_{Xp} = Tmp_{Xp}(Lv) = 10*trunc(f^{-1}(Lv)) \$
\$ Xp(Lv) = \left\lbrace \begin{array}{ccc} Tmp_{Xp} & Lv(Tmp_{Xp}) = Lv \\ Tmp_{Xp}+10 & otherwise \end{array}\right.\$

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think it was well answered. I'm also waiting for the formulas season. I just didn't like the order of numbers O(Lv*Xp) of "Lv table", the overflow restricts the scale more. Maybe I'll improve this later with things that I'm thinking about... \$\endgroup\$
    – RHER WOLF
    Sep 24, 2022 at 0:28
  • 1
    \$\begingroup\$ I edited with one more table of levels. Let's see if it's approved. \$\endgroup\$
    – RHER WOLF
    Sep 27, 2022 at 17:02
  • 1
    \$\begingroup\$ Well thought out, got simpler. I like the improvement. \$\endgroup\$ Sep 27, 2022 at 17:37
1
\$\begingroup\$

level tables are unfeasible

Why? When you have a level-to-exp table, then you also have a sorted exp-to-level table. Just fill it with the cumulative exp values, and not just the exp values to get from the previous to the next level. And if you don't want that, you can easily create that data at runtime. And it's already sorted, so if you want to derive the level from the exp, you just need to do a binary search.

I am a big fan of level tables, because even if your design document defines the exp curve by some complicated formula, a table that's hardcoded or read from a configuration file allows you to slightly fudge the numbers to make them more aesthetical. So instead of a level requiring 50,102 exp, you round that to 50,000 exp. It makes almost no difference gameplay-wise, but just looks a lot better in the UI and feels more accessible to the player.

\$\endgroup\$
1
  • \$\begingroup\$ Emerald said it but included a better solution. Your thought counts. \$\endgroup\$
    – RHER WOLF
    Oct 20, 2022 at 13:10

You must log in to answer this question.

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