001package squidpony.squidmath; 002 003/** 004 * Based on <a href="http://extremelearning.com.au/isotropic-blue-noise-point-sets/">Martin Roberts' blog post about 005 * blue noise point sets</a>, this class generates "balanced" permutations of a specific size with good performance. 006 */ 007public class BalancedPermutations { 008 public final int size; 009 private final int halfSize; 010 private final int[] delta, targets; 011 /** 012 * Can be any long. 013 */ 014 private long stateA; 015 /** 016 * Must be odd. 017 */ 018 private long stateB; 019 020 public BalancedPermutations(){ 021 this(16, 022 (long) ((Math.random() - 0.5) * 0x10000000000000L) 023 ^ (long) (((Math.random() - 0.5) * 2.0) * 0x8000000000000000L), 024 (long) ((Math.random() - 0.5) * 0x10000000000000L) 025 ^ (long) (((Math.random() - 0.5) * 2.0) * 0x8000000000000000L)); 026 } 027 public BalancedPermutations(int size, long stateA, long stateB) 028 { 029 this.size = size; 030 this.halfSize = size >>> 1; 031 delta = new int[size]; 032 targets = new int[size]; 033 this.stateA = stateA; 034 this.stateB = stateB | 1; 035 } 036 037 /** 038 * It's a weird RNG. Returns a slightly-biased pseudo-random int between 0 inclusive and bound exclusive. The bias comes from 039 * not completely implementing Daniel Lemire's fastrange algorithm, but it should only be relevant for huge bounds. The number 040 * generator itself passes PractRand without anomalies, has a state size of 127 bits, and a period of 2 to the 127. 041 * This generator will probably be added to SquidLib as "GearRNG." 042 * @param bound upper exclusive bound 043 * @return an int between 0 (inclusive) and bound (exclusive) 044 */ 045 private int nextIntBounded (int bound) { 046 final long s = (stateA += 0xC6BC279692B5C323L); 047 final long z = ((s < 0x800000006F17146DL) ? stateB : (stateB += 0x9479D2858AF899E6L)) * (s ^ s >>> 31); 048 return (int)(bound * ((z ^ z >>> 25) & 0xFFFFFFFFL) >>> 32); 049 } 050 051 private static void swap(int[] arr, int pos1, int pos2) { 052 final int tmp = arr[pos1]; 053 arr[pos1] = arr[pos2]; 054 arr[pos2] = tmp; 055 } 056 057 /** 058 * Fisher-Yates and/or Knuth shuffle, done in-place on an int array. 059 * @param elements will be modified in-place by a relatively fair shuffle 060 */ 061 private void shuffleInPlace(int[] elements) { 062 final int size = elements.length; 063 for (int i = size; i > 1; i--) { 064 swap(elements, i - 1, nextIntBounded(i)); 065 } 066 } 067 068 /** 069 * Fills {@code items} with a balanced permutation from 0 to {@code size - 1}. The length of {@code items} must be 070 * at least {@code size}. This may take a while if size is large; half a second is reasonable for when size is 48, 071 * with smaller sizes taking much less time and larger ones taking much more. 072 * @param items an int array which will be modified in-place 073 */ 074 public void fill(final int[] items) { 075 if(items == null || items.length < size) return; 076 BIG_LOOP: 077 while (true) { 078 for (int i = 0; i < halfSize; i++) { 079 delta[i] = i + 1; 080 delta[i + halfSize] = ~i; 081 } 082 shuffleInPlace(delta); 083 for (int i = 0; i < size; i++) { 084 targets[i] = i; 085 } 086 targets[items[0] = nextIntBounded(size)] = -1; 087 for (int i = 1; i < size; i++) { 088 int d = 0; 089 for (int j = 0; j < size; j++) { 090 d = delta[j]; 091 if (d == 0) continue; 092 int t = items[i - 1] + d; 093 if (t >= 0 && t < size && targets[t] != -1) { 094 items[i] = t; 095 targets[t] = -1; 096 delta[j] = 0; 097 break; 098 } else d = 0; 099 } 100 if (d == 0) continue BIG_LOOP; 101 } 102 int d = items[0] - items[size - 1]; 103 for (int j = 0; j < size; j++) { 104 if (d == delta[j]) { 105 return; // found a valid balanced permutation 106 } 107 } 108 } 109 } 110 111 public GreasedRegion rotatedGrid(){ 112 int size2 = size * size; 113 GreasedRegion region = new GreasedRegion(size2, size2); 114 int px, py = 0; 115 for (int x = 0; x < size; x++) { 116 px = size - 1 + x * size; 117 for (int y = 0; y < size; y++) { 118 region.insert(px--, py + y * size); 119 } 120 py++; 121 } 122 return region; 123 } 124 125 public GreasedRegion shuffledGrid(){ 126 int[] xPerm = new int[size], yPerm = new int[size]; 127 fill(xPerm); 128 fill(yPerm); 129 int size2 = size * size; 130 GreasedRegion region = new GreasedRegion(size2, size2); 131 int px, py; 132 for (int x = 0; x < size; x++) { 133 px = size - 1; 134 py = yPerm[x]; 135 for (int y = 0; y < size; y++) { 136 region.insert(px - xPerm[y] + xPerm[x] * size, py + yPerm[y] * size); 137 } 138 } 139 return region; 140 } 141 142 public GreasedRegion shuffledGridMultiple(int repeats){ 143 int[] xPerm = new int[size], yPerm = new int[size], rxPerm = new int[size], ryPerm = new int[size]; 144 repeats = (repeats + size - 1) % size; 145 fill(xPerm); 146 fill(yPerm); 147 fill(rxPerm); 148 fill(ryPerm); 149 int size2 = size * size; 150 GreasedRegion region = new GreasedRegion(size2, size2); 151 int px, py, rx, ry; 152 for (int r = 0; r <= repeats; r++) { 153 rx = rxPerm[r]; 154 ry = ryPerm[r]; 155 for (int x = 0; x < size; x++) { 156 px = size - 1; 157 py = yPerm[x]; 158 for (int y = 0; y < size; y++) { 159 region.insert(px - xPerm[y] + xPerm[(x + rx) % size] * size, py + yPerm[(y + ry) % size] * size); 160 } 161 } 162 } 163 return region; 164 } 165}