33
\$\begingroup\$

In my game, XP needed to reach the next level is Current Level × Level Threshold. Given that, how can I get my current level from the total XP ever earned?


For example:

Level Threshold = 50
Current Level = 1

Starting at level 1, I would need (1 × 50) = 50 XP to get to level 2, and so on.

Level 1: 50 XP needed to reach level 2
Level 2: 100 more XP needed to reach level 3
Level 3: 150 more XP needed to reach level 4

In other words, the progression table is as follows:

Level 1: 0 XP to 49 XP
Level 2: 50 XP to 149 XP 
Level 3: 150 XP to 299 XP
Level 4: 300 XP to 499 XP

If I have 300 XP, I'll just reached level 4. How can I calculate that generally?

\$\endgroup\$
  • \$\begingroup\$ Related on Stack Overflow: Calculating a triangular root without sqrt \$\endgroup\$ – Damian Yerrick Oct 28 '15 at 19:46
  • \$\begingroup\$ The amount of XP required for the next level doesn't increase the higher the current level goes? \$\endgroup\$ – Mast Oct 29 '15 at 10:15
  • \$\begingroup\$ Well, the first question you need to answer is: What is the "threshold" value for each level? Based on your example, if we assume that 300 XP is the minimum to reach level 4, then your threshold increases to 75 after level 3. Once you determine the frequency that the threshold rises, then you can come up with an algorithm to compute it, like the other folks are trying to do in their answers \$\endgroup\$ – Taegost Oct 29 '15 at 13:37
  • 3
    \$\begingroup\$ Majte gives a good answer for how to calculate it, but the "best" answer is simply not to calculate it.... store the overall exp, but also store the current level and XP delta. Reset the delta every time you level up and you have all the information you need (level, level+1, total xp, delta xp) to easily calculate anything you need to use/display \$\endgroup\$ – Jon Story Oct 29 '15 at 15:36
  • \$\begingroup\$ @JonStory Indeed. I elaborated on this a bit in my answer because, well, who actually calculates level dynamically all the time? This question is, in essence, just a math question, as it does not consider the role of levels within a game system at all. \$\endgroup\$ – zxq9 Oct 30 '15 at 4:22
33
\$\begingroup\$

When working out the maths and solving for the Level conditional on experience XP, we obtain:

$$Level = \frac{1 + \sqrt{1 + 8 \times XP \div 50}}{2}$$

For example, what is the player's level for \$XP = 300\$?

$$ \frac{1 + \sqrt{1 + 8 \times 300 \div 50}}{2} = 4 $$

As requested.

Or, what is the level for XP = 100000?

$$ \frac{1 + \sqrt{1 + 8 \times 100000 \div 50}}{2} = 63 $$

More generally expressed, for an arbitrary starting threshold at Level 1:

$$ Level = \frac{1 + \sqrt{1 + 8 \times threshold \div 50}}{2} $$

You can also do the reverse and calculate the XP needed for any given level by solving the above formula for XP.

$$ XP = \frac{(Level^2-Level) \times threshold}{2} $$

Note that the above formula works with fractions but you need to round down to the next integer value. For example in C++/C# you could use (int)Level.

To obtained the above closed form formula, I used difference equations, Gauss summation and a quadratic formula.

If you are interested in the solution of this formula step by step...

We do an recursive algorithm by starting our considerations that ultimately Experience(next_level) = Experience(current_level) + current_level*50.

For example, to obtain \$XP_{Level3}\$ we have:

$$ XP_{Level3} = XP_{Level2} + 2 \times 50 $$

Where, 2*50 comes from the OP's request that experience needed to reach the next level is current level*50.

Now, we substitute \$Xp_{Level2}\$ with the same logic into the formula. That is:

Substitute \$XP_{Level2} = XP_{Level1} + 2 \times 50\$ into the above formula:

$$ Xp_{Level3} = Xp_{Level1} + 1 \times 50 + 2 \times 50 $$

and \$ Xp_{Level1} \$ is just 50, which is our starting point. Hence

$$ Xp_{Level3} = 50 + 2 \times 50 = 150 $$

We can recognize a pattern for recursively calculating higher levels and a finite chain of summations.

$$ Xp_{LevelN} = 50 + 2 \times 50 + 3 \times 50 + ... + (N-1) \times 50 = \sum_{i=0}^{n-1} i \times 50$$

Where N is the level to be achieved. To get the XP for the level N, we need to solve for N.

$$ Xp_{LevelN} \div 50 = \sum_{i=0}^{n-1} i $$

