Planet generating algorithm

Information, contacts and source code for ports to Linux, Windows, etc.

Moderators: another_commander, winston

Post Reply
RobertK
Poor
Poor
Posts: 7
Joined: Mon Sep 03, 2018 11:06 am

Planet generating algorithm

Post by RobertK »

First of all: thanks to the Oolite team for their detailed explanation of the planet generating algorithm (here and here).

I have started building a little "planet browser" for the Sinclair ZX81 (which of course is not really a "port" of Oolite, but I hope my thread somehow fits into this sub-forum). A few things are still not clear to me, maybe these could be further explained in the Wiki:


1. Planet Names: why are some of the two-character parts left out? See for example the second planet "QUBE": the second part of the name has the value 0 and is therefore empty, that's clear. But the fourth part in the w2 hsb would be 1101 (decimal 13), which would be "DI". How do you decide that this part is not included in the planet's name?


2. Planet radius: according to the wiki, for the first planet TIBIDIED it should be 256*(11+7) = 4608. The original BBC game and Oolite show this value as 4610 (obviously rounded).
The Elite DOS games (Elite and Elite Plus) show the radius of TIBIDIED to be 7103 km. I would like to optionally generate the DOS radius value. Has someone already figured out how to do this?

BTW, the Amiga version shows the radius of TIBIDIED to be 38114 km, which seems quite uncomfortable for an earthling like me (too much gravity :wink:)...


3. The following values are not explained in the wiki:

Tech. Level
Population
Inhabitants Type
Productivity

Can you please explain what bit patterns are used to determine these values?


Many thanks in advance.
Robert (Commander, Rating Harmless)
another_commander
Quite Grand Sub-Admiral
Quite Grand Sub-Admiral
Posts: 6547
Joined: Wed Feb 28, 2007 7:54 am

Re: Planet generating algorithm

Post by another_commander »

Hi and welcome. Sorry for the delayed reply, but Oolite has moved away from the procedural planet data generation since version 1.82, so I had to go back and find the source code of v1.80 in order to help you with your questions. Unfortunately, with 1.80 being so old, it is a bit difficult to test stuff. So I will just provide the relative algorithms here and I hope they will be of help.

So, the name generation was handled by the generateSystemName method, which reads as follows:

Code: Select all

- (NSString *) generateSystemName:(Random_Seed) s_seed
{
	int i;
	
	NSString			*digrams = [self descriptionForKey:@"digrams"];
	NSString			*apostrophe = [self descriptionForKey:@"digrams-apostrophe"];
	NSMutableString		*name = [NSMutableString string];
	int size = 4;
	
	if ((s_seed.a & 0x40) == 0)
		size = 3;
	
	for (i = 0; i < size; i++)
	{
		NSString *c1, *c2;
		int x = s_seed.f & 0x1f;
		if (x != 0)
		{
			x += 12;	x *= 2;
			c1 = [digrams substringWithRange:NSMakeRange(x,1)];
			c2 = [digrams substringWithRange:NSMakeRange(x+1,1)];
			[name appendString:c1];
			if (![c2 isEqual:apostrophe])		[name appendString:c2];
		}
		rotate_seed(&s_seed);
	}
	
	return [name capitalizedString];
}
It looks that things might get dropped under certain conditions related to the system seed a and f components, as well as when the second character of the selected digram is the apostrophe.

The rest of the system parameters were calculated in the generateSystemData method using the system seed in the following way:

Code: Select all

OOGovernmentID government = (s_seed.c / 8) & 7;
	
OOEconomyID economy = s_seed.b & 7;
if (government < 2)
	economy = economy | 2;

OOTechLevelID techlevel = (economy ^ 7) + (s_seed.d & 3) + (government / 2) + (government & 1);
	
unsigned population = (unsigned)(techlevel * 4) + government + economy + 1;

unsigned productivity = ((economy ^ 7) + 3) * (government + 4) * population * 8;
	
unsigned radius = (((s_seed.f & 15) + 11) * 256) + s_seed.d;
Hope this helps. Feel free to ask if something requires further clarification.
RobertK
Poor
Poor
Posts: 7
Joined: Mon Sep 03, 2018 11:06 am

Re: Planet generating algorithm

Post by RobertK »

Thanks, that helps a lot! Now I know why I couldn't find anything helpful in the current Oolite source.

Could you please explain what parts of the seed values w0, w1 and w2 the s_seed.a through s_seed.... values correspond with? I assume that each one is either the hsb or lsb of one of the three seed words, but in what order?

The planet radius is clear now, as I can see you have to add the planet's x variable. So it goes like this:
TIBIDIED:
256*(11+7)+2 = 4610
QUBE:
256*(11+10)+152 = 5528

Population and Productivity are easy to calculate as they are simply based on the other values.

