ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/include/rng.h
(Generate patch)

Comparing deliantra/server/include/rng.h (file contents):
Revision 1.2 by root, Tue Jul 6 20:00:46 2010 UTC vs.
Revision 1.14 by root, Sat Nov 17 23:33:18 2018 UTC

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

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines