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