Portable, self-contained replacements for RANDOM_STUFF()

[Pierre-Marie Baty]

since we can't use rand() for replacing RANDOM_LONG() and RANDOM_FLOAT() and thus save costy engine calls each time, because rand() only returns short integers and not longs, a portable, fast, and self-contained random number generator is something nice indeed

irwigo, mateys

// RACC - AI development project for first-person shooter games derived from Valve's Half-Life
// (http://racc.bots-united.com/)
//
// The game to engine interfacing code is based on the work done by Jeffrey 'botman' Broome
// (http://planethalflife.com/botman/)
//
// This project is partially based on the work done by Eric Bieschke in his BSDbot
// (http://gamershomepage.com/csbot/)
//
// This project is partially based on the work done by Brendan "Spyro" McCarthy in his ODD Bot
// (http://oddbot.hlfusion.com/)
//
// This project is partially based on the work done by Alistair 'eLiTe' Stewart in his TEAMbot
// (http://www.planethalflife.com/teambot/)
//
// Rational Autonomous Cybernetic Commandos AI
//
// lrand.cpp
//
 
#include "racc.h"
 
 
// maximum value returned by our number generator (2^31 - 1 = 0x7FFFFFFF)
#define LRAND_MAX 2147483647L
 
 
long lseed; // our random number generator's seed
 
 
void lsrand (unsigned long initial_seed)
{
   // this function initializes the random seed based on the initial seed value passed in the
   // initial_seed parameter. Since random seeds are usually initialized with the time of day,
   // and time is a value that changes slowly, we bump the seed twice to have it in a more
   // random state for future calls of the random number generator.
 
   lseed = (long) initial_seed; // fill in the initial seed of the random number generator
   lseed = lrand (); // bump it once
   lseed = lrand (); // bump it twice
 
   return; // that's all folks
}
 
 
long lrand (void)
{
   // this function is the equivalent of the rand() standard C library function, except that
   // whereas rand() works only with short integers (i.e. not above 32767), this function is
   // able to generate 32-bit random numbers. Isn't that nice ?
 
   // credits go to Ray Gardner for his fast implementation of minimal random number generators
   // http://c.snippets.org/snip_lister.php?fname=rg_rand.c
 
   static unsigned long lrand_lo, lrand_hi;
 
   // compose the two 16-bit parts of the long integer and assemble them
   lrand_lo = 16807 * (long) (lseed & 0xFFFF); // low part
   lrand_hi = 16807 * (long) ((unsigned long) lseed >> 16); // high part
   lrand_lo += (lrand_hi & 0x7FFF) << 16; // assemble both in lrand_lo
 
   // is the resulting number greater than LRAND_MAX (half the capacity) ?
   if (lrand_lo > LRAND_MAX)
   {
	  lrand_lo &= LRAND_MAX; // then get rid of the disturbing bit
	  lrand_lo++; // and increase it a bit (to avoid overflow problems, I suppose)
   }
 
   lrand_lo += lrand_hi >> 15; // now do twisted maths to generate the next seed
 
   // is the resulting number greater than LRAND_MAX (half the capacity) ?
   if (lrand_lo > LRAND_MAX)
   {
	  lrand_lo &= LRAND_MAX; // then get rid of the disturbing bit
	  lrand_lo++; // and increase it a bit (to avoid overflow problems, I suppose)
   }
 
   // now we've got our (pseudo-)random number.
 
   lseed = (long) lrand_lo; // put it in the seed for next time
   return (lseed); // and return it. Yeah, simple as that.
}
 
 
long RandomLong (long from, long to)
{
   // this function returns a random integer number between (and including) the starting and
   // ending values passed by parameters from and to.
 
   if (to <= from)
	  return (from);
 
   return (from + lrand () / (LRAND_MAX / (to - from + 1)));
}
 
 
float RandomFloat (float from, float to)
{
   // this function returns a random floating-point number between (and including) the starting
   // and ending values passed by parameters from and to.
 
   if (to <= from)
	  return (from);
 
   return (from + (float) lrand () / (LRAND_MAX / (to - from)));
}
 
 
// "Anyone who consider arithmetic means of producing random number is,
// of course, in a state of sin"
//				 -- John Von Neumann

