Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Where should the RNG live?

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Where should the RNG live?
Karadoc ~~
Member #2,749
September 2002
avatar

Sometimes I find that 'good' OO game design gets in the way of me getting stuff done.

One such problem that I'm currently wrestling with is the question of where the random number generator should reside.

I've got a class called "Game" which seems to be a natural place for it to go; but most of the game mechanics is actually done in the class called "World", and that's where most of the random numbers are needed. (Game has a World member variable.)

So I put the RNG inside World, and the Game class is allowed to use its world to get random numbers when it needs to.

However... now I've made a new class called MapGenerator, which is meant to be responsible for generating random maps – so it needs access to the random number generator as well, but there's no other reason for it to see anything else in World or Game or anything like that. And in the future, I'll probably think of new classes that are going to want to use the RNG...

The bottom line is that I'm starting to think the I should just make the RNG global, so that everything can use it. Or.. alternatively I could make it so that World, and MapGenerator, and anything else that needs the RNG, all require a reference to the RNG object in the constructor...

I'd just be curious to know how other people deal with this issue. Where should the RNG live so that everything that needs it can use it?

-----------

Arthur Kalliokoski
Second in Command
February 2005
avatar

I'd make it global, after all, the plain old libc rand() already is.

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

Audric
Member #907
January 2001

If your game will implement loading/saving, or demo saving/replaying, or if it will be a game server for multiple games taking place at the same time : It will help if you have one class that can store all the "state" of a game in progress. In that case, the RNG state is one of these pieces of data.
Otherwise, global is fine.

Karadoc ~~
Member #2,749
September 2002
avatar

Alright. Thanks for the advice. I'm going to make it global. I don't think it will be a big deal to absorb it back into Game sometime in the future if I need to.

And while we're not on the subject, let me just mention that I think Boost is excellent. (I'm using boost/random.hpp for my rng, and boost everything else for pretty much everything else in my game. :p)

-----------

OICW
Member #4,069
November 2003
avatar

If you don't plan having several instances running at the same time, you can make it a singleton, which is kind of global, but provides mechanisms to ensure only one instance of the class is created.

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

Oscar Giner
Member #2,207
April 2002
avatar

Why do all classes or objects in your game need the same instance of your random class? In my case each class that needs random numbers just has its own random generator instance (the class takes care that, unless you explicitly specify otherwise, each instance will generate a different sequence of random numbers).

Karadoc ~~
Member #2,749
September 2002
avatar

That's a good question.. and I suppose the answer is that they don't really need to use the same instance. But I do feel like they should use the same instance from a resources point of view. (Allegedly, the rng I'm using uses approximately 625*sizeof(uint32_t) bytes of memory.[1]) Also, I've written a few helper functions for generating random numbers in particular ways. Those helper functions need to refer to the rng - and I'd prefer to not have to pass the rng as an argument, or duplicate the functions.

As for the singleton suggestion. I've forgotten what the advantages of doing that are. Is it something to do with guaranteeing that the constructor / destructor will run?

References

  1. mt19937

-----------

gnolam
Member #2,030
March 2002
avatar

One PRNG per class seems a bit excessive, but I definitely wouldn't assume I'd need just one PRNG. There are good reasons to separate game logic and "special effects" random number generations, for example. Determinism is a good thing. :)

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

OnlineCop
Member #7,919
October 2006
avatar

I wouldn't suggesting having the RNG be implemented in multiple locations unless there is a very good reason to do so.

Take a casino game: the RNG is actually server-side so they can ensure that a programmer doesn't give too much favor to the player, and so they can keep track of their algorithm effectiveness.

In a multiplayer game, you need two RNGs: one that doesn't matter or affect anything (like for a particle system on a local client), and one that does (like where something will respawn). The "don't matter" ones are usually implemented in the Application:: scope, where everything has equal access to it, and it can be as pseudo-random as you want to spend time implementing.

The "does matter" ones are usually implemented in the Game:: or Network:: scopes, where the pseudo-randomness comes from the main server (external or on the same system, is the same).

