## CL_Random Class

This following message was posted to the old ClanLib sourceforge developer mailing list, but it may have been forgotten about (it was not replied to).

It looks good, but I do not have enough knowledge on the subject to make a good judgement:

by Ben Chambers-3 Dec 20, 2006; 10:16pm

This patch implements a PRNG for ClanLib.

Multiple independent and unique RN streams may be created by instancing
the class. Personally, I use this feature for procedural content
generation, where you want the random placement to remain static across
multiple executions despite other uses of the PRNG.

I feel that this is an essential component for a game engine, which
unfortunately few people pay attention to, but which would benefit
ClanLib and its users immensely.

Class use is simple:

CL_Random r( SEED );

will instantiate the class, using a 32bit integer seed (it is possible
to implement this with 64bit integers, but I didn't bother).

unsigned int x=r.rand();

will assign a random value to x in the range of 0x0 .. 0xffffffff (any
32bit unsigned integer value). In addition to this, however, it has
several other functions which are useful for random generation:

even() returns either true or false, with a good distribution between
the two.
normalized() returns a float in the range of 0..1 inclusive, with an
even distribution.
ranged(min, max) returns a float in the range of min..max with an even
distribution.

distributed(mean, deviation) is special :) It returns potentially any
float value. Approximately 50% of all the values return lie within 1
deviation from the mean (note: This is NOT a Standard Deviation, and the
resulting curve is NOT a normal bell curve!). Approximately 75% of all
values lie within 2 deviations from the mean. If you want to know what
percentage P of all values will lie within X deviations from the mean,
it is:

P = 1-1/(2^x)

I don't know a better way to explain this; if someone comes up with one,
I'd appreciate hearing how they put it!

And that's just about it :) The code is not yet thread-safe; if you
will be accessing the same instance from multiple threads, it needs to
be wrapped in a mutex. However, independent instances may be used in

...Chambers

Index: Sources/API/core.h
================================================== =================
--- Sources/API/core.h (revision 110)
+++ Sources/API/core.h (working copy)
@@ -119,6 +119,7 @@
#include "Core/Math/number_pool.h"
#include "Core/Math/delauney_triangulator.h"
#include "Core/Math/outline_triangulator.h"
+#include "Core/Math/random.h"

#include "Core/XML/xml_token.h"
#include "Core/XML/xml_tokenizer.h"
Index: Sources/API/Core/Math/random.h
================================================== =================
--- Sources/API/Core/Math/random.h (revision 0)
+++ Sources/API/Core/Math/random.h (revision 0)
@@ -0,0 +1,80 @@
+/*
+** ClanLib SDK
+** Copyright (c) 1997-2005 The ClanLib Team
+**
+** This software is provided 'as-is', without any express or implied
+** warranty. In no event will the authors be held liable for any damages
+** arising from the use of this software.
+**
+** Permission is granted to anyone to use this software for any purpose,
+** including commercial applications, and to alter it and redistribute it
+** freely, subject to the following restrictions:
+**
+** 1. The origin of this software must not be misrepresented; you must not
+** claim that you wrote the original software. If you use this software
+** in a product, an acknowledgment in the product documentation would be
+** appreciated but is not required.
+** 2. Altered source versions must be plainly marked as such, and must not be
+** misrepresented as being the original software.
+** 3. This notice may not be removed or altered from any source distribution.
+**
+** Note: Some of the libraries ClanLib may link to may have additional
+** requirements or restrictions.
+**
+** File Author(s):
+**
+** Ben Chambers
+*/
+
+//! clanCore="Math"
+
+
+#if _MSC_VER > 1000
+#pragma once
+#endif
+
+//: Random number stream generator
+//- !group=Core/Math!
+class CL_Random
+{
+//! Construction:
+public:
+ //: Creates a unique random number stream.
+ //param SEED: Initial seed for the random number stream.
+ CL_Random( const unsigned int SEED=0 );
+
+//! Operations:
+public:
+ //: Returns an unsigned integer in the range of 0x0 .. 0xffffffff
+ unsigned int rand();
+
+ //: Returns a boolean value, either true or false.
+ bool even();
+
+ //: Returns a floating point value in the range of 0.0 .. 1.0, inclusive.
+ float normalized();
+
+ //: Returns a floating point value in the specified range.
+ //param min: The lower bound of the range
+ //param max: The upper bound of the range
+ float ranged(const float min, const float max);
+
+ //: Returns a floating point value randomly distributed.
+ //param mean: The central data point about which your results will be distributed.
+ //param deviation: 50% of all data will lie within this distance of the mean. 50% of all those outside, will lie within 1 additional deviation, etc.
+ float distributed(const float mean, const float deviation);
+
+//! Implementation:
+private:
+ void randomize();
+ unsigned int state[624];
+
+ unsigned int index;
+};
+
+#endif
Index: Sources/API/Makefile.am
================================================== =================
--- Sources/API/Makefile.am (revision 110)
+++ Sources/API/Makefile.am (working copy)
@@ -194,7 +194,8 @@
Core/Math/triangle_math.h \
Core/Math/pointset_math.h \
Core/Math/rect.h \
+ Core/Math/random.h \
Core/Math/size.h \
Core/Math/vector2.h \
Core/Math/point.h \
Index: Sources/Core/Math/random.cpp
================================================== =================
--- Sources/Core/Math/random.cpp (revision 0)
+++ Sources/Core/Math/random.cpp (revision 0)
@@ -0,0 +1,147 @@
+/*
+** ClanLib SDK
+** Copyright (c) 1997-2005 The ClanLib Team
+**
+** This software is provided 'as-is', without any express or implied
+** warranty. In no event will the authors be held liable for any damages
+** arising from the use of this software.
+**
+** Permission is granted to anyone to use this software for any purpose,
+** including commercial applications, and to alter it and redistribute it
+** freely, subject to the following restrictions:
+**
+** 1. The origin of this software must not be misrepresented; you must not
+** claim that you wrote the original software. If you use this software
+** in a product, an acknowledgment in the product documentation would be
+** appreciated but is not required.
+** 2. Altered source versions must be plainly marked as such, and must not be
+** misrepresented as being the original software.
+** 3. This notice may not be removed or altered from any source distribution.
+**
+** Note: Some of the libraries ClanLib may link to may have additional
+** requirements or restrictions.
+**
+** File Author(s):
+**
+** Ben Chambers
+*/
+
+// Note: This file implements the Mersenne Twist algorithm to generate a pseudorandom number stream.
+
+#include "Core/precomp.h"
+#include "API/Core/Math/random.h"
+
+/////////////////////////////////////////////////////////////////////////////
+// CL_Random constants needed:
+const double PI = 3.141592653589793238462643383279502884197169399375 10;
+const double sqrt2pi = sqrt(2*PI);
+const float inverse_log_2 = 1.0f/float(log(2.0));
+
+/////////////////////////////////////////////////////////////////////////////
+// CL_Random construction:
+
+CL_Random::CL_Random( const unsigned int SEED )
+{
+ state[0] = SEED;
+
+ for (int i=1; i<624; i++)
+ {
+ // Multiply the previous value, add 1 in case of 0, and use the lower
+ // 32 bits.
+ state[i] = (0x10dcd * state[i-1] +1)&0xffffffff;
+ }
+ randomize();
+ index=0;
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// CL_Random operations:
+
+unsigned int CL_Random::rand()
+{
+ unsigned int q=state[index];
+ index++;
+ if (index > 623)
+ {
+ index=0;
+ randomize();
+ }
+ return q;
+}
+
+bool CL_Random::even()
+{
+ unsigned int q=rand();
+ if ((rand()&0x1) == 1)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+}
+
+float CL_Random::normalized()
+{
+ return float(rand())/float(0xffffffff);
+}
+
+float CL_Random::ranged(const float min, const float max)
+{
+ float range = max-min;
+ return min+range*normalized();
+}
+
+float CL_Random::distributed(const float mean, const float deviation)
+{
+ // The function is simple... for X deviations, and a probability P that the
+ // result will lie X deviations from the mean, P=1-(1/2^x)
+ // Solving this for X, we have X=log(1/(1-P))/log(2)
+ // Of course, since P lies between 0..1, we can just use X=log(1/P)/log(2)
+
+ float x=log(1/normalized())*inverse_log_2;
+
+ if (even())
+ {
+ return mean + x*deviation;
+ }
+ return mean - x*deviation;
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// CL_Random implementation:
+
+void CL_Random::randomize()
+{
+ for (int i=0; i<623; i++)
+ {
+ // The highest bit of state[i] + the lower 31 bits of state[i+1]
+ unsigned int q = state[i]&0x80000000 + state[i+1]&0x7fffffff;
+
+ // The state is the state of i + the offset (397), bitwise
+ // xor'd with (y right shifted by 1 bit)
+ unsigned int w = state[(i+397)%624]^(q>>1);
+ if ((q&0x1) == 0)
+ {
+ // If q is even
+ state[i] = w;
+ }
+ else
+ {
+ // q is odd
+ state[i] = w^0x9908b0df;
+ }
+ }
+ unsigned int q = state[623]&0x80000000 + state[0]&0x7fffffff;
+ unsigned int w = state[396]^(q >> 1);
+ if ((q&0x1) == 0)
+ {
+ state[623]=w;
+ }
+ else
+ {
+ state[623]=w^0x9908b0df;
+ }
+}