![]() |
| Most recent update (All By Hand(TM)): 17-May-2006 00:34 |
|
It’s the nexus of the crisis
The Frontier Galaxy IV: Getting to the Floating PointA long, long time ago... in a university town far away... back when the FPU was still a device which could be piggy-backed on a CPU and had to be communicated to using a device driver... there was this guy who wanted to use a vast scale of numbers to represent a universe. The problem with plain integers is that they loose meaning rapidly, considering the difference between the Earth's radius and the distance to the Moon, and their distance to the Sun, and its distance to the nearest star. And yet this guy went on to create an entire galaxy. Being a math buff, David Braben realized that on the then-state of the art machines it was possible to use integer words for the exponent and base to form pretty large numbers, and yet to preserve at least nominal accuracy. Enter the Scaled Word. Using an unsigned word as exponent means that your range is about 2^65535, in decimals a 2 followed by 19,728 zeros. Using a single word as base also means that your accuracy is just about 5 decimal digits, but, ah well, something's gotta give. The scaled word in Frontier 2 and FFE is defined as typedef union {
unsigned int full;
struct {
unsigned short Base,Scale;
} w;
} ScaledWord_t;
and is used to represent the largest dimensions in the game: the mass of stars and planets, and the distance of a planet or moon to its parent. If you gather from this that distances between stars is expressed in other units, you are quite right: that's just in dwords, divided by 100. Nowhere in the games a conversion from light years to kilometers is done... so you can forget about pointing your Interplanetary Shuttle towards Alpha Centauri and expect to arrive there a thousand years later. What a shame! The problem with using your private format for floating point numbers is that you'll have to write your own code for even the most basic mathematical functions, but Braben got his Masters in Computer Science at Cambridge so he probably considered this loads of fun! Let's see how to do maths with this poor mans floating point format. // Basic conversion: Scaled Word to Dword unsigned int ScaledWordToDword (unsigned int number) { ScaledWord_t ScaledWord; ScaledWord.full = number; if (((signed short)ScaledWord.w.Scale) > 15) { if (ScaledWord.w.Scale > 32) return -1; return ((unsigned int)ScaledWord.w.Base)<<(ScaledWord.w.Scale-15); } return ((unsigned int)ScaledWord.w.Base)>>(15-ScaledWord.w.Scale); } // Basic conversion: Dword to Scaled Word unsigned int DWordToScaledWord (unsigned int dword) { ScaledWord_t result; if (!dword) { result.w.Base = 0; result.w.Scale = 0xfff9; } else { result.w.Scale = 0x20; while (((signed int)dword) > 0) { dword += dword; result.w.Scale--; } dword >>= 17; result.w.Base = dword; } return result.full; } // Math: Multiply unsigned int FFP_Mul(unsigned int op1, unsigned int op2) { unsigned int result; result = ((op1 & 0xffff0000)+(op2 & 0xffff0000))+ (((signed int)(((signed short)(op1 & 0xffff))* ((signed short)(op2 & 0xffff)))) >> 15); return result; } // Math: Multiply (a slightly different variant) unsigned int FractionMul (unsigned int op1, unsigned int op2) { return (((op1 & 0xffff)*op2) >> 16)+(op2*(op1 >> 16)); } // Math: Square Root; the roottable can be found here unsigned int getSqrt (unsigned int eax) { if (eax < 0x4000000) { if (eax >= 0x400000) { eax >>= 15; eax = roottable[eax]; return ((signed int)eax)>>3; } if (eax >= 0x40000) { eax >>= 11; eax = roottable[eax]; return ((signed int)eax)>>5; } if (eax >= 0x4000) { eax >>= 7; eax = roottable[eax]; return ((signed int)eax)>>7; } if (eax >= 0x400) { eax >>= 3; eax = roottable[eax]; return ((signed int)eax)>>9; } eax += eax; eax = roottable[eax]; return ((signed int)eax)>>11; } if (eax >= 0x40000000) { eax >>= 21; return roottable[eax]; } if (eax >= 0x10000000) { eax >>= 19; eax = roottable[eax]; return ((signed int)eax)>>1; } eax >>= 0x11; eax = roottable[eax]; return ((signed int)eax)>>2; } // Math: Square Root (adjusted for FP) unsigned int getSqrt_adj (unsigned int value) { ScaledWord_t temp; unsigned int tmp; temp.full = value; tmp = temp.w.Base; tmp <<= 16; if (temp.w.Scale & 1) { temp.w.Scale >>= 1; temp.w.Scale++; } else { temp.w.Scale >>= 1; tmp <<= 1; } tmp = getSqrt (tmp); tmp >>= 1; temp.w.Base = tmp; return temp.full; } // Math: Addition (as observed by John Jordan) unsigned int FFP_Add (unsigned int arg_0, unsigned int arg_4) { ScaledWord_t scaled1, scaled2, result; unsigned int ecx; scaled1.full = arg_0; scaled2.full = arg_4; if (scaled1.w.Scale > scaled2.w.Scale) { if (scaled1.w.Scale > scaled2.w.Scale+31) return scaled1.full; result.w.Scale = scaled1.w.Scale; ecx = (scaled2.w.Base >> (scaled1.w.Scale-scaled2.w.Scale))+scaled1.w.Base; } else { if (scaled2.w.Scale > scaled1.w.Scale+31) return scaled2.full; result.w.Scale = scaled2.w.Scale; ecx = (scaled1.w.Base >> (scaled2.w.Scale - scaled1.w.Scale))+scaled2.w.Base; } if (abs(ecx) > 0x7fff) { result.w.Base = ecx >> 1; result.w.Scale++; return result.full; } result.w.Base = ecx; if (!result.w.Base) return result.full; while (abs(result.w.Base) <= 0x3fff) { result.w.Base <<= 1; result.w.Scale--; } return result.full; } // Math: Divide // Original code by John Jordan, tested by Dennis Luehring (not yet by me :) unsigned int FFP_Div (unsigned int nominator0, unsigned int divider0) { ScaledWord_t result; ScaledWord_t nominator; ScaledWord_t divider; nominator.full = nominator0; divider.full = divider0; int inom, idiv; if ((divider.full & 0xffff) == 0) { result.full = 0x7fff007f; } else { result.w.Scale = nominator.w.Scale - divider.w.Scale; inom = *(short *)&nominator.w.Base << 14; idiv = *(short *)÷r.w.Base; result.w.Base = (unsigned short)(short)(inom / idiv); if ( abs(*(short *)&result.w.Base) >= 0x4000) ++result.w.Scale; else result.w.Base <<= 1; } return result.full; }
All said and done: where are these routines used? Well, shifting numbers left and right may be good enough for random star positions -- and random planets in lesser games -- but we want some real-world spicing thrown in every now and then. The physics department of the game delivers some quite realistic looking numbers, and that's because they are based on real science. The function // First a small helper function unsigned int CalcTemperature (unsigned int value) { ScaledWord_t temp; temp.full = value; if (temp.w.Scale < 32) { return (((unsigned int)temp.w.Base) << 16) >> (31-temp.w.Scale); } if (temp.w.Base == 0) return 0; return 0x80000000; } void GetTemperature (Planet_t *Planets,int Counter, int parentobject, int dd_arg_1, unsigned short dw_arg_2, int mass_unscaled) { int orbit_radius, parent_mass; ScaledWord_t temp; Planets[Counter].orbital_radius = FractionMul(dd_arg_1, dw_arg_2); if (Planets[Counter].orbital_radius) { Planets[Counter].orbital_radius = DWordToScaledWord(Planets[Counter].orbital_radius); Planets[Counter].orbital_radius += 0x190000; if (parentobject) { orbit_radius = Planets[Counter].orbital_radius; if (Planets[parentobject-1].descriptioncode == 0 && Counter-1 <= parentobject) { orbit_radius += 0x10000; } parent_mass = Planets[parentobject-1].mass; temp.full = getSqrt_adj(FFP_Div(FFP_Mul(FFP_Mul(orbit_radius,orbit_radius), orbit_radius),parent_mass)); temp.w.Base = ((temp.w.Base*0x5EDB) >> 15); Planets[Counter].orbital_period = temp.full; } else { Planets[Counter].orbital_period = 0; } Planets[Counter].latitude = BasePlayerVariables_plangen_seed & 0xffff; } Planets[Counter].random_seed = BasePlayerVariables_plangen_basemass2; BasePlayerVariables_plangen_dword_A4++; Planets[Counter].parent = parentobject; Planets[Counter].mass = DWordToScaledWord(mass_unscaled)+0x3f0000; Planets[Counter].eccentricity = (((BasePlayerVariables_plangen_seed & 0xffff)* (BasePlayerVariables_plangen_seed & 0xffff)) & 0xffff) >> 24; Planets[Counter].longitude = ((BasePlayerVariables_plangen_seed & 0xffff) >> 3)| ((BasePlayerVariables_plangen_seed & 0xffff) << 13); Planets[Counter].longitude = (Planets[Counter].longitude*Planets[Counter].longitude)>>20; if (parentobject) { Planets[Counter].longitude += Planets[parentobject-1].field_42; } Planets[Counter].field_42 = (Planets[Counter].random_seed*Planets[Counter].random_seed & 0x8000) ? -1 : 0; Planets[Counter].rotspeed = Planets[Counter].field_42 & 3; Planets[Counter].level = BasePlayerVariables_plangen_byte_AA; if (Planets[Counter].temperature >= 1000) return; int loopcounter = 0; int parentPtr; int edi = Counter; while (Planets[edi].parent) { parentPtr = Planets[edi].parent-1; if (Planets[parentPtr].field_1C) { temp.full = DWordToScaledWord(Planets[parentPtr].field_1C); temp.w.Scale += 0x32; temp.full = FFP_Div(temp.full, Planets[edi].orbital_radius); temp.full = FFP_Mul(temp.full,temp.full); loopcounter = FFP_Add (loopcounter, temp.full); } edi = parentPtr; } Planets[Counter].temperature += CalcTemperature(getSqrt_adj (getSqrt_adj (loopcounter))); } Note the unconventional way some parameters are adjusted, e.g., the orbital radius gets some constant added to it, and gets multiplied by 0x5EDB (24283). This suggests that the actual calculations are done in other units, and the result gets converted on the fly before being stored (you'll see similar conversions the other way around when we want to display those numbers). In the previous part I stated that the structure member
There are still a couple of routines from Satellites are generated using a probability table and decreasing this number until it's zero, calling dw planet_generator_array[] = {
0, 0xA, 0x29, 0x5E, 0xA7, 0x105, 0x178, 0x200,
0x29C, 0x34D, 0x411, 0x4EA, 0x5D6, 0x6D6, 0x7EA, 0x910,
0xA49, 0xB95, 0xCF3, 0xE62, 0xFE4, 0x1176, 0x1319, 0x14CD,
0x1691, 0x1864, 0x1A47, 0x1C38, 0x1E37, 0x2045, 0x2260, 0x2488,
0x26BC, 0x28FC, 0x2B48, 0x2D9E, 0x3000, 0x326B, 0x34DF, 0x375D,
0x39E3, 0x3C71, 0x3F06, 0x41A2, 0x4445, 0x46ED, 0x499B, 0x4C4E,
0x4F05, 0x51BF, 0x547D, 0x573E, 0x5A01, 0x5CC6, 0x5F8C, 0x6253,
0x651B, 0x67E2, 0x6AA9, 0x6D6F, 0x7034, 0x72F7, 0x75B7, 0x7875,
0x7B30, 0x7DE7, 0x809B, 0x834B, 0x85F6, 0x889C, 0x8B3D, 0x8DD9,
0x906F, 0x92FF, 0x9588, 0x980B, 0x9A87, 0x9CFC, 0x9F6A, 0xA1D0,
0xA42F, 0xA685, 0xA8D4, 0xAB1A, 0xAD58, 0xAF8D, 0xB1B9, 0xB3DD,
0xB5F8, 0xB80A, 0xBA13, 0xBC12, 0xBE09, 0xBFF6, 0xC1DA, 0xC3B4,
0xC586, 0xC74D, 0xC90C, 0xCAC1, 0xCC6D, 0xCE0F, 0xCFA8, 0xD138,
0xD2BF, 0xD43C, 0xD5B1, 0xD71C, 0xD87E, 0xD9D8, 0xDB29, 0xDC71,
0xDDB0, 0xDEE7, 0xE016, 0xE13C, 0xE25A, 0xE370, 0xE47F, 0xE585,
0xE684, 0xE77B, 0xE86A, 0xE953, 0xEA34, 0xEB0E, 0xEBE2, 0xECAE,
0xED74, 0xEE34, 0xEEED, 0xEFA0, 0xF04D, 0xF0F4, 0xF195, 0xF231,
0xF2C7, 0xF358, 0xF3E3, 0xF46A, 0xF4EC, 0xF568, 0xF5E1, 0xF654,
0xF6C4, 0xF72F, 0xF795, 0xF7F8, 0xF857, 0xF8B2, 0xF90A, 0xF95D,
0xF9AE, 0xF9FB, 0xFA45, 0xFA8C, 0xFAD0, 0xFB11, 0xFB4F, 0xFB8A,
0xFBC3, 0xFBF9, 0xFC2D, 0xFC5F, 0xFC8E, 0xFCBC, 0xFCE7, 0xFD10,
0xFD37, 0xFD5D, 0xFD80, 0xFDA2, 0xFDC3, 0xFDE2, 0xFDFF, 0xFE1B,
0xFE35, 0xFE4E, 0xFE66, 0xFE7D, 0xFE93, 0xFEA7, 0xFEBB, 0xFECD,
0xFEDF, 0xFEEF, 0xFEFF, 0xFF0E, 0xFF1C, 0xFF29, 0xFF36, 0xFF42,
0xFF4D, 0xFF58, 0xFF62, 0xFF6B, 0xFF74, 0xFF7D, 0xFF85, 0xFF8C,
0xFF94, 0xFF9A, 0xFFA1, 0xFFA7, 0xFFAC, 0xFFB1, 0xFFB6, 0xFFBB,
0xFFC0, 0xFFC4, 0xFFC8, 0xFFCB, 0xFFCF, 0xFFD2, 0xFFD5, 0xFFD8,
0xFFDA, 0xFFDD, 0xFFDF, 0xFFE1, 0xFFE3, 0xFFE5, 0xFFE7, 0xFFE9,
0xFFEA, 0xFFEC, 0xFFED, 0xFFEE, 0xFFF0, 0xFFF1, 0xFFF2, 0xFFF3,
0xFFF4, 0xFFF5, 0xFFF5, 0xFFF6, 0xFFF7, 0xFFF7, 0xFFF8, 0xFFF9,
0xFFF9, 0xFFFA, 0xFFFA, 0xFFFA, 0xFFFB, 0xFFFB, 0xFFFB, 0xFFFC,
0xFFFC, 0xFFFC, 0xFFFD, 0xFFFD, 0xFFFD, 0xFFFD, 0xFFFD, 0xFFFE
};
dd planet_generator_getFromArray (unsigned short value)
{
unsigned int result;
if (value >= 0x4000)
result = 0xffff;
else
result = planet_generator_array[value >> 6];
return result;
}
int GenerateBinarySystem(Planet_t *planets,int *Counter,int parentObject,
unsigned int basemass,int arg10,unsigned short short14, unsigned short short18,
char *name,int ptr_counter_0)
{
int counter_number_1=0, counter_lowercase=0, counter_number_2=0;
int parent_planet = *Counter;
if (basemass >= 0xFFFFFFEF)
goto aboveeq_FFFFFFEF_4395EF;
if (basemass < 170000000)
goto below_170000000_43964E;
if (basemass >= 175000000)
goto below_170000000_43964E;
aboveeq_FFFFFFEF_4395EF:
{
GenerateDefaultPlanet (planets, Counter, basemass, parentObject, arg10,
short14, name, ptr_counter_0, &counter_number_1, &counter_lowercase,
&counter_number_2);
GenerateDefaultPlanet (planets, Counter, basemass>>2, *Counter,
arg10, short18, name, ptr_counter_0, &counter_number_1, &counter_lowercase,
&counter_number_2);
return short18<<3;
}
below_170000000_43964E:
{
planets_do_Shuffle();
int eax = (((BasePlayerVariables_plangen_seed & 0xffff) | 0xffff8000)/4) & 0xffff;
unsigned int mass = eax * (basemass >> 16);
if (mass < 17000000)
{
mass = 17000000;
}
GetTemperature (planets, *Counter, parentObject, arg10, short14, basemass+mass);
planets[*Counter].descriptioncode = 0; // Binary system
planets[*Counter].model = 23; // !? Must be a mistake!
strcpy (planets[*Counter].name, name);
if (strlen(planets[*Counter].name) > 11) // "Groombridge 34" etc. get too long
{
planets[*Counter].name[11] = 0;
strcat (planets[*Counter].name, ".");
} else
strcat (planets[*Counter].name, " ");
char *endptr = planets[*Counter].name+strlen(planets[*Counter].name);
*endptr = BasePlayerVariables_plangen_CurrentMainStarNumber+'A';
endptr[1] = ',';
endptr[2] = BasePlayerVariables_plangen_CurrentMainStarNumber+'B';
endptr[3] = 0;
(*Counter)++;
GenerateDefaultPlanet (planets, Counter, basemass, parent_planet+1, arg10,
short18, name, ptr_counter_0, &counter_number_1, &counter_lowercase,
&counter_number_2);
planets[(*Counter)-1].latitude = 0;
GenerateDefaultPlanet (planets, Counter, mass, parent_planet+1, arg10,
short18, name, ptr_counter_0, &counter_number_1, &counter_lowercase,
&counter_number_2);
planets[(*Counter)-1].latitude = 0x7fff;
if (GSystem_CurrentConfiguration_FFE)
planets[parent_planet].field_1C += planets[(*Counter)-1].field_1C;
}
return short18<<3;
}
void GenerateSatellites(Planet_t *planets,int *Counter,int parentObject,
unsigned short short_arg_14,int arg_18,unsigned int unsigned_arg_1C,int arg_20,
char *name,int ptr_counter_0,int ptr_counter_number_1,int ptr_counter_lowercase,
int ptr_counter_number_2)
{
unsigned int l_arg10;
unsigned int orgCounter;
ScaledWord_t tempmass;
unsigned int var_8;
dd tmp_seed;
dd tmp_basemass2;
dd tmp_byte_AA;
if (unsigned_arg_1C > 0x7FFFFFFF)
l_arg10 = 0xFFFFFFFF;
else
l_arg10 = 2*unsigned_arg_1C;
tempmass.w.Scale = planet_generator_getFromArray(arg_18);
unsigned int esi,edi,eax,ebx;
esi = arg_18 & 0xffff;
edi = 0;
int DeathlockResolver = 0; // Now THAT's a descriptive variable name
while ((edi+=esi) < 0x10000)
{
ebx = planets_do_Shuffle() & 0xffff;
ebx >>= 3;
ebx += short_arg_14;
ebx = (ebx < 0x10000) ? (ebx*esi) >> 16 : esi;
if (ebx == 0 && esi == 0)
{
StatusUnsure = 1;
ebx = 1;
esi = 8;
if (++DeathlockResolver > 100)
{
break;
}
}
edi = ebx+(esi>>2)+(esi>>3);
if (edi+esi < 0x10000)
{
ebx = planets_do_Shuffle() & 0xffff;
ebx = (ebx*ebx)>>16;
ebx = (ebx*ebx)>>16;
eax = (ebx*(planet_generator_getFromArray(edi+esi) - tempmass.w.Scale)) >> 16;
ebx = eax & 0xffff;
tempmass.w.Scale += ebx;
ebx = FractionMul(arg_20, ebx);
if (ebx > 32)
{
if (ebx <= 15000)
ebx >>= 3;
orgCounter = *Counter;
if (ebx > 17000000 && BasePlayerVariables_plangen_numstars_2 > 1)
{
eax = BasePlayerVariables_plangen_basemass1 >> 1;
if (ebx > eax)
ebx = eax;
planets_do_Shuffle();
GenerateBinarySystem (planets, Counter, parentObject, ebx, l_arg10, esi+(edi>>1),
(BasePlayerVariables_plangen_basemass2 & 0xffff)>>11, name, ptr_counter_0);
BasePlayerVariables_plangen_numstars_2 -= 2;
tempmass.w.Base = 0x3000;
ebx >>= 2;
} else
{
if (ebx > 17000000)
{
if (BasePlayerVariables_plangen_numstars_2 == 0)
{
eax = planets_do_Shuffle() & 0xffff;
ebx = eax+2*((eax<<7)+eax);
} else
{
BasePlayerVariables_plangen_numstars_2--;
eax = BasePlayerVariables_plangen_basemass1 >> 1;
if (ebx > eax)
{
ebx = BasePlayerVariables_plangen_basemass1>>1;
if (ebx <= 17000000)
ebx = 17000000;
}
}
}
tempmass.w.Base = GenerateDefaultPlanet (planets, Counter, ebx, parentObject,
l_arg10, esi+(edi>>1), name, ptr_counter_0, &ptr_counter_number_1,
&ptr_counter_lowercase, &ptr_counter_number_2);
}
if (ebx <= 15000)
ebx <<= 3;
if (ebx <= (l_arg10 >> 6))
{
var_8 = ebx;
} else
{
var_8 = l_arg10 >> 6;
}
tmp_seed = BasePlayerVariables_plangen_seed;
tmp_basemass2 = BasePlayerVariables_plangen_basemass2;
tmp_byte_AA = BasePlayerVariables_plangen_byte_AA;
if (ebx > 17000000)
{
BasePlayerVariables_plangen_byte_AA = 0;
} else
{
BasePlayerVariables_plangen_byte_AA++;
}
GenerateSatellites (planets, Counter, orgCounter+1, planets_do_Shuffle(),
tempmass.w.Base, var_8, ebx >> 7, planets[orgCounter].name, ptr_counter_0,
ptr_counter_number_1, ptr_counter_lowercase, ptr_counter_number_2);
BasePlayerVariables_plangen_seed = tmp_seed;
BasePlayerVariables_plangen_basemass2 = tmp_basemass2;
BasePlayerVariables_plangen_byte_AA = tmp_byte_AA;
}
esi += edi;
}
}
}
There is another interesting kludge in
That's enough mathematics for one evening; I will return to it when discussing the predefined planets, but the next part will mainly reveal all about the random names of planets and cities!
Based on original data and algorithms from Frontier:Elite 2 and Frontier:First Encounters by David Braben (Frontier Developments) Original copyright holders: | ||||||||||||||||||||||||||||||||
![]() |
For any real questions -- I will not provide the complete source code! -- you can drop me a mail at jongware. |