Home World Forum
Stars! AutoHost web forums

Jump to Stars! AutoHost


 
 
Home » Stars! 2.6/7 » The Academy » Planet value calculation made easy!
Planet value calculation made easy! Sun, 20 March 2005 18:45 Go to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Hi,

I finally managed to understand how the planet habitability works (it took some zen!). In the process I rewrote the algorithm to make it easier on the eye (and perhaps on the compiler) as well as closer to the spirit of things. This code has already calculated 26000+ planets (belonging to 28 different planet reports) accurately.

A note for testers: Complications may arise due to integer math implicit conversions. Two of them are marked as such. The third is ugly enough that alternate code is provided.

Comments, suggestions, welcome!

#define BYTE char
#define WORD short

#define IMMUNE(a) ((a)==-1)

//simplified for this. Initialized somewhere else
struct playerDataStruct 
{
  BYTE lowerHab[3];	 // from 0 to 100 "clicks", -1 for immunity
  BYTE upperHab[3];
} player;

//in: an array of 3 bytes from 0 to 100
//out: a signed integer between -45 and 100
//hey, it was the Jeffs idea! Smile
signed long planetValueCalc(BYTE* planetHabData)
{
  signed long planetValuePoints=0,redValue=0,ideality=10000;	//in fact, they are never < 0
  WORD planetHab,habUpper,habLower,habCenter;
  WORD Excentr,habRadius,margin,Negativ,dist2Center;

  for (WORD i=0; i<3; i++) {
    habUpper = player.upperHab[i];
    if (IMMUNE(habUpper)) {			//perfect hab
      planetValuePoints += 10000;
    }
    else {	//the messy part
      habLower  = player.lowerHab[i];
      habCenter = (habUpper+habLower)/2;	//no need to precalc
      planetHab = planetHabData[i];

/*
 note: this version makes the basic assumption that habitability is
 symmetrical around the center, that is, the ideal center is located
 in the middle of the lower and upper boundaries, and both halves
 have the same value. The original algorithm seems able to cope with
 weirder definitions, i.e: bottom is 20, top is 80, center is 65,
 and hab value stretches proportionally to the different length of
 both "halves"...
*/

      dist2Center = abs(planetHab-habCenter);
      habRadius = habCenter-habLower;

      if (dist2Center<=habRadius) {		/* green planet */
	Excentr = 100*dist2Center/habRadius;	//note: implicit conversion to integer
	Excentr = 100 - Excentr;		//kind of reverse excentricity
	planetValuePoints += Excentr*Excentr;
	margin = dist2Center*2 - habRadius;
	if (margin>0) {		//hab in the "external quarters". dist2Center > 0.5*habRadius
	  ideality *= (double)(3/2 - dist2Center/habRadius);	//decrease ideality up to ~50%
	/*
	  ideality *= habRadius*2 - margin;	//better suited for integer math
	  ideality /= habRadius*2;
	*/
	}
      } else {					/* red planet */
	Negativ = dist2Center-habRadius;
	if (Negativ>15) Negativ=15;
	redValue += Negativ;
      }
    }
  }

  if (redValue!=0) return -redValue;
  planetValuePoints = sqrt((double)planetValuePoints/3)+0.9;	//rounding a la Jeffs
  planetValuePoints = planetValuePoints * ideality/10000;	//note: implicit conversion to integer

  return planetValuePoints;		//Thanks ConstB for starting this
}


{related topics: http://starsautohost.org/sahforum/index.php?t=msg&th=227 1&start=0&rid=625&S=425579ce978e6d33b2db2f095c4a 3dee

added some comments, mainly for version developers
}


[Updated on: Sun, 27 March 2005 16:10]




So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Wed, 23 March 2005 12:56 Go to previous messageGo to next message
sirgwain is currently offline sirgwain

 
Senior Chief Petty Officer

Messages: 86
Registered: March 2004
Location: Tucson
Very nice! I have a question on how you validated the data. You got planet dumps with gravity, temp, and radiation information. How did you convert from the gravity value to the number of clicks? A lookup table feels error prone because in the race UI there are multiple clicks that give you the same gravity. For example these are the first 11 clicks:

.12f, .12f, .13f, .13f, .14f, .14f, .15f, .15f, .16f, .17f, .17f

How did you get around this?

-SirGwain

[Edit]
Ahhh I see, I just read your posts on the freestars forum. You can convert from clicks to grav completely accurately but not back again.


[Updated on: Wed, 23 March 2005 13:11]

