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

botmeister 08-01-2004 04:17

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
Adobe is NOT standard post script, it's a proprietory format which sucks. To view standard post script documents, get these apps from here
http://www.cs.wisc.edu/~ghost/index.htm

I just tested the tiny random algo and it seems to work very well. It's supposed to generate a uniform distribution and is at least as good as rand().

dav 08-01-2004 04:20

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
well, i think Pagemaker has a PostScript import option, and you might look for other programs that can read PostScript as well.

Pierre-Marie Baty 08-01-2004 05:00

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
k, I'm getting GhostView and GS 8.11 right now. WTF, they weight LESS than the zipped Acrobat Reader and they do so much more !!!

dav 08-01-2004 05:04

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
lol - corporate software design for you there ;)

botmeister 08-01-2004 08:22

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
btw, I liked this book so much I downloaded the whole thing

http://www.ma.utexas.edu/documentation/nr/bookc/

It is not just about random number generation and has a lot of really usefull programming info.

Pierre-Marie Baty 08-01-2004 08:37

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
yes, I was scared off just when I saw that word: "Knuth" ;)

Austin 08-01-2004 09:07

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

Originally Posted by botmeister
btw, I liked this book so much I downloaded the whole thing

http://www.ma.utexas.edu/documentation/nr/bookc/

It is not just about random number generation and has a lot of really usefull programming info.

utexas.edu ??

Of course!
The best comes from Austin!

Bert 08-01-2004 13:11

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
This may sound stupid, but should I set the seed more than once to ensure a more random result, or is setting it once enough (as in the numbers are random enough)?

Killaruna 08-01-2004 14:03

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
You set the seed once before using the rand() function for the first time. Note that the same seed always produces the same line of "random" numbers.

Bert 08-01-2004 14:23

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
Alright thanks, I've been doing it the right way then :)

botmeister 08-01-2004 17:11

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
You can use a seed derived from the system clock, that way each time your comupter app runs, it will use a different seed.

Whistler 14-04-2006 09:56

Re: Portable, self-contained replacements for RANDOM_STUFF()
 
this is related with this thread, so instead opening a new one, just posting here.

well here is my implemention of random generator derived from an article in "Game Programming Gems", with a bit improvement, which is less "twisted" but random enough I guess:

PHP Code:

static long glSeed 0glGen2 0glGen1 0// our random number generator's seed

/**
 * This function initializes the random seed based on the initial seed value pass in the
 * initial_seed parameter.
 */
void lsrand(unsigned long initial_seed)
{
   
// Pick two large integers such that one is double the other
   
glGen2 3719;
   
glGen1 glGen2 2;

   
// fill in the initial seed of the random number generator
   
glSeed = (glGen1 initial_seed) + glGen2;
}

/**
 * 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 f$
 * able to generate 32-bit random numbers. Isn't that nice?
 */
long lrand(void)
{
   if (
glSeed == 0// if the random seed isn't initialized...
      
lsrand(time(NULL)); // initialize it first
   
glSeed = (glGen1 glSeed) + glGen2// do some twisted math
   
return glSeed glSeed : -glSeed// and return absolute value of the result
}

/**
 * This function returns a random integer number between (and including) the starting and
 * ending values passed by parameters from and to.
 */
long RandomLong(long fromlong to)
{
   if (
to <= from)
      return 
from;

   return 
from lrand() / (LONG_MAX / (to from 1));
}

/**
 * This function returns a random floating-point number between (and including) the starting
 * and ending values passed by parameters from and to.
 */
long RandomLong(long fromlong to)
{
   if (
to <= from)
      return 
from;

   return 
from + (float)lrand() / (LONG_MAX / (to from));


btw, as long as the PDF spec. and free pdf viewers like xpdf are publically available (gv is also able to open pdf file), there is not problem to use the pdf format and it still sucks less than e.g., .doc format (except its DRM "features")... :)


All times are GMT +2. The time now is 23:07.

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