001package squidpony.squidmath; 002 003/** 004 * A technique for producing organic-seeming patterns via iterative processing of random values (reaction-diffusion). 005 * The fundamental basis for why this looks organic should be credited to Alan Turing, but the specific algorithm should 006 * be credited to <a href="http://www.jonathanmccabe.com/Cyclic_Symmetric_Multi-Scale_Turing_Patterns.pdf">Jonathan 007 * McCabe</a>, who has produced significant expansions on the scope the original Turing work covered; you can see 008 * <a href=https://www.flickr.com/photos/jonathanmccabe/sets>various examples of art he produced using this and related 009 * techniques</a>. 010 * <br> 011 * This class tries to provide a fairly raw API so different adjustments can be made on top of it. 012 * <br> 013 * Created by Tommy Ettinger on 4/27/2017. 014 */ 015public class TuringPattern { 016 private static final double fraction = 0x1p-53; 017 018 /** 019 * Initializes a substance array that can be given to other static methods. Uses very little 64-bit math, 020 * making it ideal for GWT. 021 * @param width the width of the substance array; should be consistent throughout calls 022 * @param height the height of the substance array; should be consistent throughout calls 023 * @return a 1D double array that represents a 2D array with random contents; should be given to other methods 024 */ 025 public static double[] initialize(int width, int height){ 026 return initializeInto(new double[width * height]); 027 } 028 029 /** 030 * Refills a substance array that can be given to other static methods. Uses very little 64-bit math, 031 * making it ideal for GWT. 032 * @param substance a 1D double array that will be modified and filled with random values 033 * @return substance, after modification; should be given to other methods 034 */ 035 public static double[] initializeInto(double[] substance){ 036 if(substance == null) return null; 037 long seed = 65537; 038 for (int i = 0; i < substance.length; i++) { 039 substance[i] = (DiverRNG.determine(++seed) >> 11) * fraction; 040 } 041 return substance; 042 } 043 /** 044 * Initializes a substance array that can be given to other static methods. 045 * @param width the width of the substance array; should be consistent throughout calls 046 * @param height the height of the substance array; should be consistent throughout calls 047 * @param seed the long seed to use for the random contents 048 * @return a 1D double array that represents a 2D array with random contents; should be given to other methods 049 */ 050 public static double[] initialize(int width, int height, long seed){ 051 return initializeInto(new double[width * height], seed); 052 } 053 054 /** 055 * Refills a substance array that can be given to other static methods. 056 * @param substance a 1D double array that will be modified and filled with random values 057 * @param seed the long seed to use for the random contents 058 * @return substance, after modification; should be given to other methods 059 */ 060 public static double[] initializeInto(double[] substance, long seed){ 061 if(substance == null) return null; 062 for (int i = 0; i < substance.length; i++) { 063 substance[i] = (DiverRNG.determine(++seed) >> 11) * fraction; 064 } 065 return substance; 066 } 067 068 /** 069 * Initializes a substance array that can be given to other static methods. Uses an RNG to produce long values that 070 * this turns into doubles in the desired range (that is, -1.0 to 1.0). 071 * @param width the width of the substance array; should be consistent throughout calls 072 * @param height the height of the substance array; should be consistent throughout calls 073 * @param rng the random number generator responsible for producing random double values 074 * @return a 1D double array that represents a 2D array with random contents; should be given to other methods 075 */ 076 public static double[] initialize(int width, int height, IRNG rng) { 077 return initializeInto(new double[width * height], rng); 078 } 079 /** 080 * Initializes a substance array that can be given to other static methods. Uses an RNG to produce long values that 081 * this turns into doubles in the desired range (that is, -1.0 to 1.0). 082 * @param substance a 1D double array that will be modified and filled with random values 083 * @param rng the random number generator responsible for producing random double values 084 * @return a 1D double array that represents a 2D array with random contents; should be given to other methods 085 */ 086 public static double[] initializeInto(double[] substance, IRNG rng){ 087 if(substance == null || rng == null) return null; 088 for (int i = 0; i < substance.length; i++) { 089 substance[i] = rng.nextDouble(2.0) - 1.0; 090 } 091 return substance; 092 } 093 094 /** 095 * Initializes a substance array that can be given to other static methods. Uses a Noise2D instance (it may or may 096 * not use the given seed) to produce values between -1.0 and 1.0. 097 * @param width the width of the substance array; should be consistent throughout calls 098 * @param height the height of the substance array; should be consistent throughout calls 099 * @param noise a Noise.Noise2D instance, such as {@link SeededNoise#instance} 100 * @param seed the seed to use with the noise generator 101 * @return a 1D double array that represents a 2D array with random contents; should be given to other methods 102 */ 103 public static double[] initialize(int width, int height, Noise.Noise2D noise, long seed) { 104 return initializeInto(new double[width * height], width, height, noise, seed); 105 } 106 /** 107 * Initializes a substance array that can be given to other static methods. Uses a Noise2D instance (it may or may 108 * not use the given seed) to produce values between -1.0 and 1.0. 109 * @param width the width of the substance array; should be consistent throughout calls 110 * @param height the height of the substance array; should be consistent throughout calls 111 * @param noise a Noise.Noise2D instance, such as {@link SeededNoise#instance} 112 * @param seed the seed to use with the noise generator 113 * @return a 1D double array that represents a 2D array with random contents; should be given to other methods 114 */ 115 public static double[] initializeInto(double[] substance, int width, int height, Noise.Noise2D noise, long seed){ 116 if(substance == null || noise == null) return null; 117 int i = 0; 118 for (int x = 0; x < width; x++) { 119 for (int y = 0; y < height; y++) { 120 substance[i++] = noise.getNoiseWithSeed(x, y, seed); 121 } 122 } 123 return substance; 124 } 125 126 /** 127 * Modifies the data parameter so no value in it is outside the range -1.0 inclusive to 1.0 exclusive. Makes no 128 * guarantees about the values this puts in data beyond that they will be inside that range. Has undefined results 129 * if any values in data are NaN or are infinite, though it probably will still work. If all values in data are 130 * already in the range, this will still change them, though probably not beyond recognition. Does not return a 131 * value because the changes are applied to data in-place. 132 * @param data a double array that will be modified in-place so all values in it will be between -1.0 and 1.0 133 */ 134 public static void refit(final double[] data) 135 { 136 if(data == null) return; 137 for (int i = 0; i < data.length; i++) { 138 data[i] = NumberTools.bounce(data[i] + 5); 139 } 140 } 141 142 /** 143 * Given an offset information array that has been modified and should be returned to its unmodified state, this 144 * uses the given width, height, and radius (which should be the same as what this was originally constructed with) 145 * to modify offsets in-place as if it was freshly-made, even if the array is final. 146 * @param offsets an offset information array that should have been produced by {@link #offsetsCircle(int, int, double)} and may have been distorted 147 * @param width the width of the substance array; should be consistent throughout calls 148 * @param height the height of the substance array; should be consistent throughout calls 149 * @param radius the radius of the circle to 150 * @return an offset information array, as a jagged 2D int array, that can be passed to {@link #step(double[], int[][], double, int[][], double)} 151 */ 152 public static int[][] offsetsCircleInto(final int[][] offsets, final int width, final int height, double radius) { 153 if (radius > width || radius > height) radius = Math.min(width, height); 154 radius = Math.max(1, radius); 155 IntVLA ivx = new IntVLA((int) (Math.PI * radius * (radius + 1))), 156 ivy = new IntVLA((int) (Math.PI * radius * (radius + 1))); 157 for (int x = 1; x <= radius; x++) { 158 for (int y = 1; y <= radius; y++) { 159 if (Math.sqrt(x * x + y * y) + 0.5 <= radius) { 160 ivx.add(x); 161 ivy.add(y); 162 } 163 } 164 } 165 int pointSize = (ivx.size + (int) radius - 1 << 2) + 1; 166 int[] bx = new int[pointSize], by = new int[pointSize]; 167 for (int i = 0; i < ivx.size; i++) { 168 int x = ivx.get(i), y = ivy.get(i); 169 bx[i << 2] = x; 170 by[i << 2] = y; 171 bx[i << 2 | 1] = -x; 172 by[i << 2 | 1] = y; 173 bx[i << 2 | 2] = -x; 174 by[i << 2 | 2] = -y; 175 bx[i << 2 | 3] = x; 176 by[i << 2 | 3] = -y; 177 } 178 for (int i = (ivx.size + 1 << 2), p = 1; i < pointSize - 3 && p <= radius + 0.5; i += 4, p++) { 179 bx[i] = p; 180 by[i] = 0; 181 bx[i | 1] = 0; 182 by[i | 1] = p; 183 bx[i | 2] = -p; 184 by[i | 2] = 0; 185 bx[i | 3] = 0; 186 by[i | 3] = -p; 187 } 188 bx[pointSize - 1] = 0; 189 by[pointSize - 1] = 0; 190 int[] vp; 191 int bxp, byp; 192 for (int p = 0; p < pointSize; p++) { 193 vp = offsets[p]; 194 bxp = bx[p]; 195 byp = by[p]; 196 for (int x = 0; x < width; x++) { 197 for (int y = 0; y < height; y++) { 198 vp[x * height + y] = ((x + bxp + width) % width) * height + ((y + byp + height) % height); 199 } 200 } 201 } 202 return offsets; 203 } 204 205 /** 206 * Pre-calculates the indices into a substance array that will need to be averaged per point in that array for an 207 * activator or inhibitor. The radius should usually (by convention) be smaller for an activator and larger for an 208 * inhibitor, but very large radii cause this to require significantly more time; consider a maximum of about 20, or 209 * less depending on how fast it needs to run vs. quality, and how many generations you expect. 210 * @param width the width of the substance array; should be consistent throughout calls 211 * @param height the height of the substance array; should be consistent throughout calls 212 * @param radius the radius of the circle to 213 * @return an offset information array, as a jagged 2D int array, that can be passed to {@link #step(double[], int[][], double, int[][], double)} 214 */ 215 public static int[][] offsetsCircle(int width, int height, double radius) 216 { 217 if(radius > width || radius > height) radius = Math.min(width, height); 218 radius = Math.max(1, radius); 219 IntVLA ivx = new IntVLA((int)(Math.PI * radius * (radius+1))), 220 ivy = new IntVLA((int)(Math.PI * radius * (radius+1))); 221 for (int x = 1; x <= radius; x++) { 222 for (int y = 1; y <= radius; y++) { 223 if(Math.sqrt(x * x + y * y) + 0.5 <= radius) 224 { 225 ivx.add(x); 226 ivy.add(y); 227 } 228 } 229 } 230 int pointSize = (ivx.size + (int)radius - 1 << 2) + 1; 231 int[] bx = new int[pointSize], by = new int[pointSize]; 232 for (int i = 0; i < ivx.size; i++) { 233 int x = ivx.get(i), y = ivy.get(i); 234 bx[i << 2] = x; 235 by[i << 2] = y; 236 bx[i << 2 | 1] = -x; 237 by[i << 2 | 1] = y; 238 bx[i << 2 | 2] = -x; 239 by[i << 2 | 2] = -y; 240 bx[i << 2 | 3] = x; 241 by[i << 2 | 3] = -y; 242 } 243 for (int i = (ivx.size + 1 << 2), p = 1; i < pointSize - 3 && p <= radius + 0.5; i+=4, p++) { 244 bx[i] = p; 245 by[i] = 0; 246 bx[i|1] = 0; 247 by[i|1] = p; 248 bx[i|2] = -p; 249 by[i|2] = 0; 250 bx[i|3] = 0; 251 by[i|3] = -p; 252 } 253 bx[pointSize-1] = 0; 254 by[pointSize-1] = 0; 255 int[][] val = new int[pointSize][width * height]; 256 int[] vp; 257 int bxp, byp; 258 for (int p = 0; p < pointSize; p++) { 259 vp = val[p]; 260 bxp = bx[p]; 261 byp = by[p]; 262 for (int x = 0; x < width; x++) { 263 for (int y = 0; y < height; y++) { 264 vp[x * height + y] = ((x + bxp + width) % width) * height + ((y + byp + height) % height); 265 } 266 } 267 } 268 return val; 269 } 270 271 /** 272 * Alters the given offset information (as a jagged 2D int array) with the given Noise2D instance and seed. This can 273 * change the quality of the pattern produced significantly, going from stripes to whorls and fungoid shapes. 274 * Modifies offsets in-place, and repeated calls can be a good way to alter the pattern this produces. 275 * @param offsets a jagged 2D int array as produced by {@link #offsetsCircle(int, int, double)}; will be modified! 276 * @param width the width of the full area that will be used by the TuringPattern 277 * @param height the height of the full area that will be used by the TuringPattern 278 * @param noise a Noise2D instance, such as {@link SeededNoise#instance}, that will be used to alter offsets 279 * @param seed a seed for the Noise2D 280 */ 281 public static void distort(int[][] offsets, int width, int height, Noise.Noise2D noise, long seed) 282 { 283 int pointSize = offsets.length; 284 int[] vp; 285 for (int x = 0; x < width; x++) { 286 for (int y = 0; y < height; y++) { 287 int pushX = (int)(2.5 * (noise.getNoiseWithSeed(x, y, seed) + 1)) - 2, 288 pushY = (int)(2.5 * (noise.getNoiseWithSeed(x, y, DiverRNG.determine(seed)) + 1)) - 2; 289 for (int p = 0; p < pointSize; p++) { 290 vp = offsets[p]; 291 int a = vp[x * height + y], px = a / height, py = a % height; 292 vp[x * height + y] = ((px + pushX + width) % width) * height + ((py + pushY + height) % height); 293 } 294 } 295 } 296 } 297 /** 298 * Alters the given offset information (as a jagged 2D int array) with the given Noise3D instance and seed, allowing 299 * a z position for the 3D component so this can change over time with changing z. This can method change the 300 * quality of the pattern produced significantly, going from stripes to whorls and fungoid shapes. 301 * Modifies offsets in-place, and repeated calls can be a good way to alter the pattern this produces. 302 * @param offsets a jagged 2D int array as produced by {@link #offsetsCircle(int, int, double)}; will be modified! 303 * @param width the width of the full area that will be used by the TuringPattern 304 * @param height the height of the full area that will be used by the TuringPattern 305 * @param noise a Noise3D instance, such as {@link SeededNoise#instance}, that will be used to alter offsets 306 * @param z a z position to be given to the Noise3D along with a point's x and y 307 * @param seed a seed for the Noise3D 308 */ 309 public static void distort(int[][] offsets, int width, int height, Noise.Noise3D noise, double z, long seed) 310 { 311 int pointSize = offsets.length; 312 int[] vp; 313 for (int x = 0; x < width; x++) { 314 for (int y = 0; y < height; y++) { 315 int pushX = (int)(2.5 * (noise.getNoiseWithSeed(x, y, z, seed) + 1)) - 2, 316 pushY = (int)(2.5 * (noise.getNoiseWithSeed(x, y, z, DiverRNG.determine(seed)) + 1)) - 2; 317 for (int p = 0; p < pointSize; p++) { 318 vp = offsets[p]; 319 int a = vp[x * height + y], px = a / height, py = a % height; 320 vp[x * height + y] = ((px + pushX + width) % width) * height + ((py + pushY + height) % height); 321 } 322 } 323 } 324 } 325 326 /** 327 * Brings together the other methods to advance the substance simulation by one step, modifying substance in-place. 328 * You should have generated substance with either one of the initialize() methods or with {@link #refit(double[])}, 329 * and the activator and inhibitor should have been produced by calls to an offsets method like 330 * {@link #offsetsCircle(int, int, double)}, with the same width and height passed to initialize (or if you used 331 * refit, the length of the substance array should be equal to width times height). The activation and inhibition 332 * parameters should be very small (larger numbers will cause more significant jumps in a simulation, but may be 333 * better for single generations; neither amount should have an absolute value larger than 0.1 in general), and 334 * inhibition should have the opposite sign of activation. 335 * @param substance as produced by initialize; will be modified! 336 * @param activator as produced by an offsets method 337 * @param activation the small double amount to use when the activator is dominant; should usually be positive 338 * @param inhibitor as produced by an offsets method 339 * @param inhibition the small double amount to use when the inhibitor is dominant; should usually be negative 340 */ 341 public static void step(final double[] substance, final int[][] activator, 342 final double activation, final int[][] inhibitor, final double inhibition) { 343 double mn = Double.POSITIVE_INFINITY, mx = Double.NEGATIVE_INFINITY, t; 344 345 for (int s = 0; s < substance.length; s++) { 346 double activate = 0.0, inhibit = 0.0; 347 for (int p = 0; p < activator.length; p++) { 348 activate += substance[activator[p][s]]; 349 } 350 for (int p = 0; p < inhibitor.length; p++) { 351 inhibit += substance[inhibitor[p][s]]; 352 } 353 t = (substance[s] += (activate > inhibit) ? activation : inhibition); 354 mx = Math.max(mx, t); 355 mn = Math.min(mn, t); 356 } 357 t = 2.0 / (mx - mn); 358 for (int s = 0; s < substance.length; s++) { 359 substance[s] = (substance[s] - mn) * t - 1; 360 } 361 } 362 363 /** 364 * Computes the first part of a step, allowing other adjustments to be mixed in before finishing by calling 365 * {@link #normalize(double[])}. A sample adjustment would be 366 * {@link #addNoise(double[], int, int, double, Noise.Noise2D, long)}. This is probably not very useful yet. 367 * @param substance as produced by initialize; will be modified! 368 * @param activator as produced by an offsets method 369 * @param activation the small double amount to use when the activator is dominant; should usually be positive 370 * @param inhibitor as produced by an offsets method 371 * @param inhibition the small double amount to use when the inhibitor is dominant; should usually be negative 372 * @see #step(double[], int[][], double, int[][], double) step, which is preferred to this method 373 */ 374 public static void stepPartial(final double[] substance, final int[][] activator, 375 final double activation, final int[][] inhibitor, final double inhibition) { 376 for (int s = 0; s < substance.length; s++) { 377 double activate = 0.0, inhibit = 0.0; 378 for (int p = 0; p < activator.length; p++) { 379 activate += substance[activator[p][s]]; 380 } 381 for (int p = 0; p < inhibitor.length; p++) { 382 inhibit += substance[inhibitor[p][s]]; 383 } 384 substance[s] += (activate > inhibit) ? activation : inhibition; 385 } 386 } 387 388 /** 389 * Simply adds the result of a noise call, multiplied by the given multiplier, to each point in substance. 390 * Modifies substance in-place. 391 * @param substance as produced by initialize; will be modified! 392 * @param width the width of the substance array; should be consistent throughout calls 393 * @param height the height of the substance array; should be consistent throughout calls 394 * @param multiplier multiplied with each noise call, so noise (usually too significant) can have its effect reduced 395 * @param noise a Noise2D instance, such as {@link SeededNoise#instance} 396 * @param seed a seed for the Noise2D 397 */ 398 public static void addNoise(final double[] substance, final int width, final int height, 399 final double multiplier, final Noise.Noise2D noise, final long seed) 400 { 401 int s = 0; 402 for (int x = 0; x < width; x++) { 403 for (int y = 0; y < height; y++) { 404 substance[s++] += noise.getNoiseWithSeed(x, y, seed) * multiplier; 405 } 406 } 407 } 408 /** 409 * Simply adds the result of a noise call, multiplied by the given multiplier, to each point in substance. 410 * Modifies substance in-place. 411 * @param substance as produced by initialize; will be modified! 412 * @param width the width of the substance array; should be consistent throughout calls 413 * @param height the height of the substance array; should be consistent throughout calls 414 * @param multiplier multiplied with each noise call, so noise (usually too significant) can have its effect reduced 415 * @param noise a Noise3D instance, such as {@link SeededNoise#instance} 416 * @param z a z position to be given to the Noise3D along with a point's x and y 417 * @param seed a seed for the Noise3D 418 */ 419 public static void addNoise(final double[] substance, final int width, final int height, 420 final double multiplier, final Noise.Noise3D noise, final double z, final long seed) 421 { 422 int s = 0; 423 for (int x = 0; x < width; x++) { 424 for (int y = 0; y < height; y++) { 425 substance[s++] += noise.getNoiseWithSeed(x, y, z, seed) * multiplier; 426 } 427 } 428 } 429 430 /** 431 * Finds the highest and lowest values in the substance array and modifies the whole array so the lowest and highest 432 * values are contracted or expanded to -1.0 and 1.0, respectively, and other values change commensurately. 433 * @param substance a substance array, as produced by initialize, will be modified! 434 */ 435 public static void normalize(final double[] substance) 436 { 437 double mn = Double.POSITIVE_INFINITY, mx = Double.NEGATIVE_INFINITY, t; 438 for (int s = 0; s < substance.length; s++) { 439 mx = Math.max(mx, (t = substance[s])); 440 mn = Math.min(mn, t); 441 } 442 t = 2.0 / (mx - mn); 443 for (int s = 0; s < substance.length; s++) { 444 substance[s] = (substance[s] - mn) * t - 1; 445 } 446 } 447 448 /** 449 * Makes a new 2D double array with the given width and height, using the given substance array for contents. 450 * @param width the width of the 2D array to produce; must be 1 or greater 451 * @param height the height of the 2D array to produce; must be 1 or greater 452 * @param substance a substance array as produced by initialize and modified by step 453 * @return a new 2D double array with the contents of substance and the requested size 454 */ 455 public static double[][] reshape(final int width, final int height, final double[] substance) 456 { 457 double[][] val = new double[width][height]; 458 int s = 0; 459 for (int x = 0; x < width; x++) { 460 for (int y = 0; y < height; y++) { 461 val[x][y] = substance[s++]; 462 } 463 } 464 return val; 465 } 466 467 /** 468 * Modifies target in-place so it is filled with as much data as possible from substance. 469 * @param target a non-null, non-empty 2D double array; will be modified! 470 * @param substance a substance array as produced by initialize and modified by step 471 */ 472 public static void fill(final double[][] target, final double[] substance) 473 { 474 if(target == null || substance == null || target.length == 0 || target[0].length == 0 || substance.length == 0) 475 return; 476 int s = 0, width = target.length, height = target[0].length, size = substance.length; 477 for (int x = 0; x < width && s < size; x++) { 478 for (int y = 0; y < height && s < size; y++) { 479 target[x][y] = substance[s++]; 480 } 481 } 482 } 483}