How does the seed work?

Discussion and information relevant to creating special missions, new ships, skins etc.

Moderators: winston, another_commander

Post Reply
User avatar
Commander McLane
---- E L I T E ----
---- E L I T E ----
Posts: 9520
Joined: Thu Dec 14, 2006 9:08 am
Location: a Hacker Outpost in a moderately remote area
Contact:

How does the seed work?

Post by Commander McLane »

I never have understood how the galaxy seed actually works in Oolite.

Particularly I don't know why there are six seed numbers in every galaxy seed. I always thought the seed in Elite works like a Fibonacci sequence: f(n) = f(n-1) + f(n-2), and then modulo 256. But for that sequence you need only two values in the seed (the first two ones, n=1 and n=2). So why six in Oolite's seeds, which themselves aren't following the Fibonacci sequence? E.g. the seed for Galaxy 1 is: 74, 90, 72, 2, 83, 183. 74 + 90 is not 72. 90 + 72 is not 2. 72 + 2 is not 83. And 2 + 83 is not 183. So what would be the next number in the sequence? I have no idea, but it should be somehow determined by the existing sequence.

Or is it in thruth three seeds, for three different Fibonacci sequences? So the next values for the first sequence would be: 74, 90, 164, 254, 162, 160, 66, 226 etc.? And the second one: 72, 2, 74, 76, 150, 226, 120, 90 etc.? And the third one: 83, 183, 10, 193, 203, 140, 87, 227 etc.?

Or still somehow completely different?

Just out of pure interest: Could someone enlighten me how the seed actually works?
User avatar
JensAyton
Grand Admiral Emeritus
Grand Admiral Emeritus
Posts: 6657
Joined: Sat Apr 02, 2005 2:43 pm
Location: Sweden
Contact:

Re: How does the seed work?

Post by JensAyton »

Commander McLane wrote:
I never have understood how the galaxy seed actually works in Oolite.

Particularly I don't know why there are six seed numbers in every galaxy seed. I always thought the seed in Elite works like a Fibonacci sequence: f(n) = f(n-1) + f(n-2), and then modulo 256.
No. That would make a really awful psuedo-random number generator (as opposed to the merely quite bad ones actually used). I suspect Bell or Braben used the Fibonacci sequence mod N as a simple example of a chaotic sequence once, and this has been misinterpreted.
Or still somehow completely different?
Yes. :-)
Just out of pure interest: Could someone enlighten me how the seed actually works?
I don’t particularly feel like analyzing it. You can try for yourself if you wish; the code is here.
User avatar
Dr Beeb
Dangerous
Dangerous
Posts: 127
Joined: Sun Mar 23, 2008 10:28 pm
Location: Mt. Vista, Oosa, Biarge System, Galaxy 1

Re: How does the seed work?

Post by Dr Beeb »

Ahruman wrote:
Commander McLane wrote:
I never have understood how the galaxy seed actually works in Oolite.

Particularly I don't know why there are six seed numbers in every galaxy seed. I always thought the seed in Elite works like a Fibonacci sequence: f(n) = f(n-1) + f(n-2), and then modulo 256.
No. That would make a really awful psuedo-random number generator (as opposed to the merely quite bad ones actually used). I suspect Bell or Braben used the Fibonacci sequence mod N as a simple example of a chaotic sequence once, and this has been misinterpreted.
Or still somehow completely different?
Yes. :-)
Just out of pure interest: Could someone enlighten me how the seed actually works?
I don’t particularly feel like analyzing it. You can try for yourself if you wish; the code is here.
Regrettably I have studied this (and some of Ian Bell's code a bit) and have got this far: There are six bytes in the seed, a,b,c,d,e,f which appear in the save file, are different for each galaxy, and define (most?) of the properties of the first system in each galaxy. (ie Tibedied for the first Galaxy). To get to the Eighth system, ie Lave, the seed is 'rotated' or 'twisted' (8-1)*4 = 28 times with the
rotate_seed
function.
In essence the function is treating the 6 bytes as 3 16-bit words, w0, w1, w2, where w0 = 256*a+b, w1=256*c+d, w2 = 256*e+f; and the 'rotation' (or 'twist') is executed where w2 -> w0+w1+w2 , w1 -> w2, w0 -> w1. Hence the phrase 'truncated fibonacci sequence', as the highest order bit of the summation is thrown out to keep w2 16 bits in length.

The 8 galaxies starting seeds are related to each other. Each byte is separately internally left-shift rotated by 1 bit for each galaxy increment. Hence 8 galaxies in total before returning to galaxy 1 in Elite. In hex code (and apologies for big-endian vs small-endian swop compared to values in save file) The first galaxy is 0x 5A4A 0248 B753 == {74 90} {72 2} {83 183}, second galaxy is 0x B494 0490 6FA6 == {148 180} {144 4} {166 111} etc. Time for dinner.
White dots were so much easier to hit
Mr J.
Mostly Harmless
Mostly Harmless
Posts: 3
Joined: Fri Jul 18, 2008 7:32 pm
Location: France

Post by Mr J. »

Hi !
There's a really interesting article about random numbers.
It's on christian pinder's website (Elite TNK programmer).

http://www.newkind.co.uk/articles/game- ... umbers.php

enjoy ;)