Now the right hand side is simply a summation from 1 to N-1, which can be expressed by the famous Gaussian summation \$ N \times (N+1)\div2-N \$. Hence

$$ Xp_{LevelN} \div 50 = N(N+1) \div 2-N $$

or just

$$ 2*(Xp_{LevelN} - 50) \div 50 = N(N+1)-2N $$

Finally, putting everything on one side:

$$ 0 = N^2-N-2 \times Xp_{LevelN} \div 50 $$

This is now a quadratic formula yielding a negative and positive solution, of which only the positive is relevant as there are no negative levels. We now obtain:

$$ N = \frac{1 + \sqrt{\frac{1+4 \times 2 \times Xp_{LevelN}}{50}}}{2} $$

The current level conditional on XP and linear threshold is therefore:

$$ Level = \frac{1 + \sqrt{1+8\times XP \div threshold}}{2} $$

Note Knowing these steps can be useful to solve for even more complex progressions. In the RPG realm you will see besides a linear progression as here, the actually more common fractional power or square relationship, e.g. \$Level = \frac{\sqrt{XP}}{5.0}\$. However, for game implementation itself, I believe this solution to be less optimal as ideally you should know all your level progressions beforehand instead of calculating them at runtime. For my own engine, I use therefore pre-processed experience tables, which are more flexible and often faster. However, to write those tables first, or, to just merely ask yourself what XP is needed to, let's say, obtain Level 100, this formula provides the quickest way aimed at answering the OP's specific question.

Edit: This formula is fully working as it should and it outputs correctly the current level conditional on XP with a linear threshold progression as requested by the OP. (The previous formula outputted "level+1" by assuming the player started from Level 0, which was my erring--I had solved it on my lunch break by writing on a small tissue! :)

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Josh Oct 29 '15 at 16:20
  • \$\begingroup\$ @JoshPetrie The problem for us who just saw this question later, is that the chat link is broken. Any way of recovering it? \$\endgroup\$ – MAnd Nov 14 '15 at 8:33
  • \$\begingroup\$ @MAnd I undeleted it, but it will go away again on its own in another eight days or so. \$\endgroup\$ – Josh Nov 14 '15 at 16:17
25
\$\begingroup\$

The simple and generic solution, if you don't need to repeat this calculation millions of times per second (and if you do, you're probably doing something wrong), is just to use a loop:

expLeft = playerExp
level = 1
while level < levelCap and expLeft >= 0:
    expLeft = expLeft - expToAdvanceFrom(level)
    level = level + 1

if expLeft < 0: level = level - 1     # correct overshoot

The big advantage of this method, besides requiring no complicated mathematics, is that it works for any arbitrary exp-per-level function. If you like, you can even just make up arbitrary exp values per level, and store them in a table.

If you do (for some strange reason) need an even faster solution, you can also precalculate the total amount of exp needed to reach each level, store this in a table, and use a binary search to find the player's level. The precalculation still takes time proportional to the total number of levels, but the lookup then requires only time proportional to the logarithm of the number of levels.

\$\endgroup\$
  • 4
    \$\begingroup\$ Most flexible solution. And since speed doesn't matter for a one-time computation, best one i guess. \$\endgroup\$ – GameAlchemist Oct 28 '15 at 19:55
  • 4
    \$\begingroup\$ @Majte: Perhaps I wasn't clear enough. I'm not suggesting that any of the posted solutions would require "millions of iterations". What I meant to say is that, unless you somehow need to calculate the player's level millions of times per second, my (naïve brute-force) solution is more than fast enough. The other solutions, based on algebraically deriving a closed-form formula for the level as a function of exp, may be even faster -- but for code that's only rarely called (and anything less than, say, 1,000 times a second surely counts as "rare" here), it'll make no noticeable difference. \$\endgroup\$ – Ilmari Karonen Oct 28 '15 at 22:03
  • 2
    \$\begingroup\$ Ohh, I see now, sorry. I fully agree with you and you offer a great alternative for user defined advancement steps per level. But then, probably use preprocessed tables after all. \$\endgroup\$ – Majte Oct 28 '15 at 22:13
  • 2
    \$\begingroup\$ The simplicity of this solution makes it a clear winner. Do not discount the value of readability and maintainability. \$\endgroup\$ – Mauser Oct 29 '15 at 18:08
  • 1
    \$\begingroup\$ Computers are good at doing menial tasks, not people. You want to simplify the persons life, the programmer, at the expense of the computer if necessary. Using this solution, you only have to write one method, the forward, not the forward and reverse. The simplest solution is not the one he has in code, but building that lookup table. Ram is cheap, use it. \$\endgroup\$ – Mauser Oct 29 '15 at 20:04
