server/include/rng.h

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * 
 * Deliantra is free software: you can redistribute it and/or modify it under
 * the terms of the Affero GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the Affero GNU General Public License
 * and the GNU General Public License along with this program. If not, see
 * <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

#ifndef RNG_H__
#define RNG_H__

#include <compiler.h>

// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
struct tausworthe_rng
{
  uint32_t state [4];

  void seed (uint32_t seed);
  uint32_t next ();
};

// Xorshift RNGs, George Marsaglia
// http://www.jstatsoft.org/v08/i14/paper
// this one is about 40% faster than the tausworthe one above (i.e. not much),
// despite the inlining, and has the issue of only creating 2**32-1 numbers.
// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
struct xorshift_rng
{
  uint32_t x, y;

  void seed (uint32_t seed)
  {
    x = seed ? seed : 0xdeadbeef;
    y = x * 69069U;
  }

  uint32_t next ()
  {
    uint32_t t = x ^ (x << 10);
    x = y;
    y = y ^ (y >> 13) ^ t ^ (t >> 10);
    return y;
  }
};

template<uint32_t A, uint32_t B>
struct lc_rng
{
  uint32_t x;

  void seed (uint32_t seed)
  {
    x = seed;
  }

  uint32_t next ()
  {
    x = x * A + B;
    return x;
  }
};

typedef lc_rng<3039177861U, 0> borosh_niederreiter_rng;
typedef lc_rng<2147001325U, 715136305U> bcpl_rng;

template<typename T, int N, int k>
struct gfsr_rng
{
  int i;
  T x[N];

  // rng must have same bitwidth as T
  template<typename RNG>
  void seed_rng (RNG rng)
  {
    i = N;

    do
      x [--i] = rng.next ();
    while (i > sizeof (T) * 8);

    T m = 1;

    do
      {
        x [--i] = (rng.next () | m) & ~(m - 1);
        m <<= 1;
      }
    while (i);
  }

  // actually should subclass to gfsr32... :)
  void seed (uint32_t seed)
  {
    xorshift_rng rng;

    rng.seed (seed);
    this->seed_rng (rng);
  }

  T next ()
  {
    int j = i + (k - N);

    if (j < 0)
      j += N;

    T v = (x [i] ^= x [j]);

    i = (i ? i : N) - 1;

    return v;
  }
};

// these are about 2-3 times faster than tausworthe, non-inlined,
// and likely of higher quality.
typedef gfsr_rng<uint32_t, 250, 103> r250_rng;
typedef gfsr_rng<uint32_t, 521, 168> r521_rng;

// freeciv uses this one, so it's good enough for us :)
typedef gfsr_rng<uint32_t,  55,  24> freeciv_rng;

// this one should be high quality, but is slightly slower than tausworthe
struct r250521_rng
{
  r250_rng r250;
  r521_rng r521;

  void seed (uint32_t seed);
  uint32_t next ();
};

// this is actually an adaptor that provides different types
// of random numbers.
template<class generator>
struct random_number_generator : generator
{
  random_number_generator ()
  {
  }

  random_number_generator (uint32_t seed)
  {
    this->seed (seed);
  }

  // uniform distribution, [0 .. num - 1]
  uint32_t operator ()(uint32_t num)
  {
    return !is_constant (num) ? get_range (num)                        // non-constant
         : num & (num - 1)    ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two
         :                      this->next () & (num - 1);             // constant, power-of-two
  }

  // return a number within the closed interval [min .. max], max can be >, < or == min.
  int operator () (int r_min, int r_max)
  {
    return is_constant (r_min <= r_max) && r_min <= r_max
              ? r_min + operator ()(r_max - r_min + 1)
              : get_range (r_min, r_max);
  }

  uint32_t get_u32 ();
  uint64_t get_u64 ();
  float    get_float ();
  double   get_double ();

  // return a number within the half-open interval [0..1[
  double operator () ()
  {
    return get_double ();
  }

  uint32_t poisson (double mean);

protected:
  uint32_t get_range (uint32_t r_max);
  int get_range (int r_min, int r_max);
};

// the default rng used in the game
typedef random_number_generator<freeciv_rng> rand_gen;

// used when we often seed
typedef random_number_generator<tausworthe_rng> seedable_rand_gen;

extern rand_gen rndm, rmg_rndm;

#endif

