001package squidpony.squidai; 002 003import squidpony.annotation.GwtIncompatible; 004import squidpony.squidgrid.FOV; 005import squidpony.squidgrid.FOVCache; 006import squidpony.squidgrid.Radius; 007import squidpony.squidgrid.mapping.DungeonUtility; 008import squidpony.squidmath.Coord; 009 010import java.util.*; 011 012/** 013 * An AOE type that has a center and a radius, and uses shadowcasting to create a burst of rays from the center, out to 014 * the distance specified by radius. You can specify the RadiusType to Radius.DIAMOND for Manhattan distance, 015 * RADIUS.SQUARE for Chebyshev, or RADIUS.CIRCLE for Euclidean. 016 * 017 * This will produce doubles for its findArea() method which are equal to 1.0. 018 * 019 * This class uses squidpony.squidgrid.FOV to create its area of effect. 020 * Created by Tommy Ettinger on 7/13/2015. 021 */ 022public class BurstAOE implements AOE { 023 private FOV fov; 024 private Coord center, origin; 025 private int radius; 026 private double[][] map; 027 private char[][] dungeon; 028 private Radius radiusType; 029 private Reach reach = new Reach(1, 1, Radius.SQUARE, null); 030 031 public BurstAOE(Coord center, int radius, Radius radiusType) 032 { 033 fov = new FOV(FOV.SHADOW); 034 this.center = center; 035 this.radius = radius; 036 this.radiusType = radiusType; 037 } 038 public BurstAOE(Coord center, int radius, Radius radiusType, int minRange, int maxRange) 039 { 040 fov = new FOV(FOV.SHADOW); 041 this.center = center; 042 this.radius = radius; 043 this.radiusType = radiusType; 044 reach.minDistance = minRange; 045 reach.maxDistance = maxRange; 046 } 047 048 public Coord getCenter() { 049 return center; 050 } 051 052 public void setCenter(Coord center) { 053 054 if (map != null && center.isWithin(map.length, map[0].length) && 055 AreaUtils.verifyReach(reach, origin, center)) 056 { 057 this.center = center; 058 } 059 } 060 061 public int getRadius() { 062 return radius; 063 } 064 065 public void setRadius(int radius) { 066 this.radius = radius; 067 } 068 069 public Radius getRadiusType() { 070 return radiusType; 071 } 072 073 public void setRadiusType(Radius radiusType) { 074 this.radiusType = radiusType; 075 } 076 077 @Override 078 public void shift(Coord aim) { 079 setCenter(aim); 080 } 081 082 @Override 083 public boolean mayContainTarget(Set<Coord> targets) { 084 for (Coord p : targets) 085 { 086 if(radiusType.radius(center.x, center.y, p.x, p.y) <= radius) 087 return true; 088 } 089 return false; 090 } 091 092 @Override 093 public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) { 094 if(targets == null) 095 return new LinkedHashMap<>(); 096 if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>(); 097 098 //requiredExclusions.remove(origin); 099 int totalTargets = targets.size(); 100 LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8); 101 102 if(totalTargets == 0) 103 return bestPoints; 104 105 if(radius == 0) 106 { 107 for(Coord p : targets) 108 { 109 ArrayList<Coord> ap = new ArrayList<>(); 110 ap.add(p); 111 bestPoints.put(p, ap); 112 } 113 return bestPoints; 114 } 115 Coord[] ts = targets.toArray(new Coord[targets.size()]); 116 Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]); 117 Coord t = exs[0]; 118 119 double[][][] compositeMap = new double[ts.length][dungeon.length][dungeon[0].length]; 120 121 char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length]; 122 for (int i = 0; i < dungeon.length; i++) { 123 System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length); 124 } 125 double[][] tmpfov; 126 Coord tempPt = Coord.get(0, 0); 127 for (int i = 0; i < exs.length; ++i) { 128 t = exs[i]; 129 130 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 131 for (int x = 0; x < dungeon.length; x++) { 132 for (int y = 0; y < dungeon[x].length; y++) { 133 tempPt = Coord.get(x, y); 134 dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y]; 135 } 136 } 137 } 138 139 t = ts[0]; 140 141 DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN; 142 if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV; 143 else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN; 144 145 for (int i = 0; i < ts.length; ++i) { 146 DijkstraMap dm = new DijkstraMap(dungeon, dmm); 147 148 t = ts[i]; 149 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 150 151 double dist = 0.0; 152 for (int x = 0; x < dungeon.length; x++) { 153 for (int y = 0; y < dungeon[x].length; y++) { 154 if (tmpfov[x][y] > 0.0) { 155 dist = reach.metric.radius(origin.x, origin.y, x, y); 156 if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) 157 compositeMap[i][x][y] = dm.physicalMap[x][y]; 158 else 159 compositeMap[i][x][y] = DijkstraMap.WALL; 160 } 161 else compositeMap[i][x][y] = DijkstraMap.WALL; 162 } 163 } 164 if(compositeMap[i][ts[i].x][ts[i].y] > DijkstraMap.FLOOR) 165 { 166 for (int x = 0; x < dungeon.length; x++) { 167 Arrays.fill(compositeMap[i][x], 99999.0); 168 } 169 continue; 170 } 171 172 173 dm.initialize(compositeMap[i]); 174 dm.setGoal(t); 175 dm.scan(null); 176 for (int x = 0; x < dungeon.length; x++) { 177 for (int y = 0; y < dungeon[x].length; y++) { 178 compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 99999.0; 179 } 180 } 181 } 182 double bestQuality = 99999 * ts.length; 183 double[][] qualityMap = new double[dungeon.length][dungeon[0].length]; 184 for (int x = 0; x < qualityMap.length; x++) { 185 for (int y = 0; y < qualityMap[x].length; y++) { 186 qualityMap[x][y] = 0.0; 187 long bits = 0; 188 for (int i = 0; i < ts.length; ++i) { 189 qualityMap[x][y] += compositeMap[i][x][y]; 190 if(compositeMap[i][x][y] < 99999.0 && i < 63) 191 bits |= 1 << i; 192 } 193 if(qualityMap[x][y] < bestQuality) 194 { 195 ArrayList<Coord> ap = new ArrayList<>(); 196 197 for (int i = 0; i < ts.length && i < 63; ++i) { 198 if((bits & (1 << i)) != 0) 199 ap.add(ts[i]); 200 } 201 202 if(ap.size() > 0) { 203 bestQuality = qualityMap[x][y]; 204 bestPoints.clear(); 205 bestPoints.put(Coord.get(x, y), ap); 206 } } 207 else if(qualityMap[x][y] == bestQuality) 208 { 209 ArrayList<Coord> ap = new ArrayList<>(); 210 211 for (int i = 0; i < ts.length && i < 63; ++i) { 212 if((bits & (1 << i)) != 0) 213 ap.add(ts[i]); 214 } 215 216 if (ap.size() > 0) { 217 bestPoints.put(Coord.get(x, y), ap); 218 } 219 } 220 } 221 } 222 223 return bestPoints; 224 } 225 226 227 @Override 228 public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> priorityTargets, Set<Coord> lesserTargets, Set<Coord> requiredExclusions) { 229 if(priorityTargets == null) 230 return idealLocations(lesserTargets, requiredExclusions); 231 if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>(); 232 233 //requiredExclusions.remove(origin); 234 int totalTargets = priorityTargets.size() + lesserTargets.size(); 235 LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8); 236 237 if(totalTargets == 0) 238 return bestPoints; 239 240 if(radius == 0) 241 { 242 for(Coord p : priorityTargets) 243 { 244 ArrayList<Coord> ap = new ArrayList<>(); 245 ap.add(p); 246 bestPoints.put(p, ap); 247 } 248 return bestPoints; 249 } 250 Coord[] pts = priorityTargets.toArray(new Coord[priorityTargets.size()]); 251 Coord[] lts = lesserTargets.toArray(new Coord[lesserTargets.size()]); 252 Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]); 253 Coord t = exs[0]; 254 255 double[][][] compositeMap = new double[totalTargets][dungeon.length][dungeon[0].length]; 256 257 char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length], 258 dungeonPriorities = new char[dungeon.length][dungeon[0].length]; 259 for (int i = 0; i < dungeon.length; i++) { 260 System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length); 261 Arrays.fill(dungeonPriorities[i], '#'); 262 } 263 double[][] tmpfov; 264 Coord tempPt = Coord.get(0, 0); 265 for (int i = 0; i < exs.length; ++i) { 266 t = exs[i]; 267 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 268 for (int x = 0; x < dungeon.length; x++) { 269 for (int y = 0; y < dungeon[x].length; y++) { 270 tempPt = Coord.get(x, y); 271 dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y]; 272 } 273 } 274 } 275 276 t = pts[0]; 277 278 DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN; 279 if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV; 280 else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN; 281 282 for (int i = 0; i < pts.length; ++i) { 283 DijkstraMap dm = new DijkstraMap(dungeon, dmm); 284 t = pts[i]; 285 286 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 287 288 double dist = 0.0; 289 for (int x = 0; x < dungeon.length; x++) { 290 for (int y = 0; y < dungeon[x].length; y++) { 291 if (tmpfov[x][y] > 0.0){ 292 dist = reach.metric.radius(origin.x, origin.y, x, y); 293 if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) { 294 compositeMap[i][x][y] = dm.physicalMap[x][y]; 295 dungeonPriorities[x][y] = dungeon[x][y]; 296 } 297 else 298 compositeMap[i][x][y] = DijkstraMap.WALL; 299 } 300 else compositeMap[i][x][y] = DijkstraMap.WALL; 301 } 302 } 303 if(compositeMap[i][t.x][t.y] > DijkstraMap.FLOOR) 304 { 305 for (int x = 0; x < dungeon.length; x++) { 306 Arrays.fill(compositeMap[i][x], 399999.0); 307 } 308 continue; 309 } 310 311 312 dm.initialize(compositeMap[i]); 313 dm.setGoal(t); 314 dm.scan(null); 315 for (int x = 0; x < dungeon.length; x++) { 316 for (int y = 0; y < dungeon[x].length; y++) { 317 compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 399999.0; 318 } 319 } 320 dm.resetMap(); 321 dm.clearGoals(); 322 } 323 324 t = lts[0]; 325 326 for (int i = pts.length; i < totalTargets; ++i) { 327 DijkstraMap dm = new DijkstraMap(dungeon, dmm); 328 t = lts[i - pts.length]; 329 330 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 331 332 double dist = 0.0; 333 for (int x = 0; x < dungeon.length; x++) { 334 for (int y = 0; y < dungeon[x].length; y++) { 335 if (tmpfov[x][y] > 0.0){ 336 dist = reach.metric.radius(origin.x, origin.y, x, y); 337 if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) 338 compositeMap[i][x][y] = dm.physicalMap[x][y]; 339 else 340 compositeMap[i][x][y] = DijkstraMap.WALL; 341 } 342 else compositeMap[i][x][y] = DijkstraMap.WALL; 343 } 344 } 345 if(compositeMap[i][t.x][t.y] > DijkstraMap.FLOOR) 346 { 347 for (int x = 0; x < dungeon.length; x++) 348 { 349 Arrays.fill(compositeMap[i][x], 99999.0); 350 } 351 continue; 352 } 353 354 355 dm.initialize(compositeMap[i]); 356 dm.setGoal(t); 357 dm.scan(null); 358 for (int x = 0; x < dungeon.length; x++) { 359 for (int y = 0; y < dungeon[x].length; y++) { 360 compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR && dungeonCopy[x][y] != '!' && dungeonPriorities[x][y] != '#') ? dm.gradientMap[x][y] : 99999.0; 361 } 362 } 363 dm.resetMap(); 364 dm.clearGoals(); 365 } 366 double bestQuality = 99999 * lts.length + 399999 * pts.length; 367 double[][] qualityMap = new double[dungeon.length][dungeon[0].length]; 368 for (int x = 0; x < qualityMap.length; x++) { 369 for (int y = 0; y < qualityMap[x].length; y++) { 370 qualityMap[x][y] = 0.0; 371 long pbits = 0, lbits = 0; 372 for (int i = 0; i < pts.length; ++i) { 373 qualityMap[x][y] += compositeMap[i][x][y]; 374 if(compositeMap[i][x][y] < 399999.0 && i < 63) 375 pbits |= 1 << i; 376 } 377 for (int i = pts.length; i < totalTargets; ++i) { 378 qualityMap[x][y] += compositeMap[i][x][y]; 379 if(compositeMap[i][x][y] < 99999.0 && i < 63) 380 lbits |= 1 << i; 381 } 382 if(qualityMap[x][y] < bestQuality) 383 { 384 ArrayList<Coord> ap = new ArrayList<>(); 385 386 for (int i = 0; i < pts.length && i < 63; ++i) { 387 if((pbits & (1 << i)) != 0) 388 ap.add(pts[i]); 389 } 390 for (int i = pts.length; i < totalTargets && i < 63; ++i) { 391 if((lbits & (1 << i)) != 0) 392 ap.add(lts[i - pts.length]); 393 } 394 395 if(ap.size() > 0) { 396 bestQuality = qualityMap[x][y]; 397 bestPoints.clear(); 398 bestPoints.put(Coord.get(x, y), ap); 399 } 400 } 401 else if(qualityMap[x][y] == bestQuality) 402 { 403 ArrayList<Coord> ap = new ArrayList<>(); 404 405 for (int i = 0; i < pts.length && i < 63; ++i) { 406 if ((pbits & (1 << i)) != 0) { 407 ap.add(pts[i]); 408 ap.add(pts[i]); 409 ap.add(pts[i]); 410 ap.add(pts[i]); 411 } 412 } 413 for (int i = pts.length; i < totalTargets && i < 63; ++i) { 414 if((lbits & (1 << i)) != 0) 415 ap.add(lts[i - pts.length]); 416 } 417 418 if (ap.size() > 0) { 419 bestPoints.put(Coord.get(x, y), ap); 420 } 421 } 422 } 423 } 424 425 return bestPoints; 426 } 427 428 /* 429 @Override 430 public ArrayList<ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) { 431 int totalTargets = targets.size() + 1; 432 int maxEffect = (int)radiusType.volume2D(radius); 433 ArrayList<ArrayList<Coord>> locs = new ArrayList<ArrayList<Coord>>(totalTargets); 434 435 for(int i = 0; i < totalTargets; i++) 436 { 437 locs.add(new ArrayList<Coord>(maxEffect)); 438 } 439 if(totalTargets == 1) 440 return locs; 441 442 int ctr = 0; 443 if(radius < 1) 444 { 445 locs.get(totalTargets - 2).addAll(targets); 446 return locs; 447 } 448 449 boolean[][] tested = new boolean[dungeon.length][dungeon[0].length]; 450 for (int x = 1; x < dungeon.length - 1; x += radius) { 451 BY_POINT: 452 for (int y = 1; y < dungeon[x].length - 1; y += radius) { 453 for(Coord ex : requiredExclusions) 454 { 455 if(radiusType.radius(x, y, ex.x, ex.y) <= radius) 456 continue BY_POINT; 457 } 458 ctr = 0; 459 for(Coord tgt : targets) 460 { 461 if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius) 462 ctr++; 463 } 464 if(ctr > 0) 465 locs.get(totalTargets - ctr).add(Coord.get(x, y)); 466 } 467 } 468 Coord it; 469 for(int t = 0; t < totalTargets - 1; t++) 470 { 471 if(locs.get(t).size() > 0) { 472 int numPoints = locs.get(t).size(); 473 for (int i = 0; i < numPoints; i++) { 474 it = locs.get(t).get(i); 475 for (int x = Math.max(1, it.x - radius / 2); x < it.x + (radius + 1) / 2 && x < dungeon.length - 1; x++) { 476 BY_POINT: 477 for (int y = Math.max(1, it.y - radius / 2); y <= it.y + (radius - 1) / 2 && y < dungeon[0].length - 1; y++) 478 { 479 if(tested[x][y]) 480 continue; 481 tested[x][y] = true; 482 483 for(Coord ex : requiredExclusions) 484 { 485 if(radiusType.radius(x, y, ex.x, ex.y) <= radius) 486 continue BY_POINT; 487 } 488 489 ctr = 0; 490 for(Coord tgt : targets) 491 { 492 if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius) 493 ctr++; 494 } 495 if(ctr > 0) 496 locs.get(totalTargets - ctr).add(Coord.get(x, y)); 497 } 498 } 499 } 500 } 501 } 502 return locs; 503 } 504*/ 505 @Override 506 public void setMap(char[][] map) { 507 this.map = DungeonUtility.generateResistances(map); 508 dungeon = map; 509 } 510 511 @Override 512 public LinkedHashMap<Coord, Double> findArea() { 513 return AreaUtils.arrayToHashMap(fov.calculateFOV(null, center.x, center.y, radius, radiusType)); 514 } 515 516 517 @Override 518 public Coord getOrigin() { 519 return origin; 520 } 521 522 @Override 523 public void setOrigin(Coord origin) { 524 this.origin = origin; 525 526 } 527 528 @Override 529 public AimLimit getLimitType() { 530 return reach.limit; 531 } 532 533 @Override 534 public int getMinRange() { 535 return reach.minDistance; 536 } 537 538 @Override 539 public int getMaxRange() { 540 return reach.maxDistance; 541 } 542 543 @Override 544 public Radius getMetric() { 545 return reach.metric; 546 } 547 548 /** 549 * Gets the same values returned by getLimitType(), getMinRange(), getMaxRange(), and getMetric() bundled into one 550 * Reach object. 551 * 552 * @return a non-null Reach object. 553 */ 554 @Override 555 public Reach getReach() { 556 return reach; 557 } 558 559 @Override 560 public void setLimitType(AimLimit limitType) { 561 reach.limit = limitType; 562 563 } 564 565 @Override 566 public void setMinRange(int minRange) { 567 reach.minDistance = minRange; 568 } 569 570 @Override 571 public void setMaxRange(int maxRange) { 572 reach.maxDistance = maxRange; 573 574 } 575 576 @Override 577 public void setMetric(Radius metric) { 578 reach.metric = metric; 579 } 580 581 /** 582 * Sets the same values as setLimitType(), setMinRange(), setMaxRange(), and setMetric() using one Reach object. 583 * 584 * @param reach a non-null Reach object. 585 */ 586 @Override 587 public void setReach(Reach reach) { 588 if(reach != null) 589 this.reach = reach; 590 } 591 592 /** 593 * If you use FOVCache to pre-compute FOV maps for a level, you can share the speedup from using the cache with 594 * some AOE implementations that rely on FOV. Not all implementations need to actually make use of the cache, but 595 * those that use FOV for calculations should benefit. The cache parameter this receives should have completed its 596 * calculations, which can be confirmed by calling awaitCache(). Ideally, the FOVCache will have done its initial 597 * calculations in another thread while the previous level or menu was being displayed, and awaitCache() will only 598 * be a formality. 599 * 600 * @param cache The FOVCache for the current level; can be null to stop using the cache 601 */ 602 @GwtIncompatible 603 @Override 604 public void setCache(FOVCache cache) { 605 fov = cache; 606 } 607 608}