Jump to content
  • Advertisement
Sign in to follow this  
Sync Views

random number question

This topic is 3772 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there some way I can have two instances of rand? The reason is that for the actaul gameplay I want one, (which I will set and record the seed of at the start of the level), then a seprate one for user stuff (eg which of 3 diffrent things does a unit say when given a move order). This way I can "replay" a level just by tracking the commands given to the units etc each update, and the level will play out exactly the same. (without having to also track everything the player does that might result in a call to rand()) Also for multiplayer this means that things won't get out of sync because rand() was called for UI purposes or something on only one client.

Share this post


Link to post
Share on other sites
Advertisement
Yes: Don't use a random number generator like rand() which stores its state in a hidden, implementation-defined way. Instead, use something like boost::random, which is very flexible and allows you to save and reload the state of the RNG. There's also a C interface for reentrant rand() named rand_r(), but it isn't nearly as flexible.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
Is there some way I can have two instances of rand?

Sure, the last resort is to write your own Pseudo Random Number Generator class. The easiest principle is to initialize a number x with a seed and then get the next random number by doing

x := x * a + c

See Wikipedia article for further reading. There you also find nice values for a and c.

Here is my improvised stab at the problem. You can provide your own seed or let the implementation choose one based on time and a smear value. This ensures that multiple instances created within the same second still start with different seeds - time(0) only changes once per second.

class MyRand
{
static unsigned smear;
unsigned random;
public:
const unsigned seed;

MyRand(unsigned seed = time(0) ^ smear): random(seed), seed(seed)
{
smear = smear * 1103515245 + 12345;
}

void rewind()
{
random = seed;
}

unsigned operator()()
{
return random = random * 69069 + 5;
}

unsigned operator()(unsigned bound)
{
return operator()() % bound;
}

int operator()(int min, int max)
{
return operator()(max - min + 1) + min;
}
};

unsigned MyRand::smear(0);

int main()
{
MyRand r;
MyRand s;

std::cout << r() << std::endl;
std::cout << r() << std::endl;
std::cout << r() << std::endl << std::endl;

std::cout << s() << std::endl << std::endl;

r.rewind();
std::cout << r() << std::endl;
std::cout << r() << std::endl;
std::cout << r() << std::endl << std::endl;

MyRand t(r.seed);
std::cout << t() << std::endl;
std::cout << t() << std::endl;
std::cout << t() << std::endl << std::endl;
}


Note how you get the exact same sequence of numbers by either
a) rewinding r, or
b) initializing t with r's seed

The operator()(unsigned bound) implementation isn't very good, because with even bounds, the least significant bit always flips, so for example successive calls to r(10) will yield ...odd-even-odd-even-odd-even... numbers. I tried to improve it, but I'm not 100% sure my approach is correct:

unsigned operator()(unsigned bound)
{
/* 1 */ unsigned div = std::numeric_limits<signed>::min();
/* 2 */ div /= bound;
/* 3 */ return operator()() / div >> 1;
}

I would actually love to write

div = (std::numberic_limits<unsigned>::max() + 1) / bound;
return operator()() / div;

but of course a number one greater than the maximum is very unlikely to exist ;-)



Aha, my gut feeling was right, I found a corner case where operator(int bounds) yielded an illegal value.

In line 2, we do an integer division. If div is not an integral multiple of bound (this is true for every number made up of prime factors other than 2), we throw away the fractional part, thus effectively rounding down. That means div is actually a little too small, and for some (very few) large values of random, the division in line 3 yields a value that is too high (exactly bound, but the result should be lower than bound).

The workaround is to perform the first division with rounding up. In integer arithmetic, we can emulate a/b with rounding up by doing (a+b-1)/b.

unsigned operator()(unsigned bound)
{
unsigned div = std::numeric_limits<signed>::min();
div += bound - 1; // the next division should round up...
div /= bound;
return operator()() / div >> 1; // ...so that this division nexer exceeds bounds
}

This would have been a very hard to trace bug. What do we learn from this?
a) Always test corner cases. Just see what happens if random has the highest possible value.
b) Don't reinvent the wheel, use boost::random ;-)

There are still issues to fix, for example very high values of bound will yield nonsense values because of overflow, plus min and max should be checked for consistency.

We can even prove that this fix indeed does produce correct values by checking all legal values for bound:

for (unsigned i = 1, k = std::numeric_limits<signed>::max(); i <= k; ++i)
{
unsigned div = std::numeric_limits<signed>::min();
div += i - 1; // fix
div /= i;
unsigned x = std::numeric_limits<unsigned>::max() / div >> 1;
if (x >= i) std::cout << i << std::endl;
}

This takes about a minute to prove on my computer. If you take away the "// fix" line, you get all numbers that are not powers of two, as I predicted.

[Edited by - DevFred on June 23, 2008 5:09:25 PM]

Share this post


Link to post
Share on other sites
I took a look at the boost\random but that really confuses me on how to do what I want...


