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}