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 will blast outward and somewhat around corners/obstacles, 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 greater than 0.0 and less than or 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 BlastAOE implements AOE {
023    private FOV fov;
024    private Coord center, origin = null;
025    private int radius;
026    private double[][] map;
027    private char[][] dungeon;
028    private Radius radiusType;
029    
030    private Reach reach = new Reach(1, 1, Radius.SQUARE, null);
031
032    public BlastAOE(Coord center, int radius, Radius radiusType)
033    {
034        fov = new FOV(FOV.RIPPLE_LOOSE);
035        this.center = center;
036        this.radius = radius;
037        this.radiusType = radiusType;
038    }
039    public BlastAOE(Coord center, int radius, Radius radiusType, int minRange, int maxRange)
040    {
041        fov = new FOV(FOV.RIPPLE_LOOSE);
042        this.center = center;
043        this.radius = radius;
044        this.radiusType = radiusType;
045        reach.minDistance = minRange;
046        reach.maxDistance = maxRange;
047    }
048
049    public Coord getCenter() {
050        return center;
051    }
052
053    public void setCenter(Coord center) {
054
055        if (map != null && center.isWithin(map.length, map[0].length) &&
056                AreaUtils.verifyReach(reach, origin, center))
057        {
058            this.center = center;
059        }
060    }
061
062    public int getRadius() {
063        return radius;
064    }
065
066    public void setRadius(int radius) {
067        this.radius = radius;
068    }
069
070    public Radius getRadiusType() {
071        return radiusType;
072    }
073
074    public void setRadiusType(Radius radiusType) {
075        this.radiusType = radiusType;
076    }
077
078    @Override
079    public void shift(Coord aim) {
080        setCenter(aim);
081    }
082
083    @Override
084    public boolean mayContainTarget(Set<Coord> targets) {
085        for (Coord p : targets)
086        {
087            if(radiusType.radius(center.x, center.y, p.x, p.y) <= radius)
088                return true;
089        }
090        return false;
091    }
092
093    @Override
094    public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
095        if(targets == null)
096            return new LinkedHashMap<>();
097        if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>();
098
099        //requiredExclusions.remove(origin);
100        int totalTargets = targets.size();
101        LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8);
102
103        if(totalTargets == 0)
104            return bestPoints;
105
106        if(radius == 0)
107        {
108            for(Coord p : targets)
109            {
110                ArrayList<Coord> ap = new ArrayList<>();
111                ap.add(p);
112                bestPoints.put(p, ap);
113            }
114            return bestPoints;
115        }
116        Coord[] ts = targets.toArray(new Coord[targets.size()]);
117        Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]);
118        Coord t = exs[0];
119
120        double[][][] compositeMap = new double[ts.length][dungeon.length][dungeon[0].length];
121
122        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length];
123        for (int i = 0; i < dungeon.length; i++) {
124            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
125        }
126        double[][] tmpfov;
127        Coord tempPt = Coord.get(0, 0);
128        for (int i = 0; i < exs.length; ++i) {
129            t = exs[i];
130
131            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
132
133            for (int x = 0; x < dungeon.length; x++) {
134                for (int y = 0; y < dungeon[x].length; y++) {
135                    tempPt = Coord.get(x, y);
136                    dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
137                }
138            }
139        }
140
141        t = ts[0];
142
143        DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN;
144        if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV;
145        else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN;
146
147        for (int i = 0; i < ts.length; i++) {
148            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
149
150            t = ts[i];
151
152            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
153
154            for (int x = 0; x < dungeon.length; x++) {
155                for (int y = 0; y < dungeon[x].length; y++) {
156                    compositeMap[i][x][y] = (tmpfov[x][y] > 0.0) ? dm.physicalMap[x][y] : DijkstraMap.WALL;
157                }
158            }
159
160
161            double dist = 0.0;
162            for (int x = 0; x < dungeon.length; x++) {
163                for (int y = 0; y < dungeon[x].length; y++) {
164                    if (tmpfov[x][y] > 0.0){
165                        dist = reach.metric.radius(origin.x, origin.y, x, y);
166                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
167                            compositeMap[i][x][y] = dm.physicalMap[x][y];
168                        else
169                            compositeMap[i][x][y] = DijkstraMap.WALL;
170                    }
171                    else compositeMap[i][x][y] = DijkstraMap.WALL;
172                }
173            }
174            if(compositeMap[i][ts[i].x][ts[i].y] > DijkstraMap.FLOOR)
175            {
176                for (int x = 0; x < dungeon.length; x++) {
177                    Arrays.fill(compositeMap[i][x], 99999.0);
178                }
179                continue;
180            }
181
182
183            dm.initialize(compositeMap[i]);
184            dm.setGoal(t);
185            dm.scan(null);
186            for (int x = 0; x < dungeon.length; x++) {
187                for (int y = 0; y < dungeon[x].length; y++) {
188                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 99999.0;
189                }
190            }
191        }
192        double bestQuality = 99999 * ts.length;
193        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
194        for (int x = 0; x < qualityMap.length; x++) {
195            for (int y = 0; y < qualityMap[x].length; y++) {
196                qualityMap[x][y] = 0.0;
197                long bits = 0;
198                for (int i = 0; i < ts.length; i++) {
199                    qualityMap[x][y] += compositeMap[i][x][y];
200                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
201                        bits |= 1 << i;
202                }
203                if(qualityMap[x][y] < bestQuality)
204                {
205                    ArrayList<Coord> ap = new ArrayList<>();
206
207                    for (int i = 0; i < ts.length && i < 63; ++i) {
208                        if((bits & (1 << i)) != 0)
209                            ap.add(ts[i]);
210                    }
211                    if(ap.size() > 0)
212                    {
213                        bestQuality = qualityMap[x][y];
214                        bestPoints.clear();
215                        bestPoints.put(Coord.get(x, y), ap);
216                    }
217                }
218                else if(qualityMap[x][y] == bestQuality) {
219                    ArrayList<Coord> ap = new ArrayList<>();
220
221                    for (int i = 0; i < ts.length && i < 63; ++i) {
222                        if ((bits & (1 << i)) != 0)
223                            ap.add(ts[i]);
224                    }
225                    if (ap.size() > 0) {
226                        bestPoints.put(Coord.get(x, y), ap);
227                    }
228                }
229            }
230        }
231
232        return bestPoints;
233    }
234
235    @Override
236    public LinkedHashMap<Coord, ArrayList<Coord>> idealLocations(Set<Coord> priorityTargets, Set<Coord> lesserTargets, Set<Coord> requiredExclusions) {
237        if(priorityTargets == null)
238            return idealLocations(lesserTargets, requiredExclusions);
239        if(requiredExclusions == null) requiredExclusions = new LinkedHashSet<>();
240
241        //requiredExclusions.remove(origin);
242        int totalTargets = priorityTargets.size() + lesserTargets.size();
243        LinkedHashMap<Coord, ArrayList<Coord>> bestPoints = new LinkedHashMap<>(totalTargets * 8);
244
245        if(totalTargets == 0)
246            return bestPoints;
247
248        if(radius == 0)
249        {
250            for(Coord p : priorityTargets)
251            {
252                ArrayList<Coord> ap = new ArrayList<>();
253                ap.add(p);
254                bestPoints.put(p, ap);
255            }
256            return bestPoints;
257        }
258        Coord[] pts = priorityTargets.toArray(new Coord[priorityTargets.size()]);
259        Coord[] lts = lesserTargets.toArray(new Coord[lesserTargets.size()]);
260        Coord[] exs = requiredExclusions.toArray(new Coord[requiredExclusions.size()]);
261        Coord t = exs[0];
262
263        double[][][] compositeMap = new double[totalTargets][dungeon.length][dungeon[0].length];
264
265        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length],
266                dungeonPriorities = new char[dungeon.length][dungeon[0].length];
267        for (int i = 0; i < dungeon.length; i++) {
268            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
269            Arrays.fill(dungeonPriorities[i], '#');
270        }
271        double[][] tmpfov;
272        Coord tempPt = Coord.get(0, 0);
273        for (int i = 0; i < exs.length; ++i) {
274            t = exs[i];
275
276            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
277            for (int x = 0; x < dungeon.length; x++) {
278                for (int y = 0; y < dungeon[x].length; y++) {
279                    tempPt = Coord.get(x, y);
280                    dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
281                }
282            }
283        }
284
285        t = pts[0];
286
287        DijkstraMap.Measurement dmm = DijkstraMap.Measurement.MANHATTAN;
288        if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = DijkstraMap.Measurement.CHEBYSHEV;
289        else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = DijkstraMap.Measurement.EUCLIDEAN;
290
291        for (int i = 0; i < pts.length; ++i) {
292            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
293
294            t = pts[i];
295
296            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
297
298            double dist = 0.0;
299            for (int x = 0; x < dungeon.length; x++) {
300                for (int y = 0; y < dungeon[x].length; y++) {
301                    if (tmpfov[x][y] > 0.0){
302                        dist = reach.metric.radius(origin.x, origin.y, x, y);
303                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) {
304                            compositeMap[i][x][y] = dm.physicalMap[x][y];
305                            dungeonPriorities[x][y] = dungeon[x][y];
306                        }
307                        else
308                            compositeMap[i][x][y] = DijkstraMap.WALL;
309                    }
310                    else compositeMap[i][x][y] = DijkstraMap.WALL;
311                }
312            }
313            if(compositeMap[i][pts[i].x][pts[i].y] > DijkstraMap.FLOOR)
314            {
315                for (int x = 0; x < dungeon.length; x++) {
316                    Arrays.fill(compositeMap[i][x], 399999.0);
317                }
318                continue;
319            }
320
321            dm.initialize(compositeMap[i]);
322            dm.setGoal(t);
323            dm.scan(null);
324            for (int x = 0; x < dungeon.length; x++) {
325                for (int y = 0; y < dungeon[x].length; y++) {
326                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 399999.0;
327                }
328            }
329        }
330
331        t = lts[0];
332
333        for (int i = pts.length; i < totalTargets; ++i) {
334            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
335
336            t = lts[i - pts.length];
337
338            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
339
340            double dist = 0.0;
341            for (int x = 0; x < dungeon.length; x++) {
342                for (int y = 0; y < dungeon[x].length; y++) {
343                    if (tmpfov[x][y] > 0.0){
344                        dist = reach.metric.radius(origin.x, origin.y, x, y);
345                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
346                            compositeMap[i][x][y] = dm.physicalMap[x][y];
347                        else
348                            compositeMap[i][x][y] = DijkstraMap.WALL;
349                    }
350                    else compositeMap[i][x][y] = DijkstraMap.WALL;
351                }
352            }
353            if(compositeMap[i][lts[i - pts.length].x][lts[i - pts.length].y] > DijkstraMap.FLOOR)
354            {
355                for (int x = 0; x < dungeon.length; x++)
356                {
357                    Arrays.fill(compositeMap[i][x], 99999.0);
358                }
359                continue;
360            }
361
362            dm.initialize(compositeMap[i]);
363            dm.setGoal(t);
364            dm.scan(null);
365            for (int x = 0; x < dungeon.length; x++) {
366                for (int y = 0; y < dungeon[x].length; y++) {
367                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!' && dungeonPriorities[x][y] != '#') ? dm.gradientMap[x][y] : 99999.0;
368                }
369            }
370        }
371        double bestQuality = 99999 * lts.length + 399999 * pts.length;
372        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
373        for (int x = 0; x < qualityMap.length; x++) {
374            for (int y = 0; y < qualityMap[x].length; y++) {
375                qualityMap[x][y] = 0.0;
376                long pbits = 0, lbits = 0;
377                for (int i = 0; i < pts.length; ++i) {
378                    qualityMap[x][y] += compositeMap[i][x][y];
379                    if(compositeMap[i][x][y] < 399999.0 && i < 63)
380                        pbits |= 1 << i;
381                }
382                for (int i = pts.length; i < totalTargets; ++i) {
383                    qualityMap[x][y] += compositeMap[i][x][y];
384                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
385                        lbits |= 1 << i;
386                }
387                if(qualityMap[x][y] < bestQuality)
388                {
389                    ArrayList<Coord> ap = new ArrayList<>();
390
391                    for (int i = 0; i < pts.length && i < 63; ++i) {
392                        if((pbits & (1 << i)) != 0)
393                            ap.add(pts[i]);
394                    }
395                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
396                        if((lbits & (1 << i)) != 0)
397                            ap.add(lts[i - pts.length]);
398                    }
399                    if(ap.size() > 0) {
400                        bestQuality = qualityMap[x][y];
401                        bestPoints.clear();
402                        bestPoints.put(Coord.get(x, y), ap);
403                    }
404                }
405                else if(qualityMap[x][y] == bestQuality) {
406                    ArrayList<Coord> ap = new ArrayList<>();
407
408                    for (int i = 0; i < pts.length && i < 63; ++i) {
409                        if ((pbits & (1 << i)) != 0) {
410                            ap.add(pts[i]);
411                            ap.add(pts[i]);
412                            ap.add(pts[i]);
413                            ap.add(pts[i]);
414                        }
415                    }
416                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
417                        if ((lbits & (1 << i)) != 0)
418                            ap.add(lts[i - pts.length]);
419                    }
420                    if (ap.size() > 0) {
421                        bestPoints.put(Coord.get(x, y), ap);
422                    }
423                }
424            }
425        }
426
427        return bestPoints;
428    }
429
430    /*
431    @Override
432    public ArrayList<ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
433        int totalTargets = targets.size() + 1;
434        int maxEffect = (int)radiusType.volume2D(radius);
435        ArrayList<ArrayList<Coord>> locs = new ArrayList<ArrayList<Coord>>(totalTargets);
436
437        for(int i = 0; i < totalTargets; i++)
438        {
439            locs.add(new ArrayList<Coord>(maxEffect));
440        }
441        if(totalTargets == 1)
442            return locs;
443        int ctr = 0;
444        if(radius < 1)
445        {
446            locs.get(totalTargets - 2).addAll(targets);
447            return locs;
448        }
449
450        boolean[][] tested = new boolean[dungeon.length][dungeon[0].length];
451        for (int x = 1; x < dungeon.length - 1; x += radius) {
452            BY_POINT:
453            for (int y = 1; y < dungeon[x].length - 1; y += radius) {
454                for(Coord ex : requiredExclusions)
455                {
456                    if(radiusType.radius(x, y, ex.x, ex.y) <= radius)
457                        continue BY_POINT;
458                }
459                ctr = 0;
460                for(Coord tgt : targets)
461                {
462                    if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius)
463                        ctr++;
464                }
465                if(ctr > 0)
466                    locs.get(totalTargets - ctr).add(Coord.get(x, y));
467            }
468        }
469        Coord it;
470        for(int t = 0; t < totalTargets - 1; t++)
471        {
472            if(locs.get(t).size() > 0) {
473                int numPoints = locs.get(t).size();
474                for (int i = 0; i < numPoints; i++) {
475                    it = locs.get(t).get(i);
476                    for (int x = Math.max(1, it.x - radius / 2); x < it.x + (radius + 1) / 2 && x < dungeon.length - 1; x++) {
477                        BY_POINT:
478                        for (int y = Math.max(1, it.y - radius / 2); y <= it.y + (radius - 1) / 2 && y < dungeon[0].length - 1; y++)
479                        {
480                            if(tested[x][y])
481                                continue;
482                            tested[x][y] = true;
483
484                            for(Coord ex : requiredExclusions)
485                            {
486                                if(radiusType.radius(x, y, ex.x, ex.y) <= radius)
487                                    continue BY_POINT;
488                            }
489
490                            ctr = 0;
491                            for(Coord tgt : targets)
492                            {
493                                if(radiusType.radius(x, y, tgt.x, tgt.y) <= radius)
494                                    ctr++;
495                            }
496                            if(ctr > 0)
497                                locs.get(totalTargets - ctr).add(Coord.get(x, y));
498                        }
499                    }
500                }
501            }
502        }
503        return locs;
504    }
505*/
506    @Override
507    public void setMap(char[][] map) {
508        this.map = DungeonUtility.generateResistances(map);
509        dungeon = map;
510    }
511
512    @Override
513    public LinkedHashMap<Coord, Double> findArea() {
514        return AreaUtils.arrayToHashMap(fov.calculateFOV(map, center.x, center.y, radius, radiusType));
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}