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.8 by root, Sat Apr 30 11:02:25 2011 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 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.
… …
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 27
28typedef uint32_t seed_t; // overkill
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;
85
63template<typename T, int N, int k> 86template<typename T, int N, int k>
64struct gfsr_random_generator 87struct gfsr_rng
65{ 88{
66 int i; 89 int i;
67 T x[N]; 90 T x[N];
68 91
69 // rng must have same bitwidth as T 92 // rng must have same bitwidth as T
… …
85 } 108 }
86 while (i); 109 while (i);
87 } 110 }
88 111
89 // actually should subclass to gfsr32... :) 112 // actually should subclass to gfsr32... :)
90 void seed (uint32_t seed) 113 void seed (seed_t seed)
91 { 114 {
92 xorshift_random_generator rng; 115 xorshift_rng rng;
93 116
94 rng.seed (seed); 117 rng.seed (seed);
95 this->seed_rng (rng); 118 this->seed_rng (rng);
96 } 119 }
97 120
… …
110 } 133 }
111}; 134};
112 135
113// these are about 2-3 times faster than tausworthe, non-inlined, 136// these are about 2-3 times faster than tausworthe, non-inlined,
114// and likely of higher quality. 137// and likely of higher quality.
115typedef gfsr_random_generator<uint32_t, 250, 103> r250_random_generator; 138typedef gfsr_rng<uint32_t, 250, 103> r250_rng;
116typedef gfsr_random_generator<uint32_t, 521, 168> r521_random_generator; 139typedef gfsr_rng<uint32_t, 521, 168> r521_rng;
117 140
118// freeciv uses this one, so it's good enough for us :) 141// freeciv uses this one, so it's good enough for us :)
142// (also known as mitchell moore generator
119typedef gfsr_random_generator<uint32_t, 55, 24> freeciv_random_generator; 143typedef gfsr_rng<uint32_t, 55, 24> freeciv_rng;
120 144
121// this one should be high quality, but is slightly slower than tausworthe 145// this one should be high quality, but is slightly slower than tausworthe
122struct r250521_random_generator 146struct r250521_rng
123{ 147{
124 r250_random_generator r250; 148 r250_rng r250;
125 r521_random_generator r521; 149 r521_rng r521;
126 150
127 void seed (uint32_t seed); 151 void seed (uint32_t seed);
128 uint32_t next (); 152 uint32_t next ();
129}; 153};
130 154
155/////////////////////////////////////////////////////////////////////////////
156
131// this is actually an adaptor that provides different types 157// this is actually an adaptor that provides different
132// of random numbers. 158// distributions of random numbers.
133template<class generator> 159template<class generator>
134struct random_number_generator : generator 160struct random_number_generator : generator
135{ 161{
136 random_number_generator () 162 random_number_generator ()
137 { 163 {
138 } 164 }
139 165
140 random_number_generator (uint32_t seed) 166 random_number_generator (seed_t seed)
141 { 167 {
142 this->seed (seed); 168 this->seed (seed);
143 } 169 }
144 170
145 // uniform distribution, [0 .. num - 1] 171 // uniform distribution, [0 .. num - 1]
… …
156 return is_constant (r_min <= r_max) && r_min <= r_max 182 return is_constant (r_min <= r_max) && r_min <= r_max
157 ? r_min + operator ()(r_max - r_min + 1) 183 ? r_min + operator ()(r_max - r_min + 1)
158 : get_range (r_min, r_max); 184 : get_range (r_min, r_max);
159 } 185 }
160 186
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 (); 187 uint32_t get_u32 ();
168 uint64_t get_u64 (); 188 uint64_t get_u64 ();
189 float get_float ();
190 double get_double ();
191
192 // return a number within the half-open interval [0..1[
193 double operator () ()
194 {
195 return get_double ();
196 }
197
198 uint32_t poisson (double mean);
169 199
170protected: 200protected:
171 uint32_t get_range (uint32_t r_max); 201 uint32_t get_range (uint32_t r_max);
172 int get_range (int r_min, int r_max); 202 int get_range (int r_min, int r_max);
173}; 203};
174 204
175// the default rng used in the game 205// the default rng used in the game
176typedef random_number_generator<freeciv_random_generator> rand_gen; 206typedef random_number_generator<freeciv_rng> rand_gen;
177 207
178// used when we often seed 208// used when we often seed
179typedef random_number_generator<tausworthe_random_generator> seedable_rand_gen; 209typedef random_number_generator<tausworthe_rng> seedable_rand_gen;
180 210
181extern rand_gen rndm, rmg_rndm; 211extern rand_gen rndm, rmg_rndm;
182 212
183#endif 213#endif
184 214

Diff Legend

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