Report message to a moderator

Re: Planet value calculation made easy! Wed, 23 March 2005 13:45 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Hi!

sirgwain wrote on Wed, 23 March 2005 18:56

Ahhh I see, I just read your posts on the freestars forum. You can convert from clicks to grav completely accurately but not back again.



Welll, Grav to clicks has a few "ambiguous" spots. For these I coded a subsequent call to the planetValueCalc function using the "other" possible "click equivalent" for the reported grav. Twisted Evil

Thus, I've been able to test the function's accuracy against planet reports. What I've not been able to is predict with absolute certainty the planet value in the ambiguous cases without the report to give confirmation. Confused


[Updated on: Wed, 23 March 2005 13:47]




So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Wed, 23 March 2005 15:54 Go to previous messageGo to next message
sirgwain is currently offline sirgwain

 
Senior Chief Petty Officer

Messages: 86
Registered: March 2004
Location: Tucson
Would you mind posting your code to go from gravToClicks()? I looked at the clicksToGrav function posted on the other board, but I see you already reversed it. Smile

Report message to a moderator

Re: Planet value calculation made easy! Wed, 23 March 2005 16:36 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Hi,

sirgwain wrote on Wed, 23 March 2005 21:54

Would you mind posting your code to go from gravToClicks()? I looked at the clicksToGrav function posted on the other board, but I see you already reversed it. Smile



Request granted: Smile

//exact reverse except when ambiguous input.
//receives a floating point value and
// returns an unsigned byte or char
function getClicksFromGrav(grav)
{
  grav *= 100;		//local copy (needs at least 2 bytes)
  var result;		//unsigned char
  var lowerHalf = 1;	//signed char
  if (grav < 100) {
    grav = Math.floor(10000/grav);	//integer truncation
    lowerHalf = -1;
  }
  if (grav < 200) {
    result = grav/4-25;
  } else {
    result = (grav + 400) / 24;
  }
  result = Math.floor(50.9+lowerHalf*result);
  if (result < 1) result = 1;	//one less ambiguity
  return result;
}


It's JavaScript, but should be easily converted to anything. There may even exist a better algorithm!

Enjoy! Smile



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Fri, 08 April 2005 01:27 Go to previous messageGo to next message
ConstB is currently offline ConstB

 
Crewman 1st Class

Messages: 27
Registered: March 2005
Location: Tomsk, Russia
Quote:

The original algorithm seems able to cope with weirder definitions, i.e: bottom is 20, top is 80, center is 65, and hab value stretches proportionally to the different length of both "halves"...



Yes, but there is a boundschecker function for race data inside Stars! that checks hab center correctness too. And if you are cheating with race data it'll be detected and you'll be punished.

Report message to a moderator

Re: Planet value calculation made easy! Fri, 08 April 2005 04:03 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
ConstB wrote on Fri, 08 April 2005 07:27


Yes, but there is a boundschecker function for race data inside Stars! that checks hab center correctness too. And if you are cheating with race data it'll be detected and you'll be punished.


Of course, but, does the boundschecker make sure that "habCenter" is indeed centered inside the upper and lower hab, or just bracketed by them?



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Fri, 08 April 2005 05:05 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
It checks that it is in the middle.

Report message to a moderator

Re: Planet value calculation made easy! Fri, 08 April 2005 07:37 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
PricklyPear wrote on Fri, 08 April 2005 11:05

It checks that it is in the middle.


So the basic assumption in my rewrite is supported by the Jeffs. Cool But it still looks to me as if an earlier implementation of Stars! was aimed at allowing more diversity. Twisted Evil



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 12:44 Go to previous messageGo to next message
ConstB is currently offline ConstB

 
Crewman 1st Class

Messages: 27
Registered: March 2005
Location: Tomsk, Russia
m.a@stars wrote on Fri, 08 April 2005 18:37

But it still looks to me as if an earlier implementation of Stars! was aimed at allowing more diversity. Twisted Evil


I think it was aimed at avoiding recalculating hab center each time. Wink

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 12:59 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
ConstB wrote on Sat, 09 April 2005 18:44

m.a@stars wrote on Fri, 08 April 2005 18:37

But it still looks to me as if an earlier implementation of Stars! was aimed at allowing more diversity. Twisted Evil


I think it was aimed at avoiding recalculating hab center each time. Wink


That's an unrelated trivial change, easily reverted. Razz Array lookup can be slower than integer divide by 2. Sherlock



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 13:15 Go to previous messageGo to next message
Kotk

 
Commander

