.:: Bots United ::.

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   General Bot Coding (http://forums.bots-united.com/forumdisplay.php?f=24)
-   -   Portable, self-contained replacements for RANDOM_STUFF() (http://forums.bots-united.com/showthread.php?t=244)

Pierre-Marie Baty 07-01-2004 18:21

Portable, self-contained replacements for RANDOM_STUFF()
 
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, w00t w00t mateys

Code:

// 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

:D

Pierre-Marie Baty 07-01-2004 19:32

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
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 07-01-2004 20:19

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
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 :D

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

koraX 07-01-2004 20:56

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
This lrand() seems not very random to me, I think rand() uses more 'randomly' algorithm. But maybe it's just me ... :D

botmeister 07-01-2004 21:13

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
Quote:

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 ... :D

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 07-01-2004 21:53

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
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 07-01-2004 22:33

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
***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 07-01-2004 23:55

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
Quote:

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

Code:

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


Pierre-Marie Baty 08-01-2004 02:39

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
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 08-01-2004 04:15

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
Quote:

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


All times are GMT +2. The time now is 14:54.

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.