001package squidpony.squidgrid; 002 003import squidpony.squidmath.Coord; 004import squidpony.squidmath.Coord3D; 005import squidpony.squidmath.RNG; 006 007import java.util.LinkedHashSet; 008import java.util.Set; 009 010/** 011 * Basic radius strategy implementations likely to be used for roguelikes. 012 * 013 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 014 */ 015public enum Radius { 016 017 /** 018 * In an unobstructed area the FOV would be a square. 019 * 020 * This is the shape that would represent movement radius in an 8-way 021 * movement scheme with no additional cost for diagonal movement. 022 */ 023 SQUARE, 024 /** 025 * In an unobstructed area the FOV would be a diamond. 026 * 027 * This is the shape that would represent movement radius in a 4-way 028 * movement scheme. 029 */ 030 DIAMOND, 031 /** 032 * In an unobstructed area the FOV would be a circle. 033 * 034 * This is the shape that would represent movement radius in an 8-way 035 * movement scheme with all movement cost the same based on distance from 036 * the source 037 */ 038 CIRCLE, 039 /** 040 * In an unobstructed area the FOV would be a cube. 041 * 042 * This is the shape that would represent movement radius in an 8-way 043 * movement scheme with no additional cost for diagonal movement. 044 */ 045 CUBE, 046 /** 047 * In an unobstructed area the FOV would be a octahedron. 048 * 049 * This is the shape that would represent movement radius in a 4-way 050 * movement scheme. 051 */ 052 OCTAHEDRON, 053 /** 054 * In an unobstructed area the FOV would be a sphere. 055 * 056 * This is the shape that would represent movement radius in an 8-way 057 * movement scheme with all movement cost the same based on distance from 058 * the source 059 */ 060 SPHERE; 061 062 private static final double PI2 = Math.PI * 2; 063 public double radius(int startx, int starty, int startz, int endx, int endy, int endz) { 064 return radius((double) startx, (double) starty, (double) startz, (double) endx, (double) endy, (double) endz); 065 } 066 067 public double radius(double startx, double starty, double startz, double endx, double endy, double endz) { 068 double dx = Math.abs(startx - endx); 069 double dy = Math.abs(starty - endy); 070 double dz = Math.abs(startz - endz); 071 return radius(dx, dy, dz); 072 } 073 074 public double radius(int dx, int dy, int dz) { 075 return radius((float) dx, (float) dy, (float) dz); 076 } 077 078 public double radius(double dx, double dy, double dz) { 079 dx = Math.abs(dx); 080 dy = Math.abs(dy); 081 dz = Math.abs(dz); 082 double radius = 0; 083 switch (this) { 084 case SQUARE: 085 case CUBE: 086 radius = Math.max(dx, Math.max(dy, dz));//radius is longest axial distance 087 break; 088 case DIAMOND: 089 case OCTAHEDRON: 090 radius = dx + dy + dz;//radius is the manhattan distance 091 break; 092 case CIRCLE: 093 case SPHERE: 094 radius = Math.sqrt(dx * dx + dy * dy + dz * dz);//standard spherical radius 095 } 096 return radius; 097 } 098 099 public double radius(int startx, int starty, int endx, int endy) { 100 return radius((double) startx, (double) starty, (double) endx, (double) endy); 101 } 102 public double radius(Coord start, Coord end) { 103 return radius((double) start.x, (double) start.y, (double) end.x, (double) end.y); 104 } 105 public double radius(Coord end) { 106 return radius(0.0, 0.0, (double) end.x, (double) end.y); 107 } 108 109 public double radius(double startx, double starty, double endx, double endy) { 110 double dx = startx - endx; 111 double dy = starty - endy; 112 return radius(dx, dy); 113 } 114 115 public double radius(int dx, int dy) { 116 return radius((double) dx, (double) dy); 117 } 118 119 public double radius(double dx, double dy) { 120 return radius(dx, dy, 0); 121 } 122 123 public Coord onUnitShape(double distance, RNG rng) { 124 int x = 0, y = 0; 125 switch (this) { 126 case SQUARE: 127 case CUBE: 128 x = rng.between((int) -distance, (int) distance + 1); 129 y = rng.between((int) -distance, (int) distance + 1); 130 break; 131 case DIAMOND: 132 case OCTAHEDRON: 133 x = rng.between((int) -distance, (int) distance + 1); 134 y = rng.between((int) -distance, (int) distance + 1); 135 if (radius(x, y) > distance) { 136 if (x > 0) { 137 if (y > 0) { 138 x = (int) (distance - x); 139 y = (int) (distance - y); 140 } else { 141 x = (int) (distance - x); 142 y = (int) (-distance - y); 143 } 144 } else { 145 if (y > 0) { 146 x = (int) (-distance - x); 147 y = (int) (distance - y); 148 } else { 149 x = (int) (-distance - x); 150 y = (int) (-distance - y); 151 } 152 } 153 } 154 break; 155 case CIRCLE: 156 case SPHERE: 157 double radius = distance * Math.sqrt(rng.between(0.0, 1.0)); 158 double theta = rng.between(0, PI2); 159 x = (int) Math.round(Math.cos(theta) * radius); 160 y = (int) Math.round(Math.sin(theta) * radius); 161 } 162 163 return Coord.get(x, y); 164 } 165 166 public Coord3D onUnitShape3D(double distance, RNG rng) { 167 int x = 0, y = 0, z = 0; 168 switch (this) { 169 case SQUARE: 170 case DIAMOND: 171 case CIRCLE: 172 Coord p = onUnitShape(distance, rng); 173 return new Coord3D(p.x, p.y, 0);//2D strategies 174 case CUBE: 175 x = rng.between((int) -distance, (int) distance + 1); 176 y = rng.between((int) -distance, (int) distance + 1); 177 z = rng.between((int) -distance, (int) distance + 1); 178 break; 179 case OCTAHEDRON: 180 case SPHERE: 181 do { 182 x = rng.between((int) -distance, (int) distance + 1); 183 y = rng.between((int) -distance, (int) distance + 1); 184 z = rng.between((int) -distance, (int) distance + 1); 185 } while (radius(x, y, z) > distance); 186 } 187 188 return new Coord3D(x, y, z); 189 } 190 public double volume2D(double radiusLength) 191 { 192 switch (this) { 193 case SQUARE: 194 case CUBE: 195 return (radiusLength * 2 + 1) * (radiusLength * 2 + 1); 196 case DIAMOND: 197 case OCTAHEDRON: 198 return radiusLength * (radiusLength + 1) * 2 + 1; 199 default: 200 return Math.PI * radiusLength * radiusLength + 1; 201 } 202 } 203 public double volume3D(double radiusLength) 204 { 205 switch (this) { 206 case SQUARE: 207 case CUBE: 208 return (radiusLength * 2 + 1) * (radiusLength * 2 + 1) * (radiusLength * 2 + 1); 209 case DIAMOND: 210 case OCTAHEDRON: 211 double total = radiusLength * (radiusLength + 1) * 2 + 1; 212 for(double i = radiusLength - 1; i >= 0; i--) 213 { 214 total += (i * (i + 1) * 2 + 1) * 2; 215 } 216 return total; 217 default: 218 return Math.PI * radiusLength * radiusLength * radiusLength * 4.0 / 3.0 + 1; 219 } 220 } 221 222 223 224 225 private int clamp(int n, int min, int max) 226 { 227 return Math.min(Math.max(min, n), max - 1); 228 } 229 230 public Set<Coord> perimeter(Coord center, int radiusLength, boolean surpassEdges, int width, int height) 231 { 232 LinkedHashSet<Coord> rim = new LinkedHashSet<>(4 * radiusLength); 233 if(!surpassEdges && (center.x < 0 || center.x >= width || center.y < 0 || center.y > height)) 234 return rim; 235 if(radiusLength < 1) { 236 rim.add(center); 237 return rim; 238 } 239 switch (this) { 240 case SQUARE: 241 case CUBE: 242 { 243 for (int i = center.x - radiusLength; i <= center.x + radiusLength; i++) { 244 int x = i; 245 if(!surpassEdges) x = clamp(i, 0, width); 246 rim.add(Coord.get(x, clamp(center.y - radiusLength, 0, height))); 247 rim.add(Coord.get(x, clamp(center.y + radiusLength, 0, height))); 248 } 249 for (int j = center.y - radiusLength; j <= center.y + radiusLength; j++) { 250 int y = j; 251 if(!surpassEdges) y = clamp(j, 0, height); 252 rim.add(Coord.get(clamp(center.x - radiusLength, 0, height), y)); 253 rim.add(Coord.get(clamp(center.x + radiusLength, 0, height), y)); 254 } 255 } 256 break; 257 case DIAMOND: 258 case OCTAHEDRON: { 259 int xUp = center.x + radiusLength, xDown = center.x - radiusLength, 260 yUp = center.y + radiusLength, yDown = center.y - radiusLength; 261 if(!surpassEdges) { 262 xDown = clamp(xDown, 0, width); 263 xUp = clamp(xUp, 0, width); 264 yDown = clamp(yDown, 0, height); 265 yUp = clamp(yUp, 0, height); 266 } 267 268 rim.add(Coord.get(xDown, center.y)); 269 rim.add(Coord.get(xUp, center.y)); 270 rim.add(Coord.get(center.x, yDown)); 271 rim.add(Coord.get(center.x, yUp)); 272 273 for (int i = xDown + 1, c = 1; i < center.x; i++, c++) { 274 int x = i; 275 if(!surpassEdges) x = clamp(i, 0, width); 276 rim.add(Coord.get(x, clamp(center.y - c, 0, height))); 277 rim.add(Coord.get(x, clamp(center.y + c, 0, height))); 278 } 279 for (int i = center.x + 1, c = 1; i < center.x + radiusLength; i++, c++) { 280 int x = i; 281 if(!surpassEdges) x = clamp(i, 0, width); 282 rim.add(Coord.get(x, clamp(center.y + radiusLength - c, 0, height))); 283 rim.add(Coord.get(x, clamp(center.y - radiusLength + c, 0, height))); 284 } 285 } 286 break; 287 default: 288 { 289 double theta; 290 int x, y, denom = 1; 291 boolean anySuccesses; 292 while(denom <= 256) { 293 anySuccesses = false; 294 for (int i = 1; i <= denom; i+=2) 295 { 296 theta = i * (PI2 / denom); 297 x = (int) Math.round(Math.cos(theta) * radiusLength) + center.x; 298 y = (int) Math.round(Math.sin(theta) * radiusLength) + center.y; 299 if (!surpassEdges) { 300 x = clamp(x, 0, width); 301 y = clamp(y, 0, height); 302 } 303 Coord p = Coord.get(x, y); 304 boolean test = rim.contains(p); 305 306 rim.add(p); 307 anySuccesses = test || anySuccesses; 308 } 309 if(!anySuccesses) 310 break; 311 denom *= 2; 312 } 313 314 } 315 } 316 return rim; 317 } 318 public Coord extend(Coord center, Coord middle, int radiusLength, boolean surpassEdges, int width, int height) 319 { 320 if(!surpassEdges && (center.x < 0 || center.x >= width || center.y < 0 || center.y > height || 321 middle.x < 0 || middle.x >= width || middle.y < 0 || middle.y > height)) 322 return Coord.get(0, 0); 323 if(radiusLength < 1) { 324 return center; 325 } 326 double theta = Math.atan2(middle.y - center.y, middle.x - center.x), 327 cosTheta = Math.cos(theta), sinTheta = Math.sin(theta); 328 329 Coord end = Coord.get(middle.x, middle.y); 330 switch (this) { 331 case SQUARE: 332 case CUBE: 333 case DIAMOND: 334 case OCTAHEDRON: 335 { 336 int rad2 = 0; 337 if(surpassEdges) 338 { 339 while (radius(center.x, center.y, end.x, end.y) < radiusLength) { 340 rad2++; 341 end = Coord.get((int) Math.round(cosTheta * rad2) + center.x 342 , (int) Math.round(sinTheta * rad2) + center.y); 343 } 344 } 345 else { 346 while (radius(center.x, center.y, end.x, end.y) < radiusLength) { 347 rad2++; 348 end = Coord.get(clamp((int) Math.round(cosTheta * rad2) + center.x, 0, width) 349 , clamp((int) Math.round(sinTheta * rad2) + center.y, 0, height)); 350 if (end.x == 0 || end.x == width - 1 || end.y == 0 || end.y == height - 1) 351 return end; 352 } 353 } 354 355 return end; 356 } 357 default: 358 { 359 end = Coord.get(clamp( (int) Math.round(cosTheta * radiusLength) + center.x, 0, width) 360 , clamp( (int) Math.round(sinTheta * radiusLength) + center.y, 0, height)); 361 if(!surpassEdges) { 362 long edgeLength = 0; 363// if (end.x == 0 || end.x == width - 1 || end.y == 0 || end.y == height - 1) 364 if (end.x < 0) 365 { 366 // wow, we lucked out here. the only situation where cos(angle) is 0 is if the angle aims 367 // straight up or down, and then x cannot be < 0 or >= width. 368 edgeLength = Math.round((0 - center.x) / cosTheta); 369 end = end.setY(clamp((int) Math.round(sinTheta * edgeLength) + center.y, 0, height)); 370 } 371 else if(end.x >= width) 372 { 373 // wow, we lucked out here. the only situation where cos(angle) is 0 is if the angle aims 374 // straight up or down, and then x cannot be < 0 or >= width. 375 edgeLength = Math.round((width - 1 - center.x) / cosTheta); 376 end = end.setY(clamp((int) Math.round(sinTheta * edgeLength) + center.y, 0, height)); 377 } 378 379 if (end.y < 0) 380 { 381 // wow, we lucked out here. the only situation where sin(angle) is 0 is if the angle aims 382 // straight left or right, and then y cannot be < 0 or >= height. 383 edgeLength = Math.round((0 - center.y) / sinTheta); 384 end = end.setX(clamp((int) Math.round(cosTheta * edgeLength) + center.x, 0, width)); 385 } 386 else if(end.y >= height) 387 { 388 // wow, we lucked out here. the only situation where sin(angle) is 0 is if the angle aims 389 // straight left or right, and then y cannot be < 0 or >= height. 390 edgeLength = Math.round((height - 1 - center.y) / sinTheta); 391 end = end.setX(clamp((int) Math.round(cosTheta * edgeLength) + center.x, 0, width)); 392 } 393 } 394 return end; 395 } 396 } 397 } 398 399 /** 400 * Compares two Radius enums as if they are both in a 2D plane; that is, Radius.SPHERE is treated as equal to 401 * Radius.CIRCLE, Radius.CUBE is equal to Radius.SQUARE, and Radius.OCTAHEDRON is equal to Radius.DIAMOND. 402 * @param other the Radius to compare this to 403 * @return true if the 2D versions of both Radius enums are the same shape. 404 */ 405 public boolean equals2D(Radius other) 406 { 407 switch (this) 408 { 409 case CIRCLE: 410 case SPHERE: 411 return (other == CIRCLE || other == SPHERE); 412 case SQUARE: 413 case CUBE: 414 return (other == SQUARE || other == CUBE); 415 default: 416 return (other == DIAMOND || other == OCTAHEDRON); 417 } 418 } 419 public boolean inRange(int startx, int starty, int endx, int endy, int minRange, int maxRange) 420 { 421 double dist = radius(startx, starty, endx, endy); 422 return dist >= minRange - 0.001 && dist <= maxRange + 0.001; 423 } 424 425 public int roughDistance(int xPos, int yPos) { 426 int x = Math.abs(xPos), y = Math.abs(yPos); 427 switch (this) { 428 case CIRCLE: 429 case SPHERE: 430 { 431 if(x == y) 432 return 3 * x; 433 else if(x < y) 434 return 3 * x + 2 * (y - x); 435 else 436 return 3 * y + 2 * (x - y); 437 } 438 case DIAMOND: 439 case OCTAHEDRON: 440 return 2 * (x + y); 441 default: 442 return 2 * Math.max(x, y); 443 } 444 } 445 446 public Set<Coord> pointsInside(Coord center, int radiusLength, boolean surpassEdges, int width, int height) 447 { 448 LinkedHashSet<Coord> contents = new LinkedHashSet<Coord>((int)Math.ceil(volume2D(radiusLength))); 449 if(!surpassEdges && (center.x < 0 || center.x >= width || center.y < 0 || center.y >= height)) 450 return contents; 451 if(radiusLength < 1) { 452 contents.add(center); 453 return contents; 454 } 455 switch (this) { 456 case SQUARE: 457 case CUBE: 458 { 459 for (int i = center.x - radiusLength; i <= center.x + radiusLength; i++) { 460 for (int j = center.y - radiusLength; j <= center.y + radiusLength; j++) { 461 if(!surpassEdges && (i < 0 || j < 0 || i >= width || j >= height)) 462 continue; 463 contents.add(Coord.get(i, j)); 464 } 465 } 466 } 467 break; 468 case DIAMOND: 469 case OCTAHEDRON: { 470 for (int i = center.x - radiusLength; i <= center.x + radiusLength; i++) { 471 for (int j = center.y - radiusLength; j <= center.y + radiusLength; j++) { 472 if ((Math.abs(center.x - i) + Math.abs(center.y- j) > radiusLength) || 473 (!surpassEdges && (i < 0 || j < 0 || i >= width || j >= height))) 474 continue; 475 contents.add(Coord.get(i, j)); 476 } 477 } 478 } 479 break; 480 default: 481 { 482 int high; 483 for (int dx = -radiusLength; dx <= radiusLength; ++dx) { 484 high = (int) Math.floor(Math.sqrt(radiusLength * radiusLength - dx * dx)); 485 for (int dy = -high; dy <= high; ++dy) { 486 if (!surpassEdges && (center.x + dx < 0 || center.y + dy < 0 || 487 center.x + dx >= width || center.y + dy >= height)) 488 continue; 489 contents.add(Coord.get(center.x + dx, center.y + dy)); 490 } 491 } 492 } 493 } 494 return contents; 495 } 496 497 /** 498 * Given an Iterable of Coord (such as a List or Set), a distance to expand outward by (using this Radius), and the 499 * bounding height and width of the map, gets a "thickened" group of Coord as a Set where each Coord in points has 500 * been expanded out by an amount no greater than distance. As an example, you could call this on a line generated 501 * by Bresenham, OrthoLine, or an LOS object's getLastPath() method, and expand the line into a thick "brush stroke" 502 * where this Radius affects the shape of the ends. This will never produce a Coord with negative x or y, a Coord 503 * with x greater than or equal to width, or a Coord with y greater than or equal to height. 504 * @param distance the distance, as measured by this Radius, to expand each Coord on points up to 505 * @param width the bounding width of the map (exclusive) 506 * @param height the bounding height of the map (exclusive) 507 * @param points an Iterable (such as a List or Set) of Coord that this will make a "thickened" version of 508 * @return a Set of Coord that covers a wider area than what points covers; each Coord will be unique (it's a Set) 509 */ 510 public Set<Coord> expand(int distance, int width, int height, Iterable<Coord> points) 511 { 512 Set<Coord> around = pointsInside(Coord.get(distance, distance), distance, false, width, height), 513 expanded = new LinkedHashSet<>(around.size() * 16); 514 int tx, ty; 515 for(Coord pt : points) 516 { 517 for(Coord ar : around) 518 { 519 tx = pt.x + ar.x - distance; 520 ty = pt.y + ar.y - distance; 521 if(tx >= 0 && tx < width && ty >= 0 && ty < height) 522 expanded.add(Coord.get(tx, ty)); 523 } 524 } 525 return expanded; 526 } 527}