15
\$\begingroup\$

I am currently working on a program that should generate random noise on a screen based on the 'coordinates' of a pixel. The coordinates should have the same color every time you restart the program. However, using the Java's util.Random, the results I get are not as random as I'd like:

printscreen

I thought that if I used the combined coordinates (as in one integer formed from both coordinates next to eachother) each coordinate would have a different number. By using that number as a seed I expected to get a different random numbers for each coordinate to use for the rgb value of that coordinate.

This is the code I used:

public class Generate {

static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(Integer.valueOf(Integer.toString(x)+Integer.toString(y)));
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}

Is the pattern that the program creates due to the way java's Random function works or am I doing something wrong and should I try a different approach?

Update: I now tried to get rid of the problems surrounding concatenation by using the following code:

public static int TileColor(int x, int y){  
            Randomy = new Random(y);
            Randomx = new Random(x);
            Random = new Random(Integer.valueOf(Integer.toString(Randomx.nextInt(1234))+Integer.toString(Randomy.nextInt(1234))));
            int b = 1 + Random.nextInt(100);
            int g = 1 + Random.nextInt(100);
            int r = 1 + Random.nextInt(100);
            int color = -Color.rgb888(r, g, b);
            return color;
}

Somehow, this also provided a (in my opinion) sufficiently random image:

mew image

This code does however reseed three times per pixel. Even though this is not a problem for me right now, I do consider changing this code in case I need better preformance later on.

\$\endgroup\$
  • 3
    \$\begingroup\$ Not sure about Java's Random but i'm pretty sure its not real random... Read en.wikipedia.org/wiki/Pseudorandom_number_generator You'll understand why you see those patterns. \$\endgroup\$ – Salketer Oct 27 '16 at 14:29
  • 23
    \$\begingroup\$ Something crucial that’s missing from the other answers: don’t reseed the RNG for every pixel. Seed it once and generate consecutive values for all the pixels in your image based off that. \$\endgroup\$ – Konrad Rudolph Oct 27 '16 at 15:38
  • 4
    \$\begingroup\$ Note: a pseudorandom number generaot might be uniformely distributed in one dimension, but fail when using more than one dimension... you are effectively generating points in 3D (r,g and b and 3 different coordinates) so you need a random generator that guarantees not only that the values it generates are uniformely distributed, but also the triplets that it generates are uniformely distributed in the 3D space. \$\endgroup\$ – Bakuriu Oct 27 '16 at 16:21
  • 6
    \$\begingroup\$ @Bakuriu If X, Y and Z are independent uniform random variables, then I'm pretty sure (X, Y, Z) is uniform in 3d space. \$\endgroup\$ – Jack M Oct 27 '16 at 21:26
  • 2
    \$\begingroup\$ You could experiment with using different RNGs, like the Mersenne Twister. \$\endgroup\$ – Kevin Oct 28 '16 at 1:51

10 Answers 10

21
\$\begingroup\$

Java's java.util.Random class usually gives you sequences of pseudorandom numbers which are good enough for use in games1. However, that characteristic only applies to a sequence of multiple samples based on a seed. When you reinitialize the RNG with incrementing seed values and only look at the first value of each sequence, the randomness characteristics will not be nearly as good.

What you could do instead:

  • Use the same seed to generate whole chunks of pixels at a time. For example, when you need the color value of pixel 425:487, feed the coordinates 400:400 into the RNG, generate 10000 random colors and use the color at index 2587 (25 * 100 + 87). Chunks generated in that manner should be cached to avoid re-generating those 10000 random colors for every single pixel of that chunk.
  • Instead of using a random number generator, use a message digest function to turn a coordinate pair into a color value. The output of most MDF's is unpredictable enough to fulfill most tests of randomness. The output is usually more than the 24 bit you need for an RGB value, but truncating them is usually no problem.

    To improve performance you can combine message digest generation with chunks. Generate small chunks of pixels which are just large enough to use of the full length of one output of your digest function.

1 when it is absolutely essential that nobody can predict the next number, use the slower but less predictable java.security.SecureRandom

\$\endgroup\$
13
\$\begingroup\$

The coordinates should have the same color everyone you restart the program

In that case, you'll want to use a deterministic noise function such as Perlin noise or simplex noise.

(See this question for some more information on Perlin noise with some pretty pictures.)

For the most part, using a built-in random() or similar function will give you different values every time you run the program, as they may use the clock as an input or some other pseudorandom value.

