Random number generation

archive biomonkey
1

Just putting a dedicated post here. Gonna be some stuff about random numbers here, because it’s such an important part of BioMonkey.



BioMonkey doesn’t use javas default random generator, it has an XORshift generator. It is many times faster. If you look in the FastRandom class in the forester lib you will find the link to a whitepaper and some info about the quality of the numbers etc.



This is some data. I copied it from some post I made last year.



Speed check:

compile-single:
run-single:
Sampling 100000000 random floating point numbers.
Time taken for fast: 415.36368
Time taken for slow (java): 1530.294
Sampling 100000000 random floating point numbers.
Time taken for fast: 404.29938
Time taken for slow (java): 1530.1299
Sampling 100000000 random floating point numbers.
Time taken for fast: 402.24176
Time taken for slow (java): 1524.5559
BUILD SUCCESSFUL (total time: 6 seconds)

Sampling 10000000 random numbers in [0,1].
Number of partitions: 10
Using fast generator
Partition 1: 0.0999716
Partition 2: 0.0999375
Partition 3: 0.1001207
Partition 4: 0.099938
Partition 5: 0.0998954
Partition 6: 0.1001462
Partition 7: 0.1000686
Partition 8: 0.1000338
Partition 9: 0.1000256
Partition 10: 0.0998626
Max deviation: 1.3740361E-4

Sampling 10000000 random numbers in [0,1].
Number of partitions: 10
Using standard generator (java)
Partition 1: 0.1001091
Partition 2: 0.0999581
Partition 3: 0.099842
Partition 4: 0.0997741
Partition 5: 0.099973
Partition 6: 0.1000415
Partition 7: 0.1000817
Partition 8: 0.0999945
Partition 9: 0.1000933
Partition 10: 0.1001327
Max deviation: 2.259016E-4


Speed is a lot higher with the XORshift generator, and precision is pretty much the same. The speed doesn't come from loss of precision. These tests are just confirmations that the implementation itself work, and that there are no noticable biases due to float precision etc. The values are pretty much as expected.

Here's a simple 64 bit generator, for the lazy.

[java]
public class Random {
protected long x;

public Random(){
x = System.nanoTime();
}

public long next()
{
x ^= (x << 21);
x ^= (x >>> 35);
x ^= (x << 4);
return x;
}
}
[/java]

There will be more stuff here. A 2d poisson disk sampling algorithm will be next, and it'll be added to the lib as well, but I'm gonna have to test it more to make sure there are no bugs.
2

Yes, one of the things high on my todo-list was a 2d poisson disk sampling algorithm for distribution of cruft on the terrain, now I’ll wait for your implementation and save myself the trouble :wink:



The XOR-thingy I implemented a while ago and ran some tests. If you need to synchronize access to it the speed difference between that and a java Math.Random was almost nothing (i.e. almost as fast/slow). I was very surprised that synchronizing in this day and age (JDK7) cost me that much (might be an artifact of the test also).

So something to take in to consideration if you want to reuse the XORRandom across threads (like loading tiles in the background) but still get the ability to recreate a level from only a seed value.

3

One can use one generator per tile which are seeded by the tile coordinates multiplied by a master seed value. Hence no synchronization will be needed :slight_smile:

4

Yes, that is surely one way to take it into consideration and since there aren’t massive amounts of data in each generator that is viable :slight_smile:

5
@kwando said:
One can use one generator per tile which are seeded by the tile coordinates multiplied by a master seed value. Hence no synchronization will be needed :)


That sounds like what I'm doing. I had to assign a value to each world tile so that grass and stuff gets the same distribution when regenerated, so it kind of solved itself. I love that it's such a small class you can just pop one out wherever you need it.

The poisson disk sampler is a bit of a mess because I didn't code it from scratch, but it was part of some terrain generation "sketch" thing that I translated to jME. Anyways, I have to clean it up and find out where I got the thing so I can attribute it properly before adding. Shouldn't take too long, considering it's a small class.

Here's an image of a 200x200 grid with min distance 10. I recently added a validate method too (to check that the produced numbers actually satisfy the initial conditions), and also a method to dump an image like this. Everything seems to work. :D