Messages: 1227
Registered: May 2003
ConstB wrote on Sat, 09 April 2005 19:44

I think it was aimed at avoiding recalculating hab center each time. Wink

The authors of stars were quite extreme at bitpacking every little thing in order to save handful of bytes. Confused Time was harsh, internet was slow and bytes were expensive back then. Laughing
Now ... you say they WASTED 3 bytes in race file to avoid some calculations? Surprised
Sounds different from their general style. Rolling Eyes

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 13:57 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Kotk wrote on Sat, 09 April 2005 19:15


Now ... you say they WASTED 3 bytes in race file to avoid some calculations? Surprised
Sounds different from their general style. Rolling Eyes



That's exactly my point. IF "ideal hab on center" was originally meant to be only one of many hab "styles", THEN those 3 bytes would not be waste. Twisted Evil

Otherwise, the hab calculation code was too complex for the task at hand. Confused



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 13:58 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
Kotk wrote on Sat, 09 April 2005 13:15

Now ... you say they WASTED 3 bytes in race file to avoid some calculations? Surprised
Sounds different from their general style. Rolling Eyes



The bitpacking is annoying and gives all sorts of artificial limits and bugs. However, I understand that the authors wanted the program to fit on a floppy disk.

Size of race files don't necessarily matter since they are produced after the EXE is distributed.

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 14:40 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
m.a@stars wrote on Sat, 09 April 2005 13:57

That's exactly my point. IF "ideal hab on center" was originally meant to be only one of many hab "styles", THEN those 3 bytes would not be waste. Twisted Evil

Otherwise, the hab calculation code was too complex for the task at hand. Confused


Could be interesting to have ideal hab at the end of the range. BTW, where does 3 bytes come from? I think the centre information is stored in a single byte?

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 15:02 Go to previous messageGo to next message
Kotk

 
Commander

Messages: 1227
Registered: May 2003
PricklyPear wrote on Sat, 09 April 2005 20:58

Size of race files don't necessarily matter since they are produced after the EXE is distributed.

Heh? Confused I missed your point here. EXE is not bitpacked! You say you reverse engineer it? Rolling Eyes EXE itself is bit bigger than logical thanks to very lot of bitpacking code. Anyone with eye who looks into it see it.

The makers said they did bitpack stuff to get the game files size down and so e-mail size down.

Actually i suspect they bitpacked everything since they just loved to do it. Why to squeeze planets x, y and name_id into 4 bytes in xy file? Why not to use logical 6 bytes? Its e-mailed only once so why to save these 2 kilobytes? Very minor effect.

But ... sure ... it somewhat helped. When the game was made there was no autohost. Worse ... no HTML and no WWW pages back then. Things like Telnet, FTP and SMTP. Stars was made as PBEM game. Play-By-E-Mail. You got to modem somewhere, to download and upload your e-mails ... etc. So ... it helped. Smile

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 15:03 Go to previous messageGo to next message
Kotk

 
Commander

Messages: 1227
Registered: May 2003
PricklyPear wrote on Sat, 09 April 2005 21:40

BTW, where does 3 bytes come from?
Radiation, Gravity and Temperature. Rolling Eyes

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 15:25 Go to previous messageGo to next message
Ptolemy is currently offline Ptolemy

 
Commander

Messages: 1008
Registered: September 2003
Location: Finland

Hmmm,

Seems to me someone isn't remembering the history of this game very well. i.e.
Quote:

The makers said they did bitpack stuff to get the game files size down and so e-mail size down.

Actually i suspect they bitpacked everything since they just loved to do it. Why to squeeze planets x, y and name_id into 4 bytes in xy file? Why not to use logical 6 bytes? Its e-mailed only once so why to save these 2 kilobytes? Very minor effect


So, here is the condensed version:

Stars! was created BEFORE Windows 95 - back in the days of Windows 3.1 and the early internet explosion. Size WAS important. Hard disks rarely capped 250 megs back then and home broadband didn't exist. All compiling would have been done with the compiler options selected for 'minimize code size' and 'optimize code'. The original game (versions 1.0 and 1.1) fit onto a 1.44 meg floppy - and that was with the documentation and help file.

