The perfect experience / level curve

I was recently tasked to create a required-experience-per-level table for a game – that is, create a table which indicates how many experience points the player must earn to progress to a certain experience level. The requirement to reach the next level must continuously increase (the “double derivate” must be non-negative). Of course, it is easy to come up with a function to satisfy that requirement alone, but what about generating a level curve that’s also aesthetic? I mean, it’s much nicer to look forward to reaching 15000 points than, say, 16384.

So, I wrote a small program to attempt to generate experience ranks with the following properties:

  1. Continuous acceleration
  2. Smoothness (calculated as “roughness”, using the sum of squares of the “triple-derivate”)
  3. Roundness (100 is more round than 150, 150 is more round than 160, 160 is more round than 165 etc.)
  4. Emphasis on the roundness of the last level

The qualifying factor here is smoothness vs. roundness. Here are two sample outputs for 19 levels (actual output multiplied by 100):

Level Smoother Rounder
1 0 0
2 100 100
3 400 300
4 1000 600
5 2000 1000
6 3200 2100
7 5000 3500
8 7500 5000
9 11000 7000
10 15000 10000
11 20000 15000
12 26000 22000
13 33000 30500
14 41000 40000
15 50000 50000
16 60000 61000
17 71500 73000
18 85000 86000
19 100000 100000

The code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define N 19

#define FACTOR_RANK_ROUNDNESS 50
#define FACTOR_LAST_RANK_ROUNDNESS (FACTOR_RANK_ROUNDNESS*10)
#define MAX_MUTATIONS 3
#define ITERATIONS 50000000

int roundness(int n)
{
	if (n == 0)
		return -1000;
	while (n && n%10==0)
		n = n/10;
	if (n==1)
		return 2;
	int r = 2;
	if (n%10 == 5)
		r++;
	while (n)
		n = n/10, r-=2;
	return r;
}

int sqr(int x) { return x*x; }

struct P
{
	int dd[N];
	int d[N];
	int n[N];

	__forceinline int fitnessA()
	{
		int total = 0;
		for (int i=1; i<N-1; i++)
			total += roundness(n[i]) * FACTOR_RANK_ROUNDNESS;
		total += roundness(n[N-1]) * FACTOR_LAST_RANK_ROUNDNESS;
		return total;
	}

	__forceinline int fitnessB()
	{
		int total = 0;
		for (int i=1; i<N; i++)
			total -= sqr(abs(dd[i] - dd[i-1]));
		return total;
	}

	int fitness()
	{
		return fitnessA() + fitnessB();
	}

	void populate()
	{
		for (int i=0; i<N; i++)
			dd[i] = i;
	}

	void update()
	{
		d[0] = 0;
		for (int i=1; i<N; i++)
			d[i] = d[i-1] + dd[i];
		n[0] = 0;
		for (int i=1; i<N; i++)
			n[i] = n[i-1] + d[i];
	}

	void mutate()
	{
		int mutations = 2 * (1 + rand() % MAX_MUTATIONS);
		for (int m=0; m<mutations; m++)
		{
			int i = 1 + rand()%(N-1);
			int n = dd[i];
			if (n == 0)
				dd[i]++;
			else
				dd[i] += (rand()%n) - (n/2);
				//dd[i] = rand()%(n*2);
		}
	}

	void print()
	{
		printf("%d,%d - [", fitnessA(), fitnessB());
		for (int i=0; i<N-1; i++)
			printf("%d,", n[i]);
		printf("%d]\n", n[N-1]);
	}
};

P p, n;

int main()
{
	int fb, fp, fn;
	fb = INT_MIN;

	srand(time(NULL));

	while (true)
	{
		p.populate();
		p.update();
		fp = p.fitness();

		int iterations = 0;

		while (iterations < ITERATIONS)
		{
			n = p;
			n.mutate();
			n.update();
			fn = n.fitness();
			if (fn > fp)
			{
				p = n;
				fp = fn;
				iterations = 0;
			}
			else
				iterations++;
		}
		if (fp >= fb)
		{
			p.print();
			fflush(stdout);
			fb = fp;
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *