001package squidpony.squidmath; 002 003import squidpony.annotation.GwtIncompatible; 004 005import java.util.*; 006 007/** 008 * An alteration to a RandomnessSource that attempts to produce values that are perceived as fair to an imperfect user. 009 * <p> 010 * This takes a RandomnessSource, defaulting to a LightRNG, and uses it to generate random values, but tracks the total 011 * and compares it to the potential total of a generator of only numbers with a desired value (default 0.54, 012 * so it compares against a sequence of all 0.54). If the current generated total is too high or low compared to the 013 * desired total, the currently used seed is possibly changed, the generated number is moved in the direction of the 014 * desired fairness, and it returns that instead of the number that would have pushed the current generated total 015 * beyond the desired threshold. The new number, if one is changed, will always be closer to the desired fairness. 016 * This is absolutely insecure for cryptographic purposes, but should seem more "fair" to a player than a 017 * random number generator that seeks to be truly random. 018 * You can create multiple DharmaRNG objects with different fairness values and seeds, and use favorable generators 019 * (with fairness greater than 0.54) for characters that need an easier time, or unfavorable generators if you want 020 * the characters that use that RNG to be impeded somewhat. 021 * The name comes from the Wheel of Dharma. 022 * This class currently will have a slight bias toward lower numbers with many RNGs unless fairness is tweaked; 0.54 023 * can be used as a stand-in because 0.5 leans too low. 024 * 025 * <p> 026 * You can get values from this generator with: {@link #nextDouble()}, {@link #nextInt()}, 027 * {@link #nextLong()}, and the bounded variants on each of those. 028 * <p> 029 * You can alter the tracking information or requested fairness with {@link #resetFortune()}, 030 * {@link #setFairness(double)}, and {@link #getFairness()}. 031 * 032 * Created by Tommy Ettinger on 5/2/2015. 033 */ 034public class DharmaRNG extends RNG { 035 036 /** Used to tweak the generator toward high or low values. */ 037 private double fairness = 0.54; 038 039 /** Running total for what this has actually produced. */ 040 private double produced = 0.0; 041 042 /** Running total for what this would produce if it always produced a value equal to fairness. */ 043 private double baseline = 0.0; 044 045 private static final long serialVersionUID = -8919455766853811999L; 046 047 /** 048 * Constructs a DharmaRNG with a pseudo-random seed from Math.random(). 049 */ 050 public DharmaRNG() 051 { 052 this((long)(Math.random() * ((1L << 50) - 1))); 053 } 054 /** 055 * Construct a new DharmaRNG with the given seed. 056 * 057 * @param seed used to seed the default RandomnessSource. 058 */ 059 public DharmaRNG(final long seed) { 060 super(seed); 061 } 062 063 /** 064 * Construct a new DharmaRNG with the given seed. 065 * 066 * @param seed used to seed the default RandomnessSource. 067 * @param fairness the desired fairness metric, which must be between 0.0 and 1.0 068 */ 069 public DharmaRNG(final long seed, final double fairness) { 070 super(seed); 071 if(fairness < 0.0 || fairness >= 1.0) 072 this.fairness = 0.54; 073 else 074 this.fairness = fairness; 075 } 076 077 078 /** 079 * String-seeded constructor; uses a platform-independent hash of the String (it does not use String.hashCode) as a 080 * seed for LightRNG, which is of high quality, but low period (which rarely matters for games), and has good speed, 081 * tiny state size, and excellent 64-bit number generation. 082 * 083 * @param seedString a String as a seed 084 */ 085 public DharmaRNG(String seedString) { 086 super(seedString); 087 } 088 089 090 /** 091 * String-seeded constructor; uses a platform-independent hash of the String (it does not use String.hashCode) as a 092 * seed for LightRNG, which is of high quality, but low period (which rarely matters for games), and has good speed, 093 * tiny state size, and excellent 64-bit number generation. 094 * 095 * @param seedString a String as a seed 096 */ 097 public DharmaRNG(String seedString, double fairness) { 098 super(seedString); 099 if(fairness < 0.0 || fairness >= 1.0) 100 this.fairness = 0.54; 101 else 102 this.fairness = fairness; 103 104 } 105 /** 106 * Construct a new DharmaRNG with the given seed. 107 * 108 * @param rs the implementation used to generate random bits. 109 */ 110 public DharmaRNG(final RandomnessSource rs) { 111 super(rs); 112 } 113 /** 114 * Construct a new DharmaRNG with the given seed. 115 * 116 * @param rs the implementation used to generate random bits. 117 * @param fairness the desired fairness metric, which must be between 0.0 and 1.0 118 */ 119 public DharmaRNG(final RandomnessSource rs, final double fairness) { 120 super(rs); 121 if(fairness < 0.0 || fairness >= 1.0) 122 this.fairness = 0.54; 123 else 124 this.fairness = fairness; 125 } 126 127 /** 128 * Generate a random double, altering the result if recently generated results have been leaning 129 * away from this class' fairness value. 130 * @return a double between 0.0 (inclusive) and 1.0 (exclusive) 131 */ 132 @Override 133 public double nextDouble() { 134 double gen = random.nextLong() * DOUBLE_UNIT; 135 /*if(Math.abs((produced + gen) - (baseline + fairness)) > 1.5) { 136 //do some reseeding here if possible 137 }*/ 138 if(Math.abs((produced + gen) - (baseline + fairness)) > 0.5) 139 { 140 gen = (gen + fairness) / 2.0; 141 produced *= 0.5; 142 baseline *= 0.5; 143 produced += gen; 144 baseline += fairness; 145 return gen; 146 } 147 else 148 { 149 produced += gen; 150 baseline += fairness; 151 return gen; 152 } 153 } 154 155 /** 156 * This returns a random double between 0.0 (inclusive) and max (exclusive). 157 * 158 * @return a value between 0 (inclusive) and max (exclusive) 159 */ 160 @Override 161 public double nextDouble(double max) { 162 return super.nextDouble(max); 163 } 164 165 /** 166 * Returns a value from a even distribution from min (inclusive) to max 167 * (exclusive). 168 * 169 * @param min the minimum bound on the return value (inclusive) 170 * @param max the maximum bound on the return value (exclusive) 171 * @return the found value 172 */ 173 @Override 174 public double between(double min, double max) { 175 return super.between(min, max); 176 } 177 178 /** 179 * Returns a value between min (inclusive) and max (exclusive). 180 * 181 * The inclusive and exclusive behavior is to match the behavior of the 182 * similar method that deals with floating point values. 183 * 184 * @param min the minimum bound on the return value (inclusive) 185 * @param max the maximum bound on the return value (exclusive) 186 * @return the found value 187 */ 188 @Override 189 public int between(int min, int max) 190 { 191 return super.between(min, max); 192 } 193 194 /** 195 * Returns the average of a number of randomly selected numbers from the 196 * provided range, with min being inclusive and max being exclusive. It will 197 * sample the number of times passed in as the third parameter. 198 * 199 * The inclusive and exclusive behavior is to match the behavior of the 200 * similar method that deals with floating point values. 201 * 202 * This can be used to weight RNG calls to the average between min and max. 203 * 204 * @param min the minimum bound on the return value (inclusive) 205 * @param max the maximum bound on the return value (exclusive) 206 * @param samples the number of samples to take 207 * @return the found value 208 */ 209 @Override 210 public int betweenWeighted(int min, int max, int samples) { 211 return super.betweenWeighted(min, max, samples); 212 } 213 214 /** 215 * Returns a random element from the provided array and maintains object 216 * type. 217 * 218 * @param <T> the type of the returned object 219 * @param array the array to get an element from 220 * @return the randomly selected element 221 */ 222 @Override 223 public <T> T getRandomElement(T[] array) { 224 return super.getRandomElement(array); 225 } 226 227 /** 228 * Returns a random element from the provided list. If the list is empty 229 * then null is returned. 230 * 231 * @param <T> the type of the returned object 232 * @param list the list to get an element from 233 * @return the randomly selected element 234 */ 235 @Override 236 public <T> T getRandomElement(List<T> list) { 237 return super.getRandomElement(list); 238 } 239 240 /** 241 * Returns a random element from the provided ShortSet. If the set is empty 242 * then an exception is thrown. 243 * 244 * <p> 245 * Requires iterating through a random amount of the elements in set, so performance depends on the size of set but 246 * is likely to be decent. This is mostly meant for internal use, the same as ShortSet. 247 * </p> 248 * @param set the ShortSet to get an element from 249 * @return the randomly selected element 250 */ 251 public short getRandomElement(ShortSet set) { 252 return super.getRandomElement(set); 253 } 254 255 /** 256 * Returns a random element from the provided Collection, which should have predictable iteration order if you want 257 * predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection 258 * (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted 259 * Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement 260 * Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can 261 * pass the keys or values. If coll is empty, returns null. 262 * 263 * <p> 264 * Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is 265 * likely to be decent, as long as iteration isn't unusually slow. This replaces {@code getRandomElement(Queue)}, 266 * since Queue implements Collection and the older Queue-using implementation was probably less efficient. 267 * </p> 268 * @param <T> the type of the returned object 269 * @param coll the Collection to get an element from; remember, Map does not implement Collection 270 * @return the randomly selected element 271 */ 272 public <T> T getRandomElement(Collection<T> coll) { 273 return super.getRandomElement(coll); 274 } 275 276 /** 277 * @return a value from the gaussian distribution 278 */ 279 @Override 280 public synchronized double nextGaussian() { 281 return super.nextGaussian(); 282 } 283 /** 284 * Returns a random integer below the given bound, or 0 if the bound is 0 or 285 * negative. Affects the current fortune. 286 * 287 * @param bound the upper bound (exclusive) 288 * @return the found number 289 */ 290 @Override 291 public int nextInt(int bound) { 292 if (bound <= 0) { 293 return 0; 294 } 295 296 return (int)(nextDouble() * bound); 297 } 298 299 /** 300 * Returns a random integer, which may be positive or negative. Affects the current fortune. 301 * @return A random int 302 */ 303 @Override 304 public int nextInt() { 305 return (int)((nextDouble() - 0.5) * 2.0 * 0x7FFFFFFF); 306 } 307 308 /** 309 * Returns a random long, which may be positive or negative. Affects the current fortune. 310 * @return A random long 311 */ 312 @Override 313 public long nextLong() { 314 return (long)((nextDouble() - 0.5) * 2.0 * 0x7FFFFFFFFFFFFFFFL); 315 } 316 317 /** 318 * Returns a random long below the given bound, or 0 if the bound is 0 or 319 * negative. 320 * 321 * @param bound the upper bound (exclusive) 322 * @return the found number 323 */ 324 @Override 325 public long nextLong(long bound) { 326 if (bound <= 0) { 327 return 0; 328 } 329 return (long)(nextDouble() * bound); 330 } 331 /** 332 * Gets the measure that this class uses for RNG fairness, defaulting to 0.54 (always between 0.0 and 1.0). 333 * @return the current fairness metric. 334 */ 335 public double getFairness() { 336 return fairness; 337 } 338 339 /** 340 * Sets the measure that this class uses for RNG fairness, which must always be between 0.0 and 1.0, and will be 341 * set to 0.54 if an invalid value is passed. 342 * @param fairness the desired fairness metric, which must be 0.0 <= fairness < 1.0 343 */ 344 public void setFairness(double fairness) { 345 if(fairness < 0.0 || fairness >= 1.0) 346 this.fairness = 0.54; 347 else 348 this.fairness = fairness; 349 } 350 351 /** 352 * Gets the status of the fortune used when calculating fairness adjustments. 353 * @return the current value used to determine whether the results should be adjusted toward fairness. 354 */ 355 public double getFortune() 356 { 357 return Math.abs(produced - baseline); 358 } 359 360 /** 361 * Resets the stored history this RNG uses to try to ensure fairness. 362 */ 363 public void resetFortune() 364 { 365 produced = 0.0; 366 baseline = 0.0; 367 } 368 /** 369 * 370 * @param bits the number of bits to be returned 371 * @return a random int of the number of bits specified. 372 */ 373 @Override 374 public int next(int bits) { 375 if(bits <= 0) 376 return 0; 377 if(bits > 32) 378 bits = 32; 379 return (int)(nextDouble() * (1l << bits)); 380 381 } 382 383 @Override 384 public Random asRandom() { 385 return super.asRandom(); 386 } 387 388 @Override 389 @GwtIncompatible 390 public <T> List<T> randomRotation(List<T> l) { 391 return super.randomRotation(l); 392 } 393 394 @Override 395 public <T> Iterable<T> getRandomStartIterable(List<T> list) { 396 return super.getRandomStartIterable(list); 397 } 398/* 399 @Override 400 @GwtIncompatible 401 public <T> T[] shuffle(T[] elements) { 402 return super.shuffle(elements); 403 } 404*/ 405 @Override 406 public <T> T[] shuffle(T[] elements, T[] dest) { 407 return super.shuffle(elements, dest); 408 } 409 410 @Override 411 public <T> ArrayList<T> shuffle(Collection<T> elements) { 412 return super.shuffle(elements); 413 } 414 415 @Override 416 public float nextFloat() { 417 return (float)nextDouble(); 418 } 419 420 @Override 421 public boolean nextBoolean() { 422 return nextDouble() >= 0.5; 423 } 424 425 @Override 426 public RandomnessSource getRandomness() { 427 return random; 428 } 429 430 @Override 431 public void setRandomness(RandomnessSource random) { 432 this.random = random; 433 } 434 435 /** 436 * Creates a copy of this DharmaRNG; it will generate the same random numbers, given the same calls in order, as 437 * this DharmaRNG at the point copy() is called. The copy will not share references with this DharmaRNG. 438 * 439 * @return a copy of this DharmaRNG 440 */ 441 @Override 442 public RNG copy() { 443 DharmaRNG next = new DharmaRNG(random.copy(), fairness); 444 next.produced = produced; 445 next.baseline = baseline; 446 return next; 447 } 448 449 /** 450 * Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as 451 * it can, and then returns output. Will only use a given position in the given data at most once; does this by 452 * shuffling a copy of data and getting a section of it that matches the length of output. 453 * 454 * Based on http://stackoverflow.com/a/21460179 , credit to Vincent van der Weele; modifications were made to avoid 455 * copying or creating a new generic array (a problem on GWT). 456 * @param data an array of T; will not be modified. 457 * @param output an array of T that will be overwritten; should always be instantiated with the portion length 458 * @param <T> can be any non-primitive type. 459 * @return an array of T that has length equal to output's length and may contain null elements if output is shorter 460 * than data 461 */ 462 @Override 463 public <T> T[] randomPortion(T[] data, T[] output) { 464 return super.randomPortion(data, output); 465 } 466 467 /** 468 * Gets a random portion of a List and returns it as a new List. Will only use a given position in the given 469 * List at most once; does this by shuffling a copy of the List and getting a section of it. 470 * 471 * @param data a List of T; will not be modified. 472 * @param count the non-negative number of elements to randomly take from data 473 * @return a List of T that has length equal to the smaller of count or data.length 474 */ 475 @Override 476 public <T> List<T> randomPortion(List<T> data, int count) { 477 return super.randomPortion(data, count); 478 } 479 480 /** 481 * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements. 482 * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative). 483 * 484 * @param start the start of the range of numbers to potentially use (inclusive) 485 * @param end the end of the range of numbers to potentially use (exclusive) 486 * @param count the total number of elements to use; will be less if the range is smaller than count 487 * @return an int array that contains at most one of each number in the range 488 */ 489 @Override 490 public int[] randomRange(int start, int end, int count) { 491 return super.randomRange(start, end, count); 492 } 493 494 @Override 495 public String toString() { 496 return "DharmaRNG{" + 497 "fairness=" + fairness + 498 ", produced=" + produced + 499 ", baseline=" + baseline + 500 "Randomness Source" + random + 501 '}'; 502 } 503}