001package squidpony.squidai;
002
003import squidpony.annotation.GwtIncompatible;
004import squidpony.squidgrid.FOV;
005import squidpony.squidgrid.FOVCache;
006import squidpony.squidgrid.Radius;
007import squidpony.squidgrid.mapping.DungeonUtility;
008import squidpony.squidmath.Coord;
009
010import java.util.*;
011
012/**
013 * An AOE type that has a center and a radius, and uses shadowcasting to create a burst of rays from the center, out to
014 * the distance specified by radius. You can specify the RadiusType to Radius.DIAMOND for Manhattan distance,
015 * RADIUS.SQUARE for Chebyshev, or RADIUS.CIRCLE for Euclidean.
016 *
017 * This will produce doubles for its findArea() method which are equal to 1.0.
018 *
019 * This class uses squidpony.squidgrid.FOV to create its area of effect.
020 * Created by Tommy Ettinger on 7/13/2015.
021 */
022public class BurstAOE implements AOE {
023    private FOV fov;
024    private Coord center, origin;
025    private int radius;
026    private double[][] map;
027    private char[][] dungeon;
028    private Radius radiusType;
029    private Reach reach = new Reach(1, 1, Radius.SQUARE, null);
030
031    public BurstAOE(Coord center, int radius, Radius radiusType)
032    {
033        fov = new FOV(FOV.SHADOW);
034        this.center = center;
035        this.radius = radius;
036        this.radiusType = radiusType;
037    }
038    public BurstAOE(Coord center, int radius, Radius radiusType, int minRange, int maxRange)
039    {
040        fov = new FOV(FOV.SHADOW);
041        this.center = center;
042        this.radius = radius;
043        this.radiusType = radiusType;
044        reach.minDistance = minRange;
045        reach.maxDistance = maxRange;
046    }
047
048    public Coord getCenter() {
049        return center;
050    }
051
052    public void setCenter(Coord center) {
053
054        if (map != null && center.isWithin(map.length, map[0].length) &&
055                AreaUtils.verifyReach(reach, origin, center))
056        {
057            this.center = center;
058        }
059    }
060
061    public int getRadius() {
062        return radius;
063    }
064
065    public void setRadius(int radius) {
066        this.radius = radius;
067    }
068
069    public Radius getRadiusType() {
070        return radiusType;
071    }
072
073    public void setRadiusType(Radius radiusType) {
074        this.radiusType = radiusType;
075    }
076
077    @Override
078    public void shift(Coord aim) {
079        setCenter(aim);
080    }
081
082    @Override
083    public boolean mayContainTarget(Set<Coord> targets) {
084        for (Coord p : targets)
085        {
086            if(radiusType.radius(center.x, center.y, p.x, p.y) <= radius)
087                return true;
088        }
089        return false;
090    }
091
092    @Override
093    public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
094        if(targets == null)
095            return new LinkedHashMap<>();
096        if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>();
097
098        //requiredExclusions.remove(origin);
099        int totalTargets = targets.size();
100        LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8);
101
102        if(totalTargets == 0)
103            return bestPoints;
104
105        if(radius == 0)
106        {
107            for(Coord p : targets)
108            {
109                ArrayList<Coord> ap = new ArrayList<>();
110                ap.add(p);
111                bestPoints.put(p, ap);
112            }
113            return bestPoints;
114        }
115        Coord[] ts = targets.toArray(new Coord[targets.size()]);
116        Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]);
117        Coord t = exs[0];
118
119        double[][][] compositeMap = new double[ts.length][dungeon.length][dungeon[0].length];
120
121        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length];
122        for (int i = 0; i < dungeon.length; i++) {
123            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
124        }
125        double[][] tmpfov;
126        Coord tempPt = Coord.get(0, 0);
127        for (int i = 0; i < exs.length; ++i) {
128            t = exs[i];
129
130            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
131            for (int x = 0; x < dungeon.length; x++) {
132                for (int y = 0; y < dungeon[x].length; y++) {
133                    tempPt = Coord.get(x, y);
134                    dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
135                }
136            }
137        }
138
139        t = ts[0];
140
141        DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN;
142        if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV;
143        else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN;
144
145        for (int i = 0; i < ts.length; ++i) {
146            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
147
148            t = ts[i];
149            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
150
151            double dist = 0.0;
152            for (int x = 0; x < dungeon.length; x++) {
153                for (int y = 0; y < dungeon[x].length; y++) {
154                    if (tmpfov[x][y] > 0.0) {
155                        dist = reach.metric.radius(origin.x, origin.y, x, y);
156                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
157                            compositeMap[i][x][y] = dm.physicalMap[x][y];
158                        else
159                            compositeMap[i][x][y] = DijkstraMap.WALL;
160                    }
161                    else compositeMap[i][x][y] = DijkstraMap.WALL;
162                }
163            }
164            if(compositeMap[i][ts[i].x][ts[i].y] > DijkstraMap.FLOOR)
165            {
166                for (int x = 0; x < dungeon.length; x++) {
167                    Arrays.fill(compositeMap[i][x], 99999.0);
168                }
169                continue;
170            }
171
172
173            dm.initialize(compositeMap[i]);
174            dm.setGoal(t);
175            dm.scan(null);
176            for (int x = 0; x < dungeon.length; x++) {
177                for (int y = 0; y < dungeon[x].length; y++) {
178                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 99999.0;
179                }
180            }
181        }
182        double bestQuality = 99999 * ts.length;
183        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
184        for (int x = 0; x < qualityMap.length; x++) {
185            for (int y = 0; y < qualityMap[x].length; y++) {
186                qualityMap[x][y] = 0.0;
187                long bits = 0;
188                for (int i = 0; i < ts.length; ++i) {
189                    qualityMap[x][y] += compositeMap[i][x][y];
190                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
191                        bits |= 1 << i;
192                }
193                if(qualityMap[x][y] < bestQuality)
194                {
195                    ArrayList<Coord> ap = new ArrayList<>();
196
197                    for (int i = 0; i < ts.length && i < 63; ++i) {
198                        if((bits & (1 << i)) != 0)
199                            ap.add(ts[i]);
200                    }
201
202                    if(ap.size() > 0) {
203                        bestQuality = qualityMap[x][y];
204                        bestPoints.clear();
205                        bestPoints.put(Coord.get(x, y), ap);
206                    }                }
207                else if(qualityMap[x][y] == bestQuality)
208                {
209                    ArrayList<Coord> ap = new ArrayList<>();
210
211                    for (int i = 0; i < ts.length && i < 63; ++i) {
212                        if((bits & (1 << i)) != 0)
213                            ap.add(ts[i]);
214                    }
215
216                    if (ap.size() > 0) {
217                        bestPoints.put(Coord.get(x, y), ap);
218                    }
219                }
220            }
221        }
222
223        return bestPoints;
224    }
225
226
227    @Override
228    public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> priorityTargets, Set<Coord> lesserTargets, Set<Coord> requiredExclusions) {
229        if(priorityTargets == null)
230            return idealLocations(lesserTargets, requiredExclusions);
231        if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>();
232
233        //requiredExclusions.remove(origin);
234        int totalTargets = priorityTargets.size() + lesserTargets.size();
235        LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8);
236
237        if(totalTargets == 0)
238            return bestPoints;
239
240        if(radius == 0)
241        {
242            for(Coord p : priorityTargets)
243            {
244                ArrayList<Coord> ap = new ArrayList<>();
245                ap.add(p);
246                bestPoints.put(p, ap);
247            }
248            return bestPoints;
249        }
250        Coord[] pts = priorityTargets.toArray(new Coord[priorityTargets.size()]);
251        Coord[] lts = lesserTargets.toArray(new Coord[lesserTargets.size()]);
252        Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]);
253        Coord t = exs[0];
254
255        double[][][] compositeMap = new double[totalTargets][dungeon.length][dungeon[0].length];
256
257        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length],
258                dungeonPriorities = new char[dungeon.length][dungeon[0].length];
259        for (int i = 0; i < dungeon.length; i++) {
260            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
261            Arrays.fill(dungeonPriorities[i], '#');
262        }
263        double[][] tmpfov;
264        Coord tempPt = Coord.get(0, 0);
265        for (int i = 0; i < exs.length; ++i) {
266            t = exs[i];
267            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
268            for (int x = 0; x < dungeon.length; x++) {
269                for (int y = 0; y < dungeon[x].length; y++) {
270                    tempPt = Coord.get(x, y);
271                    dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
272                }
273            }
274        }
275
276        t = pts[0];
277
278        DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN;
279        if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV;
280        else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN;
281
282        for (int i = 0; i < pts.length; ++i) {
283            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
284            t = pts[i];
285
286            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
287
288            double dist = 0.0;
289            for (int x = 0; x < dungeon.length; x++) {
290                for (int y = 0; y < dungeon[x].length; y++) {
291                    if (tmpfov[x][y] > 0.0){
292                        dist = reach.metric.radius(origin.x, origin.y, x, y);
293                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) {
294                            compositeMap[i][x][y] = dm.physicalMap[x][y];
295                            dungeonPriorities[x][y] = dungeon[x][y];
296                        }
297                        else
298                            compositeMap[i][x][y] = DijkstraMap.WALL;
299                    }
300                    else compositeMap[i][x][y] = DijkstraMap.WALL;
301                }
302            }
303            if(compositeMap[i][t.x][t.y] > DijkstraMap.FLOOR)
304            {
305                for (int x = 0; x < dungeon.length; x++) {
306                    Arrays.fill(compositeMap[i][x], 399999.0);
307                }
308                continue;
309            }
310
311
312            dm.initialize(compositeMap[i]);
313            dm.setGoal(t);
314            dm.scan(null);
315            for (int x = 0; x < dungeon.length; x++) {
316                for (int y = 0; y < dungeon[x].length; y++) {
317                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 399999.0;
318                }
319            }
320            dm.resetMap();
321            dm.clearGoals();
322        }
323
324        t = lts[0];
325
326        for (int i = pts.length; i < totalTargets; ++i) {
327            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
328            t = lts[i - pts.length];
329
330            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
331
332            double dist = 0.0;
333            for (int x = 0; x < dungeon.length; x++) {
334                for (int y = 0; y < dungeon[x].length; y++) {
335                    if (tmpfov[x][y] > 0.0){
336                        dist = reach.metric.radius(origin.x, origin.y, x, y);
337                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
338                            compositeMap[i][x][y] = dm.physicalMap[x][y];
339                        else
340                            compositeMap[i][x][y] = DijkstraMap.WALL;
341                    }
342                    else compositeMap[i][x][y] = DijkstraMap.WALL;
343                }
344            }
345            if(compositeMap[i][t.x][t.y] > DijkstraMap.FLOOR)
346            {
347                for (int x = 0; x < dungeon.length; x++)
348                {
349                    Arrays.fill(compositeMap[i][x], 99999.0);
350                }
351                continue;
352            }
353
354
355            dm.initialize(compositeMap[i]);
356            dm.setGoal(t);
357            dm.scan(null);
358            for (int x = 0; x < dungeon.length; x++) {
359                for (int y = 0; y < dungeon[x].length; y++) {
360                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!' && dungeonPriorities[x][y] != '#') ? dm.gradientMap[x][y] : 99999.0;
361                }
362            }
363            dm.resetMap();
364            dm.clearGoals();
365        }
366        double bestQuality = 99999 * lts.length + 399999 * pts.length;
367        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
368        for (int x = 0; x < qualityMap.length; x++) {
369            for (int y = 0; y < qualityMap[x].length; y++) {
370                qualityMap[x][y] = 0.0;
371                long pbits = 0, lbits = 0;
372                for (int i = 0; i < pts.length; ++i) {
373                    qualityMap[x][y] += compositeMap[i][x][y];
374                    if(compositeMap[i][x][y] < 399999.0 && i < 63)
375                        pbits |= 1 << i;
376                }
377                for (int i = pts.length; i < totalTargets; ++i) {
378                    qualityMap[x][y] += compositeMap[i][x][y];
379                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
380                        lbits |= 1 << i;
381                }
382                if(qualityMap[x][y] < bestQuality)
383                {
384                    ArrayList<Coord> ap = new ArrayList<>();
385
386                    for (int i = 0; i < pts.length && i < 63; ++i) {
387                        if((pbits & (1 << i)) != 0)
388                            ap.add(pts[i]);
389                    }
390                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
391                        if((lbits & (1 << i)) != 0)
392                            ap.add(lts[i - pts.length]);
393                    }
394
395                    if(ap.size() > 0) {
396                        bestQuality = qualityMap[x][y];
397                        bestPoints.clear();
398                        bestPoints.put(Coord.get(x, y), ap);
399                    }
400                }
401                else if(qualityMap[x][y] == bestQuality)
402                {
403                    ArrayList<Coord> ap = new ArrayList<>();
404
405                    for (int i = 0; i < pts.length && i < 63; ++i) {
406                        if ((pbits & (1 << i)) != 0) {
407                            ap.add(pts[i]);
408                            ap.add(pts[i]);
409                            ap.add(pts[i]);
410                            ap.add(pts[i]);
411                        }
412                    }
413                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
414                        if((lbits & (1 << i)) != 0)
415                            ap.add(lts[i - pts.length]);
416                    }
417
418                    if (ap.size() > 0) {
419                        bestPoints.put(Coord.get(x, y), ap);
420                    }
421                }
422            }
423        }
424
425        return bestPoints;
426    }
427
428    /*
429    @Override
430    public ArrayList<ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
431        int totalTargets = targets.size() + 1;
432        int maxEffect = (int)radiusType.volume2D(radius);
433        ArrayList<ArrayList<Coord>> locs = new ArrayList<ArrayList<Coord>>(totalTargets);
434
435        for(int i = 0; i < totalTargets; i++)
436        {
437            locs.add(new ArrayList<Coord>(maxEffect));
438        }
439        if(totalTargets == 1)
440            return locs;
441
442        int ctr = 0;
443        if(radius < 1)
444        {
445            locs.get(totalTargets - 2).addAll(targets);
446            return locs;
447        }
448
449        boolean[][] tested = new boolean[dungeon.length][dungeon[0].length];
450        for (int x = 1; x < dungeon.length - 1; x += radius) {
451            BY_POINT:
452            for (int y = 1; y < dungeon[x].length - 1; y += radius) {
453                for(Coord ex : requiredExclusions)
454                {
455                    if(radiusType.radius(x, y, ex.x, ex.y) <= radius)
456                        continue BY_POINT;
457                }
458                ctr = 0;
459                for(Coord tgt : targets)
460                {
461                    if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius)
462                        ctr++;
463                }
464                if(ctr > 0)
465                    locs.get(totalTargets - ctr).add(Coord.get(x, y));
466            }
467        }
468        Coord it;
469        for(int t = 0; t < totalTargets - 1; t++)
470        {
471            if(locs.get(t).size() > 0) {
472                int numPoints = locs.get(t).size();
473                for (int i = 0; i < numPoints; i++) {
474                    it = locs.get(t).get(i);
475                    for (int x = Math.max(1, it.x - radius / 2); x < it.x + (radius + 1) / 2 && x < dungeon.length - 1; x++) {
476                        BY_POINT:
477                        for (int y = Math.max(1, it.y - radius / 2); y <= it.y + (radius - 1) / 2 && y < dungeon[0].length - 1; y++)
478                        {
479                            if(tested[x][y])
480                                continue;
481                            tested[x][y] = true;
482
483                            for(Coord ex : requiredExclusions)
484                            {
485                                if(radiusType.radius(x, y, ex.x, ex.y) <= radius)
486                                    continue BY_POINT;
487                            }
488
489                            ctr = 0;
490                            for(Coord tgt : targets)
491                            {
492                                if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius)
493                                    ctr++;
494                            }
495                            if(ctr > 0)
496                                locs.get(totalTargets - ctr).add(Coord.get(x, y));
497                        }
498                    }
499                }
500            }
501        }
502        return locs;
503    }
504*/
505    @Override
506    public void setMap(char[][] map) {
507        this.map = DungeonUtility.generateResistances(map);
508        dungeon = map;
509    }
510
511    @Override
512    public LinkedHashMap<Coord, Double> findArea() {
513        return AreaUtils.arrayToHashMap(fov.calculateFOV(null, center.x, center.y, radius, radiusType));
514    }
515
516
517    @Override
518    public Coord getOrigin() {
519        return origin;
520    }
521
522    @Override
523    public void setOrigin(Coord origin) {
524        this.origin = origin;
525
526    }
527
528    @Override
529    public AimLimit getLimitType() {
530        return reach.limit;
531    }
532
533    @Override
534    public int getMinRange() {
535        return reach.minDistance;
536    }
537
538    @Override
539    public int getMaxRange() {
540        return reach.maxDistance;
541    }
542
543    @Override
544    public Radius getMetric() {
545        return reach.metric;
546    }
547
548    /**
549     * Gets the same values returned by getLimitType(), getMinRange(), getMaxRange(), and getMetric() bundled into one
550     * Reach object.
551     *
552     * @return a non-null Reach object.
553     */
554    @Override
555    public Reach getReach() {
556        return reach;
557    }
558
559    @Override
560    public void setLimitType(AimLimit limitType) {
561        reach.limit = limitType;
562
563    }
564
565    @Override
566    public void setMinRange(int minRange) {
567        reach.minDistance = minRange;
568    }
569
570    @Override
571    public void setMaxRange(int maxRange) {
572        reach.maxDistance = maxRange;
573
574    }
575
576    @Override
577    public void setMetric(Radius metric) {
578        reach.metric = metric;
579    }
580
581    /**
582     * Sets the same values as setLimitType(), setMinRange(), setMaxRange(), and setMetric() using one Reach object.
583     *
584     * @param reach a non-null Reach object.
585     */
586    @Override
587    public void setReach(Reach reach) {
588        if(reach != null)
589            this.reach = reach;
590    }
591
592    /**
593     * If you use FOVCache to pre-compute FOV maps for a level, you can share the speedup from using the cache with
594     * some AOE implementations that rely on FOV. Not all implementations need to actually make use of the cache, but
595     * those that use FOV for calculations should benefit. The cache parameter this receives should have completed its
596     * calculations, which can be confirmed by calling awaitCache(). Ideally, the FOVCache will have done its initial
597     * calculations in another thread while the previous level or menu was being displayed, and awaitCache() will only
598     * be a formality.
599     *
600     * @param cache The FOVCache for the current level; can be null to stop using the cache
601     */
602    @GwtIncompatible
603    @Override
604    public void setCache(FOVCache cache) {
605        fov = cache;
606    }
607
608}