1

I have an algorithm question related to XP levels in games:

I have a table that lists level numbers, and number of XPs in that level:

GameLevel    ExperiencePointsInLevel
1            30
2            70
3            160
4            250

For each player, I only maintain their total XP, not any level info. Given a player's total XP, how do I determine the following via an algorithm (I'm using C# & LINQ)?

  1. Current level of person
  2. Number points the person has in this level

For example, if a player has 110 XPs, the answer would be:

  1. Level 3
  2. 10 XPs; (110-30-70 = 10)

Any ideas?

Cheers,

Dean

2
  • Why would you not maintain a record of what level they are at? The algorithm is to start at level 1, see if the XP achieve is less that this and if not subtract it, take the remainder and move on to the next level and repeat until you find that there are less XP remaining than required for the next level advancement. At that point you have the achievement within the level.
    – Lazarus
    Jul 13, 2011 at 12:07
  • Are you using EF or LINQ2SQL? I don't think you are using both in your project - but the tags on your question implies that... Jul 13, 2011 at 12:08

3 Answers 3

2

If experience points in level is changed to represent the total XP a player needs to reach that level.

Game Level    Experience Points
 1             0
 2             100
 3             200
 4             400

A more functional approach with LINQ would be something like the following:

var playerlevel = ExperiencePointsTable
    .Where(xpt => xpt.ExperiencePointsInLevel <= player.ExperiencePoints)
    .Select(xpt => xpt.GameLevel)
    .Max();

I think this simplifies the solution and avoids having to generate arrays for a look up.

Edit: fixed to check less than or equal to level.

To find out how many xp the player has to get to the next level you can use a similiar LINQ query.

var xpToNextLevel = (ExperiencePointsTable
    .Where(xpt => xpt.ExperiencePointsInLevel > player.ExperiencePoints)
    .Select(xpt => xpt.ExperiencePoints)
    .Min()) - player.ExperiencePoints;
1
  • In this case, how would I determine the max points in this level? for example, if a player has 240 points, he is in level 3, has 40 points in this level, and has 40 out of 200 (400-200) points in this level.
    – netwire
    Jul 15, 2011 at 1:12
2

You can keep a list of the upper inclusive bound of each level (Level 1: 0-29, Level 2: 30-99, etc.) and perform a binary search for the input value:

var levels = new int[]
{
    0 - 1,
    30 + 0 - 1,
    70 + 30 + 0 - 1,
    160 + 70 + 30 + 0 - 1,
    250 + 160 + 70 + 30 + 0 - 1
};

var input = 110;

var level = Array.BinarySearch(levels, input);
if (level < 0)
    level = ~level;

Console.WriteLine("Level: {0}", level);
Console.WriteLine("Points: {0}", input - (levels[level - 1] + 1));

(untested; may contain off-by-one errors)

0
0

If the table is sorted, then do something like this:

foreach(DataRow row in table.Rows)
{
    if(xp > (int)row["XP"])
    {
        xp -= (int)row["XP"];
    } else {
        Console.WriteLine("Level: " + row["Level"] + " with " + xp + " xp");
        break;
    }
}

Same idea with whatever data structure you're using

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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