[Pierre-Marie Baty]

aha, one feature is missing though.
To make them behave exactly like the engine's RANDOM_LONG() and RANDOM_FLOAT(), add this check on top of the RandomLong() and RandomFloat() functions:

PHP Code:

   if (to <= from)
      return (from); 


[@$3.1415rin]

I have somewhere a random number lib, but I guess it's not really useful for our purposes here ... it's just providing functions for random numbers based on the first 10 million or whatever you want digits of pi

pi is known to be a really good random number source ...

[koraX]

This lrand() seems not very random to me, I think rand() uses more 'randomly' algorithm. But maybe it's just me ...

[botmeister]

Originally Posted by koraX

This lrand() seems not very random to me, I think rand() uses more 'randomly' algorithm. But maybe it's just me ...

You could make an adaption to lrand( ) by concatinating the result of rand() called twice. For example

lrand_lo = rand()
lrand_hi = rand()
lrand_lo += (lrand_hi & 0x7FFF) << 16;

// obviously more thought behind this idea will be
// needed to make this work properly

Also don't forget that mostly scientific applications require highly precise random number generation. For gamming purposes even using bits from the system clock is good enough, and what you normally favor is performance over accuracy.

For the most part 16 bit rand() is more than good enough I think. Can anyone come up with a reason why 16 bots is not enough?

[Pierre-Marie Baty]

yes... more than 32767 waypoints/nodes/walkfaces/navlinks/whatever.

One reason among others

Also, I assure you that the random results are very convincing : the algorithm is based on an infinite math suite, whose start point is determined by the initial seed - and this implementation is VERY fast, much faster than calling rand() twice. I believe the guy who wrote this did a math paper somewhere, it must be lying around on the net

[Pierre-Marie Baty]

***BUGBUGBUG***

The RandomFloat() function was incorrect! It was returning numbers above the limit due to the "(to - from + 1)" bit! It's fixed now.

When I say I can't line up two words in C without writing a state of the art bug!

[botmeister]

Originally Posted by Pierre-Marie Baty

yes... more than 32767 waypoints/nodes/walkfaces/navlinks/whatever.

One reason among others

Also, I assure you that the random results are very convincing : the algorithm is based on an infinite math suite, whose start point is determined by the initial seed - and this implementation is VERY fast, much faster than calling rand() twice. I believe the guy who wrote this did a math paper somewhere, it must be lying around on the net

Yes, it is supposed to be a good random generator algo, look for references
S.K. Park and K.W. Miller, Communications of the ACM 31:10 (Oct 1988, and "Two Fast Implementations of the 'Minimal Standard' Random Number Generator", David G. Carta, Comm. ACM 33, 1 (Jan 1990), p. 87-88 linear congruential generator f(z) = 16807 z mod (2 ** 31 - 1) uses L. Schrage's method to avoid overflow roblems


I found this on-line postscript book http://www.ma.utexas.edu/documentation/nr/bookc/

Look at c7-1.ps it discusses a lot of things, and it says this is probably the simplest and fastest random number generator of all

unsigned long idnum;
 
unsigned long lrand( )
{
idnum = 1664525L * idnum + 1013904223L;
return idnum;
}

[Pierre-Marie Baty]

what do you use for viewing .ps files under Windows ? Acrobat Reader 6 doesn't seem to want to read it

I can't wait to see what they say, because your tiny number generator looks really lovely !

[Austin]

Originally Posted by Pierre-Marie Baty

what do you use for viewing .ps files under Windows ?

ghost script

And your have a mis-leading comment in your code.
float RandomFloat (float from, float to)
{
// this function returns a random integer