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.
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
Xp(Lv), right?)Xp(Lv) ≤ TotalXp < Xp(Lv+1) (you called Lv(Xp))because with these you can get more data, like
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.
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) andLv∈{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) andLv∈{3,4} (index=(3)+1) andLv∈{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).
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.
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.
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.\$
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\$
Commented
Sep 24, 2022 at 0:28
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.
O(Lv)" are options). \$\endgroup\$