001package squidpony.squidgrid; 002 003import squidpony.squidmath.*; 004 005import java.io.Serializable; 006import java.util.ArrayDeque; 007import java.util.ArrayList; 008import java.util.List; 009 010/** 011 * Line of Sight (LOS) algorithms find if there is or is not a path between two 012 * given points. 013 * <br> 014 * The line found between two points will end at either the target, the 015 * obstruction closest to the start, or the edge of the map. 016 * <br> 017 * For normal line of sight usage, you should prefer Bresenham lines, and these 018 * are the default (they can also be specified by passing {@link #BRESENHAM} to 019 * the constructor). For more specialized usage, there are other kinds of LOS in 020 * this class, like lines that make no diagonal moves between cells (using 021 * {@link #ORTHO}, or lines that check a wide path (but these use different 022 * methods, like {@link #thickReachable(Radius)}). 023 * <br> 024 * Performance-wise, all of these methods are rather fast and about the same speed. 025 * {@link #RAY} is a tiny fraction faster than {@link #BRESENHAM} but produces 026 * rather low-quality lines in comparison. Calculating the visibility of 40,000 027 * lines in a 102x102 dungeon takes within 3% of 950ms (on an Intel i7-4700MQ laptop 028 * processor) for every one of BRESENHAM, DDA, ORTHO, and RAY, even with ORTHO 029 * finding a different kind of line by design. 030 * 031 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 032 * @author Tommy Ettinger Added DDA, ORTHO, and the thick lines; some cleanup 033 * @author smelC optimized several methods 034 */ 035public class LOS implements Serializable { 036 private static final long serialVersionUID = 1L; 037 //constants to indicate desired type of solving algorithm to use 038 /** 039 * A Bresenham-based line-of-sight algorithm. 040 */ 041 public static final int BRESENHAM = 1; 042 /** 043 * Uses Wu's Algorithm as modified by Elias to draw the line. Does 044 * not end at an obstruction but rather returns one of the possible 045 * attempted paths in full. 046 */ 047 public static final int ELIAS = 2; 048 /** 049 * Uses a series of rays internal to the start and end point to 050 * determine visibility. Appearance is extremely close to DDA, which 051 * is also probably a faster algorithm, so BRESENHAM (which can look 052 * a little better) and DDA are recommended instead of RAY. 053 */ 054 public static final int RAY = 3; 055 /** 056 * Draws a line using only North/South/East/West movement. 057 */ 058 public static final int ORTHO = 4; 059 /** 060 * Optimized algorithm for Bresenham-like lines. There are slight 061 * differences in many parts of the lines this draws when compared 062 * to Bresenham lines, but it may also perform significantly better, 063 * and may also be useful as a building block for more complex LOS. 064 * Virtually identical in results to RAY, and just a hair slower, but 065 * better-tested and more predictable. 066 */ 067 public static final int DDA = 5; 068 /** 069 * Draws a line as if with a thick brush, going from a point between 070 * a corner of the starting cell and the center of the starting cell 071 * to the corresponding corner of the target cell, and considers the 072 * target visible if any portion of the thick stroke reached it. Will 073 * result in 1-width lines for exactly-orthogonal or exactly-diagonal 074 * lines and some parts of other lines, but usually is 2 cells wide. 075 */ 076 public static final int THICK = 6; 077 private ArrayDeque<Coord> lastPath = new ArrayDeque<>(); 078 private int type; 079 private double[][] resistanceMap; 080 private int startx, starty, targetx, targety; 081 private Elias elias; 082 private LOS los1, los2; 083 /** 084 * Gets the radius strategy this uses. 085 * @return the current Radius enum used to measure distance; starts at CIRCLE if not specified 086 */ 087 public Radius getRadiusStrategy() { 088 return radiusStrategy; 089 } 090 091 /** 092 * Set the radius strategy to the given Radius; the default is CIRCLE if this is not called. 093 * @param radiusStrategy a Radius enum to determine how distances are measured 094 */ 095 public void setRadiusStrategy(Radius radiusStrategy) { 096 this.radiusStrategy = radiusStrategy; 097 } 098 099 private Radius radiusStrategy = Radius.CIRCLE; 100 101 /** 102 * Constructs an LOS that will draw Bresenham lines and measure distances using the CIRCLE radius strategy. 103 */ 104 public LOS() { 105 this(BRESENHAM); 106 } 107 108 /** 109 * Constructs an LOS with the given type number, which must equal a static field in this class such as BRESENHAM. 110 * @param type an int that must correspond to the value of a static field in this class (such as BRESENHAM) 111 */ 112 public LOS(int type) { 113 this.type = type; 114 if(type == ELIAS) 115 { 116 elias = new Elias(); 117 los1 = new LOS(BRESENHAM); 118 los2 = new LOS(BRESENHAM); 119 120 } 121 } 122 123 /** 124 * Returns true if a line can be drawn from the start point to the target 125 * point without intervening obstructions. 126 * 127 * Uses RadiusStrategy.CIRCLE, or whatever RadiusStrategy was set with setRadiusStrategy . 128 * 129 * @param walls '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing. 130 * @param startx starting x position on the grid 131 * @param starty starting y position on the grid 132 * @param targetx ending x position on the grid 133 * @param targety ending y position on the grid 134 * @return true if a line can be drawn without being obstructed, false otherwise 135 */ 136 public boolean isReachable(char[][] walls, int startx, int starty, int targetx, int targety) { 137 if(walls.length < 1) return false; 138 double[][] resMap = new double[walls.length][walls[0].length]; 139 for(int x = 0; x < walls.length; x++) 140 { 141 for(int y = 0; y < walls[0].length; y++) 142 { 143 resMap[x][y] = (walls[x][y] == '#') ? 1.0 : 0.0; 144 } 145 } 146 return isReachable(resMap, startx, starty, targetx, targety, radiusStrategy); 147 } 148 149 /** 150 * Returns true if a line can be drawn from the start point to the target 151 * point without intervening obstructions. 152 * 153 * Does not take into account resistance less than opaque or distance cost. 154 * 155 * Uses RadiusStrategy.CIRCLE, or whatever RadiusStrategy was set with setRadiusStrategy . 156 * 157 * @param resistanceMap 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing. 158 * @param startx starting x position on the grid 159 * @param starty starting y position on the grid 160 * @param targetx ending x position on the grid 161 * @param targety ending y position on the grid 162 * @return true if a line can be drawn without being obstructed, false otherwise 163 */ 164 public boolean isReachable(double[][] resistanceMap, int startx, int starty, int targetx, int targety) { 165 return isReachable(resistanceMap, startx, starty, targetx, targety, radiusStrategy); 166 } 167 168 /** 169 * Returns true if a line can be drawn from the start point to the target 170 * point without intervening obstructions. 171 * 172 * @param resistanceMap 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing. 173 * @param startx starting x position on the grid 174 * @param starty starting y position on the grid 175 * @param targetx ending x position on the grid 176 * @param targety ending y position on the grid 177 * @param radiusStrategy the strategy to use in computing unit distance 178 * @return true if a line can be drawn without being obstructed, false otherwise 179 */ 180 public boolean isReachable(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy) { 181 if(resistanceMap.length < 1) return false; 182 this.resistanceMap = resistanceMap; 183 this.startx = startx; 184 this.starty = starty; 185 this.targetx = targetx; 186 this.targety = targety; 187 switch (type) { 188 case BRESENHAM: 189 return bresenhamReachable(radiusStrategy); 190 case ELIAS: 191 return eliasReachable(radiusStrategy); 192 case RAY: 193 return rayReachable(radiusStrategy); 194 case ORTHO: 195 return orthoReachable(radiusStrategy); 196 case DDA: 197 return ddaReachable(radiusStrategy); 198 case THICK: 199 return thickReachable(radiusStrategy); 200 } 201 return false; 202 } 203 204 /** 205 * Returns true if a line can be drawn from the start point to the target 206 * point without intervening obstructions. 207 * 208 * @param walls '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing. 209 * @param startx starting x position on the grid 210 * @param starty starting y position on the grid 211 * @param targetx ending x position on the grid 212 * @param targety ending y position on the grid 213 * @param radiusStrategy the strategy to use in computing unit distance 214 * @return true if a line can be drawn without being obstructed, false otherwise 215 */ 216 public boolean isReachable(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy) { 217 if(walls.length < 1) return false; 218 double[][] resMap = new double[walls.length][walls[0].length]; 219 for(int x = 0; x < walls.length; x++) 220 { 221 for(int y = 0; y < walls[0].length; y++) 222 { 223 resMap[x][y] = (walls[x][y] == '#') ? 1.0 : 0.0; 224 } 225 } 226 return isReachable(resMap, startx, starty, targetx, targety, radiusStrategy); 227 } 228 229 /** 230 * Returns true if a line can be drawn from the any of the points within spread cells of the start point, 231 * to any of the corresponding points at the same direction and distance from the target point, without 232 * intervening obstructions. Primarily useful to paint a broad line that can be retrieved with getLastPath. 233 * 234 * @param walls '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing. 235 * @param startx starting x position on the grid 236 * @param starty starting y position on the grid 237 * @param targetx ending x position on the grid 238 * @param targety ending y position on the grid 239 * @param radiusStrategy the strategy to use in computing unit distance 240 * @param spread the number of cells outward, measured by radiusStrategy, to place extra start and target points 241 * @return true if a line can be drawn without being obstructed, false otherwise 242 */ 243 public boolean spreadReachable(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread) { 244 if(walls.length < 1) return false; 245 resistanceMap = new double[walls.length][walls[0].length]; 246 for(int x = 0; x < walls.length; x++) 247 { 248 for(int y = 0; y < walls[0].length; y++) 249 { 250 resistanceMap[x][y] = (walls[x][y] == '#') ? 1.0 : 0.0; 251 } 252 } 253 this.startx = startx; 254 this.starty = starty; 255 this.targetx = targetx; 256 this.targety = targety; 257 258 return brushReachable(radiusStrategy, spread); 259 } 260 /** 261 * Returns true if a line can be drawn from the any of the points within spread cells of the start point, 262 * to any of the corresponding points at the same direction and distance from the target point, without 263 * intervening obstructions. Primarily useful to paint a broad line that can be retrieved with getLastPath. 264 * 265 * @param resistanceMap 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing. 266 * @param startx starting x position on the grid 267 * @param starty starting y position on the grid 268 * @param targetx ending x position on the grid 269 * @param targety ending y position on the grid 270 * @param radiusStrategy the strategy to use in computing unit distance 271 * @param spread the number of cells outward, measured by radiusStrategy, to place extra start and target points 272 * @return true if a line can be drawn without being obstructed, false otherwise 273 */ 274 public boolean spreadReachable(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread) { 275 if(resistanceMap.length < 1) return false; 276 this.resistanceMap = resistanceMap; 277 this.startx = startx; 278 this.starty = starty; 279 this.targetx = targetx; 280 this.targety = targety; 281 282 return brushReachable(radiusStrategy, spread); 283 } 284 /** 285 * Returns the path of the last LOS calculation, with the starting point as 286 * the head of the queue. 287 * 288 * @return the last path found during LOS calculation, as a ArrayDeque of Coord with the starting point at the head 289 */ 290 public ArrayDeque<Coord> getLastPath() { 291 return lastPath; 292 } 293/* 294 private boolean bresenhamReachable(Radius radiusStrategy) { 295 Queue<Coord> path = Bresenham.line2D(startx, starty, targetx, targety); 296 lastPath = new ArrayDeque<>(); 297 lastPath.add(Coord.get(startx, starty)); 298 double decay = 1 / radiusStrategy.radius(startx, starty, targetx, targety); 299 double currentForce = 1; 300 for (Coord p : path) { 301 lastPath.offer(p); 302 if (p.x == targetx && p.y == targety) { 303 return true;//reached the end 304 } 305 if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell 306 currentForce -= resistanceMap[p.x][p.y]; 307 } 308 double r = radiusStrategy.radius(startx, starty, p.x, p.y); 309 if (currentForce - (r * decay) <= 0) { 310 return false;//too much resistance 311 } 312 } 313 return false;//never got to the target point 314 } 315*/ 316 private boolean bresenhamReachable(Radius radiusStrategy) { 317 Coord[] path = Bresenham.line2D_(startx, starty, targetx, targety); 318 lastPath = new ArrayDeque<>(); 319 double rad = radiusStrategy.radius(startx, starty, targetx, targety); 320 if(rad == 0.0) { 321 lastPath.add(Coord.get(startx, starty)); 322 return true; // already at the point; we can see our own feet just fine! 323 } 324 double decay = 1 / rad; 325 double currentForce = 1; 326 Coord p; 327 for (int i = 0; i < path.length; i++) { 328 p = path[i]; 329 lastPath.offer(p); 330 if (p.x == targetx && p.y == targety) { 331 return true;//reached the end 332 } 333 if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell 334 currentForce -= resistanceMap[p.x][p.y]; 335 } 336 double r = radiusStrategy.radius(startx, starty, p.x, p.y); 337 if (currentForce - (r * decay) <= 0) { 338 return false;//too much resistance 339 } 340 } 341 return false;//never got to the target point 342 } 343 344 private boolean orthoReachable(Radius radiusStrategy) { 345 Coord[] path = OrthoLine.line_(startx, starty, targetx, targety); 346 lastPath = new ArrayDeque<>(); 347 double rad = radiusStrategy.radius(startx, starty, targetx, targety); 348 if(rad == 0.0) { 349 lastPath.add(Coord.get(startx, starty)); 350 return true; // already at the point; we can see our own feet just fine! 351 } 352 double decay = 1 / rad; 353 double currentForce = 1; 354 Coord p; 355 for (int i = 0; i < path.length; i++) { 356 p = path[i]; 357 lastPath.offer(p); 358 if (p.x == targetx && p.y == targety) { 359 return true;//reached the end 360 } 361 if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell 362 currentForce -= resistanceMap[p.x][p.y]; 363 } 364 double r = radiusStrategy.radius(startx, starty, p.x, p.y); 365 if (currentForce - (r * decay) <= 0) { 366 return false;//too much resistance 367 } 368 } 369 return false;//never got to the target point 370 } 371 372 private boolean ddaReachable(Radius radiusStrategy) { 373 Coord[] path = DDALine.line_(startx, starty, targetx, targety); 374 lastPath = new ArrayDeque<>(); 375 double rad = radiusStrategy.radius(startx, starty, targetx, targety); 376 if(rad == 0.0) { 377 lastPath.add(Coord.get(startx, starty)); 378 return true; // already at the point; we can see our own feet just fine! 379 } 380 double decay = 1 / rad; 381 double currentForce = 1; 382 Coord p; 383 for (int i = 0; i < path.length; i++) { 384 p = path[i]; 385 if (p.x == targetx && p.y == targety) { 386 lastPath.offer(p); 387 return true;//reached the end 388 } 389 if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell 390 currentForce -= resistanceMap[p.x][p.y]; 391 } 392 double r = radiusStrategy.radius(startx, starty, p.x, p.y); 393 if (currentForce - (r * decay) <= 0) { 394 return false;//too much resistance 395 } 396 lastPath.offer(p); 397 } 398 return false;//never got to the target point 399 } 400 401 private boolean thickReachable(Radius radiusStrategy) { 402 lastPath = new ArrayDeque<>(); 403 double dist = radiusStrategy.radius(startx, starty, targetx, targety); 404 double decay = 1.0 / dist; // note: decay can be positive infinity if dist is 0; this is actually OK 405 OrderedSet<Coord> visited = new OrderedSet<>((int) dist + 3); 406 List<List<Coord>> paths = new ArrayList<>(4); 407 /* // actual corners 408 paths.add(DDALine.line(startx, starty, targetx, targety, 0, 0)); 409 paths.add(DDALine.line(startx, starty, targetx, targety, 0, 0xffff)); 410 paths.add(DDALine.line(startx, starty, targetx, targety, 0xffff, 0)); 411 paths.add(DDALine.line(startx, starty, targetx, targety, 0xffff, 0xffff)); 412 */ 413 // halfway between the center and a corner 414 paths.add(DDALine.line(startx, starty, targetx, targety, 0x3fff, 0x3fff)); 415 paths.add(DDALine.line(startx, starty, targetx, targety, 0x3fff, 0xbfff)); 416 paths.add(DDALine.line(startx, starty, targetx, targety, 0xbfff, 0x3fff)); 417 paths.add(DDALine.line(startx, starty, targetx, targety, 0xbfff, 0xbfff)); 418 419 int length = Math.max(paths.get(0).size(), Math.max(paths.get(1).size(), 420 Math.max(paths.get(2).size(), paths.get(3).size()))); 421 double[] forces = new double[]{1,1,1,1}; 422 boolean[] go = new boolean[]{true, true, true, true}; 423 Coord p; 424 for (int d = 0; d < length; d++) { 425 for (int pc = 0; pc < 4; pc++) { 426 List<Coord> path = paths.get(pc); 427 if(d < path.size() && go[pc]) 428 p = path.get(d); 429 else continue; 430 if (p.x == targetx && p.y == targety) { 431 visited.add(p); 432 lastPath.addAll(visited); 433 return true;//reached the end 434 } 435 if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell 436 forces[pc] -= resistanceMap[p.x][p.y]; 437 } 438 double r = radiusStrategy.radius(startx, starty, p.x, p.y); 439 if (forces[pc] - (r * decay) <= 0) { 440 go[pc] = false; 441 continue;//too much resistance 442 } 443 visited.add(p); 444 } 445 } 446 lastPath.addAll(visited); 447 return false;//never got to the target point 448 } 449 450 private boolean brushReachable(Radius radiusStrategy, int spread) { 451 lastPath.clear(); 452 double dist = radiusStrategy.radius(startx, starty, targetx, targety) + spread * 2; 453 OrderedSet<Coord> visited = new OrderedSet<>((int) (dist + 3) * spread); 454// List<List<Coord>> paths = new ArrayList<>((int) (radiusStrategy.volume2D(spread) * 1.25)); 455// int length = 0; 456// List<Coord> currentPath; 457 int sx = startx, sy = starty, tx = targetx, ty = targety; 458 for (int i = -spread; i <= spread; i++) { 459 startx = sx + i; 460 targetx = tx + i; 461 for (int j = -spread; j <= spread; j++) { 462 if(radiusStrategy.inRange(sx, sy, sx + i, sy + j, 0, spread) 463 && sx + i >= 0 && sy + j >= 0 464 && sx + i < resistanceMap.length && sy + j < resistanceMap[0].length 465 && tx + i >= 0 && ty + j >= 0 466 && tx + i < resistanceMap.length && ty + j < resistanceMap[0].length) { 467// for (int q = 0x3fff; q < 0xffff; q += 0x8000) { 468// for (int r = 0x3fff; r < 0xffff; r += 0x8000) { 469 starty = sy + j; 470 targety = ty + j; 471 if(ddaReachable(radiusStrategy)) 472 visited.addAll(lastPath); 473// currentPath = DDALine.line(startx+i, starty+j, targetx+i, targety+j, q, r); 474// paths.add(currentPath); 475// length = Math.max(length, currentPath.size()); 476 477// } 478// } 479 } 480 } 481 } 482 lastPath.clear(); 483 lastPath.addAll(visited); 484 return !lastPath.isEmpty(); 485// double force; 486//// boolean[] go = new boolean[paths.size()]; 487//// Arrays.fill(go, true); 488// Coord p; 489//// boolean found = false; 490// for (int pc = 0; pc < paths.size(); pc++) { 491// List<Coord> path = paths.get(pc); 492// force = 1.0; 493// for (int d = 0; d < path.size(); d++) { 494// p = path.get(d); 495// //else continue; 496//// if (p.x == targetx && p.y == targety) { 497//// found = true; 498//// } 499// if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell 500// force -= resistanceMap[p.x][p.y]; 501// } 502// //double r = radiusStrategy.radius(startx, starty, p.x, p.y); 503// if (force <= 0) { 504// //go[pc] = false; 505// break;//too much resistance 506// } 507// visited.add(p); 508// } 509// } 510// lastPath.addAll(visited); 511// return true;//visited.contains(Coord.get(targetx, targety)); 512 } 513 514 private boolean rayReachable(Radius radiusStrategy) { 515 lastPath = new ArrayDeque<>();//save path for later retrieval 516 if (startx == targetx && starty == targety) {//already there! 517 lastPath.add(Coord.get(startx, starty)); 518 return true; 519 } 520 521 int width = resistanceMap.length; 522 int height = resistanceMap[0].length; 523 524 Coord end = Coord.get(targetx, targety); 525 //find out which direction to step, on each axis 526 int stepX = targetx == startx ? 0 : (targetx - startx >> 31 | 1), // signum with less converting to/from float 527 stepY = targety == starty ? 0 : (targety - starty >> 31 | 1); 528 529 int deltaY = Math.abs(targetx - startx), 530 deltaX = Math.abs(targety - starty); 531 532 int testX = startx, 533 testY = starty; 534 535 int maxX = deltaX, 536 maxY = deltaY; 537 538 while (testX >= 0 && testX < width && testY >= 0 && testY < height && (testX != targetx || testY != targety)) { 539 lastPath.add(Coord.get(testX, testY)); 540 if (maxY - maxX > deltaX) { 541 maxX += deltaX; 542 testX += stepX; 543 if (resistanceMap[testX][testY] >= 1f) { 544 end = Coord.get(testX, testY); 545 break; 546 } 547 } else if (maxX - maxY > deltaY) { 548 maxY += deltaY; 549 testY += stepY; 550 if (resistanceMap[testX][testY] >= 1f) { 551 end = Coord.get(testX, testY); 552 break; 553 } 554 } else {//directly on diagonal, move both full step 555 maxY += deltaY; 556 testY += stepY; 557 maxX += deltaX; 558 testX += stepX; 559 if (resistanceMap[testX][testY] >= 1f) { 560 end = Coord.get(testX, testY); 561 break; 562 } 563 } 564 if (radiusStrategy.radius(testX, testY, startx, starty) > radiusStrategy.radius(startx, starty, end.x, end.y)) {//went too far 565 break; 566 } 567 } 568 569 if (end.x >= 0 && end.x < width && end.y >= 0 && end.y < height) { 570 lastPath.add(Coord.get(end.x, end.y)); 571 } 572 573 return end.x == targetx && end.y == targety; 574 } 575 576 private boolean eliasReachable(Radius radiusStrategy) { 577 if(elias == null) 578 { 579 elias = new Elias(); 580 los1 = new LOS(BRESENHAM); 581 los2 = new LOS(BRESENHAM); 582 } 583 final ArrayList<Coord> ePath = elias.line(startx, starty, targetx, targety); 584// // very similar to RNG.shuffleInPlace(); this may be handy for getting an early shortcut return 585// final int n = ePath.size(); 586// long state = 0x58476D1CE4E5B9BFL; 587// for (int i = n; i > 1; i--) { 588// // inlined LightRNG.determineBounded(); can replace *= with usually-faster += 589// Collections.swap(ePath, (int)((i * (((state = ((state = ((state += 0x9E3779B97F4A7C15L) ^ state >>> 30) * 0xBF58476D1CE4E5B9L) ^ state >>> 27) * 0x94D049BB133111EBL) ^ state >>> 31) & 0x7FFFFFFFL)) >> 31), i - 1); 590// } 591 for(Coord p : ePath) 592 { 593 //if a non-solid midpoint on the path can see both the start and end, consider the two ends to be able to see each other 594 if (resistanceMap[p.x][p.y] < 1 595 && radiusStrategy.radius(startx, starty, p.x, p.y) <= radiusStrategy.radius(startx, starty, targetx, targety) 596 && los1.isReachable(resistanceMap, p.x, p.y, targetx, targety, radiusStrategy) 597 && los2.isReachable(resistanceMap, startx, starty, p.x, p.y, radiusStrategy)) { 598 599 //record actual sight path used 600 lastPath.clear(); 601 lastPath.addAll(los2.lastPath); 602 lastPath.remove(p); // should be the only overlapping point 603 lastPath.addAll(los1.lastPath); 604 return true; 605 } 606 607 } 608 return false;//never got to the target point 609 } 610}