# Algo for given an amount of XP, find a character's level

In a RPG context, what are the ways to quickly find a character's level, given his XP? There are two cases which I am looking at:

1. For when a formula is defined, like in the case of D&D, which is N = N*(N-1)*500, where N is the desired level.
2. When no formula is defined, each level has an amount of XP require which is defined by a table.

I guess the easiest way is to do a for loop and subtracting the XP required for that level from the character's XP pool, till he reaches a point where you can't attain the next level. What other ways are there to, given a character's XP, to find his level?

Edit: The language is PHP

• Related, possibly a duplicate: gamedev.stackexchange.com/questions/974/… Oct 3 '10 at 20:25
• Any particular language? Oct 3 '10 at 21:24
• @coderanger, the link you have provided is a design issue. My question is programming related. Oct 4 '10 at 5:34
• PHP. Made an edit to reflect this in the question Oct 4 '10 at 7:55
• Just so you know, the actual level progression (XP requirements, feat gain, etc.) for D&D is not OGL, and technically shouldn't be published anywhere but their books. Jul 2 '11 at 6:05

The right question is "will this ever be a bottleneck in my game". The answer to that, I can nearly guarantee, is "no". It will not be. You can implement this in the simplest most braindead manner and it will never use more than 0.01% of your game's CPU, most likely vastly less than that.

Loop through levels 1 through MAX_LEVEL, find the first level with a higher XP requirement than the player has. There ya go.

You're making a game, not a technology showcase. Make it work, don't agonize over every cycle.

• There's lot of truth in your comment. Oct 4 '10 at 7:58
• +1 because it's true, but makes me sad that I once did find a "get the current level" function in our engine that took about 3% of our frame time. Mostly because it did a deep copy of every item the player had.
– user744
Oct 4 '10 at 8:30
• On the other hand, this is on a PHP server; In the end only profiling will shed light on where the bottleneck is. Oct 4 '10 at 12:12
• totally +1: KISS. One single bug will be much worse for you then the good that will come from all these micro-optimizations. And if you micro-optimize everything like that, you'll most certainly generate at the very least one single bug, won't you?
– o0'.
Oct 4 '10 at 14:58
• Also it's not like you need to determine the current level all of the time. Just check to see if the current XP is more than the threshold for the NEXT level, starting from the current level that you've stored somewhere. I.e. I'm level 5. If my XP is greater than or equal to xpTable, then I'm level 6. Keep looping until you find your new current level. Oct 7 '10 at 0:17

The RPG I worked on stored both the level as well as the current percentage to next level, instead of just a raw XP amount on the player. We did this so that if we ever wanted to change the values in the experience tables, the player wouldn't see a sudden drop or rise in level.

For instance, imagine your player has 1000 XP, which is enough to make him 50% through 3rd level. If we were to suddenly make it so that 1000 XP is actually only 90% through 1st level, the next time the player plays the game you would need to level the character back down to 1st level.

As experience is earned, you can add the percentage amount of experience to the player's current XP percentage. Most RPGs are actually designed so that the amount of experience given for an encounter is easily converted to this percentage. If the percentage is ever greater than 100%, increment the level of the player, subtract 100% away from the experience, and for the extra amount over 100% give them something like:

currentXPPercentage = ((Amount over 100%) * (Amount over 100% * Total XP for Previous Level)) / (Amount over 100% * Total XP for Previous Level)


...in the end, if you did it that way you'd be storing the player's current level. Yay for no for loop to determine players level.

If the formula is defined, just invert the formula to find the xp-to-level conversion. If you can't invert the formula, then use a binary search to find the level. This assumes that more xp always correlates with a higher level, but I think this is a safe assumption for most levelling systems :)

If you have a table instead (and you are using C++) then you can use std::lower_bound to find the corresponding level for XP:

const int numLevels = 6;
int xpForLevel[numLevels] = {100, 200, 400, 800, 1600, 3200};
int* it = std::lower_bound(xpForLevel, xpForLevel + numLevels, xp);
int level = it - xpForLevel;


This will work in O(log(n)) time for n levels, so it's fast enough for pretty much any use.

Note, if the given xp is less than that required for the lowest level, then lower_bound will return xpForLevel + numLevels.

If you want to find the XP required for the next level up, use upper_bound.

• Hardcoding pointer offsets is bad practice, especially in example code handed to novice programmers. Use sizeof please. :)
– user744
Oct 3 '10 at 19:46
• I would have, but that's an implementation detail, and bloats the example, distracting the reader from its purpose. Oct 3 '10 at 19:55
• You could also argue that this should be in its own function, and the levels should have their own class etc. etc. -- I just want to show people how to use the function; good coding practice can be left for another question :-) Oct 3 '10 at 19:57
• If you want to avoid implementation details, don't give answers in C++. ;)
– user744
Oct 4 '10 at 8:26
1. For when a formula is defined, like in the case of D&D, which is Experience = Level*(Level-1)*500

I agree that you should implement what is easiest, rather than worrying about performance, because cases like this will have little or no performance impact either way. However, in this case, it would be easier to just solve the equation for Level using high-school algebra, rather than take the time to code a lookup table as suggested by everyone else.

That specific equation can be solved using the quadratic formula.

Why not use a keypair dictionary to save the level and experience points needed for a given level. Then when you want to find out the level according to experience just ask if the current XP is higher or lower from the closest keypair value.

Once you reach a point where the value is right between two keypairs you know what level you are.

• This way would be slower than just doing what the OP said with a loop and subtracting. Assuming you're doing a for loop except instead of a subtraction you're doing a table lookup within it (n*logn instead of just n). Were you thinking of some other way? Oct 3 '10 at 16:23
• The performance hit is negligible. He should be focusing on clean code that is understandable at a moments view for something this trivial.
– Sergio
Oct 4 '10 at 16:13