Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
    
Related, possibly a duplicate: gamedev.stackexchange.com/questions/974/… –  coderanger Oct 3 '10 at 20:25
    
Any particular language? –  Cyclops Oct 3 '10 at 21:24
    
@coderanger, the link you have provided is a design issue. My question is programming related. –  Extrakun Oct 4 '10 at 5:34
    
PHP. Made an edit to reflect this in the question –  Extrakun 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. –  dlras2 Jul 2 '11 at 6:05

5 Answers 5

up vote 28 down vote accepted

You're asking the wrong question.

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.

share|improve this answer
4  
There's lot of truth in your comment. –  Extrakun Oct 4 '10 at 7:58
4  
+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. –  Extrakun Oct 4 '10 at 12:12
2  
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? –  Lohoris 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[6], then I'm level 6. Keep looping until you find your new current level. –  dash-tom-bang 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.

share|improve this answer

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.

share|improve this answer
1  
Hardcoding pointer offsets is bad practice, especially in example code handed to novice programmers. Use sizeof please. :) –  user744 Oct 3 '10 at 19:46
1  
I would have, but that's an implementation detail, and bloats the example, distracting the reader from its purpose. –  Peter Alexander Oct 3 '10 at 19:55
3  
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 :-) –  Peter Alexander Oct 3 '10 at 19:57
5  
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.

share|improve this answer

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.

share|improve this answer
    
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? –  dcarrigg 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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