11
\$\begingroup\$

The question has been answered with code, but I think it should be answered with math. Someone might want to understand instead of just copy and paste.

Your system is easily described by a recurrence relation: $$ \text{XP}_{\text{Level}+1} = \text{XP}_{\text{Level}} + \text{Level} \cdot \text{Threshold} $$

Which offers a nice simple closed form solution for \$\text{XP}\$:

$$\text{XP}_{\text{Level}} = \frac{(\text{Level}-1) \cdot \text{Level} \cdot \text{Threshold}}{2}$$

Which we can solve for \$\text{Level}\$:

$$\text{Level} = \left\lfloor \frac{\sqrt{\text{Threshold}^2 + 8 \cdot \text{XP} \cdot \text{Threshold}}}{2 \cdot \text{Threshold}}+\frac{1}{2} \right\rfloor$$

(truncate to integer, because the player needs all the required XP to get any of the level-up bonus)

\$\endgroup\$
  • 2
    \$\begingroup\$ I like this answer. Clear and concise. \$\endgroup\$ – Almo Oct 29 '15 at 15:02
  • \$\begingroup\$ Hey Mick; it's been a while since I did recurrence relations. Couldn't we also specify the base case XP_Level(0) = 50 and then we can just avoid solving? Any benefits, pros, cons? I think it'd be good to touch on this answer. +1 \$\endgroup\$ – Vaughan Hilts Oct 30 '15 at 6:50
  • \$\begingroup\$ @VaughanHilts I'm not sure how your notation works or what you're asking, feel free to ping me in gamedev chat? \$\endgroup\$ – MickLH Oct 30 '15 at 16:50
  • \$\begingroup\$ I understood the code answer much easier than this. \$\endgroup\$ – Pharap Apr 12 '16 at 6:33
  • \$\begingroup\$ Keep working at it @Pharap. When I was a teenager I also understood code more easily than math, but with experience and knowledge the math will become obvious everywhere in life. \$\endgroup\$ – MickLH Apr 12 '16 at 11:07
10
\$\begingroup\$

Here's one approach to solving the problem using basic algebra. If you don't care about the steps, skip to the bottom.

An easy thing to come up with is, given a level n, the total experience e needed to obtain that level:

e = sum from k=1 to n of (t(k-1))

The t term stands for the increase in XP needed per level - 50, in the example.

We can solve the above using the formula for arithmetic sequences (sum identity):

e = t/2 * n(n-1)

However, we want the opposite formula - the player's level given their total experience. What we really want to do is solve for the level, n. First, let's group the terms:

n^2 - n - 2e/t = 0

Now we can use the quadratic formula:

n = (1 + sqrt(1+8e/t))/2

Final equation:

level = 0.5 + sqrt(1 + 8*(total experience)/(threshold)) / 2
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the answer. But what if I want to change the Threshold to other variable? Instead of 50 I would like to use 50000 or 1000 0for that matter. How should I modify the equation? \$\endgroup\$ – JayVDiyk Oct 28 '15 at 15:57
  • 2
    \$\begingroup\$ Yes, the solutions should be the same. I wanted to lay out the steps to the solution in case anyone was interested. @JayVDiyk - will edit post. \$\endgroup\$ – Chaosed0 Oct 28 '15 at 16:30
  • \$\begingroup\$ That was a bit cheeky of you, as I commented that I'll post the full solution after work ;) it's ok, I dont mind. The usual thing is to answer with a reference to the correct answer and note down the extention. Nerver mind, loved to have solved it. Wish more questions like that were posted here. \$\endgroup\$ – Majte Oct 28 '15 at 17:01
  • \$\begingroup\$ Sorry, must have missed that comment. Didn't mean to steal it out from under you or anything like that - I'll keep it in mind next time. Your answer is definitely more thorough than mine is after the edit! \$\endgroup\$ – Chaosed0 Oct 28 '15 at 19:57
  • 1
    \$\begingroup\$ +1; with no offense to @Majte intended, I personally find your explanation more readable. \$\endgroup\$ – Ilmari Karonen Oct 29 '15 at 12:57
3
\$\begingroup\$

All the math involved here is very important to know for all sorts of reasons, some of them applicable to game development.

BUT