Back in these days (which isn't so long ago in the history of the computer and that I have lived and worked through) - we CARED about code size and efficiency. You could easily play Stars! on any PC that would run Windows 3.1

So folks - there you have it in a nutshell.

Ptolemy
Emperor of a Thousand Suns




Though we often ask how and why, we must also do to get the answers to the questions.

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 15:51 Go to previous messageGo to next message
m.a@stars is currently offline m.a@stars

 
Commander

Messages: 2765
Registered: October 2004
Location: Third star to the left
Ptolemy wrote on Sat, 09 April 2005 21:25


Stars! was created BEFORE Windows 95 - back in the days of Windows 3.1 and the early internet explosion. Size WAS important. Hard disks rarely capped 250 megs back then and home broadband didn't exist.


I still remember the day I increased the number of backup folders in my good ole' 80 MB disk, and after a string of testbeds got the dreaded "insufficient disk space" error! Shocked

Quote:


Back in these days (which isn't so long ago in the history of the computer and that I have lived and worked through) - we CARED about code size and efficiency. You could easily play Stars! on any PC that would run Windows 3.1



Heh, nowadays it would be great to be able to run games that fit on a single CD and didn't require a CRAY inside the graphics card...



So many Stars, so few Missiles!

In space no one can hear you scheme! Deal

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 16:08 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
Kotk wrote on Sat, 09 April 2005 15:02

Actually i suspect they bitpacked everything since they just loved to do it. Why to squeeze planets x, y and name_id into 4 bytes in xy file? Why not to use logical 6 bytes? Its e-mailed only once so why to save these 2 kilobytes? Very minor effect.



Agree with you there. No sane person would do something like that Wink Also, does racefile really matter? This is only sent once on game set up. And if they wanted to save size of the racefiles, it could be a hell of a lot smaller than it currently is!

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 16:14 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
Kotk wrote on Sat, 09 April 2005 15:02

EXE itself is bit bigger than logical thanks to very lot of bitpacking code.



It's true that bitpacking code increases EXE size. However, compressed strings also decrease the size.

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 16:16 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
m.a@stars wrote on Sat, 09 April 2005 15:51

Heh, nowadays it would be great to be able to run games that fit on a single CD and didn't require a CRAY inside the graphics card...



Let me dig out my copies of digger, spacewar and sopwith Wink

I've actually stopped playing games about the time everybody decided 3D FPS was the only way to go. :/

Report message to a moderator

Re: Planet value calculation made easy! Sat, 09 April 2005 17:45 Go to previous messageGo to next message
PricklyPea is currently offline PricklyPea

 
Lieutenant

Messages: 534
Registered: February 2005
PricklyPear wrote on Sat, 09 April 2005 16:16

Let me dig out my copies of digger, spacewar and sopwith Wink


Just spent the time between last post and this post playing digger (www.digger.org) and watching the hall of fame. I officially need to get a life! Wink

Report message to a moderator

Re: Planet value calculation made easy! Thu, 14 April 2005 14:09 Go to previous messageGo to next message
LEit is currently offline LEit

 
Lt. Commander

Messages: 879
Registered: April 2003
Location: CT
PricklyPear wrote on Sat, 09 April 2005 17:45

Just spent the time between last post and this post playing digger (www.digger.org) and watching the hall of fame. I officially need to get a life! Wink


Only an hour? Bah! You're an amateur addict.



- LEit

Report message to a moderator

Re: Planet value calculation made easy! Tue, 02 October 2007 17:36 Go to previous messageGo to previous message
yartrebo is currently offline yartrebo

 
Petty Officer 3rd Class

Messages: 43
Registered: July 2006
Location: North America
Quote:

It's true that bitpacking code increases EXE size. However, compressed strings also decrease the size.

You can reduce both string size and EXE size by using generic compression such as bz2 or zip. Most compression algorithms handle extra 0s very easily and the bitpacking will do little to increase compression.

The compression will slow down the opening of the file a bit, but it will neither bloat the codebase nor impose tight constraints the way bitpacking does.

I am using some bitpacking the stars! clone I'm writing, but it is limited to places where it will not impose restrictions such as storing all LRTs in a 32-bit dword, where performance will be equal to or faster than using separate variables, and where the code bloat will be marginal. For the LRT examples, it's faster than using a bunch of 8-bit bytes since 8-bit operations are very slow, doesn't need as much RAM (speeding up cache performance), and can be tested in two machine operations (and bitfield, mask[IFE]; jnz), which is as fast as if I spent a whole 32-bits for each trait (xor lrt[IFE], 0x0; jnz).


[Updated on: Tue, 02 October 2007 17:38]

Report message to a moderator

Previous Topic: Research
Next Topic: Ship Teleportation bug
Goto Forum:
  


Current Time: Fri Apr 19 05:51:22 EDT 2024