I made a VR game!

james_lohr
Member #1,947
February 2002

That's a good question.. and I suppose the answer is that they don't really need to use the same instance. But I do feel like they should use the same instance from a resources point of view. (Allegedly, the rng I'm using uses approximately 625*sizeof(uint32_t) bytes of memory.[1]) Also, I've written a few helper functions for generating random numbers in particular ways. Those helper functions need to refer to the rng - and I'd prefer to not have to pass the rng as an argument, or duplicate the functions.

These are extremely poor reasons. You should be using a separate instance of your RNG class. The only excuse for using the same instance is when you want the same sequence of numbers, and requiring this across the game state and map generator makes no sense. Worrying about 625*sizeof(uint32_t) bytes of memory? - You need to get things in perspective.

Stick to correct OOP design. Maintainability is infinitely more important than a 0.00000001% of an average system's RAM, and if you break the rules here you will do it again and again, and soon enough your code will be mess that you won't want to reuse.

Quote:

Also, I've written a few helper functions for generating random numbers in particular ways.

If they are useful and independent of a particular containing class (which they must be for you to want them in more than one place) then you should add them to the RNG class.

bamccaig
Member #7,536
July 2006
avatar

I would probably avoid the global state myself. Of course you can get it done with global state, but is it the best approach? I would say no. I would probably add a property to every object that needed a RNG and pass it in through the constructor. I wouldn't likely use references though, because there's no way to know for sure that the referenced object still exists, and it's not clear from the caller's perspective that a reference is kept. Since you're already using Boost, you have a very simple solution: boost::shared_ptr<T>. You can share the RNG with as many objects as needed without worrying about wasted memory or violating best practices. :) Perhaps something like this:

#SelectExpand
1#include <boost/random/mersenne_twister.hpp> 2#include <boost/shared_ptr.hpp> 3#include <ctime> 4#include <iostream> 5 6typedef boost::mt19937 rng_t; 7typedef boost::shared_ptr<rng_t> rng_ptr_t; 8 9class Game 10{ 11protected: 12 rng_ptr_t rng_; 13public: 14 Game(const rng_ptr_t &); 15}; 16 17Game::Game(const rng_ptr_t & rng): 18 rng_(rng) 19{ 20 assert(rng.get()); 21} 22 23class World 24{ 25protected: 26 rng_ptr_t rng_; 27public: 28 World(const rng_ptr_t & rng); 29}; 30 31World::World(const rng_ptr_t & rng): 32 rng_(rng) 33{ 34 assert(rng.get()); 35} 36 37int main(int argc, char * argv[]) 38{ 39 rng_ptr_t rng(new rng_t(time(0))); 40 41 Game game(rng); 42 World world(rng); 43 44 return 0; 45}

james_lohr
Member #1,947
February 2002

Or you can make multiple constructors: one where you pass in an RNG object, and one where you don't (in which case it gets constructed internally as a new instance).

Though I suppose you're unlikely to reuse your World or Game classes, so I really don't think it matters. The only thing that is certain is that making it global is a bad choice. As soon as it's global you will be tempted to use it elsewhere in classes that could otherwise be made reusable.

Karadoc ~~
Member #2,749
September 2002
avatar

Ok. A lot of people have expressed disapproval of making it global. Having it global is the easiest way of doing it, but I agree that it's probably wise to stick to good OO design. I still don't really want to pass RNG pointers / references around though (mostly for aesthetic reasons).

So how about the half-way house: a singleton[1].

.h#SelectExpand
1class RngAccessor 2{ 3public: 4 RngAccessor(); 5 6 int operator()(int max); // random number, [0, max) 7 int nDice(int n, int sides); // roll a 'sides' sided die, n times. Sum the result. 8 uint32_t RandomIdNumber(); 9 10 // the rng itself. 11 typedef boost::mt19937 RNGType; 12 static RNGType rng; 13private: 14 static bool seeded; 15};

.cpp#SelectExpand
1bool RngAccessor::seeded = false; 2RngAccessor::RNGType RngAccessor::rng; 3 4RngAccessor::RngAccessor() 5{ 6 if (!seeded) 7 { 8 rng.seed(time(NULL)); 9 seeded = true; 10 } 11} 12 13// random number, [0, max) 14int RngAccessor::operator()(int max) 15{ 16 boost::uniform_smallint <> range(0, max-1); 17 boost::variate_generator< RNGType&, boost::uniform_smallint <> > 18 dice(rng, range); 19 20 return dice(); 21} 22 23// roll a 'sides' sided die, n times. Sum the result. 24int RngAccessor::nDice(int n, int sides) 25{ 26 boost::uniform_smallint <> range(1, sides); 27 boost::variate_generator< RNGType&, boost::uniform_smallint <> > 28 dice(rng, range); 29 30 int result = 0; 31 while (n-- > 0) 32 result += dice(); 33 34 return result; 35} 36 37// generate a random ID number 38uint32_t RngAccessor::RandomIdNumber() 39{ 40 boost::uniform_int<> range(1, id_number_max); // id = 0 is reserved 41 boost::variate_generator< RNGType&, boost::uniform_int<> > 42 dice(rng, range); 43 44 return dice(); 45}

With that the RNG is effectively global, but any class that wants to use it must explicitly have a RngAccessor member.

What do you think? Better than global? Worse than passing references?

References

  1. I'm not sure if this technically counts as a "singleton" or not.

-----------

orz
Member #565
August 2000

If you're multithreaded then you should generally have (at least) one RNG per thread. The simplest way to do that is to declare it as a TLS global. That means declaring it as a global variable but prefixing the declaration with "__declspec(thread)" or "__thread" depending upon which compiler you are using. The libc rand() uses a TLS state automatically on MSVC. If you use RNGs in multiple threads and don't have your RNGs on a per-thread basis then you need to be able to share them between threads, which means either locking or an inherently thread-safe RNG. The former is slow, and the later is generally a bad idea.

Aside from that, the more common reason to have multiple RNGs is if either some of your logic needs to be deterministic (for demo playback, debugging, networking, or other reasons) while using random numbers, in which case there should be separate RNGs for each deterministic domain.

A less common reason to have multiple RNGs is if you need various RNG properties from different bits of code that no single RNG can meet. Like, if you needed an RNG that can be both seeded and used very very quickly in one place, and one that is cryptographic quality in another place (there are fast crypto RNGs and fast seeding crypto RNGs, but none that are both), then you might use a mix of RNGs to satisfy your needs.

If you need multiple RNGs for multiple of the above reasons then things can get messy.

If you don't anticipate any need for multiple RNGs then your RNG might as well be a simple global, aside from the issue of making sure it gets seeded before any global constructors that might want to use it.

Arthur Kalliokoski
Second in Command
February 2005
avatar

It didn't occur to me earlier about the benefits of separate RNG's for demos and cut scenes earlier, but now that I consider it, it seems an excellent idea. Using a reference for private data is a miniscule chore compared to this.

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

Audric
Member #907
January 2001

Karadoc: IMO, worse than global. If you are using a single series of pseudo-random numbers, why do you need dozens of class members that lead to it ?

james_lohr
Member #1,947
February 2002

What do you think? Better than global? Worse than passing references?

It's much worse. Worse even than using a global. If two separate classes need to share the same instance of your RNG, then it makes perfect sense to instantiate the instance of RNG in the containing class and pass a reference into the constructors of the classes requiring it.

A singleton is totally the wrong pattern in this case since there are times when you will want separate instances of RNG. Also, think of someone looking at your code for the first time: in the case of the singleton, it adds unnecessary complexity and confusion. A new programmer may think "should I use the singleton or create my own instance? Is it safe to use the singleton here? Is it even really a singleton?! Why has he used a singleton, is there something dirty here I don't know about? Is it thread safe?"

On the other hand, if you simply use a reference in the constructors, it's immediately obvious what is going on. In fact there's absolutely nothing special about your RNG class that it should require a singleton - it's not even that uncommon to see two or more objects reference a common object: if you used a singleton in every case your code would be a total mess.

bamccaig
Member #7,536
July 2006
avatar

Singletons suck. Same thing as a global. You just tied a bow around its neck. :-/ Read: Singletons are not good OO design. They're bad design with icing on top. Besides, since the RNG is public static it is exactly a global anyway. :P No need for an accessor instance at all (which is really fun because until the accessor constructor has run it is seeded with a constant).

Aesthetically, passing parameters is the most clean way to do these things. :-/ It's also the most powerful/flexible.

orz
Member #565
August 2000

Technically I think a simple global is an implementation of the singleton pattern.

But, I agree, singletons as they are usually referred to - a class with a single instance and a static method to obtain a reference to that instance - does seem to be mostly pointless. Once in a while it is useful in managing initialization order but frequently it serves no purpose at all. Likewise his accessor thingy, which might be considered a singleton implementation, serves little purpose.

edit:
Actually, I want to back away from that position a bit - initialization order problems are actually not uncommon at all, and singletons are a reasonable solution to them. I have seen singletons used a bit on things that had no initialization order problems, but maybe that's a matter of better-safe-than-sorry.

OICW
Member #4,069
November 2003
avatar

A singleton is totally the wrong pattern in this case since there are times when you will want separate instances of RNG.

That's why I added: "if you plan to use only one instance." But given more information, yes, it's not a good idea.

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

bamccaig
Member #7,536
July 2006
avatar

OICW
Member #4,069
November 2003
avatar

Do you have arguments to ground that statement?

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

orz
Member #565
August 2000

bamccaig: Be more specific. What is your recommended fix for the problems that normally arise due to initialization ordering on C++ globals, which is normally handled with a singleton?

bamccaig
Member #7,536
July 2006
avatar

OICW said:

Do you have arguments to ground that statement?

Yes. Globals are bad, and not primarily because of the order of initialization. Singletons are globals. Basically, the Singleton pattern was devised to solve a non-problem: how do you enforce that only one instance exists? You only create one instance! Genius!

Basically, Singletons and all other forms of global state are used by lazy people that don't want to pass data around. It's bad because it's avoiding the inevitable design that must go into software if you want it to be robust. Basically, global state is used by people that don't want to think.

There are specific reasons that globals (and Singletons) are bad.

  • Makes testing more difficult. You can't properly control the inputs to a function if they're global.

  • Makes the code more obscure:

Foo::getInstance().foo();
Bar::getInstance().bar();
Baz::getInstance().baz();

Does the order of those calls matter? How can you tell? There are no visible dependencies between them (shared or otherwise). A world where the order of those calls doesn't matter is a lot easier to program in then a world where the order does matter. Imagine this instead:

Foo foo;

foo.foo();

Bar bar;

bar.bar(foo);

Baz baz;

baz.baz(foo, bar);

Ah, now we can clearly see that the order of the calls does matter.

orz said:

bamccaig: Be more specific. What is your recommended fix for the problems that normally arise due to initialization ordering on C++ globals, which is normally handled with a singleton?

DON'T USE GLOBALS.

Edgar Reynaldo
Member #8,592
May 2007
avatar

Get over your obsession with hating globals bamccaig. :P

Imagine Allegro 4 without globals :

screen -> GetScreen()
mouse_pos >> 16 -> GetMousePos() >> 16
palette -> GetPalette()
mouse_b & 1 -> GetMouseB() & 1
key[KEY_ESC] -> GetKeyArray()[KEY_ESC]

Instead of nice, easy to work with globals, you now have a bunch of wasteful accessor functions returning copies of data for no good reason.

Also, singletons have two good things going for them :
1) You can't access a singleton before it has been constructed properly. This makes global constructors work in the correct order.
2) Some classes shouldn't be instantiated more than once, due to heavy initialization or use of system devices.

That said, unless you need to enforce a single instance of a class, or ensure your class is constructed before it is used, then there's not much reason to use a singleton.

Really, get over your hate for globals. Sometimes they're appropriate.

 1   2 


Go to: