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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.