CyberShadow’s blog

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

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