001package squidpony.squidai;
002
003import squidpony.annotation.GwtIncompatible;
004import squidpony.squidgrid.FOVCache;
005import squidpony.squidgrid.LOS;
006import squidpony.squidgrid.Radius;
007import squidpony.squidgrid.mapping.DungeonUtility;
008import squidpony.squidmath.Coord;
009
010import java.util.*;
011
012/**
013 * Line Area of Effect that affects an slightly expanded (Elias) line from a given origin Coord to a given end Coord,
014 * plus an optional radius of cells around the path of the line, while respecting obstacles in its path and possibly
015 * stopping if obstructed. You can specify the RadiusType to Radius.DIAMOND for Manhattan distance, RADIUS.SQUARE for
016 * Chebyshev, or RADIUS.CIRCLE for Euclidean.
017 *
018 * You may want the BeamAOE class instead of this. LineAOE travels point-to-point and does not restrict length, while
019 * BeamAOE travels a specific length (and may have a radius, like LineAOE) but then stops only after the travel down the
020 * length and radius has reached its end. This difference is relevant if a game has effects that have a definite
021 * area measured in a rectangle or elongated pillbox shape, such as a "20-foot-wide bolt of lightning, 100 feet long."
022 * BeamAOE is more suitable for that effect, while LineAOE may be more suitable for things like focused lasers that
023 * pass through small (likely fleshy) obstacles but stop after hitting the aimed-at target.
024 *
025 * LineAOE will strike a small area behind the user and in the opposite direction of the target if the radius is
026 * greater than 0. This behavior may be altered in a future version.
027 *
028 * This will produce doubles for its findArea() method which are equal to 1.0.
029 *
030 * This class uses squidpony.squidmath.Elias and squidpony.squidai.DijkstraMap to create its area of effect.
031 * Created by Tommy Ettinger on 7/14/2015.
032 */
033public class LineAOE implements AOE {
034    private Coord origin, end;
035    private int radius;
036    private char[][] dungeon;
037    private DijkstraMap dijkstra;
038    private Radius rt;
039    private LOS los;
040    private Reach reach = new Reach(1, 1, Radius.SQUARE, null);
041    public LineAOE(Coord origin, Coord end)
042    {
043        dijkstra = new DijkstraMap();
044        dijkstra.measurement = DijkstraMap.Measurement.CHEBYSHEV;
045        rt = Radius.SQUARE;
046        this.origin = origin;
047        this.end = end;
048        radius = 0;
049        los = new LOS(LOS.DDA);
050    }
051    public LineAOE(Coord origin, Coord end, int radius)
052    {
053        dijkstra = new DijkstraMap();
054        dijkstra.measurement = DijkstraMap.Measurement.CHEBYSHEV;
055        rt = Radius.SQUARE;
056        this.origin = origin;
057        this.end = end;
058        this.radius = radius;
059        los = new LOS(LOS.DDA);
060    }
061    public LineAOE(Coord origin, Coord end, int radius, Radius radiusType)
062    {
063        dijkstra = new DijkstraMap();
064        rt = radiusType;
065        switch (radiusType)
066        {
067            case OCTAHEDRON:
068            case DIAMOND:
069                dijkstra.measurement = DijkstraMap.Measurement.MANHATTAN;
070                break;
071            case CUBE:
072            case SQUARE:
073                dijkstra.measurement = DijkstraMap.Measurement.CHEBYSHEV;
074                break;
075            default:
076                dijkstra.measurement = DijkstraMap.Measurement.EUCLIDEAN;
077                break;
078        }
079        this.origin = origin;
080        this.end = end;
081        this.radius = radius;
082        los = new LOS(LOS.DDA);
083    }
084    public LineAOE(Coord origin, Coord end, int radius, Radius radiusType, int minRange, int maxRange)
085    {
086        dijkstra = new DijkstraMap();
087        rt = radiusType;
088        switch (radiusType)
089        {
090            case OCTAHEDRON:
091            case DIAMOND:
092                dijkstra.measurement = DijkstraMap.Measurement.MANHATTAN;
093                break;
094            case CUBE:
095            case SQUARE:
096                dijkstra.measurement = DijkstraMap.Measurement.CHEBYSHEV;
097                break;
098            default:
099                dijkstra.measurement = DijkstraMap.Measurement.EUCLIDEAN;
100                break;
101        }
102        this.origin = origin;
103        this.end = end;
104        this.radius = radius;
105        reach.minDistance = minRange;
106        reach.maxDistance = maxRange;
107        los = new LOS(LOS.DDA);
108    }
109    private double[][] initDijkstra()
110    {
111        los.isReachable(dungeon, origin.x, origin.y, end.x, end.y, rt);
112        Queue<Coord> lit = los.getLastPath();
113
114        dijkstra.initialize(dungeon);
115        for(Coord p : lit)
116        {
117            dijkstra.setGoal(p);
118        }
119        if(radius == 0)
120            return dijkstra.gradientMap;
121        return dijkstra.partialScan(radius, null);
122    }
123
124    @Override
125    public Coord getOrigin() {
126        return origin;
127    }
128
129    @Override
130    public void setOrigin(Coord origin) {
131        this.origin = origin;
132        dijkstra.resetMap();
133        dijkstra.clearGoals();
134    }
135
136    @Override
137    public AimLimit getLimitType() {
138        return reach.limit;
139    }
140
141    @Override
142    public int getMinRange() {
143        return reach.minDistance;
144    }
145
146    @Override
147    public int getMaxRange() {
148        return reach.maxDistance;
149    }
150
151    @Override
152    public Radius getMetric() {
153        return reach.metric;
154    }
155
156    /**
157     * Gets the same values returned by getLimitType(), getMinRange(), getMaxRange(), and getMetric() bundled into one
158     * Reach object.
159     *
160     * @return a non-null Reach object.
161     */
162    @Override
163    public Reach getReach() {
164        return reach;
165    }
166
167    @Override
168    public void setLimitType(AimLimit limitType) {
169        reach.limit = limitType;
170
171    }
172
173    @Override
174    public void setMinRange(int minRange) {
175        reach.minDistance = minRange;
176    }
177
178    @Override
179    public void setMaxRange(int maxRange) {
180        reach.maxDistance = maxRange;
181
182    }
183
184    @Override
185    public void setMetric(Radius metric) {
186        reach.metric = metric;
187    }
188
189    /**
190     * Sets the same values as setLimitType(), setMinRange(), setMaxRange(), and setMetric() using one Reach object.
191     *
192     * @param reach a non-null Reach object.
193     */
194    @Override
195    public void setReach(Reach reach) {
196        if(reach != null)
197            this.reach = reach;
198    }
199
200
201    public Coord getEnd() {
202        return end;
203    }
204
205    public void setEnd(Coord end) {
206        if (dungeon != null && end.isWithin(dungeon.length, dungeon[0].length) &&
207                AreaUtils.verifyReach(reach, origin, end)) {
208            this.end = end;
209            dijkstra.resetMap();
210            dijkstra.clearGoals();
211        }
212    }
213
214    public int getRadius() {
215        return radius;
216    }
217
218    public void setRadius(int radius) {
219        this.radius = radius;
220    }
221
222    public Radius getRadiusType()
223    {
224        return rt;
225    }
226    public void setRadiusType(Radius radiusType)
227    {
228        rt = radiusType;
229        switch (radiusType)
230        {
231            case OCTAHEDRON:
232            case DIAMOND:
233                dijkstra.measurement = DijkstraMap.Measurement.MANHATTAN;
234                break;
235            case CUBE:
236            case SQUARE:
237                dijkstra.measurement = DijkstraMap.Measurement.CHEBYSHEV;
238                break;
239            default:
240                dijkstra.measurement = DijkstraMap.Measurement.EUCLIDEAN;
241                break;
242        }
243    }
244
245    @Override
246    public void shift(Coord aim) {
247        setEnd(aim);
248    }
249
250    @Override
251    public boolean mayContainTarget(Set<Coord> targets) {
252        for (Coord p : targets)
253        {
254            if(rt.radius(origin.x, origin.y, p.x, p.y) + rt.radius(end.x, end.y, p.x, p.y) -
255                    rt.radius(origin.x, origin.y, end.x, end.y) <= 3.0 + radius)
256                return true;
257        }
258        return false;
259    }
260
261    @Override
262    public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
263        if(targets == null)
264            return new LinkedHashMap<>();
265        if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>();
266
267        //requiredExclusions.remove(origin);
268        int totalTargets = targets.size();
269        LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8);
270
271        if(totalTargets == 0)
272            return bestPoints;
273
274        Coord[] ts = targets.toArray(new Coord[targets.size()]);
275        Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]);
276        Coord t = exs[0];
277
278        double[][][] compositeMap = new double[ts.length][dungeon.length][dungeon[0].length];
279
280        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length];
281        for (int i = 0; i < dungeon.length; i++) {
282            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
283        }
284        DijkstraMap dt = new DijkstraMap(dungeon, dijkstra.measurement);
285        double[][] resMap = DungeonUtility.generateResistances(dungeon);
286        Coord tempPt = Coord.get(0, 0);
287        for (int i = 0; i < exs.length; ++i) {
288            t = exs[i];
289            dt.resetMap();
290            dt.clearGoals();
291
292            los.isReachable(resMap, origin.x, origin.y, t.x, t.y, rt);
293            Queue<Coord> lit = los.getLastPath();
294
295            for(Coord p : lit)
296            {
297                dt.setGoal(p);
298            }
299            if(radius > 0)
300                dt.partialScan(radius, null);
301
302            for (int x = 0; x < dungeon.length; x++) {
303                for (int y = 0; y < dungeon[x].length; y++) {
304                    tempPt = Coord.get(x, y);
305                    dungeonCopy[x][y] = (dt.gradientMap[x][y] < DijkstraMap.FLOOR || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
306                }
307            }
308        }
309
310        t = ts[0];
311
312        for (int i = 0; i < ts.length; ++i) {
313            DijkstraMap dm = new DijkstraMap(dungeon, dijkstra.measurement);
314
315            t = ts[i];
316            dt.resetMap();
317            dt.clearGoals();
318            los.isReachable(resMap, origin.x, origin.y, t.x, t.y, rt);
319            Queue<Coord> lit = los.getLastPath();
320
321            for(Coord p : lit)
322            {
323                dt.setGoal(p);
324            }
325            if(radius > 0)
326                dt.partialScan(radius, null);
327
328
329            double dist = 0.0;
330            for (int x = 0; x < dungeon.length; x++) {
331                for (int y = 0; y < dungeon[x].length; y++) {
332                    if (dt.gradientMap[x][y] < DijkstraMap.FLOOR){
333                        dist = reach.metric.radius(origin.x, origin.y, x, y);
334                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
335                            compositeMap[i][x][y] = dm.physicalMap[x][y];
336                        else
337                            compositeMap[i][x][y] = DijkstraMap.WALL;
338                    }
339                    else compositeMap[i][x][y] = DijkstraMap.WALL;
340                }
341            }
342            if(compositeMap[i][ts[i].x][ts[i].y] > DijkstraMap.FLOOR)
343            {
344                for (int x = 0; x < dungeon.length; x++) {
345                    Arrays.fill(compositeMap[i][x], 99999.0);
346                }
347                continue;
348            }
349
350
351            dm.initialize(compositeMap[i]);
352            dm.setGoal(t);
353            dm.scan(null);
354            for (int x = 0; x < dungeon.length; x++) {
355                for (int y = 0; y < dungeon[x].length; y++) {
356                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 99999.0;
357                }
358            }
359            dm.resetMap();
360            dm.clearGoals();
361        }
362        double bestQuality = 99999 * ts.length;
363        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
364        for (int x = 0; x < qualityMap.length; x++) {
365            for (int y = 0; y < qualityMap[x].length; y++) {
366                qualityMap[x][y] = 0.0;
367                long bits = 0;
368                for (int i = 0; i < ts.length; ++i) {
369                    qualityMap[x][y] += compositeMap[i][x][y];
370                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
371                        bits |= 1 << i;
372                }
373                if(qualityMap[x][y] < bestQuality)
374                {
375                    ArrayList<Coord> ap = new ArrayList<>();
376
377                    for (int i = 0; i < ts.length && i < 63; ++i) {
378                        if((bits & (1 << i)) != 0)
379                            ap.add(ts[i]);
380                    }
381                    if(ap.size() > 0) {
382                        bestQuality = qualityMap[x][y];
383                        bestPoints.clear();
384                        bestPoints.put(Coord.get(x, y), ap);
385                    }
386                }
387                else if(qualityMap[x][y] == bestQuality)
388                {
389                    ArrayList<Coord> ap = new ArrayList<>();
390
391                    for (int i = 0; i < ts.length && i < 63; ++i) {
392                        if((bits & (1 << i)) != 0)
393                            ap.add(ts[i]);
394                    }
395
396                    if (ap.size() > 0) {
397                        bestPoints.put(Coord.get(x, y), ap);
398                    }
399                }
400            }
401        }
402
403        return bestPoints;
404    }
405
406    @Override
407    public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> priorityTargets, Set<Coord> lesserTargets, Set<Coord> requiredExclusions) {
408        if(priorityTargets == null)
409            return idealLocations(lesserTargets, requiredExclusions);
410        if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>();
411
412        //requiredExclusions.remove(origin);
413        int totalTargets = priorityTargets.size() + lesserTargets.size();
414        LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8);
415
416        if(totalTargets == 0)
417            return bestPoints;
418
419        Coord[] pts = priorityTargets.toArray(new Coord[priorityTargets.size()]);
420        Coord[] lts = lesserTargets.toArray(new Coord[lesserTargets.size()]);
421        Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]);
422        Coord t = exs[0];
423
424        double[][][] compositeMap = new double[totalTargets][dungeon.length][dungeon[0].length];
425
426        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length],
427                dungeonPriorities = new char[dungeon.length][dungeon[0].length];
428        for (int i = 0; i < dungeon.length; i++) {
429            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
430            Arrays.fill(dungeonPriorities[i], '#');
431        }
432        DijkstraMap dt = new DijkstraMap(dungeon, dijkstra.measurement);
433        double[][] resMap = DungeonUtility.generateResistances(dungeon);
434        Coord tempPt = Coord.get(0, 0);
435        for (int i = 0; i < exs.length; ++i) {
436            t = exs[i];
437            dt.resetMap();
438            dt.clearGoals();
439            los.isReachable(resMap, origin.x, origin.y, t.x, t.y, rt);
440            Queue<Coord> lit = los.getLastPath();
441
442            for(Coord p : lit)
443            {
444                dt.setGoal(p);
445            }
446            if(radius > 0)
447                dt.partialScan(radius, null);
448
449            for (int x = 0; x < dungeon.length; x++) {
450                for (int y = 0; y < dungeon[x].length; y++) {
451                    tempPt = Coord.get(x, y);
452                    dungeonCopy[x][y] = (dt.gradientMap[x][y] < DijkstraMap.FLOOR || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
453                }
454            }
455        }
456
457        t = pts[0];
458
459        for (int i = 0; i < pts.length; ++i) {
460            DijkstraMap dm = new DijkstraMap(dungeon, dijkstra.measurement);
461            t = pts[i];
462            dt.resetMap();
463            dt.clearGoals();
464            los.isReachable(resMap, origin.x, origin.y, t.x, t.y, rt);
465            Queue<Coord> lit = los.getLastPath();
466
467            for(Coord p : lit)
468            {
469                dt.setGoal(p);
470            }
471            if(radius > 0)
472                dt.partialScan(radius, null);
473
474
475            double dist = 0.0;
476            for (int x = 0; x < dungeon.length; x++) {
477                for (int y = 0; y < dungeon[x].length; y++) {
478                    if (dt.gradientMap[x][y] < DijkstraMap.FLOOR){
479                        dist = reach.metric.radius(origin.x, origin.y, x, y);
480                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) {
481                            compositeMap[i][x][y] = dm.physicalMap[x][y];
482                            dungeonPriorities[x][y] = dungeon[x][y];
483                        }
484                        else
485                            compositeMap[i][x][y] = DijkstraMap.WALL;
486                    }
487                    else compositeMap[i][x][y] = DijkstraMap.WALL;
488                }
489            }
490            if(compositeMap[i][pts[i].x][pts[i].y] > DijkstraMap.FLOOR)
491            {
492                for (int x = 0; x < dungeon.length; x++) {
493                    Arrays.fill(compositeMap[i][x], 399999.0);
494                }
495                continue;
496            }
497
498
499            dm.initialize(compositeMap[i]);
500            dm.setGoal(t);
501            dm.scan(null);
502            for (int x = 0; x < dungeon.length; x++) {
503                for (int y = 0; y < dungeon[x].length; y++) {
504                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 399999.0;
505                }
506            }
507            dm.resetMap();
508            dm.clearGoals();
509        }
510
511        t = lts[0];
512
513        for (int i = pts.length; i < totalTargets; ++i) {
514            DijkstraMap dm = new DijkstraMap(dungeon, dijkstra.measurement);
515            t = lts[i - pts.length];
516            dt.resetMap();
517            dt.clearGoals();
518            los.isReachable(resMap, origin.x, origin.y, t.x, t.y, rt);
519            Queue<Coord> lit = los.getLastPath();
520
521            for(Coord p : lit)
522            {
523                dt.setGoal(p);
524            }
525            if(radius > 0)
526                dt.partialScan(radius, null);
527
528            double dist = 0.0;
529            for (int x = 0; x < dungeon.length; x++) {
530                for (int y = 0; y < dungeon[x].length; y++) {
531                    if (dt.gradientMap[x][y] < DijkstraMap.FLOOR){
532                        dist = reach.metric.radius(origin.x, origin.y, x, y);
533                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
534                            compositeMap[i][x][y] = dm.physicalMap[x][y];
535                        else
536                            compositeMap[i][x][y] = DijkstraMap.WALL;
537                    }
538                    else compositeMap[i][x][y] = DijkstraMap.WALL;
539                }
540            }
541            if(compositeMap[i][lts[i - pts.length].x][lts[i - pts.length].y] > DijkstraMap.FLOOR)
542            {
543                for (int x = 0; x < dungeon.length; x++)
544                {
545                    Arrays.fill(compositeMap[i][x], 99999.0);
546                }
547                continue;
548            }
549
550
551            dm.initialize(compositeMap[i]);
552            dm.setGoal(t);
553            dm.scan(null);
554            for (int x = 0; x < dungeon.length; x++) {
555                for (int y = 0; y < dungeon[x].length; y++) {
556                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!' && dungeonPriorities[x][y] != '#') ? dm.gradientMap[x][y] : 99999.0;
557                }
558            }
559            dm.resetMap();
560            dm.clearGoals();
561        }
562        double bestQuality = 99999 * lts.length + 399999 * pts.length;
563        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
564        for (int x = 0; x < qualityMap.length; x++) {
565            for (int y = 0; y < qualityMap[x].length; y++) {
566                qualityMap[x][y] = 0.0;
567                long pbits = 0, lbits = 0;
568                for (int i = 0; i < pts.length; ++i) {
569                    qualityMap[x][y] += compositeMap[i][x][y];
570                    if(compositeMap[i][x][y] < 399999.0 && i < 63)
571                        pbits |= 1 << i;
572                }
573                for (int i = pts.length; i < totalTargets; ++i) {
574                    qualityMap[x][y] += compositeMap[i][x][y];
575                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
576                        lbits |= 1 << i;
577                }
578                if(qualityMap[x][y] < bestQuality)
579                {
580                    ArrayList<Coord> ap = new ArrayList<>();
581
582                    for (int i = 0; i < pts.length && i < 63; ++i) {
583                        if((pbits & (1 << i)) != 0)
584                            ap.add(pts[i]);
585                    }
586                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
587                        if((lbits & (1 << i)) != 0)
588                            ap.add(lts[i - pts.length]);
589                    }
590
591                    if(ap.size() > 0) {
592                        bestQuality = qualityMap[x][y];
593                        bestPoints.clear();
594                        bestPoints.put(Coord.get(x, y), ap);
595                    }
596                }
597                else if(qualityMap[x][y] == bestQuality) {
598                    ArrayList<Coord> ap = new ArrayList<>();
599
600                    for (int i = 0; i < pts.length && i < 63; ++i) {
601                        if ((pbits & (1 << i)) != 0) {
602                            ap.add(pts[i]);
603                            ap.add(pts[i]);
604                            ap.add(pts[i]);
605                            ap.add(pts[i]);
606                        }
607                    }
608                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
609                        if ((lbits & (1 << i)) != 0)
610                            ap.add(lts[i - pts.length]);
611                    }
612
613                    if (ap.size() > 0) {
614                        bestPoints.put(Coord.get(x, y), ap);
615                    }
616                }
617            }
618        }
619
620        return bestPoints;
621    }
622
623/*
624    @Override
625    public ArrayList<ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
626        int totalTargets = targets.size() + 1;
627        int volume = (int)(rt.radius(1, 1, dungeon.length - 2, dungeon[0].length - 2) * radius * 2.1);
628        ArrayList<ArrayList<Coord>> locs = new ArrayList<ArrayList<Coord>>(totalTargets);
629        for(int i = 0; i < totalTargets; i++)
630        {
631            locs.add(new ArrayList<Coord>(volume));
632        }
633        if(totalTargets == 1)
634            return locs;
635
636        int ctr = 0;
637
638        boolean[][] tested = new boolean[dungeon.length][dungeon[0].length];
639        for (int x = 1; x < dungeon.length - 1; x += radius) {
640            for (int y = 1; y < dungeon[x].length - 1; y += radius) {
641
642                if(mayContainTarget(requiredExclusions, x, y))
643                    continue;
644                ctr = 0;
645                for(Coord tgt : targets)
646                {
647                    if(rt.radius(origin.x, origin.y, tgt.x, tgt.y) + rt.radius(end.x, end.y, tgt.x, tgt.y) -
648                        rt.radius(origin.x, origin.y, end.x, end.y) <= 3.0 + radius)
649                        ctr++;
650                }
651                if(ctr > 0)
652                    locs.get(totalTargets - ctr).add(Coord.get(x, y));
653            }
654        }
655        Coord it;
656        for(int t = 0; t < totalTargets - 1; t++)
657        {
658            if(locs.get(t).size() > 0) {
659                int numPoints = locs.get(t).size();
660                for (int i = 0; i < numPoints; i++) {
661                    it = locs.get(t).get(i);
662                    for (int x = Math.max(1, it.x - radius / 2); x < it.x + (radius + 1) / 2 && x < dungeon.length - 1; x++) {
663                        for (int y = Math.max(1, it.y - radius / 2); y <= it.y + (radius - 1) / 2 && y < dungeon[0].length - 1; y++)
664                        {
665                            if(tested[x][y])
666                                continue;
667                            tested[x][y] = true;
668
669                            if(mayContainTarget(requiredExclusions, x, y))
670                                continue;
671
672                            ctr = 0;
673                            for(Coord tgt : targets)
674                            {
675                                if(rt.radius(origin.x, origin.y, tgt.x, tgt.y) + rt.radius(end.x, end.y, tgt.x, tgt.y) -
676                                        rt.radius(origin.x, origin.y, end.x, end.y) <= 3.0 + radius)
677                                    ctr++;
678                            }
679                            if(ctr > 0)
680                                locs.get(totalTargets - ctr).add(Coord.get(x, y));
681                        }
682                    }
683                }
684            }
685        }
686        return locs;
687    }
688*/
689    @Override
690    public void setMap(char[][] map) {
691        dungeon = map;
692        dijkstra.resetMap();
693        dijkstra.clearGoals();
694    }
695
696    @Override
697    public LinkedHashMap<Coord, Double> findArea() {
698        double[][] dmap = initDijkstra();
699        dmap[origin.x][origin.y] = DijkstraMap.DARK;
700        dijkstra.resetMap();
701        dijkstra.clearGoals();
702        return AreaUtils.dijkstraToHashMap(dmap);
703    }
704
705    /**
706     * If you use FOVCache to pre-compute FOV maps for a level, you can share the speedup from using the cache with
707     * some AOE implementations that rely on FOV. Not all implementations need to actually make use of the cache, but
708     * those that use FOV for calculations should benefit. The cache parameter this receives should have completed its
709     * calculations, which can be confirmed by calling awaitCache(). Ideally, the FOVCache will have done its initial
710     * calculations in another thread while the previous level or menu was being displayed, and awaitCache() will only
711     * be a formality.
712     *
713     * @param cache The FOVCache for the current level; can be null to stop using the cache
714     */
715    @GwtIncompatible
716    @Override
717    public void setCache(FOVCache cache) {
718
719    }
720}