This is a game development site, not a math site. So let's discuss how these things work not as algorithmic series, but as sets, because that is the sort of math that applies to leveling in games you might actually develop to sell, and this is the system that underlies most (but not all) leveling systems (at least historically).

Players tend to prefer nice, round numbers that are easy to remember and visualize, and nowhere is this more important than in a level-based game system where the player need X amounts of xp to advance to level Y.

There are two good reasons for picking round numbers:

  • The level experience itself is a nice, round number "100; 200; 1,000,000; etc."
  • The delta between levels tends to be another nice, round number the player can glance at and calculate in his head.

Round numbers are enjoyable. The purpose of games is to be enjoyable. Pleasantness is important, especially since the game dilemmas will often be anything but pleasant by design.

Why is this important to keep in mind?

Most compound series algorithms do not produce nice, round numbers

Most series do not stop at a pretty point (every answer I've seen here so far just goes on forever). So, what do we do? We approximate, and then we determine what set of levels should apply to the game system.

How do we know what approximations are appropriate? We consider what the point of leveling is within the game system.

Most games have level caps that kick in at some point. There are a few ways this can play out:

  • The cap is encountered relatively early, where the level system only exists to help players get through the first phase of the game in a focused way to force them to learn the complete game system. Once they are "fully grown" the long-game begins.
  • XP gain VS the difficulty level has a certain economy to it where yes, there is a level cap, but it is so far away that we expect players to complete the game about halfway through the leveling chart. In DQ/FF-style RPGs with multiple characters/classes it is more common to have different characters/classes be made to level easier by gaining experience at different rates than changing the required XP for each level per character class. That way players can easily remember the cute little round numbers as universal goals, and know that each character progresses toward them at some arbitrary rate set by the game system (XP + (XP * Modifier) or whatever).
  • Level caps are based on external character category. That is, some factor outside the game system proper dictates what the level system looks like. This is becoming more common as many games are pay-to-win but free-to-play. A free player may be capped at lvl 70, a subscriber may be capped at lvl 80, a one-time purchase may advance someone a level beyond some universal cap, etc.
  • Level caps are universal and tied to the game world in some way. This system has been popularized by WoW.
  • Any other level cap system you might dream up that enhances gameplay in a smarter way than simply rewarding players for wasting more minutes of their life in your made-up world than the other players.

There are some game systems where there is no level cap and the system is algorithmically determined. Usually systems like this use some X-powers-of-Y system to make the numbers explode quickly. This makes it very easy to get to level L-1, reasonably expected that most players will get to level L, inordinately difficult to get to level L+1, and players will grow old and die before reaching L+2. In this case "L" is a level you have decided is the target level appropriate for play and at which normally would have capped the system but leave the option open for people to delude themselves into thinking its a good idea to XP forever. (Sinister!) In this sort of system the math found here makes perfect sense. But it is a very narrow, and rarely encountered case in actual games.

So what do we do?

Calculate the levels and XP? No. Determine the levels and XP? Yes.

You determine what levels mean, then decide what the available set of levels should be available. This decision comes down to either granularity within the game system (Is there a huge difference in power between levels? Does each level confer a new ability? etc.) and whether or not levels are used themselves as a gating system ("Can't go to the next town until you're lvl 10, kid.", or a competitive ladder system enforces level-based tiers, etc.).

The code for this is pretty straightforward, and is just range determination:

level(XP) when XP < 100  -> 1;
level(XP) when XP < 200  -> 2;
level(XP) when XP < 500  -> 3;
level(XP) when XP < 1000 -> 4;
% ...more levels...
level(XP) when XP > 1000000 -> 70. % level cap

Or with an if statement, or a case, or a chain of if/elif, or whatever the language you happen to be using supports (This part is the least interesting element of any game system, I just provide two ways because I happen to be in Erlang mode right now, and the above syntax may not be obvious to everyone.):

level(XP) ->
    if
        XP < 100  -> 1;
        XP < 200  -> 2;
        XP < 500  -> 3;
        XP < 1000 -> 4;
        % ...more levels...
        XP > 1000000 -> 70 % level cap
    end.

Is it amazing math? No. Not at all. Is it manual implementation of set element determination? Yep. That's all it is, and this is pretty much the way I've seen it actually done in most games throughout the years.

As a side note, this should not be done every time the player gains experience. Usually you keep track of "XP to go" as one value, and once the player either exhausts or surpasses the "to go" value (whichever way you're doing it) then you calculate this once to figure out where the player is really at, store that, calculate the next "to go" minus the leftover (if carrying XP forward is allowed) and repeat.

\$\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.