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 | |
|
|
28 | typedef 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 |
31 | struct tausworthe_random_generator |
33 | struct 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 |
44 | struct xorshift_random_generator |
46 | struct 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 | |
|
|
65 | template<uint32_t A, uint32_t B> |
|
|
66 | struct 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 | |
|
|
82 | typedef lc_rng<3039177861U, 0U> borosh_niederreiter_rng; |
|
|
83 | typedef lc_rng<2147001325U, 715136305U> bcpl_rng; |
|
|
84 | typedef lc_rng< 1664525U, 1U> lavaux_janssens_rng; |
|
|
85 | typedef lc_rng< 1664525U, 1013904223U> numerical_recipes_rng; |
|
|
86 | |
63 | template<typename T, int N, int k> |
87 | template<typename T, int N, int k> |
64 | struct gfsr_random_generator |
88 | struct 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. |
115 | typedef gfsr_random_generator<uint32_t, 250, 103> r250_random_generator; |
139 | typedef gfsr_rng<uint32_t, 250, 103> r250_rng; |
116 | typedef gfsr_random_generator<uint32_t, 521, 168> r521_random_generator; |
140 | typedef 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) |
119 | typedef gfsr_random_generator<uint32_t, 55, 24> freeciv_random_generator; |
144 | typedef 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 |
122 | struct r250521_random_generator |
147 | struct 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. |
133 | template<class generator> |
160 | template<class generator> |
134 | struct random_number_generator : generator |
161 | struct 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] |
… | |
… | |
156 | return is_constant (r_min <= r_max) && r_min <= r_max |
183 | return 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 | |
170 | protected: |
201 | protected: |
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 |
176 | typedef random_number_generator<freeciv_random_generator> rand_gen; |
207 | typedef random_number_generator<freeciv_rng> rand_gen; |
177 | |
208 | |
178 | // used when we often seed |
209 | // used when we often seed |
179 | typedef random_number_generator<tausworthe_random_generator> seedable_rand_gen; |
210 | typedef random_number_generator<tausworthe_rng> seedable_rand_gen; |
180 | |
211 | |
181 | extern rand_gen rndm, rmg_rndm; |
212 | extern rand_gen rndm, rmg_rndm; |
182 | |
213 | |
183 | #endif |
214 | #endif |
184 | |
215 | |