[WGEN] Voronoi Noise

Discussion in 'Resources' started by mncat77, Jul 20, 2013.

Thread Status:
Not open for further replies.
  1. Preamble
    This thread is inspired by Hoolean 's Big World Generator Challenge and specifically to jtjj222 's post.
    Also in order to understand this thread, you should know, how ChunkGenerators work and what noises are. If you don't know these things I suggest you to read through jtjj222 's always up-to-date definitive guide to terrain generation.

    Voronoi Diagram
    Now that you know what a noise is, how to use it and I feel like I have promoted enough threads, let's get to the voronoi noise.
    Voronoi is used to divide an area into lots of polygons, based on points and their location in that area.
    You can use Fortune's algorithm to create a Voronoi Diagram from a set of points in a plane.
    Here is an example of how a Voronoi Diagram of a random set of points looks like:
    [​IMG]

    The Noise
    So now that we know, how to create a Voronoi Diagram from a random set of points, how do we make a noise out of that?
    We are going to use the distance to the reference point of the polygon we are currently in.
    We can create lots of diffrent looking noises now using multiple octave or diffrences (horizontal in the image below) and diffrent distance methods (vertical in the image below):
    View attachment 14361
    Key:
    First to Fourth = Distance to the nearest point to distance to the 4. nearest point (little correction here)
    Difference21 = Second - Third
    Difference32 = Third - Second
    Crackle = Math.max(1.0, 10*Difference21);

    Length = Math.sqrt(x*x+y*y+z*z) - Euclidean (shortest line). Square Root may be slow for some applications.
    Length2 = x*x+y*y+z*z - Saves the slow Square Root for some calculations.
    Manhatten = x+z
    Chebychev = Math.max(x,z);
    Quadratic = (x*x+y*y+z*z+x*y+x*z+y*z)
    Minkowski4 = Math.pow(x*x*x*x+y*y*y*y+z*z*z*z,0.25);
    Source: LumpyLumpy

    Implementation in Java
    And finally, here is an implemetation of the Voronoi noise in java, based on libnoiseforjava.
    Code:java
    1. import java.util.Random;
    2.  
    3. public class VoronoiGenerator {
    4.  
    5. private static final double SQRT_2 = 1.4142135623730950488;
    6. private static final double SQRT_3 = 1.7320508075688772935;
    7.  
    8. private long seed;
    9. private short distanceMethod;
    10.  
    11.  
    12. public VoronoiGenerator(long seed, short distanceMethod /*TODO: int octaves*/) {
    13. this.seed = seed;
    14. this.distanceMethod = distanceMethod;
    15. }
    16.  
    17. private double getDistance(double xDist, double zDist) {
    18. switch(distanceMethod) {
    19. case 0:
    20. return Math.sqrt(xDist * xDist + zDist * zDist) / SQRT_2;
    21. case 1:
    22. return xDist + zDist;
    23. case 2:
    24. return Math.pow(Math.E, Math.sqrt(xDist * xDist + zDist * zDist) / SQRT_2)/Math.E;
    25. default:
    26. return 1.0;
    27. }
    28. }
    29.  
    30. private double getDistance(double xDist, double yDist, double zDist) {
    31. switch(distanceMethod) {
    32. case 0:
    33. return Math.sqrt(xDist * xDist + yDist * yDist + zDist * zDist) / SQRT_3;
    34. case 1:
    35. return xDist + yDist + zDist;
    36. default:
    37. return 1.0;
    38. }
    39. }
    40.  
    41. public short getDistanceMethod() {
    42. return distanceMethod;
    43. }
    44.  
    45. public long getSeed() {
    46. return seed;
    47. }
    48.  
    49. public double noise(double x, double z, double frequency) {
    50. x *= frequency;
    51. z *= frequency;
    52.  
    53. int xInt = (x > .0? (int)x: (int)x - 1);
    54. int zInt = (z > .0? (int)z: (int)z - 1);
    55.  
    56. double minDist = 32000000.0;
    57.  
    58. double xCandidate = 0;
    59. double zCandidate = 0;
    60.  
    61. for(int zCur = zInt - 2; zCur <= zInt + 2; zCur++) {
    62. for(int xCur = xInt - 2; xCur <= xInt + 2; xCur++) {
    63.  
    64. double xPos = xCur + valueNoise2D(xCur, zCur, seed);
    65. double zPos = zCur + valueNoise2D(xCur, zCur, new Random(seed).nextLong());
    66. double xDist = xPos - x;
    67. double zDist = zPos - z;
    68. double dist = xDist * xDist + zDist * zDist;
    69.  
    70. if(dist < minDist) {
    71. minDist = dist;
    72. xCandidate = xPos;
    73. zCandidate = zPos;
    74. }
    75. }
    76. }
    77.  
    78. double xDist = xCandidate - x;
    79. double zDist = zCandidate - z;
    80.  
    81. return getDistance(xDist, zDist);
    82. }
    83.  
    84. public double noise(double x, double y, double z, double frequency) {
    85. x *= frequency;
    86. y *= frequency;
    87. z *= frequency;
    88.  
    89. int xInt = (x > .0? (int)x: (int)x - 1);
    90. int yInt = (y > .0? (int)y: (int)y - 1);
    91. int zInt = (z > .0? (int)z: (int)z - 1);
    92.  
    93. double minDist = 32000000.0;
    94.  
    95. double xCandidate = 0;
    96. double yCandidate = 0;
    97. double zCandidate = 0;
    98.  
    99. Random rand = new Random(seed);
    100.  
    101. for(int zCur = zInt - 2; zCur <= zInt + 2; zCur++) {
    102. for(int yCur = yInt - 2; yCur <= yInt + 2; yCur++) {
    103. for(int xCur = xInt - 2; xCur <= xInt + 2; xCur++) {
    104.  
    105. double xPos = xCur + valueNoise3D (xCur, yCur, zCur, seed);
    106. double yPos = yCur + valueNoise3D (xCur, yCur, zCur, rand.nextLong());
    107. double zPos = zCur + valueNoise3D (xCur, yCur, zCur, rand.nextLong());
    108. double xDist = xPos - x;
    109. double yDist = yPos - y;
    110. double zDist = zPos - z;
    111. double dist = xDist * xDist + yDist * yDist + zDist * zDist;
    112.  
    113. if(dist < minDist) {
    114. minDist = dist;
    115. xCandidate = xPos;
    116. yCandidate = yPos;
    117. zCandidate = zPos;
    118. }
    119. }
    120. }
    121. }
    122.  
    123. double xDist = xCandidate - x;
    124. double yDist = yCandidate - y;
    125. double zDist = zCandidate - z;
    126.  
    127. return getDistance(xDist, yDist, zDist);
    128. }
    129.  
    130. public void setDistanceMethod(short distanceMethod) {
    131. this.distanceMethod = distanceMethod;
    132. }
    133.  
    134. public void setSeed(long seed) {
    135. this.seed = seed;
    136. }
    137.  
    138. public static double valueNoise2D (int x, int z, long seed) {
    139. long n = (1619 * x + 6971 * z + 1013 * seed) & 0x7fffffff;
    140. n = (n >> 13) ^ n;
    141. return 1.0 - ((double)((n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff) / 1073741824.0);
    142. }
    143.  
    144. public static double valueNoise3D (int x, int y, int z, long seed) {
    145. long n = (1619 * x + 31337 * y + 6971 * z + 1013 * seed) & 0x7fffffff;
    146. n = (n >> 13) ^ n;
    147. return 1.0 - ((double)((n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff) / 1073741824.0);
    148. }
    149.  
    150. }


    Images of this in action
    Show Spoiler
    [​IMG][​IMG][​IMG][​IMG]



    Thanks again to jtjj222 for helping me a lot with this topic.
     
    _DSH105_, Miro, Burnett1 and 4 others like this.
  2. Offline

    jtjj222

    For anyone who wants to learn more about how the noise is generated, take a look at http://aftbit.com/cell-noise-2/. Some practical examples of how to use this in your terrain generator will be coming up, and I plan to include this in the Always up-to-date definitive guide to terrain generation, it that's all right with mncat77
     
    mncat77 likes this.
  3. Offline

    Miro

    I'd really want a source to see this in action.. it confuses me.. How would i apply Difference21 to my chunkgenerator, from what i see, all i can change is the distance method. Anyways, nice job!
     
  4. Thanks, some images of this in action can be found in the spoiler, also for Diffrence21 in action: this and the noise method to do that (the picture sets the block up or down with the condition that the Diffrence21 is <0.1 with 2 noises with diffrent frequencies) :
    Code:java
    1. public double noise(double x, double z, double frequency) {
    2. x *= frequency;
    3. z *= frequency;
    4.  
    5. int xInt = (x > .0? (int)x: (int)x - 1);
    6. int zInt = (z > .0? (int)z: (int)z - 1);
    7.  
    8. double minDist = 32000000.0;
    9.  
    10. double xCandidate1 = 0;
    11. double zCandidate1 = 0;
    12. double xCandidate2 = 0;
    13. double zCandidate2 = 0;
    14.  
    15. for(int zCur = zInt - 2; zCur <= zInt + 2; zCur++) {
    16. for(int xCur = xInt - 2; xCur <= xInt + 2; xCur++) {
    17.  
    18. double xPos = xCur + valueNoise2D(xCur, zCur, seed);
    19. double zPos = zCur + valueNoise2D(xCur, zCur, new Random(seed).nextLong());
    20. double xDist = xPos - x;
    21. double zDist = zPos - z;
    22. double dist = xDist*xDist+zDist*zDist;
    23.  
    24. if(dist < minDist) {
    25. xCandidate2 = xCandidate1;
    26. zCandidate2 = zCandidate1;
    27. xCandidate1 = xPos;
    28. zCandidate1 = zPos;
    29. minDist = dist;
    30. }
    31. }
    32. }
    33.  
    34. return getDistance(xCandidate2 - x, zCandidate2 - z) - getDistance(xCandidate1 - x, zCandidate1 - z);
    35. }
     
    Miro likes this.
  5. Offline

    Miro

    Ah, Thanks!!
    It'd be awesome if i could see the generateBlockSections aswell, since i can't seem to get that right
     
  6. If you use the 2D version you make a for(int x=0; x<16; x++) {for(int z=0; z<16; z++) { /**/ }} loop and in that loop you multiply the value you get from the noisefunction with chunkX*16+x, chunkZ*16+z and use it as altitude, for 3d you add a y loop and use the return value of the noise method as density/material. If thats not enough read more up in the above mentioned always up-to-date definitive guide to terrain generation.
     
    Miro likes this.
  7. Offline

    Miro


    I now get this:
    [​IMG]
    with this code:
    Code:java
    1.  
    2. VoronoiGenerator gen1 = new VoronoiGenerator(world.getSeed(), (short) 0);
    3.  
    4.  
    5. for (int x=0; x<16; x++) {
    6. for (int z=0; z<16; z++) {
    7.  
    8. int realX = x + ChunkX * 16; //used so that the noise function gives us
    9. int realZ = z + ChunkZ * 16; //different values each chunk
    10. double frequency = 0.1; // the reciprocal of the distance between points
    11. int multitude = 10; //how much we multiply the value between -1 and 1. It will determine how "steep" the hills will be.
    12. int sea_level = 64;
    13.  
    14. double maxHeight = gen1.noise(realX, realZ, frequency) * multitude + sea_level;
    15. for (int y=0;y<maxHeight;y++) {
    16. setBlock(x,y,z,chunk,Material.STONE); //set the current block to stone
    17. }
    18. }
    19. }

    but how would i re-create the "hills" and patterns on the screenshot? (Sorry, I'm probally being a noob, but I really appreciate that you are trying to help me)
     
  8. The first image was made with a much smaller frequency with just 1 - the first (not Diffrence21 or anything) second one about with your frequency. The last image is actually a Voronoi noise combined with a simplex noise put on an exponential scale, so the voronoi creates hills that go really high up and almost cancels out the simplex there and the simplex creates a smooth ground almost cancelling out the Voronoi.
    Edit:
    For the last image:
    Code:java
    1.  
    2.  
    3. private SimplexOctaveGenerator simplex;
    4. private VoronoiGenerator voronoi;
    5.  
    6. public double noise(double x, double z, double frequency, double amplitude, double frequency2) {
    7. double v = voronoi.noise(x, z, frequency2);
    8. double s = (simplex.noise(x, z, frequency, amplitude)+1)/2;
    9. double p = Math.pow(v, Math.E);
    10. return (p*v + (1-p) * s)/2;
    11. }
     
    Miro likes this.
  9. Offline

    Miro

    thanks for all your help! i ended up getting this: [​IMG]

    with this code:
    Code:java
    1.  
    2. VoronoiGenerator gen1 = new VoronoiGenerator(world.getSeed(), (short) 0);
    3.  
    4. for (int x=0; x<16; x++) {
    5. for (int z=0; z<16; z++) {
    6.  
    7. int realX = x + ChunkX * 16; //used so that the noise function gives us
    8. int realZ = z + ChunkZ * 16; //different values each chunk
    9. double frequency = 0.02; // the reciprocal of the distance between points
    10. int multitude = 8; //how much we multiply the value between -1 and 1. It will determine how "steep" the hills will be.
    11. int sea_level = 38;
    12.  
    13. double noise = gen1.noise(realX, realZ, frequency);
    14. double finalnoise = noise * multitude + sea_level;
    15.  
    16. if(noise > 0.3){
    17. for (int y=0;y<finalnoise;y++) {
    18. setBlock(x,y,z,chunk,Material.STONE); //set the current block to stone
    19. }
    20. }else{
    21. for (int y=0;y<sea_level;y++) {
    22. setBlock(x,y,z,chunk,Material.LAVA); //set the current block to stone
    23. }
    24. }
    25. }
    26. }
     
Thread Status:
Not open for further replies.

Share This Page