Another option is to generate a "noise map" once, offline, and then use that as your random number source later on.

In your implementation, you're concatenating the string representations of x and y. That is bad as it's not unique across the domain. For instance,

x    y   concatenated
40   20  4020
402   0  4020
10   10  1010
101   0  1010
12   34  1234
123   4  1234
1   234  1234

Good luck!

\$\endgroup\$
  • 1
    \$\begingroup\$ Good point about the concatenated numbers. The program does however always give the exact same result if I run the program multiple times. I have considered perlin/simplex noise as well, might have a look into that and see if it works out better. I am however not yet sure why Java does create patterns, for the concatenation problem does not seem to solve it entirely \$\endgroup\$ – dragonfly Oct 27 '16 at 14:42
  • 1
    \$\begingroup\$ Is it not sufficient to simply seed Random with a constant seed value before generating the pixels? \$\endgroup\$ – Jack M Oct 27 '16 at 21:28
  • 1
    \$\begingroup\$ @JackM That depends entirely upon the PRNG algorithm in play. \$\endgroup\$ – 3Dave Oct 27 '16 at 21:29
  • 4
    \$\begingroup\$ "I once saw a rand() implementation that used each value as a seed for the next value." Isn't that how most non-cryptographic pseudorandom number generators work? They use the previous random number (or state) as input to generate the next random number/state. \$\endgroup\$ – JAB Oct 27 '16 at 21:44
  • 2
    \$\begingroup\$ @DavidLively Virtually all PRNGs do this or something equivalent, unless their internal state is larger than the range of numbers they generate (e.g. Mersenne twisters), and even then the sequence of random numbers is of course entirely determined by the seed. \$\endgroup\$ – Konrad Rudolph Oct 28 '16 at 6:53
9
\$\begingroup\$

Let's see what you are doing exactly:

  • You loop through all pixels one by one
  • For each pixel, you use the concatenation of its coordinates as a seed
  • You then start a new random from the given seed and take out 3 numbers

All this sounds alright, but you are receiving a pattern because:

Pixel at 1,11 and pixel at 11,1 are both seeded the number 111 so they are certain to have the same color.

Also, as long as you always cycle the same way, you can use only one generator, no need to use one for each pixel. One for the whole image will do! There are still going to be some sort of patterns because of pseudo-randomness. @David_Lively is right about using some Noise algorithm, it will make it look more random.

\$\endgroup\$
  • \$\begingroup\$ The thing is that the view of the image should be able to shift (further to positive coordinates). So this approach won't work completely \$\endgroup\$ – dragonfly Oct 27 '16 at 14:44
  • 4
    \$\begingroup\$ Actually “all this” doesn’t sound alright — reseeding a deterministic RNG for every pixel is a terrible strategy unless the seed itself is from a cryptographic RNG (and even then it’s a wonky strategy for reasons unrelated to distribution). \$\endgroup\$ – Konrad Rudolph Oct 27 '16 at 15:37
  • \$\begingroup\$ you might include the correct way of concatentating the numbers in this context. Ie. (x+y*width) \$\endgroup\$ – Taemyr Oct 28 '16 at 13:43
1
\$\begingroup\$

Make a color generator, then produce your colors for your tile. Seed only once! You don't need to seed more than that, at least per tile.

public class RandomColorGenerator {
  private final int minValue;
  private final int range;
  private final Random random;
  public RandomColorGenerator(int minValue, int maxValue, Random random) {
    if (minValue > maxValue || (long)maxValue - (long)minValue > (long)Integer.MAX_VALUE) {
      throw new IllegalArgumentException();
    }
    this.minValue = minValue;
    this.range = maxValue - minValue + 1;
    this.random = Objects.requireNonNull(random);
  }

  public int nextColor() {
    int r = minValue + random.nextInt(range);
    int g = minValue + random.nextInt(range);
    int b = minValue + random.nextInt(range);
    return -Color.rgb888(r, g, b);
  }
}

public class Tile {
  private final int[][] colors;
  public Tile(int width, int height, RandomColorGenerator colorGenerator) {
    this.colors = new int[width][height];
    for (int x = 0; x < width; x++) {
      for (int y = 0; y < height; y++) {
        this.colors[x][y] = colorGenerator.nextColor();
      }
    }
  }

  public int getColor(int x, int y) {
    return colors[x][y];
  }
}

And the usage will be like follow:

