help me with weird random number thing!

Discussion in 'Game Development (Technical)' started by cliffski, Jun 27, 2010.

  1. cliffski

    cliffski
    Expand Collapse
    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    3,898
    Likes Received:
    0
    Ok, I'm no dork, I know to seed srand() with the system time on startup but.............

    There is ONE random number that I generate in my game that is always the same. It's always 41.
    In other words:

    rand()

    returns 41.

    Its probably the 300th call to rand() or somesuch.
    And yet if I make my game dump out all of its random numebrs to a log, they DO seem to be different and totally random...
    Is this a debugger thing? Shurely no co-incidence!
    I have only 1 call to srand() in the whole app. There is nothing magical about this specific call.
    What could I be doign wrong, like a dork?
     
  2. Bad Sector

    Bad Sector
    Expand Collapse
    Original Member

    Joined:
    May 28, 2005
    Messages:
    2,740
    Likes Received:
    0
    Does the srand() get a different value each time though? Have you checked this possibility? How do you use the rand() and how the srand()?
     
  3. cliffski

    cliffski
    Expand Collapse
    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    3,898
    Likes Received:
    0
    I do srand(timeGetTime()) and I check what timeGetTime() was. get this:

    first attempt:
    timeGeTime() 310713421
    first rand() 11654
    second rand() 41

    secondattempt:
    timeGeTime() 310766985
    first rand() 1353
    second rand() 41

    etc.. :(
    I may reboot... and do a total rebuild.
     
  4. zoombapup

    zoombapup
    Expand Collapse
    Moderator Original Member

    Joined:
    Nov 25, 2004
    Messages:
    2,890
    Likes Received:
    0
    Hmm, just 1 away from the answer to life the universe and everything. I'd say thats usually a good thing :)

    Try using a proper random number generator? rand() isnt.
     
  5. cliffski

    cliffski
    Expand Collapse
    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    3,898
    Likes Received:
    0
    rand() should not be predictable. if I call it twice, having seeded it with the system time, it should return different numbers.
    And even if it doesnt, it shouldnt magically pick a single call to rand() to return the same number.
     
  6. cliffski

    cliffski
    Expand Collapse
    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    3,898
    Likes Received:
    0
  7. Game Producer

    Game Producer
    Expand Collapse
    Moderator Original Member

    Joined:
    Jan 13, 2006
    Messages:
    1,418
    Likes Received:
    0
    I betcha you are doing seeding srand() with something between those first and second rand() calls.

    Have you done an a piece of software that does exactly that and only that - or are you taking this code from your software code. :)

    Is there other ways to seed the random thing besides srand()?
     
  8. Game Producer

    Game Producer
    Expand Collapse
    Moderator Original Member

    Joined:
    Jan 13, 2006
    Messages:
    1,418
    Likes Received:
    0
    And if it's not that, then perhaps it's the germany-england soccer result that keeps haunting you :D
     
  9. Game Producer

    Game Producer
    Expand Collapse
    Moderator Original Member

    Joined:
    Jan 13, 2006
    Messages:
    1,418
    Likes Received:
    0
    Ah, we wrote simultaneously. Was just about to mention "other thread"...

    Oh well, nice that it got sorted out.
     
  10. oNyx

    oNyx
    Expand Collapse
    Original Member

    Joined:
    Jul 26, 2004
    Messages:
    1,212
    Likes Received:
    0
    I highly recommend to use a different PRNG. That way you can get deterministic results with different compilers, different operating systems, and even entirely different languages. Additionally, it's entirely up to you how sophisticated the PRNG is.

    Nowadays I recommend XorShift. It's a surprisingly simple looking algorithm with excellent characteristics. It passes the Diehard tests (i.e. it got good statistical properties) and it's also very fast - at least in all languages where binary operators work directly with proper integers (C/C++, Java, AS3, etc.).

    JavaScript for example only got IEEE 754 floating point (aka double) and nothing else. If you use a binary operator, the value(s) get(s) converted to int first, then the operation is performed, and finally it's converted back again. This does, of course, affect performance a bit. I still do use XorShift over there though (I use it everywhere). I don't really need thousands of random numbers per second. I'm fine without that 3-4x speed boost.
     
  11. Vino

    Vino
    Expand Collapse
    New Member

    Joined:
    May 16, 2010
    Messages:
    345
    Likes Received:
    0
    Here's my handy and reliable mersenne twister c implementation for you:

    Code:
    #define MT_SIZE 624
    static size_t g_aiMT[MT_SIZE];
    static size_t g_iMTI = 0;
    
    // Mersenne Twister implementation from Wikipedia.
    void mtsrand(size_t iSeed)
    {
    	g_aiMT[0] = iSeed;
    	for (size_t i = 1; i < MT_SIZE; i++)
    	{
    		size_t inner1 = g_aiMT[i-1];
    		size_t inner2 = (g_aiMT[i-1]>>30);
    		size_t inner = inner1 ^ inner2;
    		g_aiMT[i] = (0x6c078965 * inner) + i;
    	}
    
    	g_iMTI = 0;
    }
    
    size_t mtrand()
    {
    	if (g_iMTI == 0)
    	{
    		for (size_t i = 0; i < MT_SIZE; i++)
    		{
    			size_t y = (0x80000000&(g_aiMT[i])) + (0x7fffffff&(g_aiMT[(i+1) % MT_SIZE]));
    			g_aiMT[i] = g_aiMT[(i + 397)%MT_SIZE] ^ (y>>1);
    			if ((y%2) == 1)
    				g_aiMT[i] = g_aiMT[i] ^ 0x9908b0df;
    		}
    	}
    
    	size_t y = g_aiMT[g_iMTI];
    	y = y ^ (y >> 11);
    	y = y ^ ((y << 7) & (0x9d2c5680));
    	y = y ^ ((y << 15) & (0xefc60000));
    	y = y ^ (y >> 18);
    
    	g_iMTI = (g_iMTI + 1) % MT_SIZE;
    
    	return y;
    }
    
    I don't know if you code in C or C++ but if you do, you're welcome. It's deterministic on every platform I've used it on so far. I keep it handy in a common library that I import into all my projects.
     
  12. oNyx

    oNyx
    Expand Collapse
    Original Member

    Joined:
    Jul 26, 2004
    Messages:
    1,212
    Likes Received:
    0
    Ye, the Mersenne Twister is also a good choice. Even if it fell a bit out of favor these days, since it's rather complicated to implement. Other PRNGs like Multiply-with-carry or WELL512 are simpler, are equally good or better at generating random numbers, and they are also faster.

    XorShift on the other hand is somewhat low tech in comparison, having a period of "only" 2^128-1. Well, for games it's good enough in my opinion. rand() typically only has a period of 2^31 or 2^32 for example and it generally doesn't pass Diehard or similar tests.
     
  13. Pogacha

    Pogacha
    Expand Collapse
    Original Member

    Joined:
    Jan 21, 2005
    Messages:
    605
    Likes Received:
    0
    Depending on what I was using MT or rand(), but that XorShift looks great :)
    far simplier and faster than MT, less memory footprint too.
    Thanks for sharing.
     
  14. Mattias Gustavsson

    Mattias Gustavsson
    Expand Collapse
    Original Member

    Joined:
    Aug 10, 2005
    Messages:
    669
    Likes Received:
    0
    Here's the implementation of WELL512 that I'm using in my Pixie game engine
    Header file:
    Code:
    /**
     * \class	Random
     * 
     * \ingroup	core
     * \brief	
     * \author	Mattias Gustavsson	
     * 
     * Random number generation, using the WELL algorithm by F. Panneton, P. L'Ecuyer and M. Matsumoto.
     * The creators of the algorithm describes it like this:
     *
     *      Fast uniform random number generators with extremely long periods have been defined and implemented based on 
     *      linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the 
     *      period length, the statistical quality of these generators is usually assessed via their equidistribution 
     *      properties. The huge-period generators proposed so far are not quite optimal in that respect. In this paper, 
     *      we propose new generators, with better equidistribution and "bit-mixing" properties for equivalent period length 
     *      and speed. Approximately half of the coefficients of the characteristic polynomial of these generators are 
     *      nonzero. The state of our new generators evolves in a more chaotic way than for the Mersenne twister. We 
     *      illustrate how this can reduce the impact of persistent dependencies among successive output values, which can 
     *      be observed in certain parts of the period of gigantic generators such as the Mersenne twister.
     *
     * More information in the original paper: http://www.iro.umontreal.ca/~panneton/WELLRNG.html
     *
     * This code is originally based on WELL512 C/C++ code written by Chris Lomont (published in Game Programming Gems 7) 
     * and placed in the public domain. There's also an article about it on Lomont's site:
     *
     *      http://lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf
     */
    
    #ifndef __Random_H__
    #define __Random_H__
    
    class Random
        {
        public:
            Random();
    
            void Seed(unsigned int seed);
            void SetState(const unsigned int state[16], int index);
            void GetState(unsigned int state[16], int& index);
    
            /** 
             * Generates a random number on [0,0xffffffff] interval
             */
            unsigned int RandomInteger();
    
            /**
             * Generates a random number on [0,0.99999999999...] interval
             */
            float RandomFloat();
    
            /**
             * Generates a random number on [min,max] interval
             */
            int RandomRanged(int min, int max);
    
        private:
            unsigned int state_[16];
            unsigned int index_;
    
        };
    
    #endif /* __Random_H__ */
    
    Cpp file:
    Code:
    //*** Random.cpp ***
    
    
    #include "Random.h"
    
    //*** Constructor ***
    
    Random::Random():
        index_(0)
        {
        Seed(0x5ee39c34);
        }
    
    
    //*** Seed ***
    
    void Random::Seed(unsigned int s)
        {	
        state_[0]=s^0xf68a9fc1;
        for (int i=1; i<16; i++) 
            {
            state_[i] = (0x6c078965U * (state_[i-1] ^ (state_[i-1] >> 30)) + i); 
            }
        }
    
    
    //*** SetState ***
    
    void Random::SetState(const unsigned int state[16], int index)
        {
        for (int i=0; i<16; i++)
            {
            state_[i]=state[i];
            }
    
        index_=index&15;
        }
    
    
    //*** GetState ***
    
    void Random::GetState(unsigned int state[16], int& index)
        {
        for (int i=0; i<16; i++)
            {
            state[i]=state_[i];
            }
    
        index=index_;
        }
    
    
    //*** RandomInteger ***
    
    unsigned int Random::RandomInteger()
        {
        unsigned int a = state_[index_];
        unsigned int c = state_[(index_+13)&15];
        unsigned int b = a^c^(a<<16)^(c<<15);
        c = state_[(index_+9)&15];
        c ^= (c>>11);
        a = state_[index_] = b^c;
        unsigned int d = a^((a<<5)&0xda442d20U);
        index_ = (index_ + 15)&15;
        a = state_[index_];
        state_[index_] = a^b^d^(a<<2)^(b<<18)^(c<<28);
        return state_[index_];
        }
    
    
    //*** RandomRanged ***
    
    int Random::RandomRanged(int min, int max)
        {
        int range=(max-min)+1;
        if (range<=0)
            {
            return min;
            }
        int value=(int)(RandomFloat()*range);
        return min+value; 
        }
    
    
    //*** RandomFloat ***
    
    float Random::RandomFloat()
        {
        // Get a random integer, and divide by 2^32
        return (RandomInteger()/4294967296.0f);     
        }
    
    
     
    #14 Mattias Gustavsson, Jun 28, 2010
    Last edited: Jun 30, 2010
  15. oNyx

    oNyx
    Expand Collapse
    Original Member

    Joined:
    Jul 26, 2004
    Messages:
    1,212
    Likes Received:
    0
    Thanks for sharing, Matt.

    I haven't seen the Whitesmiths indent style since ages. Pretty nostalgic, really. It's the style I started with. I then switched to Allman (the braces' content is indented - it worked better in most editors) and finally to 1TBS (hugging braces - industry standard with Java, mandatory with JavaScript).


    By the way, that "[0,0xffffffff]-interval" comment... the hyphen shouldn't be there.
     
  16. Mattias Gustavsson

    Mattias Gustavsson
    Expand Collapse
    Original Member

    Joined:
    Aug 10, 2005
    Messages:
    669
    Likes Received:
    0
    Yeah, it's not the most common one - I used to use Allman for years, but switched over to Whitesmiths some 7 years ago, and have stuck with it for my personal projects ever since, while still using Allman at most of the places I've worked. I do think that once I got used to Whitesmiths, it is the one which suits me better - I just think it's easier to see the code structure :cool:

    Well spotted on the hyphen *removed*
     

Share This Page