Calculation position in Fibonacci order

Question

I want to programm a level system for a small game. The level system would be tied to the score and the levels would get further appart only 2 score values are given

lvl, score
0, 50 (from 0 - 50)
1, 100 (from 51 to 100)
2, 150
3, 250
4, 400
5, 650
...

How could I elegantly calculate witch level I am in with a given score and 2 start values (50 and 100 in the example)

Or is it best to just calculate the score values in a list or array

Don't know any formula to reverse Fibonacci, personally. Given that you're probably not working with hundreds of thousands of levels, it's probably loads easier to either just precalculate them to the max level in your game, or just calculate Fibonacci numbers until the point where you reach the given score. — Nyerguds, Aug 06 '19 at 06:51
The number grow pretty big pretty fast. Could we simply store the value in an array? — xdtTransform, Aug 06 '19 at 06:52
Question: By "_ elegantly calculate_", you mean simple as a LinQ, Or brain teaser like an Binary search with a comparer? — xdtTransform, Aug 06 '19 at 07:33
This problem is sometimes called "the fibonacci logarithm" and is addressed in the wikipedia article. — President James K. Polk, Aug 06 '19 at 22:00

just.another.programmer · Answer 1 · 2019-08-08T11:31:33.550

There's actually a formula to calculate Fibonacci numbers. That can be transformed into an algorithm to find the index of any given Fibonacci number. There's an example of how to do this in C# here.

You need to adapt that formula for use with your initial conditions of 50 and 100.

I asked a question over on Mathematics SE for help adjusting the original forumula and they suggested using

It's pretty easy to implement this as a C# method.

public int GetScoreIndex(int score)
{
    const double phi = 1.61803398875;
    const double rad5 = 2.2360679775;

    var preLog = (score / 50) * rad5 + (1/2);
    var log = Math.Log(preLog, phi);
    var floor = (int) Math.Floor(log);
    var index = floor - 1;

    return index;
}

xdtTransform · Accepted Answer · 2019-08-06T11:19:23.280

1

With out any formula you can simply compute the whole table in a flash (under 0.0002 sec on a core2). Summing int is pretty fast. That's only 36 computation before hitting the max on int32.

var scoreTable = new []{50, 100, 150, 250, 400, 650, 1050, 1700, 2750, 4450, 7200, 11650, 18850, 
30500, 49350, 79850, 129200, 209050, 338250, 547300, 885550, 1432850, 2318400, 3751250, 
6069650, 9820900, 15890550, 25711450, 41602000, 67313450, 108915450, 176228900, 
285144350, 461373250, 746517600, 1207890850, 1954408450};

For the math to create the table, let's be simple:

var thresholds = new List<int> {50, 100};  
var index = 1;
while(true){
  var temp = thresholds[cpt] + thresholds[cpt - 1];
  if (temp < 0) break;
  thresholds.Add(temp);
}

And to know the level:

var score = 51;
// Index is Zero-based numbering. Count is One-based. Index = Count -1;
var level = scoreTable.Where(x => x < score ).Count() - 1;

Binary.Search:

public class SupComparer : IComparer
{
    public int Compare(object x, object y)
    {
        var t1 = UInt64.Parse(x.ToString());
        var t2 = UInt64.Parse(y.ToString());
        return  t1.CompareTo(t2) > 0 ? 1 : 0;
    }
}

var cp = new SupComparer();
var level = Array.BinarySearch(scoreTable, score, (IComparer)cp);

edited Aug 06 '19 at 11:19

answered Aug 06 '19 at 07:08

xdtTransform

1,986
14
34

@Nyerguds, for Generating the int32 table? He will only generate the table once. But if he needs bigger score, yes. – xdtTransform Aug 06 '19 at 07:42
Yes. If you need to go higher than level 36, you shouldn't generate an `Int32` table at all. You should generate an `Int64` table. Though given how it scales, this whole levelling method might be ill-advised; it does indeed go to ridiculously high required scores really fast. – Nyerguds Aug 06 '19 at 07:44
@Nyerguds, Int64 => 82 levels in 00:00:00.0000040 sec. For more level it's time to hit the UInt64 => 134217728 levels in 00:00:05.3629467. – xdtTransform Aug 06 '19 at 07:47
Oh, I wasn't arguing processing time. But these are the kinds of numbers that stop having a meaning when people look at them. They're just too high. Ah well, that's OP's responsibility/problem. – Nyerguds Aug 06 '19 at 07:48
@Nyerguds, I know . 36 level was short. But int64 is only 82. While UInt64 give more level to clear! 134_217_728 ! – xdtTransform Aug 06 '19 at 07:53

Calculation position in Fibonacci order

2 Answers2