class DLL Random
{
public:
virtual double Uniform()=0;//0 <= x < 1. Uniform distribution
virtual double Uniform(double Min, double Max)=0;//Min <= x < 1. Uniform distribution
virtual double Gaussian()=0;//0 <= x < 1. More dense in the centre
virtual double InverseGaussian()=0;//0 <= x < 1. Inverse

virtual unsigned GetSeed()=0;
virtual void SetSeed(unsigned s)=0;
};




Basicly I want to have at least that functionality, so that I can just pass a pointer to my functions.

I'll take a look at DevFred's implemntation, at least I can follow whats going on there :)

[Edited by - Sync Views on June 23, 2008 5:19:04 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
I'll take a look at DevFred's implemntation, at least I can follow whats going on there :)

You're welcome. Before you get into any trouble because of static member initializations and header files, I split the latest version up for you:

myrand.h
#ifndef MYRAND_H
#define MYRAND_H

#include <ctime>
#include <limits>

class MyRand
{
static unsigned smear;
unsigned random;
public:
const unsigned seed;

MyRand(unsigned seed = time(0) ^ smear): random(seed), seed(seed)
{
smear = smear * 1103515245 + 12345;
}

void rewind()
{
random = seed;
}

unsigned operator()()
{
return random = random * 69069 + 5;
}

unsigned operator()(unsigned bound)
{
unsigned div = std::numeric_limits<signed>::min();
div += bound - 1;
div /= bound;
return operator()() / div >> 1;
}

int operator()(int min, int max)
{
return operator()(max - min + 1) + min;
}
};

#endif


myrand.cpp
#include "myrand.h"

unsigned MyRand::smear(0);


your own code
#include "myrand.h"
#include <iostream>

int main()
{
MyRand test;
std::cout << test(10) << std::endl;
}


Have fun with it and report any problems you have.

Share this post


Link to post
Share on other sites
I implemented you generator into my class, although I changed how the number is returned to this for the 0 <= x < 1 range:
return (double)r / (std::numeric_limits<unsigned>::max)();


class rng : public Random
{
unsigned r,s;
public:
rng();
rng(unsigned s);
virtual unsigned GetSeed();
virtual void SetSeed(unsigned s);

virtual double Uniform();
virtual double Uniform(double Min, double Max);
};




rng::rng()
{
r = s = (unsigned)(time(NULL) % 0xFFFFFFFF);//so it works with a 64bit time stamp
}
rng::rng(unsigned int _s)
: r(_s), s(_s)
{}
unsigned rng::GetSeed()
{
return s;
}
void rng::SetSeed(unsigned _s)
{
r = s = _s;
}
double rng::Uniform()
{
r = r * 69069 + 5;
return (double)r / (std::numeric_limits<unsigned>::max)();
}
double rng::Uniform(double Min, double Max)
{
return Uniform()*(Max - Min) + Min;
}



So I made a quick test to see if this worked, and got some intresting results

rng::uniform()
Tests: 100000000
Distribution over 0.1 blocks:
0.0999577
0.0999817
0.1000150
0.0999711
0.1000210
0.1000200
0.0999882
0.1000030
0.1000170
0.1000260
000000000
Time taken: 4.25 seconds
Numbers per second: 23529000

rand()/(double)RAND_MAX
Tests: 100000000
Distribution over 0.1 blocks:
0.0999927
0.0999800
0.1000170
0.0999700
0.0999731
0.0999819
0.0999994
0.1000150
0.1000210
0.1000190
3.044e-005 <--ok...so why are there results over 1?
Time taken: 8.032 seconds
Numbers per second: 12450000


[Edited by - Sync Views on June 24, 2008 8:40:15 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
3.044e-005 <--ok...so why are there results over 1?

Your fault is in this line of code:

return (double)r / (std::numeric_limits<unsigned>::max)();

What happens if r IS std::numeric_limits<unsigned>::max()? You get exactly 1. You need to divide by one more, but since that number isn't representable as an unsigned, you have to cast that to double first.
Rewrite the line to this and tell me if that fixes the problem:

return r / (1.0 + std::numeric_limits<unsigned>::max());

Furthermore, why do you inherit from Random?

Plus this line of code looks silly:

r = s = (unsigned)(time(NULL) % 0xFFFFFFFF);//so it works with a 64bit time stamp

If you want the lowest 32 bit, don't divide by 0xFFFFFFFF, but instead BITWISE AND by 0xFFFFFFFF. Plus you don't really need that, just assign to s and r. It will get truncated automatically:

r = s = (time(NULL);

Share this post


Link to post
Share on other sites
THe thing is, the test that failed was with the standard rand()...

I can see how sometimes my rng::uniform will fail now though.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
THe thing is, the test that failed was with the standard rand()...

Oh :) Well, you also have to divide by one more than the maximum with rand() if you want to get values < 1.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
3.044e-005 <--ok...so why are there results over 1?


3.044e-005 is scientific notation for 0.00003044 ;) so it's not generating over 1 at all, just closer to 0.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!