ps: thank you Dr BeeB !! :D
User avatar
Commander McLane
---- E L I T E ----
---- E L I T E ----
Posts: 9520
Joined: Thu Dec 14, 2006 9:08 am
Location: a Hacker Outpost in a moderately remote area
Contact:

Post by Commander McLane »

Thanks, Dr Beeb! I couldn't have wished for more. :)
User avatar
Dr Beeb
Dangerous
Dangerous
Posts: 127
Joined: Sun Mar 23, 2008 10:28 pm
Location: Mt. Vista, Oosa, Biarge System, Galaxy 1

Post by Dr Beeb »

Commander McLane wrote:
Thanks, Dr Beeb! I couldn't have wished for more. :)
You're welcome, and the story wouldn't be complete without this following (urban legend?) from the Universe in a Bottle chapter (see off-world topics)
Braben and Bell called the starting number for a galaxy "a seed" and, in truth, creating the game this way was more like gardening than deliberately constructing something. You had to plant the seed and see what grew. It was another sense in which they were ceding direct control over the game in favour of working indirectly on the player's experience. But they did want to start the player off in a reasonably friendly bit of space, where the pickings were good and they wouldn't get instantly clobbered. Since there was no way to edit a galaxy, you just had to try galaxy after galaxy, seed after seed, until something suitable grew. "I remember thinking it was very wasteful," Braben says. "You'd type in a number, a birthday or something, and see what galaxy that came out with. 'No, I don't like that. No, I don't like that. That cluster looks horrible'." They also decided they had better check the 256 system names in the galaxy where the player would be plunked down, in case any of the four-letter words were actually four-letter words. "One of the first galaxies we tried had a system called Arse. We couldn't use the whole galaxy. We just threw it away!"
White dots were so much easier to hit
User avatar
FSOneblin
---- E L I T E ----
---- E L I T E ----
Posts: 460
Joined: Tue Oct 30, 2007 12:15 am
Location: Yes, That is True

Post by FSOneblin »

So, they couldn't use 4 letter words in elite? What was lave called? llave?

Don't panic: FSOneblin
Don't panic

Now an "adult!"
User avatar
JohnnyBoy
---- E L I T E ----
---- E L I T E ----
Posts: 490
Joined: Mon May 05, 2008 9:41 pm
Location: West Sussex, UK (rich agricultural)

Post by JohnnyBoy »

FSOneblin wrote:
So, they couldn't use 4 letter words in elite? What was lave called? llave?
No, they couldn't use any words that turned out to be "four-letter words" - a euphemism for swear words or vulgarity.

I still marvel at Braben and Bell's ingenuity in using the Fibonacci sequence to generate far more data about 8 galaxies than a BBC Micro could possibly hold in its memory. Awesome stuff.
"That's no vicious Treeoid. That's my wife."
User avatar
JensAyton
Grand Admiral Emeritus
Grand Admiral Emeritus
Posts: 6657
Joined: Sat Apr 02, 2005 2:43 pm
Location: Sweden
Contact:

Post by JensAyton »

JohnnyBoy wrote:
FSOneblin wrote:
So, they couldn't use 4 letter words in elite? What was lave called? llave?
No, they couldn't use any words that turned out to be "four-letter words" - a euphemism for swear words or vulgarity.

I still marvel at Braben and Bell's ingenuity in using the Fibonacci sequence to generate far more data about 8 galaxies than a BBC Micro could possibly hold in its memory. Awesome stuff.
I thought we’d covered this already… the Fibonacci sequence is not involved.
User avatar
JohnnyBoy
---- E L I T E ----
---- E L I T E ----
Posts: 490
Joined: Mon May 05, 2008 9:41 pm
Location: West Sussex, UK (rich agricultural)

Post by JohnnyBoy »

Ahruman wrote:
I thought we’d covered this already… the Fibonacci sequence is not involved.
According to Dr. Beeb, a modified version is involved...
Dr. Beeb wrote:
Hence the phrase 'truncated fibonacci sequence', as the highest order bit of the summation is thrown out to keep w2 16 bits in length.
"That's no vicious Treeoid. That's my wife."
Post Reply