001package squidpony.squidai;
002
003import squidpony.squidgrid.FOV;
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;
015
016/**
017 * An AOE type that has a center and a radius, and will blast outward and somewhat around corners/obstacles, out to
018 * the distance specified by radius. You can specify the radiusType to Radius.DIAMOND for Manhattan distance,
019 * RADIUS.SQUARE for Chebyshev, or RADIUS.CIRCLE for Euclidean.
020 *
021 * This will produce doubles for its {@link #findArea()} method that are greater than 0.0 and less than or equal to 1.0.
022 *
023 * This class uses {@link FOV} to create its area of effect.
024 * Created by Tommy Ettinger on 7/13/2015.
025 */
026public class BlastAOE implements AOE, Serializable {
027    private static final long serialVersionUID = 2L;
028    private FOV fov;
029    private Coord center, origin;
030    private int radius;
031    private double[][] map;
032    private char[][] dungeon;
033    private Radius radiusType;
034    
035    private Reach reach = new Reach(1, 1, Radius.SQUARE, AimLimit.FREE);
036
037    public BlastAOE(Coord center, int radius, Radius radiusType)
038    {
039        fov = new FOV(FOV.RIPPLE_LOOSE);
040        this.center = center;
041        this.radius = radius;
042        this.radiusType = radiusType;
043    }
044    public BlastAOE(Coord center, int radius, Radius radiusType, int minRange, int maxRange)
045    {
046        fov = new FOV(FOV.RIPPLE_LOOSE);
047        this.center = center;
048        this.radius = radius;
049        this.radiusType = radiusType;
050        reach.minDistance = minRange;
051        reach.maxDistance = maxRange;
052    }
053
054    public Coord getCenter() {
055        return center;
056    }
057
058    public void setCenter(Coord center) {
059
060        if (map != null && center.isWithin(map.length, map[0].length) &&
061                AreaUtils.verifyReach(reach, origin, center))
062        {
063            this.center = center;
064        }
065    }
066
067    public int getRadius() {
068        return radius;
069    }
070
071    public void setRadius(int radius) {
072        this.radius = radius;
073    }
074
075    public Radius getRadiusType() {
076        return radiusType;
077    }
078
079    public void setRadiusType(Radius radiusType) {
080        this.radiusType = radiusType;
081    }
082
083    @Override
084    public void shift(Coord aim) {
085        setCenter(aim);
086    }
087
088    @Override
089    public boolean mayContainTarget(Collection<Coord> targets) {
090        for (Coord p : targets)
091        {
092            if(radiusType.radius(center.x, center.y, p.x, p.y) <= radius)
093                return true;
094        }
095        return false;
096    }
097
098    @Override
099    public OrderedMap<Coord, ArrayList<Coord>> idealLocations(Collection<Coord> targets, Collection<Coord> requiredExclusions) {
100        if(targets == null)
101            return new OrderedMap<>();
102        if(requiredExclusions == null) requiredExclusions = new OrderedSet<>();
103
104        //requiredExclusions.remove(origin);
105        int totalTargets = targets.size();
106        OrderedMap<Coord, ArrayList<Coord>> bestPoints = new OrderedMap<>(totalTargets * 8);
107
108        if(totalTargets == 0)
109            return bestPoints;
110
111        if(radius == 0)
112        {
113            for(Coord p : targets)
114            {
115                ArrayList<Coord> ap = new ArrayList<>();
116                ap.add(p);
117                bestPoints.put(p, ap);
118            }
119            return bestPoints;
120        }
121        Coord[] ts = targets.toArray(new Coord[0]);
122        Coord[] exs = requiredExclusions.toArray(new Coord[0]);
123        Coord t;
124
125        double[][][] compositeMap = new double[ts.length][dungeon.length][dungeon[0].length];
126
127        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length];
128        for (int i = 0; i < dungeon.length; i++) {
129            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
130        }
131        double[][] tmpfov;
132        Coord tempPt;
133        for (int i = 0; i < exs.length; ++i) {
134            t = exs[i];
135
136            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
137
138            for (int x = 0; x < dungeon.length; x++) {
139                for (int y = 0; y < dungeon[x].length; y++) {
140                    tempPt = Coord.get(x, y);
141                    dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
142                }
143            }
144        }
145
146        Measurement dmm = Measurement.MANHATTAN;
147        if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = Measurement.CHEBYSHEV;
148        else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = Measurement.EUCLIDEAN;
149
150        for (int i = 0; i < ts.length; i++) {
151            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
152
153            t = ts[i];
154
155            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
156
157            for (int x = 0; x < dungeon.length; x++) {
158                for (int y = 0; y < dungeon[x].length; y++) {
159                    compositeMap[i][x][y] = (tmpfov[x][y] > 0.0) ? dm.physicalMap[x][y] : DijkstraMap.WALL;
160                }
161            }
162
163
164            double dist;
165            for (int x = 0; x < dungeon.length; x++) {
166                for (int y = 0; y < dungeon[x].length; y++) {
167                    if (tmpfov[x][y] > 0.0){
168                        dist = reach.metric.radius(origin.x, origin.y, x, y);
169                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
170                            compositeMap[i][x][y] = dm.physicalMap[x][y];
171                        else
172                            compositeMap[i][x][y] = DijkstraMap.WALL;
173                    }
174                    else compositeMap[i][x][y] = DijkstraMap.WALL;
175                }
176            }
177            if(compositeMap[i][ts[i].x][ts[i].y] > DijkstraMap.FLOOR)
178            {
179                for (int x = 0; x < dungeon.length; x++) {
180                    Arrays.fill(compositeMap[i][x], 99999.0);
181                }
182                continue;
183            }
184
185
186            dm.initialize(compositeMap[i]);
187            dm.setGoal(t);
188            dm.scan(null, null, true);
189            for (int x = 0; x < dungeon.length; x++) {
190                for (int y = 0; y < dungeon[x].length; y++) {
191                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 99999.0;
192                }
193            }
194        }
195        double bestQuality = 99999 * ts.length;
196        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
197        for (int x = 0; x < qualityMap.length; x++) {
198            for (int y = 0; y < qualityMap[x].length; y++) {
199                qualityMap[x][y] = 0.0;
200                long bits = 0;
201                for (int i = 0; i < ts.length; i++) {
202                    qualityMap[x][y] += compositeMap[i][x][y];
203                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
204                        bits |= 1 << i;
205                }
206                if(qualityMap[x][y] < bestQuality)
207                {
208                    ArrayList<Coord> ap = new ArrayList<>();
209
210                    for (int i = 0; i < ts.length && i < 63; ++i) {
211                        if((bits & (1 << i)) != 0)
212                            ap.add(ts[i]);
213                    }
214                    if(ap.size() > 0)
215                    {
216                        bestQuality = qualityMap[x][y];
217                        bestPoints.clear();
218                        bestPoints.put(Coord.get(x, y), ap);
219                    }
220                }
221                else if(qualityMap[x][y] == bestQuality) {
222                    ArrayList<Coord> ap = new ArrayList<>();
223
224                    for (int i = 0; i < ts.length && i < 63; ++i) {
225                        if ((bits & (1 << i)) != 0)
226                            ap.add(ts[i]);
227                    }
228                    if (ap.size() > 0) {
229                        bestPoints.put(Coord.get(x, y), ap);
230                    }
231                }
232            }
233        }
234
235        return bestPoints;
236    }
237
238    @Override
239    public OrderedMap<Coord, ArrayList<Coord>> idealLocations(Collection<Coord> priorityTargets, Collection<Coord> lesserTargets, Collection<Coord> requiredExclusions) {
240        if(priorityTargets == null)
241            return idealLocations(lesserTargets, requiredExclusions);
242        if(requiredExclusions == null) requiredExclusions = new OrderedSet<>();
243
244        //requiredExclusions.remove(origin);
245        int totalTargets = priorityTargets.size() + lesserTargets.size();
246        OrderedMap<Coord, ArrayList<Coord>> bestPoints = new OrderedMap<>(totalTargets * 8);
247
248        if(totalTargets == 0)
249            return bestPoints;
250
251        if(radius == 0)
252        {
253            for(Coord p : priorityTargets)
254            {
255                ArrayList<Coord> ap = new ArrayList<>();
256                ap.add(p);
257                bestPoints.put(p, ap);
258            }
259            return bestPoints;
260        }
261        Coord[] pts = priorityTargets.toArray(new Coord[0]);
262        Coord[] lts = lesserTargets.toArray(new Coord[0]);
263        Coord[] exs = requiredExclusions.toArray(new Coord[0]);
264        Coord t;
265
266        double[][][] compositeMap = new double[totalTargets][dungeon.length][dungeon[0].length];
267
268        char[][] dungeonCopy = new char[dungeon.length][dungeon[0].length],
269                dungeonPriorities = new char[dungeon.length][dungeon[0].length];
270        for (int i = 0; i < dungeon.length; i++) {
271            System.arraycopy(dungeon[i], 0, dungeonCopy[i], 0, dungeon[i].length);
272            Arrays.fill(dungeonPriorities[i], '#');
273        }
274        double[][] tmpfov;
275        Coord tempPt;
276        for (int i = 0; i < exs.length; ++i) {
277            t = exs[i];
278
279            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
280            for (int x = 0; x < dungeon.length; x++) {
281                for (int y = 0; y < dungeon[x].length; y++) {
282                    tempPt = Coord.get(x, y);
283                    dungeonCopy[x][y] = (tmpfov[x][y] > 0.0 || !AreaUtils.verifyReach(reach, origin, tempPt)) ? '!' : dungeonCopy[x][y];
284                }
285            }
286        }
287
288        Measurement dmm = Measurement.MANHATTAN;
289        if(radiusType == Radius.SQUARE || radiusType == Radius.CUBE) dmm = Measurement.CHEBYSHEV;
290        else if(radiusType == Radius.CIRCLE || radiusType == Radius.SPHERE) dmm = Measurement.EUCLIDEAN;
291
292        for (int i = 0; i < pts.length; ++i) {
293            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
294
295            t = pts[i];
296
297            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
298
299            double dist;
300            for (int x = 0; x < dungeon.length; x++) {
301                for (int y = 0; y < dungeon[x].length; y++) {
302                    if (tmpfov[x][y] > 0.0){
303                        dist = reach.metric.radius(origin.x, origin.y, x, y);
304                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius) {
305                            compositeMap[i][x][y] = dm.physicalMap[x][y];
306                            dungeonPriorities[x][y] = dungeon[x][y];
307                        }
308                        else
309                            compositeMap[i][x][y] = DijkstraMap.WALL;
310                    }
311                    else compositeMap[i][x][y] = DijkstraMap.WALL;
312                }
313            }
314            if(compositeMap[i][pts[i].x][pts[i].y] > DijkstraMap.FLOOR)
315            {
316                for (int x = 0; x < dungeon.length; x++) {
317                    Arrays.fill(compositeMap[i][x], 399999.0);
318                }
319                continue;
320            }
321
322            dm.initialize(compositeMap[i]);
323            dm.setGoal(t);
324            dm.scan(null, null);
325            for (int x = 0; x < dungeon.length; x++) {
326                for (int y = 0; y < dungeon[x].length; y++) {
327                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!') ? dm.gradientMap[x][y] : 399999.0;
328                }
329            }
330        }
331
332        for (int i = pts.length; i < totalTargets; ++i) {
333            DijkstraMap dm = new DijkstraMap(dungeon, dmm);
334
335            t = lts[i - pts.length];
336
337            tmpfov = fov.calculateFOV(map, t.x, t.y, radius, radiusType);
338
339            double dist;
340            for (int x = 0; x < dungeon.length; x++) {
341                for (int y = 0; y < dungeon[x].length; y++) {
342                    if (tmpfov[x][y] > 0.0){
343                        dist = reach.metric.radius(origin.x, origin.y, x, y);
344                        if(dist <= reach.maxDistance + radius && dist >= reach.minDistance - radius)
345                            compositeMap[i][x][y] = dm.physicalMap[x][y];
346                        else
347                            compositeMap[i][x][y] = DijkstraMap.WALL;
348                    }
349                    else compositeMap[i][x][y] = DijkstraMap.WALL;
350                }
351            }
352            if(compositeMap[i][lts[i - pts.length].x][lts[i - pts.length].y] > DijkstraMap.FLOOR)
353            {
354                for (int x = 0; x < dungeon.length; x++)
355                {
356                    Arrays.fill(compositeMap[i][x], 99999.0);
357                }
358                continue;
359            }
360
361            dm.initialize(compositeMap[i]);
362            dm.setGoal(t);
363            dm.scan(null, null);
364            for (int x = 0; x < dungeon.length; x++) {
365                for (int y = 0; y < dungeon[x].length; y++) {
366                    compositeMap[i][x][y] = (dm.gradientMap[x][y] < DijkstraMap.FLOOR  && dungeonCopy[x][y] != '!' && dungeonPriorities[x][y] != '#') ? dm.gradientMap[x][y] : 99999.0;
367                }
368            }
369        }
370        double bestQuality = 99999 * lts.length + 399999 * pts.length;
371        double[][] qualityMap = new double[dungeon.length][dungeon[0].length];
372        for (int x = 0; x < qualityMap.length; x++) {
373            for (int y = 0; y < qualityMap[x].length; y++) {
374                qualityMap[x][y] = 0.0;
375                long pbits = 0, lbits = 0;
376                for (int i = 0; i < pts.length; ++i) {
377                    qualityMap[x][y] += compositeMap[i][x][y];
378                    if(compositeMap[i][x][y] < 399999.0 && i < 63)
379                        pbits |= 1 << i;
380                }
381                for (int i = pts.length; i < totalTargets; ++i) {
382                    qualityMap[x][y] += compositeMap[i][x][y];
383                    if(compositeMap[i][x][y] < 99999.0 && i < 63)
384                        lbits |= 1 << i;
385                }
386                if(qualityMap[x][y] < bestQuality)
387                {
388                    ArrayList<Coord> ap = new ArrayList<>();
389
390                    for (int i = 0; i < pts.length && i < 63; ++i) {
391                        if((pbits & (1 << i)) != 0)
392                            ap.add(pts[i]);
393                    }
394                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
395                        if((lbits & (1 << i)) != 0)
396                            ap.add(lts[i - pts.length]);
397                    }
398                    if(ap.size() > 0) {
399                        bestQuality = qualityMap[x][y];
400                        bestPoints.clear();
401                        bestPoints.put(Coord.get(x, y), ap);
402                    }
403                }
404                else if(qualityMap[x][y] == bestQuality) {
405                    ArrayList<Coord> ap = new ArrayList<>();
406
407                    for (int i = 0; i < pts.length && i < 63; ++i) {
408                        if ((pbits & (1 << i)) != 0) {
409                            ap.add(pts[i]);
410                            ap.add(pts[i]);
411                            ap.add(pts[i]);
412                            ap.add(pts[i]);
413                        }
414                    }
415                    for (int i = pts.length; i < totalTargets && i < 63; ++i) {
416                        if ((lbits & (1 << i)) != 0)
417                            ap.add(lts[i - pts.length]);
418                    }
419                    if (ap.size() > 0) {
420                        bestPoints.put(Coord.get(x, y), ap);
421                    }
422                }
423            }
424        }
425
426        return bestPoints;
427    }
428
429    /*
430    @Override
431    public ArrayList<ArrayList<Coord>> idealLocations(Set<Coord> targets, Set<Coord> requiredExclusions) {
432        int totalTargets = targets.size() + 1;
433        int maxEffect = (int)radiusType.volume2D(radius);
434        ArrayList<ArrayList<Coord>> locs = new ArrayList<ArrayList<Coord>>(totalTargets);
435
436        for(int i = 0; i < totalTargets; i++)
437        {
438            locs.add(new ArrayList<Coord>(maxEffect));
439        }
440        if(totalTargets == 1)
441            return locs;
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 OrderedMap<Coord, Double> findArea() {
513        return AreaUtils.arrayToHashMap(fov.calculateFOV(map, center.x, center.y, radius, radiusType));
514    }
515
516    @Override
517    public Coord getOrigin() {
518        return origin;
519    }
520
521    @Override
522    public void setOrigin(Coord origin) {
523        this.origin = origin;
524
525    }
526
527    @Override
528    public AimLimit getLimitType() {
529        return reach.limit;
530    }
531
532    @Override
533    public int getMinRange() {
534        return reach.minDistance;
535    }
536
537    @Override
538    public int getMaxRange() {
539        return reach.maxDistance;
540    }
541
542    @Override
543    public Radius getMetric() {
544        return reach.metric;
545    }
546
547    /**
548     * Gets the same values returned by getLimitType(), getMinRange(), getMaxRange(), and getMetric() bundled into one
549     * Reach object.
550     *
551     * @return a non-null Reach object.
552     */
553    @Override
554    public Reach getReach() {
555        return reach;
556    }
557
558    @Override
559    public void setLimitType(AimLimit limitType) {
560        reach.limit = limitType;
561
562    }
563
564    @Override
565    public void setMinRange(int minRange) {
566        reach.minDistance = minRange;
567    }
568
569    @Override
570    public void setMaxRange(int maxRange) {
571        reach.maxDistance = maxRange;
572
573    }
574
575    @Override
576    public void setMetric(Radius metric) {
577        reach.metric = metric;
578    }
579
580    /**
581     * Sets the same values as setLimitType(), setMinRange(), setMaxRange(), and setMetric() using one Reach object.
582     *
583     * @param reach a non-null Reach object.
584     */
585    @Override
586    public void setReach(Reach reach) {
587        if(reach != null)
588            this.reach = reach;
589    }
590
591}