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}