OpenArena Message Boards

id Tech 3 => cgame/game/ui => Topic started by: The Geez on September 12, 2011, 03:07:35 pm



Title: Better random numbers?
Post by: The Geez on September 12, 2011, 03:07:35 pm
Currently I am employing the following method of returning a random number between a range, but i dont believe this is the best way to do it, anyone have any other ways of doing this?

int a, b, c, d;

a = rand() % 40 + 10;
b = rand() % 40 + 10;
c = rand() % 45 + 25;
d = rand() % -10 + (-20);




Title: Re: Better random numbers?
Post by: 7 on September 12, 2011, 04:47:55 pm
Quote from: man 3 rand
NOTES
       The  versions of rand() and srand() in the Linux C Library use the same
       random number generator as random(3) and srandom(3), so the lower-order
       bits  should  be as random as the higher-order bits.  However, on older
       rand() implementations, and on  current  implementations  on  different
       systems,  the  lower-order  bits  are much less random than the higher-
       order bits.  Do not use this function in applications  intended  to  be
       portable when good randomness is needed.  (Use random(3) instead.)

If you insist on using high-order bits and not random(), you'll have to use floating point arithmetic:

Quote from: Numerical Recipes in C: The Art of Scientific Computing
If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

    j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));


Title: Re: Better random numbers?
Post by: VortexHU on September 12, 2011, 04:51:35 pm
what is the issue that you see with your approach? top google results use it. if the problem is that you're not getting floating-point numbers, see 7's reply.

http://www.safercode.com/blog/2009/12/08/random-number-between-two-integers.html
http://www.dreamincode.net/forums/topic/65642-random-number-between-2-ints/


Title: Re: Better random numbers?
Post by: The Geez on September 12, 2011, 04:58:50 pm
Quote from: man 3 rand

If you insist on using high-order bits and not random(), you'll have to use floating point arithmetic:
Quote from: Numerical Recipes in C: The Art of Scientific Computing
If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

    j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

Yes, I found something along the lines of this as well.. Just wondering if Q3 had any special built-in functions for this. From this information, I have derived the following, and it works very well:

a = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));      
b = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));
c = 1 + (int) (45.0 * (rand() / (32768 + 25.0)));
d = 1 + (int) (-10.0 * (rand() / (32768 + -20.0)));

Instead of using RAND_MAX, I just plugged in the 32768 myself.

Thanks!



UPDATE: This does not seem to work accurately, here's a file of the generated results.



Title: Re: Better random numbers?
Post by: The Geez on September 12, 2011, 05:06:20 pm
Ultimately, I think this is the best way to do it, but I havent figured out how to do this in Q3.. I need to call time into it somehow.

http://www.linuxquestions.org/questions/programming-9/random-number-in-c-linux-760390/#post3712743 (http://www.linuxquestions.org/questions/programming-9/random-number-in-c-linux-760390/#post3712743)


Title: Re: Better random numbers?
Post by: 7 on September 12, 2011, 05:23:23 pm
I have derived the following, and it works very well:

a = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));      
b = 1 + (int) (40.0 * (rand() / (32768 + 10.0)));
c = 1 + (int) (45.0 * (rand() / (32768 + 25.0)));
d = 1 + (int) (-10.0 * (rand() / (32768 + -20.0)));

Instead of using RAND_MAX, I just plugged in the 32768 myself.

Does this really what you want? Also, RAND_MAX is usually 32767.

The 1.0 in the (rand() / (RAND_MAX + 1.0)) expression is a constant, this expression produces a good standard random number in the range [0..1> (a fraction from 0 to 0.999...), the (RAND_MAX + 1.0) part of this expression serves to a) convert into a float and b) guarantee that the result of the division is always < 1.

So I think what you really want is:
Code:
a = 10 + (int) (40.0 * (rand() / 32768.0));
b = 10 + (int) (40.0 * (rand() / 32768.0));
c = 25 + (int) (45.0 * (rand() / 32768.0));
d = -20 + (int) (-10.0 * (rand() / 32768.0));


Title: Re: Better random numbers?
Post by: The Geez on September 12, 2011, 05:36:01 pm
Quote
So I think what you really want is:
Code:
a = 10 + (int) (40.0 * (rand() / 32768.0));
b = 10 + (int) (40.0 * (rand() / 32768.0));
c = 25 + (int) (45.0 * (rand() / 32768.0));
d = -20 + (int) (-10.0 * (rand() / 32768.0));

Produces the following results:
A:47, B:40, C:25, D:-20
A:27, B:32, C:51, D:-24
A:37, B:34, C:48, D:-29
A:20, B:34, C:31, D:-21
A:20, B:42, C:38, D:-28
A:21, B:46, C:40, D:-27
A:27, B:15, C:29, D:-26
A:20, B:17, C:67, D:-20
A:46, B:22, C:55, D:-29
A:48, B:18, C:55, D:-27