And can you please search the old source for how the Inhabitants Type (e.g. "Human Colonials") is determined?
another_commander
Quite Grand Sub-Admiral
Quite Grand Sub-Admiral
Posts: 6547
Joined: Wed Feb 28, 2007 7:54 am

Re: Planet generating algorithm

Post by another_commander »

Not really sure what the w0, w1 etc. refer to. Not sure about the correspondence, as I am not famiiar with the old Elite code.

Regarding the second question, here is the source of the method that was doing the system descriptions in 1.80. The arrays under the system_description container array in descriptions.plist were used to build up the system description phrase.

Code: Select all

NSString *OOExpandDescriptionString(Random_Seed seed, NSString *string, NSDictionary *overrides, NSDictionary *legacyLocals, NSString *systemName, OOExpandOptions options)
{
	if (string == nil)  return nil;
	
	OOStringExpansionContext context =
	{
		.seed = seed,
		.systemName = [systemName retain],
		.overrides = [overrides retain],
		.legacyLocals = [legacyLocals retain],
		.isJavaScript = options & kOOExpandForJavaScript,
		.convertBackslashN = options & kOOExpandBackslashN,
		.useGoodRNG = options & kOOExpandGoodRNG
	};
	
	// Avoid recursive %I expansion by pre-seeding cache with literal %I.
	if (options & kOOExpandDisallowPercentI) {
		context.systemNameWithIan = @"%I";
	}
	
	OORandomState savedRandomState;
	if (options & kOOExpandReseedRNG)
	{
		savedRandomState = OOSaveRandomState();
		OOSetReallyRandomRANROTAndRndSeeds();
	}
	
	NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
	NSString *result = nil, *intermediate = nil;
	@try
	{
		// TODO: profile caching the results. Would need to keep track of whether we've done something nondeterministic (array selection, %R etc).
		if (options & kOOExpandKey)
		{
			intermediate = ExpandStringKey(&context, string, kStackAllocationLimit, kRecursionLimit);
		}
		else
		{
			intermediate = Expand(&context, string, kStackAllocationLimit, kRecursionLimit);
		}
		if (!context.hasPercentR)
		{
			result = intermediate;
		}
		else
		{
			result = ExpandPercentR(&context, intermediate);
		}
	}
	@finally
	{
		[context.systemName release];
		[context.overrides release];
		[context.legacyLocals release];
		[context.systemNameWithIan release];
		[context.randomNameN release];
		[context.randomNameR release];
		[context.systemDescriptions release];
	}
	
	if (options & kOOExpandReseedRNG)
	{
		OORestoreRandomState(savedRandomState);
	}
	
	result = [result copy];
	[pool release];
	return [result autorelease];
}
The string that sets the description domino going is in descriptions.plist: "system-description-string" = "[14] is [22].";. This, together with the system seed is passed to the above method for expansion.
RobertK
Poor
Poor
Posts: 7
Joined: Mon Sep 03, 2018 11:06 am

Re: Planet generating algorithm

Post by RobertK »

Sorry for the late reply, I was busy with other projects.

Thanks, I didn't notice that the inhabitants type is expanded just like the planet description string, I thought these were simply constant values.

Finally, could you please check the old source once more and tell me how seed.a through seed.f are initialized when the sequence starts at the first planet (Tibedied) of the first Galaxy?

That should clarifiy how these compare to the seed words w0, w1 and w2 from the Wiki description.
User avatar
Getafix
Quite Grand Sub-Admiral
Quite Grand Sub-Admiral
Posts: 979
Joined: Tue Apr 01, 2008 12:55 pm
Location: A small ice asteroid, orbiting Oresrati in Galaxy 8 (a.k.a. northwest Armorica).
Contact:

Re: Planet generating algorithm

Post by Getafix »

Hi Robert,

till a_c comes in, feel free to check our previous releases archives, where source code is also available. 8)
"Any sufficiently advanced information is indistinguishable from noise." [Newman, Lachmann, Moore]
RobertK
Poor
Poor
Posts: 7
Joined: Mon Sep 03, 2018 11:06 am

Re: Planet generating algorithm

Post by RobertK »

Thanks, I've found it now in the 1.80 source:

In Universe.m in keyForPlanetOverridesForSystemSeed:

Code: Select all

Random_Seed g0 = {0x4a, 0x5a, 0x48, 0x02, 0x53, 0xb7};
In the wiki description (w0 / w1 / w2):

Code: Select all

w0 = 5A4A , w1 = 0248 , w2 = B753
Therefore it goes like this:

w0 => seed.b seed.a
w1 => seed.d seed.c
w2 => seed.f seed.e

Many thanks!
RobertK
Poor
Poor
Posts: 7
Joined: Mon Sep 03, 2018 11:06 am

