A nifty new abstraction for the RNG: defer_rand

A defer_rand object stores random numbers in a resolution-independant
fashion, providing interesting monotonicity guarantees.  See the next
patch for a good use.

1 files changed, 35 insertions, 0 deletions

diff --git a/crawl-ref/source/random.h b/crawl-ref/source/random.h
index b1bdbe5021..b4d48639c9 100644
--- a/crawl-ref/source/random.h
+++ b/crawl-ref/source/random.h
@@ -3,6 +3,9 @@
 
 #include "rng.h"
 
+#include <map>
+#include <vector>
+
 bool coinflip();
 int div_rand_round( int num, int den );
 int div_round_up( int num, int den );
@@ -42,6 +45,38 @@ public:
     ~rng_save_excursion()         { pop_rng_state(); }
 };
 
+// A defer_rand object represents an infinite tree of random values, allowing
+// for a much more functional approach to randomness.  defer_rand values which
+// have been used should not be copy-constructed.  Querying the same path
+// multiple times will always give the same result.
+
+// An important property of defer_rand is that, except for rounding,
+// float(r.random2(X)) / X == float(r.random2(Y)) / Y for all X and Y.  In
+// other words:
+//
+// * The parameter you use on any given call does not matter.
+// * The object stores the fraction, not a specific integer.
+// * random2() is monotonic in its argument.
+class defer_rand
+{
+    std::vector<unsigned long> bits;
+    std::map<int, defer_rand> children;
+
+    bool x_chance_in_y_contd(int x, int y, int index);
+public:
+    // TODO It would probably be a good idea to have some sort of random
+    // number generator API, and the ability to pass RNGs into any function
+    // that wants them.
+    bool x_chance_in_y(int x, int y) { return x_chance_in_y_contd(x,y,0); }
+    bool one_chance_in(int a_million) { return x_chance_in_y(1,a_million); }
+    int random2(int maxp1);
+
+    int random_range(int low, int high);
+    int random2avg(int max, int rolls);
+
+    defer_rand& operator[] (int i);
+};
+
 template<typename Iterator>
 int choose_random_weighted(Iterator beg, const Iterator end)
 {