001package squidpony.squidai; 002 003import squidpony.GwtCompatibility; 004import squidpony.annotation.GwtIncompatible; 005import squidpony.squidgrid.*; 006import squidpony.squidmath.*; 007 008import java.util.*; 009 010/** 011 * An alternative to AStarSearch when you want to fully explore a search space, or when you want a gradient floodfill. 012 * If you can't remember how to spell this, just remember: Does It Just Know Stuff? That's Really Awesome! 013 * Created by Tommy Ettinger on 4/4/2015. 014 */ 015public class DijkstraMap { 016 /** 017 * The type of heuristic to use. 018 */ 019 public enum Measurement { 020 021 /** 022 * The distance it takes when only the four primary directions can be 023 * moved in. The default. 024 */ 025 MANHATTAN, 026 /** 027 * The distance it takes when diagonal movement costs the same as 028 * cardinal movement. 029 */ 030 CHEBYSHEV, 031 /** 032 * The distance it takes as the crow flies. This will NOT affect movement cost when calculating a path, 033 * only the preferred squares to travel to (resulting in drastically more reasonable-looking paths). 034 */ 035 EUCLIDEAN 036 } 037 038 /** 039 * This affects how distance is measured on diagonal directions vs. orthogonal directions. MANHATTAN should form a 040 * diamond shape on a featureless map, while CHEBYSHEV and EUCLIDEAN will form a square. EUCLIDEAN does not affect 041 * the length of paths, though it will change the DijkstraMap's gradientMap to have many non-integer values, and 042 * that in turn will make paths this finds much more realistic and smooth (favoring orthogonal directions unless a 043 * diagonal one is a better option). 044 */ 045 public Measurement measurement = Measurement.MANHATTAN; 046 047 048 /** 049 * Stores which parts of the map are accessible and which are not. Should not be changed unless the actual physical 050 * terrain has changed. You should call initialize() with a new map instead of changing this directly. 051 */ 052 public double[][] physicalMap; 053 /** 054 * The frequently-changing values that are often the point of using this class; goals will have a value of 0, and 055 * any cells that can have a character reach a goal in n steps will have a value of n. Cells that cannot be 056 * entered because they are solid will have a very high value equal to the WALL constant in this class, and cells 057 * that cannot be entered because they cannot reach a goal will have a different very high value equal to the 058 * DARK constant in this class. 059 */ 060 public double[][] gradientMap; 061 /** 062 * A 2D array of modifiers to apply to the perceived safety of an area; modifiers go up when deteriorate() is 063 * called, which makes the cells specified in that method call more dangerous (usually because staying in one place 064 * is perceived as risky). 065 */ 066 public double[][] safetyMap; 067 /** 068 * This stores the entry cost multipliers for each cell; that is, a value of 1.0 is a normal, unmodified cell, but 069 * a value of 0.5 can be entered easily (two cells of its cost can be entered for the cost of one 1.0 cell), and a 070 * value of 2.0 can only be entered with difficulty (one cell of its cost can be entered for the cost of two 1.0 071 * cells). Unlike the measurement field, this does affect the length of paths, as well as the numbers assigned 072 * to gradientMap during a scan. The values for walls are identical to the value used by gradientMap, that is, this 073 * class' WALL static final field. Floors, however, are never given FLOOR as a value, and default to 1.0 . 074 */ 075 public double[][] costMap = null; 076 /** 077 * Height of the map. Exciting stuff. Don't change this, instead call initialize(). 078 */ 079 public int height; 080 /** 081 * Width of the map. Exciting stuff. Don't change this, instead call initialize(). 082 */ 083 public int width; 084 /** 085 * The latest path that was obtained by calling findPath(). It will not contain the value passed as a starting 086 * cell; only steps that require movement will be included, and so if the path has not been found or a valid 087 * path toward a goal is impossible, this ArrayList will be empty. 088 */ 089 public ArrayList<Coord> path = new ArrayList<>(); 090 /** 091 * Goals are always marked with 0. 092 */ 093 public static final double GOAL = 0.0; 094 /** 095 * Floor cells, which include any walkable cell, are marked with a high number equal to 999200.0 . 096 */ 097 public static final double FLOOR = 999200.0; 098 /** 099 * Walls, which are solid no-entry cells, are marked with a high number equal to 999500.0 . 100 */ 101 public static final double WALL = 999500.0; 102 /** 103 * This is used to mark cells that the scan couldn't reach, and these dark cells are marked with a high number 104 * equal to 999800.0 . 105 */ 106 public static final double DARK = 999800.0; 107 /** 108 * Goals that pathfinding will seek out. The Double value should almost always be 0.0 , the same as the static GOAL 109 * constant in this class. 110 */ 111 public LinkedHashMap<Coord, Double> goals; 112 private LinkedHashMap<Coord, Double> fresh, closed, open; 113 /** 114 * The RNG used to decide which one of multiple equally-short paths to take. 115 */ 116 public RNG rng; 117 private int frustration = 0; 118 public Coord[][] targetMap; 119 120 121 private boolean initialized = false; 122 123 124 private int mappedCount = 0; 125 126 public int getMappedCount() { 127 return mappedCount; 128 } 129 130 /** 131 * Construct a DijkstraMap without a level to actually scan. If you use this constructor, you must call an 132 * initialize() method before using this class. 133 */ 134 public DijkstraMap() { 135 rng = new RNG(new LightRNG()); 136 path = new ArrayList<>(); 137 138 goals = new LinkedHashMap<>(); 139 fresh = new LinkedHashMap<>(); 140 closed = new LinkedHashMap<>(); 141 open = new LinkedHashMap<>(); 142 } 143 144 /** 145 * Construct a DijkstraMap without a level to actually scan. This constructor allows you to specify an RNG before 146 * it is ever used in this class. If you use this constructor, you must call an initialize() method before using 147 * any other methods in the class. 148 */ 149 public DijkstraMap(RNG random) { 150 rng = random; 151 path = new ArrayList<>(); 152 153 goals = new LinkedHashMap<>(); 154 fresh = new LinkedHashMap<>(); 155 closed = new LinkedHashMap<>(); 156 open = new LinkedHashMap<>(); 157 } 158 159 /** 160 * Used to construct a DijkstraMap from the output of another. 161 * 162 * @param level 163 */ 164 public DijkstraMap(final double[][] level) { 165 rng = new RNG(new LightRNG()); 166 path = new ArrayList<>(); 167 168 goals = new LinkedHashMap<>(); 169 fresh = new LinkedHashMap<>(); 170 closed = new LinkedHashMap<>(); 171 open = new LinkedHashMap<>(); 172 initialize(level); 173 } 174 175 /** 176 * Used to construct a DijkstraMap from the output of another, specifying a distance calculation. 177 * 178 * @param level 179 * @param measurement 180 */ 181 public DijkstraMap(final double[][] level, Measurement measurement) { 182 rng = new RNG(new LightRNG()); 183 this.measurement = measurement; 184 path = new ArrayList<>(); 185 186 goals = new LinkedHashMap<>(); 187 fresh = new LinkedHashMap<>(); 188 closed = new LinkedHashMap<>(); 189 open = new LinkedHashMap<>(); 190 initialize(level); 191 } 192 193 /** 194 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 195 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 196 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 197 * map that can be used here. 198 * 199 * @param level 200 */ 201 public DijkstraMap(final char[][] level) { 202 rng = new RNG(new LightRNG()); 203 path = new ArrayList<>(); 204 205 goals = new LinkedHashMap<>(); 206 fresh = new LinkedHashMap<>(); 207 closed = new LinkedHashMap<>(); 208 open = new LinkedHashMap<>(); 209 initialize(level); 210 } 211 212 /** 213 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 214 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 215 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 216 * map that can be used here. Also takes an RNG that ensures predictable path choices given 217 * otherwise identical inputs and circumstances. 218 * 219 * @param level 220 * @param rng The RNG to use for certain decisions; only affects find* methods like findPath, not scan. 221 */ 222 public DijkstraMap(final char[][] level, RNG rng) { 223 this.rng = rng; 224 path = new ArrayList<>(); 225 226 goals = new LinkedHashMap<>(); 227 fresh = new LinkedHashMap<>(); 228 closed = new LinkedHashMap<>(); 229 open = new LinkedHashMap<>(); 230 initialize(level); 231 } 232 233 /** 234 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 235 * char[][] where one char means a wall and anything else is a walkable tile. If you only have 236 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 237 * map that can be used here. You can specify the character used for walls. 238 * 239 * @param level 240 */ 241 public DijkstraMap(final char[][] level, char alternateWall) { 242 rng = new RNG(new LightRNG()); 243 path = new ArrayList<>(); 244 245 goals = new LinkedHashMap<>(); 246 fresh = new LinkedHashMap<>(); 247 closed = new LinkedHashMap<>(); 248 open = new LinkedHashMap<>(); 249 initialize(level, alternateWall); 250 } 251 252 /** 253 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 254 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 255 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 256 * map that can be used here. This constructor specifies a distance measurement. 257 * 258 * @param level 259 * @param measurement 260 */ 261 public DijkstraMap(final char[][] level, Measurement measurement) { 262 rng = new RNG(new LightRNG()); 263 path = new ArrayList<>(); 264 this.measurement = measurement; 265 266 goals = new LinkedHashMap<>(); 267 fresh = new LinkedHashMap<>(); 268 closed = new LinkedHashMap<>(); 269 open = new LinkedHashMap<>(); 270 initialize(level); 271 } 272 273 /** 274 * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other 275 * char[][] where '#' means a wall and anything else is a walkable tile. If you only have 276 * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a 277 * map that can be used here. Also takes a distance measurement and an RNG that ensures 278 * predictable path choices given otherwise identical inputs and circumstances. 279 * 280 * @param level 281 * @param rng The RNG to use for certain decisions; only affects find* methods like findPath, not scan. 282 */ 283 public DijkstraMap(final char[][] level, Measurement measurement, RNG rng) { 284 this.rng = rng; 285 path = new ArrayList<>(); 286 this.measurement = measurement; 287 288 goals = new LinkedHashMap<>(); 289 fresh = new LinkedHashMap<>(); 290 closed = new LinkedHashMap<>(); 291 open = new LinkedHashMap<>(); 292 initialize(level); 293 } 294 295 /** 296 * Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given 297 * one when it was constructed, or because the contents of the terrain have changed permanently (not if a 298 * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). 299 * 300 * @param level 301 * @return 302 */ 303 public DijkstraMap initialize(final double[][] level) { 304 width = level.length; 305 height = level[0].length; 306 gradientMap = new double[width][height]; 307 safetyMap = new double[width][height]; 308 physicalMap = new double[width][height]; 309 costMap = new double[width][height]; 310 targetMap = new Coord[width][height]; 311 for (int x = 0; x < width; x++) { 312 System.arraycopy(level[x], 0, gradientMap[x], 0, height); 313 System.arraycopy(level[x], 0, physicalMap[x], 0, height); 314 Arrays.fill(costMap[x], 1.0); 315 } 316 initialized = true; 317 return this; 318 } 319 320 /** 321 * Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given 322 * one when it was constructed, or because the contents of the terrain have changed permanently (not if a 323 * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). 324 * 325 * @param level 326 * @return 327 */ 328 public DijkstraMap initialize(final char[][] level) { 329 width = level.length; 330 height = level[0].length; 331 gradientMap = new double[width][height]; 332 safetyMap = new double[width][height]; 333 physicalMap = new double[width][height]; 334 costMap = new double[width][height]; 335 targetMap = new Coord[width][height]; 336 for (int x = 0; x < width; x++) { 337 Arrays.fill(costMap[x], 1.0); 338 for (int y = 0; y < height; y++) { 339 double t = (level[x][y] == '#') ? WALL : FLOOR; 340 gradientMap[x][y] = t; 341 physicalMap[x][y] = t; 342 } 343 } 344 initialized = true; 345 return this; 346 } 347 348 /** 349 * Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given 350 * one when it was constructed, or because the contents of the terrain have changed permanently (not if a 351 * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). This 352 * initialize() method allows you to specify an alternate wall char other than the default character, '#' . 353 * 354 * @param level 355 * @param alternateWall 356 * @return 357 */ 358 public DijkstraMap initialize(final char[][] level, char alternateWall) { 359 width = level.length; 360 height = level[0].length; 361 gradientMap = new double[width][height]; 362 safetyMap = new double[width][height]; 363 physicalMap = new double[width][height]; 364 costMap = new double[width][height]; 365 targetMap = new Coord[width][height]; 366 for (int x = 0; x < width; x++) { 367 Arrays.fill(costMap[x], 1.0); 368 for (int y = 0; y < height; y++) { 369 double t = (level[x][y] == alternateWall) ? WALL : FLOOR; 370 gradientMap[x][y] = t; 371 physicalMap[x][y] = t; 372 } 373 } 374 initialized = true; 375 return this; 376 } 377 378 /** 379 * Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects 380 * a char[][] of the same exact dimensions as the 2D array that was used to previously initialize() this 381 * DijkstraMap, treating the '#' char as a wall (impassable) and anything else as having a normal cost to enter. 382 * The costs can be accessed later by using costMap directly (which will have a valid value when this does not 383 * throw an exception), or by calling setCost(). 384 * 385 * @param level a 2D char array that uses '#' for walls 386 * @return this DijkstraMap for chaining. 387 */ 388 public DijkstraMap initializeCost(final char[][] level) { 389 if (!initialized) throw new IllegalStateException("DijkstraMap must be initialized first!"); 390 for (int x = 0; x < width; x++) { 391 for (int y = 0; y < height; y++) { 392 costMap[x][y] = (level[x][y] == '#') ? WALL : 1.0; 393 } 394 } 395 return this; 396 } 397 398 /** 399 * Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects 400 * a char[][] of the same exact dimensions as the 2D array that was used to previously initialize() this 401 * DijkstraMap, treating the '#' char as a wall (impassable) and anything else as having a normal cost to enter. 402 * The costs can be accessed later by using costMap directly (which will have a valid value when this does not 403 * throw an exception), or by calling setCost(). 404 * <p/> 405 * This method allows you to specify an alternate wall char other than the default character, '#' . 406 * 407 * @param level a 2D char array that uses alternateChar for walls. 408 * @param alternateWall a char to use to represent walls. 409 * @return this DijkstraMap for chaining. 410 */ 411 public DijkstraMap initializeCost(final char[][] level, char alternateWall) { 412 if (!initialized) throw new IllegalStateException("DijkstraMap must be initialized first!"); 413 for (int x = 0; x < width; x++) { 414 for (int y = 0; y < height; y++) { 415 costMap[x][y] = (level[x][y] == alternateWall) ? WALL : 1.0; 416 } 417 } 418 return this; 419 } 420 421 /** 422 * Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects 423 * a double[][] of the same exact dimensions as the 2D array that was used to previously initialize() this 424 * DijkstraMap, using the exact values given in costs as the values to enter cells, even if they aren't what this 425 * class would assign normally -- walls and other impassable values should be given WALL as a value, however. 426 * The costs can be accessed later by using costMap directly (which will have a valid value when this does not 427 * throw an exception), or by calling setCost(). 428 * <p/> 429 * This method should be slightly more efficient than the other initializeCost methods. 430 * 431 * @param costs a 2D double array that already has the desired cost values 432 * @return this DijkstraMap for chaining. 433 */ 434 public DijkstraMap initializeCost(final double[][] costs) { 435 if (!initialized) throw new IllegalStateException("DijkstraMap must be initialized first!"); 436 costMap = new double[width][height]; 437 for (int x = 0; x < width; x++) { 438 System.arraycopy(costs[x], 0, costMap[x], 0, height); 439 } 440 return this; 441 } 442 443 /** 444 * Gets the appropriate DijkstraMap.Measurement to pass to a constructor if you already have a Radius. 445 * Matches SQUARE or CUBE to CHEBYSHEV, DIAMOND or OCTAHEDRON to MANHATTAN, and CIRCLE or SPHERE to EUCLIDEAN. 446 * 447 * @param radius the Radius to find the corresponding Measurement for 448 * @return a DijkstraMap.Measurement that matches radius; SQUARE to CHEBYSHEV, DIAMOND to MANHATTAN, etc. 449 */ 450 public static Measurement findMeasurement(Radius radius) { 451 if (radius.equals2D(Radius.SQUARE)) 452 return DijkstraMap.Measurement.CHEBYSHEV; 453 else if (radius.equals2D(Radius.DIAMOND)) 454 return DijkstraMap.Measurement.MANHATTAN; 455 else 456 return DijkstraMap.Measurement.EUCLIDEAN; 457 } 458 459 /** 460 * Gets the appropriate Radius corresponding to a DijkstraMap.Measurement. 461 * Matches CHEBYSHEV to SQUARE, MANHATTAN to DIAMOND, and EUCLIDEAN to CIRCLE. 462 * 463 * @param measurement the Measurement to find the corresponding Radius for 464 * @return a DijkstraMap.Measurement that matches radius; CHEBYSHEV to SQUARE, MANHATTAN to DIAMOND, etc. 465 */ 466 public static Radius findRadius(Measurement measurement) { 467 switch (measurement) { 468 case CHEBYSHEV: 469 return Radius.SQUARE; 470 case EUCLIDEAN: 471 return Radius.CIRCLE; 472 default: 473 return Radius.DIAMOND; 474 } 475 } 476 477 /** 478 * Resets the gradientMap to its original value from physicalMap. 479 */ 480 public void resetMap() { 481 if (!initialized) return; 482 for (int x = 0; x < width; x++) { 483 for (int y = 0; y < height; y++) { 484 gradientMap[x][y] = physicalMap[x][y]; 485 } 486 } 487 } 488 489 /** 490 * Resets the targetMap (which is only assigned in the first place if you use findTechniquePath() ). 491 */ 492 public void resetTargetMap() { 493 if (!initialized) return; 494 for (int x = 0; x < width; x++) { 495 for (int y = 0; y < height; y++) { 496 targetMap[x][y] = null; 497 } 498 } 499 } 500 501 /** 502 * Resets the targetMap (which is only assigned in the first place if you use findTechniquePath() ). 503 */ 504 public void resetSafetyMap() { 505 if (!initialized) return; 506 for (int x = 0; x < width; x++) { 507 for (int y = 0; y < height; y++) { 508 safetyMap[x][y] = 0.0; 509 } 510 } 511 } 512 513 /** 514 * Resets this DijkstraMap to a state with no goals, no discovered path, and no changes made to gradientMap 515 * relative to physicalMap. 516 */ 517 public void reset() { 518 resetMap(); 519 resetTargetMap(); 520 goals.clear(); 521 path.clear(); 522 closed.clear(); 523 fresh.clear(); 524 open.clear(); 525 frustration = 0; 526 } 527 528 /** 529 * Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing). 530 * 531 * @param x 532 * @param y 533 */ 534 public void setGoal(int x, int y) { 535 if (!initialized) return; 536 if (physicalMap[x][y] > FLOOR) { 537 return; 538 } 539 540 goals.put(Coord.get(x, y), GOAL); 541 } 542 543 /** 544 * Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing). 545 * 546 * @param pt 547 */ 548 public void setGoal(Coord pt) { 549 if (!initialized) return; 550 if (physicalMap[pt.x][pt.y] > FLOOR) { 551 return; 552 } 553 554 goals.put(pt, GOAL); 555 } 556 557 /** 558 * Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets 559 * the cost to the value of the WALL field). 560 * 561 * @param pt 562 * @param cost 563 */ 564 public void setCost(Coord pt, double cost) { 565 if (!initialized) return; 566 if (physicalMap[pt.x][pt.y] > FLOOR) { 567 costMap[pt.x][pt.y] = WALL; 568 return; 569 } 570 costMap[pt.x][pt.y] = cost; 571 } 572 573 /** 574 * Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets 575 * the cost to the value of the WALL field). 576 * 577 * @param x 578 * @param y 579 * @param cost 580 */ 581 public void setCost(int x, int y, double cost) { 582 if (!initialized) return; 583 if (physicalMap[x][y] > FLOOR) { 584 costMap[x][y] = WALL; 585 return; 586 } 587 costMap[x][y] = cost; 588 } 589 590 /** 591 * Marks a specific cell in gradientMap as completely impossible to enter. 592 * 593 * @param x 594 * @param y 595 */ 596 public void setOccupied(int x, int y) { 597 if (!initialized) return; 598 gradientMap[x][y] = WALL; 599 } 600 601 /** 602 * Reverts a cell to the value stored in the original state of the level as known by physicalMap. 603 * 604 * @param x 605 * @param y 606 */ 607 public void resetCell(int x, int y) { 608 if (!initialized) return; 609 gradientMap[x][y] = physicalMap[x][y]; 610 } 611 612 /** 613 * Reverts a cell to the value stored in the original state of the level as known by physicalMap. 614 * 615 * @param pt 616 */ 617 public void resetCell(Coord pt) { 618 if (!initialized) return; 619 gradientMap[pt.x][pt.y] = physicalMap[pt.x][pt.y]; 620 } 621 622 /** 623 * Used to remove all goals and undo any changes to gradientMap made by having a goal present. 624 */ 625 public void clearGoals() { 626 if (!initialized) 627 return; 628 for (Coord entry : goals.keySet()) { 629 resetCell(entry); 630 } 631 goals.clear(); 632 } 633 634 protected void setFresh(int x, int y, double counter) { 635 if (!initialized) return; 636 gradientMap[x][y] = counter; 637 fresh.put(Coord.get(x, y), counter); 638 } 639 640 protected void setFresh(final Coord pt, double counter) { 641 if (!initialized) return; 642 gradientMap[pt.x][pt.y] = counter; 643 fresh.put(pt, counter); 644 } 645 646 /** 647 * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes 648 * specified risky points to be considered less safe, and will encourage a pathfinder to keep moving toward a goal 649 * instead of just staying in cover forever (or until an enemy moves around the cover and ambushes the pathfinder). 650 * Typically, you call deteriorate() with the current Coord position of the pathfinder and any Coords they stayed at 651 * earlier along a path, and you do this once every turn or once every few turns, depending on how aggressively the 652 * pathfinder should seek a goal. 653 * 654 * @param riskyPoints a List of Coord that should be considered more risky to stay at with each call. 655 * @return the current safetyMap. 656 */ 657 public double[][] deteriorate(List<Coord> riskyPoints) { 658 return deteriorate(riskyPoints.toArray(new Coord[riskyPoints.size()])); 659 } 660 661 /** 662 * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes 663 * specified risky points to be considered less safe, and will encourage a pathfinder to keep moving toward a goal 664 * instead of just staying in cover forever (or until an enemy moves around the cover and ambushes the pathfinder). 665 * Typically, you call deteriorate() with the current Coord position of the pathfinder and any Coords they stayed at 666 * earlier along a path, and you do this once every turn or once every few turns, depending on how aggressively the 667 * pathfinder should seek a goal. 668 * 669 * @param riskyPoints a vararg or array of Coord that should be considered more risky to stay at with each call. 670 * @return the current safetyMap. 671 */ 672 public double[][] deteriorate(Coord... riskyPoints) { 673 if (!initialized) 674 return null; 675 Coord c; 676 for (int i = 0; i < riskyPoints.length; i++) { 677 c = riskyPoints[i]; 678 safetyMap[c.x][c.y] += 1.0; 679 } 680 return safetyMap; 681 } 682 683 /** 684 * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes 685 * specified safer points to be considered more safe, and will make a pathfinder more likely to enter those places 686 * if they were considered dangerous earlier (due to calling deteriorate()). 687 * <p/> 688 * Typically, you call relax() with previous Coords a pathfinder stayed at that should be safer now than they were 689 * at some previous point in time, and you might do this when no one has been attacked in a while or when the AI is 690 * sure that a threat has been neutralized or no longer threatens a safer point. 691 * 692 * @param saferPoints a List of Coord that should be considered less risky to stay at with each call. 693 * @return the current safetyMap. 694 */ 695 public double[][] relax(List<Coord> saferPoints) { 696 return relax(saferPoints.toArray(new Coord[saferPoints.size()])); 697 } 698 699 /** 700 * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes 701 * specified safer points to be considered more safe, and will make a pathfinder more likely to enter those places 702 * if they were considered dangerous earlier (due to calling deteriorate()). 703 * <p/> 704 * Typically, you call relax() with previous Coords a pathfinder stayed at that should be safer now than they were 705 * at some previous point in time, and you might do this when no one has been attacked in a while or when the AI is 706 * sure that a threat has been neutralized or no longer threatens a safer point. 707 * 708 * @param saferPoints a vararg or array of Coord that should be considered less risky to stay at with each call. 709 * @return the current safetyMap. 710 */ 711 public double[][] relax(Coord... saferPoints) { 712 if (!initialized) 713 return null; 714 Coord c; 715 for (int i = 0; i < saferPoints.length; i++) { 716 c = saferPoints[i]; 717 safetyMap[c.x][c.y] -= 1.0; 718 if (safetyMap[c.x][c.y] < 0.0) 719 safetyMap[c.x][c.y] = 0.0; 720 } 721 return safetyMap; 722 } 723 724 /** 725 * Recalculate the Dijkstra map and return it. Cells that were marked as goals with setGoal will have 726 * a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further 727 * from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, 728 * which will have a value defined by the WALL constant in this class, and areas that the scan was 729 * unable to reach, which will have a value defined by the DARK constant in this class (typically, 730 * these areas should not be used to place NPCs or items and should be filled with walls). This uses the 731 * current measurement. 732 * 733 * @param impassable A Set of Position keys representing the locations of enemies or other moving obstacles to a 734 * path that cannot be moved through; this can be null if there are no such obstacles. 735 * @return A 2D double[width][height] using the width and height of what this knows about the physical map. 736 */ 737 public double[][] scan(Set<Coord> impassable) { 738 if (!initialized) return null; 739 if (impassable == null) 740 impassable = new LinkedHashSet<>(); 741 LinkedHashMap<Coord, Double> blocking = new LinkedHashMap<>(impassable.size()); 742 for (Coord pt : impassable) { 743 blocking.put(pt, WALL); 744 } 745 closed.putAll(blocking); 746 747 for (Map.Entry<Coord, Double> entry : goals.entrySet()) { 748 if (closed.containsKey(entry.getKey())) 749 closed.remove(entry.getKey()); 750 gradientMap[entry.getKey().x][entry.getKey().y] = entry.getValue(); 751 } 752 double currentLowest = 999000; 753 LinkedHashMap<Coord, Double> lowest = new LinkedHashMap<>(); 754 755 for (int y = 0; y < height; y++) { 756 for (int x = 0; x < width; x++) { 757 if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y))) 758 closed.put(Coord.get(x, y), physicalMap[x][y]); 759 else if (gradientMap[x][y] < currentLowest) { 760 currentLowest = gradientMap[x][y]; 761 lowest.clear(); 762 lowest.put(Coord.get(x, y), currentLowest); 763 } else if (gradientMap[x][y] == currentLowest) { 764 lowest.put(Coord.get(x, y), currentLowest); 765 } 766 } 767 } 768 int numAssigned = lowest.size(); 769 mappedCount = goals.size(); 770 open.putAll(lowest); 771 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 772 while (numAssigned > 0) { 773// ++iter; 774 numAssigned = 0; 775 776 for (Map.Entry<Coord, Double> cell : open.entrySet()) { 777 for (int d = 0; d < dirs.length; d++) { 778 Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY); 779 if (adj.x < 0 || adj.y < 0 || width <= adj.x || height <= adj.y) 780 /* Outside the map */ 781 continue; 782 double h = heuristic(dirs[d]); 783 if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) { 784 setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]); 785 ++numAssigned; 786 ++mappedCount; 787 } 788 } 789 } 790// closed.putAll(open); 791 open = new LinkedHashMap<>(fresh); 792 fresh.clear(); 793 } 794 closed.clear(); 795 open.clear(); 796 797 double[][] gradientClone = new double[width][height]; 798 for (int x = 0; x < width; x++) { 799 for (int y = 0; y < height; y++) { 800 if (gradientMap[x][y] == FLOOR) { 801 gradientMap[x][y] = DARK; 802 } 803 } 804 System.arraycopy(gradientMap[x], 0, gradientClone[x], 0, height); 805 } 806 807 return gradientClone; 808 } 809 810 /** 811 * Recalculate the Dijkstra map up to a limit and return it. Cells that were marked as goals with setGoal will have 812 * a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further 813 * from goals will have a value equal to the distance from the nearest goal. If a cell would take more steps to 814 * reach than the given limit, it will have a value of DARK if it was passable instead of the distance. The 815 * exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan 816 * was unable to reach, which will have a value defined by the DARK constant in this class. This uses the 817 * current measurement. 818 * 819 * @param limit The maximum number of steps to scan outward from a goal. 820 * @param impassable A Set of Position keys representing the locations of enemies or other moving obstacles to a 821 * path that cannot be moved through; this can be null if there are no such obstacles. 822 * @return A 2D double[width][height] using the width and height of what this knows about the physical map. 823 */ 824 public double[][] partialScan(int limit, Set<Coord> impassable) { 825 if (!initialized) return null; 826 if (impassable == null) 827 impassable = new LinkedHashSet<>(); 828 LinkedHashMap<Coord, Double> blocking = new LinkedHashMap<>(impassable.size()); 829 for (Coord pt : impassable) { 830 blocking.put(pt, WALL); 831 } 832 closed.putAll(blocking); 833 834 for (Map.Entry<Coord, Double> entry : goals.entrySet()) { 835 if (closed.containsKey(entry.getKey())) 836 closed.remove(entry.getKey()); 837 gradientMap[entry.getKey().x][entry.getKey().y] = entry.getValue(); 838 } 839 double currentLowest = 999000; 840 LinkedHashMap<Coord, Double> lowest = new LinkedHashMap<>(); 841 842 for (int y = 0; y < height; y++) { 843 for (int x = 0; x < width; x++) { 844 if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y))) 845 closed.put(Coord.get(x, y), physicalMap[x][y]); 846 else if (gradientMap[x][y] < currentLowest) { 847 currentLowest = gradientMap[x][y]; 848 lowest.clear(); 849 lowest.put(Coord.get(x, y), currentLowest); 850 } else if (gradientMap[x][y] == currentLowest) { 851 lowest.put(Coord.get(x, y), currentLowest); 852 } 853 } 854 } 855 int numAssigned = lowest.size(); 856 mappedCount = goals.size(); 857 open.putAll(lowest); 858 859 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 860 int iter = 0; 861 while (numAssigned > 0 && iter < limit) { 862// ++iter; 863 numAssigned = 0; 864 865 for (Map.Entry<Coord, Double> cell : open.entrySet()) { 866 for (int d = 0; d < dirs.length; d++) { 867 Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY); 868 double h = heuristic(dirs[d]); 869 if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) { 870 setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]); 871 ++numAssigned; 872 ++mappedCount; 873 } 874 } 875 } 876// closed.putAll(open); 877 open = new LinkedHashMap<>(fresh); 878 fresh.clear(); 879 ++iter; 880 } 881 closed.clear(); 882 open.clear(); 883 884 885 double[][] gradientClone = new double[width][height]; 886 for (int x = 0; x < width; x++) { 887 for (int y = 0; y < height; y++) { 888 if (gradientMap[x][y] == FLOOR) { 889 gradientMap[x][y] = DARK; 890 } 891 } 892 System.arraycopy(gradientMap[x], 0, gradientClone[x], 0, height); 893 } 894 return gradientClone; 895 } 896 897 /** 898 * Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found. 899 * This uses the current measurement. 900 * 901 * @param start the cell to use as the origin for finding the nearest target 902 * @param targets the Coords that this is trying to find; it will stop once it finds one 903 * @return the Coord that it found first. 904 */ 905 public Coord findNearest(Coord start, Set<Coord> targets) { 906 if (!initialized) return null; 907 if (targets == null) 908 return null; 909 if (targets.contains(start)) 910 return start; 911 resetMap(); 912 Coord start2 = start; 913 int xShift = width / 8, yShift = height / 8; 914 while (physicalMap[start.x][start.y] >= WALL && frustration < 50) { 915 start2 = Coord.get(Math.min(Math.max(1, start.x + rng.nextInt(1 + xShift * 2) - xShift), width - 2), 916 Math.min(Math.max(1, start.y + rng.nextInt(1 + yShift * 2) - yShift), height - 2)); 917 } 918 if (closed.containsKey(start2)) 919 closed.remove(start2); 920 gradientMap[start2.x][start2.y] = 0.0; 921 922 for (int y = 0; y < height; y++) { 923 for (int x = 0; x < width; x++) { 924 if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y))) 925 closed.put(Coord.get(x, y), physicalMap[x][y]); 926 } 927 } 928 int numAssigned = 1; 929 mappedCount = 1; 930 open.put(start2, 0.0); 931 932 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 933 while (numAssigned > 0) { 934// ++iter; 935 numAssigned = 0; 936 937 for (Map.Entry<Coord, Double> cell : open.entrySet()) { 938 for (int d = 0; d < dirs.length; d++) { 939 Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY); 940 double h = heuristic(dirs[d]); 941 if (!closed.containsKey(adj) && !open.containsKey(adj) && 942 gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) { 943 setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]); 944 ++numAssigned; 945 ++mappedCount; 946 if (targets.contains(adj)) { 947 fresh.clear(); 948 closed.clear(); 949 open.clear(); 950 return adj; 951 } 952 } 953 } 954 } 955// closed.putAll(open); 956 open = new LinkedHashMap<>(fresh); 957 fresh.clear(); 958 } 959 closed.clear(); 960 open.clear(); 961 return null; 962 } 963 964 /** 965 * Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found. 966 * This uses the current measurement. 967 * 968 * @param start the cell to use as the origin for finding the nearest target 969 * @param targets the Coords that this is trying to find; it will stop once it finds one 970 * @return the Coord that it found first. 971 */ 972 public Coord findNearest(Coord start, Coord... targets) { 973 LinkedHashSet<Coord> tgts = new LinkedHashSet<>(targets.length); 974 Collections.addAll(tgts, targets); 975 return findNearest(start, tgts); 976 } 977 978 /** 979 * If you have a target or group of targets you want to pathfind to without scanning the full map, this can be good. 980 * It may find sub-optimal paths in the presence of costs to move into cells. It is useful when you want to move in 981 * a straight line to a known nearby goal. 982 * 983 * @param start your starting location 984 * @param targets an array or vararg of Coords to pathfind to the nearest of 985 * @return an ArrayList of Coord that goes from a cell adjacent to start and goes to one of the targets. Copy of path. 986 */ 987 public ArrayList<Coord> findShortcutPath(Coord start, Coord... targets) { 988 if (targets.length == 0) { 989 path.clear(); 990 return new ArrayList<>(path); 991 } 992 Coord currentPos = findNearest(start, targets); 993 while (true) { 994 if (frustration > 500) { 995 path.clear(); 996 break; 997 } 998 double best = gradientMap[currentPos.x][currentPos.y]; 999 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 1000 int choice = rng.nextInt(dirs.length); 1001 1002 for (int d = 0; d < dirs.length; d++) { 1003 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 1004 if (gradientMap[pt.x][pt.y] < best) { 1005 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 1006 best = gradientMap[pt.x][pt.y]; 1007 choice = d; 1008 } 1009 } 1010 } 1011 1012 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 1013 path.clear(); 1014 break; 1015 } 1016 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 1017 if (gradientMap[currentPos.x][currentPos.y] == 0) 1018 break; 1019 path.add(currentPos); 1020 frustration++; 1021 } 1022 frustration = 0; 1023 Collections.reverse(path); 1024 return new ArrayList<>(path); 1025 1026 } 1027 1028 /** 1029 * Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first several targets found, 1030 * up to limit or less if the map is fully searched without finding enough. 1031 * This uses the current measurement. 1032 * 1033 * @param start the cell to use as the origin for finding the nearest targets 1034 * @param limit the maximum number of targets to find before returning 1035 * @param targets the Coords that this is trying to find; it will stop once it finds enough (based on limit) 1036 * @return the Coords that it found first. 1037 */ 1038 public ArrayList<Coord> findNearestMultiple(Coord start, int limit, Set<Coord> targets) { 1039 if (!initialized) return null; 1040 if (targets == null) 1041 return null; 1042 ArrayList<Coord> found = new ArrayList<>(limit); 1043 if (targets.contains(start)) 1044 return found; 1045 Coord start2 = start; 1046 while (physicalMap[start.x][start.y] >= WALL && frustration < 50) { 1047 start2 = Coord.get(Math.min(Math.max(1, start.x + rng.nextInt(15) - 7), width - 2), 1048 Math.min(Math.max(1, start.y + rng.nextInt(15) - 7), height - 2)); 1049 frustration++; 1050 } 1051 if (closed.containsKey(start2)) 1052 closed.remove(start2); 1053 gradientMap[start2.x][start2.y] = 0.0; 1054 1055 for (int y = 0; y < height; y++) { 1056 for (int x = 0; x < width; x++) { 1057 if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y))) 1058 closed.put(Coord.get(x, y), physicalMap[x][y]); 1059 } 1060 } 1061 int numAssigned = 1; 1062 mappedCount = 1; 1063 open.put(start2, 0.0); 1064 1065 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 1066 while (numAssigned > 0) { 1067// ++iter; 1068 numAssigned = 0; 1069 1070 for (Map.Entry<Coord, Double> cell : open.entrySet()) { 1071 for (int d = 0; d < dirs.length; d++) { 1072 Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY); 1073 double h = heuristic(dirs[d]); 1074 if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) { 1075 setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]); 1076 ++numAssigned; 1077 ++mappedCount; 1078 if (targets.contains(adj)) { 1079 found.add(adj); 1080 if (found.size() >= limit) { 1081 fresh.clear(); 1082 open.clear(); 1083 closed.clear(); 1084 return found; 1085 } 1086 } 1087 } 1088 } 1089 } 1090// closed.putAll(open); 1091 open = new LinkedHashMap<>(fresh); 1092 fresh.clear(); 1093 } 1094 closed.clear(); 1095 open.clear(); 1096 return found; 1097 } 1098 1099 /** 1100 * Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it. The value of 1101 * a cell in the returned Dijkstra map assumes that a creature is square, with a side length equal to the passed 1102 * size, that its minimum-x, minimum-y cell is the starting cell, and that any cell with a distance number 1103 * represents the distance for the creature's minimum-x, minimum-y cell to reach it. Cells that cannot be entered 1104 * by the minimum-x, minimum-y cell because of sizing (such as a floor cell next to a maximum-x and/or maximum-y 1105 * wall if size is > 1) will be marked as DARK. Cells that were marked as goals with setGoal will have 1106 * a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further 1107 * from goals will have a value equal to the distance from the nearest goal. The exceptions are walls, 1108 * which will have a value defined by the WALL constant in this class, and areas that the scan was 1109 * unable to reach, which will have a value defined by the DARK constant in this class. (typically, 1110 * these areas should not be used to place NPCs or items and should be filled with walls). This uses the 1111 * current measurement. 1112 * 1113 * @param impassable A Set of Position keys representing the locations of enemies or other moving obstacles to a 1114 * path that cannot be moved through; this can be null if there are no such obstacles. 1115 * @param size The length of one side of a square creature using this to find a path, i.e. 2 for a 2x2 cell 1116 * creature. Non-square creatures are not supported because turning is really hard. 1117 * @return A 2D double[width][height] using the width and height of what this knows about the physical map. 1118 */ 1119 public double[][] scan(Set<Coord> impassable, int size) { 1120 if (!initialized) return null; 1121 if (impassable == null) 1122 impassable = new LinkedHashSet<>(); 1123 LinkedHashMap<Coord, Double> blocking = new LinkedHashMap<>(impassable.size()); 1124 for (Coord pt : impassable) { 1125 blocking.put(pt, WALL); 1126 for (int x = 0; x < size; x++) { 1127 for (int y = 0; y < size; y++) { 1128 if (x + y == 0) 1129 continue; 1130 if (gradientMap[pt.x - x][pt.y - y] <= FLOOR) 1131 blocking.put(Coord.get(pt.x - x, pt.y - y), DARK); 1132 } 1133 } 1134 } 1135 closed.putAll(blocking); 1136 1137 for (Map.Entry<Coord, Double> entry : goals.entrySet()) { 1138 if (closed.containsKey(entry.getKey())) 1139 closed.remove(entry.getKey()); 1140 gradientMap[entry.getKey().x][entry.getKey().y] = entry.getValue(); 1141 } 1142 mappedCount = goals.size(); 1143 double currentLowest = 999000; 1144 LinkedHashMap<Coord, Double> lowest = new LinkedHashMap<>(); 1145 Coord p = Coord.get(0, 0), temp = Coord.get(0, 0); 1146 for (int y = 0; y < height; y++) { 1147 I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS: 1148 for (int x = 0; x < width; x++) { 1149 p = Coord.get(x, y); 1150 if (gradientMap[x][y] > FLOOR && !goals.containsKey(p)) { 1151 closed.put(p, physicalMap[x][y]); 1152 if (gradientMap[x][y] == WALL) { 1153 for (int i = 0; i < size; i++) { 1154 if (x - i < 0) 1155 continue; 1156 for (int j = 0; j < size; j++) { 1157 temp = Coord.get(x - i, y - j); 1158 if (y - j < 0 || closed.containsKey(temp)) 1159 continue; 1160 if (gradientMap[temp.x][temp.y] <= FLOOR && !goals.containsKey(temp)) 1161 closed.put(Coord.get(temp.x, temp.y), DARK); 1162 } 1163 } 1164 } 1165 } else if (gradientMap[x][y] < currentLowest && !closed.containsKey(p)) { 1166 for (int i = 0; i < size; i++) { 1167 if (x + i >= width) 1168 continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS; 1169 for (int j = 0; j < size; j++) { 1170 temp = Coord.get(x + i, y + j); 1171 if (y + j >= height || closed.containsKey(temp)) 1172 continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS; 1173 } 1174 } 1175 1176 currentLowest = gradientMap[x][y]; 1177 lowest.clear(); 1178 lowest.put(Coord.get(x, y), currentLowest); 1179 1180 } else if (gradientMap[x][y] == currentLowest && !closed.containsKey(p)) { 1181 if (!closed.containsKey(p)) { 1182 for (int i = 0; i < size; i++) { 1183 if (x + i >= width) 1184 continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS; 1185 for (int j = 0; j < size; j++) { 1186 temp = Coord.get(x + i, y + j); 1187 if (y + j >= height || closed.containsKey(temp)) 1188 continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS; 1189 } 1190 } 1191 lowest.put(Coord.get(x, y), currentLowest); 1192 } 1193 } 1194 } 1195 } 1196 int numAssigned = lowest.size(); 1197 open.putAll(lowest); 1198 Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS; 1199 while (numAssigned > 0) { 1200 numAssigned = 0; 1201 for (Map.Entry<Coord, Double> cell : open.entrySet()) { 1202 for (int d = 0; d < dirs.length; d++) { 1203 Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY); 1204 double h = heuristic(dirs[d]); 1205 if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) { 1206 setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]); 1207 ++numAssigned; 1208 ++mappedCount; 1209 } 1210 } 1211 } 1212// closed.putAll(open); 1213 open = new LinkedHashMap<>(fresh); 1214 fresh.clear(); 1215 } 1216 closed.clear(); 1217 open.clear(); 1218 1219 1220 double[][] gradientClone = new double[width][height]; 1221 for (int x = 0; x < width; x++) { 1222 for (int y = 0; y < height; y++) { 1223 if (gradientMap[x][y] == FLOOR) { 1224 gradientMap[x][y] = DARK; 1225 } 1226 } 1227 System.arraycopy(gradientMap[x], 0, gradientClone[x], 0, height); 1228 } 1229 return gradientClone; 1230 } 1231 1232 /** 1233 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 1234 * of Coord positions (using the current measurement) needed to get closer to the closest reachable 1235 * goal. The maximum length of the returned list is given by length; if moving the full length of 1236 * the list would place the mover in a position shared by one of the positions in onlyPassable 1237 * (which is typically filled with friendly units that can be passed through in multi-tile- 1238 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 1239 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1240 * through, and will be ignored if there is a goal overlapping one. 1241 * <br> 1242 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1243 * each call to a pathfinding method. 1244 * @param length the length of the path to calculate 1245 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 1246 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 1247 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 1248 * @param targets a vararg or array of Coord that this will try to pathfind toward 1249 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 1250 */ 1251 public ArrayList<Coord> findPath(int length, Set<Coord> impassable, 1252 Set<Coord> onlyPassable, Coord start, Coord... targets) { 1253 if (!initialized) return null; 1254 path.clear(); 1255 LinkedHashSet<Coord> impassable2; 1256 if (impassable == null) 1257 impassable2 = new LinkedHashSet<>(); 1258 else 1259 impassable2 = new LinkedHashSet<>(impassable); 1260 if (onlyPassable == null) 1261 onlyPassable = new LinkedHashSet<>(); 1262 1263 resetMap(); 1264 for (Coord goal : targets) { 1265 setGoal(goal.x, goal.y); 1266 } 1267 if (goals.isEmpty()) 1268 return new ArrayList<>(path); 1269 scan(impassable2); 1270 Coord currentPos = start; 1271 double paidLength = 0.0; 1272 while (true) { 1273 if (frustration > 500) { 1274 path.clear(); 1275 break; 1276 } 1277 double best = gradientMap[currentPos.x][currentPos.y]; 1278 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 1279 int choice = rng.nextInt(dirs.length); 1280 1281 for (int d = 0; d < dirs.length; d++) { 1282 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 1283 if (gradientMap[pt.x][pt.y] < best) { 1284 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 1285 best = gradientMap[pt.x][pt.y]; 1286 choice = d; 1287 } 1288 } 1289 } 1290 1291 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 1292 path.clear(); 1293 break; 1294 } 1295 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 1296 path.add(currentPos); 1297 paidLength += costMap[currentPos.x][currentPos.y]; 1298 frustration++; 1299 if (paidLength > length - 1.0) { 1300 if (onlyPassable.contains(currentPos)) { 1301 1302 closed.put(currentPos, WALL); 1303 impassable2.add(currentPos); 1304 return findPath(length, impassable2, onlyPassable, start, targets); 1305 } 1306 break; 1307 } 1308 if (gradientMap[currentPos.x][currentPos.y] == 0) 1309 break; 1310 } 1311 frustration = 0; 1312 goals.clear(); 1313 return new ArrayList<>(path); 1314 } 1315 1316 /** 1317 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 1318 * of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is 1319 * reached, or further from a goal if the preferredRange has not been met at the current distance. 1320 * The maximum length of the returned list is given by moveLength; if moving the full length of 1321 * the list would place the mover in a position shared by one of the positions in onlyPassable 1322 * (which is typically filled with friendly units that can be passed through in multi-tile- 1323 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 1324 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1325 * through, and will be ignored if there is a goal overlapping one. 1326 * <br> 1327 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1328 * each call to a pathfinding method. 1329 * 1330 * @param moveLength the length of the path to calculate 1331 * @param preferredRange the distance this unit will try to keep from a target 1332 * @param los a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS 1333 * should be disregarded. 1334 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 1335 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 1336 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 1337 * @param targets a vararg or array of Coord that this will try to pathfind toward 1338 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 1339 */ 1340 public ArrayList<Coord> findAttackPath(int moveLength, int preferredRange, LOS los, Set<Coord> impassable, 1341 Set<Coord> onlyPassable, Coord start, Coord... targets) { 1342 return findAttackPath(moveLength, preferredRange, preferredRange, los, impassable, onlyPassable, start, targets); 1343 } 1344 1345 /** 1346 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 1347 * of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with 1348 * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, 1349 * which may go further from a goal if the minPreferredRange has not been met at the current distance. 1350 * The maximum length of the returned list is given by moveLength; if moving the full length of 1351 * the list would place the mover in a position shared by one of the positions in onlyPassable 1352 * (which is typically filled with friendly units that can be passed through in multi-tile- 1353 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 1354 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1355 * through, and will be ignored if there is a goal overlapping one. 1356 * <br> 1357 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1358 * each call to a pathfinding method. 1359 * 1360 * @param moveLength the length of the path to calculate 1361 * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target 1362 * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target 1363 * @param los a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS 1364 * should be disregarded. 1365 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 1366 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 1367 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 1368 * @param targets a vararg or array of Coord that this will try to pathfind toward 1369 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 1370 */ 1371 public ArrayList<Coord> findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, LOS los, 1372 Set<Coord> impassable, Set<Coord> onlyPassable, Coord start, Coord... targets) { 1373 if (!initialized) return null; 1374 if (minPreferredRange < 0) minPreferredRange = 0; 1375 if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange; 1376 double[][] resMap = new double[width][height]; 1377 if (los != null) { 1378 for (int x = 0; x < width; x++) { 1379 for (int y = 0; y < height; y++) { 1380 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 1381 } 1382 } 1383 } 1384 path.clear(); 1385 LinkedHashSet<Coord> impassable2; 1386 if (impassable == null) 1387 impassable2 = new LinkedHashSet<>(); 1388 else 1389 impassable2 = new LinkedHashSet<>(impassable); 1390 if (onlyPassable == null) 1391 onlyPassable = new LinkedHashSet<>(); 1392 1393 resetMap(); 1394 for (Coord goal : targets) { 1395 setGoal(goal.x, goal.y); 1396 } 1397 if (goals.isEmpty()) 1398 return new ArrayList<>(path); 1399 1400 Measurement mess = measurement; 1401 if (measurement == Measurement.EUCLIDEAN) { 1402 measurement = Measurement.CHEBYSHEV; 1403 } 1404 scan(impassable2); 1405 goals.clear(); 1406 1407 for (int x = 0; x < width; x++) { 1408 CELL: 1409 for (int y = 0; y < height; y++) { 1410 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 1411 continue; 1412 if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) { 1413 1414 for (Coord goal : targets) { 1415 if (los == null || los.isReachable(resMap, x, y, goal.x, goal.y)) { 1416 setGoal(x, y); 1417 gradientMap[x][y] = 0; 1418 continue CELL; 1419 } 1420 } 1421 gradientMap[x][y] = FLOOR; 1422 } else 1423 gradientMap[x][y] = FLOOR; 1424 } 1425 } 1426 measurement = mess; 1427 scan(impassable2); 1428 1429 Coord currentPos = start; 1430 double paidLength = 0.0; 1431 while (true) { 1432 if (frustration > 500) { 1433 path.clear(); 1434 break; 1435 } 1436 double best = gradientMap[currentPos.x][currentPos.y]; 1437 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 1438 int choice = rng.nextInt(dirs.length); 1439 1440 for (int d = 0; d < dirs.length; d++) { 1441 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 1442 if (gradientMap[pt.x][pt.y] < best) { 1443 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 1444 best = gradientMap[pt.x][pt.y]; 1445 choice = d; 1446 } 1447 } 1448 } 1449 1450 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 1451 path.clear(); 1452 break; 1453 } 1454 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 1455 path.add(Coord.get(currentPos.x, currentPos.y)); 1456 paidLength += costMap[currentPos.x][currentPos.y]; 1457 frustration++; 1458 if (paidLength > moveLength - 1.0) { 1459 1460 if (onlyPassable.contains(currentPos)) { 1461 1462 closed.put(currentPos, WALL); 1463 impassable2.add(currentPos); 1464 return findAttackPath(moveLength, minPreferredRange, maxPreferredRange, los, impassable2, 1465 onlyPassable, start, targets); 1466 } 1467 break; 1468 } 1469 if (gradientMap[currentPos.x][currentPos.y] == 0) 1470 break; 1471 } 1472 frustration = 0; 1473 goals.clear(); 1474 return new ArrayList<>(path); 1475 } 1476 1477 /** 1478 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 1479 * of Coord positions (using the current measurement) needed to get closer to a goal, where goals are 1480 * considered valid if they are at a valid range for the given Technique to hit at least one target 1481 * and ideal if that Technique can affect as many targets as possible from a cell that can be moved 1482 * to with at most movelength steps. 1483 * <br> 1484 * The return value of this method is the path to get to a location to attack, but on its own it 1485 * does not tell the user how to perform the attack. It does set the targetMap 2D Coord array field 1486 * so that if your position at the end of the returned path is non-null in targetMap, it will be 1487 * a Coord that can be used as a target position for Technique.apply() . If your position at the end 1488 * of the returned path is null, then an ideal attack position was not reachable by the path. 1489 * <br> 1490 * This needs a char[][] dungeon as an argument because DijkstraMap does not always have a char[][] 1491 * version of the map available to it, and certain AOE implementations that a Technique uses may 1492 * need a char[][] specifically to determine what they affect. 1493 * <br> 1494 * The maximum length of the returned list is given by moveLength; if moving the full length of 1495 * the list would place the mover in a position shared by one of the positions in allies 1496 * (which is typically filled with friendly units that can be passed through in multi-tile- 1497 * movement scenarios, and is also used considered an undesirable thing to affect for the Technique), 1498 * it will recalculate a move so that it does not pass into that cell. 1499 * <br> 1500 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1501 * through, and will be ignored if there is a target overlapping one. 1502 * <br> 1503 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1504 * each call to a pathfinding method. 1505 * 1506 * @param moveLength the maximum distance to try to pathfind out to; if a spot to use a Technique can be found 1507 * while moving no more than this distance, then the targetMap field in this object will have a 1508 * target Coord that is ideal for the given Technique at the x, y indices corresponding to the 1509 * last Coord in the returned path. 1510 * @param tech a Technique that we will try to find an ideal place to use, and/or a path toward that place. 1511 * @param dungeon a char 2D array with '#' for walls. 1512 * @param los a squidgrid.LOS object if the preferred range should try to stay in line of sight, or null if LoS 1513 * should be disregarded. 1514 * @param impassable locations of enemies or mobile hazards/obstacles that aren't in the map as walls 1515 * @param allies called onlyPassable in other methods, here it also represents allies for Technique things 1516 * @param start the Coord the pathfinder starts at. 1517 * @param targets a Set of Coord, not an array of Coord or variable argument list as in other methods. 1518 * @return an ArrayList of Coord that represents a path to travel to get to an ideal place to use tech. Copy of path. 1519 */ 1520 public ArrayList<Coord> findTechniquePath(int moveLength, Technique tech, char[][] dungeon, LOS los, 1521 Set<Coord> impassable, Set<Coord> allies, Coord start, Set<Coord> targets) { 1522 if (!initialized) return null; 1523 tech.setMap(dungeon); 1524 double[][] resMap = new double[width][height]; 1525 double[][] worthMap = new double[width][height]; 1526 double[][] userDistanceMap; 1527 double paidLength = 0.0; 1528 1529 LinkedHashSet<Coord> friends; 1530 1531 1532 for (int x = 0; x < width; x++) { 1533 for (int y = 0; y < height; y++) { 1534 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 1535 targetMap[x][y] = null; 1536 } 1537 } 1538 1539 path.clear(); 1540 if (targets == null || targets.size() == 0) 1541 return new ArrayList<>(path); 1542 LinkedHashSet<Coord> impassable2; 1543 if (impassable == null) 1544 impassable2 = new LinkedHashSet<>(); 1545 else 1546 impassable2 = new LinkedHashSet<>(impassable); 1547 1548 if (allies == null) 1549 friends = new LinkedHashSet<>(); 1550 else { 1551 friends = new LinkedHashSet<>(allies); 1552 friends.remove(start); 1553 } 1554 1555 resetMap(); 1556 setGoal(start); 1557 userDistanceMap = scan(impassable2); 1558 clearGoals(); 1559 resetMap(); 1560 for (Coord goal : targets) { 1561 setGoal(goal.x, goal.y); 1562 } 1563 if (goals.isEmpty()) 1564 return new ArrayList<>(path); 1565 1566 Measurement mess = measurement; 1567 /* 1568 if(measurement == Measurement.EUCLIDEAN) 1569 { 1570 measurement = Measurement.CHEBYSHEV; 1571 } 1572 */ 1573 scan(impassable2); 1574 clearGoals(); 1575 1576 Coord tempPt = Coord.get(0, 0); 1577 LinkedHashMap<Coord, ArrayList<Coord>> ideal; 1578 // generate an array of the single best location to attack when you are in a given cell. 1579 for (int x = 0; x < width; x++) { 1580 CELL: 1581 for (int y = 0; y < height; y++) { 1582 tempPt = Coord.get(x, y); 1583 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK || userDistanceMap[x][y] > moveLength * 2.0) 1584 continue; 1585 if (gradientMap[x][y] >= tech.aoe.getMinRange() && gradientMap[x][y] <= tech.aoe.getMaxRange()) { 1586 for (Coord tgt : targets) { 1587 if (los == null || los.isReachable(resMap, x, y, tgt.x, tgt.y)) { 1588 ideal = tech.idealLocations(tempPt, targets, friends); 1589 // this is weird but it saves the trouble of getting the iterator and checking hasNext() . 1590 for (Map.Entry<Coord, ArrayList<Coord>> ip : ideal.entrySet()) { 1591 targetMap[x][y] = ip.getKey(); 1592 worthMap[x][y] = ip.getValue().size(); 1593 setGoal(x, y); 1594 gradientMap[x][y] = 0; 1595 break; 1596 } 1597 continue CELL; 1598 } 1599 } 1600 gradientMap[x][y] = FLOOR; 1601 } else 1602 gradientMap[x][y] = FLOOR; 1603 } 1604 } 1605 scan(impassable2); 1606 1607 double currentDistance = gradientMap[start.x][start.y]; 1608 if (currentDistance <= moveLength) { 1609 Coord[] g_arr = new Coord[goals.size()]; 1610 g_arr = goals.keySet().toArray(g_arr); 1611 1612 goals.clear(); 1613 setGoal(start); 1614 scan(impassable2); 1615 goals.clear(); 1616 gradientMap[start.x][start.y] = moveLength; 1617 1618 for (Coord g : g_arr) { 1619 if (gradientMap[g.x][g.y] <= moveLength && worthMap[g.x][g.y] > 0) { 1620 goals.put(g, 0.0 - worthMap[g.x][g.y]); 1621 } 1622 } 1623 resetMap(); 1624 /* for(Coord g : goals.keySet()) 1625 { 1626 gradientMap[g.x][g.y] = 0.0 - worthMap[g.x][g.y]; 1627 }*/ 1628 scan(impassable2); 1629 1630 } 1631 1632 measurement = mess; 1633 1634 Coord currentPos = Coord.get(start.x, start.y); 1635 while (true) { 1636 if (frustration > 500) { 1637 path.clear(); 1638 break; 1639 } 1640 double best = gradientMap[currentPos.x][currentPos.y]; 1641 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 1642 int choice = rng.nextInt(dirs.length); 1643 1644 for (int d = 0; d < dirs.length; d++) { 1645 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 1646 if (gradientMap[pt.x][pt.y] < best) { 1647 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 1648 best = gradientMap[pt.x][pt.y]; 1649 choice = d; 1650 } 1651 } 1652 } 1653 if (best >= gradientMap[currentPos.x][currentPos.y]) { 1654 if (friends.contains(currentPos)) { 1655 closed.put(currentPos, WALL); 1656 impassable2.add(currentPos); 1657 return findTechniquePath(moveLength, tech, dungeon, los, impassable2, 1658 friends, start, targets); 1659 } 1660 break; 1661 } 1662 if (best > gradientMap[start.x][start.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 1663 path.clear(); 1664 break; 1665 } 1666 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 1667 path.add(currentPos); 1668 paidLength += costMap[currentPos.x][currentPos.y]; 1669 frustration++; 1670 if (paidLength > moveLength - 1.0) { 1671 if (friends.contains(currentPos)) { 1672 closed.put(currentPos, WALL); 1673 impassable2.add(currentPos); 1674 return findTechniquePath(moveLength, tech, dungeon, los, impassable2, 1675 friends, start, targets); 1676 } 1677 break; 1678 } 1679// if(gradientMap[currentPos.x][currentPos.y] == 0) 1680// break; 1681 } 1682 frustration = 0; 1683 goals.clear(); 1684 return new ArrayList<>(path); 1685 } 1686 1687 1688 /** 1689 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 1690 * of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is 1691 * reached, or further from a goal if the preferredRange has not been met at the current distance. 1692 * The maximum length of the returned list is given by moveLength; if moving the full length of 1693 * the list would place the mover in a position shared by one of the positions in onlyPassable 1694 * (which is typically filled with friendly units that can be passed through in multi-tile- 1695 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 1696 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1697 * through, and will be ignored if there is a goal overlapping one. 1698 * <br> 1699 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1700 * each call to a pathfinding method. 1701 * 1702 * @param moveLength the length of the path to calculate 1703 * @param preferredRange the distance this unit will try to keep from a target 1704 * @param cache a FOVCache that has completed its calculations, and will be used for LOS work, may be null 1705 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 1706 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 1707 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 1708 * @param targets a vararg or array of Coord that this will try to pathfind toward 1709 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 1710 */ 1711 @GwtIncompatible 1712 public ArrayList<Coord> findAttackPath(int moveLength, int preferredRange, FOVCache cache, Set<Coord> impassable, 1713 Set<Coord> onlyPassable, Coord start, Coord... targets) { 1714 return findAttackPath(moveLength, preferredRange, preferredRange, cache, impassable, onlyPassable, start, targets); 1715 } 1716 1717 /** 1718 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 1719 * of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with 1720 * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, 1721 * which may go further from a goal if the minPreferredRange has not been met at the current distance. 1722 * The maximum length of the returned list is given by moveLength; if moving the full length of 1723 * the list would place the mover in a position shared by one of the positions in onlyPassable 1724 * (which is typically filled with friendly units that can be passed through in multi-tile- 1725 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 1726 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1727 * through, and will be ignored if there is a goal overlapping one. 1728 * <br> 1729 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1730 * each call to a pathfinding method. 1731 * 1732 * @param moveLength the length of the path to calculate 1733 * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target 1734 * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target 1735 * @param cache a FOVCache that has completed its calculations, and will be used for LOS work, may be null 1736 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 1737 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 1738 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 1739 * @param targets a vararg or array of Coord that this will try to pathfind toward 1740 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 1741 */ 1742 @GwtIncompatible 1743 public ArrayList<Coord> findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, FOVCache cache, 1744 Set<Coord> impassable, Set<Coord> onlyPassable, Coord start, Coord... targets) { 1745 if (!initialized) return null; 1746 if (minPreferredRange < 0) minPreferredRange = 0; 1747 if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange; 1748 1749 path.clear(); 1750 LinkedHashSet<Coord> impassable2; 1751 if (impassable == null) 1752 impassable2 = new LinkedHashSet<>(); 1753 else 1754 impassable2 = new LinkedHashSet<>(impassable); 1755 if (onlyPassable == null) 1756 onlyPassable = new LinkedHashSet<>(); 1757 1758 resetMap(); 1759 for (Coord goal : targets) { 1760 setGoal(goal.x, goal.y); 1761 } 1762 if (goals.isEmpty()) 1763 return new ArrayList<>(path); 1764 1765 Measurement mess = measurement; 1766 if (measurement == Measurement.EUCLIDEAN) { 1767 measurement = Measurement.CHEBYSHEV; 1768 } 1769 scan(impassable2); 1770 goals.clear(); 1771 1772 for (int x = 0; x < width; x++) { 1773 CELL: 1774 for (int y = 0; y < height; y++) { 1775 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 1776 continue; 1777 if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) { 1778 1779 for (Coord goal : targets) { 1780 if (cache == null || cache.queryLOS(x, y, goal.x, goal.y)) { 1781 setGoal(x, y); 1782 gradientMap[x][y] = 0; 1783 continue CELL; 1784 } 1785 } 1786 gradientMap[x][y] = FLOOR; 1787 } else 1788 gradientMap[x][y] = FLOOR; 1789 } 1790 } 1791 measurement = mess; 1792 scan(impassable2); 1793 1794 Coord currentPos = start; 1795 double paidLength = 0.0; 1796 while (true) { 1797 if (frustration > 500) { 1798 path.clear(); 1799 break; 1800 } 1801 double best = gradientMap[currentPos.x][currentPos.y]; 1802 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 1803 int choice = rng.nextInt(dirs.length); 1804 1805 for (int d = 0; d < dirs.length; d++) { 1806 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 1807 if (gradientMap[pt.x][pt.y] < best) { 1808 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 1809 best = gradientMap[pt.x][pt.y]; 1810 choice = d; 1811 } 1812 } 1813 } 1814 1815 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 1816 path.clear(); 1817 break; 1818 } 1819 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 1820 path.add(Coord.get(currentPos.x, currentPos.y)); 1821 paidLength += costMap[currentPos.x][currentPos.y]; 1822 frustration++; 1823 if (paidLength > moveLength - 1.0) { 1824 1825 if (onlyPassable.contains(currentPos)) { 1826 1827 closed.put(currentPos, WALL); 1828 impassable2.add(currentPos); 1829 return findAttackPath(moveLength, minPreferredRange, maxPreferredRange, cache, impassable2, 1830 onlyPassable, start, targets); 1831 } 1832 break; 1833 } 1834 if (gradientMap[currentPos.x][currentPos.y] == 0) 1835 break; 1836 } 1837 frustration = 0; 1838 goals.clear(); 1839 return new ArrayList<>(path); 1840 } 1841 1842 /** 1843 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord 1844 * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the 1845 * given threats are able to see (which should prevent them from attacking), until a cell is reached with 1846 * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, 1847 * which may go further from a goal if the minPreferredRange has not been met at the current distance. 1848 * <p/> 1849 * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being 1850 * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes 1851 * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()). 1852 * <p/> 1853 * The maximum length of the returned list is given by moveLength; if moving the full length of 1854 * the list would place the mover in a position shared by one of the positions in onlyPassable 1855 * (which is typically filled with friendly units that can be passed through in multi-tile- 1856 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 1857 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 1858 * through, and will be ignored if there is a goal overlapping one. 1859 * <br> 1860 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 1861 * each call to a pathfinding method. 1862 * 1863 * @param moveLength the length of the path to calculate 1864 * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target 1865 * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target 1866 * @param coverPreference positive, typically around 1.0, higher numbers make the pathfinder stay behind cover 1867 * more, lower numbers make the pathfinder move more aggressively toward targets 1868 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 1869 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 1870 * @param threats a List of Threat objects that store a position, min and max threatening distance 1871 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 1872 * @param targets a vararg or array of Coord that this will try to pathfind toward 1873 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 1874 */ 1875 public ArrayList<Coord> findCoveredAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, 1876 double coverPreference, Set<Coord> impassable, 1877 Set<Coord> onlyPassable, List<Threat> threats, Coord start, 1878 Coord... targets) { 1879 if (!initialized) return null; 1880 1881 if (minPreferredRange < 0) minPreferredRange = 0; 1882 if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange; 1883 double[][] resMap = new double[width][height]; 1884 1885 for (int x = 0; x < width; x++) { 1886 for (int y = 0; y < height; y++) { 1887 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 1888 } 1889 } 1890 1891 1892 path = new ArrayList<Coord>(); 1893 LinkedHashSet<Coord> impassable2; 1894 if (impassable == null) 1895 impassable2 = new LinkedHashSet<Coord>(); 1896 else 1897 impassable2 = new LinkedHashSet<Coord>(impassable); 1898 if (onlyPassable == null) 1899 onlyPassable = new LinkedHashSet<Coord>(); 1900 1901 resetMap(); 1902 for (Coord goal : targets) { 1903 setGoal(goal.x, goal.y); 1904 } 1905 if (goals.isEmpty()) 1906 return new ArrayList<>(path); 1907 1908 Measurement mess = measurement; 1909 if (measurement == Measurement.EUCLIDEAN) { 1910 measurement = Measurement.CHEBYSHEV; 1911 } 1912 scan(impassable2); 1913 goals.clear(); 1914 LinkedHashMap<Coord, Double> cachedGoals = new LinkedHashMap<Coord, Double>(); 1915 1916 for (int x = 0; x < width; x++) { 1917 for (int y = 0; y < height; y++) { 1918 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 1919 continue; 1920 if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) { 1921 gradientMap[x][y] = 0.001 * (maxPreferredRange - gradientMap[x][y]); 1922 cachedGoals.put(Coord.get(x, y), gradientMap[x][y]); 1923 } else 1924 gradientMap[x][y] = FLOOR; 1925 } 1926 } 1927 measurement = mess; 1928 double[][] storedScan = scan(impassable2); 1929 if(storedScan[start.x][start.y] > moveLength) { 1930 clearGoals(); 1931 resetMap(); 1932 double[][] seen; 1933 short[] packed = CoordPacker.ALL_WALL, floors = CoordPacker.pack(physicalMap, FLOOR), tempPacked; 1934 for (Threat t : threats) { 1935 packed = CoordPacker.unionPacked( 1936 packed, CoordPacker.reachable(floors, CoordPacker.packOne(t.position), t.reach)); 1937 1938 } 1939 short[] unseen = CoordPacker.differencePacked(CoordPacker.rectangle(width, height), 1940 CoordPacker.expand(packed, 1, width, height)); 1941 Coord[] safe = CoordPacker.allPacked(unseen); 1942 for (int i = 0; i < safe.length; i++) { 1943 setGoal(safe[i]); 1944 } 1945 safetyMap = scan(impassable2); 1946 for (int x = 0; x < width; x++) { 1947 for (int y = 0; y < height; y++) { 1948 if (storedScan[x][y] < FLOOR) 1949 { 1950 gradientMap[x][y] = storedScan[x][y] * 2.0 * (moveLength+1) + safetyMap[x][y] * coverPreference; 1951 } 1952 //safeMap[x][y] = Math.pow(safeMap[x][y] + safetyMap[x][y], 1.5); 1953 } 1954 } 1955 goals = cachedGoals; 1956 scan(impassable2); 1957 1958 //gradientMap = storedScan; 1959 } 1960 Coord currentPos = start; 1961 double paidLength = 0.0; 1962 while (true) { 1963 if (frustration > 500) { 1964 path = new ArrayList<Coord>(); 1965 break; 1966 } 1967 double best = gradientMap[currentPos.x][currentPos.y]; 1968 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 1969 int choice = rng.nextInt(dirs.length); 1970 1971 for (int d = 0; d < dirs.length; d++) { 1972 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 1973 if (gradientMap[pt.x][pt.y] < best) { 1974 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 1975 best = gradientMap[pt.x][pt.y]; 1976 choice = d; 1977 } 1978 } 1979 } 1980 1981 if (best >= gradientMap[currentPos.x][currentPos.y] || 1982 physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 1983 break; 1984 } 1985 currentPos = currentPos.translate(dirs[choice]); 1986 path.add(Coord.get(currentPos.x, currentPos.y)); 1987 paidLength += costMap[currentPos.x][currentPos.y]; 1988 frustration++; 1989 if(paidLength > moveLength - 1.0) 1990 break; 1991 if (gradientMap[currentPos.x][currentPos.y] == 0) 1992 break; 1993 } 1994 goals.clear(); 1995 if (onlyPassable.contains(currentPos) || impassable2.contains(currentPos)) { 1996 closed.put(currentPos, WALL); 1997 impassable2.add(currentPos); 1998 return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference, 1999 impassable2, onlyPassable, threats, start, targets); 2000 } 2001 2002 frustration = 0; 2003 return new ArrayList<>(path); 2004 } 2005 2006 /** 2007 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord 2008 * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the 2009 * given threats are able to see (which should prevent them from attacking), until a cell is reached with 2010 * a distance from a goal that is at equal to preferredRange, 2011 * which may go further from a goal if the preferredRange has not been met at the current distance. 2012 * <p/> 2013 * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being 2014 * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes 2015 * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()). 2016 * <p/> 2017 * The maximum length of the returned list is given by moveLength; if moving the full length of 2018 * the list would place the mover in a position shared by one of the positions in onlyPassable 2019 * (which is typically filled with friendly units that can be passed through in multi-tile- 2020 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2021 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2022 * through, and will be ignored if there is a goal overlapping one. 2023 * <br> 2024 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2025 * each call to a pathfinding method. 2026 * 2027 * @param moveLength the length of the path to calculate 2028 * @param preferredRange the distance this unit will try to keep from a target 2029 * @param fov a FOV that will be used for LOS work, must not be null 2030 * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding 2031 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2032 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2033 * @param threats a List of Threat objects that store a position, min and max threatening distance 2034 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2035 * @param targets a vararg or array of Coord that this will try to pathfind toward 2036 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 2037 */ 2038 public ArrayList<Coord> findCoveredAttackPath(int moveLength, int preferredRange, double coverPreference, 2039 FOV fov, boolean seekDistantGoals, Set<Coord> impassable, 2040 Set<Coord> onlyPassable, List<Threat> threats, Coord start, 2041 Coord... targets) { 2042 return findCoveredAttackPath(moveLength, preferredRange, preferredRange, coverPreference, fov, 2043 seekDistantGoals, impassable, onlyPassable, threats, start, targets); 2044 } 2045 2046 /** 2047 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord 2048 * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the 2049 * given threats are able to see (which should prevent them from attacking), until a cell is reached with 2050 * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, 2051 * which may go further from a goal if the minPreferredRange has not been met at the current distance. 2052 * <p/> 2053 * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being 2054 * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes 2055 * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()). 2056 * <p/> 2057 * The maximum length of the returned list is given by moveLength; if moving the full length of 2058 * the list would place the mover in a position shared by one of the positions in onlyPassable 2059 * (which is typically filled with friendly units that can be passed through in multi-tile- 2060 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2061 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2062 * through, and will be ignored if there is a goal overlapping one. 2063 * <br> 2064 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2065 * each call to a pathfinding method. 2066 * 2067 * @param moveLength the length of the path to calculate 2068 * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target 2069 * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target 2070 * @param coverPreference positive, typically around 1.0, higher numbers make the pathfinder stay behind cover 2071 * more, lower numbers make the pathfinder move more aggressively toward targets 2072 * @param fov a FOV that will be used for LOS work, MUST NOT be null 2073 * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding 2074 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2075 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2076 * @param threats a List of Threat objects that store a position, min and max threatening distance 2077 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2078 * @param targets a vararg or array of Coord that this will try to pathfind toward 2079 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 2080 */ 2081 public ArrayList<Coord> findCoveredAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, 2082 double coverPreference, FOV fov, boolean seekDistantGoals, Set<Coord> impassable, 2083 Set<Coord> onlyPassable, List<Threat> threats, Coord start, 2084 Coord... targets) { 2085 if (!initialized) return null; 2086 if(fov == null) { 2087 return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference, 2088 impassable, onlyPassable, threats, start, targets); 2089 } 2090 if (minPreferredRange < 0) minPreferredRange = 0; 2091 if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange; 2092 double[][] resMap = new double[width][height]; 2093 2094 for (int x = 0; x < width; x++) { 2095 for (int y = 0; y < height; y++) { 2096 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 2097 } 2098 } 2099 2100 2101 path = new ArrayList<Coord>(); 2102 LinkedHashSet<Coord> impassable2; 2103 if (impassable == null) 2104 impassable2 = new LinkedHashSet<Coord>(); 2105 else 2106 impassable2 = new LinkedHashSet<Coord>(impassable); 2107 if (onlyPassable == null) 2108 onlyPassable = new LinkedHashSet<Coord>(); 2109 2110 resetMap(); 2111 for (Coord goal : targets) { 2112 setGoal(goal.x, goal.y); 2113 } 2114 if (goals.isEmpty()) 2115 return new ArrayList<>(path); 2116 2117 Measurement mess = measurement; 2118 if (measurement == Measurement.EUCLIDEAN) { 2119 measurement = Measurement.CHEBYSHEV; 2120 } 2121 scan(impassable2); 2122 goals.clear(); 2123 LinkedHashMap<Coord, Double> cachedGoals = new LinkedHashMap<Coord, Double>(); 2124 2125 for (int x = 0; x < width; x++) { 2126 CELL: 2127 for (int y = 0; y < height; y++) { 2128 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 2129 continue; 2130 if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) { 2131 2132 double[][] results = new double[width][height]; 2133 if (!seekDistantGoals) 2134 results = fov.calculateFOV(resMap, x, y, maxPreferredRange, findRadius(mess)); 2135 for (Coord goal : targets) { 2136 if (seekDistantGoals || results[goal.x][goal.y] > 0.0) { 2137 gradientMap[x][y] = 0.001 * (maxPreferredRange - gradientMap[x][y]); 2138 cachedGoals.put(Coord.get(x, y), gradientMap[x][y]); 2139 continue CELL; 2140 } 2141 } 2142 gradientMap[x][y] = FLOOR; 2143 } else 2144 gradientMap[x][y] = FLOOR; 2145 } 2146 } 2147 measurement = mess; 2148 double[][] storedScan = scan(impassable2); 2149 if(storedScan[start.x][start.y] > moveLength) { 2150 clearGoals(); 2151 resetMap(); 2152 double[][] seen; 2153 short[] packed = CoordPacker.ALL_WALL, tempPacked; 2154 for (Threat t : threats) { 2155 seen = fov.calculateFOV(resMap, t.position.x, t.position.y, t.reach.maxDistance, findRadius(measurement)); 2156 tempPacked = CoordPacker.pack(seen); 2157 2158 if (t.reach.minDistance > 0) { 2159 2160 seen = fov.calculateFOV(resMap, t.position.x, t.position.y, t.reach.minDistance, findRadius(measurement)); 2161 tempPacked = CoordPacker.differencePacked(tempPacked, CoordPacker.pack(seen)); 2162 2163 } 2164 packed = CoordPacker.unionPacked(packed, tempPacked); 2165 } 2166 short[] unseen = CoordPacker.differencePacked(CoordPacker.rectangle(width, height), 2167 CoordPacker.expand(packed, 1, width, height)); 2168 Coord[] safe = CoordPacker.allPacked(unseen); 2169 for (int i = 0; i < safe.length; i++) { 2170 setGoal(safe[i]); 2171 } 2172 safetyMap = scan(impassable2); 2173 for (int x = 0; x < width; x++) { 2174 for (int y = 0; y < height; y++) { 2175 if (storedScan[x][y] < FLOOR) 2176 { 2177 gradientMap[x][y] = storedScan[x][y] * 2.0 * (moveLength+1) + safetyMap[x][y] * coverPreference; 2178 } 2179 //safeMap[x][y] = Math.pow(safeMap[x][y] + safetyMap[x][y], 1.5); 2180 } 2181 } 2182 goals = cachedGoals; 2183 scan(impassable2); 2184 2185 //gradientMap = storedScan; 2186 } 2187 Coord currentPos = start; 2188 double paidLength = 0.0; 2189 while (true) { 2190 if (frustration > 500) { 2191 path = new ArrayList<Coord>(); 2192 break; 2193 } 2194 double best = gradientMap[currentPos.x][currentPos.y]; 2195 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 2196 int choice = rng.nextInt(dirs.length); 2197 2198 for (int d = 0; d < dirs.length; d++) { 2199 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 2200 if (gradientMap[pt.x][pt.y] < best) { 2201 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 2202 best = gradientMap[pt.x][pt.y]; 2203 choice = d; 2204 } 2205 } 2206 } 2207 2208 if (best >= gradientMap[currentPos.x][currentPos.y] || 2209 physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 2210 break; 2211 } 2212 currentPos = currentPos.translate(dirs[choice]); 2213 path.add(Coord.get(currentPos.x, currentPos.y)); 2214 paidLength += costMap[currentPos.x][currentPos.y]; 2215 frustration++; 2216 if(paidLength > moveLength - 1.0) 2217 break; 2218 if (gradientMap[currentPos.x][currentPos.y] == 0) 2219 break; 2220 } 2221 goals.clear(); 2222 if (onlyPassable.contains(currentPos) || impassable2.contains(currentPos)) { 2223 closed.put(currentPos, WALL); 2224 impassable2.add(currentPos); 2225 return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference, 2226 fov, seekDistantGoals, impassable2, onlyPassable, threats, start, targets); 2227 } 2228 2229 frustration = 0; 2230 return new ArrayList<>(path); 2231 } 2232 2233 /** 2234 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord 2235 * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the 2236 * given threats are able to see (which should prevent them from attacking), until a cell is reached with 2237 * a distance from a goal that is at equal to preferredRange, 2238 * which may go further from a goal if the preferredRange has not been met at the current distance. 2239 * <p/> 2240 * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being 2241 * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes 2242 * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()). 2243 * <p/> 2244 * The maximum length of the returned list is given by moveLength; if moving the full length of 2245 * the list would place the mover in a position shared by one of the positions in onlyPassable 2246 * (which is typically filled with friendly units that can be passed through in multi-tile- 2247 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2248 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2249 * through, and will be ignored if there is a goal overlapping one. 2250 * <br> 2251 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2252 * each call to a pathfinding method. 2253 * 2254 * @param moveLength the length of the path to calculate 2255 * @param preferredRange the distance this unit will try to keep from a target 2256 * @param fov a FOVCache that has completed its calculations, and will be used for LOS work, may be null 2257 * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding 2258 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2259 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2260 * @param threats a List of Threat objects that store a position, min and max threatening distance 2261 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2262 * @param targets a vararg or array of Coord that this will try to pathfind toward 2263 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 2264 */ 2265 @GwtIncompatible 2266 public ArrayList<Coord> findCoveredAttackPath(int moveLength, int preferredRange, double coverPreference, 2267 FOVCache fov, boolean seekDistantGoals, Set<Coord> impassable, 2268 Set<Coord> onlyPassable, List<Threat> threats, Coord start, 2269 Coord... targets) { 2270 return findCoveredAttackPath(moveLength, preferredRange, preferredRange, coverPreference, fov, 2271 seekDistantGoals, impassable, onlyPassable, threats, start, targets); 2272 } 2273 2274 /** 2275 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord 2276 * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the 2277 * given threats are able to see (which should prevent them from attacking), until a cell is reached with 2278 * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, 2279 * which may go further from a goal if the minPreferredRange has not been met at the current distance. 2280 * <p/> 2281 * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being 2282 * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes 2283 * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()). 2284 * <p/> 2285 * The maximum length of the returned list is given by moveLength; if moving the full length of 2286 * the list would place the mover in a position shared by one of the positions in onlyPassable 2287 * (which is typically filled with friendly units that can be passed through in multi-tile- 2288 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2289 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2290 * through, and will be ignored if there is a goal overlapping one. 2291 * <br> 2292 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2293 * each call to a pathfinding method. 2294 * 2295 * @param moveLength the length of the path to calculate 2296 * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target 2297 * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target 2298 * @param coverPreference positive, typically around 1.0, higher numbers make the pathfinder stay behind cover 2299 * more, lower numbers make the pathfinder move more aggressively toward targets 2300 * @param fov a FOVCache that has completed its calculations, and will be used for LOS work 2301 * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding 2302 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2303 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2304 * @param threats a List of Threat objects that store a position, min and max threatening distance 2305 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2306 * @param targets a vararg or array of Coord that this will try to pathfind toward 2307 * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path. 2308 */ 2309 @GwtIncompatible 2310 public ArrayList<Coord> findCoveredAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, 2311 double coverPreference, FOVCache fov, boolean seekDistantGoals, Set<Coord> impassable, 2312 Set<Coord> onlyPassable, List<Threat> threats, Coord start, 2313 Coord... targets) { 2314 if (!initialized) return null; 2315 if(fov == null) { 2316 return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference, 2317 impassable, onlyPassable, threats, start, targets); 2318 } 2319 2320 if (minPreferredRange < 0) minPreferredRange = 0; 2321 if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange; 2322 double[][] resMap = new double[width][height]; 2323 2324 for (int x = 0; x < width; x++) { 2325 for (int y = 0; y < height; y++) { 2326 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 2327 } 2328 } 2329 2330 path.clear(); 2331 LinkedHashSet<Coord> impassable2; 2332 if (impassable == null) 2333 impassable2 = new LinkedHashSet<>(); 2334 else 2335 impassable2 = new LinkedHashSet<>(impassable); 2336 if (onlyPassable == null) 2337 onlyPassable = new LinkedHashSet<>(); 2338 2339 resetMap(); 2340 for (Coord goal : targets) { 2341 setGoal(goal.x, goal.y); 2342 } 2343 if (goals.isEmpty()) 2344 return new ArrayList<>(path); 2345 2346 Measurement mess = measurement; 2347 if (measurement == Measurement.EUCLIDEAN) { 2348 measurement = Measurement.CHEBYSHEV; 2349 } 2350 scan(impassable2); 2351 goals.clear(); 2352 LinkedHashMap<Coord, Double> cachedGoals = new LinkedHashMap<>(); 2353 2354 for (int x = 0; x < width; x++) { 2355 CELL: 2356 for (int y = 0; y < height; y++) { 2357 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 2358 continue; 2359 if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) { 2360 2361 double[][] results = new double[width][height]; 2362 if (!seekDistantGoals) 2363 results = fov.calculateFOV(resMap, x, y, maxPreferredRange, findRadius(mess)); 2364 for (Coord goal : targets) { 2365 if (seekDistantGoals || results[goal.x][goal.y] > 0.0) { 2366 gradientMap[x][y] = 0.001 * (maxPreferredRange - gradientMap[x][y]); 2367 cachedGoals.put(Coord.get(x, y), gradientMap[x][y]); 2368 continue CELL; 2369 } 2370 } 2371 gradientMap[x][y] = FLOOR; 2372 } else 2373 gradientMap[x][y] = FLOOR; 2374 } 2375 } 2376 measurement = mess; 2377 double[][] storedScan = scan(impassable2); 2378 if(storedScan[start.x][start.y] > moveLength) { 2379 clearGoals(); 2380 resetMap(); 2381 double[][] seen; 2382 short[] packed = CoordPacker.ALL_WALL, tempPacked; 2383 for (Threat t : threats) { 2384 2385 tempPacked = fov.getCacheEntry(t.position.x, t.position.y, t.reach.maxDistance); 2386 2387 2388 if (t.reach.minDistance > 0) { 2389 tempPacked = CoordPacker.differencePacked(tempPacked, 2390 fov.getCacheEntry(t.position.x, t.position.y, t.reach.minDistance)); 2391 } 2392 packed = CoordPacker.unionPacked(packed, tempPacked); 2393 } 2394 short[] unseen = CoordPacker.differencePacked(CoordPacker.rectangle(width, height), 2395 CoordPacker.expand(packed, 1, width, height)); 2396 Coord[] safe = CoordPacker.allPacked(unseen); 2397 for (int i = 0; i < safe.length; i++) { 2398 setGoal(safe[i]); 2399 } 2400 safetyMap = scan(impassable2); 2401 for (int x = 0; x < width; x++) { 2402 for (int y = 0; y < height; y++) { 2403 if (storedScan[x][y] < FLOOR) 2404 { 2405 gradientMap[x][y] = storedScan[x][y] * 2.0 * (moveLength+1) + safetyMap[x][y] * coverPreference; 2406 } 2407 //safeMap[x][y] = Math.pow(safeMap[x][y] + safetyMap[x][y], 1.5); 2408 } 2409 } 2410 goals = cachedGoals; 2411 scan(impassable2); 2412 2413 //gradientMap = storedScan; 2414 } 2415 Coord currentPos = start; 2416 double paidLength = 0.0; 2417 while (true) { 2418 if (frustration > 500) { 2419 path.clear(); 2420 break; 2421 } 2422 double best = gradientMap[currentPos.x][currentPos.y]; 2423 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 2424 int choice = rng.nextInt(dirs.length); 2425 2426 for (int d = 0; d < dirs.length; d++) { 2427 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 2428 if (gradientMap[pt.x][pt.y] < best) { 2429 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 2430 best = gradientMap[pt.x][pt.y]; 2431 choice = d; 2432 } 2433 } 2434 } 2435 2436 if (best >= gradientMap[currentPos.x][currentPos.y] || 2437 physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 2438 break; 2439 } 2440 currentPos = currentPos.translate(dirs[choice]); 2441 path.add(Coord.get(currentPos.x, currentPos.y)); 2442 paidLength += costMap[currentPos.x][currentPos.y]; 2443 frustration++; 2444 if(paidLength > moveLength - 1.0) 2445 break; 2446 if (gradientMap[currentPos.x][currentPos.y] == 0) 2447 break; 2448 } 2449 goals.clear(); 2450 if (onlyPassable.contains(currentPos) || impassable2.contains(currentPos)) { 2451 closed.put(currentPos, WALL); 2452 impassable2.add(currentPos); 2453 return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference, 2454 fov, seekDistantGoals, impassable2, onlyPassable, threats, start, targets); 2455 } 2456 2457 frustration = 0; 2458 return new ArrayList<>(path); 2459 } 2460 2461 /** 2462 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 2463 * of Coord positions (using the current measurement) needed to get closer to a goal, where goals are 2464 * considered valid if they are at a valid range for the given Technique to hit at least one target 2465 * and ideal if that Technique can affect as many targets as possible from a cell that can be moved 2466 * to with at most movelength steps. 2467 * <p/> 2468 * The return value of this method is the path to get to a location to attack, but on its own it 2469 * does not tell the user how to perform the attack. It does set the targetMap 2D Coord array field 2470 * so that if your position at the end of the returned path is non-null in targetMap, it will be 2471 * a Coord that can be used as a target position for Technique.apply() . If your position at the end 2472 * of the returned path is null, then an ideal attack position was not reachable by the path. 2473 * <p/> 2474 * This needs a char[][] dungeon as an argument because DijkstraMap does not always have a char[][] 2475 * version of the map available to it, and certain AOE implementations that a Technique uses may 2476 * need a char[][] specifically to determine what they affect. 2477 * <p/> 2478 * The maximum length of the returned list is given by moveLength; if moving the full length of 2479 * the list would place the mover in a position shared by one of the positions in allies 2480 * (which is typically filled with friendly units that can be passed through in multi-tile- 2481 * movement scenarios, and is also used considered an undesirable thing to affect for the Technique), 2482 * it will recalculate a move so that it does not pass into that cell. 2483 * <p/> 2484 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2485 * through, and will be ignored if there is a target overlapping one. 2486 * <br> 2487 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2488 * each call to a pathfinding method. 2489 * 2490 * @param moveLength the maximum distance to try to pathfind out to; if a spot to use a Technique can be found 2491 * while moving no more than this distance, then the targetMap field in this object will have a 2492 * target Coord that is ideal for the given Technique at the x, y indices corresponding to the 2493 * last Coord in the returned path. 2494 * @param tech a Technique that we will try to find an ideal place to use, and/or a path toward that place. 2495 * @param dungeon a char 2D array with '#' for walls. 2496 * @param cache a FOVCache that has completed its calculations, and will be used for LOS and Technique work, may be null 2497 * @param impassable locations of enemies or mobile hazards/obstacles that aren't in the map as walls 2498 * @param allies called onlyPassable in other methods, here it also represents allies for Technique things 2499 * @param start the Coord the pathfinder starts at. 2500 * @param targets a Set of Coord, not an array of Coord or variable argument list as in other methods. 2501 * @return an ArrayList of Coord that represents a path to travel to get to an ideal place to use tech. Copy of path. 2502 */ 2503 @GwtIncompatible 2504 public ArrayList<Coord> findTechniquePath(int moveLength, Technique tech, char[][] dungeon, FOVCache cache, 2505 Set<Coord> impassable, Set<Coord> allies, Coord start, Set<Coord> targets) { 2506 if (!initialized) return null; 2507 tech.setMap(dungeon); 2508 if (cache != null) 2509 tech.aoe.setCache(cache); 2510 double[][] resMap = new double[width][height]; 2511 double[][] worthMap = new double[width][height]; 2512 double[][] userDistanceMap; 2513 double paidLength = 0.0; 2514 2515 LinkedHashSet<Coord> friends; 2516 2517 2518 for (int x = 0; x < width; x++) { 2519 for (int y = 0; y < height; y++) { 2520 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 2521 targetMap[x][y] = null; 2522 } 2523 } 2524 2525 path.clear(); 2526 if (targets == null || targets.size() == 0) 2527 return new ArrayList<>(path); 2528 LinkedHashSet<Coord> impassable2; 2529 if (impassable == null) 2530 impassable2 = new LinkedHashSet<>(); 2531 else 2532 impassable2 = new LinkedHashSet<>(impassable); 2533 2534 if (allies == null) 2535 friends = new LinkedHashSet<>(); 2536 else { 2537 friends = new LinkedHashSet<>(allies); 2538 friends.remove(start); 2539 } 2540 2541 resetMap(); 2542 setGoal(start); 2543 userDistanceMap = scan(impassable2); 2544 clearGoals(); 2545 resetMap(); 2546 for (Coord goal : targets) { 2547 setGoal(goal.x, goal.y); 2548 } 2549 if (goals.isEmpty()) 2550 return new ArrayList<>(path); 2551 2552 Measurement mess = measurement; 2553 /* 2554 if(measurement == Measurement.EUCLIDEAN) 2555 { 2556 measurement = Measurement.CHEBYSHEV; 2557 } 2558 */ 2559 scan(impassable2); 2560 clearGoals(); 2561 2562 Coord tempPt = Coord.get(0, 0); 2563 LinkedHashMap<Coord, ArrayList<Coord>> ideal; 2564 // generate an array of the single best location to attack when you are in a given cell. 2565 for (int x = 0; x < width; x++) { 2566 CELL: 2567 for (int y = 0; y < height; y++) { 2568 tempPt = Coord.get(x, y); 2569 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK || userDistanceMap[x][y] > moveLength * 2.0) 2570 continue; 2571 if (gradientMap[x][y] >= tech.aoe.getMinRange() && gradientMap[x][y] <= tech.aoe.getMaxRange()) { 2572 for (Coord tgt : targets) { 2573 if (cache == null || cache.queryLOS(x, y, tgt.x, tgt.y)) { 2574 ideal = tech.idealLocations(tempPt, targets, friends); 2575 // this is weird but it saves the trouble of getting the iterator and checking hasNext() . 2576 for (Map.Entry<Coord, ArrayList<Coord>> ip : ideal.entrySet()) { 2577 targetMap[x][y] = ip.getKey(); 2578 worthMap[x][y] = ip.getValue().size(); 2579 setGoal(x, y); 2580 gradientMap[x][y] = 0; 2581 break; 2582 } 2583 continue CELL; 2584 } 2585 } 2586 gradientMap[x][y] = FLOOR; 2587 } else 2588 gradientMap[x][y] = FLOOR; 2589 } 2590 } 2591 scan(impassable2); 2592 2593 double currentDistance = gradientMap[start.x][start.y]; 2594 if (currentDistance <= moveLength) { 2595 Coord[] g_arr = new Coord[goals.size()]; 2596 g_arr = goals.keySet().toArray(g_arr); 2597 2598 goals.clear(); 2599 setGoal(start); 2600 scan(impassable2); 2601 goals.clear(); 2602 gradientMap[start.x][start.y] = moveLength; 2603 2604 for (Coord g : g_arr) { 2605 if (gradientMap[g.x][g.y] <= moveLength && worthMap[g.x][g.y] > 0) { 2606 goals.put(g, 0.0 - worthMap[g.x][g.y]); 2607 } 2608 } 2609 resetMap(); 2610 /* for(Coord g : goals.keySet()) 2611 { 2612 gradientMap[g.x][g.y] = 0.0 - worthMap[g.x][g.y]; 2613 }*/ 2614 scan(impassable2); 2615 2616 } 2617 2618 measurement = mess; 2619 2620 Coord currentPos = Coord.get(start.x, start.y); 2621 while (true) { 2622 if (frustration > 500) { 2623 path.clear(); 2624 break; 2625 } 2626 double best = gradientMap[currentPos.x][currentPos.y]; 2627 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 2628 int choice = rng.nextInt(dirs.length); 2629 2630 for (int d = 0; d < dirs.length; d++) { 2631 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 2632 if (gradientMap[pt.x][pt.y] < best) { 2633 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 2634 best = gradientMap[pt.x][pt.y]; 2635 choice = d; 2636 } 2637 } 2638 } 2639 if (best >= gradientMap[currentPos.x][currentPos.y]) { 2640 if (friends.contains(currentPos)) { 2641 closed.put(currentPos, WALL); 2642 impassable2.add(currentPos); 2643 return findTechniquePath(moveLength, tech, dungeon, cache, impassable2, 2644 friends, start, targets); 2645 } 2646 break; 2647 } 2648 if (best > gradientMap[start.x][start.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 2649 path.clear(); 2650 break; 2651 } 2652 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 2653 path.add(currentPos); 2654 paidLength += costMap[currentPos.x][currentPos.y]; 2655 frustration++; 2656 if (paidLength > moveLength - 1.0) { 2657 if (friends.contains(currentPos)) { 2658 closed.put(currentPos, WALL); 2659 impassable2.add(currentPos); 2660 return findTechniquePath(moveLength, tech, dungeon, cache, impassable2, 2661 friends, start, targets); 2662 } 2663 break; 2664 } 2665// if(gradientMap[currentPos.x][currentPos.y] == 0) 2666// break; 2667 } 2668 frustration = 0; 2669 goals.clear(); 2670 return new ArrayList<>(path); 2671 } 2672 2673 2674 private double cachedLongerPaths = 1.2; 2675 private Set<Coord> cachedImpassable = new LinkedHashSet<>(); 2676 private Coord[] cachedFearSources; 2677 private double[][] cachedFleeMap; 2678 private int cachedSize = 1; 2679 2680 /** 2681 * Scans the dungeon using DijkstraMap.scan with the listed fearSources and start point, and returns a list 2682 * of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant 2683 * for running away. The maximum length of the returned list is given by length; if moving the full 2684 * length of the list would place the mover in a position shared by one of the positions in onlyPassable 2685 * (which is typically filled with friendly units that can be passed through in multi-tile- 2686 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2687 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2688 * through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter 2689 * is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of 2690 * doorways instead of hiding in the closest corner, and a value of 1.2 should be typical for many maps. 2691 * The parameters preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and 2692 * any subsequent calls that use the same values as the last values passed will avoid recalculating 2693 * unnecessary scans. 2694 * <br> 2695 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2696 * each call to a pathfinding method. 2697 * 2698 * @param length the length of the path to calculate 2699 * @param preferLongerPaths Set this to 1.2 if you aren't sure; it will probably need tweaking for different maps. 2700 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2701 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2702 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2703 * @param fearSources a vararg or array of Coord positions to run away from 2704 * @return an ArrayList of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path. 2705 */ 2706 public ArrayList<Coord> findFleePath(int length, double preferLongerPaths, Set<Coord> impassable, 2707 Set<Coord> onlyPassable, Coord start, Coord... fearSources) { 2708 if (!initialized) return null; 2709 path.clear(); 2710 LinkedHashSet<Coord> impassable2; 2711 if (impassable == null) 2712 impassable2 = new LinkedHashSet<>(); 2713 else 2714 impassable2 = new LinkedHashSet<>(impassable); 2715 2716 if (onlyPassable == null) 2717 onlyPassable = new LinkedHashSet<>(); 2718 if (fearSources == null || fearSources.length < 1) { 2719 path.clear(); 2720 return new ArrayList<>(path); 2721 } 2722 if (cachedSize == 1 && preferLongerPaths == cachedLongerPaths && impassable2.equals(cachedImpassable) && 2723 Arrays.equals(fearSources, cachedFearSources)) { 2724 gradientMap = cachedFleeMap; 2725 } else { 2726 cachedLongerPaths = preferLongerPaths; 2727 cachedImpassable = new LinkedHashSet<>(impassable2); 2728 cachedFearSources = GwtCompatibility.cloneCoords(fearSources); 2729 cachedSize = 1; 2730 resetMap(); 2731 for (Coord goal : fearSources) { 2732 setGoal(goal.x, goal.y); 2733 } 2734 if (goals.isEmpty()) 2735 return new ArrayList<>(path); 2736 2737 scan(impassable2); 2738 2739 for (int x = 0; x < gradientMap.length; x++) { 2740 for (int y = 0; y < gradientMap[x].length; y++) { 2741 gradientMap[x][y] *= (gradientMap[x][y] >= FLOOR) ? 1.0 : (0.0 - preferLongerPaths); 2742 } 2743 } 2744 cachedFleeMap = scan(impassable2); 2745 } 2746 Coord currentPos = start; 2747 double paidLength = 0.0; 2748 while (true) { 2749 if (frustration > 500) { 2750 path.clear(); 2751 break; 2752 } 2753 double best = gradientMap[currentPos.x][currentPos.y]; 2754 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 2755 int choice = rng.nextInt(dirs.length); 2756 2757 for (int d = 0; d < dirs.length; d++) { 2758 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 2759 if (gradientMap[pt.x][pt.y] < best) { 2760 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 2761 best = gradientMap[pt.x][pt.y]; 2762 choice = d; 2763 } 2764 } 2765 } 2766 if (best >= gradientMap[start.x][start.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 2767 path.clear(); 2768 break; 2769 } 2770 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 2771 if (path.size() > 0) { 2772 Coord last = path.get(path.size() - 1); 2773 if (gradientMap[last.x][last.y] <= gradientMap[currentPos.x][currentPos.y]) 2774 break; 2775 } 2776 path.add(currentPos); 2777 frustration++; 2778 paidLength += costMap[currentPos.x][currentPos.y]; 2779 if (paidLength > length - 1.0) { 2780 if (onlyPassable.contains(currentPos)) { 2781 2782 closed.put(currentPos, WALL); 2783 impassable2.add(currentPos); 2784 return findFleePath(length, preferLongerPaths, impassable2, onlyPassable, start, fearSources); 2785 } 2786 break; 2787 } 2788 } 2789 frustration = 0; 2790 goals.clear(); 2791 return new ArrayList<>(path); 2792 } 2793 2794 /** 2795 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 2796 * of Coord positions (using the current measurement) needed to get closer to the closest reachable 2797 * goal. The maximum length of the returned list is given by length; if moving the full length of 2798 * the list would place the mover in a position shared by one of the positions in onlyPassable 2799 * (which is typically filled with friendly units that can be passed through in multi-tile- 2800 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2801 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2802 * through, and will be ignored if there is a goal overlapping one. 2803 * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The 2804 * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and 2805 * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell. 2806 * <br> 2807 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2808 * each call to a pathfinding method. 2809 * 2810 * @param size the side length of the creature trying to find a path 2811 * @param length the length of the path to calculate 2812 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2813 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2814 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2815 * @param targets a vararg or array of Coord that this will try to pathfind toward 2816 * @return an ArrayList of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path. 2817 */ 2818 2819 public ArrayList<Coord> findPathLarge(int size, int length, Set<Coord> impassable, 2820 Set<Coord> onlyPassable, Coord start, Coord... targets) { 2821 if (!initialized) return null; 2822 path.clear(); 2823 LinkedHashSet<Coord> impassable2; 2824 if (impassable == null) 2825 impassable2 = new LinkedHashSet<>(); 2826 else 2827 impassable2 = new LinkedHashSet<>(impassable); 2828 2829 if (onlyPassable == null) 2830 onlyPassable = new LinkedHashSet<>(); 2831 2832 resetMap(); 2833 for (Coord goal : targets) { 2834 setGoal(goal.x, goal.y); 2835 } 2836 if (goals.isEmpty()) 2837 return new ArrayList<>(path); 2838 2839 scan(impassable2, size); 2840 Coord currentPos = start; 2841 double paidLength = 0.0; 2842 while (true) { 2843 if (frustration > 500) { 2844 path.clear(); 2845 break; 2846 } 2847 double best = gradientMap[currentPos.x][currentPos.y]; 2848 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 2849 int choice = rng.nextInt(dirs.length); 2850 2851 for (int d = 0; d < dirs.length; d++) { 2852 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 2853 if (gradientMap[pt.x][pt.y] < best) { 2854 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 2855 best = gradientMap[pt.x][pt.y]; 2856 choice = d; 2857 } 2858 } 2859 } 2860 2861 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 2862 path.clear(); 2863 break; 2864 } 2865 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 2866 2867 path.add(currentPos); 2868 paidLength += costMap[currentPos.x][currentPos.y]; 2869 frustration++; 2870 if (paidLength > length - 1.0) { 2871 if (onlyPassable.contains(currentPos)) { 2872 2873 closed.put(currentPos, WALL); 2874 impassable2.add(currentPos); 2875 return findPathLarge(size, length, impassable2, onlyPassable, start, targets); 2876 } 2877 break; 2878 } 2879 if (gradientMap[currentPos.x][currentPos.y] == 0) 2880 break; 2881 } 2882 frustration = 0; 2883 goals.clear(); 2884 return new ArrayList<>(path); 2885 } 2886 2887 /** 2888 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 2889 * of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is 2890 * reached, or further from a goal if the preferredRange has not been met at the current distance. 2891 * The maximum length of the returned list is given by moveLength; if moving the full length of 2892 * the list would place the mover in a position shared by one of the positions in onlyPassable 2893 * (which is typically filled with friendly units that can be passed through in multi-tile- 2894 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 2895 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 2896 * through, and will be ignored if there is a goal overlapping one. 2897 * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The 2898 * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and 2899 * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell. 2900 * <br> 2901 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 2902 * each call to a pathfinding method. 2903 * 2904 * @param size the side length of the creature trying to find a path 2905 * @param moveLength the length of the path to calculate 2906 * @param preferredRange the distance this unit will try to keep from a target 2907 * @param los a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS 2908 * should be disregarded. 2909 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 2910 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 2911 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 2912 * @param targets a vararg or array of Coord that this will try to pathfind toward 2913 * @return an ArrayList of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path. 2914 */ 2915 public ArrayList<Coord> findAttackPathLarge(int size, int moveLength, int preferredRange, LOS los, Set<Coord> impassable, 2916 Set<Coord> onlyPassable, Coord start, Coord... targets) { 2917 if (!initialized) return null; 2918 if (preferredRange < 0) preferredRange = 0; 2919 double[][] resMap = new double[width][height]; 2920 if (los != null) { 2921 for (int x = 0; x < width; x++) { 2922 for (int y = 0; y < height; y++) { 2923 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 2924 } 2925 } 2926 } 2927 path.clear(); 2928 LinkedHashSet<Coord> impassable2; 2929 if (impassable == null) 2930 impassable2 = new LinkedHashSet<>(); 2931 else 2932 impassable2 = new LinkedHashSet<>(impassable); 2933 2934 if (onlyPassable == null) 2935 onlyPassable = new LinkedHashSet<>(); 2936 2937 resetMap(); 2938 for (Coord goal : targets) { 2939 setGoal(goal.x, goal.y); 2940 } 2941 if (goals.isEmpty()) 2942 return new ArrayList<>(path); 2943 2944 Measurement mess = measurement; 2945 if (measurement == Measurement.EUCLIDEAN) { 2946 measurement = Measurement.CHEBYSHEV; 2947 } 2948 scan(impassable2, size); 2949 goals.clear(); 2950 2951 for (int x = 0; x < width; x++) { 2952 CELL: 2953 for (int y = 0; y < height; y++) { 2954 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 2955 continue; 2956 if (x + 2 < width && y + 2 < height && gradientMap[x][y] == preferredRange) { 2957 for (Coord goal : targets) { 2958 if (los == null 2959 || los.isReachable(resMap, x, y, goal.x, goal.y) 2960 || los.isReachable(resMap, x + 1, y, goal.x, goal.y) 2961 || los.isReachable(resMap, x, y + 1, goal.x, goal.y) 2962 || los.isReachable(resMap, x + 1, y + 1, goal.x, goal.y)) { 2963 setGoal(x, y); 2964 gradientMap[x][y] = 0; 2965 continue CELL; 2966 } 2967 } 2968 gradientMap[x][y] = FLOOR; 2969 } else 2970 gradientMap[x][y] = FLOOR; 2971 } 2972 } 2973 measurement = mess; 2974 scan(impassable2, size); 2975 2976 Coord currentPos = start; 2977 double paidLength = 0.0; 2978 while (true) { 2979 if (frustration > 500) { 2980 path.clear(); 2981 break; 2982 } 2983 double best = gradientMap[currentPos.x][currentPos.y]; 2984 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 2985 int choice = rng.nextInt(dirs.length); 2986 2987 for (int d = 0; d < dirs.length; d++) { 2988 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 2989 if (gradientMap[pt.x][pt.y] < best) { 2990 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 2991 best = gradientMap[pt.x][pt.y]; 2992 choice = d; 2993 } 2994 } 2995 } 2996 2997 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 2998 path.clear(); 2999 break; 3000 } 3001 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 3002 path.add(currentPos); 3003 frustration++; 3004 paidLength += costMap[currentPos.x][currentPos.y]; 3005 if (paidLength > moveLength - 1.0) { 3006 if (onlyPassable.contains(currentPos)) { 3007 3008 closed.put(currentPos, WALL); 3009 impassable2.add(currentPos); 3010 return findAttackPathLarge(size, moveLength, preferredRange, los, impassable2, onlyPassable, start, targets); 3011 } 3012 break; 3013 } 3014 if (gradientMap[currentPos.x][currentPos.y] == 0) 3015 break; 3016 } 3017 frustration = 0; 3018 goals.clear(); 3019 return new ArrayList<>(path); 3020 } 3021 3022 /** 3023 * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list 3024 * of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with 3025 * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange, 3026 * which may go further from a goal if the minPreferredRange has not been met at the current distance. 3027 * The maximum length of the returned list is given by moveLength; if moving the full length of 3028 * the list would place the mover in a position shared by one of the positions in onlyPassable 3029 * (which is typically filled with friendly units that can be passed through in multi-tile- 3030 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 3031 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 3032 * through, and will be ignored if there is a goal overlapping one. 3033 * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The 3034 * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and 3035 * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell. 3036 * <br> 3037 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 3038 * each call to a pathfinding method. 3039 * 3040 * @param size the side length of the creature trying to find a path 3041 * @param moveLength the length of the path to calculate 3042 * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target 3043 * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target 3044 * @param los a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS 3045 * should be disregarded. 3046 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 3047 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 3048 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 3049 * @param targets a vararg or array of Coord that this will try to pathfind toward 3050 * @return an ArrayList of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path. 3051 */ 3052 public ArrayList<Coord> findAttackPathLarge(int size, int moveLength, int minPreferredRange, int maxPreferredRange, LOS los, 3053 Set<Coord> impassable, Set<Coord> onlyPassable, Coord start, Coord... targets) { 3054 if (!initialized) return null; 3055 if (minPreferredRange < 0) minPreferredRange = 0; 3056 if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange; 3057 double[][] resMap = new double[width][height]; 3058 if (los != null) { 3059 for (int x = 0; x < width; x++) { 3060 for (int y = 0; y < height; y++) { 3061 resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0; 3062 } 3063 } 3064 } 3065 path.clear(); 3066 LinkedHashSet<Coord> impassable2; 3067 if (impassable == null) 3068 impassable2 = new LinkedHashSet<>(); 3069 else 3070 impassable2 = new LinkedHashSet<>(impassable); 3071 3072 if (onlyPassable == null) 3073 onlyPassable = new LinkedHashSet<>(); 3074 3075 resetMap(); 3076 for (Coord goal : targets) { 3077 setGoal(goal); 3078 } 3079 if (goals.isEmpty()) 3080 return new ArrayList<>(path); 3081 3082 Measurement mess = measurement; 3083 if (measurement == Measurement.EUCLIDEAN) { 3084 measurement = Measurement.CHEBYSHEV; 3085 } 3086 scan(impassable2, size); 3087 goals.clear(); 3088 3089 for (int x = 0; x < width; x++) { 3090 CELL: 3091 for (int y = 0; y < height; y++) { 3092 if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK) 3093 continue; 3094 if (x + 2 < width && y + 2 < height && gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) { 3095 for (Coord goal : targets) { 3096 if (los == null 3097 || los.isReachable(resMap, x, y, goal.x, goal.y) 3098 || los.isReachable(resMap, x + 1, y, goal.x, goal.y) 3099 || los.isReachable(resMap, x, y + 1, goal.x, goal.y) 3100 || los.isReachable(resMap, x + 1, y + 1, goal.x, goal.y)) { 3101 setGoal(x, y); 3102 gradientMap[x][y] = 0; 3103 continue CELL; 3104 } 3105 } 3106 gradientMap[x][y] = FLOOR; 3107 } else 3108 gradientMap[x][y] = FLOOR; 3109 } 3110 } 3111 measurement = mess; 3112 scan(impassable2, size); 3113 3114 Coord currentPos = start; 3115 double paidLength = 0.0; 3116 while (true) { 3117 if (frustration > 500) { 3118 path.clear(); 3119 break; 3120 } 3121 3122 double best = gradientMap[currentPos.x][currentPos.y]; 3123 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 3124 int choice = rng.nextInt(dirs.length); 3125 3126 for (int d = 0; d < dirs.length; d++) { 3127 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 3128 if (gradientMap[pt.x][pt.y] < best) { 3129 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 3130 best = gradientMap[pt.x][pt.y]; 3131 choice = d; 3132 } 3133 } 3134 } 3135 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 3136 path.clear(); 3137 break; 3138 } 3139 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 3140 3141 path.add(currentPos); 3142 frustration++; 3143 paidLength += costMap[currentPos.x][currentPos.y]; 3144 if (paidLength > moveLength - 1.0) { 3145 if (onlyPassable.contains(currentPos)) { 3146 3147 closed.put(currentPos, WALL); 3148 impassable2.add(currentPos); 3149 return findAttackPathLarge(size, moveLength, minPreferredRange, maxPreferredRange, los, impassable2, 3150 onlyPassable, start, targets); 3151 } 3152 break; 3153 } 3154 if (gradientMap[currentPos.x][currentPos.y] == 0) 3155 break; 3156 } 3157 frustration = 0; 3158 goals.clear(); 3159 return new ArrayList<>(path); 3160 } 3161 3162 /** 3163 * Scans the dungeon using DijkstraMap.scan with the listed fearSources and start point, and returns a list 3164 * of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant 3165 * for running away. The maximum length of the returned list is given by length; if moving the full 3166 * length of the list would place the mover in a position shared by one of the positions in onlyPassable 3167 * (which is typically filled with friendly units that can be passed through in multi-tile- 3168 * movement scenarios), it will recalculate a move so that it does not pass into that cell. 3169 * The keys in impassable should be the positions of enemies and obstacles that cannot be moved 3170 * through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter 3171 * is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of 3172 * doorways instead of hiding in the closest corner, and a value of 1.2 should be typical for many maps. 3173 * The parameters size, preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and 3174 * any subsequent calls that use the same values as the last values passed will avoid recalculating 3175 * unnecessary scans. Calls to findFleePath will cache as if size is 1, and may share a cache with this function. 3176 * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The 3177 * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is > 1, and 3178 * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell. 3179 * <br> 3180 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 3181 * each call to a pathfinding method. 3182 * 3183 * @param size the side length of the creature trying the find a path 3184 * @param length the length of the path to calculate 3185 * @param preferLongerPaths Set this to 1.2 if you aren't sure; it will probably need tweaking for different maps. 3186 * @param impassable a Set of impassable Coord positions that may change (not constant like walls); can be null 3187 * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null 3188 * @param start the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder 3189 * @param fearSources a vararg or array of Coord positions to run away from 3190 * @return an ArrayList of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path. 3191 */ 3192 public ArrayList<Coord> findFleePathLarge(int size, int length, double preferLongerPaths, Set<Coord> impassable, 3193 Set<Coord> onlyPassable, Coord start, Coord... fearSources) { 3194 if (!initialized) return null; 3195 path.clear(); 3196 LinkedHashSet<Coord> impassable2; 3197 if (impassable == null) 3198 impassable2 = new LinkedHashSet<>(); 3199 else 3200 impassable2 = new LinkedHashSet<>(impassable); 3201 3202 if (onlyPassable == null) 3203 onlyPassable = new LinkedHashSet<>(); 3204 if (fearSources == null || fearSources.length < 1) { 3205 path.clear(); 3206 return new ArrayList<>(path); 3207 } 3208 if (size == cachedSize && preferLongerPaths == cachedLongerPaths && impassable2.equals(cachedImpassable) 3209 && Arrays.equals(fearSources, cachedFearSources)) { 3210 gradientMap = cachedFleeMap; 3211 } else { 3212 cachedLongerPaths = preferLongerPaths; 3213 cachedImpassable = new LinkedHashSet<>(impassable2); 3214 cachedFearSources = GwtCompatibility.cloneCoords(fearSources); 3215 cachedSize = size; 3216 resetMap(); 3217 for (Coord goal : fearSources) { 3218 setGoal(goal.x, goal.y); 3219 } 3220 if (goals.isEmpty()) 3221 return new ArrayList<>(path); 3222 3223 scan(impassable2, size); 3224 3225 for (int x = 0; x < gradientMap.length; x++) { 3226 for (int y = 0; y < gradientMap[x].length; y++) { 3227 gradientMap[x][y] *= (gradientMap[x][y] >= FLOOR) ? 1.0 : (0.0 - preferLongerPaths); 3228 } 3229 } 3230 cachedFleeMap = scan(impassable2, size); 3231 } 3232 Coord currentPos = start; 3233 double paidLength = 0.0; 3234 while (true) { 3235 if (frustration > 500) { 3236 path.clear(); 3237 break; 3238 } 3239 3240 double best = gradientMap[currentPos.x][currentPos.y]; 3241 final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE); 3242 int choice = rng.nextInt(dirs.length); 3243 3244 for (int d = 0; d < dirs.length; d++) { 3245 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 3246 if (gradientMap[pt.x][pt.y] < best) { 3247 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 3248 best = gradientMap[pt.x][pt.y]; 3249 choice = d; 3250 } 3251 } 3252 } 3253 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 3254 path.clear(); 3255 break; 3256 } 3257 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 3258 3259 if (path.size() > 0) { 3260 Coord last = path.get(path.size() - 1); 3261 if (gradientMap[last.x][last.y] <= gradientMap[currentPos.x][currentPos.y]) 3262 break; 3263 } 3264 path.add(currentPos); 3265 frustration++; 3266 paidLength += costMap[currentPos.x][currentPos.y]; 3267 if (paidLength > length - 1.0) { 3268 if (onlyPassable.contains(currentPos)) { 3269 3270 closed.put(currentPos, WALL); 3271 impassable2.add(currentPos); 3272 return findFleePathLarge(size, length, preferLongerPaths, impassable2, onlyPassable, start, fearSources); 3273 } 3274 break; 3275 } 3276 } 3277 frustration = 0; 3278 goals.clear(); 3279 return new ArrayList<>(path); 3280 } 3281 3282 3283 /** 3284 * Intended primarily for internal use. Needs scan() to already be called and at least one goal to already be set, 3285 * and does not restrict the length of the path or behave as if the pathfinder has allies or enemies. 3286 * <br> 3287 * This caches its result in a member field, path, which can be fetched after finding a path and will change with 3288 * each call to a pathfinding method. 3289 * 3290 * @param target the target cell 3291 * @return an ArrayList of Coord that make up the best path. Copy of path. 3292 */ 3293 public ArrayList<Coord> findPathPreScanned(Coord target) { 3294 if (!initialized || goals == null || goals.isEmpty()) return null; 3295 RNG rng2 = new StatefulRNG(new LightRNG(0xf00d)); 3296 path.clear(); 3297 Coord currentPos = target; 3298 while (true) { 3299 if (frustration > 2000) { 3300 path.clear(); 3301 break; 3302 } 3303 double best = gradientMap[currentPos.x][currentPos.y]; 3304 final Direction[] dirs = appendDir(shuffleDirs(rng2), Direction.NONE); 3305 int choice = rng2.nextInt(dirs.length); 3306 3307 for (int d = 0; d < dirs.length; d++) { 3308 Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY); 3309 if (gradientMap[pt.x][pt.y] < best) { 3310 if (dirs[choice] == Direction.NONE || !path.contains(pt)) { 3311 best = gradientMap[pt.x][pt.y]; 3312 choice = d; 3313 } 3314 } 3315 } 3316 3317 if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) { 3318 path.clear(); 3319 break; 3320 } 3321 currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY); 3322 path.add(0, currentPos); 3323 frustration++; 3324 3325 if (gradientMap[currentPos.x][currentPos.y] == 0) 3326 break; 3327 } 3328 frustration = 0; 3329 return new ArrayList<>(path); 3330 } 3331 3332 /** 3333 * A simple limited flood-fill that returns a LinkedHashMap of Coord keys to the Double values in the DijkstraMap, only 3334 * calculating out to a number of steps determined by limit. This can be useful if you need many flood-fills and 3335 * don't need a large area for each, or if you want to have an effect spread to a certain number of cells away. 3336 * 3337 * @param radius the number of steps to take outward from each starting position. 3338 * @param starts a vararg group of Points to step outward from; this often will only need to be one Coord. 3339 * @return A LinkedHashMap of Coord keys to Double values; the starts are included in this with the value 0.0. 3340 */ 3341 public LinkedHashMap<Coord, Double> floodFill(int radius, Coord... starts) { 3342 if (!initialized) return null; 3343 LinkedHashMap<Coord, Double> fill = new LinkedHashMap<>(); 3344 3345 resetMap(); 3346 for (Coord goal : starts) { 3347 setGoal(goal.x, goal.y); 3348 } 3349 if (goals.isEmpty()) 3350 return fill; 3351 3352 partialScan(radius, null); 3353 double temp; 3354 for (int x = 1; x < width - 1; x++) { 3355 for (int y = 1; y < height - 1; y++) { 3356 temp = gradientMap[x][y]; 3357 if (temp < FLOOR) { 3358 fill.put(Coord.get(x, y), temp); 3359 } 3360 } 3361 } 3362 goals.clear(); 3363 return fill; 3364 } 3365 3366 private static final double root2 = Math.sqrt(2.0); 3367 3368 private double heuristic(Direction target) { 3369 switch (measurement) { 3370 case MANHATTAN: 3371 case CHEBYSHEV: 3372 return 1.0; 3373 case EUCLIDEAN: 3374 switch (target) { 3375 case DOWN_LEFT: 3376 case DOWN_RIGHT: 3377 case UP_LEFT: 3378 case UP_RIGHT: 3379 return root2; 3380 default: 3381 return 1.0; 3382 } 3383 } 3384 return 1.0; 3385 } 3386 3387 /* For Gwt compatibility */ 3388 private Direction[] shuffleDirs(RNG rng) { 3389 final Direction[] src = measurement == Measurement.MANHATTAN 3390 ? Direction.CARDINALS : Direction.OUTWARDS; 3391 return rng.shuffle(src, new Direction[src.length]); 3392 } 3393 3394 /* For Gwt compatibility */ 3395 private static Direction[] appendDir(Direction[] src, Direction additional) { 3396 final Direction[] result = new Direction[src.length + 1]; 3397 for (int i = 0; i < src.length; i++) 3398 result[i] = src[i]; 3399 result[result.length - 1] = additional; 3400 return result; 3401 } 3402}