Re: Planet generating algorithm

Post by RobertK »

I think that I will need your help one more time...

My "Elite Planet Browser" is basically complete now and running on 40 different systems, the only thing that's left to be done is the planet description string.

I understand the basic concept: it all starts with "[14] is [22]", and each [..] is expanded using "system_description" from descriptions.plist, returning either a string or recursively leading into another expansion.

But I still haven't figured out how exactly the pseudo-random index (based on the planet seed) for which of the five description items to use is calculated - the way I do it leads to wrong values.

Let's take a look at QUBE, the second planet of the first galaxy. Its description string is:

"Qube is reasonably well known for its great dense forests but scourged by deadly civil war."

So the indices should be like this (the value on the right), I assume that the expansion is done in this order:

Code: Select all

"[14] is [22]"

( // [14]				--> 0
	"%H",
	"The planet %H",
	"The world %H",
	"This planet",
	"This world"
),

( // [22]				--> 3
	"[1] [0] for [9]",
	"[1] [0] for [9] and [9]",
	"[7] by [8]",
	"[1] [0] for [9] but [7] by [8]",
	"a[15] [16]"
),

[1] - resonably				--> 3
[0] - well known			--> 2
[9] - "its [2] [3]" 			--> 0

[2] - great				--> 2
[3] - "[19] forests"			--> 3

[19] - dense				--> 1

[7] - scourged				--> 4

[8] - "[21] civil war"			--> 0

[21] - deadly				--> 4

What I do is: I first set up the separate description seed just as it is done in OOLite 1.80 in seed_RNG_only_for_planet_description(). Then I repeatedly call the gen_rnd_number() function which is almost an exact copy of the function from the OOLite 1.80 source. This function returns a pseudo-random index and rotates the description seed. I expected to get the values shown above, but what I get is this:

Image

The resulting index is the value in the middle, which is the value in parentheses modulo 5.

Here is my code just in case that any of you want to take a look at it. For the planet seed I am using the w0 /w1 / w2 notation from the Wiki page, see my posting above.

Code: Select all

...

// Seed variables
int w0;
int w1;
int w2;
// Extra seed variables used for the planet description
int rnd_seed_a; // = s_seed.c;
int rnd_seed_b; // = s_seed.d;
int rnd_seed_c; // = s_seed.e;
int rnd_seed_d; // = s_seed.f;

int gen_rnd_number()
{
	// Generates a pseudo random number based on the current seed and makes a seed rotation	
	// This function was taken from the OOLite 1.80 source and modified
	int a,x;
	
	x = (rnd_seed_a * 2) & 0xFF;
	a = x + rnd_seed_c;
	if (rnd_seed_a > 127)
		a++;
	rnd_seed_a = a & 0xFF;
	rnd_seed_c = x;
	
	a = a / 256;	/* a = any carry left from above */
	x = rnd_seed_b;
	a = (a + x + rnd_seed_d) & 0xFF;
	rnd_seed_b = a;
	rnd_seed_d = x;
	return a;
}

void main()
{	
	...
	
	MoveToPlanet(1,1,0);	// Moves the planet seed to the desired planet

	printf("planet seed w0 w1 w2:\n%x %x %x\n\n",w0,w1,w2);
	
	// set rnd_seed_a to s_seed.c --> lsb of w1 -> w1 & 0x00FF
	rnd_seed_a = w1 & 0x00FF;
	// set rnd_seed_b to s_seed.d --> hsb of w1 -> (w1 >> 8) & 0x00FF
	rnd_seed_b = (w1 >> 8) & 0x00FF;
	// set rnd_seed_c to s_seed.e --> lsb of w2 -> w2 & 0x00FF
	rnd_seed_c = w2 & 0x00FF;
	// set rnd_seed_d to s_seed.f --> hsb of w2 -> (w2 >> 8) & 0x00FF
	rnd_seed_d = (w2 >> 8) & 0x00FF;

	printf("rnd seed abcd:\n%x %x %x %x\n\n",rnd_seed_a,rnd_seed_b,rnd_seed_c,rnd_seed_d);
	
	int rndnum;
	for (int i = 1; i <11; i++)
	{
		rndnum = gen_rnd_number();
		printf("%-2d. %d (%d)\n",i,rndnum % 5, rndnum);
	}
	
}
So something is wrong, but what...?
RobertK
Poor
Poor
Posts: 7
Joined: Mon Sep 03, 2018 11:06 am

Re: Planet generating algorithm

Post by RobertK »

I have now released a WIP version of my little browser for classic Z80-based machines:

https://sourceforge.net/projects/elitepb/

Maybe some of you could help me with the planet description string (see my last post), then I would be able to call this finished.

Here are a few screenshots:

Image

Image

Image
Post Reply