Strange, but still not completely accurate
And thanks for the heads up on the RAND_MAX, I assumed 32768.. my bad.. but the results are still slightly inaccurate.


Title: Re: Better random numbers?
Post by: 7 on September 12, 2011, 05:54:20 pm
Strange, but still not completely accurate
And thanks for the heads up on the RAND_MAX, I assumed 32768.. my bad.. but the results are still slightly inaccurate.

Well, I didn't exactly give a heads up, I wrote usually. ;) More so because when you sometimes get numbers greater than the maximum you're expecting for A,B,or C, or numbers smaller than the minimum for D, this can only mean that the real RAND_MAX must be greater than 32767. What are you coding in? Quake lcc?

Edit:
On second thought: I can't see what's wrong with your results: A and B should be in range [10..49], C in range [25..69] and D in range [-29..-20] and they all are if I'm not completely blind, so I guess you really wanted other ranges?


Title: Re: Better random numbers?
Post by: The Geez on September 12, 2011, 06:02:48 pm
Quote
What are you coding in? Quake lcc?

I am just using gedit, and compiling with make in linux? Whats Quake lcc? lol

Forgive my ignorance, I'm still figuring a lot of stuff out.


Title: Re: Better random numbers?
Post by: 7 on September 12, 2011, 06:11:35 pm
Quote
What are you coding in? Quake lcc?

I am just using gedit, and compiling with make in linux? Whats Quake lcc? lol

Forgive my ignorance, I'm still figuring a lot of stuff out.

No problem, just write what ranges (minimum and maximum numbers) you really want for A, B, C and D and I'll try to help.

Edit:
Perhaps you want something like this?:
Code:
#include <stdlib.h> /* Pull in rand() and RAND_MAX */
#include <stdio.h> /* Pull in printf() */

int my_rand( int min, int max )
{
return min + (int) ((max - min + 1) * (rand() / (RAND_MAX + 1.0)));
}

int main( void )
{
int c;
for ( c = 0; c < 1000; ++c ) {
printf( "A:%2d B:%2d C:%2d D:%3d\n",
my_rand( 10, 40 ),
my_rand( 10, 40 ),
my_rand( 25, 65 ),
my_rand( -30, -20 )
);
}
return 0;
}


Title: Re: Better random numbers?
Post by: The Geez on September 12, 2011, 07:14:44 pm
Thanks, I will try that!   :)


Title: Re: Better random numbers?
Post by: sago007 on September 13, 2011, 11:22:31 am
You cannot improve on the default rand in ioquake3. It is implemented like this:

Code:
int rand( void ) {
randSeed = (69069 * randSeed + 1);
return randSeed & 0x7fff;
}

I don't know how much better you can make it if you are limited to 16 bit integers.

The C reference rand implementation is a lot bigger:
Code:
int rand(void)
{
  randSeed = randSeed * 1103515245 +12345;
  return (unsigned int)(randSeed/65536) % 32768;
}

Just remember that changing a variable or a attempting to make it better usually makes it a lot worse. Changing any constant is likely to make the function very predictable.

One can attempt to use alternative constants but one must remember to analyze the result for patterns. There are a lot of statistical work that needs to be done to test a random-function.


Title: Re: Better random numbers?
Post by: 7 on September 13, 2011, 01:08:57 pm
Well, you can do better, but its not easy.  The ioquake3 pseudorandom number generator is the "stolen" old VAX MTH$RANDOM linear congruential generator (http://en.wikipedia.org/wiki/Linear_congruential_generator).

These LCG's (algorithms of type seed = BigPrime * seed + SmallPrime (% (MediumPrime + 1))) have some bad properties like high serial correlation (if you have a few random numbers, you can predict the next one), small period (the generated sequences repeat after relatively few numbers, specially if you isolate low-order bits) and bad distribution (not all numbers in the range 0..MediumPrime get generated).

If you need random numbers for serious work, a Mersenne twister (http://en.wikipedia.org/wiki/Mersenne_twister) algorithm generally is a much better choice (but much more expensive in CPU time).


Title: Re: Better random numbers?
Post by: grey matter on November 14, 2011, 02:54:53 pm
Take a look at qnoiz (http://icculus.org/~phaethon/q3/nbrng/nbrng.html) for Quake3 QVM. It allows to create better random numbers by using non-deterministic data such as human player input etc.

I haven't tested this, but it looks quite promising.


Title: Re: Better random numbers?
Post by: Cacatoes on November 14, 2011, 03:28:03 pm
In which part of the game could we see effects from this ? Spawn points ?


Title: Re: Better random numbers?
Post by: grey matter on November 14, 2011, 03:38:20 pm
The code is meant to be used in the game module, so yes, spawnpoint logic could benefit from it. Be aware that the current code selects e.g. a random furthest spawnpoint and thereby limits the number of choices anyways.

I can not really think of a place in game code where you would badly need better random numbers. The engine itself already uses /dev/urandom and such.