Sign in to follow this  
Dark_Oppressor

Outgrowing rand()

Recommended Posts

Dark_Oppressor    163
I'm making a networked game in c++ that has a lot of particles (not just for looks, they are a gameplay thing). These particles use tons of calls to rand() to determine their movement. When a game starts, I've been using srand() to start a new sequence of numbers for everyone with a shared seed. Due to the number of particles in the game, I am using a lock-step system, which also allows me to ensure an identical sequence of calls to rand() for each client. However, I would also like to use random numbers in displaying these particles, which means that I need a second rand(), essentially. Since I know of no way to use rand() in this way, I thought now might be a good time to find a new way to generate random numbers. Since this is a game, I only need a nice pseudo-random number generator. However, I guess what I need is a RNG class or something, so I can use more than one RNG object at once. I just read that Boost has a random number generator class of some kind, so I was thinking of looking into that. What are your suggestions? If I could create my own, without need for adding another library to my project, that would be great. any recommended reading for creating my own pseudo-RNG? I've done some more research, and the Mersenne twister sounds pretty cool. I also read about WELL, which sounds like it might be even better, but I couldn't tell for sure. I would like to keep the possibility of one day selling this game (or some other game I write using some of this code). It looks like WELL is not for commercial use, but the Mersenne twister is. Is Mersenne probably good enough for my purposes? I'm guessing that it probably is. [Edited by - Dark_Oppressor on March 30, 2010 3:11:07 PM]

Share this post


Link to post
Share on other sites
Sneftel    1788
Boost.random is fine, especially if you're already using Boost in your project. Alternatively, implementing LCG or MT or pretty much any non-crypto-grade PRNG is pretty trivial.

Share this post


Link to post
Share on other sites
Dark_Oppressor    163
Thanks for the reply. I've got the Mersenne Twister implemented. I am using it to find a random range between 2 numbers. Here is the equation I'm using:

(mersenne_random_number()%range)+lownum




where lownum and highnum are the two numbers taken as parameters, and range is highnum-lownum+1.

I was reading up on this some more, and I've found some people saying that using the modulus like this might not give as good results as something along the lines of

lownum+(range*mersenne_random_number()/(MAX_MERSENNE_RESULT+1))



Is there any merit to that?

Share this post


Link to post
Share on other sites
Atrix256    539
The twister should be fine for your needs and i'm sure that minor tweak to it gives better number distribution, but that for your needs you won't even notice a difference.

For what you are doing, you don't need perfection, you just need "good enough", so give it a shot and if you have a problem (ie the particles are noticeably clustering in a way that looks bad) go from there (:

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Atrix256
For what you are doing, you don't need perfection, you just need "good enough", so give it a shot and if you have a problem (ie the particles are noticeably clustering in a way that looks bad) go from there (:

This. You'll find that PRNG geeks have a much stricter definition of what's "random looking" than you or I. Your bog-standard LCG will show real, clearly visible artifacts under some of the most normal of situations. Pretty much any other generator is very unlikely to.

Share this post


Link to post
Share on other sites
Kylotan    9871
Quote:
Original post by Dark_Oppressor
Thanks for the reply. I've got the Mersenne Twister implemented. I am using it to find a random range between 2 numbers. Here is the equation I'm using:

Don't do that. Instead, use the supplied uniform distribution stuff to generate the range of values you need.

http://www.boost.org/doc/libs/1_42_0/libs/random/index.html (see very first example)

If you create a distribution with exactly the numbers you need, you don't have to worry about the modulus or any of that. Obviously if you find yourself needing a wide variety of different ranges it gets a bit fiddly compared to modulus, but you can wrap it up in a function if you need.

It also paves the way for you to consider the more interesting distributions for other purposes, should you wish.

Share this post


Link to post
Share on other sites
taby    1265
Quote:
Original post by Sneftel
Quote:
Original post by Atrix256
For what you are doing, you don't need perfection, you just need "good enough", so give it a shot and if you have a problem (ie the particles are noticeably clustering in a way that looks bad) go from there (:

This. You'll find that PRNG geeks have a much stricter definition of what's "random looking" than you or I. Your bog-standard LCG will show real, clearly visible artifacts under some of the most normal of situations. Pretty much any other generator is very unlikely to.


This reminds me of a blog post... http://motls.blogspot.com/2009/04/perceiving-randomness-egalitarian-bias.html

Share this post


Link to post
Share on other sites
Smilediver    142
I'm using this one:

seed = seed * 1103515245 + 12345;
random = (seed >> 16) & 0x7FFF;

I don't remember where I took it from when I was doing my research on them, but it's pretty good, and does it's job. And since it's just a couple ops, it's fast, and should be perfect for particles.

Share this post


Link to post
Share on other sites
cache_hit    614
Quote:
Original post by Kylotan
It also paves the way for you to consider the more interesting distributions for other purposes, should you wish.


I always thought it was awesome that you can actually generate common alternative distributions like normal, logarithmic, etc by combining successive calls to rand with various operators like +, -, and *. And the results are often much faster than algorithms that generate these distributions natively.

I don't know how mathematically sound such methods are, but often mathematical soundness is not as important as speed. Gnu plot seems to suggest they're pretty accurate though.

Share this post


Link to post
Share on other sites
Dark_Oppressor    163
What I've done for now is use the Mersenne twister, but I should have specified that I'm not using Boost. I decided to go the fun learning route :-P

Anyway, it's working well enough for me now, I'm pretty happy with it. My particles are acting much more randomly than they did before.

Now, I'm off to build mountains of stone particles and then blow them up :-D

Share this post


Link to post
Share on other sites
speciesUnknown    527
here's the thing - you may be overengineering this. If the particles dont affect gameplay then there is no need to have identically appearing particle systems on all player machines. rand() is probably all you need.

Share this post


Link to post
Share on other sites
summaky    134
Quote:
Original post by speciesUnknown
here's the thing - you may be overengineering this. If the particles dont affect gameplay then there is no need to have identically appearing particle systems on all player machines. rand() is probably all you need.


Yes, except that:

Quote:
Original post by Dark_Oppressor
I'm making a networked game in c++ that has a lot of particles (not just for looks, they are a gameplay thing). [...]

Share this post


Link to post
Share on other sites
Dark_Oppressor    163
Quote:
Original post by summaky
Quote:
Original post by speciesUnknown
here's the thing - you may be overengineering this. If the particles dont affect gameplay then there is no need to have identically appearing particle systems on all player machines. rand() is probably all you need.


Yes, except that:

Quote:
Original post by Dark_Oppressor
I'm making a networked game in c++ that has a lot of particles (not just for looks, they are a gameplay thing). [...]


Haha, what he said. The whole thing is mostly particles, that's the game! :-P And it's multiplayer, and since there can be 500,000ish particles in the game at once, I am using a lock-step system, meaning that I need determinism for the particles.

Trust me, this little PRNG thing took like 30 minutes, it is the least of my worries. Now, learning all about networking, multiplayer programming, and the MILLION difficult things when using a lock-step system, that is a pain! Ok... and it's also a little fun. Heh.

And even if I didn't need determinism and such, I would still want this better PRNG. My particles look more natural now, and water flows much more naturally, instead of dancing around or trying to prefer one side or the other.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this