http://www.jamtlandoutdoors.se/images/dist/PoissonDisk_200x200_min10.png
1 Like
6

@jmaasing

Interesting. Haven’t done any real comparisons with other generators except the default java myself. I guess the “smallness” of the class is the only thing separating it from LCG’s etc. It’s so easy to just use it everywhere without having to work with weird seeds and tables and stuff.

7

Min value 3 this time. still 200x200.



http://www.jamtlandoutdoors.se/images/dist/PoissonDisk_200x200_min_3.png

8

My current playground loop over the terrain quad with +10 on x and y, generate a random number and if it is smaller than the density map create a boulder or something (currently just placeholders). With the XOR rand and (even pre-calculated) poisson disk points I think it will be both fast and look good. The only thing lacking now is time to actually code the stuff :slight_smile:



I think maybe that is a good start to some general placement design. First find a set of sample points taken from the height map (poisson disk to find the height from terrain or whatever). Then filter them according to different strategies like removing points according to a densitymap, remove some more them if they are at the wrong height and so on. Maybe not the most efficient but pretty easy to understand and should lend itself to tools. Almost like the nodes in NeoTexture editor.

9

Added the PoissonDisk2D class to the lib now. Also cleaned up and added a 1D random Gaussian generator.



I woun’t post the code here as the classes will likely be updated in the future, and I don’t wanna go back and edit this post every time…

10

have you tested colt library random generators ? they may be better.



http://acs.lbl.gov/software/colt/api/index.html



look at cern.jet.random.engine

11

Found a nice article with source for Poisson disk sample but there is no license information I could find :frowning:

12

There’s a poisson disk sampler in the biomonkey lib. it made the images in the posts above.



I don’t want to include colt in this lib. It is large, and most of the stuff is not needed. Normal, Poisson disk and regular uniform distributions is enough, and I’m using a good generator and good algorithms for those.

13

This sounds good :slight_smile:



A fast random generator may be a good candidate for inclusion in the core…

14

This is the poisson disk sampler from BioMonkey. Been using it for a month or so, and validation + printed images suggests it’s working well. No guarantees tho.



[java]

import com.jme3.math.FastMath;

import com.jme3.math.Vector2f;

import java.awt.image.BufferedImage;

import java.awt.image.DataBufferByte;

import java.awt.image.WritableRaster;

import java.io.File;

import java.io.FileOutputStream;

import java.io.IOException;

import java.io.OutputStream;

import java.util.ArrayList;

import java.util.Collection;

import java.util.LinkedList;

import javax.imageio.ImageIO;

import se.jod.biomonkey.random.FastRandom;