RandomColorGenerator generator = new RandomColorGenerator(1, 100, new Random(0xcafebabe));
Tile tile = new Tile(300, 200, generator);
...
// getting the color for x, y:
tile.getColor(x, y);

With this if you're not happy with the result just change Random seed. Also, you only have to store/communicate the seed and sizes so that all the clients have the same image.

\$\endgroup\$
1
\$\begingroup\$

Instead of using Random, considering using a hash digest like MD5. It provides a hard to predict 'random' value based on a certain input, but always the same value for the same input.

Example:

public static int TileColor(int x, int y){
        final MessageDigest md = MessageDigest.getInstance("MD5");
        final ByteBuffer b = ByteBuffer.allocate(8);
        b.putInt(x).putInt(y);
        final byte[] digest = md.digest(b.array());
        return -Color.rgb888(digest[0], digest[1], digest[2]);
}

NOTE: I Don't know where Color.rgb888(..) comes from, so I don't know what the allowed range is. 0-255 is normal though.

Improvements to consider:

  • Make MessageDigest and ByteBuffer variables outside of the class, to improve performance. You will need to reset the ByteBuffer to do that, and the method will no longer be Thread safe.
  • The digest array will contain byte values 0-255, if you want other ranges, you'll have to do some math on them.
  • If you want different 'random' results, you can add some kind of 'seed'. For example change to ByteBuffer.allocate(12), and add a .putInt(seed).
\$\endgroup\$
1
\$\begingroup\$

Others have pointed out that one way to get the behaviour you want is to use a hash function, aka "message digest function." The problem is that these are often based on algorithms like MD5, which is cryptographically secure (i.e. really, really, really random) but very slow. If you use a cryptographic hash function every time you need a random pixel you will run into quite severe performance issues.

However, there are non-cryptographic hash functions that can produce values that are random enough for your purpose while also being fast. The one I usually reach for is murmurhash. I'm not a Java user but it seems there is at least one Java implementation available. If you find that you really need to have each pixel be generated from its coordinates, rather than generating them all at once and storing them in a texture, then this would be a good way to do it.

\$\endgroup\$
1
\$\begingroup\$

I would use a prime over 2000 (max typical resolution)
This will minimize (or eliminate duplicate seeds)

public class Generate {

    static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(x + 2213 * y);
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}
\$\endgroup\$
0
\$\begingroup\$

Random is random enough. You're using it wrong for two main reasons.

  • It wasn't designed to be repeatedly re-seeded. The random properties only hold for a single sequence of random numbers.
  • There's huge correlation of Integer.valueOf(Integer.toString(x)+Integer.toString(y)) between pixels that you're seeding with.

I'd just use some variation of the following code, where you can pick a hash function (don't use Integer.getHashCode) from the answers at https://stackoverflow.com/questions/9624963/java-simplest-integer-hash

public static int TileColor(int x, int y) {
    return hash(x ^ hash(y));
}

where the hash function could be

\$\endgroup\$
0
\$\begingroup\$

You could try using the systems current clock time as a seed like this:

Random random = new Random(System.currentTimeMillis())

Hopefully it produces a more random value.

\$\endgroup\$
  • \$\begingroup\$ That does not create the dame value for the dame coordinate everytime, however. \$\endgroup\$ – dragonfly Oct 28 '16 at 23:01
0
\$\begingroup\$

Here is a one line static shader function I came up with - poltergeist (Noisy Ghost).

It takes a 2D coordinate and a seed, and renders in monotone as requested. It runs at realtime fps, regardless of screen resolution. This is what GPUs are for.

// poltergeist (noisy ghost) pseudo-random noise generator function
// dominic.cerisano@standard3d.com 03/24/2015

precision highp float;

float poltergeist(in vec2 coordinate, in float seed) 
{
    return fract(sin(dot(coordinate*seed, vec2(12.9898, 78.233)))*43758.5453); 
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) 
{   
    fragColor = vec4(poltergeist(fragCoord, iGlobalTime)); 
}

Any resolution, any texture, on any device (mobile too) supporting GL (which is pretty much any with a screen).

See it running here, right now!

https://www.shadertoy.com/view/ltB3zD

You can easily include this shader in your java program using standard opengl, or in any browser using standard webgl.

Just for fun, I throw down the gauntlet for anyone to beat Poltergeist in quality and performance on all devices. Noisy Ghost rules! Undefeated!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.