001package squidpony.squidgrid; 002 003import squidpony.annotation.GwtIncompatible; 004import squidpony.squidgrid.mapping.DungeonUtility; 005import squidpony.squidmath.Coord; 006import squidpony.squidmath.ShortVLA; 007 008import java.util.*; 009import java.util.concurrent.*; 010 011import static squidpony.squidmath.CoordPacker.*; 012 013/** 014 * A combined FOV calculator, partial LOS calculator, FOV/LOS compressor, and tool to store/query/extract compressed 015 * FOV/LOS data. It operates on one level map at a time and stores FOV maps for all cells in a memory-efficient way, 016 * though it is likely to take too long to process large maps to be useful on those unless run before the player gets 017 * to that map. (Large here means more than 10,000 total cells, or 100 width * 100 height, but this rough upper bound is 018 * based on the capability of the machine running the calculations, and should be expected to be much lower on, for 019 * instance, older dual-core phones than newer quad-core desktops). There are a few ways to ensure FOVCache is done 020 * processing a map by the time a player gets to that map; the recommended approach for games with clearly defined, 021 * separate levels is to generate the first level as part of game startup, run cacheAll() immediately afterward (this 022 * will start calculation on a second thread), and when the map needs to be displayed (because gameplay has started and 023 * any character creation steps are done), to call the caching method's counterpart, awaitCache(), which will cause 024 * gameplay to be essentially frozen until the cache completes (you could display a loading message before calling it). 025 * The next part is more interesting; you should generate the second level immediately after the awaiting method 026 * finishes, before the player has approached the second level, and create another FOVCache object using the second 027 * level as its map, then call cacheAll() on the second level's FOVCache. This will calculate the cache, as before, on 028 * another thread, and you should call the appropriate awaiting method when the player is entering the second level 029 * (descending or ascending a staircase, for example). This time, as long as the player spent more than a few seconds on 030 * the first level for most maps, the cache should be pre-calculated and awaiting should take no time. 031 * <br> 032 * The FOV calculation this class performs includes a post-processing stage that guarantees symmetry for both LOS and 033 * FOV. This works by checking every cell that is within the maximum radius for each non-wall cell, and if any cell A 034 * can see cell B, but cell B can not yet see A, then B's cached FOV map will be altered so it can see A. The other 035 * post-processing step provides distant lighting; if lights have been passed to the constructor as a Map of Coord keys 036 * to Integer values, then the Coords in that Map that are walkable squares will emit light up to a radius equal to 037 * their value in that Map. Cells with distant lighting will always be in FOV if they could be seen at up to radius 038 * equal to maxLOSRadius, which defaults to 62 and is calculated for every FOVCache as an LOS cache. Calculating distant 039 * lighting adds a somewhat substantial amount of time to each caching attempt, estimated at tripling the amount of time 040 * used in cases where there are very many lights in a large dungeon (in a 100x100 dungeon, with one light per 5x5 area 041 * when the center of that area is walkable, for example), but the lighting is expected to be much less of a performance 042 * hindrance on smaller maps (80x40, 60x60, anything smaller, etc.) or when there are simply less lights to process 043 * (because distant lighting is meant to go beyond nearby cells, it needs to run through essentially all lights for every 044 * cell it processes, and even though adding the lit area to FOV is very efficient and does not require recalculating 045 * FOV, having lots of lights means lots of work per cell). 046 * <br> 047 * This class extends FOV and can be used as a replacement for FOV in some cases. Generally, FOVCache provides methods 048 * that allow faster manipulation and checks of certain values (such as a simple case of whether a cell can be seen from 049 * another cell at a given FOV radius), but will fall back to Shadowcasting FOV (without using the cache) if any calls 050 * to FOV methods are made that have not had their needed information cached. Uncached calls to FOV will not have some 051 * of the niceties FOVCache can provide, like distant lights. If different light levels are needed (which Shadowcasting 052 * does not provide), you can call Graded variants on the FOV methods, which will fall back to a Ripple FOV instead and 053 * will have values between 0.0 and 1.0 instead of only those two extremes. 054 * <br> 055 * Conservation of memory usage is a primary concern for this class; storing a full 2D array for every cell on a map 056 * that is even moderately large uses outrageous amounts of RAM, and attempting that naive approach on a 256x256 map 057 * would use more than 4 GB of RAM for purely the data from storing bytes or booleans, not including the JVM's overhead 058 * of between 12 and 19 bytes for every array. Using smaller maps helps both this class and any other approach (less 059 * cells to store FOV for), and at least for FOVCache, using smaller maxRadius values can reduce memory usage as well. 060 * For a normal 100x100 map, storing one byte[][] for every cell, and storing a 2D array of those (which has a minimal 061 * effect on memory consumption vs. a 1D array in this case), the resulting byte[][][][] will use 112,161,616 bytes of 062 * RAM, approximately 110 MB; this would still need an additional step of processing when used to limit a requested 063 * FOV map stored in it to the appropriate vision range. To contrast, the current version of FOVCache on the same size 064 * of map, caching 12 separate FOV radii, uses approximately 6.2 MB. Tests run on ten 100x100 dungeons ran the gamut 065 * between 6,049,760 and 6,404,336 bytes (the layout of the dungeon doesn't affect memory usage of the naive case, but 066 * it does have a small effect on the compressed version). To actually use the compressed maps does take an additional 067 * processing step, but careful benchmarking indicates running FOV for a roughly 12 radius (Radius.SQUARE kind) area 068 * takes twice as long as simply extracting a cached FOV map, and the advantage for the cache is greater for larger FOV 069 * radii (but the cache also uses slightly more memory). This compares against the fastest FOV type, Shadowcasting, but 070 * to get distance information from an FOV you need to use either the customized FOV algorithm in this class (Slope 071 * Shadowcasting), or to use the Ripple FOV type. Ripple does respect translucent objects, which neither shadowcasting 072 * nor this class' slope shadowcasting does, but getting 16 FOV levels from the cache for every walkable cell on a 073 * 100x100 dungeon map takes approximately 19 ms while running Ripple FOV for the same set of cells takes over 700 ms. 074 * Benchmarks are conducted using JMH, a tool developed by the OpenJDK team, in a Maven module called 075 * squidlib-performance that is not distributed with SquidLib but is available if you download the SquidLib source code. 076 * 077 * @see squidpony.squidmath.CoordPacker has various utilities for operating on compressed data of this kind. 078 * Created by Tommy Ettinger on 10/7/2015. 079 * @author Tommy Ettinger 080 */ 081@GwtIncompatible 082public class FOVCache extends FOV{ 083 084 protected int maxRadius, maxLOSRadius; 085 protected int width; 086 protected int height; 087 protected int mapLimit; 088 protected int limit; 089 protected double[][] resMap; 090 protected Radius radiusKind; 091 protected short[][][] cache; 092 protected short[][][] tmpCache; 093 protected short[][] losCache; 094 protected boolean complete, qualityComplete, refreshComplete; 095 protected FOV fov, gradedFOV; 096 protected short[][] ALL_WALLS; 097 protected short[] wallMap; 098 protected double[][] atan2Cache, directionAngles; 099 protected short[][] distanceCache; 100 protected Coord[][] waves; 101 protected final int NUM_THREADS; 102 private ExecutorService executor; 103 protected double fovPermissiveness; 104 protected LinkedHashMap<Coord, Integer> lights; 105 protected Coord[] lightSources; 106 protected int[] lightBrightnesses; 107 private double[][] levels; 108 protected double decay; 109 private Thread performanceThread = null, qualityThread = null; 110 private static final double HALF_PI = Math.PI * 0.5, QUARTER_PI = Math.PI * 0.25125, 111 SLIVER_PI = Math.PI * 0.05, PI2 = Math.PI * 2; 112 113 /** 114 * Create an FOVCache for a given map (as a char[][]), caching all FOV radii from 0 up to and including maxRadius, 115 * using the given Radius enum to determine FOV shape. Upon calling cacheAllPerformance() or cacheAll(), 116 * (collectively, the caching methods), the object this creates will run a medium-quality, fairly permissive FOV 117 * calculation for every cell on the map using 8 threads, and if cacheAll() was called, will then ensure 118 * symmetry (if cell A can see cell B, then it will make cell B able to see cell A even if it couldn't in an earlier 119 * step). At the same time as the first caching method call, this will calculate Line of Sight at maxLOSRadius (here 120 * it is given a default of 62) for all cells. Walls will always have no cells in their FOV or LOS. 121 * @param map a char[][] as returned by SquidLib's map generators 122 * @param maxRadius the longest radius that will possibly need to be cached for FOV; LOS is separate 123 * @param radiusKind a Radius enum that determines the shape of each FOV area 124 */ 125 public FOVCache(char[][] map, int maxRadius, Radius radiusKind) 126 { 127 if(map == null || map.length == 0) 128 throw new UnsupportedOperationException("The map used by FOVCache must not be null or empty"); 129 NUM_THREADS = 8; 130 executor = Executors.newFixedThreadPool(NUM_THREADS); 131 width = map.length; 132 height = map[0].length; 133 if(width > 256 || height > 256) 134 throw new UnsupportedOperationException("Map size is too large to efficiently cache, aborting"); 135 mapLimit = width * height; 136 if(maxRadius <= 0 || maxRadius >= 63) 137 throw new UnsupportedOperationException("FOV radius is incorrect. Must be 0 < maxRadius < 63"); 138 fov = new FOV(FOV.SHADOW); 139 gradedFOV = new FOV(RIPPLE); 140 resMap = DungeonUtility.generateResistances(map); 141 this.maxRadius = Math.max(1, maxRadius); 142 this.maxLOSRadius = 62; 143 decay = 1.0 / maxRadius; 144 this.radiusKind = radiusKind; 145 fovPermissiveness = 0.9; 146 lights = new LinkedHashMap<>(); 147 cache = new short[mapLimit][][]; 148 tmpCache = new short[mapLimit][][]; 149 losCache = new short[mapLimit][]; 150 ALL_WALLS = new short[maxRadius + 1][]; 151 for (int i = 0; i < maxRadius + 1; i++) { 152 ALL_WALLS[i] = ALL_WALL; 153 } 154 limit = 0x10000; 155 if(height <= 128) { 156 limit >>= 1; 157 if (width <= 128) { 158 limit >>= 1; 159 if (width <= 64) { 160 limit >>= 1; 161 if (height <= 64) { 162 limit >>= 1; 163 if (height <= 32) { 164 limit >>= 1; 165 if (width <= 32) { 166 limit >>= 1; 167 } 168 } 169 } 170 } 171 } 172 } 173 preloadMeasurements(); 174 complete = false; 175 } 176 177 /** 178 * Create an FOVCache for a given map (as a char[][]), caching all FOV radii from 0 up to and including maxRadius, 179 * using the given Radius enum to determine FOV shape. Upon calling cacheAllPerformance() or cacheAll(), 180 * (collectively, the caching methods), the object this creates will run a medium-quality, fairly permissive FOV 181 * calculation for every cell on the map using a number of threads equal to threadCount, and if cacheAll() 182 * was called, will then ensure symmetry (if cell A can see cell B, then it will make cell B able to see cell A even 183 * if it couldn't in an earlier step). At the same time as the first caching method call, this will calculate Line 184 * of Sight at maximum range (given by maxLOSRadius) for all cells. Walls will always have no cells in their FOV or 185 * in their LOS. 186 * @param map a char[][] as returned by SquidLib's map generators 187 * @param maxRadius the longest radius that will possibly need to be cached for FOV; LOS is separate 188 * @param maxLOSRadius the longest radius that will possibly need to be cached for LOS, must be less than 63 189 * @param radiusKind a Radius enum that determines the shape of each FOV area 190 * @param threadCount how many threads to use during the full-map calculations 191 */ 192 public FOVCache(char[][] map, int maxRadius, int maxLOSRadius, Radius radiusKind, int threadCount) 193 { 194 if(map == null || map.length == 0) 195 throw new UnsupportedOperationException("The map used by FOVCache must not be null or empty"); 196 NUM_THREADS = threadCount; 197 executor = Executors.newFixedThreadPool(NUM_THREADS); 198 width = map.length; 199 height = map[0].length; 200 if(width > 256 || height > 256) 201 throw new UnsupportedOperationException("Map size is too large to efficiently cache, aborting"); 202 mapLimit = width * height; 203 if(maxRadius <= 0 || maxRadius >= 63) 204 throw new UnsupportedOperationException("FOV radius is incorrect. Must be 0 < maxRadius < 63"); 205 if(maxLOSRadius <= 0 || maxLOSRadius >= 63) 206 throw new UnsupportedOperationException("LOS radius is incorrect. Must be 0 < maxLOSRadius < 63"); 207 fov = new FOV(FOV.SHADOW); 208 gradedFOV = new FOV(RIPPLE); 209 resMap = DungeonUtility.generateResistances(map); 210 this.maxRadius = Math.max(1, maxRadius); 211 this.maxLOSRadius = Math.max(1, maxLOSRadius); 212 decay = 1.0 / maxRadius; 213 this.radiusKind = radiusKind; 214 fovPermissiveness = 0.9; 215 lights = new LinkedHashMap<>(); 216 cache = new short[mapLimit][][]; 217 tmpCache = new short[mapLimit][][]; 218 losCache = new short[mapLimit][]; 219 ALL_WALLS = new short[maxRadius][]; 220 for (int i = 0; i < maxRadius; i++) { 221 ALL_WALLS[i] = ALL_WALL; 222 } 223 limit = 0x10000; 224 if(height <= 128) { 225 limit >>= 1; 226 if (width <= 128) { 227 limit >>= 1; 228 if (width <= 64) { 229 limit >>= 1; 230 if (height <= 64) { 231 limit >>= 1; 232 if (height <= 32) { 233 limit >>= 1; 234 if (width <= 32) { 235 limit >>= 1; 236 } 237 } 238 } 239 } 240 } 241 } 242 preloadMeasurements(); 243 complete = false; 244 } 245 246 /** 247 * Create an FOVCache for a given map (as a char[][]), caching all FOV radii from 0 up to and including maxRadius, 248 * using the given Radius enum to determine FOV shape. Upon calling cacheAllPerformance() or cacheAll(), 249 * (collectively, the caching methods), the object this creates will run a medium-quality, fairly permissive FOV 250 * calculation for every cell on the map using a number of threads equal to threadCount, and if cacheAll() 251 * was called, will then ensure symmetry (if cell A can see cell B, then it will make cell B able to see cell A even 252 * if it couldn't in an earlier step). At the same time as the first caching method call, this will calculate Line 253 * of Sight at maximum range (given by maxLOSRadius) for all cells. Walls will always have no cells in their FOV or 254 * in their LOS. This constructor also allows you to initialize light sources in the level using the lights 255 * parameter; any Coord keys should correspond to walkable cells (or they will be ignored), and the values will be 256 * the range those cells should light up.. 257 * @param map a char[][] as returned by SquidLib's map generators 258 * @param maxRadius the longest radius that will possibly need to be cached for FOV; LOS is separate 259 * @param maxLOSRadius the longest radius that will possibly need to be cached for LOS, must be less than 63 260 * @param radiusKind a Radius enum that determines the shape of each FOV area 261 * @param threadCount how many threads to use during the full-map calculations 262 * @param lights a Map of Coords (which should be walkable) to the radii they should light (not for moving lights) 263 */ 264 public FOVCache(char[][] map, int maxRadius, int maxLOSRadius, Radius radiusKind, int threadCount, Map<Coord, Integer> lights) 265 { 266 if(map == null || map.length == 0) 267 throw new UnsupportedOperationException("The map used by FOVCache must not be null or empty"); 268 NUM_THREADS = threadCount; 269 executor = Executors.newFixedThreadPool(NUM_THREADS); 270 width = map.length; 271 height = map[0].length; 272 if(width > 256 || height > 256) 273 throw new UnsupportedOperationException("Map size is too large to efficiently cache, aborting"); 274 mapLimit = width * height; 275 if(maxRadius <= 0 || maxRadius >= 63) 276 throw new UnsupportedOperationException("FOV radius is incorrect. Must be 0 < maxRadius < 63"); 277 if(maxLOSRadius <= 0 || maxLOSRadius >= 63) 278 throw new UnsupportedOperationException("LOS radius is incorrect. Must be 0 < maxLOSRadius < 63"); 279 fov = new FOV(FOV.SHADOW); 280 gradedFOV = new FOV(RIPPLE); 281 resMap = DungeonUtility.generateResistances(map); 282 this.maxRadius = Math.max(1, maxRadius); 283 this.maxLOSRadius = Math.max(1, maxLOSRadius); 284 decay = 1.0 / maxRadius; 285 this.radiusKind = radiusKind; 286 fovPermissiveness = 0.9; 287 this.lights = new LinkedHashMap<>(lights); 288 cache = new short[mapLimit][][]; 289 tmpCache = new short[mapLimit][][]; 290 losCache = new short[mapLimit][]; 291 ALL_WALLS = new short[maxRadius][]; 292 for (int i = 0; i < maxRadius; i++) { 293 ALL_WALLS[i] = ALL_WALL; 294 } 295 limit = 0x10000; 296 if(height <= 128) { 297 limit >>= 1; 298 if (width <= 128) { 299 limit >>= 1; 300 if (width <= 64) { 301 limit >>= 1; 302 if (height <= 64) { 303 limit >>= 1; 304 if (height <= 32) { 305 limit >>= 1; 306 if (width <= 32) { 307 limit >>= 1; 308 } 309 } 310 } 311 } 312 } 313 } 314 preloadMeasurements(); 315 complete = false; 316 } 317 318 private void preloadLights() 319 { 320 321 Iterator<Coord> it = lights.keySet().iterator(); 322 Coord pos; 323 while (it.hasNext()) 324 { 325 pos = it.next(); 326 if(resMap[pos.x][pos.y] >= 1.0) 327 it.remove(); 328 } 329 330 lightSources = lights.keySet().toArray(new Coord[lights.size()]); 331 lightBrightnesses = new int[lights.size()]; 332 for (int i = 0; i < lightSources.length; i++) { 333 lightBrightnesses[i] = lights.get(lightSources[i]); 334 } 335 } 336 337 private void preloadMeasurements() 338 { 339 levels = new double[maxRadius + 1][maxRadius + 1]; 340 //levels[maxRadius][maxRadius] = 1.0; 341 for (int i = 1; i <= maxRadius; i++) { 342 System.arraycopy(generateLightLevels(i), 0, levels[i], maxRadius - i + 1, i); 343 } 344 boolean[][] walls = new boolean[width][height]; 345 for (int i = 0; i < width; i++) { 346 for (int j = 0; j < height; j++) { 347 walls[i][j] = resMap[i][j] >= 1.0; 348 } 349 } 350 wallMap = pack(walls); 351 352 preloadLights(); 353 354 atan2Cache = new double[maxRadius * 2 + 1][maxRadius * 2 + 1]; 355 distanceCache = new short[maxRadius * 2 + 1][maxRadius * 2 + 1]; 356 waves = new Coord[maxRadius + 1][]; 357 waves[0] = new Coord[]{Coord.get(maxRadius, maxRadius)}; 358 359 ShortVLA[] positionsAtDistance = new ShortVLA[maxRadius + 1]; 360 for (int i = 0; i < maxRadius + 1; i++) { 361 positionsAtDistance[i] = new ShortVLA(i * 8 + 1); 362 } 363 short tmp, inverse_tmp; 364 for (int i = 0; i <= maxRadius; i++) { 365 for (int j = 0; j <= maxRadius; j++) { 366 tmp = distance(i, j); 367 inverse_tmp = (short)(maxRadius + 1 - tmp / 2); 368 369 atan2Cache[maxRadius + i][maxRadius + j] = Math.atan2(j, i); 370 if(atan2Cache[maxRadius + i][maxRadius + j] < 0) 371 atan2Cache[maxRadius + i][maxRadius + j] += PI2; 372 if(tmp > 0) { 373 atan2Cache[maxRadius - i][maxRadius + j] = Math.atan2(j, -i); 374 if(atan2Cache[maxRadius - i][maxRadius + j] < 0) 375 atan2Cache[maxRadius - i][maxRadius + j] += PI2; 376 377 atan2Cache[maxRadius + i][maxRadius - j] = Math.atan2(-j, i); 378 if(atan2Cache[maxRadius + i][maxRadius - j] < 0) 379 atan2Cache[maxRadius + i][maxRadius - j] += PI2; 380 381 atan2Cache[maxRadius - i][maxRadius - j] = Math.atan2(-j, -i); 382 if(atan2Cache[maxRadius - i][maxRadius - j] < 0) 383 atan2Cache[maxRadius - i][maxRadius - j] += PI2; 384 385 } 386 if(tmp / 2 <= maxRadius && inverse_tmp > 0) { 387 distanceCache[maxRadius + i][maxRadius + j] = inverse_tmp; 388 if (tmp > 0) { 389 distanceCache[maxRadius - i][maxRadius + j] = inverse_tmp; 390 distanceCache[maxRadius + i][maxRadius - j] = inverse_tmp; 391 distanceCache[maxRadius - i][maxRadius - j] = inverse_tmp; 392 positionsAtDistance[tmp / 2].add(zEncode((short) (maxRadius + i), (short) (maxRadius + j))); 393 if (i > 0) 394 positionsAtDistance[tmp / 2].add(zEncode((short) (maxRadius - i), (short) (maxRadius + j))); 395 if (j > 0) 396 positionsAtDistance[tmp / 2].add(zEncode((short) (maxRadius + i), (short) (maxRadius - j))); 397 if(i > 0 && j > 0) 398 positionsAtDistance[tmp / 2].add(zEncode((short) (maxRadius - i), (short) (maxRadius - j))); 399 400 }else { 401 positionsAtDistance[0].add(zEncode((short) maxRadius, (short) maxRadius)); 402 } 403 } 404 } 405 } 406 short[][] positionsZ = new short[maxRadius + 1][]; 407 for (int i = 0; i <= maxRadius; i++) { 408 positionsZ[i] = positionsAtDistance[i].toArray(); 409 waves[i] = new Coord[positionsZ[i].length]; 410 for (int j = 0; j < waves[i].length; j++) { 411 waves[i][j] = zDecode(positionsZ[i][j]); 412 } 413 } 414 directionAngles = new double[3][3]; 415 directionAngles[0][0] = Math.atan2(1,1); 416 directionAngles[0][1] = Math.atan2(0,1); 417 directionAngles[0][2] = Math.atan2(-1,1) + PI2; 418 directionAngles[1][0] = Math.atan2(1,0); 419 directionAngles[1][1] = 0; 420 directionAngles[1][2] = Math.atan2(-1,0) + PI2; 421 directionAngles[2][0] = Math.atan2(1,-1); 422 directionAngles[2][1] = Math.atan2(0,-1); 423 directionAngles[2][2] = Math.atan2(-1,-1) + PI2; 424 } 425 426 /** 427 * Packs FOV for a point as a center, and returns it to be stored. 428 * @param index an int that stores the x,y center of FOV as calculated by: x + y * width 429 * @return a multi-packed series of progressively wider FOV radii 430 */ 431 protected long storeCellFOV(int index) { 432 long startTime = System.currentTimeMillis(); 433 cache[index] = calculatePackedSlopeShadowFOV(index % width, index / width); 434 //cache[index] = calculatePackedExternalFOV(index % width, index / width); 435 return System.currentTimeMillis() - startTime; 436 } 437 438 /** 439 * Packs FOV for a point as a center, and returns it to be stored. 440 * @param index an int that stores the x,y center of FOV as calculated by: x + y * width 441 * @return a multi-packed series of progressively wider FOV radii 442 */ 443 protected long storeCellLOS(int index) { 444 long startTime = System.currentTimeMillis(); 445 losCache[index] = calculatePackedLOS(index % width, index / width); 446 return System.currentTimeMillis() - startTime; 447 } 448 449 /** 450 * Uses previously cached FOV and makes it symmetrical. Also handles distant lights 451 * @param index an int that stores the x,y center of FOV as calculated by: x + y * width 452 * @return a multi-packed series of progressively wider FOV radii 453 */ 454 protected long storeCellSymmetry(int index) { 455 long startTime = System.currentTimeMillis(); 456 tmpCache[index] = improveQuality(index % width, index / width); 457 return System.currentTimeMillis() - startTime; 458 } 459 460 /** 461 * Packs FOV for the given viewer's X and Y as a center, and returns the packed data to be stored. 462 * @param viewerX an int less than 256 and less than width 463 * @param viewerY an int less than 256 and less than height 464 * @return a multi-packed series of progressively wider FOV radii 465 */ 466 @SuppressWarnings("unused") 467 private short[][] calculatePackedExternalFOV(int viewerX, int viewerY) 468 { 469 if(viewerX < 0 || viewerY < 0 || viewerX >= width || viewerY >= height) 470 return ALL_WALLS; 471 if(resMap[viewerX][viewerY] >= 1.0) 472 { 473 return ALL_WALLS; 474 } 475 long on = 0, current = 0; 476 ShortVLA[] packing = new ShortVLA[maxRadius]; 477 int[] skip = new int[maxRadius]; 478 short x, y; 479 short[][] packed = new short[maxRadius][]; 480 double[][] fovMap; 481 for(int l = 0; l < maxRadius; l++) { 482 483 fovMap = fov.calculateFOV(resMap, viewerX, viewerY, l + 1, radiusKind); 484 packing[l] = new ShortVLA(64); 485 for (int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip[l]++) { 486 487 x = hilbertX[i]; 488 y = hilbertY[i]; 489 if (x >= width || y >= height) { 490 if ((on & (1L << l)) != 0L) { 491 on ^= (1L << l); 492 packing[l].add((short) skip[l]); 493 skip[l] = 0; 494 } 495 continue; 496 } 497 ml++; 498 // sets the bit at position l in current to 1 if the following is true, 0 if it is false: 499 // fovMap[x][y] > levels[l] 500 // looks more complicated than it is. 501 current ^= ((fovMap[x][y] > 0.0 ? -1 : 0) ^ current) & (1 << l); 502 if (((current >> l) & 1L) != ((on >> l) & 1L)) { 503 packing[l].add((short) skip[l]); 504 skip[l] = 0; 505 on = current; 506 507 // sets the bit at position l in on to the same as the bit at position l in current. 508 on ^= (-((current >> l) & 1L) ^ on) & (1L << l); 509 510 } 511 } 512 513 if (((on >> l) & 1L) == 1L) 514 packing[l].add((short) skip[l]); 515 if(packing[l].size == 0) 516 packed[l] = ALL_WALL; 517 else 518 packed[l] = packing[l].toArray(); 519 } 520 return packed; 521 } 522 523 /** 524 * Packs FOV for the given viewer's X and Y as a center, and returns the packed data to be stored. 525 * @param viewerX an int less than 256 and less than width 526 * @param viewerY an int less than 256 and less than height 527 * @return a packed FOV map for radius equal to maxLOSRadius 528 */ 529 public short[] calculatePackedLOS(int viewerX, int viewerY) 530 { 531 if(viewerX < 0 || viewerY < 0 || viewerX >= width || viewerY >= height) 532 return ALL_WALL; 533 if(resMap[viewerX][viewerY] >= 1.0) 534 { 535 return ALL_WALL; 536 } 537 return pack(fov.calculateFOV(resMap, viewerX, viewerY, maxLOSRadius, radiusKind)); 538 } 539 540 /** 541 * Packs FOV for the given viewer's X and Y as a center, and returns the packed data to be stored. 542 * @param viewerX an int less than 256 and less than width 543 * @param viewerY an int less than 256 and less than height 544 * @return a multi-packed series of progressively wider FOV radii 545 */ 546 public short[][] calculatePackedSlopeShadowFOV(int viewerX, int viewerY) { 547 if (viewerX < 0 || viewerY < 0 || viewerX >= width || viewerY >= height) 548 return ALL_WALLS; 549 if (resMap[viewerX][viewerY] >= 1.0) { 550 return ALL_WALLS; 551 } 552 return packMulti(slopeShadowFOV(viewerX, viewerY), maxRadius + 1); 553 } 554 555 /** 556 * Packs FOV for the given viewer's X and Y as a center, and returns the packed data to be stored. 557 * @param viewerX an int less than 256 and less than width 558 * @param viewerY an int less than 256 and less than height 559 * @return a multi-packed series of progressively wider FOV radii 560 */ 561 public short[][] calculatePackedWaveFOV(int viewerX, int viewerY) { 562 if (viewerX < 0 || viewerY < 0 || viewerX >= width || viewerY >= height) 563 return ALL_WALLS; 564 if (resMap[viewerX][viewerY] >= 1.0) { 565 return ALL_WALLS; 566 } 567 return packMulti(waveFOV(viewerX, viewerY), maxRadius + 1); 568 } 569 public short[][] getCacheEntry(int x, int y) 570 { 571 return cache[x + y * width]; 572 } 573 public short[] getCacheEntry(int x, int y, int radius) 574 { 575 return cache[x + y * width][maxRadius - radius]; 576 } 577 578 public short[] getLOSEntry(int x, int y) 579 { 580 return losCache[x + y * width]; 581 } 582 583 public boolean queryCache(int visionRange, int viewerX, int viewerY, int targetX, int targetY) 584 { 585 return queryPacked(cache[viewerX + viewerY * width][maxRadius - visionRange], targetX, targetY); 586 } 587 public boolean isCellVisible(int visionRange, int viewerX, int viewerY, int targetX, int targetY) 588 { 589 return queryPacked(cache[viewerX + viewerY * width][maxRadius - visionRange], targetX, targetY) || 590 queryPacked(cache[targetX + targetY * width][maxRadius - visionRange], viewerX, viewerY); 591 } 592 public boolean queryLOS(int viewerX, int viewerY, int targetX, int targetY) 593 { 594 return queryPacked(losCache[viewerX + viewerY * width], targetX, targetY); 595 } 596 597 private long arrayMemoryUsage(int length, long bytesPerItem) 598 { 599 return (((bytesPerItem * length + 12 - 1) / 8) + 1) * 8L; 600 } 601 @SuppressWarnings("unused") 602 private long arrayMemoryUsage2D(int xSize, int ySize, long bytesPerItem) 603 { 604 return arrayMemoryUsage(xSize, (((bytesPerItem * ySize + 12 - 1) / 8) + 1) * 8L); 605 } 606 private int arrayMemoryUsageJagged(short[][] arr) 607 { 608 int ctr = 0; 609 for (int i = 0; i < arr.length; i++) { 610 ctr += arrayMemoryUsage(arr[i].length, 2); 611 } 612 return (((ctr + 12 - 1) / 8) + 1) * 8; 613 } 614 public long approximateMemoryUsage() 615 { 616 long ctr = 0; 617 for (int i = 0; i < cache.length; i++) { 618 ctr += arrayMemoryUsageJagged(cache[i]); 619 } 620 ctr = (((ctr + 12L - 1L) / 8L) + 1L) * 8L; 621 ctr += (((arrayMemoryUsageJagged(losCache) + 12L - 1L) / 8L) + 1L) * 8L; 622 return ctr; 623 } 624 625 /* 626 //needs rewrite, must store the angle a ray traveled at to get around an obstacle, and propagate it to the end of 627 //the ray. It should check if the angle theta for a given point is too different from the angle in angleMap. 628 private byte[][] waveFOVWIP(int viewerX, int viewerY) { 629 byte[][] gradientMap = new byte[width][height]; 630 double[][] angleMap = new double[2 * maxRadius + 1][2 * maxRadius + 1]; 631 for (int i = 0; i < angleMap.length; i++) { 632 Arrays.fill(angleMap[i], -20); 633 } 634 gradientMap[viewerX][viewerY] = (byte)(2 * maxRadius); 635 Direction[] dirs = (radiusKind == Radius.DIAMOND || radiusKind == Radius.OCTAHEDRON) 636 ? Direction.CARDINALS : Direction.OUTWARDS; 637 int cx, cy, ccwAdjX, ccwAdjY, cwAdjX, cwAdjY, ccwGridX, ccwGridY, cwGridX, cwGridY; 638 Coord pt; 639 double theta, angleCW, angleCCW; 640 byte dist; 641 boolean blockedCCW, blockedCW, isStraightCCW; 642 for(int w = 0; w < waves.length; w++) 643 { 644 for(int c = 0; c < waves[w].length; c++) 645 { 646 pt = waves[w][c]; 647 cx = viewerX - maxRadius + pt.x; 648 cy = viewerY - maxRadius + pt.y; 649 if(cx < width && cx >= 0 && cy < height && cy >= 0) 650 { 651 theta = atan2Cache[pt.x][pt.y]; 652 dist = (byte)(distanceCache[pt.x][pt.y ]); 653 654 if(w <= 0) 655 { 656 gradientMap[cx][cy] = dist; 657 } 658 else { 659 switch ((int) Math.floor(theta / QUARTER_PI)) { 660 661 //positive x, postive y (lower on screen), closer to x-axis 662 case 0: 663 cwAdjX = pt.x - 1; 664 cwAdjY = pt.y; 665 angleCW = directionAngles[0][1]; 666 isStraightCCW = false; 667 ccwAdjX = pt.x - 1; 668 ccwAdjY = pt.y - 1; 669 angleCCW = directionAngles[0][0]; 670 break; 671 //positive x, postive y (lower on screen), closer to y-axis 672 case 1: 673 cwAdjX = pt.x - 1; 674 cwAdjY = pt.y - 1; 675 angleCW = directionAngles[0][0]; 676 ccwAdjX = pt.x; 677 ccwAdjY = pt.y - 1; 678 angleCCW = directionAngles[1][0]; 679 isStraightCCW = true; 680 break; 681 //negative x, postive y (lower on screen), closer to y-axis 682 case 2: 683 cwAdjX = pt.x; 684 cwAdjY = pt.y - 1; 685 angleCW = directionAngles[1][0]; 686 isStraightCCW = false; 687 ccwAdjX = pt.x + 1; 688 ccwAdjY = pt.y - 1; 689 angleCCW = directionAngles[2][0]; 690 break; 691 //negative x, postive y (lower on screen), closer to x-axis 692 case 3: 693 cwAdjX = pt.x + 1; 694 cwAdjY = pt.y - 1; 695 angleCW = directionAngles[2][0]; 696 ccwAdjX = pt.x + 1; 697 ccwAdjY = pt.y; 698 angleCCW = directionAngles[2][1]; 699 isStraightCCW = true; 700 break; 701 702 //negative x, negative y (higher on screen), closer to x-axis 703 case 4: 704 cwAdjX = pt.x + 1; 705 cwAdjY = pt.y + 1; 706 angleCW = directionAngles[2][2]; 707 ccwAdjX = pt.x + 1; 708 ccwAdjY = pt.y; 709 angleCCW = directionAngles[2][1]; 710 isStraightCCW = false; 711 break; 712 //negative x, negative y (higher on screen), closer to y-axis 713 case 5: 714 cwAdjX = pt.x + 1; 715 cwAdjY = pt.y + 1; 716 angleCW = directionAngles[2][2]; 717 ccwAdjX = pt.x; 718 ccwAdjY = pt.y + 1; 719 angleCCW = directionAngles[1][2]; 720 isStraightCCW = true; 721 break; 722 //positive x, negative y (higher on screen), closer to y-axis 723 case 6: 724 cwAdjX = pt.x; 725 cwAdjY = pt.y + 1; 726 angleCW = directionAngles[1][2]; 727 isStraightCCW = false; 728 ccwAdjX = pt.x - 1; 729 ccwAdjY = pt.y + 1; 730 angleCCW = directionAngles[0][2]; 731 break; 732 //positive x, negative y (higher on screen), closer to x-axis 733 default: 734 cwAdjX = pt.x - 1; 735 cwAdjY = pt.y + 1; 736 angleCW = directionAngles[0][2]; 737 ccwAdjX = pt.x - 1; 738 ccwAdjY = pt.y; 739 angleCCW = directionAngles[0][1]; 740 isStraightCCW = true; 741 break; 742 } 743 /* 744 angleCCW = (((Math.abs(atan2Cache[ccwAdjX][ccwAdjY] - angleCCW) > Math.PI) 745 ? atan2Cache[ccwAdjX][ccwAdjY] + angleCCW + PI2 746 : atan2Cache[ccwAdjX][ccwAdjY] + angleCCW) 747 * 0.5) % PI2; 748 //(angleCCW + atan2Cache[ccwAdjX][ccwAdjY]) * 0.5; 749 angleCW = (((Math.abs(atan2Cache[cwAdjX][cwAdjY] - angleCW) > Math.PI) 750 ? atan2Cache[cwAdjX][cwAdjY] + angleCW + PI2 751 : atan2Cache[cwAdjX][cwAdjY] + angleCW) 752 * 0.5) % PI2; 753 //(angleCW + atan2Cache[cwAdjX][cwAdjY]) * 0.5; 754 755 * / 756 angleCCW = atan2Cache[ccwAdjX][ccwAdjY]; 757 //(angleCCW + atan2Cache[ccwAdjX][ccwAdjY]) * 0.5; 758 angleCW = atan2Cache[cwAdjX][cwAdjY]; 759 //(angleCW + atan2Cache[cwAdjX][cwAdjY]) * 0.5; 760 761 762 cwGridX = cwAdjX + viewerX - maxRadius; 763 ccwGridX = ccwAdjX + viewerX - maxRadius; 764 cwGridY = cwAdjY + viewerY - maxRadius; 765 ccwGridY = ccwAdjY + viewerY - maxRadius; 766 767 blockedCW = cwGridX >= width || cwGridY >= height || cwGridX < 0 || cwGridY < 0 || 768 resMap[cwGridX][cwGridY] > 0.5 || 769 angleMap[cwAdjX][cwAdjY] >= PI2; 770 blockedCCW = ccwGridX >= width || ccwGridY >= height || ccwGridX < 0 || ccwGridY < 0 || 771 resMap[ccwGridX][ccwGridY] > 0.5 || 772 angleMap[ccwAdjX][ccwAdjY] >= PI2; 773 774 if (blockedCW && blockedCCW) { 775 angleMap[pt.x][pt.y] = PI2; 776 continue; 777 } 778 if (theta % (HALF_PI - 0.00125) < 0.005) 779 if (isStraightCCW) { 780 if (blockedCCW) { 781 angleMap[pt.x][pt.y] = PI2; 782 gradientMap[cx][cy] = dist; 783 continue; 784 } 785 else 786 angleMap[pt.x][pt.y] = theta; 787 } else { 788 if (blockedCW) { 789 angleMap[pt.x][pt.y] = PI2; 790 gradientMap[cx][cy] = dist; 791 continue; 792 } 793 else 794 angleMap[pt.x][pt.y] = theta; 795 } 796 else if(theta % (QUARTER_PI - 0.0025) < 0.005) 797 if (isStraightCCW) { 798 if (blockedCW) { 799 angleMap[pt.x][pt.y] = PI2; 800 gradientMap[cx][cy] = dist; 801 continue; 802 } 803 else 804 angleMap[pt.x][pt.y] = theta; 805 } else { 806 if (blockedCCW) { 807 angleMap[pt.x][pt.y] = PI2; 808 gradientMap[cx][cy] = dist; 809 continue; 810 } 811 else 812 angleMap[pt.x][pt.y] = theta; 813 } 814 else { 815 if (blockedCW) { 816 angleMap[pt.x][pt.y] = angleMap[ccwAdjX][ccwAdjY]; 817// angleMap[pt.x][pt.y] = Math.max(angleMap[ccwAdjX][ccwAdjY], 818// (theta - (angleCCW - theta + PI2) % PI2 * 0.5 + PI2) % PI2); 819// (theta - angleCCW > Math.PI) 820// ? (theta - (angleCCW - theta + PI2) * 0.5) % PI2 821// : theta - (angleCCW - theta + PI2) % PI2 * 0.5; 822 //angleMap[pt.x][pt.y] = angleCCW; 823 824 // (((Math.abs(theta - angleCCW) > Math.PI) 825 // ? theta + angleCCW + PI2 826 // : theta + angleCCW) 827 // * 0.5) % PI2; 828 //angleMap[cwAdjX - viewerX + maxRadius][cwAdjY - viewerY + maxRadius]; 829 //Math.abs(angleMap[cwAdjX - viewerX + maxRadius][cwAdjY - viewerY + maxRadius] - 830 831 //angleMap[pt.x][pt.y] = Math.abs(theta - angleCCW) + 832 // angleMap[cwAdjX - viewerX + maxRadius][cwAdjY - viewerY + maxRadius]; 833 834 } else if (blockedCCW) { 835 angleMap[pt.x][pt.y] = angleMap[cwAdjX][cwAdjY]; 836// angleMap[pt.x][pt.y] = Math.max(angleMap[cwAdjX][cwAdjY], 837// (theta + (theta - angleCW + PI2) % PI2 * 0.5 + PI2) % PI2); 838// (angleCW - theta > Math.PI) 839// ? theta + (theta - angleCW + PI2) % PI2 * 0.5 840// : (theta + (theta - angleCW + PI2) * 0.5) % PI2; 841 //angleCW; 842 843 //angleMap[ccwAdjX - viewerX + maxRadius][ccwAdjY - viewerY + maxRadius]; 844 //angleMap[ccwAdjX - viewerX + maxRadius][ccwAdjY - viewerY + maxRadius] 845 } 846 else 847 { 848 double cwTemp = angleMap[cwAdjX][cwAdjY], ccwTemp = angleMap[ccwAdjX][ccwAdjY]; 849 if(cwTemp < 0) 850 cwTemp = (atan2Cache[cwAdjX][cwAdjY]); 851 if(ccwTemp < 0) 852 ccwTemp = (atan2Cache[ccwAdjX][ccwAdjY]); 853 if(cwTemp != atan2Cache[cwAdjX][cwAdjY] && 854 ccwTemp != atan2Cache[ccwAdjX][ccwAdjY]) 855 angleMap[pt.x][pt.y] = 0.5 * (cwTemp + ccwTemp); 856 else if(ccwTemp != atan2Cache[ccwAdjX][ccwAdjY]) 857 angleMap[pt.x][pt.y] = ccwTemp; 858 else if(cwTemp != atan2Cache[cwAdjX][cwAdjY]) 859 angleMap[pt.x][pt.y] = cwTemp; 860 else 861 angleMap[pt.x][pt.y] = theta; 862 } 863 /* 864 865 else if (!blockedCW) 866 angleMap[pt.x][pt.y] = (angleMap[cwAdjX][cwAdjY] != atan2Cache[cwAdjX][cwAdjY]) 867 ? angleMap[cwAdjX][cwAdjY] 868 : theta; 869 else 870 angleMap[pt.x][pt.y] = (angleMap[ccwAdjX][ccwAdjY] != atan2Cache[ccwAdjX][ccwAdjY]) 871 ? angleMap[ccwAdjX][ccwAdjY] 872 : theta; 873 * / 874 } 875 if(Math.abs(angleMap[pt.x][pt.y] - theta) <= 0.001 || resMap[pt.x][pt.y] > 0.5) 876 gradientMap[cx][cy] = dist; 877 else 878 angleMap[pt.x][pt.y] = PI2 * 2; 879 } 880 } 881 } 882 } 883 884 return gradientMap; 885 } 886 */ 887 public byte[][] waveFOV(int viewerX, int viewerY) { 888 byte[][] gradientMap = new byte[width][height]; 889 double[][] angleMap = new double[2 * maxRadius + 1][2 * maxRadius + 1]; 890 gradientMap[viewerX][viewerY] = (byte)(1 + maxRadius); 891 int cx, cy, nearCWx, nearCWy, nearCCWx, nearCCWy; 892 Coord pt; 893 double theta, angleCW, angleCCW, straight; 894 byte dist; 895 boolean blockedCCW, blockedCW; 896 for(int w = 0; w < waves.length; w++) 897 { 898 for(int c = 0; c < waves[w].length; c++) 899 { 900 pt = waves[w][c]; 901 cx = viewerX - maxRadius + pt.x; 902 cy = viewerY - maxRadius + pt.y; 903 if(cx < width && cx >= 0 && cy < height && cy >= 0) 904 { 905 theta = atan2Cache[pt.x][pt.y]; 906 dist = (byte)(distanceCache[pt.x][pt.y ]); 907 908 if(w <= 0) 909 { 910 gradientMap[cx][cy] = dist; 911 } 912 else { 913 switch ((int) Math.floor(theta / QUARTER_PI)) { 914 915 //positive x, postive y, closer to x-axis 916 case 0: 917 nearCCWx = pt.x - 1; 918 nearCCWy = pt.y; 919 angleCCW = directionAngles[0][1]; //atan2Cache[nearCCWx][nearCCWy]; 920 straight = angleCCW; 921 nearCWx = pt.x - 1; 922 nearCWy = pt.y - 1; 923 angleCW = directionAngles[0][0]; //atan2Cache[nearCWx][nearCWy]; 924 break; 925 //positive x, postive y, closer to y-axis 926 case 1: 927 nearCWx = pt.x; 928 nearCWy = pt.y - 1; 929 angleCW = directionAngles[1][0]; 930 straight = angleCW; 931 nearCCWx = pt.x - 1; 932 nearCCWy = pt.y - 1; 933 angleCCW = directionAngles[0][0]; 934 break; 935 //negative x, postive y, closer to y-axis 936 case 2: 937 nearCCWx = pt.x; 938 nearCCWy = pt.y - 1; 939 angleCCW = directionAngles[1][0]; 940 straight = angleCCW; 941 nearCWx = pt.x + 1; 942 nearCWy = pt.y - 1; 943 angleCW = directionAngles[2][0]; 944 break; 945 //negative x, postive y, closer to x-axis 946 case 3: 947 nearCCWx = pt.x + 1; 948 nearCCWy = pt.y; 949 angleCCW = directionAngles[2][1]; 950 straight = angleCCW; 951 nearCWx = pt.x + 1; 952 nearCWy = pt.y - 1; 953 angleCW = directionAngles[2][0]; 954 break; 955 956 //negative x, negative y, closer to x-axis 957 case 4: 958 nearCWx = pt.x + 1; 959 nearCWy = pt.y; 960 angleCW = -directionAngles[2][1]; 961 straight = angleCW; 962 nearCCWx = pt.x + 1; 963 nearCCWy = pt.y + 1; 964 angleCCW = directionAngles[2][2]; 965 966 break; 967 //negative x, negative y, closer to y-axis 968 case 5: 969 nearCWx = pt.x; 970 nearCWy = pt.y + 1; 971 angleCW = directionAngles[1][2]; 972 straight = angleCW; 973 nearCCWx = pt.x + 1; 974 nearCCWy = pt.y + 1; 975 angleCCW = directionAngles[2][2]; 976 break; 977 //positive x, negative y, closer to y-axis 978 case 6: 979 nearCCWx = pt.x; 980 nearCCWy = pt.y + 1; 981 angleCCW = directionAngles[1][2]; 982 straight = angleCCW; 983 nearCWx = pt.x - 1; 984 nearCWy = pt.y + 1; 985 angleCW = directionAngles[0][2]; 986 break; 987 //positive x, negative y, closer to x-axis 988 default: 989 nearCWx = pt.x - 1; 990 nearCWy = pt.y; 991 angleCW = directionAngles[0][1]; 992 straight = angleCW; 993 nearCCWx = pt.x - 1; 994 nearCCWy = pt.y + 1; 995 angleCCW = directionAngles[0][2]; 996 break; 997 } 998 nearCCWx += viewerX - maxRadius; 999 nearCWx += viewerX - maxRadius; 1000 nearCCWy += viewerY - maxRadius; 1001 nearCWy += viewerY - maxRadius; 1002 1003 blockedCCW = resMap[nearCCWx][nearCCWy] > 0.5 || 1004 angleMap[nearCCWx - viewerX + maxRadius][nearCCWy - viewerY + maxRadius] >= PI2; 1005 blockedCW = resMap[nearCWx][nearCWy] > 0.5 || 1006 angleMap[nearCWx - viewerX + maxRadius][nearCWy - viewerY + maxRadius] >= PI2; 1007 1008 if( theta == 0 || theta == Math.PI || (Math.abs(theta) - HALF_PI < 0.005 && Math.abs(theta) - HALF_PI > -0.005)) 1009 angleMap[pt.x][pt.y] = (straight == angleCCW) 1010 ? (blockedCCW) 1011 ? PI2 1012 : angleMap[nearCCWx - viewerX + maxRadius][nearCCWy - viewerY + maxRadius] 1013 : (blockedCW) 1014 ? PI2 1015 : angleMap[nearCWx - viewerX + maxRadius][nearCWy - viewerY + maxRadius]; 1016 else { 1017 if (blockedCW && blockedCCW) { 1018 angleMap[pt.x][pt.y] = PI2; 1019 continue; 1020 } 1021 if (blockedCW) { 1022 angleMap[pt.x][pt.y] = Math.abs(theta - angleCCW) + SLIVER_PI; 1023 //angleMap[nearCCWx - viewerX + maxRadius][nearCCWy - viewerY + maxRadius]; 1024 //Math.abs(angleMap[nearCCWx - viewerX + maxRadius][nearCCWy - viewerY + maxRadius] - 1025 1026 1027 //angleMap[pt.x][pt.y] = Math.abs(theta - angleCCW) + 1028 // angleMap[nearCCWx - viewerX + maxRadius][nearCCWy - viewerY + maxRadius]; 1029 1030 } else if (blockedCCW) { 1031 angleMap[pt.x][pt.y] = Math.abs(angleCW - theta) + SLIVER_PI; 1032 //angleMap[nearCWx - viewerX + maxRadius][nearCWy - viewerY + maxRadius]; 1033 //angleMap[nearCWx - viewerX + maxRadius][nearCWy - viewerY + maxRadius] 1034 } 1035 if (!blockedCW) 1036 angleMap[pt.x][pt.y] += 0.5 * 1037 angleMap[nearCWx - viewerX + maxRadius][nearCWy - viewerY + maxRadius]; 1038 if (!blockedCCW) 1039 angleMap[pt.x][pt.y] += 0.5 * 1040 angleMap[nearCCWx - viewerX + maxRadius][nearCCWy - viewerY + maxRadius]; 1041 } 1042 if(angleMap[pt.x][pt.y] <= fovPermissiveness) 1043 gradientMap[cx][cy] = dist; 1044 else 1045 angleMap[pt.x][pt.y] = PI2; 1046 } 1047 } 1048 } 1049 } 1050 1051 return gradientMap; 1052 } 1053 1054 public byte[][] slopeShadowFOV(int viewerX, int viewerY) 1055 { 1056 byte[][] lightMap = new byte[width][height]; 1057 lightMap[viewerX][viewerY] = (byte)(1 + maxRadius); 1058 1059 for (Direction d : Direction.DIAGONALS) { 1060 slopeShadowCast(1, 1.0, 0.0, 0, d.deltaX, d.deltaY, 0, viewerX, viewerY, lightMap); 1061 slopeShadowCast(1, 1.0, 0.0, d.deltaX, 0, 0, d.deltaY, viewerX, viewerY, lightMap); 1062 } 1063 return lightMap; 1064 } 1065 1066 private byte[][] slopeShadowCast(int row, double start, double end, int xx, int xy, int yx, int yy, 1067 int viewerX, int viewerY, byte[][] lightMap) { 1068 double newStart = 0; 1069 if (start < end) { 1070 return lightMap; 1071 } 1072 int width = lightMap.length; 1073 int height = lightMap[0].length; 1074 1075 boolean blocked = false; 1076 int dist; 1077 for (int distance = row; distance <= maxRadius && !blocked; distance++) { 1078 int deltaY = -distance; 1079 for (int deltaX = -distance; deltaX <= 0; deltaX++) { 1080 int currentX = viewerX + deltaX * xx + deltaY * xy; 1081 int currentY = viewerY + deltaX * yx + deltaY * yy; 1082 double leftSlope = (deltaX - 0.5f) / (deltaY + 0.5f); 1083 double rightSlope = (deltaX + 0.5f) / (deltaY - 0.5f); 1084 1085 if (!(currentX >= 0 && currentY >= 0 && currentX < width && currentY < height 1086 && currentX - viewerX + maxRadius >= 0 && currentX - viewerX <= maxRadius 1087 && currentY - viewerY + maxRadius >= 0 && currentY - viewerY <= maxRadius) 1088 || start < rightSlope) { 1089 continue; 1090 } else if (end > leftSlope) { 1091 break; 1092 } 1093 1094 dist = distanceCache[currentX - viewerX + maxRadius][currentY - viewerY + maxRadius]; 1095 //check if it's within the lightable area and light if needed 1096 if (dist <= maxRadius) { 1097 lightMap[currentX][currentY] = (byte) dist; 1098 } 1099 1100 if (blocked) { //previous cell was a blocking one 1101 if (resMap[currentX][currentY] >= 0.5) {//hit a wall 1102 newStart = rightSlope; 1103 } else { 1104 blocked = false; 1105 start = newStart; 1106 } 1107 } else { 1108 if (resMap[currentX][currentY] >= 0.5 && distance < maxRadius) {//hit a wall within sight line 1109 blocked = true; 1110 lightMap = slopeShadowCast(distance + 1, start, leftSlope, xx, xy, yx, yy, viewerX, viewerY, lightMap); 1111 newStart = rightSlope; 1112 } 1113 } 1114 } 1115 } 1116 return lightMap; 1117 } 1118 1119 1120 public short[][] improveQuality(int viewerX, int viewerY) { 1121 if(!complete) throw new IllegalStateException( 1122 "cacheAllPerformance() must be called before improveQuality() to fill the cache."); 1123 1124 if (viewerX < 0 || viewerY < 0 || viewerX >= width || viewerY >= height) 1125 return ALL_WALLS; 1126 if (resMap[viewerX][viewerY] >= 1.0) { 1127 return ALL_WALLS; 1128 } 1129 short myHilbert = (short)posToHilbert(viewerX, viewerY); 1130 ShortVLA packing = new ShortVLA(128); 1131 short[][] packed = new short[maxRadius + 1][], cached = cache[viewerX + viewerY * width]; 1132 short[] losCached = losCache[viewerX + viewerY * width]; 1133 1134 ///* 1135 //short[] perimeter = allPackedHilbert(fringe(losCached, 2, width, height)); 1136 int xr = Math.max(0, viewerX - 1 - maxLOSRadius), yr = Math.max(0, viewerY - 1 - maxLOSRadius), 1137 wr = Math.min(width - 1 - viewerX, maxLOSRadius * 2 + 3), 1138 hr = Math.min(height - 1 - viewerY, maxLOSRadius * 2 + 3); 1139 short[] perimeter = rectangleHilbert(xr, yr, wr, hr); 1140 short p_x, p_y; 1141 for (int i = 0; i < perimeter.length; i++) { 1142 p_x = hilbertX[perimeter[i] & 0xffff]; 1143 p_y = hilbertY[perimeter[i] & 0xffff]; 1144 if (queryPackedHilbert(losCache[p_x + p_y * width], myHilbert)) 1145 packing.add(perimeter[i]); 1146 } 1147 //*/ 1148 /* 1149 boolean[][] losUnpacked = unpack(losCached, width, height); 1150 for (int x = Math.max(0, viewerX - 62); x <= Math.min(viewerX + 62, width - 1); x++) { 1151 for (int y = Math.max(0, viewerY - 62); y <= Math.min(viewerY + 62, height - 1); y++) { 1152 if (losUnpacked[x][y]) 1153 continue; 1154 if(losCache[x + y * width] == ALL_WALL) 1155 continue; 1156 if (distance(x - viewerX, y - viewerY) / 2 > 62) 1157 continue; 1158 if (queryPackedHilbert(losCache[x + y * width], myHilbert)) 1159 packing.add((short) posToHilbert(x, y)); 1160 } 1161 } 1162 */ 1163 losCache[viewerX + viewerY * width] = insertSeveralPacked(losCached, packing.asInts()); 1164 1165 1166 for (int l = 0; l <= maxRadius; l++) { 1167 packing.clear(); 1168 xr = Math.max(0, viewerX - l); 1169 yr = Math.max(0, viewerY - l); 1170 wr = Math.min(width - viewerX + l, l * 2 + 1); 1171 hr = Math.min(height - viewerY + l, l * 2 + 1); 1172 perimeter = rectangleHilbert(xr, yr, wr, hr); 1173 1174 //short p_x, p_y; 1175 for (int i = 0; i < perimeter.length; i++) { 1176 if(queryPackedHilbert(cached[maxRadius - l], perimeter[i])) { 1177 packing.add(perimeter[i]); 1178 continue; 1179 } 1180 p_x = hilbertX[perimeter[i] & 0xffff]; 1181 p_y = hilbertY[perimeter[i] & 0xffff]; 1182 1183 if(cache[p_x + p_y * width] == ALL_WALLS) 1184 continue; 1185 1186 if (distance(p_x - viewerX, p_y - viewerY) / 2 > l) 1187 continue; 1188 if (queryPackedHilbert(cache[p_x + p_y * width][maxRadius - l], myHilbert)) 1189 packing.add(perimeter[i]); 1190 } 1191 /* 1192 knownSeen = cached[maxRadius - l]; 1193 for (int x = Math.max(0, viewerX - l); x <= Math.min(viewerX + l, width - 1); x++) { 1194 for (int y = Math.max(0, viewerY - l); y <= Math.min(viewerY + l, height - 1); y++) { 1195 if(cache[x + y * width] == ALL_WALLS) 1196 continue; 1197 if (distance(x - viewerX, y - viewerY) / 2 > l) 1198 continue; 1199 short i = (short) posToHilbert(x, y); 1200 if (queryPackedHilbert(knownSeen, i)) 1201 continue; 1202 if (queryPackedHilbert(cache[x + y * width][maxRadius - l], myHilbert)) 1203 packing.add(i); 1204 } 1205 }*/ 1206 packed[maxRadius - l] = packSeveral(packing.asInts()); 1207 Coord light; 1208 for (int i = 0; i < lightSources.length; i++) { 1209 light = lightSources[i]; 1210 packed[maxRadius - l] = unionPacked(packed[maxRadius - l], differencePacked(intersectPacked(losCached, 1211 cache[light.x + light.y * width][maxRadius - lightBrightnesses[i]]), wallMap)); 1212 } 1213 } 1214 1215 return packed; 1216 } 1217 1218 /** 1219 * Runs FOV calculations on another thread, without interrupting this one. Before using the cache, you should call 1220 * awaitCachePerformance() to ensure this method has finished on its own thread, but be aware that this will cause 1221 * the thread that calls awaitCachePerformance() to essentially freeze until FOV calculations are over. 1222 */ 1223 private void cacheAllPerformance() { 1224 if(performanceThread != null || complete) 1225 return; 1226 performanceThread = new Thread(new PerformanceUnit()); 1227 performanceThread.start(); 1228 } 1229 1230 /** 1231 * If FOV calculations from cacheAllPerformance() are being done on another thread, calling this method will make 1232 * the current thread wait for the FOV calculations' thread to finish, "freezing" the current thread until it does. 1233 * This ensures the cache will be complete after this method returns true, and if this method returns false, then 1234 * something has gone wrong. 1235 * @return true if cacheAllPerformance() has successfully completed, false otherwise. 1236 */ 1237 @SuppressWarnings("unused") 1238 private boolean awaitCachePerformance() 1239 { 1240 if(performanceThread == null && !complete) 1241 cacheAllPerformance(); 1242 if(complete) return true; 1243 try { 1244 performanceThread.join(); 1245 } catch (InterruptedException e) { 1246 return false; 1247 } 1248 return complete; 1249 } 1250 1251 /** 1252 * Runs FOV calculations on another thread, without interrupting this one, then performs additional quality tweaks 1253 * and adds any distant lights, if there were any in the constructor. Before using the cache, you should call 1254 * awaitCache() to ensure this method has finished on its own thread, but be aware that this will cause 1255 * the thread that calls awaitCache() to essentially freeze until FOV calculations are over. 1256 */ 1257 public void cacheAll() 1258 { 1259 if(qualityThread != null || qualityComplete) 1260 return; 1261 qualityThread = new Thread(new QualityUnit()); 1262 qualityThread.start(); 1263 } 1264 1265 /** 1266 * If FOV calculations from cacheAll() are being done on another thread, calling this method will make 1267 * the current thread wait for the FOV calculations' thread to finish, "freezing" the current thread until it does. 1268 * This ensures the cache will be complete with the additional quality improvements such as distant lights after 1269 * this method returns true, and if this method returns false, then something has gone wrong. 1270 * @return true if cacheAll() has successfully completed, false otherwise. 1271 */ 1272 public boolean awaitCache() 1273 { 1274 if(qualityThread == null && !qualityComplete) 1275 cacheAll(); 1276 if(qualityComplete) return true; 1277 try { 1278 qualityThread.join(); 1279 } catch (InterruptedException e) { 1280 return false; 1281 } 1282 return qualityComplete; 1283 } 1284 1285 /** 1286 * Runs FOV calculations for any cells that were changed as a result of newMap being different from the map passed 1287 * to the FOVCache constructor. It runs these on another thread, without interrupting this one. Before using the 1288 * cache, you should call awaitRefresh() to ensure this method has finished on its own thread, but be aware that 1289 * this will cause the thread that calls awaitRefresh() to essentially freeze until FOV calculations are over. 1290 */ 1291 public void refreshCache(char[][] newMap) 1292 { 1293 performanceThread = new Thread(new RefreshUnit(newMap)); 1294 performanceThread.start(); 1295 } 1296 1297 /** 1298 * If FOV calculations from refreshCache() are being done on another thread, calling this method will make 1299 * the current thread wait for the FOV calculations' thread to finish, "freezing" the current thread until it does. 1300 * This ensures the cache will be complete with the updates from things like opening a door after 1301 * this method returns true, and if this method returns false, then something has gone wrong. 1302 * @return true if refreshCache() has successfully completed, false otherwise. 1303 */ 1304 public boolean awaitRefresh(char[][] newMap) 1305 { 1306 if(!performanceThread.isAlive() && !refreshComplete) 1307 refreshCache(newMap); 1308 if(refreshComplete) return true; 1309 try { 1310 performanceThread.join(); 1311 } catch (InterruptedException e) { 1312 return false; 1313 } 1314 if(refreshComplete) 1315 { 1316 refreshComplete = false; 1317 return true; 1318 } 1319 else return false; 1320 } 1321 1322 1323 @SuppressWarnings("unused") 1324 private byte heuristic(Direction target) { 1325 switch (radiusKind) { 1326 case CIRCLE: 1327 case SPHERE: 1328 switch (target) { 1329 case DOWN_LEFT: 1330 case DOWN_RIGHT: 1331 case UP_LEFT: 1332 case UP_RIGHT: 1333 return 3; 1334 default: 1335 return 2; 1336 } 1337 default: 1338 return 2; 1339 } 1340 } 1341 private short distance(int xPos, int yPos) { 1342 int x = Math.abs(xPos), y = Math.abs(yPos); 1343 switch (radiusKind) { 1344 case CIRCLE: 1345 case SPHERE: 1346 { 1347 if(x == y) 1348 return (short)(3 * x); 1349 else if(x < y) 1350 return (short)(3 * x + 2 * (y - x)); 1351 else 1352 return (short)(3 * y + 2 * (x - y)); 1353 } 1354 case DIAMOND: 1355 case OCTAHEDRON: 1356 return (short)(2 * (x + y)); 1357 default: 1358 return (short)(2 * Math.max(x, y)); 1359 } 1360 } 1361 1362 /** 1363 * Calculates the Field Of View for the provided map from the given x, y 1364 * coordinates. Returns a light map where the values are either 1.0 or 0.0. 1365 * Takes a double[][] resistance map that will be disregarded. 1366 * <br> 1367 * The starting point for the calculation is considered to be at the center 1368 * of the origin cell. Radius determinations are based on the radiusKind given 1369 * in construction. The light will be treated as having radius 62, regardless 1370 * of the maxRadius passed to the constructor; this should in most cases be 1371 * suitable when limitless light is desired. 1372 * If the cache has not been fully constructed, this will compute a new FOV 1373 * map using Shadow FOV instead of using the cache, and the result will not 1374 * be cached. 1375 * 1376 * @param resistanceMap the grid of cells to calculate on 1377 * @param startx the horizontal component of the starting location 1378 * @param starty the vertical component of the starting location 1379 * @return the computed light grid 1380 */ 1381 @Override 1382 public double[][] calculateFOV(double[][] resistanceMap, int startx, int starty) { 1383 if(qualityComplete || complete) 1384 return unpackDouble(losCache[startx + starty * width], width, height); 1385 else 1386 return fov.calculateFOV(resMap, startx, starty, maxRadius, radiusKind); 1387 } 1388 1389 /* 1390 * Calculates the Field Of View for the provided map from the given x, y 1391 * coordinates. Returns a light map where the values are either 1.0 or 0.0. 1392 * Takes a double radius to extend out to (rounded to the nearest int) and 1393 * a double[][] resistance map that will be disregarded. 1394 * <br> 1395 * The starting point for the calculation is considered to be at the center 1396 * of the origin cell. Radius determinations are based on the radiusKind given 1397 * in construction. The light will be treated as having the given radius, but 1398 * if that is higher than the maximum possible radius stored by this FOVCache, 1399 * it will compute a new FOV map using Shadow FOV instead of using the cache. 1400 * If the cache has not been fully constructed, this will compute a new FOV 1401 * map using Shadow FOV instead of using the cache, and the result will not 1402 * be cached. 1403 * 1404 * @param resistanceMap the grid of cells to calculate on 1405 * @param startx the horizontal component of the starting location 1406 * @param starty the vertical component of the starting location 1407 * @param radius the distance the light will extend to 1408 * @return the computed light grid 1409 */ 1410 /* 1411 @Override 1412 public double[][] calculateFOV(double[][] resistanceMap, int startx, int starty, double radius) { 1413 if((qualityComplete || complete) && radius >= 0 && radius <= maxRadius) 1414 return unpackDouble(cache[startx + starty * width][maxRadius - (int) Math.round(radius)], width, height); 1415 else 1416 return fov.calculateFOV(resMap, startx, starty, radius, radiusKind); 1417 }*/ 1418 1419 1420 /* 1421 * Calculates the Field Of View for the provided map from the given x, y 1422 * coordinates. Returns a light map where the values are either 1.0 or 0.0. 1423 * Takes a double radius to extend out to (rounded to the nearest int), a 1424 * Radius enum that should match the Radius this FOVCache was constructed 1425 * with, and a double[][] resistance map that will be disregarded. 1426 * <br> 1427 * The starting point for the calculation is considered to be at the center 1428 * of the origin cell. Radius determinations are based on the radiusTechnique 1429 * passed to this method, but will only use the cache if the Radius given is 1430 * the same kind as the one given in construction. The light will be treated 1431 * as having the given radius, but if that is higher than the maximum possible 1432 * radius stored by this FOVCache, it will compute a new FOV map using Shadow 1433 * FOV instead of using the cache. 1434 * If the cache has not been fully constructed, this will compute a new FOV 1435 * map using Shadow FOV instead of using the cache, and the result will not 1436 * be cached. 1437 * 1438 * @param resistanceMap the grid of cells to calculate on 1439 * @param startX the horizontal component of the starting location 1440 * @param startY the vertical component of the starting location 1441 * @param radius the distance the light will extend to 1442 * @param radiusTechnique provides a means to calculate the radius as desired 1443 * @return the computed light grid 1444 */ 1445 /* 1446 @Override 1447 public double[][] calculateFOV(double[][] resistanceMap, int startX, int startY, double radius, 1448 Radius radiusTechnique) { 1449 if((qualityComplete || complete) && radius >= 0 && radius <= maxRadius && 1450 radiusKind.equals2D(radiusTechnique)) 1451 return unpackDouble(cache[startX + startY * width][maxRadius - (int) Math.round(radius)], width, height); 1452 else 1453 return fov.calculateFOV(resMap, startX, startY, radius, radiusTechnique); 1454 }*/ 1455 1456 /* 1457 * Calculates the conical Field Of View for the provided map from the given 1458 * x, y coordinates. Returns a light map where the values are either 1.0 or 1459 * 0.0. Takes a double radius to extend out to (rounded to the nearest int), 1460 * a Radius enum that should match the Radius this FOVCache was constructed 1461 * with, a double[][] resistance map that will be disregarded, an angle to 1462 * center the conical FOV on (in degrees), and the total span in degrees 1463 * for the FOV to cover. 1464 * <br> 1465 * The starting point for the calculation is considered to be at the center 1466 * of the origin cell. Radius determinations are based on the radiusTechnique 1467 * passed to this method, but will only use the cache if the Radius given is 1468 * the same kind as the one given in construction. The light will be treated 1469 * as having the given radius, but if that is higher than the maximum possible 1470 * radius stored by this FOVCache, it will compute a new FOV map using Shadow 1471 * FOV instead of using the cache. A conical section of FOV is lit by this 1472 * method if span is greater than 0. 1473 * 1474 * If the cache has not been fully constructed, this will compute a new FOV 1475 * map using Shadow FOV instead of using the cache, and the result will not 1476 * be cached. 1477 * 1478 * @param resistanceMap the grid of cells to calculate on 1479 * @param startX the horizontal component of the starting location 1480 * @param startY the vertical component of the starting location 1481 * @param radius the distance the light will extend to 1482 * @param radiusTechnique provides a means to calculate the radius as desired 1483 * @param angle the angle in degrees that will be the center of the FOV cone, 0 points right 1484 * @param span the angle in degrees that measures the full arc contained in the FOV cone 1485 * @return the computed light grid 1486 */ 1487/* @Override 1488 public double[][] calculateFOV(double[][] resistanceMap, int startX, int startY, double radius, 1489 Radius radiusTechnique, double angle, double span) { 1490 if((qualityComplete || complete) && radius >= 0 && radius <= maxRadius && 1491 radiusKind.equals2D(radiusTechnique)) 1492 return unpackDoubleConical(cache[startX + startY * width][maxRadius - (int) Math.round(radius)], width, height, 1493 startX, startY, angle, span); 1494 else 1495 return fov.calculateFOV(resMap, startX, startY, radius, radiusTechnique, angle, span); 1496 } 1497*/ 1498 /** 1499 * Calculates the Field Of View for the provided map from the given x, y 1500 * coordinates. Returns a light map where the values range from 1.0 (center 1501 * of the FOV) to 0.0 (not seen), with values between those two extremes 1502 * for the rest of the seen area. 1503 * Takes a double radius to extend out to (rounded to the nearest int), and 1504 * a double[][] resistance map that will be disregarded. 1505 * <br> 1506 * The starting point for the calculation is considered to be at the center 1507 * of the origin cell. Radius determinations are based on the radiusKind given 1508 * in construction. The light will be treated as having the given radius, but 1509 * if that is higher than the maximum possible radius stored by this FOVCache, 1510 * it will compute a new FOV map using Ripple FOV instead of using the cache. 1511 * If the cache has not been fully constructed, this will compute a new FOV 1512 * map using Ripple FOV instead of using the cache, and the result will not 1513 * be cached. 1514 * 1515 * @param resistanceMap the grid of cells to calculate on 1516 * @param startx the horizontal component of the starting location 1517 * @param starty the vertical component of the starting location 1518 * @param radius the distance the light will extend to 1519 * @return the computed light grid 1520 */ 1521 @Override 1522 public double[][] calculateFOV(double[][] resistanceMap, int startx, int starty, double radius) { 1523 if((qualityComplete || complete) && radius > 0 && radius <= maxRadius) 1524 return unpackMultiDoublePartial(cache[startx + starty * width], width, height, 1525 levels[(int) Math.round(radius)], (int) Math.round(radius)); 1526 else 1527 return gradedFOV.calculateFOV(resMap, startx, starty, radius, radiusKind); 1528 } 1529 1530 1531 /** 1532 * Calculates the Field Of View for the provided map from the given x, y 1533 * coordinates. Returns a light map where the values range from 1.0 (center 1534 * of the FOV) to 0.0 (not seen), with values between those two extremes 1535 * for the rest of the seen area. 1536 * Takes a double radius to extend out to (rounded to the nearest int), a 1537 * Radius enum that should match the Radius this FOVCache was constructed 1538 * with, and a double[][] resistance map that will be disregarded. 1539 * <br> 1540 * The starting point for the calculation is considered to be at the center 1541 * of the origin cell. Radius determinations are based on the radiusTechnique 1542 * passed to this method, but will only use the cache if the Radius given is 1543 * the same kind as the one given in construction. The light will be treated 1544 * as having the given radius, but if that is higher than the maximum possible 1545 * radius stored by this FOVCache, it will compute a new FOV map using Ripple 1546 * FOV instead of using the cache. 1547 * If the cache has not been fully constructed, this will compute a new FOV 1548 * map using Ripple FOV instead of using the cache, and the result will not 1549 * be cached. 1550 * 1551 * @param resistanceMap the grid of cells to calculate on 1552 * @param startX the horizontal component of the starting location 1553 * @param startY the vertical component of the starting location 1554 * @param radius the distance the light will extend to 1555 * @param radiusTechnique provides a means to calculate the radius as desired 1556 * @return the computed light grid 1557 */ 1558 @Override 1559 public double[][] calculateFOV(double[][] resistanceMap, int startX, int startY, double radius, 1560 Radius radiusTechnique) { 1561 if((qualityComplete || complete) && radius > 0 && radius <= maxRadius && 1562 radiusKind.equals2D(radiusTechnique)) 1563 return unpackMultiDoublePartial(cache[startX + startY * width], width, height, 1564 levels[(int) Math.round(radius)], (int) Math.round(radius)); 1565 else 1566 return gradedFOV.calculateFOV(resMap, startX, startY, radius, radiusTechnique); 1567 } 1568 1569 /** 1570 * Calculates the conical Field Of View for the provided map from the given 1571 * x, y coordinates. Returns a light map where the values range from 1.0 1572 * (center of the FOV) to 0.0 (not seen), with values between those two 1573 * extremes for the rest of the seen area. 1574 * Takes a double radius to extend out to (rounded to the nearest int), a 1575 * Radius enum that should match the Radius this FOVCache was constructed 1576 * with, a double[][] resistance map that will be disregarded, an angle to 1577 * center the conical FOV on (in degrees), and the total span in degrees 1578 * for the FOV to cover. 1579 * <br> 1580 * The starting point for the calculation is considered to be at the center 1581 * of the origin cell. Radius determinations are based on the radiusTechnique 1582 * passed to this method, but will only use the cache if the Radius given is 1583 * the same kind as the one given in construction. The light will be treated 1584 * as having the given radius, but if that is higher than the maximum possible 1585 * radius stored by this FOVCache, it will compute a new FOV map using Ripple 1586 * FOV instead of using the cache. A conical section of FOV is lit by this 1587 * method if span is greater than 0. 1588 * 1589 * If the cache has not been fully constructed, this will compute a new FOV 1590 * map using Ripple FOV instead of using the cache, and the result will not 1591 * be cached. 1592 * 1593 * @param resistanceMap the grid of cells to calculate on 1594 * @param startX the horizontal component of the starting location 1595 * @param startY the vertical component of the starting location 1596 * @param radius the distance the light will extend to 1597 * @param radiusTechnique provides a means to calculate the radius as desired 1598 * @param angle the angle in degrees that will be the center of the FOV cone, 0 points right 1599 * @param span the angle in degrees that measures the full arc contained in the FOV cone 1600 * @return the computed light grid 1601 */ 1602 @Override 1603 public double[][] calculateFOV(double[][] resistanceMap, int startX, int startY, double radius, 1604 Radius radiusTechnique, double angle, double span) { 1605 if((qualityComplete || complete) && radius > 0 && radius <= maxRadius && 1606 radiusKind.equals2D(radiusTechnique)) 1607 return unpackMultiDoublePartialConical(cache[startX + startY * width], width, height, 1608 levels[(int) Math.round(radius)], (int) Math.round(radius), startX, startY, angle, span); 1609 else 1610 return gradedFOV.calculateFOV(resMap, startX, startY, radius, radiusTechnique, angle, span); 1611 } 1612 1613 /** 1614 * Calculates an array of Coord positions that can be seen along the line from the given start point and end point. 1615 * Does not order the array. Uses the pre-computed LOS cache to determine obstacles, and tends to draw a 1616 * thicker line than Bresenham lines will. This uses the same radiusKind the FOVCache was created with, but the line 1617 * this draws doesn't necessarily travel along valid directions for creatures (in particular, Radius.DIAMOND should 1618 * only allow orthogonal movement, but if you request a 45-degree line, the LOS will have Coords on a perfect 1619 * diagonal, though they won't travel through walls that occupy a thin perpendicular diagonal). 1620 * @param startX the x position of the starting point; must be within bounds of the map 1621 * @param startY the y position of the starting point; must be within bounds of the map 1622 * @param endX the x position of the endpoint; does not need to be within bounds (will stop LOS at the edge) 1623 * @param endY the y position of the endpoint; does not need to be within bounds (will stop LOS at the edge) 1624 * @return a Coord[], unordered, that can be seen along the line of sight; limited to maxLOSRadius, default 62 1625 */ 1626 public Coord[] calculateLOS(int startX, int startY, int endX, int endY) 1627 { 1628 if(!complete || startX < 0 || startX >= width || startY < 0 || startY >= height) 1629 return new Coord[0]; 1630 int max = distance(endX - startX, endY - startY); 1631 ArrayList<Coord> path = new ArrayList<>(max / 2 + 1); 1632 short[] losCached = losCache[startX + startY * width]; 1633 if(losCached.length == 0) 1634 return new Coord[0]; 1635 boolean on = false; 1636 int idx = 0, xt, yt; 1637 short x =0, y = 0; 1638 path.add(Coord.get(startX, startY)); 1639 if(startX == endX && startY == endY) 1640 return path.toArray(new Coord[1]); 1641 1642 double angle = Math.atan2(endY - startY, endX - startX); 1643 double x2 = Math.sin(angle) * 0.5, y2 = Math.cos(angle) * 0.5; 1644 boolean[][] mask = new boolean[width][height]; 1645 for (int d = 2; d <= max; d++) { 1646 xt = startX + (int)(x2 * d + 0.5); 1647 yt = startY + (int)(y2 * d + 0.5); 1648 if(xt < 0 || xt >= width || yt < 0 || yt >= height) 1649 break; 1650 mask[xt][yt] = true; 1651 } 1652 1653 for(int p = 0; p < losCached.length; p++, on = !on) { 1654 if (on) { 1655 for (int toSkip = idx +(losCached[p] & 0xffff); idx < toSkip && idx < limit; idx++) { 1656 x = hilbertX[idx]; 1657 y = hilbertY[idx]; 1658 // this should never be possible, removing tentatively 1659 //if(x >= width || y >= height) 1660 // continue; 1661 if(mask[x][y]) 1662 path.add(Coord.get(x, y)); 1663 } 1664 } else { 1665 idx += losCached[p] & 0xffff; 1666 } 1667 } 1668 return path.toArray(new Coord[path.size()]); 1669 } 1670 1671 /** 1672 * Calculates an array of Coord positions that can be seen along the line from the given start point and end point. 1673 * Sorts the array, starting from the closest Coord to start and ending close to end. Uses the pre-computed LOS 1674 * cache to determine obstacles, and tends to draw a thicker line than Bresenham lines will. This uses the same 1675 * radiusKind the FOVCache was created with, but the line this draws doesn't necessarily travel along valid 1676 * directions for creatures (in particular, Radius.DIAMOND should only allow orthogonal movement, but if you request 1677 * a 45-degree line, the LOS will have Coords on a perfect diagonal, though they won't travel through walls that 1678 * occupy a thin perpendicular diagonal). 1679 * @param startX the x position of the starting point; must be within bounds of the map 1680 * @param startY the y position of the starting point; must be within bounds of the map 1681 * @param endX the x position of the endpoint; does not need to be within bounds (will stop LOS at the edge) 1682 * @param endY the y position of the endpoint; does not need to be within bounds (will stop LOS at the edge) 1683 * @return a Coord[], sorted, that can be seen along the line of sight; limited to max LOS range, 62 1684 */ 1685 public Coord[] sortedLOS(int startX, int startY, int endX, int endY) { 1686 Coord[] path = calculateLOS(startX, startY, endX, endY); 1687 SortedMap<Double, Coord> sorted = new TreeMap<>(); 1688 double modifier = 0.0001; 1689 Coord c; 1690 for (int i = 0; i < path.length; i++, modifier += 0.0001) { 1691 c = path[i]; 1692 sorted.put(distance(c.x, c.y) + modifier, c); 1693 } 1694 return sorted.values().toArray(new Coord[sorted.size()]); 1695 } 1696 /** 1697 * Given a path as a List of Coords (such as one produced by DijkstraMap.getPath()), this method will look up the 1698 * FOV for the given fovRange at each Coord, and returns an array of packed FOV maps where each map is the union 1699 * of the FOV centered on a Coord in path with all FOVs centered on previous Coords in path. The purpose of this is 1700 * mainly to have an efficient way to show the progressively expanding seen area of a character who moves multiple 1701 * tiles. It may be desirable to add the entire path's cumulative FOV (stored in the last element of the returned 1702 * short[][]) to the history of what a character has seen, removing the path's FOV from the currently visible cells 1703 * either after the character has finished their action, or even immediately after moving if, for instance, the 1704 * movement was part of a rapid leap that wouldn't let the character spot details while moving (but the general 1705 * layout provided by the seen-cell history could suffice). This method never unpacks any packed data. 1706 * @param path a List of Coords that will be added, in order, to multiple packed FOVs for the path so far 1707 * @param fovRange the radius the creature or thing taking the path can see (or possibly light up). 1708 * @return a packed short[][], each short[] encoding the FOV around an additional Coord merged with those before 1709 */ 1710 public short[][] pathFOVPacked(List<Coord> path, int fovRange) 1711 { 1712 if(!complete) 1713 throw new IllegalStateException("Cache is not yet constructed"); 1714 if(fovRange > maxRadius) 1715 throw new UnsupportedOperationException("Given fovRange parameter exceeds maximum cached range"); 1716 short[][] fovSteps = new short[path.size()][]; 1717 int idx = 0; 1718 for (Coord c : path) 1719 { 1720 if(c.x < 0 || c.y < 0 || c.x >= width || c.y >= height) 1721 throw new ArrayIndexOutOfBoundsException("Along given path, encountered an invalid Coord: " 1722 + c); 1723 if(idx == 0) 1724 { 1725 fovSteps[idx] = cache[c.x + c.y * width][maxRadius - fovRange]; 1726 } 1727 else 1728 { 1729 fovSteps[idx] = unionPacked(fovSteps[idx - 1], cache[c.x + c.y * width][maxRadius - fovRange]); 1730 } 1731 idx++; 1732 } 1733 return fovSteps; 1734 } 1735 1736 /** 1737 * Given a path as a List of Coords (such as one produced by DijkstraMap.getPath()), this method will look up the 1738 * FOV for the given fovRange at each Coord, and returns an array of full FOV maps where each map is the union 1739 * of the FOV centered on a Coord in path with all FOVs centered on previous Coords in path. The purpose of this is 1740 * mainly to have a way to show the progressively expanding seen area of a character who moves multiple 1741 * tiles. It may be desirable to add the entire path's cumulative FOV (stored in the last element of the returned 1742 * double[][][]) to the history of what a character has seen, removing the path's FOV from the currently visible 1743 * cells either after the character has finished their action, or even immediately after moving if, for instance, 1744 * the movement was part of a rapid leap that wouldn't let the character spot details while moving (but the general 1745 * layout provided by the seen-cell history could suffice). This method computes the union of the FOV without 1746 * unpacking, but then unpacks each step along the path into a double[][] of 1.0 and 0.0 values. 1747 * @param path a List of Coords that will be added, in order, to multiple FOVs for the path so far 1748 * @param fovRange the radius the creature or thing taking the path can see (or possibly light up). 1749 * @return a packed double[][][]; each double[][] is the FOV around an additional Coord merged with those before 1750 */ 1751 public double[][][] pathFOV(List<Coord> path, int fovRange) 1752 { 1753 short[][] compressed = pathFOVPacked(path, fovRange); 1754 double[][][] fovSteps = new double[compressed.length][][]; 1755 for (int i = 0; i < compressed.length; i++) { 1756 fovSteps[i] = unpackDouble(compressed[i], width, height); 1757 } 1758 return fovSteps; 1759 } 1760 1761 /** 1762 * In games that have multiple characters who should share one FOV map, this method should provide optimal 1763 * performance when collecting several cached FOV maps into one packed map. It takes a Map of Coord keys to Integer 1764 * values, and since it does not modify its parameter, nor does it need a particular iteration order, it doesn't 1765 * perform a defensive copy of the team parameter. Each Coord key should correspond to the position of a character, 1766 * and each Integer value should be the FOV range of that character. This returns a short[] as a packed FOV map for 1767 * all characters in team as a collective. 1768 * @param team a Map of Coord keys for characters' positions to Integer values for the FOV range of each character 1769 * @return a packed FOV map that can be used with other packed data using CoordPacker. 1770 */ 1771 public short[] teamFOVPacked(Map<Coord, Integer> team) 1772 { 1773 if(!complete) 1774 throw new IllegalStateException("Cache is not yet constructed"); 1775 short[] packing = new short[0]; 1776 int idx = 0; 1777 Coord c; 1778 int range; 1779 for (Map.Entry<Coord, Integer> kv : team.entrySet()) 1780 { 1781 c = kv.getKey(); 1782 range = kv.getValue(); 1783 if(c.x < 0 || c.y < 0 || c.x >= width || c.y >= height) 1784 throw new ArrayIndexOutOfBoundsException("Among team, encountered an invalid Coord: " 1785 + c); 1786 if(idx == 0) 1787 { 1788 packing = cache[c.x + c.y * width][maxRadius - range]; 1789 } 1790 else 1791 { 1792 packing = unionPacked(packing, cache[c.x + c.y * width][maxRadius - range]); 1793 } 1794 idx++; 1795 } 1796 return packing; 1797 } 1798 1799 /** 1800 * In games that have multiple characters who should share one FOV map, this method should provide optimal 1801 * performance when collecting several cached FOV maps into one full map. It takes a Map of Coord keys to Integer 1802 * values, and since it does not modify its parameter, nor does it need a particular iteration order, it doesn't 1803 * perform a defensive copy of the team parameter. Each Coord key should correspond to the position of a character, 1804 * and each Integer value should be the FOV range of that character. This returns a double[][] as a full FOV map, 1805 * with values of either 1.0 or 0.0, for all characters in team as a collective. 1806 * @param team a Map of Coord keys for characters' positions to Integer values for the FOV range of each character 1807 * @return a double[][] FOV map with 1.0 and 0.0 as values, combining all characters' FOV maps. 1808 */ 1809 public double[][] teamFOV(Map<Coord, Integer> team) 1810 { 1811 return unpackDouble(teamFOVPacked(team), width, height); 1812 } 1813 1814 /** 1815 * When you have some packed on/off data and want to make sure it does not include walls, you can use this. It does 1816 * not need to unpack the given packed short[] to get the subset of it without walls. Of course, this needs the 1817 * FOVCache to be 1818 * @param packed a short[] produced by some CoordPacker method or obtained by getLOSEntry() or getCacheEntry(). 1819 * @return another packed array containing only the non-wall "on" cells in packed 1820 */ 1821 public short[] removeWalls(short[] packed) 1822 { 1823 return differencePacked(packed, wallMap); 1824 } 1825 1826 public int getMaxRadius() { 1827 return maxRadius; 1828 } 1829 1830 public Radius getRadiusKind() { 1831 return radiusKind; 1832 } 1833 1834 public int getWidth() { 1835 return width; 1836 } 1837 1838 public int getHeight() { 1839 return height; 1840 } 1841 1842 @GwtIncompatible 1843 protected class PerformanceUnit implements Runnable 1844 { 1845 1846 /** 1847 * When an object implementing interface <code>Runnable</code> is used 1848 * to create a thread, starting the thread causes the object's 1849 * <code>run</code> method to be called in that separately executing 1850 * thread. 1851 * <p> 1852 * The general contract of the method <code>run</code> is that it may 1853 * take any action whatsoever. 1854 * 1855 * @see Thread#run() 1856 */ 1857 @Override 1858 public void run() { 1859 ArrayList<ArrayList<LOSUnit>> losUnits = new ArrayList<>(24); 1860 ArrayList<ArrayList<FOVUnit>> fovUnits = new ArrayList<>(24); 1861 for (int p = 0; p < 24; p++) { 1862 losUnits.add(new ArrayList<LOSUnit>(mapLimit / 20)); 1863 fovUnits.add(new ArrayList<FOVUnit>(mapLimit / 20)); 1864 } 1865 for (int i = 0, p = 0; i < mapLimit; i++, p = (p+1) % 24) { 1866 losUnits.get(p).add(new LOSUnit(i)); 1867 fovUnits.get(p).add(new FOVUnit(i)); 1868 } 1869 //long totalTime = System.currentTimeMillis(), threadTime = 0L; 1870 for (int p = 23; p >= 0; p--) { 1871 try { 1872 final List<Future<Long>> invoke = executor.invokeAll(losUnits.get(p)); 1873 for (Future<Long> future : invoke) { 1874 future.get(); 1875 //long t = future.get(); 1876 //threadTime += t; 1877 //System.out.println(t); 1878 } 1879 } catch (InterruptedException | ExecutionException e) { 1880 e.printStackTrace(); 1881 } 1882 losUnits.remove(p); 1883 System.gc(); 1884 } 1885 for (int p = 23; p >= 0; p--) { 1886 try { 1887 final List<Future<Long>> invoke = executor.invokeAll(fovUnits.get(p)); 1888 for (Future<Long> future : invoke) { 1889 future.get(); 1890 //long t = future.get(); 1891 //threadTime += t; 1892 //System.out.println(t); 1893 } 1894 } catch (InterruptedException | ExecutionException e) { 1895 e.printStackTrace(); 1896 } 1897 fovUnits.remove(p); 1898 System.gc(); 1899 } 1900 //totalTime = System.currentTimeMillis() - totalTime; 1901 //System.out.println("Total real time elapsed: " + totalTime); 1902 //System.out.println("Total CPU time elapsed, on " + NUM_THREADS + " threads: " + threadTime); 1903 /* 1904 long totalRAM = 0; 1905 for (int c = 0; c < width * height; c++) { 1906 long ctr = 0, losCtr = 0; 1907 for (int i = 0; i < cache[c].length; i++) { 1908 ctr += (((2 * cache[c][i].length + 12 - 1) / 8) + 1) * 8L; 1909 } 1910 totalRAM += (((ctr + 12 - 1) / 8) + 1) * 8; 1911 1912 losCtr = (((2 * losCache[c].length + 12 - 1) / 8) + 1) * 8L; 1913 totalRAM += (((losCtr + 12 - 1) / 8) + 1) * 8; 1914 } 1915 System.out.println("Total memory used by cache: " + totalRAM); 1916 */ 1917 complete = true; 1918 1919 } 1920 } 1921 1922 @GwtIncompatible 1923 protected class QualityUnit implements Runnable 1924 { 1925 1926 /** 1927 * When an object implementing interface <code>Runnable</code> is used 1928 * to create a thread, starting the thread causes the object's 1929 * <code>run</code> method to be called in that separately executing 1930 * thread. 1931 * <p> 1932 * The general contract of the method <code>run</code> is that it may 1933 * take any action whatsoever. 1934 * 1935 * @see Thread#run() 1936 */ 1937 @Override 1938 public void run() { 1939 //long totalTime = System.currentTimeMillis(), threadTime = 0L; 1940 if(!complete) { 1941 cacheAllPerformance(); 1942 try { 1943 performanceThread.join(); 1944 } catch (InterruptedException e) { 1945 return; 1946 } 1947 } 1948 1949 ArrayList<ArrayList<SymmetryUnit>> symUnits = new ArrayList<>(4); 1950 for (int p = 0; p < 4; p++) { 1951 symUnits.add(new ArrayList<SymmetryUnit>(mapLimit / 3)); 1952 } 1953 for (int i = 0, p = 0; i < mapLimit; i++, p = (p+1) % 4) { 1954 symUnits.get(p).add(new SymmetryUnit(i)); 1955 } 1956 1957 for (int p = 3; p >= 0; p--) { 1958 try { 1959 final List<Future<Long>> invoke = executor.invokeAll(symUnits.get(p)); 1960 for (Future<Long> future : invoke) { 1961 //threadTime += 1962 future.get(); 1963 //System.out.println(t); 1964 } 1965 } catch (InterruptedException | ExecutionException e) { 1966 e.printStackTrace(); 1967 } 1968 symUnits.remove(p); 1969 System.gc(); 1970 } 1971 cache = tmpCache; 1972 qualityComplete = true; 1973 /* 1974 totalTime = System.currentTimeMillis() - totalTime; 1975 System.out.println("Total real time elapsed : " + totalTime); 1976 System.out.println("Total CPU time elapsed, on " + NUM_THREADS + " threads: " + threadTime); 1977 1978 long totalRAM = 0; 1979 for (int c = 0; c < width * height; c++) { 1980 long ctr = 0, losCtr = 0; 1981 for (int i = 0; i < cache[c].length; i++) { 1982 ctr += (((2 * cache[c][i].length + 12 - 1) / 8) + 1) * 8L; 1983 } 1984 totalRAM += (((ctr + 12 - 1) / 8) + 1) * 8; 1985 1986 losCtr = (((2 * losCache[c].length + 12 - 1) / 8) + 1) * 8L; 1987 totalRAM += (((losCtr + 12 - 1) / 8) + 1) * 8; 1988 } 1989 System.out.println("Total memory used by cache: " + totalRAM); 1990 1991 System.out.println("FOV Map stored for every cell, booleans or bytes, "+width+"x"+height+": " + 1992 ((((((((((((height + 12 - 1) / 8) + 1) * 8L * width + 12 - 1) / 8) + 1) * 8L 1993 * height + 12 - 1) / 8) + 1) * 8L * width + 12 - 1) / 8) + 1) * 8L); 1994 */ 1995 } 1996 } 1997 1998 @GwtIncompatible 1999 protected class RefreshUnit implements Runnable 2000 { 2001 protected double[][] res; 2002 protected RefreshUnit(char[][] newMap) 2003 { 2004 res = DungeonUtility.generateResistances(newMap); 2005 2006 } 2007 2008 /** 2009 * When an object implementing interface <code>Runnable</code> is used 2010 * to create a thread, starting the thread causes the object's 2011 * <code>run</code> method to be called in that separately executing 2012 * thread. 2013 * <p> 2014 * The general contract of the method <code>run</code> is that it may 2015 * take any action whatsoever. 2016 * 2017 * @see Thread#run() 2018 */ 2019 @Override 2020 public void run() { 2021 System.arraycopy(cache, 0, tmpCache, 0, tmpCache.length); 2022 short[] needsChange = new short[0]; 2023 for (int i = 0; i < width; i++) { 2024 for (int j = 0; j < height; j++) { 2025 if(resMap[i][j] != res[i][j]) 2026 { 2027 needsChange = unionPacked(needsChange, losCache[i + j * width]); 2028 } 2029 } 2030 } 2031 needsChange = differencePacked(needsChange, wallMap); 2032 resMap = res; 2033 Coord[] changingCoords = allPacked(needsChange); 2034 List<LOSUnit> losUnits = new ArrayList<>(changingCoords.length); 2035 List<FOVUnit> fovUnits = new ArrayList<>(changingCoords.length); 2036 List<SymmetryUnit> symUnits = new ArrayList<>(changingCoords.length); 2037 2038 for (int i = 0, idx; i < changingCoords.length; i++) 2039 { 2040 idx = changingCoords[i].x + changingCoords[i].y * width; 2041 losUnits.add(new LOSUnit(idx)); 2042 fovUnits.add(new FOVUnit(idx)); 2043 symUnits.add(new SymmetryUnit(idx)); 2044 } 2045 2046 try { 2047 final List<Future<Long>> invoke = executor.invokeAll(losUnits); 2048 for (Future<Long> future : invoke) { 2049 //threadTime += 2050 future.get(); 2051 //System.out.println(t); 2052 } 2053 } catch (InterruptedException | ExecutionException e) { 2054 e.printStackTrace(); 2055 } 2056 try { 2057 final List<Future<Long>> invoke = executor.invokeAll(fovUnits); 2058 for (Future<Long> future : invoke) { 2059 //threadTime += 2060 future.get(); 2061 //System.out.println(t); 2062 } 2063 } catch (InterruptedException | ExecutionException e) { 2064 e.printStackTrace(); 2065 } 2066 try { 2067 final List<Future<Long>> invoke = executor.invokeAll(symUnits); 2068 for (Future<Long> future : invoke) { 2069 //threadTime += 2070 future.get(); 2071 //System.out.println(t); 2072 } 2073 } catch (InterruptedException | ExecutionException e) { 2074 e.printStackTrace(); 2075 } 2076 cache = tmpCache; 2077 refreshComplete = true; 2078 } 2079 } 2080 2081 @GwtIncompatible 2082 protected class FOVUnit implements Callable<Long> 2083 { 2084 protected int index; 2085 public FOVUnit(int index) 2086 { 2087 this.index = index; 2088 } 2089 2090 /** 2091 * Computes a result, or throws an exception if unable to do so. 2092 * 2093 * @return computed result 2094 * @throws Exception if unable to compute a result 2095 */ 2096 @Override 2097 public Long call() throws Exception { 2098 return storeCellFOV(index); 2099 } 2100 } 2101 2102 @GwtIncompatible 2103 protected class LOSUnit implements Callable<Long> 2104 { 2105 protected int index; 2106 public LOSUnit(int index) 2107 { 2108 this.index = index; 2109 } 2110 2111 /** 2112 * Computes a result, or throws an exception if unable to do so. 2113 * 2114 * @return computed result 2115 * @throws Exception if unable to compute a result 2116 */ 2117 @Override 2118 public Long call() throws Exception { 2119 return storeCellLOS(index); 2120 } 2121 } 2122 2123 @GwtIncompatible 2124 protected class SymmetryUnit implements Callable<Long> 2125 { 2126 protected int index; 2127 public SymmetryUnit(int index) 2128 { 2129 this.index = index; 2130 } 2131 2132 /** 2133 * Computes a result, or throws an exception if unable to do so. 2134 * 2135 * @return computed result 2136 * @throws Exception if unable to compute a result 2137 */ 2138 @Override 2139 public Long call() throws Exception { 2140 return storeCellSymmetry(index); 2141 } 2142 } 2143}