CODEWITHSUNDEEP
c#math
Throneos
Throneos

Reputation: 47

Calculation position in Fibonacci order

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

Upvotes: 2

Views: 366

Answers (2)

just.another.programmer
just.another.programmer

Reputation: 8805

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

Forumula

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;
}

Upvotes: 1

xdtTransform
xdtTransform

Reputation: 2057

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);

Upvotes: 1

Related Questions