/**

  • Poisson disk sampling for semi-random distributions. Adapted from
  • a similar class in this sketch:

    *
  • "http://www.openprocessing.org/sketch/30809"

    *
  • @author Andreas

    /

    public class PoissonDisk2D {



    /    * From "Fast Poisson Disk Sampling in Arbitrary Dimensions"
  • by Robert Bridson
  • http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

    **/

    protected ArrayList<Vec2List> grid;

    protected float cellSize;

    protected float minDist;

    protected int gridWidth, gridHeight;

    protected float xmin, xmax, ymin, ymax;

    protected Vec2List points;

    protected FastRandom rand;



    public PoissonDisk2D() {

    points = new Vec2List();

    rand = new FastRandom();

    }



    public Vec2List getPoints() {

    return points;

    }



    public Vec2List generate(float xmin, float ymin, float xmax, float ymax, float minDist, int rejectionLimit) {

    this.xmin = xmin;

    this.xmax = xmax;

    this.ymin = ymin;

    this.ymax = ymax;

    this.minDist = minDist;

    this.cellSize = minDist / FastMath.sqrt(2);

    this.gridWidth = (int) FastMath.ceil((xmax - xmin) / cellSize);

    this.gridHeight = (int) FastMath.ceil((ymax - ymin) / cellSize);

    int s = gridWidth * gridHeight;

    grid = new ArrayList<Vec2List>();



    for (int i = 0; i < s; i++) {

    grid.add(new Vec2List());

    }



    points.clear();

    LinkedList<Vector2f> processList = new LinkedList<Vector2f>();



    Vector2f p = new Vector2f(random(xmin, xmax), random(ymin, ymax));

    processList.add§;

    points.add§;

    addToGrid§;



    while (processList.size() > 0) {

    int i = (int) (random(processList.size()));

    p = processList.get(i);

    processList.remove(i);

    for (i = 0; i < rejectionLimit; i++) {

    Vector2f n = createRandomPointAround(p, minDist, minDist * 2);

    if (insideBoundaries(n) && testGrid(n, minDist)) {

    processList.add(n);

    points.add(n);

    addToGrid(n);

    }

    }

    }



    return points;

    }



    protected boolean insideBoundaries(Vector2f p) {

    return (p.x >= xmin && p.x < xmax && p.y >= ymin && p.y < ymax);

    }



    protected Vector2f createRandomPointAround(Vector2f p, float minDist, float maxDist) {

    float a = random(2 * FastMath.PI);

    float r = random(minDist, maxDist);

    return new Vector2f(p.x + r * FastMath.cos(a), p.y + r * FastMath.sin(a));

    }



    // return true if there are no points inside the circle of minDist radius around p

    protected boolean testGrid(Vector2f p, float minDist) {



    int minX = (int) FastMath.floor(max(0, (p.x - minDist - xmin) / cellSize));

    int maxX = (int) FastMath.ceil(min(gridWidth - 1, (p.x + minDist - xmin) / cellSize));

    int minY = (int) FastMath.floor(max(0, (p.y - minDist - ymin) / cellSize));

    int maxY = (int) FastMath.ceil(min(gridHeight - 1, (p.y + minDist - ymin) / cellSize));



    minDist *= minDist;



    for (int y = minY; y <= maxY; y++) {

    for (int x = minX; x <= maxX; x++) {

    Vec2List cell = grid.get(y * gridWidth + x);

    for (Vector2f t : cell) {

    if (t.distanceSquared§ <= minDist) {

    return false;

    }

    }

    }

    }



    return true;

    }



    protected void addToGrid(Vector2f p) {

    grid.get(index(p.x, p.y)).add§;

    }



    protected int index(float x, float y) {

    int gx = (int) FastMath.floor((x - xmin) / cellSize);

    int gy = (int) FastMath.floor((y - ymin) / cellSize);

    return gy * gridWidth + gx;

    }



    protected float random(float min, float max) {

    return min + rand.unitRandom() * (max - min);

    }



    protected float random(float f) {

    return rand.unitRandom() * f;

    }



    protected float min(float x, float y) {

    return (x < y) ? x : y;

    }



    protected float max(float x, float y) {

    return (x > y) ? x : y;

    }



    protected class Vec2List extends ArrayList<Vector2f>{



    public Vec2List(Collection<? extends Vector2f> c) {

    super©;

    }



    public Vec2List() {

    }



    public Vec2List(int initialCapacity) {

    super(initialCapacity);

    }



    }

    }

    [/java]



    The FastRandom class can be replaced with java random generator or w/e. It is only referenced in the two random(float f) and random(float min, float max) methods. Otherwise it will be available in BioMonkey (just as the poisson disk sampler).



    Here’s how to use:



    [java]

    public static void main(String[] args) {

    float xMin = 0, xMax = 10;

    float yMin = 0, yMax = 10;

    float minDist = 3;

    PoissonDisk2D pd = new PoissonDisk2D();

    // 30 is a good rejection limit value.

    pd.generate(xMin, yMin, xMax, yMax, minDist, 30);

    }

    [/java]
1 Like
15

Speaking of random number generation, I found that a long while ago, I don’t remember where, but it’s a random generator for GLSL.



I have no idea how fast it is though. But, if someone would like to test it, you technically could paint x number of pixels and manually count the time it took. Very dirty, I know, but result could be interesting.



The formula is simple, admittedly, you couldn’t outsource it to a shader to get and use the result externally.



[java]float rand(vec2 co){

return fract(sin(dot(co.xy, vec2(12.9898,78.233))) * 43758.5453);

}[/java]