Revision:	1.4
Committed:	Sun Sep 5 04:18:05 2010 UTC (13 years, 8 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.3:	+1 -1 lines
Log Message:	fix random map duplication
#	Content
1	/*
2	* This file is part of Deliantra, the Roguelike Realtime MMORPG.
3	*
4	* Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5	*
6	* Deliantra is free software: you can redistribute it and/or modify it under
7	* the terms of the Affero GNU General Public License as published by the
8	* Free Software Foundation, either version 3 of the License, or (at your
9	* option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the Affero GNU General Public License
17	* and the GNU General Public License along with this program. If not, see
18	* <http://www.gnu.org/licenses/>.
19	*
20	* The authors can be reached via e-mail to <support@deliantra.net>
21	*/
22
23	#ifndef RNG_H__
24	#define RNG_H__
25
26	#include <compiler.h>
27
28	// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
29	// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
30	// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
31	struct tausworthe_rng
32	{
33	uint32_t state [4];
34
35	void seed (uint32_t seed);
36	uint32_t next ();
37	};
38
39	// Xorshift RNGs, George Marsaglia
40	// http://www.jstatsoft.org/v08/i14/paper
41	// this one is about 40% faster than the tausworthe one above (i.e. not much),
42	// despite the inlining, and has the issue of only creating 2**32-1 numbers.
43	// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
44	struct xorshift_rng
45	{
46	uint32_t x, y;
47
48	void seed (uint32_t seed)
49	{
50	x = seed ? seed : 0xdeadbeef;
51	y = x * 69069U;
52	}
53
54	uint32_t next ()
55	{
56	uint32_t t = x ^ (x << 10);
57	x = y;
58	y = y ^ (y >> 13) ^ t ^ (t >> 10);
59	return y;
60	}
61	};
62
63	template<uint32_t A, uint32_t B>
64	struct lc_rng
65	{
66	uint32_t x;
67
68	void seed (uint32_t seed)
69	{
70	x = seed;
71	}
72
73	uint32_t next ()
74	{
75	x = x * A + B;
76	return x;
77	}
78	};
79
80	typedef lc_rng<3039177861U, 0> borosh_niederreiter_rng;
81	typedef lc_rng<2147001325U, 715136305U> bcpl_rng;
82
83	template<typename T, int N, int k>
84	struct gfsr_rng
85	{
86	int i;
87	T x[N];
88
89	// rng must have same bitwidth as T
90	template<typename RNG>
91	void seed_rng (RNG rng)
92	{
93	i = N;
94
95	do
96	x [--i] = rng.next ();
97	while (i > sizeof (T) * 8);
98
99	T m = 1;
100
101	do
102	{
103	x [--i] = (rng.next () \| m) & ~(m - 1);
104	m <<= 1;
105	}
106	while (i);
107	}
108
109	// actually should subclass to gfsr32... :)
110	void seed (uint32_t seed)
111	{
112	xorshift_rng rng;
113
114	rng.seed (seed);
115	this->seed_rng (rng);
116	}
117
118	T next ()
119	{
120	int j = i + (k - N);
121
122	if (j < 0)
123	j += N;
124
125	T v = (x [i] ^= x [j]);
126
127	i = (i ? i : N) - 1;
128
129	return v;
130	}
131	};
132
133	// these are about 2-3 times faster than tausworthe, non-inlined,
134	// and likely of higher quality.
135	typedef gfsr_rng<uint32_t, 250, 103> r250_rng;
136	typedef gfsr_rng<uint32_t, 521, 168> r521_rng;
137
138	// freeciv uses this one, so it's good enough for us :)
139	typedef gfsr_rng<uint32_t, 55, 24> freeciv_rng;
140
141	// this one should be high quality, but is slightly slower than tausworthe
142	struct r250521_rng
143	{
144	r250_rng r250;
145	r521_rng r521;
146
147	void seed (uint32_t seed);
148	uint32_t next ();
149	};
150
151	// this is actually an adaptor that provides different types
152	// of random numbers.
153	template<class generator>
154	struct random_number_generator : generator
155	{
156	random_number_generator ()
157	{
158	}
159
160	random_number_generator (uint32_t seed)
161	{
162	this->seed (seed);
163	}
164
165	// uniform distribution, [0 .. num - 1]
166	uint32_t operator ()(uint32_t num)
167	{
168	return !is_constant (num) ? get_range (num) // non-constant
169	: num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two
170	: this->next () & (num - 1); // constant, power-of-two
171	}
172
173	// return a number within the closed interval [min .. max], max can be >, < or == min.
174	int operator () (int r_min, int r_max)
175	{
176	return is_constant (r_min <= r_max) && r_min <= r_max
177	? r_min + operator ()(r_max - r_min + 1)
178	: get_range (r_min, r_max);
179	}
180
181	uint32_t get_u32 ();
182	uint64_t get_u64 ();
183	float get_float ();
184	double get_double ();
185
186	// return a number within the half-open interval [0..1[
187	double operator () ()
188	{
189	return get_double ();
190	}
191
192	uint32_t poisson (double mean);
193
194	protected:
195	uint32_t get_range (uint32_t r_max);
196	int get_range (int r_min, int r_max);
197	};
198
199	// the default rng used in the game
200	typedef random_number_generator<freeciv_rng> rand_gen;
201
202	// used when we often seed
203	typedef random_number_generator<tausworthe_rng> seedable_rand_gen;
204
205	extern rand_gen rndm, rmg_rndm;
206
207	#endif
208