Source code

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