001/* 002 * Trident - A Multithreaded Server Alternative 003 * Copyright 2014 The TridentSDK Team 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package net.tridentsdk.server.world.gen; 018 019import java.util.Random; 020 021/** 022 * Based on example code by Stefan Gustavson (stegu@itn.liu.se). 023 * Optimisations by Peter Eastman (peastman@drizzle.stanford.edu). 024 * Better rank ordering method by Stefan Gustavson in 2012. 025 * 026 * @author Stefan Gustavson 027 * @author Peter Eastman 028 * @author The TridentSDK Team 029 */ 030public class SimplexNoiseGenerator { // Simplex noise in 2D and 3D 031 private static final int NUMBER_OF_SWAPS = 400; 032 033 // Skewing and unskewing factors for 2, 3, and 4 dimensions 034 private static final double F2 = 0.5 * (Math.sqrt(3.0) - 1.0); 035 private static final double G2 = (3.0 - Math.sqrt(3.0)) / 6.0; 036 private static final double F3 = 1.0 / 3.0; 037 private static final double G3 = 1.0 / 6.0; 038 039 private static final Grad grad3[] = {new Grad(1, 1, 0), new Grad(-1, 1, 0), new Grad(1, -1, 0), new Grad(-1, -1, 0), 040 new Grad(1, 0, 1), new Grad(-1, 0, 1), new Grad(1, 0, -1), new Grad(-1, 0, -1), 041 new Grad(0, 1, 1), new Grad(0, -1, 1), new Grad(0, 1, -1), new Grad(0, -1, -1)}; 042 043 private static final short p_supply[] = {151, 160, 137, 91, 90, 15, //this contains all the numbers between 0 and 255, these are put in a random order depending upon the seed 044 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 045 190, 6, 148, 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 046 88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 047 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 048 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 049 135, 130, 116, 188, 159, 86, 164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 050 5, 202, 38, 147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 051 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 172, 9, 052 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 053 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145, 235, 249, 14, 239, 107, 054 49, 192, 214, 31, 181, 199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 055 138, 236, 205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180}; 056 057 private final short p[]; 058 059 // To remove the need for index wrapping, double the permutation table length 060 private final short perm[] = new short[512]; 061 private final short permMod12[] = new short[512]; 062 063 public SimplexNoiseGenerator() { 064 this(new Random().nextInt()); 065 } 066 067 public SimplexNoiseGenerator(int seed) { 068 p = p_supply.clone(); 069 070 //the random for the swaps 071 Random rand = new Random(seed); 072 073 //the seed determines the swaps that occur between the default order and the order we're actually going to use 074 for (int i = 0; i < NUMBER_OF_SWAPS; i++) { 075 int swapFrom = rand.nextInt(p.length); 076 int swapTo = rand.nextInt(p.length); 077 078 short temp = p[swapFrom]; 079 p[swapFrom] = p[swapTo]; 080 p[swapTo] = temp; 081 } 082 083 // make a copy of the p array twice, so that we don't need to index wrap 084 for (int i = 0; i < 512; i++) { 085 perm[i] = p[i & 255]; 086 permMod12[i] = (short) (perm[i] % 12); 087 } 088 } 089 090 091 // This method is a *lot* faster than using (int)Math.floor(x) 092 private static int fastfloor(double x) { 093 int xi = (int) x; 094 return x < xi ? xi - 1 : xi; 095 } 096 097 private static double dot(Grad g, double x, double y) { 098 return g.x * x + g.y * y; 099 } 100 101 private static double dot(Grad g, double x, double y, double z) { 102 return g.x * x + g.y * y + g.z * z; 103 } 104 105 // 2D simplex noise 106 public double noise(double xin, double yin) { 107 double n0, n1, n2; // Noise contributions from the three corners 108 // Skew the input space to determine which simplex cell we're in 109 double s = (xin + yin) * F2; // Hairy factor for 2D 110 int i = fastfloor(xin + s); 111 int j = fastfloor(yin + s); 112 double t = (i + j) * G2; 113 double X0 = i - t; // Unskew the cell origin back to (x,y) space 114 double Y0 = j - t; 115 double x0 = xin - X0; // The x,y distances from the cell origin 116 double y0 = yin - Y0; 117 // For the 2D case, the simplex shape is an equilateral triangle. 118 // Determine which simplex we are in. 119 int i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords 120 if (x0 > y0) { 121 i1 = 1; 122 j1 = 0; 123 } // lower triangle, XY order: (0,0)->(1,0)->(1,1) 124 else { 125 i1 = 0; 126 j1 = 1; 127 } // upper triangle, YX order: (0,0)->(0,1)->(1,1) 128 // A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and 129 // a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where 130 // c = (3-sqrt(3))/6 131 double x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords 132 double y1 = y0 - j1 + G2; 133 double x2 = x0 - 1.0 + 2.0 * G2; // Offsets for last corner in (x,y) unskewed coords 134 double y2 = y0 - 1.0 + 2.0 * G2; 135 // Work out the hashed gradient indices of the three simplex corners 136 int ii = i & 255; 137 int jj = j & 255; 138 int gi0 = permMod12[ii + perm[jj]]; 139 int gi1 = permMod12[ii + i1 + perm[jj + j1]]; 140 int gi2 = permMod12[ii + 1 + perm[jj + 1]]; 141 // Calculate the contribution from the three corners 142 double t0 = 0.5 - x0 * x0 - y0 * y0; 143 if (t0 < 0) n0 = 0.0; 144 else { 145 t0 *= t0; 146 n0 = t0 * t0 * dot(grad3[gi0], x0, y0); // (x,y) of grad3 used for 2D gradient 147 } 148 double t1 = 0.5 - x1 * x1 - y1 * y1; 149 if (t1 < 0) n1 = 0.0; 150 else { 151 t1 *= t1; 152 n1 = t1 * t1 * dot(grad3[gi1], x1, y1); 153 } 154 double t2 = 0.5 - x2 * x2 - y2 * y2; 155 if (t2 < 0) n2 = 0.0; 156 else { 157 t2 *= t2; 158 n2 = t2 * t2 * dot(grad3[gi2], x2, y2); 159 } 160 // Add contributions from each corner to get the final noise value. 161 // The result is scaled to return values in the interval [-1,1]. 162 return 70.0 * (n0 + n1 + n2); 163 } 164 165 166 // 3D simplex noise 167 public double noise(double xin, double yin, double zin) { 168 double n0, n1, n2, n3; // Noise contributions from the four corners 169 // Skew the input space to determine which simplex cell we're in 170 double s = (xin + yin + zin) * F3; // Very nice and simple skew factor for 3D 171 int i = fastfloor(xin + s); 172 int j = fastfloor(yin + s); 173 int k = fastfloor(zin + s); 174 double t = (i + j + k) * G3; 175 double X0 = i - t; // Unskew the cell origin back to (x,y,z) space 176 double Y0 = j - t; 177 double Z0 = k - t; 178 double x0 = xin - X0; // The x,y,z distances from the cell origin 179 double y0 = yin - Y0; 180 double z0 = zin - Z0; 181 // For the 3D case, the simplex shape is a slightly irregular tetrahedron. 182 // Determine which simplex we are in. 183 int i1, j1, k1; // Offsets for second corner of simplex in (i,j,k) coords 184 int i2, j2, k2; // Offsets for third corner of simplex in (i,j,k) coords 185 if (x0 >= y0) { 186 if (y0 >= z0) { 187 i1 = 1; 188 j1 = 0; 189 k1 = 0; 190 i2 = 1; 191 j2 = 1; 192 k2 = 0; 193 } // X Y Z order 194 else if (x0 >= z0) { 195 i1 = 1; 196 j1 = 0; 197 k1 = 0; 198 i2 = 1; 199 j2 = 0; 200 k2 = 1; 201 } // X Z Y order 202 else { 203 i1 = 0; 204 j1 = 0; 205 k1 = 1; 206 i2 = 1; 207 j2 = 0; 208 k2 = 1; 209 } // Z X Y order 210 } else { // x0<y0 211 if (y0 < z0) { 212 i1 = 0; 213 j1 = 0; 214 k1 = 1; 215 i2 = 0; 216 j2 = 1; 217 k2 = 1; 218 } // Z Y X order 219 else if (x0 < z0) { 220 i1 = 0; 221 j1 = 1; 222 k1 = 0; 223 i2 = 0; 224 j2 = 1; 225 k2 = 1; 226 } // Y Z X order 227 else { 228 i1 = 0; 229 j1 = 1; 230 k1 = 0; 231 i2 = 1; 232 j2 = 1; 233 k2 = 0; 234 } // Y X Z order 235 } 236 // A step of (1,0,0) in (i,j,k) means a step of (1-c,-c,-c) in (x,y,z), 237 // a step of (0,1,0) in (i,j,k) means a step of (-c,1-c,-c) in (x,y,z), and 238 // a step of (0,0,1) in (i,j,k) means a step of (-c,-c,1-c) in (x,y,z), where 239 // c = 1/6. 240 double x1 = x0 - i1 + G3; // Offsets for second corner in (x,y,z) coords 241 double y1 = y0 - j1 + G3; 242 double z1 = z0 - k1 + G3; 243 double x2 = x0 - i2 + 2.0 * G3; // Offsets for third corner in (x,y,z) coords 244 double y2 = y0 - j2 + 2.0 * G3; 245 double z2 = z0 - k2 + 2.0 * G3; 246 double x3 = x0 - 1.0 + 3.0 * G3; // Offsets for last corner in (x,y,z) coords 247 double y3 = y0 - 1.0 + 3.0 * G3; 248 double z3 = z0 - 1.0 + 3.0 * G3; 249 // Work out the hashed gradient indices of the four simplex corners 250 int ii = i & 255; 251 int jj = j & 255; 252 int kk = k & 255; 253 int gi0 = permMod12[ii + perm[jj + perm[kk]]]; 254 int gi1 = permMod12[ii + i1 + perm[jj + j1 + perm[kk + k1]]]; 255 int gi2 = permMod12[ii + i2 + perm[jj + j2 + perm[kk + k2]]]; 256 int gi3 = permMod12[ii + 1 + perm[jj + 1 + perm[kk + 1]]]; 257 // Calculate the contribution from the four corners 258 double t0 = 0.6 - x0 * x0 - y0 * y0 - z0 * z0; 259 if (t0 < 0) n0 = 0.0; 260 else { 261 t0 *= t0; 262 n0 = t0 * t0 * dot(grad3[gi0], x0, y0, z0); 263 } 264 double t1 = 0.6 - x1 * x1 - y1 * y1 - z1 * z1; 265 if (t1 < 0) n1 = 0.0; 266 else { 267 t1 *= t1; 268 n1 = t1 * t1 * dot(grad3[gi1], x1, y1, z1); 269 } 270 double t2 = 0.6 - x2 * x2 - y2 * y2 - z2 * z2; 271 if (t2 < 0) n2 = 0.0; 272 else { 273 t2 *= t2; 274 n2 = t2 * t2 * dot(grad3[gi2], x2, y2, z2); 275 } 276 double t3 = 0.6 - x3 * x3 - y3 * y3 - z3 * z3; 277 if (t3 < 0) n3 = 0.0; 278 else { 279 t3 *= t3; 280 n3 = t3 * t3 * dot(grad3[gi3], x3, y3, z3); 281 } 282 // Add contributions from each corner to get the final noise value. 283 // The result is scaled to stay just inside [-1,1] 284 return 32.0 * (n0 + n1 + n2 + n3); 285 } 286 287 private static class Grad { 288 final double x; 289 final double y; 290 final double z; 291 292 Grad(double x, double y, double z) { 293 this.x = x; 294 this.y = y; 295 this.z = z; 296 } 297 } 298}