Source code

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