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