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