001package squidpony.squidmath; 002 003import squidpony.squidgrid.Radius; 004 005import java.util.ArrayList; 006import java.util.Collections; 007import java.util.HashSet; 008import java.util.LinkedHashSet; 009 010/** 011 * This provides a Uniform Poisson Disk Sampling technique that can be used to generate random points that have a 012 * uniform minimum distance between each other. Due to Coord in SquidLib using ints and most Poisson Disk algorithms 013 * using floating-point numbers, some imprecision is to be expected from rounding to the nearest integers x and y. 014 * 015 * The algorithm is from the "Fast Poisson Disk Sampling in Arbitrary Dimensions" paper by Robert Bridson 016 * http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf 017 * 018 * Adapted from C# by Renaud Bedard, which was adapted from Java source by Herman Tulleken 019 * http://theinstructionlimit.com/fast-uniform-poisson-disk-sampling-in-c 020 * Created by Tommy Ettinger on 10/20/2015. 021 */ 022public class PoissonDisk { 023 private static final float rootTwo = (float) Math.sqrt(2), 024 pi = (float) Math.PI, pi2 = pi * 2f, halfPi = pi * 0.5f; 025 026 private static final int defaultPointsPlaced = 10; 027 private static final Radius disk = Radius.CIRCLE; 028 029 private PoissonDisk() { 030 } 031 032 /** 033 * Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with 034 * Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list. 035 * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have 036 * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have 037 * negative x or y. 038 * @param center the center of the circle to spray Coords into 039 * @param radius the radius of the circle to spray Coords into 040 * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float. 041 * @param maxX one more than the highest x that can be assigned; typically an array length 042 * @param maxY one more than the highest y that can be assigned; typically an array length 043 * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary 044 */ 045 public static ArrayList<Coord> sampleCircle(Coord center, float radius, float minimumDistance, 046 int maxX, int maxY) 047 { 048 return sampleCircle(center, radius, minimumDistance, maxX, maxY, defaultPointsPlaced, new StatefulRNG()); 049 } 050 051 /** 052 * Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with 053 * Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list. 054 * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have 055 * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have 056 * negative x or y. 057 * @param center the center of the circle to spray Coords into 058 * @param radius the radius of the circle to spray Coords into 059 * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float. 060 * @param maxX one more than the highest x that can be assigned; typically an array length 061 * @param maxY one more than the highest y that can be assigned; typically an array length 062 * @param pointsPerIteration with small radii, this can be around 5; with larger ones, 30 is reasonable 063 * @param rng an RNG to use for all random sampling. 064 * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary 065 */ 066 public static ArrayList<Coord> sampleCircle(Coord center, float radius, float minimumDistance, 067 int maxX, int maxY, int pointsPerIteration, RNG rng) 068 { 069 int radius2 = Math.round(radius); 070 return sample(center.translate(-radius2, -radius2), center.translate(radius2, radius2), radius, minimumDistance, maxX, maxY, pointsPerIteration, rng); 071 } 072 073 /** 074 * Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and 075 * maxPosition, but with the given minimum distance from any other Coord in the list. 076 * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have 077 * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have 078 * negative x or y. 079 * @param minPosition the Coord with the lowest x and lowest y to be used as a corner for the bounding box 080 * @param maxPosition the Coord with the highest x and highest y to be used as a corner for the bounding box 081 * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float. 082 * @param maxX one more than the highest x that can be assigned; typically an array length 083 * @param maxY one more than the highest y that can be assigned; typically an array length 084 * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary 085 */ 086 public static ArrayList<Coord> sampleRectangle(Coord minPosition, Coord maxPosition, float minimumDistance, 087 int maxX, int maxY) 088 { 089 return sampleRectangle(minPosition, maxPosition, minimumDistance, maxX, maxY, defaultPointsPlaced, new StatefulRNG()); 090 } 091 092 /** 093 * Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and 094 * maxPosition, but with the given minimum distance from any other Coord in the list. 095 * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have 096 * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have 097 * negative x or y. 098 * @param minPosition the Coord with the lowest x and lowest y to be used as a corner for the bounding box 099 * @param maxPosition the Coord with the highest x and highest y to be used as a corner for the bounding box 100 * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float. 101 * @param maxX one more than the highest x that can be assigned; typically an array length 102 * @param maxY one more than the highest y that can be assigned; typically an array length 103 * @param pointsPerIteration with small areas, this can be around 5; with larger ones, 30 is reasonable 104 * @param rng an RNG to use for all random sampling. 105 * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary 106 */ 107 public static ArrayList<Coord> sampleRectangle(Coord minPosition, Coord maxPosition, float minimumDistance, 108 int maxX, int maxY, int pointsPerIteration, RNG rng) 109 { 110 return sample(minPosition, maxPosition, 0f, minimumDistance, maxX, maxY, pointsPerIteration, rng); 111 } 112 113 private static ArrayList<Coord> sample(Coord minPosition, Coord maxPosition, float rejectionDistance, 114 float minimumDistance, int maxX, int maxY, int pointsPerIteration, RNG rng) 115 { 116 117 Coord center = minPosition.average(maxPosition); 118 Coord dimensions = maxPosition.subtract(minPosition); 119 float cellSize = Math.max(minimumDistance / rootTwo, 0.25f); 120 int gridWidth = (int)(dimensions.x / cellSize) + 1; 121 int gridHeight = (int)(dimensions.y / cellSize) + 1; 122 Coord[][] grid = new Coord[gridWidth][gridHeight]; 123 ArrayList<Coord> activePoints = new ArrayList<>(); 124 LinkedHashSet<Coord> points = new LinkedHashSet<>(128); 125 126 //add first point 127 boolean added = false; 128 while (!added) 129 { 130 float d = rng.nextFloat(); 131 int xr = Math.round(minPosition.x + dimensions.x * d); 132 133 d = rng.nextFloat(); 134 int yr = Math.round(minPosition.y + dimensions.y * d); 135 136 if (rejectionDistance > 0 && disk.radius(center.x, center.y, xr, yr) > rejectionDistance) 137 continue; 138 added = true; 139 Coord p = Coord.get(Math.min(xr, maxX - 1), Math.min(yr, maxY - 1)); 140 Coord index = p.subtract(minPosition).divide(cellSize); 141 142 grid[index.x][index.y] = p; 143 144 activePoints.add(p); 145 points.add(p); 146 } 147 //end add first point 148 149 while (activePoints.size() != 0) 150 { 151 int listIndex = rng.nextInt(activePoints.size()); 152 153 Coord point = activePoints.get(listIndex); 154 boolean found = false; 155 156 for (int k = 0; k < pointsPerIteration; k++) 157 { 158 //add next point 159 //get random point around 160 float d = rng.nextFloat(); 161 float radius = minimumDistance + minimumDistance * d; 162 d = rng.nextFloat(); 163 float angle = pi2 * d; 164 165 float newX = radius * (float)Math.sin(angle); 166 float newY = radius * (float)Math.cos(angle); 167 Coord q = point.translateCapped(Math.round(newX), Math.round(newY), maxX, maxY); 168 //end get random point around 169 170 if (q.x >= minPosition.x && q.x <= maxPosition.x && 171 q.y >= minPosition.y && q.y <= maxPosition.y && 172 (rejectionDistance <= 0 || disk.radius(center.x, center.y, q.x, q.y) <= rejectionDistance)) 173 { 174 Coord qIndex = q.subtract(minPosition).divide((int)Math.ceil(cellSize)); 175 boolean tooClose = false; 176 177 for (int i = Math.max(0, qIndex.x - 2); i < Math.min(gridWidth, qIndex.x + 3) && !tooClose; i++) { 178 for (int j = Math.max(0, qIndex.y - 2); j < Math.min(gridHeight, qIndex.y + 3); j++) { 179 if (grid[i][j] != null && disk.radius(grid[i][j], q) < minimumDistance) { 180 tooClose = true; 181 break; 182 } 183 } 184 } 185 if (!tooClose) 186 { 187 found = true; 188 activePoints.add(q); 189 points.add(q); 190 grid[qIndex.x][qIndex.y] = q; 191 } 192 } 193 //end add next point 194 } 195 196 if (!found) 197 activePoints.remove(listIndex); 198 } 199 activePoints = new ArrayList<>(points); 200 return activePoints; 201 } 202 203 public static ArrayList<Coord> sampleMap(char[][] map, 204 float minimumDistance, RNG rng, Character... blocking) 205 { 206 return sampleMap(Coord.get(1, 1), Coord.get(map.length - 2, map[0].length - 2), 207 map, minimumDistance, rng, blocking); 208 } 209 210 public static ArrayList<Coord> sampleMap(Coord minPosition, Coord maxPosition, char[][] map, 211 float minimumDistance, RNG rng, Character... blocking) { 212 int width = map.length; 213 int height = map[0].length; 214 HashSet<Character> blocked = new HashSet<>(); 215 Collections.addAll(blocked, blocking); 216 boolean restricted = false; 217 if (blocked.size() > 0) { 218 restricted = true; 219 } 220 Coord dimensions = maxPosition.subtract(minPosition); 221 float cellSize = Math.max(minimumDistance / rootTwo, 1f); 222 int gridWidth = (int) (dimensions.x / cellSize) + 1; 223 int gridHeight = (int) (dimensions.y / cellSize) + 1; 224 Coord[][] grid = new Coord[gridWidth][gridHeight]; 225 ArrayList<Coord> activePoints = new ArrayList<>(); 226 LinkedHashSet<Coord> points = new LinkedHashSet<>(128); 227 228 //add first point 229 230 Coord p = randomUnblockedTile(minPosition, maxPosition, map, rng, blocked); 231 if (p == null) 232 return activePoints; 233 Coord index = p.subtract(minPosition).divide(cellSize); 234 235 grid[index.x][index.y] = p; 236 237 activePoints.add(p); 238 points.add(p); 239 240 //end add first point 241 242 while (activePoints.size() != 0) { 243 int listIndex = rng.nextInt(activePoints.size()); 244 245 Coord point = activePoints.get(listIndex); 246 boolean found = false; 247 248 for (int k = 0; k < 20; k++) { 249 //add next point 250 //get random point around 251 float d = rng.nextFloat(); 252 float radius = minimumDistance + minimumDistance * d; 253 d = rng.nextFloat(); 254 float angle = pi2 * d; 255 256 float newX = radius * (float) Math.sin(angle); 257 float newY = radius * (float) Math.cos(angle); 258 Coord q = point.translateCapped(Math.round(newX), Math.round(newY), width, height); 259 int frustration = 0; 260 while(blocked.contains(map[q.x][q.y]) && frustration < 8) 261 { 262 d = rng.nextFloat(); 263 angle = pi2 * d; 264 newX = radius * (float) Math.sin(angle); 265 newY = radius * (float) Math.cos(angle); 266 q = point.translateCapped(Math.round(newX), Math.round(newY), width, height); 267 frustration++; 268 } 269 270 //end get random point around 271 272 if (q.x >= minPosition.x && q.x <= maxPosition.x && 273 q.y >= minPosition.y && q.y <= maxPosition.y) { 274 Coord qIndex = q.subtract(minPosition).divide((int) Math.ceil(cellSize)); 275 boolean tooClose = false; 276 277 for (int i = Math.max(0, qIndex.x - 2); i < Math.min(gridWidth, qIndex.x + 3) && !tooClose; i++) { 278 for (int j = Math.max(0, qIndex.y - 2); j < Math.min(gridHeight, qIndex.y + 3); j++) { 279 if (grid[i][j] != null && disk.radius(grid[i][j], q) < minimumDistance) { 280 tooClose = true; 281 break; 282 } 283 } 284 } 285 if (!tooClose) { 286 found = true; 287 activePoints.add(q); 288 if(!blocked.contains(map[q.x][q.y])) 289 points.add(q); 290 grid[qIndex.x][qIndex.y] = q; 291 } 292 } 293 //end add next point 294 } 295 296 if (!found) 297 activePoints.remove(listIndex); 298 } 299 activePoints = new ArrayList<>(points); 300 return activePoints; 301 } 302 /** 303 * Finds a random Coord where the x and y match up to a [x][y] location on map that has any value not in blocking. 304 * Uses the given RNG for pseudo-random number generation. 305 * @param minPosition the Coord with the lowest x and lowest y to be used as a corner for the bounding box 306 * @param maxPosition the Coord with the highest x and highest y to be used as a corner for the bounding box 307 * @param map a dungeon map or something, x then y 308 * @param rng a RNG to generate random choices 309 * @param blocked a Set of Characters that block a tile from being chosen 310 * @return a Coord that corresponds to a map element equal to tile, or null if tile cannot be found or if map is too small. 311 */ 312 public static Coord randomUnblockedTile(Coord minPosition, Coord maxPosition, char[][] map, RNG rng, HashSet<Character> blocked) 313 { 314 int width = map.length; 315 int height = map[0].length; 316 if(width < 3 || height < 3) 317 return null; 318 if(blocked.size() == 0) { 319 return Coord.get(rng.between(minPosition.x, maxPosition.x), rng.between(minPosition.y, maxPosition.y)); 320 } 321 322 int x = rng.between(minPosition.x, maxPosition.x), y = rng.between(minPosition.y, maxPosition.y); 323 for(int i = 0; i < (width + height) / 4; i++) 324 { 325 if(!blocked.contains(map[x][y])) 326 { 327 return Coord.get(x, y); 328 } 329 else 330 { 331 x = rng.between(minPosition.x, maxPosition.x); 332 y = rng.between(minPosition.y, maxPosition.y); 333 } 334 } 335 x = 1; 336 y = 1; 337 if(!blocked.contains(map[x][y])) 338 return Coord.get(x, y); 339 340 while(blocked.contains(map[x][y])) 341 { 342 x += 1; 343 if(x >= width - 1) 344 { 345 x = 1; 346 y += 1; 347 } 348 if(y >= height - 1) 349 return null; 350 } 351 return Coord.get(x, y); 352 } 353 354}