001package squidpony.squidmath;
002
003import squidpony.annotation.GwtIncompatible;
004
005import java.util.ArrayList;
006import java.util.Collection;
007import java.util.List;
008import java.util.Random;
009
010/**
011 * A subclass of StatefulRNG (and thus RNG) that allows customizing many parts of the random number generation.
012 * This is meant to be a more comprehensible version of the functionality present in RandomBias, and also for it to be
013 * easier to use with methods that expect an RNG.
014 * <br>
015 * You can change the expected average for the values this produces, which uses the RandomBias.EXPONENTIAL distribution,
016 * with all the caveats it has: it strongly favors either high or low values when the average gets especially high or
017 * low, but it can essentially cover all averages between 0.0 and 1.0 (this class limits it to 0.1 and 0.9, so other
018 * techniques can be used effectively).
019 * <br>
020 * You can also affect the "centrality" of random numbers, causing more to occur near the expected average (a bell curve
021 * effect), or cause more near extreme ends of the random number spectrum. In practice, centrality changes are hard to
022 * notice, but may be useful to simulate certain effects. An example of centrality changes in existing games include the
023 * Nintendo title Advance Wars 2, where a brutish commander could increase the amount of damage his units dealt but also
024 * suffered unpredictability; attacks could deal even more or much less damage than normal without any way to build
025 * tactics around it. Square Enix's Final Fantasy XII also notably differentiated certain weapons (axes, hammers, and
026 * "hand-cannons") from other similar options by making them deal less predictable damage. In both cases the connotation
027 * is that more randomness is fitting for a brute-force approach to combat where pre-planned strategies are less
028 * emphasized. It should also be noted that increasing the frequency of extreme results makes small bonuses to defense
029 * or offense typically less useful, and small penalties less harmful. The opposite can be true for a carefully tuned
030 * game where the most common results are tightly clustered, and most target numbers are just slightly above the
031 * ordinary average. In tabletop games, 1d20 and 3d6 have the same average, but 1d20 is uniform, where 3d6 is clustered
032 * around 10 and 11, each the result of 1/8 of rolls on their own and 1/4 together. This makes the case where a +1 bonus
033 * to succeed changes the outcome on approximately 5% of 1d20 rolls, regardless of the required number to succeed if it
034 * is less than 20. However, a +1 bonus matters on a variable portion of 3d6 rolls; if you become able to succeed on a
035 * 10 or 11 where that was a failure before, the bonus applies approximately 12.5% of the time. Becoming able to succeed
036 * on an 18 where that was a failure before is essentially worthless, affecting less than 0.5% of rolls. This property
037 * of centralized results should be considered if game balance and/or the lethality of combat is important. One lengthy
038 * stretch of extreme results by enemies that work against the favor of a player character generally result in a dead
039 * player character, and RNGs that make extreme results more common may seem particularly cruel to players.
040 * <br>
041 * This generator sets a field, rawLatest, every time a random number is produced. This stores a pseudo-random double
042 * between 0.0 (inclusive) and 1.0 (exclusive) that is not subject to the bias an expected average introduces, and is
043 * close to uniformly distributed. You should expect rawLatest to be higher when higher numbers are returned from a
044 * method like nextInt(), and lower when lower numbers are returned. This can be useful for rare effects that should not
045 * be drastically more or less likely when slight changes are made to the expected average; if the expected average is
046 * 0.65, many more random doubles from nextDouble() will be between 0.95 and 1.0 (probably more than 10% of random
047 * numbers), but rawLatest will only be between 0.95 and 1.0 for close to 5% of all generations.
048 * <br>
049 * You can get and set the state this uses internally, and this is stored as a 64-bit long.
050 * <br>
051 * The choice of RandomnessSource doesn't really matter since this will always use a LightRNG internally. LightRNG is
052 * the current best StatefulRandomness implementation, with excellent performance characteristics and few flaws, though
053 * its relatively low period may sometimes be a detriment.
054 * <br>
055 * More customizations may be added in the future to the ones available currently.
056 */
057public class EditRNG extends StatefulRNG {
058
059        /** Used to tweak the generator toward high or low values. */
060    private double expected = 0.5;
061
062    /**
063     * When positive, makes the generator more likely to generate values close to the average (bell curve).
064     * When zero (the default), makes no changes to the centering of values.
065     * When negative, makes the generator swing more toward extremes rather than gravitate toward the average.
066     * Values are typically between -100 and 100, but can have extreme weight and overshadow other parts of the RNG if
067     * they go much higher than 200.
068     */
069    private double centrality = 0.0;
070    /**
071     * The latest generated double, between 0.0 and 1.0, before changes for centrality and expected average.
072     * Doubles are used to generate all random numbers this class produces, so be aware that calling getRandomElement()
073     * will change this just as much as nextDouble(), nextInt(), or between() will. Primarily useful to obtain
074     * uniformly-distributed random numbers that are related to the biased random numbers this returns as a main result,
075     * such as to find when the last number generated was in the bottom 5% (less than 0.05, which could represent some
076     * kind of critical failure or fumble) or top 10% (greater than or equal to 0.9, which could grant a critical
077     * success or luck-based reward of some kind).
078     */
079    public double rawLatest = 0.5;
080        private static final long serialVersionUID = -2458726316853811777L;
081
082    /**
083     * Constructs an EditRNG with a pseudo-random seed from Math.random().
084     */
085    public EditRNG()
086    {
087    }
088    /**
089     * Construct a new EditRNG with the given seed.
090     *
091     * @param seed used to seed the default RandomnessSource.
092     */
093    public EditRNG(final long seed) {
094        super(seed);
095    }
096    /**
097     * Construct a new EditRNG with the given seed.
098     *
099     * @param seed used to seed the default RandomnessSource.
100     */
101    public EditRNG(final String seed) {
102        super(seed);
103    }
104
105    /**
106     * Construct a new EditRNG with the given seed.
107     *
108     * @param seed used to seed the default RandomnessSource.
109     * @param expected the expected average for random doubles, which will be capped between 0.1 and 0.9
110     */
111    public EditRNG(final long seed, double expected) {
112        super(seed);
113        this.expected = Math.max(0.1, Math.min(0.89999994, expected));
114    }
115    /**
116     * Construct a new EditRNG with the given seed.
117     *
118     * @param seed used to seed the default RandomnessSource.
119     * @param expected the expected average for random doubles, which will be capped between 0.1 and 0.9
120     */
121    public EditRNG(final String seed, double expected) {
122        super(seed);
123        this.expected = Math.max(0.1, Math.min(0.89999994, expected));
124    }
125
126    /**
127     * Construct a new EditRNG with the given seed.
128     *
129     * @param seed used to seed the default RandomnessSource.
130     * @param expected the expected average for random doubles, which will be capped between 0.1 and 0.9
131     * @param centrality if positive, makes results more likely to be near expected; if negative, the opposite. The
132     *                   absolute value of centrality affects how centered results will be, with 0 having no effect
133     */
134    public EditRNG(final long seed, double expected, double centrality) {
135        super(seed);
136        this.expected = Math.max(0.1, Math.min(0.89999994, expected));
137        this.centrality = centrality;
138    }
139    /**
140     * Construct a new EditRNG with the given seed.
141     *
142     * @param seed used to seed the default RandomnessSource.
143     * @param expected the expected average for random doubles, which will be capped between 0.1 and 0.9
144     * @param centrality if positive, makes results more likely to be near expected; if negative, the opposite. The
145     *                   absolute value of centrality affects how centered results will be, with 0 having no effect
146     */
147    public EditRNG(final String seed, double expected, double centrality) {
148        super(seed);
149        this.expected = Math.max(0.1, Math.min(0.89999994, expected));
150        this.centrality = centrality;
151    }
152
153    /**
154     * Construct a new EditRNG with the given seed.
155     *
156     * @param rs the implementation used to generate random bits.
157     */
158    public EditRNG(final RandomnessSource rs) {
159        super(rs);
160    }
161    /**
162     * Construct a new EditRNG with the given seed.
163     *
164     * @param rs the implementation used to generate random bits.
165     * @param expected the expected average for random doubles, which will be capped between 0.1 and 0.9
166     */
167    public EditRNG(final RandomnessSource rs, double expected) {
168        super(rs);
169        this.expected = Math.max(0.1, Math.min(0.89999994, expected));
170    }
171    /**
172     * Construct a new EditRNG with the given seed.
173     *
174     * @param rs the implementation used to generate random bits.
175     * @param expected the expected average for random doubles, which will be capped between 0.1 and 0.9
176     * @param centrality if positive, makes results more likely to be near expected; if negative, the opposite. The
177     *                   absolute value of centrality affects how centered results will be, with 0 having no effect
178     */
179    public EditRNG(final RandomnessSource rs, double expected, double centrality) {
180        super(rs);
181        this.expected = Math.max(0.1, Math.min(0.89999994, expected));
182        this.centrality = centrality;
183    }
184
185    /**
186     * Generate a random double, altered to try to match the expected average and centrality.
187     * @return a double between 0.0 (inclusive) and 1.0 (exclusive)
188     */
189    @Override
190    public double nextDouble() {
191        long l = random.nextLong();
192        double gen = (l & 0x1fffffffffffffL) * DOUBLE_UNIT, scatter = (l & 0xffffffL) * FLOAT_UNIT;
193        rawLatest = 0.9999999999999999 - gen;
194        gen = 0.9999999999999999 - Math.pow(gen, 1.0 / (1.0 - expected) - 1.0);
195        if(centrality > 0) {
196            scatter = 0.9999999999999999 - Math.pow(scatter, 1.0 / (1.0 - expected) - 1.0);
197            gen = (gen * 100 + scatter * centrality) / (100 + centrality);
198        }
199        else if(centrality < 0)
200        {
201            scatter = Math.sin(scatter * Math.PI * 0.5);
202            scatter *= scatter;
203            if(expected >= 0.5)
204                scatter = scatter * (1.0 - expected) * 2 + expected - (1.0 - expected);
205            else
206                scatter *= expected * 2;
207            gen = (gen * 100 + scatter * -centrality) / (100 - centrality);
208        }
209
210        return gen;
211
212    }
213
214    /**
215     * This returns a random double between 0.0 (inclusive) and max (exclusive).
216     *
217     * @return a value between 0 (inclusive) and max (exclusive)
218     */
219    @Override
220    public double nextDouble(double max) {
221        return nextDouble() * max;
222    }
223
224    /**
225     * Returns a value from a even distribution from min (inclusive) to max
226     * (exclusive).
227     *
228     * @param min the minimum bound on the return value (inclusive)
229     * @param max the maximum bound on the return value (exclusive)
230     * @return the found value
231     */
232    @Override
233    public double between(double min, double max) {
234        return super.between(min, max);
235    }
236
237    /**
238     * Returns a value between min (inclusive) and max (exclusive).
239     *
240     * The inclusive and exclusive behavior is to match the behavior of the
241     * similar method that deals with floating point values.
242     *
243     * @param min the minimum bound on the return value (inclusive)
244     * @param max the maximum bound on the return value (exclusive)
245     * @return the found value
246     */
247    @Override
248    public int between(int min, int max)
249    {
250        return super.between(min, max);
251    }
252
253    @Override
254    public long between(long min, long max) {
255        return super.between(min, max);
256    }
257
258    /**
259     * Returns the average of a number of randomly selected numbers from the
260     * provided range, with min being inclusive and max being exclusive. It will
261     * sample the number of times passed in as the third parameter.
262     *
263     * The inclusive and exclusive behavior is to match the behavior of the
264     * similar method that deals with floating point values.
265     *
266     * This can be used to weight RNG calls to the average between min and max.
267     *
268     * @param min the minimum bound on the return value (inclusive)
269     * @param max the maximum bound on the return value (exclusive)
270     * @param samples the number of samples to take
271     * @return the found value
272     */
273    @Override
274    public int betweenWeighted(int min, int max, int samples) {
275        return super.betweenWeighted(min, max, samples);
276    }
277
278    /**
279     * Returns a random element from the provided array and maintains object
280     * type.
281     *
282     * @param <T> the type of the returned object
283     * @param array the array to get an element from
284     * @return the randomly selected element
285     */
286    @Override
287    public <T> T getRandomElement(T[] array) {
288        return super.getRandomElement(array);
289    }
290
291    /**
292     * Returns a random element from the provided list. If the list is empty
293     * then null is returned.
294     *
295     * @param <T> the type of the returned object
296     * @param list the list to get an element from
297     * @return the randomly selected element
298     */
299    @Override
300    public <T> T getRandomElement(List<T> list) {
301        return super.getRandomElement(list);
302    }
303
304    /**
305     * Returns a random element from the provided ShortSet. If the set is empty
306     * then an exception is thrown.
307     *
308     * <p>
309     * Requires iterating through a random amount of the elements in set, so performance depends on the size of set but
310     * is likely to be decent. This is mostly meant for internal use, the same as ShortSet.
311     * </p>
312     * @param set the ShortSet to get an element from
313     * @return the randomly selected element
314     */
315    public short getRandomElement(ShortSet set) {
316        return super.getRandomElement(set);
317    }
318
319    /**
320     * Returns a random element from the provided Collection, which should have predictable iteration order if you want
321     * predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection
322     * (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted
323     * Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement
324     * Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can
325     * pass the keys or values. If coll is empty, returns null.
326     *
327     * <p>
328     * Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is
329     * likely to be decent, as long as iteration isn't unusually slow. This replaces {@code getRandomElement(Queue)},
330     * since Queue implements Collection and the older Queue-using implementation was probably less efficient.
331     * </p>
332     * @param <T> the type of the returned object
333     * @param coll the Collection to get an element from; remember, Map does not implement Collection
334     * @return the randomly selected element
335     */
336    public <T> T getRandomElement(Collection<T> coll) {
337        return super.getRandomElement(coll);
338    }
339
340    /**
341     * @return a value from the gaussian distribution
342     */
343    @Override
344    public synchronized double nextGaussian() {
345        return super.nextGaussian();
346    }
347    /**
348     * Returns a random integer below the given bound, or 0 if the bound is 0 or
349     * negative.
350     *
351     * @param bound the upper bound (exclusive)
352     * @return the found number
353     */
354    @Override
355    public int nextInt(int bound) {
356        if (bound <= 0) {
357            return 0;
358        }
359
360        return (int)(nextDouble() * bound);
361    }
362
363    /**
364     * Returns a random integer, which may be positive or negative.
365     * @return A random int
366     */
367    @Override
368    public int nextInt() {
369        return (int)((nextDouble() * 2.0 - 1.0) * 0x7FFFFFFF);
370    }
371
372    /**
373     * Returns a random long, which may be positive or negative.
374     * @return A random long
375     */
376    @Override
377    public long nextLong() {
378        return (long)((nextDouble() * 2.0 - 1.0) * 0x7FFFFFFFFFFFFFFFL);
379    }
380
381    /**
382     * Returns a random long below the given bound, or 0 if the bound is 0 or
383     * negative.
384     *
385     * @param bound the upper bound (exclusive)
386     * @return the found number
387     */
388    @Override
389        public long nextLong(long bound) {
390        if (bound <= 0) {
391            return 0;
392        }
393        return (long)(nextDouble() * bound);
394    }
395    /**
396     * Gets the current expected average for this EditRNG.
397     * @return the current expected average.
398     */
399    public double getExpected() {
400        return expected;
401    }
402
403    /**
404     * Sets the expected average for random doubles this produces, which must always be between 0.1 and 0.9, and will be
405     * set to 0.5 if an invalid value is passed.
406     * @param expected the expected average to use, which should be 0.1 &lt;= fairness &lt; 0.9
407     */
408    public void setExpected(double expected) {
409        if(expected < 0.0 || expected >= 1.0)
410            this.expected = 0.5;
411        else
412            this.expected = expected;
413    }
414
415    /**
416     * Gets the current centrality measure of this EditRNG.
417     * Centrality has several possible effects:
418     * When positive, makes the generator more likely to generate values close to the average (bell curve).
419     * When zero (the default), makes no changes to the centering of values.
420     * When negative, makes the generator swing more toward extremes rather than gravitate toward the average.
421     * <br>
422     * Values are typically between -100 and 100, but can have extreme weight and overshadow other parts of the RNG if
423     * they go much higher than 200.
424     * @return the current centrality
425     */
426    public double getCentrality() {
427        return centrality;
428    }
429
430    /**
431     * Gets the current centrality measure of this EditRNG.
432     * Centrality has several possible effects:
433     * When positive, makes the generator more likely to generate values close to the average (bell curve).
434     * When zero (the default), makes no changes to the centering of values.
435     * When negative, makes the generator swing more toward extremes rather than gravitate toward the average.
436     * <br>
437     * Values are typically between -100 and 100, but can have extreme weight and overshadow other parts of the RNG if
438     * they go much higher than 200.
439     * @param centrality the new centrality measure to use
440     */
441    public void setCentrality(double centrality) {
442        this.centrality = centrality;
443    }
444
445    /**
446     *
447     * @param bits the number of bits to be returned
448     * @return a random int of the number of bits specified.
449     */
450    @Override
451    public int next(int bits) {
452        if(bits <= 0)
453            return 0;
454        if(bits > 32)
455            bits = 32;
456        return (int)(nextDouble() * (1L << bits));
457
458    }
459
460    @Override
461    public Random asRandom() {
462        return super.asRandom();
463    }
464
465    @Override
466    @GwtIncompatible
467    public <T> List<T> randomRotation(List<T> l) {
468        return super.randomRotation(l);
469    }
470
471    @Override
472    public <T> Iterable<T> getRandomStartIterable(List<T> list) {
473        return super.getRandomStartIterable(list);
474    }
475
476    @Override
477    public <T> T[] shuffle(T[] elements, T[] dest) {
478        return super.shuffle(elements, dest);
479    }
480
481    @Override
482    public <T> ArrayList<T> shuffle(Collection<T> elements) {
483        return super.shuffle(elements);
484    }
485
486    @Override
487    public float nextFloat() {
488        return (float)nextDouble();
489    }
490
491    @Override
492    public boolean nextBoolean() {
493        return nextDouble() >= 0.5;
494    }
495
496    @Override
497    public RandomnessSource getRandomness() {
498        return random;
499    }
500
501    @Override
502    public void setRandomness(RandomnessSource random) {
503        this.random = random;
504    }
505
506    /**
507     * Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as
508     * it can, and then returns output. Will only use a given position in the given data at most once; does this by
509     * shuffling a copy of data and getting a section of it that matches the length of output.
510     *
511     * Based on http://stackoverflow.com/a/21460179 , credit to Vincent van der Weele; modifications were made to avoid
512     * copying or creating a new generic array (a problem on GWT).
513     * @param data an array of T; will not be modified.
514     * @param output an array of T that will be overwritten; should always be instantiated with the portion length
515     * @param <T> can be any non-primitive type.
516     * @return an array of T that has length equal to output's length and may contain null elements if output is shorter
517     * than data
518     */
519    @Override
520    public <T> T[] randomPortion(T[] data, T[] output) {
521        return super.randomPortion(data, output);
522    }
523
524    /**
525     * Gets a random portion of a List and returns it as a new List. Will only use a given position in the given
526     * List at most once; does this by shuffling a copy of the List and getting a section of it.
527     *
528     * @param data  a List of T; will not be modified.
529     * @param count the non-negative number of elements to randomly take from data
530     * @return a List of T that has length equal to the smaller of count or data.length
531     */
532    @Override
533    public <T> List<T> randomPortion(List<T> data, int count) {
534        return super.randomPortion(data, count);
535    }
536
537    /**
538     * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements.
539     * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative).
540     *
541     * @param start the start of the range of numbers to potentially use (inclusive)
542     * @param end   the end of the range of numbers to potentially use (exclusive)
543     * @param count the total number of elements to use; will be less if the range is smaller than count
544     * @return an int array that contains at most one of each number in the range
545     */
546    @Override
547    public int[] randomRange(int start, int end, int count) {
548        return super.randomRange(start, end, count);
549    }
550
551    /**
552     * Gets the latest "un-biased" random double used to produce the most recent (potentially) biased random number
553     * generated for another method in this class, such as nextDouble(), between(), or getRandomElement(). This is a
554     * double between 0.0 (inclusive) and 1.0 (exclusive).
555     * @return the latest uniformly-distributed double before bias is added; between 0.0 and 1.0 (exclusive upper)
556     */
557    public double getRawLatest() {
558        return rawLatest;
559    }
560
561    /**
562     * Creates a copy of this StatefulRNG; it will generate the same random numbers, given the same calls in order, as
563     * this StatefulRNG at the point copy() is called. The copy will not share references with this StatefulRNG.
564     *
565     * @return a copy of this StatefulRNG
566     */
567    @Override
568    public RNG copy() {
569        EditRNG next = new EditRNG(random.copy(), expected, centrality);
570        next.rawLatest = rawLatest;
571        return next;
572    }
573}