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 will blast outward and somewhat around corners/obstacles, 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 greater than 0.0 and less than or 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 BlastAOE implements AOE { 023 private FOV fov; 024 private Coord center, origin = null; 025 private int radius; 026 private double[][] map; 027 private char[][] dungeon; 028 private Radius radiusType; 029 030 private Reach reach = new Reach(1, 1, Radius.SQUARE, null); 031 032 public BlastAOE(Coord center, int radius, Radius radiusType) 033 { 034 fov = new FOV(FOV.RIPPLE_LOOSE); 035 this.center = center; 036 this.radius = radius; 037 this.radiusType = radiusType; 038 } 039 public BlastAOE(Coord center, int radius, Radius radiusType, int minRange, int maxRange) 040 { 041 fov = new FOV(FOV.RIPPLE_LOOSE); 042 this.center = center; 043 this.radius = radius; 044 this.radiusType = radiusType; 045 reach.minDistance = minRange; 046 reach.maxDistance = maxRange; 047 } 048 049 public Coord getCenter() { 050 return center; 051 } 052 053 public void setCenter(Coord center) { 054 055 if (map != null && center.isWithin(map.length, map[0].length) && 056 AreaUtils.verifyReach(reach, origin, center)) 057 { 058 this.center = center; 059 } 060 } 061 062 public int getRadius() { 063 return radius; 064 } 065 066 public void setRadius(int radius) { 067 this.radius = radius; 068 } 069 070 public Radius getRadiusType() { 071 return radiusType; 072 } 073 074 public void setRadiusType(Radius radiusType) { 075 this.radiusType = radiusType; 076 } 077 078 @Override 079 public void shift(Coord aim) { 080 setCenter(aim); 081 } 082 083 @Override 084 public boolean mayContainTarget(Set<Coord> targets) { 085 for (Coord p : targets) 086 { 087 if(radiusType.radius(center.x, center.y, p.x, p.y) <= radius) 088 return true; 089 } 090 return false; 091 } 092 093 @Override 094 public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) { 095 if(targets == null) 096 return new LinkedHashMap<>(); 097 if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>(); 098 099 //requiredExclusions.remove(origin); 100 int totalTargets = targets.size(); 101 LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8); 102 103 if(totalTargets == 0) 104 return bestPoints; 105 106 if(radius == 0) 107 { 108 for(Coord p : targets) 109 { 110 ArrayList<Coord> ap = new ArrayList<>(); 111 ap.add(p); 112 bestPoints.put(p, ap); 113 } 114 return bestPoints; 115 } 116 Coord[] ts = targets.toArray(new Coord[targets.size()]); 117 Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]); 118 Coord t = exs[0]; 119 120 double[][][] compositeMap = new double[ts.length][dungeon.length][dungeon[0].length]; 121 122 char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length]; 123 for (int i = 0; i < dungeon.length; i++) { 124 System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length); 125 } 126 double[][] tmpfov; 127 Coord tempPt = Coord.get(0, 0); 128 for (int i = 0; i < exs.length; ++i) { 129 t = exs[i]; 130 131 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 132 133 for (int x = 0; x < dungeon.length; x++) { 134 for (int y = 0; y < dungeon[x].length; y++) { 135 tempPt = Coord.get(x, y); 136 dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y]; 137 } 138 } 139 } 140 141 t = ts[0]; 142 143 DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN; 144 if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV; 145 else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN; 146 147 for (int i = 0; i < ts.length; i++) { 148 DijkstraMap dm = new DijkstraMap(dungeon, dmm); 149 150 t = ts[i]; 151 152 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 153 154 for (int x = 0; x < dungeon.length; x++) { 155 for (int y = 0; y < dungeon[x].length; y++) { 156 compositeMap[i][x][y] = (tmpfov[x][y] > 0.0) ? dm.physicalMap[x][y] : DijkstraMap.WALL; 157 } 158 } 159 160 161 double dist = 0.0; 162 for (int x = 0; x < dungeon.length; x++) { 163 for (int y = 0; y < dungeon[x].length; y++) { 164 if (tmpfov[x][y] > 0.0){ 165 dist = reach.metric.radius(origin.x, origin.y, x, y); 166 if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) 167 compositeMap[i][x][y] = dm.physicalMap[x][y]; 168 else 169 compositeMap[i][x][y] = DijkstraMap.WALL; 170 } 171 else compositeMap[i][x][y] = DijkstraMap.WALL; 172 } 173 } 174 if(compositeMap[i][ts[i].x][ts[i].y] > DijkstraMap.FLOOR) 175 { 176 for (int x = 0; x < dungeon.length; x++) { 177 Arrays.fill(compositeMap[i][x], 99999.0); 178 } 179 continue; 180 } 181 182 183 dm.initialize(compositeMap[i]); 184 dm.setGoal(t); 185 dm.scan(null); 186 for (int x = 0; x < dungeon.length; x++) { 187 for (int y = 0; y < dungeon[x].length; y++) { 188 compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 99999.0; 189 } 190 } 191 } 192 double bestQuality = 99999 * ts.length; 193 double[][] qualityMap = new double[dungeon.length][dungeon[0].length]; 194 for (int x = 0; x < qualityMap.length; x++) { 195 for (int y = 0; y < qualityMap[x].length; y++) { 196 qualityMap[x][y] = 0.0; 197 long bits = 0; 198 for (int i = 0; i < ts.length; i++) { 199 qualityMap[x][y] += compositeMap[i][x][y]; 200 if(compositeMap[i][x][y] < 99999.0 && i < 63) 201 bits |= 1 << i; 202 } 203 if(qualityMap[x][y] < bestQuality) 204 { 205 ArrayList<Coord> ap = new ArrayList<>(); 206 207 for (int i = 0; i < ts.length && i < 63; ++i) { 208 if((bits & (1 << i)) != 0) 209 ap.add(ts[i]); 210 } 211 if(ap.size() > 0) 212 { 213 bestQuality = qualityMap[x][y]; 214 bestPoints.clear(); 215 bestPoints.put(Coord.get(x, y), ap); 216 } 217 } 218 else if(qualityMap[x][y] == bestQuality) { 219 ArrayList<Coord> ap = new ArrayList<>(); 220 221 for (int i = 0; i < ts.length && i < 63; ++i) { 222 if ((bits & (1 << i)) != 0) 223 ap.add(ts[i]); 224 } 225 if (ap.size() > 0) { 226 bestPoints.put(Coord.get(x, y), ap); 227 } 228 } 229 } 230 } 231 232 return bestPoints; 233 } 234 235 @Override 236 public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> priorityTargets, Set<Coord> lesserTargets, Set<Coord> requiredExclusions) { 237 if(priorityTargets == null) 238 return idealLocations(lesserTargets, requiredExclusions); 239 if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>(); 240 241 //requiredExclusions.remove(origin); 242 int totalTargets = priorityTargets.size() + lesserTargets.size(); 243 LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8); 244 245 if(totalTargets == 0) 246 return bestPoints; 247 248 if(radius == 0) 249 { 250 for(Coord p : priorityTargets) 251 { 252 ArrayList<Coord> ap = new ArrayList<>(); 253 ap.add(p); 254 bestPoints.put(p, ap); 255 } 256 return bestPoints; 257 } 258 Coord[] pts = priorityTargets.toArray(new Coord[priorityTargets.size()]); 259 Coord[] lts = lesserTargets.toArray(new Coord[lesserTargets.size()]); 260 Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]); 261 Coord t = exs[0]; 262 263 double[][][] compositeMap = new double[totalTargets][dungeon.length][dungeon[0].length]; 264 265 char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length], 266 dungeonPriorities = new char[dungeon.length][dungeon[0].length]; 267 for (int i = 0; i < dungeon.length; i++) { 268 System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length); 269 Arrays.fill(dungeonPriorities[i], '#'); 270 } 271 double[][] tmpfov; 272 Coord tempPt = Coord.get(0, 0); 273 for (int i = 0; i < exs.length; ++i) { 274 t = exs[i]; 275 276 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 277 for (int x = 0; x < dungeon.length; x++) { 278 for (int y = 0; y < dungeon[x].length; y++) { 279 tempPt = Coord.get(x, y); 280 dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y]; 281 } 282 } 283 } 284 285 t = pts[0]; 286 287 DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN; 288 if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV; 289 else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN; 290 291 for (int i = 0; i < pts.length; ++i) { 292 DijkstraMap dm = new DijkstraMap(dungeon, dmm); 293 294 t = pts[i]; 295 296 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 297 298 double dist = 0.0; 299 for (int x = 0; x < dungeon.length; x++) { 300 for (int y = 0; y < dungeon[x].length; y++) { 301 if (tmpfov[x][y] > 0.0){ 302 dist = reach.metric.radius(origin.x, origin.y, x, y); 303 if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) { 304 compositeMap[i][x][y] = dm.physicalMap[x][y]; 305 dungeonPriorities[x][y] = dungeon[x][y]; 306 } 307 else 308 compositeMap[i][x][y] = DijkstraMap.WALL; 309 } 310 else compositeMap[i][x][y] = DijkstraMap.WALL; 311 } 312 } 313 if(compositeMap[i][pts[i].x][pts[i].y] > DijkstraMap.FLOOR) 314 { 315 for (int x = 0; x < dungeon.length; x++) { 316 Arrays.fill(compositeMap[i][x], 399999.0); 317 } 318 continue; 319 } 320 321 dm.initialize(compositeMap[i]); 322 dm.setGoal(t); 323 dm.scan(null); 324 for (int x = 0; x < dungeon.length; x++) { 325 for (int y = 0; y < dungeon[x].length; y++) { 326 compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 399999.0; 327 } 328 } 329 } 330 331 t = lts[0]; 332 333 for (int i = pts.length; i < totalTargets; ++i) { 334 DijkstraMap dm = new DijkstraMap(dungeon, dmm); 335 336 t = lts[i - pts.length]; 337 338 tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType); 339 340 double dist = 0.0; 341 for (int x = 0; x < dungeon.length; x++) { 342 for (int y = 0; y < dungeon[x].length; y++) { 343 if (tmpfov[x][y] > 0.0){ 344 dist = reach.metric.radius(origin.x, origin.y, x, y); 345 if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) 346 compositeMap[i][x][y] = dm.physicalMap[x][y]; 347 else 348 compositeMap[i][x][y] = DijkstraMap.WALL; 349 } 350 else compositeMap[i][x][y] = DijkstraMap.WALL; 351 } 352 } 353 if(compositeMap[i][lts[i - pts.length].x][lts[i - pts.length].y] > DijkstraMap.FLOOR) 354 { 355 for (int x = 0; x < dungeon.length; x++) 356 { 357 Arrays.fill(compositeMap[i][x], 99999.0); 358 } 359 continue; 360 } 361 362 dm.initialize(compositeMap[i]); 363 dm.setGoal(t); 364 dm.scan(null); 365 for (int x = 0; x < dungeon.length; x++) { 366 for (int y = 0; y < dungeon[x].length; y++) { 367 compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR && dungeonCopy[x][y] != '!' && dungeonPriorities[x][y] != '#') ? dm.gradientMap[x][y] : 99999.0; 368 } 369 } 370 } 371 double bestQuality = 99999 * lts.length + 399999 * pts.length; 372 double[][] qualityMap = new double[dungeon.length][dungeon[0].length]; 373 for (int x = 0; x < qualityMap.length; x++) { 374 for (int y = 0; y < qualityMap[x].length; y++) { 375 qualityMap[x][y] = 0.0; 376 long pbits = 0, lbits = 0; 377 for (int i = 0; i < pts.length; ++i) { 378 qualityMap[x][y] += compositeMap[i][x][y]; 379 if(compositeMap[i][x][y] < 399999.0 && i < 63) 380 pbits |= 1 << i; 381 } 382 for (int i = pts.length; i < totalTargets; ++i) { 383 qualityMap[x][y] += compositeMap[i][x][y]; 384 if(compositeMap[i][x][y] < 99999.0 && i < 63) 385 lbits |= 1 << i; 386 } 387 if(qualityMap[x][y] < bestQuality) 388 { 389 ArrayList<Coord> ap = new ArrayList<>(); 390 391 for (int i = 0; i < pts.length && i < 63; ++i) { 392 if((pbits & (1 << i)) != 0) 393 ap.add(pts[i]); 394 } 395 for (int i = pts.length; i < totalTargets && i < 63; ++i) { 396 if((lbits & (1 << i)) != 0) 397 ap.add(lts[i - pts.length]); 398 } 399 if(ap.size() > 0) { 400 bestQuality = qualityMap[x][y]; 401 bestPoints.clear(); 402 bestPoints.put(Coord.get(x, y), ap); 403 } 404 } 405 else if(qualityMap[x][y] == bestQuality) { 406 ArrayList<Coord> ap = new ArrayList<>(); 407 408 for (int i = 0; i < pts.length && i < 63; ++i) { 409 if ((pbits & (1 << i)) != 0) { 410 ap.add(pts[i]); 411 ap.add(pts[i]); 412 ap.add(pts[i]); 413 ap.add(pts[i]); 414 } 415 } 416 for (int i = pts.length; i < totalTargets && i < 63; ++i) { 417 if ((lbits & (1 << i)) != 0) 418 ap.add(lts[i - pts.length]); 419 } 420 if (ap.size() > 0) { 421 bestPoints.put(Coord.get(x, y), ap); 422 } 423 } 424 } 425 } 426 427 return bestPoints; 428 } 429 430 /* 431 @Override 432 public ArrayList<ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) { 433 int totalTargets = targets.size() + 1; 434 int maxEffect = (int)radiusType.volume2D(radius); 435 ArrayList<ArrayList<Coord>> locs = new ArrayList<ArrayList<Coord>>(totalTargets); 436 437 for(int i = 0; i < totalTargets; i++) 438 { 439 locs.add(new ArrayList<Coord>(maxEffect)); 440 } 441 if(totalTargets == 1) 442 return locs; 443 int ctr = 0; 444 if(radius < 1) 445 { 446 locs.get(totalTargets - 2).addAll(targets); 447 return locs; 448 } 449 450 boolean[][] tested = new boolean[dungeon.length][dungeon[0].length]; 451 for (int x = 1; x < dungeon.length - 1; x += radius) { 452 BY_POINT: 453 for (int y = 1; y < dungeon[x].length - 1; y += radius) { 454 for(Coord ex : requiredExclusions) 455 { 456 if(radiusType.radius(x, y, ex.x, ex.y) <= radius) 457 continue BY_POINT; 458 } 459 ctr = 0; 460 for(Coord tgt : targets) 461 { 462 if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius) 463 ctr++; 464 } 465 if(ctr > 0) 466 locs.get(totalTargets - ctr).add(Coord.get(x, y)); 467 } 468 } 469 Coord it; 470 for(int t = 0; t < totalTargets - 1; t++) 471 { 472 if(locs.get(t).size() > 0) { 473 int numPoints = locs.get(t).size(); 474 for (int i = 0; i < numPoints; i++) { 475 it = locs.get(t).get(i); 476 for (int x = Math.max(1, it.x - radius / 2); x < it.x + (radius + 1) / 2 && x < dungeon.length - 1; x++) { 477 BY_POINT: 478 for (int y = Math.max(1, it.y - radius / 2); y <= it.y + (radius - 1) / 2 && y < dungeon[0].length - 1; y++) 479 { 480 if(tested[x][y]) 481 continue; 482 tested[x][y] = true; 483 484 for(Coord ex : requiredExclusions) 485 { 486 if(radiusType.radius(x, y, ex.x, ex.y) <= radius) 487 continue BY_POINT; 488 } 489 490 ctr = 0; 491 for(Coord tgt : targets) 492 { 493 if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius) 494 ctr++; 495 } 496 if(ctr > 0) 497 locs.get(totalTargets - ctr).add(Coord.get(x, y)); 498 } 499 } 500 } 501 } 502 } 503 return locs; 504 } 505*/ 506 @Override 507 public void setMap(char[][] map) { 508 this.map = DungeonUtility.generateResistances(map); 509 dungeon = map; 510 } 511 512 @Override 513 public LinkedHashMap<Coord, Double> findArea() { 514 return AreaUtils.arrayToHashMap(fov.calculateFOV(map, center.x, center.y, radius, radiusType)); 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}