001package squidpony.squidgrid;
002
003import squidpony.GwtCompatibility;
004import squidpony.squidmath.Coord;
005
006import java.io.Serializable;
007import java.util.*;
008
009/**
010 * This class provides methods for calculating Field of View in grids. Field of
011 * View (FOV) algorithms determine how much area surrounding a point can be
012 * seen. They return a two dimensional array of doubles, representing the amount
013 * of view (typically sight, but perhaps sound, smell, etc.) which the origin
014 * has of each cell.
015 * <br>
016 * The input resistanceMap is considered the percent of opacity. This resistance
017 * is on top of the resistance applied from the light spreading out. You can
018 * obtain a resistance map easily with the DungeonUtility.generateResistances()
019 * method, which uses defaults for common chars used in SquidLib, but you may
020 * also want to create a resistance map manually if a given char means something
021 * very different in your game. This is easy enough to do by looping over all the
022 * x,y positions in your char[][] map and running a switch statement on each char,
023 * assigning a double to the same x,y position in a double[][]. The value should
024 * be between 0.0 (unblocked) for things light passes through, 1.0 (blocked) for
025 * things light can't pass at all, and possibly other values if you have
026 * translucent obstacles.
027 * <br>
028 * The returned light map is considered the percent of light in the cells.
029 * <br>
030 * Not all implementations are required to provide percentage levels of light.
031 * In such cases the returned values will be 0 for no light and 1.0 for fully
032 * lit. Implementations that return this way note so in their documentation.
033 * Currently, all implementations do provide percentage levels.
034 * <br>
035 * All solvers perform bounds checking so solid borders in the map are not
036 * required.
037 * <br>
038 * Static methods are provided to add together FOV maps in the simple way
039 * (disregarding visibility of distant FOV from a given cell), or the more
040 * practical way for roguelikes (where a cell needs to be within line-of-sight
041 * in the first place for a distant light to illuminate it). The second method
042 * relies on an LOS map, which is essentially the same as a very-high-radius
043 * FOV map and can be easily obtained with calculateLOSMap().
044 * <br>
045 * If you want to iterate through cells that are visible in a double[][] returned
046 * by FOV, you can pass that double[][] to the constructor for Region, and you
047 * can use the Region as a reliably-ordered List of Coord (among other things).
048 * The order Region iterates in is somewhat strange, and doesn't, for example,
049 * start at the center of an FOV map, but it will be the same every time you
050 * create a Region with the same FOV map (or the same visible Coords).
051 *
052 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
053 */
054public class FOV implements Serializable {
055    private static final long serialVersionUID = 3258723684733275798L;
056
057    public static final int
058            /**
059             * Performs FOV by pushing values outwards from the source location.
060             * It will go around corners a bit.
061             */
062            RIPPLE = 1,
063            /**
064             * Performs FOV by pushing values outwards from the source location.
065             * It will spread around edges like smoke or water, but maintain a
066             * tendency to curl towards the start position when going around
067             * edges.
068             */
069            RIPPLE_LOOSE = 2,
070            /**
071             * Performs FOV by pushing values outwards from the source location.
072             * It will only go around corners slightly.
073             */
074            RIPPLE_TIGHT = 3,
075            /**
076             * Performs FOV by pushing values outwards from the source location.
077             * It will go around corners massively.
078             */
079            RIPPLE_VERY_LOOSE = 4,
080            /**
081             * Uses Shadow Casting FOV algorithm. Treats all translucent cells
082             * as fully transparent. Returns a percentage from 1.0 (center of
083             * FOV) to 0.0 (outside of FOV).
084             */
085    SHADOW = 5;
086    private int type = SHADOW;
087    private static final Direction[] ccw = new Direction[]
088            {Direction.UP_RIGHT, Direction.UP_LEFT, Direction.DOWN_LEFT, Direction.DOWN_RIGHT, Direction.UP_RIGHT},
089            ccw_full = new Direction[]{Direction.RIGHT, Direction.UP_RIGHT, Direction.UP, Direction.UP_LEFT,
090            Direction.LEFT, Direction.DOWN_LEFT, Direction.DOWN, Direction.DOWN_RIGHT};
091
092    /**
093     * Creates a solver which will use the default SHADOW solver.
094     */
095    public FOV() {
096    }
097
098    /**
099     * Creates a solver which will use the provided FOV solver type.
100     *
101     * @param type
102     */
103    public FOV(int type) {
104        this.type = type;
105    }
106
107    /**
108     * Calculates the Field Of View for the provided map from the given x, y
109     * coordinates. Returns a light map where the values represent a percentage
110     * of fully lit.
111     *
112     * The starting point for the calculation is considered to be at the center
113     * of the origin cell. Radius determinations based on Euclidean
114     * calculations. The light will be treated as having infinite possible
115     * radius.
116     *
117     * @param resistanceMap the grid of cells to calculate on; the kind made by DungeonUtility.generateResistances()
118     * @param startx the horizontal component of the starting location
119     * @param starty the vertical component of the starting location
120     * @return the computed light grid
121     */
122    public double[][] calculateFOV(double[][] resistanceMap, int startx, int starty) {
123        return calculateFOV(resistanceMap, startx, starty, Integer.MAX_VALUE);
124    }
125
126    /**
127     * Calculates the Field Of View for the provided map from the given x, y
128     * coordinates. Returns a light map where the values represent a percentage
129     * of fully lit.
130     *
131     * The starting point for the calculation is considered to be at the center
132     * of the origin cell. Radius determinations based on Euclidean
133     * calculations.
134     *
135     * @param resistanceMap the grid of cells to calculate on; the kind made by DungeonUtility.generateResistances()
136     * @param startx the horizontal component of the starting location
137     * @param starty the vertical component of the starting location
138     * @param radius the distance the light will extend to
139     * @return the computed light grid
140     */
141    public double[][] calculateFOV(double[][] resistanceMap, int startx, int starty, double radius) {
142        return calculateFOV(resistanceMap, startx, starty, radius, Radius.CIRCLE);
143    }
144
145    /**
146     * Calculates the Field Of View for the provided map from the given x, y
147     * coordinates. Returns a light map where the values represent a percentage
148     * of fully lit.
149     *
150     * The starting point for the calculation is considered to be at the center
151     * of the origin cell. Radius determinations are determined by the provided
152     * RadiusStrategy.
153     *
154     * @param resistanceMap the grid of cells to calculate on; the kind made by DungeonUtility.generateResistances()
155     * @param startX the horizontal component of the starting location
156     * @param startY the vertical component of the starting location
157     * @param radius the distance the light will extend to
158     * @param radiusTechnique provides a means to calculate the radius as desired
159     * @return the computed light grid
160     */
161    public double[][] calculateFOV(double[][] resistanceMap, int startX, int startY, double radius, Radius radiusTechnique) {
162
163        double rad = Math.max(1, radius);
164        double decay = 1.0 / rad;
165
166        int width = resistanceMap.length;
167        int height = resistanceMap[0].length;
168
169        double[][] lightMap = new double[width][height];
170        lightMap[startX][startY] = 1;//make the starting space full power
171
172        boolean[][] nearLight = new boolean[width][height];
173        switch (type) {
174            case RIPPLE:
175                lightMap = doRippleFOV(lightMap, 2, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique);
176                break;
177            case RIPPLE_LOOSE:
178                lightMap = doRippleFOV(lightMap, 3, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique);
179                break;
180            case RIPPLE_TIGHT:
181                lightMap = doRippleFOV(lightMap, 1, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique);
182                break;
183            case RIPPLE_VERY_LOOSE:
184                lightMap = doRippleFOV(lightMap, 6, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique);
185                break;
186            case SHADOW:
187                // hotfix for too large radius -> set to longest possible straight-line Manhattan distance instead
188                // does not cause problems with brightness falloff because shadowcasting is on/off
189
190                // this should be fixed now, sorta. the distance is checked in the method this calls, so it doesn't ever
191                // run through more than 512 iterations of the radius-related loop (which seemed to be the only problem,
192                // running through billions of iterations when Integer/MAX_VALUE is given as a radius).
193                //if (rad > width + height){
194                //    rad = width + height;
195                //}
196                for (Direction d : Direction.DIAGONALS) {
197                    shadowCast(1, 1.0, 0.0, 0, d.deltaX, d.deltaY, 0, rad, startX, startY, decay, lightMap, resistanceMap, radiusTechnique);
198                    shadowCast(1, 1.0, 0.0, d.deltaX, 0, 0, d.deltaY, rad, startX, startY, decay, lightMap, resistanceMap, radiusTechnique);
199                }
200                break;
201        }
202
203        return lightMap;
204    }
205
206
207    /**
208     * Calculates the Field Of View for the provided map from the given x, y
209     * coordinates. Returns a light map where the values represent a percentage
210     * of fully lit.
211     *
212     * The starting point for the calculation is considered to be at the center
213     * of the origin cell. Radius determinations are determined by the provided
214     * RadiusStrategy. A conical section of FOV is lit by this method if
215     * span is greater than 0.
216     *
217     * @param resistanceMap the grid of cells to calculate on; the kind made by DungeonUtility.generateResistances()
218     * @param startX the horizontal component of the starting location
219     * @param startY the vertical component of the starting location
220     * @param radius the distance the light will extend to
221     * @param radiusTechnique provides a means to calculate the radius as desired
222     * @param angle the angle in degrees that will be the center of the FOV cone, 0 points right
223     * @param span the angle in degrees that measures the full arc contained in the FOV cone
224     * @return the computed light grid
225     */
226    public double[][] calculateFOV(double[][] resistanceMap, int startX, int startY, double radius,
227                                   Radius radiusTechnique, double angle, double span) {
228
229        double rad = Math.max(1, radius);
230
231        double decay = 1.0 / rad;
232
233                double angle2 = Math.toRadians((angle > 360.0 || angle < 0.0)
234                                ? GwtCompatibility.IEEEremainder(angle + 720.0, 360.0) : angle);
235        double span2 = Math.toRadians(span);
236        int width = resistanceMap.length;
237        int height = resistanceMap[0].length;
238
239        double[][] lightMap = new double[width][height];
240        lightMap[startX][startY] = 1;//make the starting space full power
241
242        boolean[][] nearLight = new boolean[width][height];
243        switch (type) {
244            case RIPPLE:
245                lightMap = doRippleFOV(lightMap, 2, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique, angle2, span2);
246                break;
247            case RIPPLE_LOOSE:
248                lightMap = doRippleFOV(lightMap, 3, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique, angle2, span2);
249                break;
250            case RIPPLE_TIGHT:
251                lightMap = doRippleFOV(lightMap, 1, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique, angle2, span2);
252                break;
253            case RIPPLE_VERY_LOOSE:
254                lightMap = doRippleFOV(lightMap, 6, startX, startY, startX, startY, decay, rad, resistanceMap, nearLight, radiusTechnique, angle2, span2);
255                break;
256            case SHADOW:
257                // hotfix for too large radius -> set to longest possible straight-line Manhattan distance instead
258                // does not cause problems with brightness falloff because shadowcasting is on/off
259
260                // this should be fixed now, sorta. the distance is checked in the method this calls, so it doesn't ever
261                // run through more than 512 iterations of the radius-related loop (which seemed to be the only problem,
262                // running through billions of iterations when Integer/MAX_VALUE is given as a radius).
263                //if (rad > width + height){
264                //    rad = width + height;
265                //}
266                int ctr = 0;
267                boolean started = false;
268                for (Direction d : ccw) {
269                    ctr %= 4;
270                    ++ctr;
271                    if (angle <= Math.PI / 2.0 * ctr + span / 2.0)
272                        started = true;
273                    if (started) {
274                        if(ctr < 4 && angle < Math.PI / 2.0 * (ctr - 1) - span / 2.0)
275                            break;
276                        lightMap = shadowCastLimited(1, 1.0, 0.0, 0, d.deltaX, d.deltaY, 0, rad, startX, startY, decay, lightMap, resistanceMap, radiusTechnique, angle2, span2);
277                        lightMap = shadowCastLimited(1, 1.0, 0.0, d.deltaX, 0, 0, d.deltaY, rad, startX, startY, decay, lightMap, resistanceMap, radiusTechnique, angle2, span2);
278                    }
279                }
280                break;
281        }
282
283        return lightMap;
284    }
285
286
287    private double[][] doRippleFOV(double[][] lightMap, int ripple, int x, int y, int startx, int starty, double decay, double radius, double[][] map, boolean[][] indirect, Radius radiusStrategy) {
288        /* Not using Deque's interface, it isn't GWT compatible */
289        final LinkedList<Coord> dq = new LinkedList<>();
290        int width = lightMap.length;
291        int height = lightMap[0].length;
292        dq.offer(Coord.get(x, y));
293        while (!dq.isEmpty()) {
294            Coord p = dq.removeFirst();
295            if (lightMap[p.x][p.y] <= 0 || indirect[p.x][p.y]) {
296                continue;//no light to spread
297            }
298
299            for (Direction dir : Direction.OUTWARDS) {
300                int x2 = p.x + dir.deltaX;
301                int y2 = p.y + dir.deltaY;
302                if (x2 < 0 || x2 >= width || y2 < 0 || y2 >= height //out of bounds
303                        || radiusStrategy.radius(startx, starty, x2, y2) >= radius + 1) {//+1 to cover starting tile
304                    continue;
305                }
306
307                double surroundingLight = nearRippleLight(x2, y2, ripple, startx, starty, decay, lightMap, map, indirect, radiusStrategy);
308                if (lightMap[x2][y2] < surroundingLight) {
309                    lightMap[x2][y2] = surroundingLight;
310                    if (map[x2][y2] < 1) {//make sure it's not a wall
311                        dq.offer(Coord.get(x2, y2));//redo neighbors since this one's light changed
312                    }
313                }
314            }
315        }
316        return lightMap;
317    }
318
319
320
321    private double[][] doRippleFOV(double[][] lightMap, int ripple, int x, int y, int startx, int starty, double decay, double radius, double[][] map, boolean[][] indirect, Radius radiusStrategy, double angle, double span) {
322        /* Not using Deque's interface, it isn't GWT compatible */
323        final LinkedList<Coord> dq = new LinkedList<>();
324        int width = lightMap.length;
325        int height = lightMap[0].length;
326        dq.offer(Coord.get(x, y));
327        while (!dq.isEmpty()) {
328            Coord p = dq.removeFirst();
329            if (lightMap[p.x][p.y] <= 0 || indirect[p.x][p.y]) {
330                continue;//no light to spread
331            }
332
333            for (Direction dir : ccw_full) {
334                int x2 = p.x + dir.deltaX;
335                int y2 = p.y + dir.deltaY;
336                if (x2 < 0 || x2 >= width || y2 < 0 || y2 >= height //out of bounds
337                        || radiusStrategy.radius(startx, starty, x2, y2) >= radius + 1) {//+1 to cover starting tile
338                    continue;
339                }
340                double newAngle = Math.atan2(y2 - starty, x2 - startx) + Math.PI * 2;
341                                if (Math.abs(GwtCompatibility.IEEEremainder(angle - newAngle + Math.PI * 8, Math.PI * 2)) > span / 2.0)
342                                        continue;
343
344                double surroundingLight = nearRippleLight(x2, y2, ripple, startx, starty, decay, lightMap, map, indirect, radiusStrategy );
345                if (lightMap[x2][y2] < surroundingLight) {
346                    lightMap[x2][y2] = surroundingLight;
347                    if (map[x2][y2] < 1) {//make sure it's not a wall
348                        dq.offer(Coord.get(x2, y2));//redo neighbors since this one's light changed
349                    }
350                }
351            }
352        }
353        return lightMap;
354    }
355
356    private double nearRippleLight(int x, int y, int rippleNeighbors, int startx, int starty, double decay, double[][] lightMap, double[][] map, boolean[][] indirect, Radius radiusStrategy) {
357        if (x == startx && y == starty) {
358            return 1;
359        }
360        int width = lightMap.length;
361        int height = lightMap[0].length;
362        List<Coord> neighbors = new ArrayList<>();
363        double tmpDistance = 0, testDistance;
364        Coord c;
365        for (Direction di : Direction.OUTWARDS) {
366            int x2 = x + di.deltaX;
367            int y2 = y + di.deltaY;
368            if (x2 >= 0 && x2 < width && y2 >= 0 && y2 < height) {
369                tmpDistance = radiusStrategy.radius(startx, starty, x2, y2);
370                int idx = 0;
371                for(int i = 0; i < neighbors.size() && i <= rippleNeighbors; i++)
372                {
373                    c = neighbors.get(i);
374                    testDistance = radiusStrategy.radius(startx, starty, c.x, c.y);
375                    if(tmpDistance < testDistance) {
376                        break;
377                    }
378                    idx++;
379                }
380                neighbors.add(idx, Coord.get(x2, y2));
381            }
382        }
383
384        if (neighbors.isEmpty()) {
385            return 0;
386        }
387        neighbors = neighbors.subList(0, rippleNeighbors);
388/*
389        while (neighbors.size() > rippleNeighbors) {
390            Coord p = neighbors.remove(0);
391            double dist = radiusStrategy.radius(startx, starty, p.x, p.y);
392            double dist2 = 0;
393            for (Coord p2 : neighbors) {
394                dist2 = Math.max(dist2, radiusStrategy.radius(startx, starty, p2.x, p2.y));
395            }
396            if (dist < dist2) {//not the largest, put it back
397                neighbors.add(p);
398            }
399        }
400*/
401        double light = 0;
402        int lit = 0, indirects = 0;
403        for (Coord p : neighbors) {
404            if (lightMap[p.x][p.y] > 0) {
405                lit++;
406                if (indirect[p.x][p.y]) {
407                    indirects++;
408                }
409                double dist = radiusStrategy.radius(x, y, p.x, p.y);
410                light = Math.max(light, lightMap[p.x][p.y] - dist * decay - map[p.x][p.y]);
411            }
412        }
413
414        if (map[x][y] >= 1 || indirects >= lit) {
415            indirect[x][y] = true;
416        }
417        return light;
418    }
419
420    private double[][] shadowCast(int row, double start, double end, int xx, int xy, int yx, int yy,
421                                  double radius, int startx, int starty, double decay, double[][] lightMap,
422                                  double[][] map, Radius radiusStrategy) {
423        double newStart = 0;
424        if (start < end) {
425            return lightMap;
426        }
427        int width = lightMap.length;
428        int height = lightMap[0].length;
429
430        boolean blocked = false;
431        for (int distance = row; distance <= radius && distance < width + height && !blocked; distance++) {
432            int deltaY = -distance;
433            for (int deltaX = -distance; deltaX <= 0; deltaX++) {
434                int currentX = startx + deltaX * xx + deltaY * xy;
435                int currentY = starty + deltaX * yx + deltaY * yy;
436                double leftSlope = (deltaX - 0.5f) / (deltaY + 0.5f);
437                double rightSlope = (deltaX + 0.5f) / (deltaY - 0.5f);
438
439                if (!(currentX >= 0 && currentY >= 0 && currentX < width && currentY < height) || start < rightSlope) {
440                    continue;
441                } else if (end > leftSlope) {
442                    break;
443                }
444                double deltaRadius = radiusStrategy.radius(deltaX, deltaY);
445                //check if it's within the lightable area and light if needed
446                if (deltaRadius <= radius) {
447                    double bright = 1 - decay * deltaRadius;
448                    lightMap[currentX][currentY] = bright;
449                }
450
451                if (blocked) { //previous cell was a blocking one
452                    if (map[currentX][currentY] >= 1) {//hit a wall
453                        newStart = rightSlope;
454                    } else {
455                        blocked = false;
456                        start = newStart;
457                    }
458                } else {
459                    if (map[currentX][currentY] >= 1 && distance < radius) {//hit a wall within sight line
460                        blocked = true;
461                        lightMap = shadowCast(distance + 1, start, leftSlope, xx, xy, yx, yy, radius, startx, starty, decay, lightMap, map, radiusStrategy);
462                        newStart = rightSlope;
463                    }
464                }
465            }
466        }
467        return lightMap;
468    }
469    private double[][] shadowCastLimited(int row, double start, double end, int xx, int xy, int yx, int yy,
470                                         double radius, int startx, int starty, double decay, double[][] lightMap,
471                                         double[][] map, Radius radiusStrategy, double angle, double span) {
472        double newStart = 0;
473        if (start < end) {
474            return lightMap;
475        }
476        int width = lightMap.length;
477        int height = lightMap[0].length;
478
479        boolean blocked = false;
480        for (int distance = row; distance <= radius && distance < width + height && !blocked; distance++) {
481            int deltaY = -distance;
482            for (int deltaX = -distance; deltaX <= 0; deltaX++) {
483                int currentX = startx + deltaX * xx + deltaY * xy;
484                int currentY = starty + deltaX * yx + deltaY * yy;
485                double leftSlope = (deltaX - 0.5f) / (deltaY + 0.5f);
486                double rightSlope = (deltaX + 0.5f) / (deltaY - 0.5f);
487
488                if (!(currentX >= 0 && currentY >= 0 && currentX < width && currentY < height) || start < rightSlope) {
489                    continue;
490                } else if (end > leftSlope) {
491                    break;
492                }
493                double newAngle = Math.atan2(currentY - starty, currentX - startx) + Math.PI * 2;
494                                if (Math.abs(GwtCompatibility.IEEEremainder(angle - newAngle + Math.PI * 8, Math.PI * 2)) > span / 2.0)
495                                        continue;
496
497                double deltaRadius = radiusStrategy.radius(deltaX, deltaY);
498                //check if it's within the lightable area and light if needed
499                if (deltaRadius <= radius) {
500                    double bright = 1 - decay * deltaRadius;
501                    lightMap[currentX][currentY] = bright;
502                }
503
504                if (blocked) { //previous cell was a blocking one
505                    if (map[currentX][currentY] >= 1) {//hit a wall
506                        newStart = rightSlope;
507                    } else {
508                        blocked = false;
509                        start = newStart;
510                    }
511                } else {
512                    if (map[currentX][currentY] >= 1 && distance < radius) {//hit a wall within sight line
513                        blocked = true;
514                        lightMap = shadowCastLimited(distance + 1, start, leftSlope, xx, xy, yx, yy, radius, startx, starty, decay, lightMap, map, radiusStrategy, angle, span);
515                        newStart = rightSlope;
516                    }
517                }
518            }
519        }
520        return lightMap;
521    }
522
523    /**
524     * Adds multiple FOV maps together in the simplest way possible; does not check line-of-sight between FOV maps.
525     * Clamps the highest value for any single position at 1.0.
526     * @param maps an array or vararg of 2D double arrays, each usually returned by calculateFOV()
527     * @return the sum of all the 2D double arrays passed, using the dimensions of the first if they don't all match
528     */
529    public static double[][] addFOVs(double[][]... maps)
530    {
531        if(maps == null || maps.length == 0)
532            return new double[0][0];
533        double[][] map = GwtCompatibility.copy2D(maps[0]);
534        for(int i = 1; i < maps.length; i++)
535        {
536            for (int x = 0; x < map.length && x < maps[i].length; x++) {
537                for (int y = 0; y < map[x].length && y < maps[i][x].length; y++) {
538                    map[x][y] += maps[i][x][y];
539                }
540            }
541        }
542        for (int x = 0; x < map.length; x++) {
543            for (int y = 0; y < map[x].length; y++) {
544                if(map[x][y] > 1.0) map[x][y] = 1.0;
545            }
546        }
547        return map;
548    }
549
550    /**
551     * Adds multiple FOV maps together in the simplest way possible; does not check line-of-sight between FOV maps.
552     * Clamps the highest value for any single position at 1.0.
553     * @param maps an Iterable of 2D double arrays (most collections implement Iterable),
554     *             each usually returned by calculateFOV()
555     * @return the sum of all the 2D double arrays passed, using the dimensions of the first if they don't all match
556     */
557    public static double[][] addFOVs(Iterable<double[][]> maps)
558    {
559        if(maps == null)
560            return new double[0][0];
561        Iterator<double[][]> it = maps.iterator();
562        if(!it.hasNext())
563            return new double[0][0];
564        double[][] map = GwtCompatibility.copy2D(it.next()), t;
565        while (it.hasNext())
566        {
567            t = it.next();
568            for (int x = 0; x < map.length && x < t.length; x++) {
569                for (int y = 0; y < map[x].length && y < t[x].length; y++) {
570                    map[x][y] += t[x][y];
571                }
572            }
573        }
574        for (int x = 0; x < map.length; x++) {
575            for (int y = 0; y < map[x].length; y++) {
576                if(map[x][y] > 1.0) map[x][y] = 1.0;
577            }
578        }
579        return map;
580    }
581
582    /**
583     * Adds together multiple FOV maps, but only adds to a position if it is visible in the given LOS map. Useful if
584     * you want distant lighting to be visible only if the player has line-of-sight to a lit cell. Typically the LOS map
585     * is calculated by calculateLOSMap(), using the same resistance map used to calculate the FOV maps.
586     * Clamps the highest value for any single position at 1.0.
587     * @param losMap an LOS map such as one generated by calculateLOSMap()
588     * @param maps an array or vararg of 2D double arrays, each usually returned by calculateFOV()
589     * @return the sum of all the 2D double arrays in maps where a cell was visible in losMap
590     */
591    public static double[][] mixVisibleFOVs(double[][] losMap, double[][]... maps)
592    {
593        if(losMap == null || losMap.length == 0)
594            return addFOVs(maps);
595        double[][] map = new double[losMap.length][losMap[0].length];
596        if(maps == null || maps.length == 0)
597            return map;
598        for(int i = 0; i < maps.length; i++)
599        {
600            for (int x = 0; x < losMap.length && x < map.length && x < maps[i].length; x++) {
601                for (int y = 0; y < losMap[x].length && y < map[x].length && y < maps[i][x].length; y++) {
602                    if(losMap[x][y] > 0.0001) {
603                        map[x][y] += maps[i][x][y];
604                        if(map[x][y] > 1.0) map[x][y] = 1.0;
605                    }
606                }
607            }
608        }
609        return map;
610    }
611
612    /**
613     * Adds together multiple FOV maps, but only adds to a position if it is visible in the given LOS map. Useful if
614     * you want distant lighting to be visible only if the player has line-of-sight to a lit cell. Typically the LOS map
615     * is calculated by calculateLOSMap(), using the same resistance map used to calculate the FOV maps.
616     * Clamps the highest value for any single position at 1.0.
617     * @param losMap an LOS map such as one generated by calculateLOSMap()
618     * @param maps an Iterable of 2D double arrays, each usually returned by calculateFOV()
619     * @return the sum of all the 2D double arrays in maps where a cell was visible in losMap
620     */
621    public static double[][] mixVisibleFOVs(double[][] losMap, Iterable<double[][]> maps)
622    {
623        if(losMap == null || losMap.length == 0)
624            return addFOVs(maps);
625        double[][] map = new double[losMap.length][losMap[0].length], t;
626        if(maps == null)
627            return map;
628        Iterator<double[][]> it = maps.iterator();
629        if(!it.hasNext())
630            return map;
631
632        while (it.hasNext())
633        {
634            t = it.next();
635            for (int x = 0; x < losMap.length && x < map.length && x < t.length; x++) {
636                for (int y = 0; y < losMap[x].length && y < map[x].length && y < t[x].length; y++) {
637                    if (losMap[x][y] > 0.0001) {
638                        map[x][y] += t[x][y];
639                        if(map[x][y] > 1.0) map[x][y] = 1.0;
640                    }
641                }
642            }
643        }
644        return map;
645    }
646
647    /**
648     * Calculates what cells are visible from (startX,startY) using the given resistanceMap; this can be given to
649     * mixVisibleFOVs() to limit extra light sources to those visible from the starting point. Just like calling
650     * calculateFOV(), this creates a new double[][]; there doesn't appear to be a way to work with Ripple FOV and avoid
651     * needing an empty double[][] every time, since it uses previously-placed light to determine how it should spread.
652     * @param resistanceMap the grid of cells to calculate on; the kind made by DungeonUtility.generateResistances()
653     * @param startX the center of the LOS map; typically the player's x-position
654     * @param startY the center of the LOS map; typically the player's y-position
655     * @return an LOS map with the given starting point
656     */
657    public double[][] calculateLOSMap(double[][] resistanceMap, int startX, int startY)
658    {
659        if(resistanceMap == null || resistanceMap.length == 0)
660            return new double[0][0];
661        return calculateFOV(resistanceMap, startX, startY, resistanceMap.length + resistanceMap[0].length, Radius.SQUARE);
662    }
663}