public class VanDerCorputQRNG extends java.lang.Object implements StatefulRandomness, RandomnessSource, java.io.Serializable
nextDouble()
; and there are several static methods offered for convenient generation of points on the
related Halton sequence (as well as faster generation of doubles in the base-2 van der Corput sequence, and a special
method that switches which base it uses depending on the index to seem even less clearly-patterned). There are also,
for lack of a better place to put such small code, methods to generate points in the R2 sequence found by Martin
Roberts, which is very similar in 2D to some Halton sequences but has better separation between points.
SobolQRNG
). So what's it good for?
halton(int, int, int, int[])
here. If it doesn't meet your needs, there's a little more complexity involved.
Using a VanDerCorputQRNG with base 3 for the x-axis and another VanDerCorputQRNG with base 5 for the y-axis,
requesting a double from each to make points between (0.0, 0.0) and (1.0, 1.0), has an interesting trait that can be
desirable for many kinds of positioning in 2D: once a point has been generated, an identical point will never be
generated until floating-point precision runs out, but more than that, nearby points will almost never be generated
for many generations, and most points will stay at a comfortable distance from each other if the bases are different
and both prime (or, more technically, if they share no common denominators). This is also known as a Halton sequence,
which is a group of sequences of points instead of simply numbers. The choices of 3 and 5 are examples; any two
different primes will technically work for 2D (as well as any two numbers that share no common factor other than 1,
that is, they are relatively coprime), but patterns can be noticeable with primes larger than about 7, with 11 and 13
sometimes acceptable. Three VanDerCorputQRNG sequences could be used for a Halton sequence of 3D
points, using three different prime bases, four for 4D, etc. SobolQRNG can be used for the same purpose, but the
points it generates are typically more closely-aligned to a specific pattern, the pattern is symmetrical between all
four quadrants of the square between (0.0, 0.0) and (1.0, 1.0) in 2D, and it probably extends into higher dimensions.
Using one of the possible Halton sequences gives some more flexibility in the kinds of random-like points produced.
Oddly, using a base-2 van der Corput sequence as the x axis in a Halton sequence and a base-39 van der Corput
sequence as the y axis results in the greatest minimum distance between points found so far while still involving a
base-2 sequence (which is preferential for performance). There, the minimum distance between the first 65536 points
in the [0,1) range is 0.001147395; a runner-up is a y base of 13, which has a minimum distance of 0.000871727 . The
(2,39) Halton sequence is used by halton(int, int, int)
and halton(int, int, int, int[])
.
Constructor and Description |
---|
VanDerCorputQRNG()
Constructs a new van der Corput sequence generator with base 7, starting point 37, and scrambling disabled.
|
VanDerCorputQRNG(int base,
long seed)
Constructs a new van der Corput sequence generator with the given base (a.k.a.
|
VanDerCorputQRNG(long seed)
Constructs a new van der Corput sequence generator with the given starting point in the sequence as a seed.
|
Modifier and Type | Method and Description |
---|---|
static double |
altDetermine(long base,
int index)
Similar to
determine(int, int) , but can take bases that aren't prime and can sometimes produce a
Halton-like sequence with almost-as-good distance between points. |
VanDerCorputQRNG |
copy()
Produces a copy of this StatefulRandomness that, if next() and/or nextLong() are called on this object and the
copy, both will generate the same sequence of random numbers from the point copy() was called.
|
static double |
determine(int base,
int index)
Convenience method to get a double from the van der Corput sequence with the given
base at the requested
index without needing to construct a VanDerCorputQRNG. |
static double |
determine2_scrambled(int index)
Method to get a double from the van der Corput sequence with the base 2 at a scrambling of the requested
index without needing to construct a VanDerCorputQRNG. |
static double |
determine2(int index)
Convenience method to get a double from the van der Corput sequence with the base 2 at the requested
index without needing to construct a VanDerCorputQRNG. |
static double |
determineMixed(int index)
Chooses one sequence from the van der Corput sequences with bases 2, 3, and 5, where 5 is used 1/8 of the time,
3 is used 3/8 of the time, and 2 is used 1/2 of the time, and returns a double from the chosen sequence at the
specified
index . |
boolean |
equals(java.lang.Object o) |
long |
getState()
Get the current internal state of the StatefulRandomness as a long.
|
static Coord |
haltoid(int seed,
int width,
int height,
int xOffset,
int yOffset,
int index)
Samples a quasi-random Coord sequence that is almost unique to the given seed, getting a Coord with x between
xOffset (inclusive) and width + xOffset (exclusive), y between yOffset (inclusive) and height + yOffset
(exclusive).
|
static Coord |
halton(int width,
int height,
int index)
Convenience method that gets a quasi-random Coord between integer (0,0) inclusive and (width,height) exclusive
and gets the corresponding Coord from the Coord pool.
|
static Coord3D |
halton(int width,
int height,
int depth,
int index)
Convenience method that gets a quasi-random Coord3D between integer (0,0,0) inclusive and (width,height,depth)
exclusive.
|
static int[] |
halton(int width,
int height,
int index,
int[] point)
Convenience method that gets a quasi-random 2D point between integer (0,0) inclusive and (width,height)
exclusive and fills it into point.
|
static Coord |
halton(int width,
int height,
int xOffset,
int yOffset,
int index)
Convenience method that gets a quasi-random Coord between integer (0,0) inclusive and (width,height) exclusive
and gets the corresponding Coord from the Coord pool.
|
static int[] |
halton(int width,
int height,
int depth,
int index,
int[] point)
Convenience method that gets a quasi-random 3D point between integer (0,0,0) inclusive and (width,height,depth)
exclusive.
|
int |
hashCode() |
int |
next(int bits)
Using this method, any algorithm that might use the built-in Java Random
can interface with this randomness source.
|
double |
nextDouble()
Gets the next quasi-random double from between 0.0 and 1.0 (normally both exclusive; only if state is negative or
has wrapped around to a negative value can 0.0 ever be produced).
|
long |
nextLong()
Gets the next quasi-random long as a fraction of
Long.MAX_VALUE ; this can never produce a negative value. |
static double |
planarDetermine(long base,
int index)
A quasi-random number generator of doubles between 0.0 inclusive and 1.0 exclusive, but that has issues when it
would be used like a Halton sequence.
|
static int |
roberts(int span,
int offset,
int index)
Martin Roberts' "unreasonably effective" quasi-random int sequence based on the golden ratio.
|
static Coord |
roberts(int width,
int height,
int xOffset,
int yOffset,
int index)
Martin Roberts' "unreasonably effective" quasi-random point sequence based on a 2D analogue to the golden ratio.
|
void |
setState(long state)
Set the current internal state of this StatefulRandomness with a long.
|
java.lang.String |
toString() |
static float |
weakDetermine(int index)
Given any int (0 is allowed), this gets a somewhat-sub-random float from 0.0 (inclusive) to 1.0 (exclusive)
using the same implementation as
NumberTools.randomFloat(long) but with index alterations. |
static float |
weakSignedDetermine(int index)
Like
weakDetermine(int) , but returns a float between -1.0f and 1.0f, exclusive on both. |
public VanDerCorputQRNG()
public VanDerCorputQRNG(long seed)
seed
- the seed as a long that will be used as the starting point in the sequence; ideally positive but lowpublic VanDerCorputQRNG(int base, long seed)
base
- the base or radix used for this VanDerCorputQRNG; for most uses this should be prime but small-ishseed
- the seed as a long that will be used as the starting point in the sequence; ideally positive but lowpublic long nextLong()
Long.MAX_VALUE
; this can never produce a negative value.
It is extremely unlikely to produce two identical values unless the state is very high or is negative; state
increases by exactly 1 each time this, next(int)
, or nextDouble()
is called and can potentially
wrap around to negative values after many generations.nextLong
in interface RandomnessSource
Long.MAX_VALUE
public int next(int bits)
RandomnessSource
next
in interface RandomnessSource
bits
- the number of bits to be returnedpublic double nextDouble()
public VanDerCorputQRNG copy()
StatefulRandomness
copy
in interface RandomnessSource
copy
in interface StatefulRandomness
public long getState()
StatefulRandomness
getState
in interface StatefulRandomness
public void setState(long state)
StatefulRandomness
setState
in interface StatefulRandomness
state
- a 64-bit long. You should avoid passing 0, even though some implementations can handle that.public java.lang.String toString()
toString
in class java.lang.Object
public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public int hashCode()
hashCode
in class java.lang.Object
public static int[] halton(int width, int height, int index, int[] point)
new VanDerCorputQRNG(2, index)
and the other with
new VanDerCorputQRNG(39, index)
, then getting an x-coordinate from the first with
(int)(nextDouble() * width)
and similarly for y with the other generator. The advantage here is you don't
actually create any objects using this static method, only assigning to point, if valid. You might find an
advantage in using values for index that start higher than 20 or so, but you can pass sequential values for index
and generally get points that won't be near each other; this is not true for all parameters to Halton sequences,
but it is true for this one.width
- the maximum exclusive bound for the x-positions (index 0) of points this can returnheight
- the maximum exclusive bound for the y-positions (index 1) of points this can returnindex
- an int that, if unique, positive, and not too large, will usually result in unique pointspoint
- an int array that will be modified; should have length 2; if null or too small, a new array will be createdpublic static Coord halton(int width, int height, int index)
new VanDerCorputQRNG(2, index)
and the other with
new VanDerCorputQRNG(39, index)
, then getting an x-coordinate from the first with
(int)(nextDouble() * width)
and similarly for y with the other generator. You might find an advantage in
using values for index that start higher than 20 or so, but you can pass sequential values for index and
generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but
it is true for this one.width
- the maximum exclusive bound for the x-positions (index 0) of points this can returnheight
- the maximum exclusive bound for the y-positions (index 1) of points this can returnindex
- an int that, if unique, positive, and not too large, will usually result in unique pointspublic static Coord halton(int width, int height, int xOffset, int yOffset, int index)
new VanDerCorputQRNG(2, index)
and the other with
new VanDerCorputQRNG(39, index)
, then getting an x-coordinate from the first with
(int)(nextDouble() * width)
and similarly for y with the other generator. You might find an advantage in
using values for index that start higher than 20 or so, but you can pass sequential values for index and
generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but
it is true for this one.width
- the width of the area this can coverheight
- the height of the area this can coverxOffset
- the lowest x-coordinate this can produce, and also added to width to get the upper bound on xyOffset
- the lowest y-coordinate this can produce, and also added to height to get the upper bound on yindex
- an int that, if unique, positive, and not too large, will usually result in unique pointspublic static int[] halton(int width, int height, int depth, int index, int[] point)
new VanDerCorputQRNG(2, index)
another with new VanDerCorputQRNG(3, index)
,
and another with new VanDerCorputQRNG(5, index)
, then getting an x-coordinate from the first with
(int)(nextDouble() * width)
and similarly for y and z with the other generators. The advantage here is
you don't actually create any objects using this static method, only assigning to point, if valid. You might find
an advantage in using values for index that start higher than 20 or so, but you can pass sequential values for
index and generally get points that won't be near each other; this is not true for all parameters to Halton
sequences, but it is true for this one.width
- the maximum exclusive bound for the x-positions (index 0) of points this can returnheight
- the maximum exclusive bound for the y-positions (index 1) of points this can returndepth
- the maximum exclusive bound for the z-positions (index 2) of points this can returnindex
- an int that, if unique, positive, and not too large, will usually result in unique pointspoint
- an int array that will be modified; should have length 3; if null or too small, a new array will be createdpublic static Coord3D halton(int width, int height, int depth, int index)
new VanDerCorputQRNG(2, index)
another with new VanDerCorputQRNG(3, index)
,
and another with new VanDerCorputQRNG(5, index)
, then getting an x-coordinate from the first with
(int)(nextDouble() * width)
and similarly for y and z with the other generators. This overload always
creates a new Coord3D object, so you might prefer halton(int, int, int, int, int[])
, which can reuse an
int array. You might find an advantage in using values for index that start higher than 20 or so, but you can
pass sequential values for index and generally get points that won't be near each other; this is not true for all
parameters to Halton sequences, but it is true for this one.width
- the maximum exclusive bound for the x-positions (index 0) of points this can returnheight
- the maximum exclusive bound for the y-positions (index 1) of points this can returndepth
- the maximum exclusive bound for the z-positions (index 2) of points this can returnindex
- an int that, if unique, positive, and not too large, will usually result in unique pointspublic static double determine(int base, int index)
base
at the requested
index
without needing to construct a VanDerCorputQRNG. You should use a prime number for base; 2, 3, 5,
and 7 should be among the first choices to ensure optimal quality unless you are scrambling the index yourself.
If speed is the priority, then larger prime bases counter-intuitively perform better than small ones; 0x1337,
0xDE4D, 0x510B and 0xACED are all probable primes (using BigInteger.isProbablePrime(int)
) that
may do well here for speed but will likely require some basic scrambling of the index order. This method on its
own does not perform any scrambling on index other than incrementing it and ensuring it is positive (by
discarding the sign bit; for all positive index values other than 0x7FFFFFFF, this has no effect). If you want
to quickly scramble an int index i
for this purpose, try
(i ^ (i << 7 | i >>> 25) ^ (i << 19 | i >>> 13))
, which may compile to SSE instructions on recent
desktop processors and won't risk losing precision on GWT.
determine2(int)
when base is 2, which should offer some speed improvement.
The other bases use code adapted from
Alan Wolfe's blog,
which turned out to be a lot faster than the previous way I had it implemented.base
- a prime number to use as the base/radix of the van der Corput sequenceindex
- the position in the sequence of the requested base, as a non-negative intpublic static double determine2(int index)
index
without needing to construct a VanDerCorputQRNG. This does not perform any scrambling on index
other than incrementing it and ensuring it is positive (by discarding the sign bit; for all positive index values
other than 0x7FFFFFFF (Integer.MAX_VALUE
), this has no effect).
determine(int, int)
when base is 2, and should be faster than other bases.index
- the position in the base-2 van der Corput sequence, as a non-negative intpublic static double determine2_scrambled(int index)
index
without needing to construct a VanDerCorputQRNG. This performs different scrambling on index
than the instance methods on this class perform, and it seems to do well enough while being a little simpler.
This is meant to be usable as an alternative to a different base for a van der Corput sequence when you need two
different sequences, and are already using base 2 via determine2(int)
.
determine(int, int)
with base 2. It should take only slightly longer to run than
determine2(int)
, due to the brief amount of time needed to scramble the index.index
- the position in the sequence of the requested basepublic static double determineMixed(int index)
index
. The exact setup used for the choice this makes is potentially fragile, but in certain
circumstances this does better than SobolQRNG
at avoiding extremely close values (the kind that overlap
on actual maps). Speed is not a concern here; this should be very much fast enough for the expected usage in
map generation (it's used in GreasedRegion.quasiRandomSeparated(double)
.index
- the index to use from one of the sequences; will also be used to select sequencepublic static float weakDetermine(int index)
NumberTools.randomFloat(long)
but with index alterations. Only "weak"
because it lacks the stronger certainty of subsequent numbers being separated that the Van der Corput sequence
has. Not actually sub-random, but should be distributed fairly well (internally uses ThrustAltRNG
's
algorithm, which does not guarantee that its outputs are unique).
index
- any intpublic static float weakSignedDetermine(int index)
weakDetermine(int)
, but returns a float between -1.0f and 1.0f, exclusive on both. Uses
NumberTools.randomSignedFloat(long)
internally but alters the index parameter so calls with nearby values
for index are less likely to have nearby results.index
- any intpublic static double altDetermine(long base, int index)
determine(int, int)
, but can take bases that aren't prime and can sometimes produce a
Halton-like sequence with almost-as-good distance between points. The base is allowed to be any odd long,
(negative bases are allowed). The index can technically also be negative, and if this is given 0 it will not
return any specific number (it will vary with the base). This returns a double between 0.0 inclusive and 1.0
exclusive. Better results have been found with larger bases (points tend to be more spread out). It is never as
good at spreading out 2D points as a 2,3 Halton sequence, at least for any bases tried so far.
((base * Integer.reverse(index) << 21) & 0x1fffffffffffffL) * 0x1p-53
, where base is an odd long and
index is any int. It works best in one dimension.base
- any odd longindex
- any intpublic static double planarDetermine(long base, int index)
(((base * Integer.reverse(index)) << 21) & 0x1fffffffffffffL) * 0x1p-53;
, where base is a long and index
is an int (as in the method signature). The multiplier 0x1p-53 is a very small hexadecimal double literal, using
the same syntax as other parts of SquidLib use for packed floats; using this helps avoid precision loss. If you
want a range larger than 0.0 to 1.0, you can change the multiplier 0x1p-53
to some other constant, like
declaring final double upTo100 = 0x1p-53 * 100.0
before some code that wants quasi-random numbers between
0.0 inclusive and 100.0 exclusive, then using
(((base * Integer.reverse(index)) << 21) & 0x1fffffffffffffL) * upTo100;
to get those numbers. It isn't
precise to use this technique to get numbers with an upper bound less than 1.0, because 0x1p-53 is about as small
as a double can get with precision intact. In that case, you can use
(((base * Integer.reverse(index)) << 8) & 0xffffffffffL) * smallBound;
where smallBound has been declared
as final double smallBound = 0x1p-40 * 0.05;
(where 0.05 can be switched out for any double between
1.0/8192.0 and 1.0).base
- any odd long; the most significant 21 bits (except the sign bit) are effectively ignoredindex
- any int; if 0 this will return 0public static Coord haltoid(int seed, int width, int height, int xOffset, int yOffset, int index)
seed
- an int seed that should be an odd numberwidth
- the width of the area this can coverheight
- the height of the area this can coverxOffset
- the lowest x-coordinate this can produce, and also added to width to get the upper bound on xyOffset
- the lowest y-coordinate this can produce, and also added to height to get the upper bound on yindex
- the index in the sequence, almost always a positive int that increases by 1 with each callpublic static int roberts(int span, int offset, int index)
index
likely to be different for at least span / 4
indices (very low spans may offer less of
a guarantee).
roberts(int, int, int, int, int)
for 2D points and this method for 1D values; the same
properties won't be preserved if you use a 1D Roberts sequence in 2D.span
- the size of the range this can returnoffset
- the minimum value this can returnindex
- the index of the int in the 1D Roberts sequence; should be greater than 0, but not required to bepublic static Coord roberts(int width, int height, int xOffset, int yOffset, int index)
index
likely to be
different for at least width * height / 4
indices (very low sizes may offer less of a guarantee).width
- the x-size of the space this can place a Coordheight
- the y-size of the space this can place a CoordxOffset
- the minimum x-position of a CoordyOffset
- the minimum y-position of a Coordindex
- the index of the Coord in the 2D Roberts sequence; should be greater than 0, but not required to beCopyright © Eben Howard 2012–2022. All rights reserved.