001package squidpony.squidai;
002
003import squidpony.GwtCompatibility;
004import squidpony.annotation.GwtIncompatible;
005import squidpony.squidgrid.*;
006import squidpony.squidmath.*;
007
008import java.util.*;
009
010/**
011 * An alternative to AStarSearch when you want to fully explore a search space, or when you want a gradient floodfill.
012 * If you can't remember how to spell this, just remember: Does It Just Know Stuff? That's Really Awesome!
013 * Created by Tommy Ettinger on 4/4/2015.
014 */
015public class DijkstraMap {
016    /**
017     * The type of heuristic to use.
018     */
019    public enum Measurement {
020
021        /**
022         * The distance it takes when only the four primary directions can be
023         * moved in. The default.
024         */
025        MANHATTAN,
026        /**
027         * The distance it takes when diagonal movement costs the same as
028         * cardinal movement.
029         */
030        CHEBYSHEV,
031        /**
032         * The distance it takes as the crow flies. This will NOT affect movement cost when calculating a path,
033         * only the preferred squares to travel to (resulting in drastically more reasonable-looking paths).
034         */
035        EUCLIDEAN
036    }
037
038    /**
039     * This affects how distance is measured on diagonal directions vs. orthogonal directions. MANHATTAN should form a
040     * diamond shape on a featureless map, while CHEBYSHEV and EUCLIDEAN will form a square. EUCLIDEAN does not affect
041     * the length of paths, though it will change the DijkstraMap's gradientMap to have many non-integer values, and
042     * that in turn will make paths this finds much more realistic and smooth (favoring orthogonal directions unless a
043     * diagonal one is a better option).
044     */
045    public Measurement measurement = Measurement.MANHATTAN;
046
047
048    /**
049     * Stores which parts of the map are accessible and which are not. Should not be changed unless the actual physical
050     * terrain has changed. You should call initialize() with a new map instead of changing this directly.
051     */
052    public double[][] physicalMap;
053    /**
054     * The frequently-changing values that are often the point of using this class; goals will have a value of 0, and
055     * any cells that can have a character reach a goal in n steps will have a value of n. Cells that cannot be
056     * entered because they are solid will have a very high value equal to the WALL constant in this class, and cells
057     * that cannot be entered because they cannot reach a goal will have a different very high value equal to the
058     * DARK constant in this class.
059     */
060    public double[][] gradientMap;
061    /**
062     * A 2D array of modifiers to apply to the perceived safety of an area; modifiers go up when deteriorate() is
063     * called, which makes the cells specified in that method call more dangerous (usually because staying in one place
064     * is perceived as risky).
065     */
066    public double[][] safetyMap;
067    /**
068     * This stores the entry cost multipliers for each cell; that is, a value of 1.0 is a normal, unmodified cell, but
069     * a value of 0.5 can be entered easily (two cells of its cost can be entered for the cost of one 1.0 cell), and a
070     * value of 2.0 can only be entered with difficulty (one cell of its cost can be entered for the cost of two 1.0
071     * cells). Unlike the measurement field, this does affect the length of paths, as well as the numbers assigned
072     * to gradientMap during a scan. The values for walls are identical to the value used by gradientMap, that is, this
073     * class' WALL static final field. Floors, however, are never given FLOOR as a value, and default to 1.0 .
074     */
075    public double[][] costMap = null;
076    /**
077     * Height of the map. Exciting stuff. Don't change this, instead call initialize().
078     */
079    public int height;
080    /**
081     * Width of the map. Exciting stuff. Don't change this, instead call initialize().
082     */
083    public int width;
084    /**
085     * The latest path that was obtained by calling findPath(). It will not contain the value passed as a starting
086     * cell; only steps that require movement will be included, and so if the path has not been found or a valid
087     * path toward a goal is impossible, this ArrayList will be empty.
088     */
089    public ArrayList<Coord> path = new ArrayList<>();
090    /**
091     * Goals are always marked with 0.
092     */
093    public static final double GOAL = 0.0;
094    /**
095     * Floor cells, which include any walkable cell, are marked with a high number equal to 999200.0 .
096     */
097    public static final double FLOOR = 999200.0;
098    /**
099     * Walls, which are solid no-entry cells, are marked with a high number equal to 999500.0 .
100     */
101    public static final double WALL = 999500.0;
102    /**
103     * This is used to mark cells that the scan couldn't reach, and these dark cells are marked with a high number
104     * equal to 999800.0 .
105     */
106    public static final double DARK = 999800.0;
107    /**
108     * Goals that pathfinding will seek out. The Double value should almost always be 0.0 , the same as the static GOAL
109     * constant in this class.
110     */
111    public LinkedHashMap<Coord, Double> goals;
112    private LinkedHashMap<Coord, Double> fresh, closed, open;
113    /**
114     * The RNG used to decide which one of multiple equally-short paths to take.
115     */
116    public RNG rng;
117    private int frustration = 0;
118    public Coord[][] targetMap;
119
120
121    private boolean initialized = false;
122
123
124    private int mappedCount = 0;
125
126    public int getMappedCount() {
127        return mappedCount;
128    }
129
130    /**
131     * Construct a DijkstraMap without a level to actually scan. If you use this constructor, you must call an
132     * initialize() method before using this class.
133     */
134    public DijkstraMap() {
135        rng = new RNG(new LightRNG());
136        path = new ArrayList<>();
137
138        goals = new LinkedHashMap<>();
139        fresh = new LinkedHashMap<>();
140        closed = new LinkedHashMap<>();
141        open = new LinkedHashMap<>();
142    }
143
144    /**
145     * Construct a DijkstraMap without a level to actually scan. This constructor allows you to specify an RNG before
146     * it is ever used in this class. If you use this constructor, you must call an initialize() method before using
147     * any other methods in the class.
148     */
149    public DijkstraMap(RNG random) {
150        rng = random;
151        path = new ArrayList<>();
152
153        goals = new LinkedHashMap<>();
154        fresh = new LinkedHashMap<>();
155        closed = new LinkedHashMap<>();
156        open = new LinkedHashMap<>();
157    }
158
159    /**
160     * Used to construct a DijkstraMap from the output of another.
161     *
162     * @param level
163     */
164    public DijkstraMap(final double[][] level) {
165        rng = new RNG(new LightRNG());
166        path = new ArrayList<>();
167
168        goals = new LinkedHashMap<>();
169        fresh = new LinkedHashMap<>();
170        closed = new LinkedHashMap<>();
171        open = new LinkedHashMap<>();
172        initialize(level);
173    }
174
175    /**
176     * Used to construct a DijkstraMap from the output of another, specifying a distance calculation.
177     *
178     * @param level
179     * @param measurement
180     */
181    public DijkstraMap(final double[][] level, Measurement measurement) {
182        rng = new RNG(new LightRNG());
183        this.measurement = measurement;
184        path = new ArrayList<>();
185
186        goals = new LinkedHashMap<>();
187        fresh = new LinkedHashMap<>();
188        closed = new LinkedHashMap<>();
189        open = new LinkedHashMap<>();
190        initialize(level);
191    }
192
193    /**
194     * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other
195     * char[][] where '#' means a wall and anything else is a walkable tile. If you only have
196     * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a
197     * map that can be used here.
198     *
199     * @param level
200     */
201    public DijkstraMap(final char[][] level) {
202        rng = new RNG(new LightRNG());
203        path = new ArrayList<>();
204
205        goals = new LinkedHashMap<>();
206        fresh = new LinkedHashMap<>();
207        closed = new LinkedHashMap<>();
208        open = new LinkedHashMap<>();
209        initialize(level);
210    }
211
212    /**
213     * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other
214     * char[][] where '#' means a wall and anything else is a walkable tile. If you only have
215     * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a
216     * map that can be used here. Also takes an RNG that ensures predictable path choices given
217     * otherwise identical inputs and circumstances.
218     *
219     * @param level
220     * @param rng   The RNG to use for certain decisions; only affects find* methods like findPath, not scan.
221     */
222    public DijkstraMap(final char[][] level, RNG rng) {
223        this.rng = rng;
224        path = new ArrayList<>();
225
226        goals = new LinkedHashMap<>();
227        fresh = new LinkedHashMap<>();
228        closed = new LinkedHashMap<>();
229        open = new LinkedHashMap<>();
230        initialize(level);
231    }
232
233    /**
234     * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other
235     * char[][] where one char means a wall and anything else is a walkable tile. If you only have
236     * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a
237     * map that can be used here. You can specify the character used for walls.
238     *
239     * @param level
240     */
241    public DijkstraMap(final char[][] level, char alternateWall) {
242        rng = new RNG(new LightRNG());
243        path = new ArrayList<>();
244
245        goals = new LinkedHashMap<>();
246        fresh = new LinkedHashMap<>();
247        closed = new LinkedHashMap<>();
248        open = new LinkedHashMap<>();
249        initialize(level, alternateWall);
250    }
251
252    /**
253     * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other
254     * char[][] where '#' means a wall and anything else is a walkable tile. If you only have
255     * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a
256     * map that can be used here. This constructor specifies a distance measurement.
257     *
258     * @param level
259     * @param measurement
260     */
261    public DijkstraMap(final char[][] level, Measurement measurement) {
262        rng = new RNG(new LightRNG());
263        path = new ArrayList<>();
264        this.measurement = measurement;
265
266        goals = new LinkedHashMap<>();
267        fresh = new LinkedHashMap<>();
268        closed = new LinkedHashMap<>();
269        open = new LinkedHashMap<>();
270        initialize(level);
271    }
272
273    /**
274     * Constructor meant to take a char[][] returned by DungeonGen.generate(), or any other
275     * char[][] where '#' means a wall and anything else is a walkable tile. If you only have
276     * a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a
277     * map that can be used here. Also takes a distance measurement and an RNG that ensures
278     * predictable path choices given otherwise identical inputs and circumstances.
279     *
280     * @param level
281     * @param rng   The RNG to use for certain decisions; only affects find* methods like findPath, not scan.
282     */
283    public DijkstraMap(final char[][] level, Measurement measurement, RNG rng) {
284        this.rng = rng;
285        path = new ArrayList<>();
286        this.measurement = measurement;
287
288        goals = new LinkedHashMap<>();
289        fresh = new LinkedHashMap<>();
290        closed = new LinkedHashMap<>();
291        open = new LinkedHashMap<>();
292        initialize(level);
293    }
294
295    /**
296     * Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given
297     * one when it was constructed, or because the contents of the terrain have changed permanently (not if a
298     * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
299     *
300     * @param level
301     * @return
302     */
303    public DijkstraMap initialize(final double[][] level) {
304        width = level.length;
305        height = level[0].length;
306        gradientMap = new double[width][height];
307        safetyMap = new double[width][height];
308        physicalMap = new double[width][height];
309        costMap = new double[width][height];
310        targetMap = new Coord[width][height];
311        for (int x = 0; x < width; x++) {
312            System.arraycopy(level[x], 0, gradientMap[x], 0, height);
313            System.arraycopy(level[x], 0, physicalMap[x], 0, height);
314            Arrays.fill(costMap[x], 1.0);
315        }
316        initialized = true;
317        return this;
318    }
319
320    /**
321     * Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given
322     * one when it was constructed, or because the contents of the terrain have changed permanently (not if a
323     * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
324     *
325     * @param level
326     * @return
327     */
328    public DijkstraMap initialize(final char[][] level) {
329        width = level.length;
330        height = level[0].length;
331        gradientMap = new double[width][height];
332        safetyMap = new double[width][height];
333        physicalMap = new double[width][height];
334        costMap = new double[width][height];
335        targetMap = new Coord[width][height];
336        for (int x = 0; x < width; x++) {
337            Arrays.fill(costMap[x], 1.0);
338            for (int y = 0; y < height; y++) {
339                double t = (level[x][y] == '#') ? WALL : FLOOR;
340                gradientMap[x][y] = t;
341                physicalMap[x][y] = t;
342            }
343        }
344        initialized = true;
345        return this;
346    }
347
348    /**
349     * Used to initialize or re-initialize a DijkstraMap that needs a new PhysicalMap because it either wasn't given
350     * one when it was constructed, or because the contents of the terrain have changed permanently (not if a
351     * creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). This
352     * initialize() method allows you to specify an alternate wall char other than the default character, '#' .
353     *
354     * @param level
355     * @param alternateWall
356     * @return
357     */
358    public DijkstraMap initialize(final char[][] level, char alternateWall) {
359        width = level.length;
360        height = level[0].length;
361        gradientMap = new double[width][height];
362        safetyMap = new double[width][height];
363        physicalMap = new double[width][height];
364        costMap = new double[width][height];
365        targetMap = new Coord[width][height];
366        for (int x = 0; x < width; x++) {
367            Arrays.fill(costMap[x], 1.0);
368            for (int y = 0; y < height; y++) {
369                double t = (level[x][y] == alternateWall) ? WALL : FLOOR;
370                gradientMap[x][y] = t;
371                physicalMap[x][y] = t;
372            }
373        }
374        initialized = true;
375        return this;
376    }
377
378    /**
379     * Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects
380     * a char[][] of the same exact dimensions as the 2D array that was used to previously initialize() this
381     * DijkstraMap, treating the '#' char as a wall (impassable) and anything else as having a normal cost to enter.
382     * The costs can be accessed later by using costMap directly (which will have a valid value when this does not
383     * throw an exception), or by calling setCost().
384     *
385     * @param level a 2D char array that uses '#' for walls
386     * @return this DijkstraMap for chaining.
387     */
388    public DijkstraMap initializeCost(final char[][] level) {
389        if (!initialized) throw new IllegalStateException("DijkstraMap must be initialized first!");
390        for (int x = 0; x < width; x++) {
391            for (int y = 0; y < height; y++) {
392                costMap[x][y] = (level[x][y] == '#') ? WALL : 1.0;
393            }
394        }
395        return this;
396    }
397
398    /**
399     * Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects
400     * a char[][] of the same exact dimensions as the 2D array that was used to previously initialize() this
401     * DijkstraMap, treating the '#' char as a wall (impassable) and anything else as having a normal cost to enter.
402     * The costs can be accessed later by using costMap directly (which will have a valid value when this does not
403     * throw an exception), or by calling setCost().
404     * <p/>
405     * This method allows you to specify an alternate wall char other than the default character, '#' .
406     *
407     * @param level         a 2D char array that uses alternateChar for walls.
408     * @param alternateWall a char to use to represent walls.
409     * @return this DijkstraMap for chaining.
410     */
411    public DijkstraMap initializeCost(final char[][] level, char alternateWall) {
412        if (!initialized) throw new IllegalStateException("DijkstraMap must be initialized first!");
413        for (int x = 0; x < width; x++) {
414            for (int y = 0; y < height; y++) {
415                costMap[x][y] = (level[x][y] == alternateWall) ? WALL : 1.0;
416            }
417        }
418        return this;
419    }
420
421    /**
422     * Used to initialize the entry cost modifiers for games that require variable costs to enter squares. This expects
423     * a double[][] of the same exact dimensions as the 2D array that was used to previously initialize() this
424     * DijkstraMap, using the exact values given in costs as the values to enter cells, even if they aren't what this
425     * class would assign normally -- walls and other impassable values should be given WALL as a value, however.
426     * The costs can be accessed later by using costMap directly (which will have a valid value when this does not
427     * throw an exception), or by calling setCost().
428     * <p/>
429     * This method should be slightly more efficient than the other initializeCost methods.
430     *
431     * @param costs a 2D double array that already has the desired cost values
432     * @return this DijkstraMap for chaining.
433     */
434    public DijkstraMap initializeCost(final double[][] costs) {
435        if (!initialized) throw new IllegalStateException("DijkstraMap must be initialized first!");
436        costMap = new double[width][height];
437        for (int x = 0; x < width; x++) {
438            System.arraycopy(costs[x], 0, costMap[x], 0, height);
439        }
440        return this;
441    }
442
443    /**
444     * Gets the appropriate DijkstraMap.Measurement to pass to a constructor if you already have a Radius.
445     * Matches SQUARE or CUBE to CHEBYSHEV, DIAMOND or OCTAHEDRON to MANHATTAN, and CIRCLE or SPHERE to EUCLIDEAN.
446     *
447     * @param radius the Radius to find the corresponding Measurement for
448     * @return a DijkstraMap.Measurement that matches radius; SQUARE to CHEBYSHEV, DIAMOND to MANHATTAN, etc.
449     */
450    public static Measurement findMeasurement(Radius radius) {
451        if (radius.equals2D(Radius.SQUARE))
452            return DijkstraMap.Measurement.CHEBYSHEV;
453        else if (radius.equals2D(Radius.DIAMOND))
454            return DijkstraMap.Measurement.MANHATTAN;
455        else
456            return DijkstraMap.Measurement.EUCLIDEAN;
457    }
458
459    /**
460     * Gets the appropriate Radius corresponding to a DijkstraMap.Measurement.
461     * Matches CHEBYSHEV to SQUARE, MANHATTAN to DIAMOND, and EUCLIDEAN to CIRCLE.
462     *
463     * @param measurement the Measurement to find the corresponding Radius for
464     * @return a DijkstraMap.Measurement that matches radius; CHEBYSHEV to SQUARE, MANHATTAN to DIAMOND, etc.
465     */
466    public static Radius findRadius(Measurement measurement) {
467        switch (measurement) {
468            case CHEBYSHEV:
469                return Radius.SQUARE;
470            case EUCLIDEAN:
471                return Radius.CIRCLE;
472            default:
473                return Radius.DIAMOND;
474        }
475    }
476
477    /**
478     * Resets the gradientMap to its original value from physicalMap.
479     */
480    public void resetMap() {
481        if (!initialized) return;
482        for (int x = 0; x < width; x++) {
483            for (int y = 0; y < height; y++) {
484                gradientMap[x][y] = physicalMap[x][y];
485            }
486        }
487    }
488
489    /**
490     * Resets the targetMap (which is only assigned in the first place if you use findTechniquePath() ).
491     */
492    public void resetTargetMap() {
493        if (!initialized) return;
494        for (int x = 0; x < width; x++) {
495            for (int y = 0; y < height; y++) {
496                targetMap[x][y] = null;
497            }
498        }
499    }
500
501    /**
502     * Resets the targetMap (which is only assigned in the first place if you use findTechniquePath() ).
503     */
504    public void resetSafetyMap() {
505        if (!initialized) return;
506        for (int x = 0; x < width; x++) {
507            for (int y = 0; y < height; y++) {
508                safetyMap[x][y] = 0.0;
509            }
510        }
511    }
512
513    /**
514     * Resets this DijkstraMap to a state with no goals, no discovered path, and no changes made to gradientMap
515     * relative to physicalMap.
516     */
517    public void reset() {
518        resetMap();
519        resetTargetMap();
520        goals.clear();
521        path.clear();
522        closed.clear();
523        fresh.clear();
524        open.clear();
525        frustration = 0;
526    }
527
528    /**
529     * Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
530     *
531     * @param x
532     * @param y
533     */
534    public void setGoal(int x, int y) {
535        if (!initialized) return;
536        if (physicalMap[x][y] > FLOOR) {
537            return;
538        }
539
540        goals.put(Coord.get(x, y), GOAL);
541    }
542
543    /**
544     * Marks a cell as a goal for pathfinding, unless the cell is a wall or unreachable area (then it does nothing).
545     *
546     * @param pt
547     */
548    public void setGoal(Coord pt) {
549        if (!initialized) return;
550        if (physicalMap[pt.x][pt.y] > FLOOR) {
551            return;
552        }
553
554        goals.put(pt, GOAL);
555    }
556
557    /**
558     * Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets
559     * the cost to the value of the WALL field).
560     *
561     * @param pt
562     * @param cost
563     */
564    public void setCost(Coord pt, double cost) {
565        if (!initialized) return;
566        if (physicalMap[pt.x][pt.y] > FLOOR) {
567            costMap[pt.x][pt.y] = WALL;
568            return;
569        }
570        costMap[pt.x][pt.y] = cost;
571    }
572
573    /**
574     * Marks a cell's cost for pathfinding as cost, unless the cell is a wall or unreachable area (then it always sets
575     * the cost to the value of the WALL field).
576     *
577     * @param x
578     * @param y
579     * @param cost
580     */
581    public void setCost(int x, int y, double cost) {
582        if (!initialized) return;
583        if (physicalMap[x][y] > FLOOR) {
584            costMap[x][y] = WALL;
585            return;
586        }
587        costMap[x][y] = cost;
588    }
589
590    /**
591     * Marks a specific cell in gradientMap as completely impossible to enter.
592     *
593     * @param x
594     * @param y
595     */
596    public void setOccupied(int x, int y) {
597        if (!initialized) return;
598        gradientMap[x][y] = WALL;
599    }
600
601    /**
602     * Reverts a cell to the value stored in the original state of the level as known by physicalMap.
603     *
604     * @param x
605     * @param y
606     */
607    public void resetCell(int x, int y) {
608        if (!initialized) return;
609        gradientMap[x][y] = physicalMap[x][y];
610    }
611
612    /**
613     * Reverts a cell to the value stored in the original state of the level as known by physicalMap.
614     *
615     * @param pt
616     */
617    public void resetCell(Coord pt) {
618        if (!initialized) return;
619        gradientMap[pt.x][pt.y] = physicalMap[pt.x][pt.y];
620    }
621
622    /**
623     * Used to remove all goals and undo any changes to gradientMap made by having a goal present.
624     */
625    public void clearGoals() {
626        if (!initialized)
627            return;
628        for (Coord entry : goals.keySet()) {
629            resetCell(entry);
630        }
631        goals.clear();
632    }
633
634    protected void setFresh(int x, int y, double counter) {
635        if (!initialized) return;
636        gradientMap[x][y] = counter;
637        fresh.put(Coord.get(x, y), counter);
638    }
639
640    protected void setFresh(final Coord pt, double counter) {
641        if (!initialized) return;
642        gradientMap[pt.x][pt.y] = counter;
643        fresh.put(pt, counter);
644    }
645
646    /**
647     * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes
648     * specified risky points to be considered less safe, and will encourage a pathfinder to keep moving toward a goal
649     * instead of just staying in cover forever (or until an enemy moves around the cover and ambushes the pathfinder).
650     * Typically, you call deteriorate() with the current Coord position of the pathfinder and any Coords they stayed at
651     * earlier along a path, and you do this once every turn or once every few turns, depending on how aggressively the
652     * pathfinder should seek a goal.
653     *
654     * @param riskyPoints a List of Coord that should be considered more risky to stay at with each call.
655     * @return the current safetyMap.
656     */
657    public double[][] deteriorate(List<Coord> riskyPoints) {
658        return deteriorate(riskyPoints.toArray(new Coord[riskyPoints.size()]));
659    }
660
661    /**
662     * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes
663     * specified risky points to be considered less safe, and will encourage a pathfinder to keep moving toward a goal
664     * instead of just staying in cover forever (or until an enemy moves around the cover and ambushes the pathfinder).
665     * Typically, you call deteriorate() with the current Coord position of the pathfinder and any Coords they stayed at
666     * earlier along a path, and you do this once every turn or once every few turns, depending on how aggressively the
667     * pathfinder should seek a goal.
668     *
669     * @param riskyPoints a vararg or array of Coord that should be considered more risky to stay at with each call.
670     * @return the current safetyMap.
671     */
672    public double[][] deteriorate(Coord... riskyPoints) {
673        if (!initialized)
674            return null;
675        Coord c;
676        for (int i = 0; i < riskyPoints.length; i++) {
677            c = riskyPoints[i];
678            safetyMap[c.x][c.y] += 1.0;
679        }
680        return safetyMap;
681    }
682
683    /**
684     * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes
685     * specified safer points to be considered more safe, and will make a pathfinder more likely to enter those places
686     * if they were considered dangerous earlier (due to calling deteriorate()).
687     * <p/>
688     * Typically, you call relax() with previous Coords a pathfinder stayed at that should be safer now than they were
689     * at some previous point in time, and you might do this when no one has been attacked in a while or when the AI is
690     * sure that a threat has been neutralized or no longer threatens a safer point.
691     *
692     * @param saferPoints a List of Coord that should be considered less risky to stay at with each call.
693     * @return the current safetyMap.
694     */
695    public double[][] relax(List<Coord> saferPoints) {
696        return relax(saferPoints.toArray(new Coord[saferPoints.size()]));
697    }
698
699    /**
700     * Used in conjunction with methods that depend on finding cover, like findCoveredAttackPath(), this method causes
701     * specified safer points to be considered more safe, and will make a pathfinder more likely to enter those places
702     * if they were considered dangerous earlier (due to calling deteriorate()).
703     * <p/>
704     * Typically, you call relax() with previous Coords a pathfinder stayed at that should be safer now than they were
705     * at some previous point in time, and you might do this when no one has been attacked in a while or when the AI is
706     * sure that a threat has been neutralized or no longer threatens a safer point.
707     *
708     * @param saferPoints a vararg or array of Coord that should be considered less risky to stay at with each call.
709     * @return the current safetyMap.
710     */
711    public double[][] relax(Coord... saferPoints) {
712        if (!initialized)
713            return null;
714        Coord c;
715        for (int i = 0; i < saferPoints.length; i++) {
716            c = saferPoints[i];
717            safetyMap[c.x][c.y] -= 1.0;
718            if (safetyMap[c.x][c.y] < 0.0)
719                safetyMap[c.x][c.y] = 0.0;
720        }
721        return safetyMap;
722    }
723
724    /**
725     * Recalculate the Dijkstra map and return it. Cells that were marked as goals with setGoal will have
726     * a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further
727     * from goals will have a value equal to the distance from the nearest goal. The exceptions are walls,
728     * which will have a value defined by the WALL constant in this class, and areas that the scan was
729     * unable to reach, which will have a value defined by the DARK constant in this class (typically,
730     * these areas should not be used to place NPCs or items and should be filled with walls). This uses the
731     * current measurement.
732     *
733     * @param impassable A Set of Position keys representing the locations of enemies or other moving obstacles to a
734     *                   path that cannot be moved through; this can be null if there are no such obstacles.
735     * @return A 2D double[width][height] using the width and height of what this knows about the physical map.
736     */
737    public double[][] scan(Set<Coord> impassable) {
738        if (!initialized) return null;
739        if (impassable == null)
740            impassable = new LinkedHashSet<>();
741        LinkedHashMap<Coord, Double> blocking = new LinkedHashMap<>(impassable.size());
742        for (Coord pt : impassable) {
743            blocking.put(pt, WALL);
744        }
745        closed.putAll(blocking);
746
747        for (Map.Entry<Coord, Double> entry : goals.entrySet()) {
748            if (closed.containsKey(entry.getKey()))
749                closed.remove(entry.getKey());
750            gradientMap[entry.getKey().x][entry.getKey().y] = entry.getValue();
751        }
752        double currentLowest = 999000;
753        LinkedHashMap<Coord, Double> lowest = new LinkedHashMap<>();
754
755        for (int y = 0; y < height; y++) {
756            for (int x = 0; x < width; x++) {
757                if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y)))
758                    closed.put(Coord.get(x, y), physicalMap[x][y]);
759                else if (gradientMap[x][y] < currentLowest) {
760                    currentLowest = gradientMap[x][y];
761                    lowest.clear();
762                    lowest.put(Coord.get(x, y), currentLowest);
763                } else if (gradientMap[x][y] == currentLowest) {
764                    lowest.put(Coord.get(x, y), currentLowest);
765                }
766            }
767        }
768        int numAssigned = lowest.size();
769        mappedCount = goals.size();
770        open.putAll(lowest);
771        Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS;
772        while (numAssigned > 0) {
773//            ++iter;
774            numAssigned = 0;
775
776            for (Map.Entry<Coord, Double> cell : open.entrySet()) {
777                for (int d = 0; d < dirs.length; d++) {
778                    Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY);
779                    if (adj.x < 0 || adj.y < 0 || width <= adj.x || height <= adj.y)
780                        /* Outside the map */
781                        continue;
782                    double h = heuristic(dirs[d]);
783                    if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) {
784                        setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]);
785                        ++numAssigned;
786                        ++mappedCount;
787                    }
788                }
789            }
790//            closed.putAll(open);
791            open = new LinkedHashMap<>(fresh);
792            fresh.clear();
793        }
794        closed.clear();
795        open.clear();
796
797        double[][] gradientClone = new double[width][height];
798        for (int x = 0; x < width; x++) {
799            for (int y = 0; y < height; y++) {
800                if (gradientMap[x][y] == FLOOR) {
801                    gradientMap[x][y] = DARK;
802                }
803            }
804            System.arraycopy(gradientMap[x], 0, gradientClone[x], 0, height);
805        }
806
807        return gradientClone;
808    }
809
810    /**
811     * Recalculate the Dijkstra map up to a limit and return it. Cells that were marked as goals with setGoal will have
812     * a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further
813     * from goals will have a value equal to the distance from the nearest goal. If a cell would take more steps to
814     * reach than the given limit, it will have a value of DARK if it was passable instead of the distance. The
815     * exceptions are walls, which will have a value defined by the WALL constant in this class, and areas that the scan
816     * was unable to reach, which will have a value defined by the DARK constant in this class. This uses the
817     * current measurement.
818     *
819     * @param limit      The maximum number of steps to scan outward from a goal.
820     * @param impassable A Set of Position keys representing the locations of enemies or other moving obstacles to a
821     *                   path that cannot be moved through; this can be null if there are no such obstacles.
822     * @return A 2D double[width][height] using the width and height of what this knows about the physical map.
823     */
824    public double[][] partialScan(int limit, Set<Coord> impassable) {
825        if (!initialized) return null;
826        if (impassable == null)
827            impassable = new LinkedHashSet<>();
828        LinkedHashMap<Coord, Double> blocking = new LinkedHashMap<>(impassable.size());
829        for (Coord pt : impassable) {
830            blocking.put(pt, WALL);
831        }
832        closed.putAll(blocking);
833
834        for (Map.Entry<Coord, Double> entry : goals.entrySet()) {
835            if (closed.containsKey(entry.getKey()))
836                closed.remove(entry.getKey());
837            gradientMap[entry.getKey().x][entry.getKey().y] = entry.getValue();
838        }
839        double currentLowest = 999000;
840        LinkedHashMap<Coord, Double> lowest = new LinkedHashMap<>();
841
842        for (int y = 0; y < height; y++) {
843            for (int x = 0; x < width; x++) {
844                if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y)))
845                    closed.put(Coord.get(x, y), physicalMap[x][y]);
846                else if (gradientMap[x][y] < currentLowest) {
847                    currentLowest = gradientMap[x][y];
848                    lowest.clear();
849                    lowest.put(Coord.get(x, y), currentLowest);
850                } else if (gradientMap[x][y] == currentLowest) {
851                    lowest.put(Coord.get(x, y), currentLowest);
852                }
853            }
854        }
855        int numAssigned = lowest.size();
856        mappedCount = goals.size();
857        open.putAll(lowest);
858
859        Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS;
860        int iter = 0;
861        while (numAssigned > 0 && iter < limit) {
862//            ++iter;
863            numAssigned = 0;
864
865            for (Map.Entry<Coord, Double> cell : open.entrySet()) {
866                for (int d = 0; d < dirs.length; d++) {
867                    Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY);
868                    double h = heuristic(dirs[d]);
869                    if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) {
870                        setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]);
871                        ++numAssigned;
872                        ++mappedCount;
873                    }
874                }
875            }
876//            closed.putAll(open);
877            open = new LinkedHashMap<>(fresh);
878            fresh.clear();
879            ++iter;
880        }
881        closed.clear();
882        open.clear();
883
884
885        double[][] gradientClone = new double[width][height];
886        for (int x = 0; x < width; x++) {
887            for (int y = 0; y < height; y++) {
888                if (gradientMap[x][y] == FLOOR) {
889                    gradientMap[x][y] = DARK;
890                }
891            }
892            System.arraycopy(gradientMap[x], 0, gradientClone[x], 0, height);
893        }
894        return gradientClone;
895    }
896
897    /**
898     * Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found.
899     * This uses the current measurement.
900     *
901     * @param start   the cell to use as the origin for finding the nearest target
902     * @param targets the Coords that this is trying to find; it will stop once it finds one
903     * @return the Coord that it found first.
904     */
905    public Coord findNearest(Coord start, Set<Coord> targets) {
906        if (!initialized) return null;
907        if (targets == null)
908            return null;
909        if (targets.contains(start))
910            return start;
911        resetMap();
912        Coord start2 = start;
913        int xShift = width / 8, yShift = height / 8;
914        while (physicalMap[start.x][start.y] >= WALL && frustration < 50) {
915            start2 = Coord.get(Math.min(Math.max(1, start.x + rng.nextInt(1 + xShift * 2) - xShift), width - 2),
916                    Math.min(Math.max(1, start.y + rng.nextInt(1 + yShift * 2) - yShift), height - 2));
917        }
918        if (closed.containsKey(start2))
919            closed.remove(start2);
920        gradientMap[start2.x][start2.y] = 0.0;
921
922        for (int y = 0; y < height; y++) {
923            for (int x = 0; x < width; x++) {
924                if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y)))
925                    closed.put(Coord.get(x, y), physicalMap[x][y]);
926            }
927        }
928        int numAssigned = 1;
929        mappedCount = 1;
930        open.put(start2, 0.0);
931
932        Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS;
933        while (numAssigned > 0) {
934//            ++iter;
935            numAssigned = 0;
936
937            for (Map.Entry<Coord, Double> cell : open.entrySet()) {
938                for (int d = 0; d < dirs.length; d++) {
939                    Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY);
940                    double h = heuristic(dirs[d]);
941                    if (!closed.containsKey(adj) && !open.containsKey(adj) &&
942                            gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) {
943                        setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]);
944                        ++numAssigned;
945                        ++mappedCount;
946                        if (targets.contains(adj)) {
947                            fresh.clear();
948                            closed.clear();
949                            open.clear();
950                            return adj;
951                        }
952                    }
953                }
954            }
955//            closed.putAll(open);
956            open = new LinkedHashMap<>(fresh);
957            fresh.clear();
958        }
959        closed.clear();
960        open.clear();
961        return null;
962    }
963
964    /**
965     * Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first target found.
966     * This uses the current measurement.
967     *
968     * @param start   the cell to use as the origin for finding the nearest target
969     * @param targets the Coords that this is trying to find; it will stop once it finds one
970     * @return the Coord that it found first.
971     */
972    public Coord findNearest(Coord start, Coord... targets) {
973        LinkedHashSet<Coord> tgts = new LinkedHashSet<>(targets.length);
974        Collections.addAll(tgts, targets);
975        return findNearest(start, tgts);
976    }
977
978    /**
979     * If you have a target or group of targets you want to pathfind to without scanning the full map, this can be good.
980     * It may find sub-optimal paths in the presence of costs to move into cells. It is useful when you want to move in
981     * a straight line to a known nearby goal.
982     *
983     * @param start   your starting location
984     * @param targets an array or vararg of Coords to pathfind to the nearest of
985     * @return an ArrayList of Coord that goes from a cell adjacent to start and goes to one of the targets. Copy of path.
986     */
987    public ArrayList<Coord> findShortcutPath(Coord start, Coord... targets) {
988        if (targets.length == 0) {
989            path.clear();
990            return new ArrayList<>(path);
991        }
992        Coord currentPos = findNearest(start, targets);
993        while (true) {
994            if (frustration > 500) {
995                path.clear();
996                break;
997            }
998            double best = gradientMap[currentPos.x][currentPos.y];
999            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
1000            int choice = rng.nextInt(dirs.length);
1001
1002            for (int d = 0; d < dirs.length; d++) {
1003                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
1004                if (gradientMap[pt.x][pt.y] < best) {
1005                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
1006                        best = gradientMap[pt.x][pt.y];
1007                        choice = d;
1008                    }
1009                }
1010            }
1011
1012            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
1013                path.clear();
1014                break;
1015            }
1016            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
1017            if (gradientMap[currentPos.x][currentPos.y] == 0)
1018                break;
1019            path.add(currentPos);
1020            frustration++;
1021        }
1022        frustration = 0;
1023        Collections.reverse(path);
1024        return new ArrayList<>(path);
1025
1026    }
1027
1028    /**
1029     * Recalculate the Dijkstra map until it reaches a Coord in targets, then returns the first several targets found,
1030     * up to limit or less if the map is fully searched without finding enough.
1031     * This uses the current measurement.
1032     *
1033     * @param start   the cell to use as the origin for finding the nearest targets
1034     * @param limit   the maximum number of targets to find before returning
1035     * @param targets the Coords that this is trying to find; it will stop once it finds enough (based on limit)
1036     * @return the Coords that it found first.
1037     */
1038    public ArrayList<Coord> findNearestMultiple(Coord start, int limit, Set<Coord> targets) {
1039        if (!initialized) return null;
1040        if (targets == null)
1041            return null;
1042        ArrayList<Coord> found = new ArrayList<>(limit);
1043        if (targets.contains(start))
1044            return found;
1045        Coord start2 = start;
1046        while (physicalMap[start.x][start.y] >= WALL && frustration < 50) {
1047            start2 = Coord.get(Math.min(Math.max(1, start.x + rng.nextInt(15) - 7), width - 2),
1048                    Math.min(Math.max(1, start.y + rng.nextInt(15) - 7), height - 2));
1049            frustration++;
1050        }
1051        if (closed.containsKey(start2))
1052            closed.remove(start2);
1053        gradientMap[start2.x][start2.y] = 0.0;
1054
1055        for (int y = 0; y < height; y++) {
1056            for (int x = 0; x < width; x++) {
1057                if (gradientMap[x][y] > FLOOR && !goals.containsKey(Coord.get(x, y)))
1058                    closed.put(Coord.get(x, y), physicalMap[x][y]);
1059            }
1060        }
1061        int numAssigned = 1;
1062        mappedCount = 1;
1063        open.put(start2, 0.0);
1064
1065        Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS;
1066        while (numAssigned > 0) {
1067//            ++iter;
1068            numAssigned = 0;
1069
1070            for (Map.Entry<Coord, Double> cell : open.entrySet()) {
1071                for (int d = 0; d < dirs.length; d++) {
1072                    Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY);
1073                    double h = heuristic(dirs[d]);
1074                    if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) {
1075                        setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]);
1076                        ++numAssigned;
1077                        ++mappedCount;
1078                        if (targets.contains(adj)) {
1079                            found.add(adj);
1080                            if (found.size() >= limit) {
1081                                fresh.clear();
1082                                open.clear();
1083                                closed.clear();
1084                                return found;
1085                            }
1086                        }
1087                    }
1088                }
1089            }
1090//            closed.putAll(open);
1091            open = new LinkedHashMap<>(fresh);
1092            fresh.clear();
1093        }
1094        closed.clear();
1095        open.clear();
1096        return found;
1097    }
1098
1099    /**
1100     * Recalculate the Dijkstra map for a creature that is potentially larger than 1x1 cell and return it. The value of
1101     * a cell in the returned Dijkstra map assumes that a creature is square, with a side length equal to the passed
1102     * size, that its minimum-x, minimum-y cell is the starting cell, and that any cell with a distance number
1103     * represents the distance for the creature's minimum-x, minimum-y cell to reach it. Cells that cannot be entered
1104     * by the minimum-x, minimum-y cell because of sizing (such as a floor cell next to a maximum-x and/or maximum-y
1105     * wall if size is &gt; 1) will be marked as DARK. Cells that were marked as goals with setGoal will have
1106     * a value of 0, the cells adjacent to goals will have a value of 1, and cells progressively further
1107     * from goals will have a value equal to the distance from the nearest goal. The exceptions are walls,
1108     * which will have a value defined by the WALL constant in this class, and areas that the scan was
1109     * unable to reach, which will have a value defined by the DARK constant in this class. (typically,
1110     * these areas should not be used to place NPCs or items and should be filled with walls). This uses the
1111     * current measurement.
1112     *
1113     * @param impassable A Set of Position keys representing the locations of enemies or other moving obstacles to a
1114     *                   path that cannot be moved through; this can be null if there are no such obstacles.
1115     * @param size       The length of one side of a square creature using this to find a path, i.e. 2 for a 2x2 cell
1116     *                   creature. Non-square creatures are not supported because turning is really hard.
1117     * @return A 2D double[width][height] using the width and height of what this knows about the physical map.
1118     */
1119    public double[][] scan(Set<Coord> impassable, int size) {
1120        if (!initialized) return null;
1121        if (impassable == null)
1122            impassable = new LinkedHashSet<>();
1123        LinkedHashMap<Coord, Double> blocking = new LinkedHashMap<>(impassable.size());
1124        for (Coord pt : impassable) {
1125            blocking.put(pt, WALL);
1126            for (int x = 0; x < size; x++) {
1127                for (int y = 0; y < size; y++) {
1128                    if (x + y == 0)
1129                        continue;
1130                    if (gradientMap[pt.x - x][pt.y - y] <= FLOOR)
1131                        blocking.put(Coord.get(pt.x - x, pt.y - y), DARK);
1132                }
1133            }
1134        }
1135        closed.putAll(blocking);
1136
1137        for (Map.Entry<Coord, Double> entry : goals.entrySet()) {
1138            if (closed.containsKey(entry.getKey()))
1139                closed.remove(entry.getKey());
1140            gradientMap[entry.getKey().x][entry.getKey().y] = entry.getValue();
1141        }
1142        mappedCount = goals.size();
1143        double currentLowest = 999000;
1144        LinkedHashMap<Coord, Double> lowest = new LinkedHashMap<>();
1145        Coord p = Coord.get(0, 0), temp = Coord.get(0, 0);
1146        for (int y = 0; y < height; y++) {
1147            I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS:
1148            for (int x = 0; x < width; x++) {
1149                p = Coord.get(x, y);
1150                if (gradientMap[x][y] > FLOOR && !goals.containsKey(p)) {
1151                    closed.put(p, physicalMap[x][y]);
1152                    if (gradientMap[x][y] == WALL) {
1153                        for (int i = 0; i < size; i++) {
1154                            if (x - i < 0)
1155                                continue;
1156                            for (int j = 0; j < size; j++) {
1157                                temp = Coord.get(x - i, y - j);
1158                                if (y - j < 0 || closed.containsKey(temp))
1159                                    continue;
1160                                if (gradientMap[temp.x][temp.y] <= FLOOR && !goals.containsKey(temp))
1161                                    closed.put(Coord.get(temp.x, temp.y), DARK);
1162                            }
1163                        }
1164                    }
1165                } else if (gradientMap[x][y] < currentLowest && !closed.containsKey(p)) {
1166                    for (int i = 0; i < size; i++) {
1167                        if (x + i >= width)
1168                            continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS;
1169                        for (int j = 0; j < size; j++) {
1170                            temp = Coord.get(x + i, y + j);
1171                            if (y + j >= height || closed.containsKey(temp))
1172                                continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS;
1173                        }
1174                    }
1175
1176                    currentLowest = gradientMap[x][y];
1177                    lowest.clear();
1178                    lowest.put(Coord.get(x, y), currentLowest);
1179
1180                } else if (gradientMap[x][y] == currentLowest && !closed.containsKey(p)) {
1181                    if (!closed.containsKey(p)) {
1182                        for (int i = 0; i < size; i++) {
1183                            if (x + i >= width)
1184                                continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS;
1185                            for (int j = 0; j < size; j++) {
1186                                temp = Coord.get(x + i, y + j);
1187                                if (y + j >= height || closed.containsKey(temp))
1188                                    continue I_AM_BECOME_DEATH_DESTROYER_OF_WORLDS;
1189                            }
1190                        }
1191                        lowest.put(Coord.get(x, y), currentLowest);
1192                    }
1193                }
1194            }
1195        }
1196        int numAssigned = lowest.size();
1197        open.putAll(lowest);
1198        Direction[] dirs = (measurement == Measurement.MANHATTAN) ? Direction.CARDINALS : Direction.OUTWARDS;
1199        while (numAssigned > 0) {
1200            numAssigned = 0;
1201            for (Map.Entry<Coord, Double> cell : open.entrySet()) {
1202                for (int d = 0; d < dirs.length; d++) {
1203                    Coord adj = cell.getKey().translate(dirs[d].deltaX, dirs[d].deltaY);
1204                    double h = heuristic(dirs[d]);
1205                    if (!closed.containsKey(adj) && !open.containsKey(adj) && gradientMap[cell.getKey().x][cell.getKey().y] + h * costMap[adj.x][adj.y] < gradientMap[adj.x][adj.y]) {
1206                        setFresh(adj, cell.getValue() + h * costMap[adj.x][adj.y]);
1207                        ++numAssigned;
1208                        ++mappedCount;
1209                    }
1210                }
1211            }
1212//            closed.putAll(open);
1213            open = new LinkedHashMap<>(fresh);
1214            fresh.clear();
1215        }
1216        closed.clear();
1217        open.clear();
1218
1219
1220        double[][] gradientClone = new double[width][height];
1221        for (int x = 0; x < width; x++) {
1222            for (int y = 0; y < height; y++) {
1223                if (gradientMap[x][y] == FLOOR) {
1224                    gradientMap[x][y] = DARK;
1225                }
1226            }
1227            System.arraycopy(gradientMap[x], 0, gradientClone[x], 0, height);
1228        }
1229        return gradientClone;
1230    }
1231
1232    /**
1233     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
1234     * of Coord positions (using the current measurement) needed to get closer to the closest reachable
1235     * goal. The maximum length of the returned list is given by length; if moving the full length of
1236     * the list would place the mover in a position shared by one of the positions in onlyPassable
1237     * (which is typically filled with friendly units that can be passed through in multi-tile-
1238     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
1239     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1240     * through, and will be ignored if there is a goal overlapping one.
1241     * <br>
1242     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1243     * each call to a pathfinding method.
1244     * @param length       the length of the path to calculate
1245     * @param impassable   a Set of impassable Coord positions that may change (not constant like walls); can be null
1246     * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
1247     * @param start        the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
1248     * @param targets      a vararg or array of Coord that this will try to pathfind toward
1249     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
1250     */
1251    public ArrayList<Coord> findPath(int length, Set<Coord> impassable,
1252                                     Set<Coord> onlyPassable, Coord start, Coord... targets) {
1253        if (!initialized) return null;
1254        path.clear();
1255        LinkedHashSet<Coord> impassable2;
1256        if (impassable == null)
1257            impassable2 = new LinkedHashSet<>();
1258        else
1259            impassable2 = new LinkedHashSet<>(impassable);
1260        if (onlyPassable == null)
1261            onlyPassable = new LinkedHashSet<>();
1262
1263        resetMap();
1264        for (Coord goal : targets) {
1265            setGoal(goal.x, goal.y);
1266        }
1267        if (goals.isEmpty())
1268            return new ArrayList<>(path);
1269        scan(impassable2);
1270        Coord currentPos = start;
1271        double paidLength = 0.0;
1272        while (true) {
1273            if (frustration > 500) {
1274                path.clear();
1275                break;
1276            }
1277            double best = gradientMap[currentPos.x][currentPos.y];
1278            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
1279            int choice = rng.nextInt(dirs.length);
1280
1281            for (int d = 0; d < dirs.length; d++) {
1282                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
1283                if (gradientMap[pt.x][pt.y] < best) {
1284                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
1285                        best = gradientMap[pt.x][pt.y];
1286                        choice = d;
1287                    }
1288                }
1289            }
1290
1291            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
1292                path.clear();
1293                break;
1294            }
1295            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
1296            path.add(currentPos);
1297            paidLength += costMap[currentPos.x][currentPos.y];
1298            frustration++;
1299            if (paidLength > length - 1.0) {
1300                if (onlyPassable.contains(currentPos)) {
1301
1302                    closed.put(currentPos, WALL);
1303                    impassable2.add(currentPos);
1304                    return findPath(length, impassable2, onlyPassable, start, targets);
1305                }
1306                break;
1307            }
1308            if (gradientMap[currentPos.x][currentPos.y] == 0)
1309                break;
1310        }
1311        frustration = 0;
1312        goals.clear();
1313        return new ArrayList<>(path);
1314    }
1315
1316    /**
1317     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
1318     * of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is
1319     * reached, or further from a goal if the preferredRange has not been met at the current distance.
1320     * The maximum length of the returned list is given by moveLength; if moving the full length of
1321     * the list would place the mover in a position shared by one of the positions in onlyPassable
1322     * (which is typically filled with friendly units that can be passed through in multi-tile-
1323     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
1324     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1325     * through, and will be ignored if there is a goal overlapping one.
1326     * <br>
1327     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1328     * each call to a pathfinding method.
1329     *
1330     * @param moveLength     the length of the path to calculate
1331     * @param preferredRange the distance this unit will try to keep from a target
1332     * @param los            a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS
1333     *                       should be disregarded.
1334     * @param impassable     a Set of impassable Coord positions that may change (not constant like walls); can be null
1335     * @param onlyPassable   a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
1336     * @param start          the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
1337     * @param targets        a vararg or array of Coord that this will try to pathfind toward
1338     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
1339     */
1340    public ArrayList<Coord> findAttackPath(int moveLength, int preferredRange, LOS los, Set<Coord> impassable,
1341                                           Set<Coord> onlyPassable, Coord start, Coord... targets) {
1342        return findAttackPath(moveLength, preferredRange, preferredRange, los, impassable, onlyPassable, start, targets);
1343    }
1344
1345    /**
1346     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
1347     * of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with
1348     * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange,
1349     * which may go further from a goal if the minPreferredRange has not been met at the current distance.
1350     * The maximum length of the returned list is given by moveLength; if moving the full length of
1351     * the list would place the mover in a position shared by one of the positions in onlyPassable
1352     * (which is typically filled with friendly units that can be passed through in multi-tile-
1353     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
1354     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1355     * through, and will be ignored if there is a goal overlapping one.
1356     * <br>
1357     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1358     * each call to a pathfinding method.
1359     *
1360     * @param moveLength        the length of the path to calculate
1361     * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target
1362     * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target
1363     * @param los               a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS
1364     *                          should be disregarded.
1365     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
1366     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
1367     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
1368     * @param targets           a vararg or array of Coord that this will try to pathfind toward
1369     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
1370     */
1371    public ArrayList<Coord> findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, LOS los,
1372                                           Set<Coord> impassable, Set<Coord> onlyPassable, Coord start, Coord... targets) {
1373        if (!initialized) return null;
1374        if (minPreferredRange < 0) minPreferredRange = 0;
1375        if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange;
1376        double[][] resMap = new double[width][height];
1377        if (los != null) {
1378            for (int x = 0; x < width; x++) {
1379                for (int y = 0; y < height; y++) {
1380                    resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
1381                }
1382            }
1383        }
1384        path.clear();
1385        LinkedHashSet<Coord> impassable2;
1386        if (impassable == null)
1387            impassable2 = new LinkedHashSet<>();
1388        else
1389            impassable2 = new LinkedHashSet<>(impassable);
1390        if (onlyPassable == null)
1391            onlyPassable = new LinkedHashSet<>();
1392
1393        resetMap();
1394        for (Coord goal : targets) {
1395            setGoal(goal.x, goal.y);
1396        }
1397        if (goals.isEmpty())
1398            return new ArrayList<>(path);
1399
1400        Measurement mess = measurement;
1401        if (measurement == Measurement.EUCLIDEAN) {
1402            measurement = Measurement.CHEBYSHEV;
1403        }
1404        scan(impassable2);
1405        goals.clear();
1406
1407        for (int x = 0; x < width; x++) {
1408            CELL:
1409            for (int y = 0; y < height; y++) {
1410                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
1411                    continue;
1412                if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) {
1413
1414                    for (Coord goal : targets) {
1415                        if (los == null || los.isReachable(resMap, x, y, goal.x, goal.y)) {
1416                            setGoal(x, y);
1417                            gradientMap[x][y] = 0;
1418                            continue CELL;
1419                        }
1420                    }
1421                    gradientMap[x][y] = FLOOR;
1422                } else
1423                    gradientMap[x][y] = FLOOR;
1424            }
1425        }
1426        measurement = mess;
1427        scan(impassable2);
1428
1429        Coord currentPos = start;
1430        double paidLength = 0.0;
1431        while (true) {
1432            if (frustration > 500) {
1433                path.clear();
1434                break;
1435            }
1436            double best = gradientMap[currentPos.x][currentPos.y];
1437            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
1438            int choice = rng.nextInt(dirs.length);
1439
1440            for (int d = 0; d < dirs.length; d++) {
1441                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
1442                if (gradientMap[pt.x][pt.y] < best) {
1443                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
1444                        best = gradientMap[pt.x][pt.y];
1445                        choice = d;
1446                    }
1447                }
1448            }
1449
1450            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
1451                path.clear();
1452                break;
1453            }
1454            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
1455            path.add(Coord.get(currentPos.x, currentPos.y));
1456            paidLength += costMap[currentPos.x][currentPos.y];
1457            frustration++;
1458            if (paidLength > moveLength - 1.0) {
1459
1460                if (onlyPassable.contains(currentPos)) {
1461
1462                    closed.put(currentPos, WALL);
1463                    impassable2.add(currentPos);
1464                    return findAttackPath(moveLength, minPreferredRange, maxPreferredRange, los, impassable2,
1465                            onlyPassable, start, targets);
1466                }
1467                break;
1468            }
1469            if (gradientMap[currentPos.x][currentPos.y] == 0)
1470                break;
1471        }
1472        frustration = 0;
1473        goals.clear();
1474        return new ArrayList<>(path);
1475    }
1476
1477    /**
1478     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
1479     * of Coord positions (using the current measurement) needed to get closer to a goal, where goals are
1480     * considered valid if they are at a valid range for the given Technique to hit at least one target
1481     * and ideal if that Technique can affect as many targets as possible from a cell that can be moved
1482     * to with at most movelength steps.
1483     * <br>
1484     * The return value of this method is the path to get to a location to attack, but on its own it
1485     * does not tell the user how to perform the attack.  It does set the targetMap 2D Coord array field
1486     * so that if your position at the end of the returned path is non-null in targetMap, it will be
1487     * a Coord that can be used as a target position for Technique.apply() . If your position at the end
1488     * of the returned path is null, then an ideal attack position was not reachable by the path.
1489     * <br>
1490     * This needs a char[][] dungeon as an argument because DijkstraMap does not always have a char[][]
1491     * version of the map available to it, and certain AOE implementations that a Technique uses may
1492     * need a char[][] specifically to determine what they affect.
1493     * <br>
1494     * The maximum length of the returned list is given by moveLength; if moving the full length of
1495     * the list would place the mover in a position shared by one of the positions in allies
1496     * (which is typically filled with friendly units that can be passed through in multi-tile-
1497     * movement scenarios, and is also used considered an undesirable thing to affect for the Technique),
1498     * it will recalculate a move so that it does not pass into that cell.
1499     * <br>
1500     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1501     * through, and will be ignored if there is a target overlapping one.
1502     * <br>
1503     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1504     * each call to a pathfinding method.
1505     *
1506     * @param moveLength the maximum distance to try to pathfind out to; if a spot to use a Technique can be found
1507     *                   while moving no more than this distance, then the targetMap field in this object will have a
1508     *                   target Coord that is ideal for the given Technique at the x, y indices corresponding to the
1509     *                   last Coord in the returned path.
1510     * @param tech       a Technique that we will try to find an ideal place to use, and/or a path toward that place.
1511     * @param dungeon    a char 2D array with '#' for walls.
1512     * @param los        a squidgrid.LOS object if the preferred range should try to stay in line of sight, or null if LoS
1513     *                   should be disregarded.
1514     * @param impassable locations of enemies or mobile hazards/obstacles that aren't in the map as walls
1515     * @param allies     called onlyPassable in other methods, here it also represents allies for Technique things
1516     * @param start      the Coord the pathfinder starts at.
1517     * @param targets    a Set of Coord, not an array of Coord or variable argument list as in other methods.
1518     * @return an ArrayList of Coord that represents a path to travel to get to an ideal place to use tech. Copy of path.
1519     */
1520    public ArrayList<Coord> findTechniquePath(int moveLength, Technique tech, char[][] dungeon, LOS los,
1521                                              Set<Coord> impassable, Set<Coord> allies, Coord start, Set<Coord> targets) {
1522        if (!initialized) return null;
1523        tech.setMap(dungeon);
1524        double[][] resMap = new double[width][height];
1525        double[][] worthMap = new double[width][height];
1526        double[][] userDistanceMap;
1527        double paidLength = 0.0;
1528
1529        LinkedHashSet<Coord> friends;
1530
1531
1532        for (int x = 0; x < width; x++) {
1533            for (int y = 0; y < height; y++) {
1534                resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
1535                targetMap[x][y] = null;
1536            }
1537        }
1538
1539        path.clear();
1540        if (targets == null || targets.size() == 0)
1541            return new ArrayList<>(path);
1542        LinkedHashSet<Coord> impassable2;
1543        if (impassable == null)
1544            impassable2 = new LinkedHashSet<>();
1545        else
1546            impassable2 = new LinkedHashSet<>(impassable);
1547
1548        if (allies == null)
1549            friends = new LinkedHashSet<>();
1550        else {
1551            friends = new LinkedHashSet<>(allies);
1552            friends.remove(start);
1553        }
1554
1555        resetMap();
1556        setGoal(start);
1557        userDistanceMap = scan(impassable2);
1558        clearGoals();
1559        resetMap();
1560        for (Coord goal : targets) {
1561            setGoal(goal.x, goal.y);
1562        }
1563        if (goals.isEmpty())
1564            return new ArrayList<>(path);
1565
1566        Measurement mess = measurement;
1567        /*
1568        if(measurement == Measurement.EUCLIDEAN)
1569        {
1570            measurement = Measurement.CHEBYSHEV;
1571        }
1572        */
1573        scan(impassable2);
1574        clearGoals();
1575
1576        Coord tempPt = Coord.get(0, 0);
1577        LinkedHashMap<Coord, ArrayList<Coord>> ideal;
1578        // generate an array of the single best location to attack when you are in a given cell.
1579        for (int x = 0; x < width; x++) {
1580            CELL:
1581            for (int y = 0; y < height; y++) {
1582                tempPt = Coord.get(x, y);
1583                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK || userDistanceMap[x][y] > moveLength * 2.0)
1584                    continue;
1585                if (gradientMap[x][y] >= tech.aoe.getMinRange() && gradientMap[x][y] <= tech.aoe.getMaxRange()) {
1586                    for (Coord tgt : targets) {
1587                        if (los == null || los.isReachable(resMap, x, y, tgt.x, tgt.y)) {
1588                            ideal = tech.idealLocations(tempPt, targets, friends);
1589                            // this is weird but it saves the trouble of getting the iterator and checking hasNext() .
1590                            for (Map.Entry<Coord, ArrayList<Coord>> ip : ideal.entrySet()) {
1591                                targetMap[x][y] = ip.getKey();
1592                                worthMap[x][y] = ip.getValue().size();
1593                                setGoal(x, y);
1594                                gradientMap[x][y] = 0;
1595                                break;
1596                            }
1597                            continue CELL;
1598                        }
1599                    }
1600                    gradientMap[x][y] = FLOOR;
1601                } else
1602                    gradientMap[x][y] = FLOOR;
1603            }
1604        }
1605        scan(impassable2);
1606
1607        double currentDistance = gradientMap[start.x][start.y];
1608        if (currentDistance <= moveLength) {
1609            Coord[] g_arr = new Coord[goals.size()];
1610            g_arr = goals.keySet().toArray(g_arr);
1611
1612            goals.clear();
1613            setGoal(start);
1614            scan(impassable2);
1615            goals.clear();
1616            gradientMap[start.x][start.y] = moveLength;
1617
1618            for (Coord g : g_arr) {
1619                if (gradientMap[g.x][g.y] <= moveLength && worthMap[g.x][g.y] > 0) {
1620                    goals.put(g, 0.0 - worthMap[g.x][g.y]);
1621                }
1622            }
1623            resetMap();
1624           /* for(Coord g : goals.keySet())
1625            {
1626                gradientMap[g.x][g.y] = 0.0 - worthMap[g.x][g.y];
1627            }*/
1628            scan(impassable2);
1629
1630        }
1631
1632        measurement = mess;
1633
1634        Coord currentPos = Coord.get(start.x, start.y);
1635        while (true) {
1636            if (frustration > 500) {
1637                path.clear();
1638                break;
1639            }
1640            double best = gradientMap[currentPos.x][currentPos.y];
1641            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
1642            int choice = rng.nextInt(dirs.length);
1643
1644            for (int d = 0; d < dirs.length; d++) {
1645                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
1646                if (gradientMap[pt.x][pt.y] < best) {
1647                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
1648                        best = gradientMap[pt.x][pt.y];
1649                        choice = d;
1650                    }
1651                }
1652            }
1653            if (best >= gradientMap[currentPos.x][currentPos.y]) {
1654                if (friends.contains(currentPos)) {
1655                    closed.put(currentPos, WALL);
1656                    impassable2.add(currentPos);
1657                    return findTechniquePath(moveLength, tech, dungeon, los, impassable2,
1658                            friends, start, targets);
1659                }
1660                break;
1661            }
1662            if (best > gradientMap[start.x][start.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
1663                path.clear();
1664                break;
1665            }
1666            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
1667            path.add(currentPos);
1668            paidLength += costMap[currentPos.x][currentPos.y];
1669            frustration++;
1670            if (paidLength > moveLength - 1.0) {
1671                if (friends.contains(currentPos)) {
1672                    closed.put(currentPos, WALL);
1673                    impassable2.add(currentPos);
1674                    return findTechniquePath(moveLength, tech, dungeon, los, impassable2,
1675                            friends, start, targets);
1676                }
1677                break;
1678            }
1679//            if(gradientMap[currentPos.x][currentPos.y] == 0)
1680//                break;
1681        }
1682        frustration = 0;
1683        goals.clear();
1684        return new ArrayList<>(path);
1685    }
1686
1687
1688    /**
1689     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
1690     * of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is
1691     * reached, or further from a goal if the preferredRange has not been met at the current distance.
1692     * The maximum length of the returned list is given by moveLength; if moving the full length of
1693     * the list would place the mover in a position shared by one of the positions in onlyPassable
1694     * (which is typically filled with friendly units that can be passed through in multi-tile-
1695     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
1696     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1697     * through, and will be ignored if there is a goal overlapping one.
1698     * <br>
1699     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1700     * each call to a pathfinding method.
1701     *
1702     * @param moveLength     the length of the path to calculate
1703     * @param preferredRange the distance this unit will try to keep from a target
1704     * @param cache          a FOVCache that has completed its calculations, and will be used for LOS work, may be null
1705     * @param impassable     a Set of impassable Coord positions that may change (not constant like walls); can be null
1706     * @param onlyPassable   a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
1707     * @param start          the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
1708     * @param targets        a vararg or array of Coord that this will try to pathfind toward
1709     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
1710     */
1711    @GwtIncompatible
1712    public ArrayList<Coord> findAttackPath(int moveLength, int preferredRange, FOVCache cache, Set<Coord> impassable,
1713                                           Set<Coord> onlyPassable, Coord start, Coord... targets) {
1714        return findAttackPath(moveLength, preferredRange, preferredRange, cache, impassable, onlyPassable, start, targets);
1715    }
1716
1717    /**
1718     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
1719     * of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with
1720     * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange,
1721     * which may go further from a goal if the minPreferredRange has not been met at the current distance.
1722     * The maximum length of the returned list is given by moveLength; if moving the full length of
1723     * the list would place the mover in a position shared by one of the positions in onlyPassable
1724     * (which is typically filled with friendly units that can be passed through in multi-tile-
1725     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
1726     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1727     * through, and will be ignored if there is a goal overlapping one.
1728     * <br>
1729     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1730     * each call to a pathfinding method.
1731     *
1732     * @param moveLength        the length of the path to calculate
1733     * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target
1734     * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target
1735     * @param cache             a FOVCache that has completed its calculations, and will be used for LOS work, may be null
1736     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
1737     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
1738     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
1739     * @param targets           a vararg or array of Coord that this will try to pathfind toward
1740     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
1741     */
1742    @GwtIncompatible
1743    public ArrayList<Coord> findAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange, FOVCache cache,
1744                                           Set<Coord> impassable, Set<Coord> onlyPassable, Coord start, Coord... targets) {
1745        if (!initialized) return null;
1746        if (minPreferredRange < 0) minPreferredRange = 0;
1747        if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange;
1748
1749        path.clear();
1750        LinkedHashSet<Coord> impassable2;
1751        if (impassable == null)
1752            impassable2 = new LinkedHashSet<>();
1753        else
1754            impassable2 = new LinkedHashSet<>(impassable);
1755        if (onlyPassable == null)
1756            onlyPassable = new LinkedHashSet<>();
1757
1758        resetMap();
1759        for (Coord goal : targets) {
1760            setGoal(goal.x, goal.y);
1761        }
1762        if (goals.isEmpty())
1763            return new ArrayList<>(path);
1764
1765        Measurement mess = measurement;
1766        if (measurement == Measurement.EUCLIDEAN) {
1767            measurement = Measurement.CHEBYSHEV;
1768        }
1769        scan(impassable2);
1770        goals.clear();
1771
1772        for (int x = 0; x < width; x++) {
1773            CELL:
1774            for (int y = 0; y < height; y++) {
1775                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
1776                    continue;
1777                if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) {
1778
1779                    for (Coord goal : targets) {
1780                        if (cache == null || cache.queryLOS(x, y, goal.x, goal.y)) {
1781                            setGoal(x, y);
1782                            gradientMap[x][y] = 0;
1783                            continue CELL;
1784                        }
1785                    }
1786                    gradientMap[x][y] = FLOOR;
1787                } else
1788                    gradientMap[x][y] = FLOOR;
1789            }
1790        }
1791        measurement = mess;
1792        scan(impassable2);
1793
1794        Coord currentPos = start;
1795        double paidLength = 0.0;
1796        while (true) {
1797            if (frustration > 500) {
1798                path.clear();
1799                break;
1800            }
1801            double best = gradientMap[currentPos.x][currentPos.y];
1802            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
1803            int choice = rng.nextInt(dirs.length);
1804
1805            for (int d = 0; d < dirs.length; d++) {
1806                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
1807                if (gradientMap[pt.x][pt.y] < best) {
1808                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
1809                        best = gradientMap[pt.x][pt.y];
1810                        choice = d;
1811                    }
1812                }
1813            }
1814
1815            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
1816                path.clear();
1817                break;
1818            }
1819            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
1820            path.add(Coord.get(currentPos.x, currentPos.y));
1821            paidLength += costMap[currentPos.x][currentPos.y];
1822            frustration++;
1823            if (paidLength > moveLength - 1.0) {
1824
1825                if (onlyPassable.contains(currentPos)) {
1826
1827                    closed.put(currentPos, WALL);
1828                    impassable2.add(currentPos);
1829                    return findAttackPath(moveLength, minPreferredRange, maxPreferredRange, cache, impassable2,
1830                            onlyPassable, start, targets);
1831                }
1832                break;
1833            }
1834            if (gradientMap[currentPos.x][currentPos.y] == 0)
1835                break;
1836        }
1837        frustration = 0;
1838        goals.clear();
1839        return new ArrayList<>(path);
1840    }
1841
1842    /**
1843     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord
1844     * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the
1845     * given threats are able to see (which should prevent them from attacking), until a cell is reached with
1846     * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange,
1847     * which may go further from a goal if the minPreferredRange has not been met at the current distance.
1848     * <p/>
1849     * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being
1850     * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes
1851     * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()).
1852     * <p/>
1853     * The maximum length of the returned list is given by moveLength; if moving the full length of
1854     * the list would place the mover in a position shared by one of the positions in onlyPassable
1855     * (which is typically filled with friendly units that can be passed through in multi-tile-
1856     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
1857     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
1858     * through, and will be ignored if there is a goal overlapping one.
1859     * <br>
1860     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
1861     * each call to a pathfinding method.
1862     *
1863     * @param moveLength        the length of the path to calculate
1864     * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target
1865     * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target
1866     * @param coverPreference positive, typically around 1.0, higher numbers make the pathfinder stay behind cover
1867     *                        more, lower numbers make the pathfinder move more aggressively toward targets
1868     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
1869     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
1870     * @param threats           a List of Threat objects that store a position, min and max threatening distance
1871     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
1872     * @param targets           a vararg or array of Coord that this will try to pathfind toward
1873     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
1874     */
1875    public ArrayList<Coord> findCoveredAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange,
1876                                                  double coverPreference, Set<Coord> impassable,
1877                                                  Set<Coord> onlyPassable, List<Threat> threats, Coord start,
1878                                                  Coord... targets) {
1879        if (!initialized) return null;
1880
1881        if (minPreferredRange < 0) minPreferredRange = 0;
1882        if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange;
1883        double[][] resMap = new double[width][height];
1884
1885        for (int x = 0; x < width; x++) {
1886            for (int y = 0; y < height; y++) {
1887                resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
1888            }
1889        }
1890
1891
1892        path = new ArrayList<Coord>();
1893        LinkedHashSet<Coord> impassable2;
1894        if (impassable == null)
1895            impassable2 = new LinkedHashSet<Coord>();
1896        else
1897            impassable2 = new LinkedHashSet<Coord>(impassable);
1898        if (onlyPassable == null)
1899            onlyPassable = new LinkedHashSet<Coord>();
1900
1901        resetMap();
1902        for (Coord goal : targets) {
1903            setGoal(goal.x, goal.y);
1904        }
1905        if (goals.isEmpty())
1906            return new ArrayList<>(path);
1907
1908        Measurement mess = measurement;
1909        if (measurement == Measurement.EUCLIDEAN) {
1910            measurement = Measurement.CHEBYSHEV;
1911        }
1912        scan(impassable2);
1913        goals.clear();
1914        LinkedHashMap<Coord, Double> cachedGoals = new LinkedHashMap<Coord, Double>();
1915
1916        for (int x = 0; x < width; x++) {
1917            for (int y = 0; y < height; y++) {
1918                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
1919                    continue;
1920                if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) {
1921                    gradientMap[x][y] = 0.001 * (maxPreferredRange - gradientMap[x][y]);
1922                    cachedGoals.put(Coord.get(x, y), gradientMap[x][y]);
1923                } else
1924                    gradientMap[x][y] = FLOOR;
1925            }
1926        }
1927        measurement = mess;
1928        double[][] storedScan = scan(impassable2);
1929        if(storedScan[start.x][start.y] > moveLength) {
1930            clearGoals();
1931            resetMap();
1932            double[][] seen;
1933            short[] packed = CoordPacker.ALL_WALL, floors = CoordPacker.pack(physicalMap, FLOOR), tempPacked;
1934            for (Threat t : threats) {
1935                packed = CoordPacker.unionPacked(
1936                        packed, CoordPacker.reachable(floors, CoordPacker.packOne(t.position), t.reach));
1937
1938            }
1939            short[] unseen = CoordPacker.differencePacked(CoordPacker.rectangle(width, height),
1940                    CoordPacker.expand(packed, 1, width, height));
1941            Coord[] safe = CoordPacker.allPacked(unseen);
1942            for (int i = 0; i < safe.length; i++) {
1943                setGoal(safe[i]);
1944            }
1945            safetyMap = scan(impassable2);
1946            for (int x = 0; x < width; x++) {
1947                for (int y = 0; y < height; y++) {
1948                    if (storedScan[x][y] < FLOOR)
1949                    {
1950                        gradientMap[x][y] = storedScan[x][y] * 2.0 * (moveLength+1) + safetyMap[x][y] * coverPreference;
1951                    }
1952                    //safeMap[x][y] = Math.pow(safeMap[x][y] + safetyMap[x][y], 1.5);
1953                }
1954            }
1955            goals = cachedGoals;
1956            scan(impassable2);
1957
1958            //gradientMap = storedScan;
1959        }
1960        Coord currentPos = start;
1961        double paidLength = 0.0;
1962        while (true) {
1963            if (frustration > 500) {
1964                path = new ArrayList<Coord>();
1965                break;
1966            }
1967            double best = gradientMap[currentPos.x][currentPos.y];
1968            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
1969            int choice = rng.nextInt(dirs.length);
1970
1971            for (int d = 0; d < dirs.length; d++) {
1972                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
1973                if (gradientMap[pt.x][pt.y] < best) {
1974                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
1975                        best = gradientMap[pt.x][pt.y];
1976                        choice = d;
1977                    }
1978                }
1979            }
1980
1981            if (best >= gradientMap[currentPos.x][currentPos.y] ||
1982                    physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
1983                break;
1984            }
1985            currentPos = currentPos.translate(dirs[choice]);
1986            path.add(Coord.get(currentPos.x, currentPos.y));
1987            paidLength += costMap[currentPos.x][currentPos.y];
1988            frustration++;
1989            if(paidLength > moveLength - 1.0)
1990                break;
1991            if (gradientMap[currentPos.x][currentPos.y] == 0)
1992                break;
1993        }
1994        goals.clear();
1995        if (onlyPassable.contains(currentPos) || impassable2.contains(currentPos)) {
1996            closed.put(currentPos, WALL);
1997            impassable2.add(currentPos);
1998            return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference,
1999                    impassable2, onlyPassable, threats, start, targets);
2000        }
2001
2002        frustration = 0;
2003        return new ArrayList<>(path);
2004    }
2005
2006    /**
2007     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord
2008     * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the
2009     * given threats are able to see (which should prevent them from attacking), until a cell is reached with
2010     * a distance from a goal that is at equal to preferredRange,
2011     * which may go further from a goal if the preferredRange has not been met at the current distance.
2012     * <p/>
2013     * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being
2014     * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes
2015     * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()).
2016     * <p/>
2017     * The maximum length of the returned list is given by moveLength; if moving the full length of
2018     * the list would place the mover in a position shared by one of the positions in onlyPassable
2019     * (which is typically filled with friendly units that can be passed through in multi-tile-
2020     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2021     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2022     * through, and will be ignored if there is a goal overlapping one.
2023     * <br>
2024     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2025     * each call to a pathfinding method.
2026     *
2027     * @param moveLength     the length of the path to calculate
2028     * @param preferredRange the distance this unit will try to keep from a target
2029     * @param fov            a FOV that will be used for LOS work, must not be null
2030     * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding
2031     * @param impassable     a Set of impassable Coord positions that may change (not constant like walls); can be null
2032     * @param onlyPassable   a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2033     * @param threats        a List of Threat objects that store a position, min and max threatening distance
2034     * @param start          the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2035     * @param targets        a vararg or array of Coord that this will try to pathfind toward
2036     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
2037     */
2038    public ArrayList<Coord> findCoveredAttackPath(int moveLength, int preferredRange, double coverPreference,
2039                                                  FOV fov, boolean seekDistantGoals, Set<Coord> impassable,
2040                                                  Set<Coord> onlyPassable, List<Threat> threats, Coord start,
2041                                                  Coord... targets) {
2042        return findCoveredAttackPath(moveLength, preferredRange, preferredRange, coverPreference, fov,
2043                seekDistantGoals, impassable, onlyPassable, threats, start, targets);
2044    }
2045
2046    /**
2047     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord
2048     * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the
2049     * given threats are able to see (which should prevent them from attacking), until a cell is reached with
2050     * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange,
2051     * which may go further from a goal if the minPreferredRange has not been met at the current distance.
2052     * <p/>
2053     * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being
2054     * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes
2055     * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()).
2056     * <p/>
2057     * The maximum length of the returned list is given by moveLength; if moving the full length of
2058     * the list would place the mover in a position shared by one of the positions in onlyPassable
2059     * (which is typically filled with friendly units that can be passed through in multi-tile-
2060     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2061     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2062     * through, and will be ignored if there is a goal overlapping one.
2063     * <br>
2064     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2065     * each call to a pathfinding method.
2066     *
2067     * @param moveLength        the length of the path to calculate
2068     * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target
2069     * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target
2070     * @param coverPreference positive, typically around 1.0, higher numbers make the pathfinder stay behind cover
2071     *                        more, lower numbers make the pathfinder move more aggressively toward targets
2072     * @param fov               a FOV that will be used for LOS work, MUST NOT be null
2073     * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding
2074     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
2075     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2076     * @param threats           a List of Threat objects that store a position, min and max threatening distance
2077     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2078     * @param targets           a vararg or array of Coord that this will try to pathfind toward
2079     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
2080     */
2081    public ArrayList<Coord> findCoveredAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange,
2082                                                  double coverPreference, FOV fov, boolean seekDistantGoals, Set<Coord> impassable,
2083                                                  Set<Coord> onlyPassable, List<Threat> threats, Coord start,
2084                                                  Coord... targets) {
2085        if (!initialized) return null;
2086        if(fov == null) {
2087            return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference,
2088                    impassable, onlyPassable, threats, start, targets);
2089        }
2090        if (minPreferredRange < 0) minPreferredRange = 0;
2091        if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange;
2092        double[][] resMap = new double[width][height];
2093
2094        for (int x = 0; x < width; x++) {
2095            for (int y = 0; y < height; y++) {
2096                resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
2097            }
2098        }
2099
2100
2101        path = new ArrayList<Coord>();
2102        LinkedHashSet<Coord> impassable2;
2103        if (impassable == null)
2104            impassable2 = new LinkedHashSet<Coord>();
2105        else
2106            impassable2 = new LinkedHashSet<Coord>(impassable);
2107        if (onlyPassable == null)
2108            onlyPassable = new LinkedHashSet<Coord>();
2109
2110        resetMap();
2111        for (Coord goal : targets) {
2112            setGoal(goal.x, goal.y);
2113        }
2114        if (goals.isEmpty())
2115            return new ArrayList<>(path);
2116
2117        Measurement mess = measurement;
2118        if (measurement == Measurement.EUCLIDEAN) {
2119            measurement = Measurement.CHEBYSHEV;
2120        }
2121        scan(impassable2);
2122        goals.clear();
2123        LinkedHashMap<Coord, Double> cachedGoals = new LinkedHashMap<Coord, Double>();
2124
2125        for (int x = 0; x < width; x++) {
2126            CELL:
2127            for (int y = 0; y < height; y++) {
2128                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
2129                    continue;
2130                if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) {
2131
2132                    double[][] results = new double[width][height];
2133                    if (!seekDistantGoals)
2134                        results = fov.calculateFOV(resMap, x, y, maxPreferredRange, findRadius(mess));
2135                    for (Coord goal : targets) {
2136                        if (seekDistantGoals || results[goal.x][goal.y] > 0.0) {
2137                            gradientMap[x][y] = 0.001 * (maxPreferredRange - gradientMap[x][y]);
2138                            cachedGoals.put(Coord.get(x, y), gradientMap[x][y]);
2139                            continue CELL;
2140                        }
2141                    }
2142                    gradientMap[x][y] = FLOOR;
2143                } else
2144                    gradientMap[x][y] = FLOOR;
2145            }
2146        }
2147        measurement = mess;
2148        double[][] storedScan = scan(impassable2);
2149        if(storedScan[start.x][start.y] > moveLength) {
2150            clearGoals();
2151            resetMap();
2152            double[][] seen;
2153            short[] packed = CoordPacker.ALL_WALL, tempPacked;
2154            for (Threat t : threats) {
2155                seen = fov.calculateFOV(resMap, t.position.x, t.position.y, t.reach.maxDistance, findRadius(measurement));
2156                tempPacked = CoordPacker.pack(seen);
2157
2158                if (t.reach.minDistance > 0) {
2159
2160                    seen = fov.calculateFOV(resMap, t.position.x, t.position.y, t.reach.minDistance, findRadius(measurement));
2161                    tempPacked = CoordPacker.differencePacked(tempPacked, CoordPacker.pack(seen));
2162
2163                }
2164                packed = CoordPacker.unionPacked(packed, tempPacked);
2165            }
2166            short[] unseen = CoordPacker.differencePacked(CoordPacker.rectangle(width, height),
2167                    CoordPacker.expand(packed, 1, width, height));
2168            Coord[] safe = CoordPacker.allPacked(unseen);
2169            for (int i = 0; i < safe.length; i++) {
2170                setGoal(safe[i]);
2171            }
2172            safetyMap = scan(impassable2);
2173            for (int x = 0; x < width; x++) {
2174                for (int y = 0; y < height; y++) {
2175                    if (storedScan[x][y] < FLOOR)
2176                    {
2177                        gradientMap[x][y] = storedScan[x][y] * 2.0 * (moveLength+1) + safetyMap[x][y] * coverPreference;
2178                    }
2179                    //safeMap[x][y] = Math.pow(safeMap[x][y] + safetyMap[x][y], 1.5);
2180                }
2181            }
2182            goals = cachedGoals;
2183            scan(impassable2);
2184
2185            //gradientMap = storedScan;
2186        }
2187        Coord currentPos = start;
2188        double paidLength = 0.0;
2189        while (true) {
2190            if (frustration > 500) {
2191                path = new ArrayList<Coord>();
2192                break;
2193            }
2194            double best = gradientMap[currentPos.x][currentPos.y];
2195            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
2196            int choice = rng.nextInt(dirs.length);
2197
2198            for (int d = 0; d < dirs.length; d++) {
2199                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
2200                if (gradientMap[pt.x][pt.y] < best) {
2201                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
2202                        best = gradientMap[pt.x][pt.y];
2203                        choice = d;
2204                    }
2205                }
2206            }
2207
2208            if (best >= gradientMap[currentPos.x][currentPos.y] ||
2209                    physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
2210                break;
2211            }
2212            currentPos = currentPos.translate(dirs[choice]);
2213            path.add(Coord.get(currentPos.x, currentPos.y));
2214            paidLength += costMap[currentPos.x][currentPos.y];
2215            frustration++;
2216            if(paidLength > moveLength - 1.0)
2217                break;
2218            if (gradientMap[currentPos.x][currentPos.y] == 0)
2219                break;
2220        }
2221        goals.clear();
2222        if (onlyPassable.contains(currentPos) || impassable2.contains(currentPos)) {
2223            closed.put(currentPos, WALL);
2224            impassable2.add(currentPos);
2225            return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference,
2226                    fov, seekDistantGoals, impassable2, onlyPassable, threats, start, targets);
2227        }
2228
2229        frustration = 0;
2230        return new ArrayList<>(path);
2231    }
2232
2233    /**
2234     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord
2235     * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the
2236     * given threats are able to see (which should prevent them from attacking), until a cell is reached with
2237     * a distance from a goal that is at equal to preferredRange,
2238     * which may go further from a goal if the preferredRange has not been met at the current distance.
2239     * <p/>
2240     * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being
2241     * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes
2242     * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()).
2243     * <p/>
2244     * The maximum length of the returned list is given by moveLength; if moving the full length of
2245     * the list would place the mover in a position shared by one of the positions in onlyPassable
2246     * (which is typically filled with friendly units that can be passed through in multi-tile-
2247     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2248     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2249     * through, and will be ignored if there is a goal overlapping one.
2250     * <br>
2251     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2252     * each call to a pathfinding method.
2253     *
2254     * @param moveLength     the length of the path to calculate
2255     * @param preferredRange the distance this unit will try to keep from a target
2256     * @param fov            a FOVCache that has completed its calculations, and will be used for LOS work, may be null
2257     * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding
2258     * @param impassable     a Set of impassable Coord positions that may change (not constant like walls); can be null
2259     * @param onlyPassable   a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2260     * @param threats        a List of Threat objects that store a position, min and max threatening distance
2261     * @param start          the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2262     * @param targets        a vararg or array of Coord that this will try to pathfind toward
2263     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
2264     */
2265    @GwtIncompatible
2266    public ArrayList<Coord> findCoveredAttackPath(int moveLength, int preferredRange, double coverPreference,
2267                                                  FOVCache fov, boolean seekDistantGoals, Set<Coord> impassable,
2268                                                  Set<Coord> onlyPassable, List<Threat> threats, Coord start,
2269                                                  Coord... targets) {
2270        return findCoveredAttackPath(moveLength, preferredRange, preferredRange, coverPreference, fov,
2271                seekDistantGoals, impassable, onlyPassable, threats, start, targets);
2272    }
2273
2274    /**
2275     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list of Coord
2276     * positions (using the current measurement) needed to get closer to a goal while staying in areas that none of the
2277     * given threats are able to see (which should prevent them from attacking), until a cell is reached with
2278     * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange,
2279     * which may go further from a goal if the minPreferredRange has not been met at the current distance.
2280     * <p/>
2281     * Essentially, this method is for finding ways to approach enemies who can attack at range without constantly being
2282     * attacked by them. You are expected to call deteriorate() and possible relax() at points when a position becomes
2283     * riskier to stay at (then you call deteriorate()) or a position starts to seem like a safer place (then, relax()).
2284     * <p/>
2285     * The maximum length of the returned list is given by moveLength; if moving the full length of
2286     * the list would place the mover in a position shared by one of the positions in onlyPassable
2287     * (which is typically filled with friendly units that can be passed through in multi-tile-
2288     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2289     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2290     * through, and will be ignored if there is a goal overlapping one.
2291     * <br>
2292     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2293     * each call to a pathfinding method.
2294     *
2295     * @param moveLength        the length of the path to calculate
2296     * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target
2297     * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target
2298     * @param coverPreference positive, typically around 1.0, higher numbers make the pathfinder stay behind cover
2299     *                        more, lower numbers make the pathfinder move more aggressively toward targets
2300     * @param fov               a FOVCache that has completed its calculations, and will be used for LOS work
2301     * @param seekDistantGoals true if this should pathfind to goals that it cannot see, false if FOV restricts pathfinding
2302     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
2303     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2304     * @param threats           a List of Threat objects that store a position, min and max threatening distance
2305     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2306     * @param targets           a vararg or array of Coord that this will try to pathfind toward
2307     * @return an ArrayList of Coord that will contain the locations of this creature as it goes toward a target. Copy of path.
2308     */
2309    @GwtIncompatible
2310    public ArrayList<Coord> findCoveredAttackPath(int moveLength, int minPreferredRange, int maxPreferredRange,
2311                                                  double coverPreference, FOVCache fov, boolean seekDistantGoals, Set<Coord> impassable,
2312                                                  Set<Coord> onlyPassable, List<Threat> threats, Coord start,
2313                                                  Coord... targets) {
2314        if (!initialized) return null;
2315        if(fov == null) {
2316            return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference,
2317                    impassable, onlyPassable, threats, start, targets);
2318        }
2319
2320        if (minPreferredRange < 0) minPreferredRange = 0;
2321        if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange;
2322        double[][] resMap = new double[width][height];
2323
2324        for (int x = 0; x < width; x++) {
2325            for (int y = 0; y < height; y++) {
2326                resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
2327            }
2328        }
2329
2330        path.clear();
2331        LinkedHashSet<Coord> impassable2;
2332        if (impassable == null)
2333            impassable2 = new LinkedHashSet<>();
2334        else
2335            impassable2 = new LinkedHashSet<>(impassable);
2336        if (onlyPassable == null)
2337            onlyPassable = new LinkedHashSet<>();
2338
2339        resetMap();
2340        for (Coord goal : targets) {
2341            setGoal(goal.x, goal.y);
2342        }
2343        if (goals.isEmpty())
2344            return new ArrayList<>(path);
2345
2346        Measurement mess = measurement;
2347        if (measurement == Measurement.EUCLIDEAN) {
2348            measurement = Measurement.CHEBYSHEV;
2349        }
2350        scan(impassable2);
2351        goals.clear();
2352        LinkedHashMap<Coord, Double> cachedGoals = new LinkedHashMap<>();
2353
2354        for (int x = 0; x < width; x++) {
2355            CELL:
2356            for (int y = 0; y < height; y++) {
2357                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
2358                    continue;
2359                if (gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) {
2360
2361                    double[][] results = new double[width][height];
2362                    if (!seekDistantGoals)
2363                        results = fov.calculateFOV(resMap, x, y, maxPreferredRange, findRadius(mess));
2364                    for (Coord goal : targets) {
2365                        if (seekDistantGoals || results[goal.x][goal.y] > 0.0) {
2366                            gradientMap[x][y] = 0.001 * (maxPreferredRange - gradientMap[x][y]);
2367                            cachedGoals.put(Coord.get(x, y), gradientMap[x][y]);
2368                            continue CELL;
2369                        }
2370                    }
2371                    gradientMap[x][y] = FLOOR;
2372                } else
2373                    gradientMap[x][y] = FLOOR;
2374            }
2375        }
2376        measurement = mess;
2377        double[][] storedScan = scan(impassable2);
2378        if(storedScan[start.x][start.y] > moveLength) {
2379            clearGoals();
2380            resetMap();
2381            double[][] seen;
2382            short[] packed = CoordPacker.ALL_WALL, tempPacked;
2383            for (Threat t : threats) {
2384
2385                tempPacked = fov.getCacheEntry(t.position.x, t.position.y, t.reach.maxDistance);
2386
2387
2388                if (t.reach.minDistance > 0) {
2389                        tempPacked = CoordPacker.differencePacked(tempPacked,
2390                                fov.getCacheEntry(t.position.x, t.position.y, t.reach.minDistance));
2391                }
2392                packed = CoordPacker.unionPacked(packed, tempPacked);
2393            }
2394            short[] unseen = CoordPacker.differencePacked(CoordPacker.rectangle(width, height),
2395                    CoordPacker.expand(packed, 1, width, height));
2396            Coord[] safe = CoordPacker.allPacked(unseen);
2397            for (int i = 0; i < safe.length; i++) {
2398                setGoal(safe[i]);
2399            }
2400            safetyMap = scan(impassable2);
2401            for (int x = 0; x < width; x++) {
2402                for (int y = 0; y < height; y++) {
2403                    if (storedScan[x][y] < FLOOR)
2404                    {
2405                        gradientMap[x][y] = storedScan[x][y] * 2.0 * (moveLength+1) + safetyMap[x][y] * coverPreference;
2406                    }
2407                    //safeMap[x][y] = Math.pow(safeMap[x][y] + safetyMap[x][y], 1.5);
2408                }
2409            }
2410            goals = cachedGoals;
2411            scan(impassable2);
2412
2413            //gradientMap = storedScan;
2414        }
2415        Coord currentPos = start;
2416        double paidLength = 0.0;
2417        while (true) {
2418            if (frustration > 500) {
2419                path.clear();
2420                break;
2421            }
2422            double best = gradientMap[currentPos.x][currentPos.y];
2423            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
2424            int choice = rng.nextInt(dirs.length);
2425
2426            for (int d = 0; d < dirs.length; d++) {
2427                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
2428                if (gradientMap[pt.x][pt.y] < best) {
2429                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
2430                        best = gradientMap[pt.x][pt.y];
2431                        choice = d;
2432                    }
2433                }
2434            }
2435
2436            if (best >= gradientMap[currentPos.x][currentPos.y] ||
2437                    physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
2438                break;
2439            }
2440            currentPos = currentPos.translate(dirs[choice]);
2441            path.add(Coord.get(currentPos.x, currentPos.y));
2442            paidLength += costMap[currentPos.x][currentPos.y];
2443            frustration++;
2444            if(paidLength > moveLength - 1.0)
2445                break;
2446            if (gradientMap[currentPos.x][currentPos.y] == 0)
2447                break;
2448        }
2449        goals.clear();
2450        if (onlyPassable.contains(currentPos) || impassable2.contains(currentPos)) {
2451            closed.put(currentPos, WALL);
2452            impassable2.add(currentPos);
2453            return findCoveredAttackPath(moveLength, minPreferredRange, maxPreferredRange, coverPreference,
2454                    fov, seekDistantGoals, impassable2, onlyPassable, threats, start, targets);
2455        }
2456
2457        frustration = 0;
2458        return new ArrayList<>(path);
2459    }
2460
2461    /**
2462     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
2463     * of Coord positions (using the current measurement) needed to get closer to a goal, where goals are
2464     * considered valid if they are at a valid range for the given Technique to hit at least one target
2465     * and ideal if that Technique can affect as many targets as possible from a cell that can be moved
2466     * to with at most movelength steps.
2467     * <p/>
2468     * The return value of this method is the path to get to a location to attack, but on its own it
2469     * does not tell the user how to perform the attack.  It does set the targetMap 2D Coord array field
2470     * so that if your position at the end of the returned path is non-null in targetMap, it will be
2471     * a Coord that can be used as a target position for Technique.apply() . If your position at the end
2472     * of the returned path is null, then an ideal attack position was not reachable by the path.
2473     * <p/>
2474     * This needs a char[][] dungeon as an argument because DijkstraMap does not always have a char[][]
2475     * version of the map available to it, and certain AOE implementations that a Technique uses may
2476     * need a char[][] specifically to determine what they affect.
2477     * <p/>
2478     * The maximum length of the returned list is given by moveLength; if moving the full length of
2479     * the list would place the mover in a position shared by one of the positions in allies
2480     * (which is typically filled with friendly units that can be passed through in multi-tile-
2481     * movement scenarios, and is also used considered an undesirable thing to affect for the Technique),
2482     * it will recalculate a move so that it does not pass into that cell.
2483     * <p/>
2484     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2485     * through, and will be ignored if there is a target overlapping one.
2486     * <br>
2487     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2488     * each call to a pathfinding method.
2489     *
2490     * @param moveLength the maximum distance to try to pathfind out to; if a spot to use a Technique can be found
2491     *                   while moving no more than this distance, then the targetMap field in this object will have a
2492     *                   target Coord that is ideal for the given Technique at the x, y indices corresponding to the
2493     *                   last Coord in the returned path.
2494     * @param tech       a Technique that we will try to find an ideal place to use, and/or a path toward that place.
2495     * @param dungeon    a char 2D array with '#' for walls.
2496     * @param cache      a FOVCache that has completed its calculations, and will be used for LOS and Technique work, may be null
2497     * @param impassable locations of enemies or mobile hazards/obstacles that aren't in the map as walls
2498     * @param allies     called onlyPassable in other methods, here it also represents allies for Technique things
2499     * @param start      the Coord the pathfinder starts at.
2500     * @param targets    a Set of Coord, not an array of Coord or variable argument list as in other methods.
2501     * @return an ArrayList of Coord that represents a path to travel to get to an ideal place to use tech. Copy of path.
2502     */
2503    @GwtIncompatible
2504    public ArrayList<Coord> findTechniquePath(int moveLength, Technique tech, char[][] dungeon, FOVCache cache,
2505                                              Set<Coord> impassable, Set<Coord> allies, Coord start, Set<Coord> targets) {
2506        if (!initialized) return null;
2507        tech.setMap(dungeon);
2508        if (cache != null)
2509            tech.aoe.setCache(cache);
2510        double[][] resMap = new double[width][height];
2511        double[][] worthMap = new double[width][height];
2512        double[][] userDistanceMap;
2513        double paidLength = 0.0;
2514
2515        LinkedHashSet<Coord> friends;
2516
2517
2518        for (int x = 0; x < width; x++) {
2519            for (int y = 0; y < height; y++) {
2520                resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
2521                targetMap[x][y] = null;
2522            }
2523        }
2524
2525        path.clear();
2526        if (targets == null || targets.size() == 0)
2527            return new ArrayList<>(path);
2528        LinkedHashSet<Coord> impassable2;
2529        if (impassable == null)
2530            impassable2 = new LinkedHashSet<>();
2531        else
2532            impassable2 = new LinkedHashSet<>(impassable);
2533
2534        if (allies == null)
2535            friends = new LinkedHashSet<>();
2536        else {
2537            friends = new LinkedHashSet<>(allies);
2538            friends.remove(start);
2539        }
2540
2541        resetMap();
2542        setGoal(start);
2543        userDistanceMap = scan(impassable2);
2544        clearGoals();
2545        resetMap();
2546        for (Coord goal : targets) {
2547            setGoal(goal.x, goal.y);
2548        }
2549        if (goals.isEmpty())
2550            return new ArrayList<>(path);
2551
2552        Measurement mess = measurement;
2553        /*
2554        if(measurement == Measurement.EUCLIDEAN)
2555        {
2556            measurement = Measurement.CHEBYSHEV;
2557        }
2558        */
2559        scan(impassable2);
2560        clearGoals();
2561
2562        Coord tempPt = Coord.get(0, 0);
2563        LinkedHashMap<Coord, ArrayList<Coord>> ideal;
2564        // generate an array of the single best location to attack when you are in a given cell.
2565        for (int x = 0; x < width; x++) {
2566            CELL:
2567            for (int y = 0; y < height; y++) {
2568                tempPt = Coord.get(x, y);
2569                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK || userDistanceMap[x][y] > moveLength * 2.0)
2570                    continue;
2571                if (gradientMap[x][y] >= tech.aoe.getMinRange() && gradientMap[x][y] <= tech.aoe.getMaxRange()) {
2572                    for (Coord tgt : targets) {
2573                        if (cache == null || cache.queryLOS(x, y, tgt.x, tgt.y)) {
2574                            ideal = tech.idealLocations(tempPt, targets, friends);
2575                            // this is weird but it saves the trouble of getting the iterator and checking hasNext() .
2576                            for (Map.Entry<Coord, ArrayList<Coord>> ip : ideal.entrySet()) {
2577                                targetMap[x][y] = ip.getKey();
2578                                worthMap[x][y] = ip.getValue().size();
2579                                setGoal(x, y);
2580                                gradientMap[x][y] = 0;
2581                                break;
2582                            }
2583                            continue CELL;
2584                        }
2585                    }
2586                    gradientMap[x][y] = FLOOR;
2587                } else
2588                    gradientMap[x][y] = FLOOR;
2589            }
2590        }
2591        scan(impassable2);
2592
2593        double currentDistance = gradientMap[start.x][start.y];
2594        if (currentDistance <= moveLength) {
2595            Coord[] g_arr = new Coord[goals.size()];
2596            g_arr = goals.keySet().toArray(g_arr);
2597
2598            goals.clear();
2599            setGoal(start);
2600            scan(impassable2);
2601            goals.clear();
2602            gradientMap[start.x][start.y] = moveLength;
2603
2604            for (Coord g : g_arr) {
2605                if (gradientMap[g.x][g.y] <= moveLength && worthMap[g.x][g.y] > 0) {
2606                    goals.put(g, 0.0 - worthMap[g.x][g.y]);
2607                }
2608            }
2609            resetMap();
2610           /* for(Coord g : goals.keySet())
2611            {
2612                gradientMap[g.x][g.y] = 0.0 - worthMap[g.x][g.y];
2613            }*/
2614            scan(impassable2);
2615
2616        }
2617
2618        measurement = mess;
2619
2620        Coord currentPos = Coord.get(start.x, start.y);
2621        while (true) {
2622            if (frustration > 500) {
2623                path.clear();
2624                break;
2625            }
2626            double best = gradientMap[currentPos.x][currentPos.y];
2627            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
2628            int choice = rng.nextInt(dirs.length);
2629
2630            for (int d = 0; d < dirs.length; d++) {
2631                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
2632                if (gradientMap[pt.x][pt.y] < best) {
2633                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
2634                        best = gradientMap[pt.x][pt.y];
2635                        choice = d;
2636                    }
2637                }
2638            }
2639            if (best >= gradientMap[currentPos.x][currentPos.y]) {
2640                if (friends.contains(currentPos)) {
2641                    closed.put(currentPos, WALL);
2642                    impassable2.add(currentPos);
2643                    return findTechniquePath(moveLength, tech, dungeon, cache, impassable2,
2644                            friends, start, targets);
2645                }
2646                break;
2647            }
2648            if (best > gradientMap[start.x][start.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
2649                path.clear();
2650                break;
2651            }
2652            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
2653            path.add(currentPos);
2654            paidLength += costMap[currentPos.x][currentPos.y];
2655            frustration++;
2656            if (paidLength > moveLength - 1.0) {
2657                if (friends.contains(currentPos)) {
2658                    closed.put(currentPos, WALL);
2659                    impassable2.add(currentPos);
2660                    return findTechniquePath(moveLength, tech, dungeon, cache, impassable2,
2661                            friends, start, targets);
2662                }
2663                break;
2664            }
2665//            if(gradientMap[currentPos.x][currentPos.y] == 0)
2666//                break;
2667        }
2668        frustration = 0;
2669        goals.clear();
2670        return new ArrayList<>(path);
2671    }
2672
2673
2674    private double cachedLongerPaths = 1.2;
2675    private Set<Coord> cachedImpassable = new LinkedHashSet<>();
2676    private Coord[] cachedFearSources;
2677    private double[][] cachedFleeMap;
2678    private int cachedSize = 1;
2679
2680    /**
2681     * Scans the dungeon using DijkstraMap.scan with the listed fearSources and start point, and returns a list
2682     * of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant
2683     * for running away. The maximum length of the returned list is given by length; if moving the full
2684     * length of the list would place the mover in a position shared by one of the positions in onlyPassable
2685     * (which is typically filled with friendly units that can be passed through in multi-tile-
2686     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2687     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2688     * through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter
2689     * is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of
2690     * doorways instead of hiding in the closest corner, and a value of 1.2 should be typical for many maps.
2691     * The parameters preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and
2692     * any subsequent calls that use the same values as the last values passed will avoid recalculating
2693     * unnecessary scans.
2694     * <br>
2695     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2696     * each call to a pathfinding method.
2697     *
2698     * @param length            the length of the path to calculate
2699     * @param preferLongerPaths Set this to 1.2 if you aren't sure; it will probably need tweaking for different maps.
2700     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
2701     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2702     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2703     * @param fearSources       a vararg or array of Coord positions to run away from
2704     * @return an ArrayList of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path.
2705     */
2706    public ArrayList<Coord> findFleePath(int length, double preferLongerPaths, Set<Coord> impassable,
2707                                         Set<Coord> onlyPassable, Coord start, Coord... fearSources) {
2708        if (!initialized) return null;
2709        path.clear();
2710        LinkedHashSet<Coord> impassable2;
2711        if (impassable == null)
2712            impassable2 = new LinkedHashSet<>();
2713        else
2714            impassable2 = new LinkedHashSet<>(impassable);
2715
2716        if (onlyPassable == null)
2717            onlyPassable = new LinkedHashSet<>();
2718        if (fearSources == null || fearSources.length < 1) {
2719            path.clear();
2720            return new ArrayList<>(path);
2721        }
2722        if (cachedSize == 1 && preferLongerPaths == cachedLongerPaths && impassable2.equals(cachedImpassable) &&
2723                Arrays.equals(fearSources, cachedFearSources)) {
2724            gradientMap = cachedFleeMap;
2725        } else {
2726            cachedLongerPaths = preferLongerPaths;
2727            cachedImpassable = new LinkedHashSet<>(impassable2);
2728            cachedFearSources = GwtCompatibility.cloneCoords(fearSources);
2729            cachedSize = 1;
2730            resetMap();
2731            for (Coord goal : fearSources) {
2732                setGoal(goal.x, goal.y);
2733            }
2734            if (goals.isEmpty())
2735                return new ArrayList<>(path);
2736
2737            scan(impassable2);
2738
2739            for (int x = 0; x < gradientMap.length; x++) {
2740                for (int y = 0; y < gradientMap[x].length; y++) {
2741                    gradientMap[x][y] *= (gradientMap[x][y] >= FLOOR) ? 1.0 : (0.0 - preferLongerPaths);
2742                }
2743            }
2744            cachedFleeMap = scan(impassable2);
2745        }
2746        Coord currentPos = start;
2747        double paidLength = 0.0;
2748        while (true) {
2749            if (frustration > 500) {
2750                path.clear();
2751                break;
2752            }
2753            double best = gradientMap[currentPos.x][currentPos.y];
2754            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
2755            int choice = rng.nextInt(dirs.length);
2756
2757            for (int d = 0; d < dirs.length; d++) {
2758                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
2759                if (gradientMap[pt.x][pt.y] < best) {
2760                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
2761                        best = gradientMap[pt.x][pt.y];
2762                        choice = d;
2763                    }
2764                }
2765            }
2766            if (best >= gradientMap[start.x][start.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
2767                path.clear();
2768                break;
2769            }
2770            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
2771            if (path.size() > 0) {
2772                Coord last = path.get(path.size() - 1);
2773                if (gradientMap[last.x][last.y] <= gradientMap[currentPos.x][currentPos.y])
2774                    break;
2775            }
2776            path.add(currentPos);
2777            frustration++;
2778            paidLength += costMap[currentPos.x][currentPos.y];
2779            if (paidLength > length - 1.0) {
2780                if (onlyPassable.contains(currentPos)) {
2781
2782                    closed.put(currentPos, WALL);
2783                    impassable2.add(currentPos);
2784                    return findFleePath(length, preferLongerPaths, impassable2, onlyPassable, start, fearSources);
2785                }
2786                break;
2787            }
2788        }
2789        frustration = 0;
2790        goals.clear();
2791        return new ArrayList<>(path);
2792    }
2793
2794    /**
2795     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
2796     * of Coord positions (using the current measurement) needed to get closer to the closest reachable
2797     * goal. The maximum length of the returned list is given by length; if moving the full length of
2798     * the list would place the mover in a position shared by one of the positions in onlyPassable
2799     * (which is typically filled with friendly units that can be passed through in multi-tile-
2800     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2801     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2802     * through, and will be ignored if there is a goal overlapping one.
2803     * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The
2804     * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is &gt; 1, and
2805     * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
2806     * <br>
2807     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2808     * each call to a pathfinding method.
2809     *
2810     * @param size         the side length of the creature trying to find a path
2811     * @param length       the length of the path to calculate
2812     * @param impassable   a Set of impassable Coord positions that may change (not constant like walls); can be null
2813     * @param onlyPassable a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2814     * @param start        the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2815     * @param targets      a vararg or array of Coord that this will try to pathfind toward
2816     * @return an ArrayList of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path.
2817     */
2818
2819    public ArrayList<Coord> findPathLarge(int size, int length, Set<Coord> impassable,
2820                                          Set<Coord> onlyPassable, Coord start, Coord... targets) {
2821        if (!initialized) return null;
2822        path.clear();
2823        LinkedHashSet<Coord> impassable2;
2824        if (impassable == null)
2825            impassable2 = new LinkedHashSet<>();
2826        else
2827            impassable2 = new LinkedHashSet<>(impassable);
2828
2829        if (onlyPassable == null)
2830            onlyPassable = new LinkedHashSet<>();
2831
2832        resetMap();
2833        for (Coord goal : targets) {
2834            setGoal(goal.x, goal.y);
2835        }
2836        if (goals.isEmpty())
2837            return new ArrayList<>(path);
2838
2839        scan(impassable2, size);
2840        Coord currentPos = start;
2841        double paidLength = 0.0;
2842        while (true) {
2843            if (frustration > 500) {
2844                path.clear();
2845                break;
2846            }
2847            double best = gradientMap[currentPos.x][currentPos.y];
2848            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
2849            int choice = rng.nextInt(dirs.length);
2850
2851            for (int d = 0; d < dirs.length; d++) {
2852                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
2853                if (gradientMap[pt.x][pt.y] < best) {
2854                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
2855                        best = gradientMap[pt.x][pt.y];
2856                        choice = d;
2857                    }
2858                }
2859            }
2860
2861            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
2862                path.clear();
2863                break;
2864            }
2865            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
2866
2867            path.add(currentPos);
2868            paidLength += costMap[currentPos.x][currentPos.y];
2869            frustration++;
2870            if (paidLength > length - 1.0) {
2871                if (onlyPassable.contains(currentPos)) {
2872
2873                    closed.put(currentPos, WALL);
2874                    impassable2.add(currentPos);
2875                    return findPathLarge(size, length, impassable2, onlyPassable, start, targets);
2876                }
2877                break;
2878            }
2879            if (gradientMap[currentPos.x][currentPos.y] == 0)
2880                break;
2881        }
2882        frustration = 0;
2883        goals.clear();
2884        return new ArrayList<>(path);
2885    }
2886
2887    /**
2888     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
2889     * of Coord positions (using the current measurement) needed to get closer to a goal, until preferredRange is
2890     * reached, or further from a goal if the preferredRange has not been met at the current distance.
2891     * The maximum length of the returned list is given by moveLength; if moving the full length of
2892     * the list would place the mover in a position shared by one of the positions in onlyPassable
2893     * (which is typically filled with friendly units that can be passed through in multi-tile-
2894     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
2895     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
2896     * through, and will be ignored if there is a goal overlapping one.
2897     * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The
2898     * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is &gt; 1, and
2899     * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
2900     * <br>
2901     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
2902     * each call to a pathfinding method.
2903     *
2904     * @param size           the side length of the creature trying to find a path
2905     * @param moveLength     the length of the path to calculate
2906     * @param preferredRange the distance this unit will try to keep from a target
2907     * @param los            a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS
2908     *                       should be disregarded.
2909     * @param impassable     a Set of impassable Coord positions that may change (not constant like walls); can be null
2910     * @param onlyPassable   a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
2911     * @param start          the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
2912     * @param targets        a vararg or array of Coord that this will try to pathfind toward
2913     * @return an ArrayList of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path.
2914     */
2915    public ArrayList<Coord> findAttackPathLarge(int size, int moveLength, int preferredRange, LOS los, Set<Coord> impassable,
2916                                                Set<Coord> onlyPassable, Coord start, Coord... targets) {
2917        if (!initialized) return null;
2918        if (preferredRange < 0) preferredRange = 0;
2919        double[][] resMap = new double[width][height];
2920        if (los != null) {
2921            for (int x = 0; x < width; x++) {
2922                for (int y = 0; y < height; y++) {
2923                    resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
2924                }
2925            }
2926        }
2927        path.clear();
2928        LinkedHashSet<Coord> impassable2;
2929        if (impassable == null)
2930            impassable2 = new LinkedHashSet<>();
2931        else
2932            impassable2 = new LinkedHashSet<>(impassable);
2933
2934        if (onlyPassable == null)
2935            onlyPassable = new LinkedHashSet<>();
2936
2937        resetMap();
2938        for (Coord goal : targets) {
2939            setGoal(goal.x, goal.y);
2940        }
2941        if (goals.isEmpty())
2942            return new ArrayList<>(path);
2943
2944        Measurement mess = measurement;
2945        if (measurement == Measurement.EUCLIDEAN) {
2946            measurement = Measurement.CHEBYSHEV;
2947        }
2948        scan(impassable2, size);
2949        goals.clear();
2950
2951        for (int x = 0; x < width; x++) {
2952            CELL:
2953            for (int y = 0; y < height; y++) {
2954                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
2955                    continue;
2956                if (x + 2 < width && y + 2 < height && gradientMap[x][y] == preferredRange) {
2957                    for (Coord goal : targets) {
2958                        if (los == null
2959                                || los.isReachable(resMap, x, y, goal.x, goal.y)
2960                                || los.isReachable(resMap, x + 1, y, goal.x, goal.y)
2961                                || los.isReachable(resMap, x, y + 1, goal.x, goal.y)
2962                                || los.isReachable(resMap, x + 1, y + 1, goal.x, goal.y)) {
2963                            setGoal(x, y);
2964                            gradientMap[x][y] = 0;
2965                            continue CELL;
2966                        }
2967                    }
2968                    gradientMap[x][y] = FLOOR;
2969                } else
2970                    gradientMap[x][y] = FLOOR;
2971            }
2972        }
2973        measurement = mess;
2974        scan(impassable2, size);
2975
2976        Coord currentPos = start;
2977        double paidLength = 0.0;
2978        while (true) {
2979            if (frustration > 500) {
2980                path.clear();
2981                break;
2982            }
2983            double best = gradientMap[currentPos.x][currentPos.y];
2984            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
2985            int choice = rng.nextInt(dirs.length);
2986
2987            for (int d = 0; d < dirs.length; d++) {
2988                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
2989                if (gradientMap[pt.x][pt.y] < best) {
2990                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
2991                        best = gradientMap[pt.x][pt.y];
2992                        choice = d;
2993                    }
2994                }
2995            }
2996
2997            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
2998                path.clear();
2999                break;
3000            }
3001            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
3002            path.add(currentPos);
3003            frustration++;
3004            paidLength += costMap[currentPos.x][currentPos.y];
3005            if (paidLength > moveLength - 1.0) {
3006                if (onlyPassable.contains(currentPos)) {
3007
3008                    closed.put(currentPos, WALL);
3009                    impassable2.add(currentPos);
3010                    return findAttackPathLarge(size, moveLength, preferredRange, los, impassable2, onlyPassable, start, targets);
3011                }
3012                break;
3013            }
3014            if (gradientMap[currentPos.x][currentPos.y] == 0)
3015                break;
3016        }
3017        frustration = 0;
3018        goals.clear();
3019        return new ArrayList<>(path);
3020    }
3021
3022    /**
3023     * Scans the dungeon using DijkstraMap.scan with the listed goals and start point, and returns a list
3024     * of Coord positions (using the current measurement) needed to get closer to a goal, until a cell is reached with
3025     * a distance from a goal that is at least equal to minPreferredRange and no more than maxPreferredRange,
3026     * which may go further from a goal if the minPreferredRange has not been met at the current distance.
3027     * The maximum length of the returned list is given by moveLength; if moving the full length of
3028     * the list would place the mover in a position shared by one of the positions in onlyPassable
3029     * (which is typically filled with friendly units that can be passed through in multi-tile-
3030     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
3031     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
3032     * through, and will be ignored if there is a goal overlapping one.
3033     * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The
3034     * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is &gt; 1, and
3035     * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
3036     * <br>
3037     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
3038     * each call to a pathfinding method.
3039     *
3040     * @param size              the side length of the creature trying to find a path
3041     * @param moveLength        the length of the path to calculate
3042     * @param minPreferredRange the (inclusive) lower bound of the distance this unit will try to keep from a target
3043     * @param maxPreferredRange the (inclusive) upper bound of the distance this unit will try to keep from a target
3044     * @param los               a squidgrid.LOS object if the preferredRange should try to stay in line of sight, or null if LoS
3045     *                          should be disregarded.
3046     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
3047     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
3048     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
3049     * @param targets           a vararg or array of Coord that this will try to pathfind toward
3050     * @return an ArrayList of Coord that will contain the min-x, min-y locations of this creature as it goes toward a target. Copy of path.
3051     */
3052    public ArrayList<Coord> findAttackPathLarge(int size, int moveLength, int minPreferredRange, int maxPreferredRange, LOS los,
3053                                                Set<Coord> impassable, Set<Coord> onlyPassable, Coord start, Coord... targets) {
3054        if (!initialized) return null;
3055        if (minPreferredRange < 0) minPreferredRange = 0;
3056        if (maxPreferredRange < minPreferredRange) maxPreferredRange = minPreferredRange;
3057        double[][] resMap = new double[width][height];
3058        if (los != null) {
3059            for (int x = 0; x < width; x++) {
3060                for (int y = 0; y < height; y++) {
3061                    resMap[x][y] = (physicalMap[x][y] == WALL) ? 1.0 : 0.0;
3062                }
3063            }
3064        }
3065        path.clear();
3066        LinkedHashSet<Coord> impassable2;
3067        if (impassable == null)
3068            impassable2 = new LinkedHashSet<>();
3069        else
3070            impassable2 = new LinkedHashSet<>(impassable);
3071
3072        if (onlyPassable == null)
3073            onlyPassable = new LinkedHashSet<>();
3074
3075        resetMap();
3076        for (Coord goal : targets) {
3077            setGoal(goal);
3078        }
3079        if (goals.isEmpty())
3080            return new ArrayList<>(path);
3081
3082        Measurement mess = measurement;
3083        if (measurement == Measurement.EUCLIDEAN) {
3084            measurement = Measurement.CHEBYSHEV;
3085        }
3086        scan(impassable2, size);
3087        goals.clear();
3088
3089        for (int x = 0; x < width; x++) {
3090            CELL:
3091            for (int y = 0; y < height; y++) {
3092                if (gradientMap[x][y] == WALL || gradientMap[x][y] == DARK)
3093                    continue;
3094                if (x + 2 < width && y + 2 < height && gradientMap[x][y] >= minPreferredRange && gradientMap[x][y] <= maxPreferredRange) {
3095                    for (Coord goal : targets) {
3096                        if (los == null
3097                                || los.isReachable(resMap, x, y, goal.x, goal.y)
3098                                || los.isReachable(resMap, x + 1, y, goal.x, goal.y)
3099                                || los.isReachable(resMap, x, y + 1, goal.x, goal.y)
3100                                || los.isReachable(resMap, x + 1, y + 1, goal.x, goal.y)) {
3101                            setGoal(x, y);
3102                            gradientMap[x][y] = 0;
3103                            continue CELL;
3104                        }
3105                    }
3106                    gradientMap[x][y] = FLOOR;
3107                } else
3108                    gradientMap[x][y] = FLOOR;
3109            }
3110        }
3111        measurement = mess;
3112        scan(impassable2, size);
3113
3114        Coord currentPos = start;
3115        double paidLength = 0.0;
3116        while (true) {
3117            if (frustration > 500) {
3118                path.clear();
3119                break;
3120            }
3121
3122            double best = gradientMap[currentPos.x][currentPos.y];
3123            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
3124            int choice = rng.nextInt(dirs.length);
3125
3126            for (int d = 0; d < dirs.length; d++) {
3127                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
3128                if (gradientMap[pt.x][pt.y] < best) {
3129                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
3130                        best = gradientMap[pt.x][pt.y];
3131                        choice = d;
3132                    }
3133                }
3134            }
3135            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
3136                path.clear();
3137                break;
3138            }
3139            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
3140
3141            path.add(currentPos);
3142            frustration++;
3143            paidLength += costMap[currentPos.x][currentPos.y];
3144            if (paidLength > moveLength - 1.0) {
3145                if (onlyPassable.contains(currentPos)) {
3146
3147                    closed.put(currentPos, WALL);
3148                    impassable2.add(currentPos);
3149                    return findAttackPathLarge(size, moveLength, minPreferredRange, maxPreferredRange, los, impassable2,
3150                            onlyPassable, start, targets);
3151                }
3152                break;
3153            }
3154            if (gradientMap[currentPos.x][currentPos.y] == 0)
3155                break;
3156        }
3157        frustration = 0;
3158        goals.clear();
3159        return new ArrayList<>(path);
3160    }
3161
3162    /**
3163     * Scans the dungeon using DijkstraMap.scan with the listed fearSources and start point, and returns a list
3164     * of Coord positions (using Manhattan distance) needed to get further from the closest fearSources, meant
3165     * for running away. The maximum length of the returned list is given by length; if moving the full
3166     * length of the list would place the mover in a position shared by one of the positions in onlyPassable
3167     * (which is typically filled with friendly units that can be passed through in multi-tile-
3168     * movement scenarios), it will recalculate a move so that it does not pass into that cell.
3169     * The keys in impassable should be the positions of enemies and obstacles that cannot be moved
3170     * through, and will be ignored if there is a fearSource overlapping one. The preferLongerPaths parameter
3171     * is meant to be tweaked and adjusted; higher values should make creatures prefer to escape out of
3172     * doorways instead of hiding in the closest corner, and a value of 1.2 should be typical for many maps.
3173     * The parameters size, preferLongerPaths, impassable, and the varargs used for fearSources will be cached, and
3174     * any subsequent calls that use the same values as the last values passed will avoid recalculating
3175     * unnecessary scans. Calls to findFleePath will cache as if size is 1, and may share a cache with this function.
3176     * The parameter size refers to the side length of a square unit, such as 2 for a 2x2 unit. The
3177     * parameter start must refer to the minimum-x, minimum-y cell of that unit if size is &gt; 1, and
3178     * all positions in the returned path will refer to movement of the minimum-x, minimum-y cell.
3179     * <br>
3180     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
3181     * each call to a pathfinding method.
3182     *
3183     * @param size              the side length of the creature trying the find a path
3184     * @param length            the length of the path to calculate
3185     * @param preferLongerPaths Set this to 1.2 if you aren't sure; it will probably need tweaking for different maps.
3186     * @param impassable        a Set of impassable Coord positions that may change (not constant like walls); can be null
3187     * @param onlyPassable      a Set of Coord positions that this pathfinder cannot end a path occupying (typically allies); can be null
3188     * @param start             the start of the path, should correspond to the minimum-x, minimum-y position of the pathfinder
3189     * @param fearSources       a vararg or array of Coord positions to run away from
3190     * @return an ArrayList of Coord that will contain the locations of this creature as it goes away from fear sources. Copy of path.
3191     */
3192    public ArrayList<Coord> findFleePathLarge(int size, int length, double preferLongerPaths, Set<Coord> impassable,
3193                                              Set<Coord> onlyPassable, Coord start, Coord... fearSources) {
3194        if (!initialized) return null;
3195        path.clear();
3196        LinkedHashSet<Coord> impassable2;
3197        if (impassable == null)
3198            impassable2 = new LinkedHashSet<>();
3199        else
3200            impassable2 = new LinkedHashSet<>(impassable);
3201
3202        if (onlyPassable == null)
3203            onlyPassable = new LinkedHashSet<>();
3204        if (fearSources == null || fearSources.length < 1) {
3205            path.clear();
3206            return new ArrayList<>(path);
3207        }
3208        if (size == cachedSize && preferLongerPaths == cachedLongerPaths && impassable2.equals(cachedImpassable)
3209                && Arrays.equals(fearSources, cachedFearSources)) {
3210            gradientMap = cachedFleeMap;
3211        } else {
3212            cachedLongerPaths = preferLongerPaths;
3213            cachedImpassable = new LinkedHashSet<>(impassable2);
3214            cachedFearSources = GwtCompatibility.cloneCoords(fearSources);
3215            cachedSize = size;
3216            resetMap();
3217            for (Coord goal : fearSources) {
3218                setGoal(goal.x, goal.y);
3219            }
3220            if (goals.isEmpty())
3221                return new ArrayList<>(path);
3222
3223            scan(impassable2, size);
3224
3225            for (int x = 0; x < gradientMap.length; x++) {
3226                for (int y = 0; y < gradientMap[x].length; y++) {
3227                    gradientMap[x][y] *= (gradientMap[x][y] >= FLOOR) ? 1.0 : (0.0 - preferLongerPaths);
3228                }
3229            }
3230            cachedFleeMap = scan(impassable2, size);
3231        }
3232        Coord currentPos = start;
3233        double paidLength = 0.0;
3234        while (true) {
3235            if (frustration > 500) {
3236                path.clear();
3237                break;
3238            }
3239
3240            double best = gradientMap[currentPos.x][currentPos.y];
3241            final Direction[] dirs = appendDir(shuffleDirs(rng), Direction.NONE);
3242            int choice = rng.nextInt(dirs.length);
3243
3244            for (int d = 0; d < dirs.length; d++) {
3245                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
3246                if (gradientMap[pt.x][pt.y] < best) {
3247                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
3248                        best = gradientMap[pt.x][pt.y];
3249                        choice = d;
3250                    }
3251                }
3252            }
3253            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
3254                path.clear();
3255                break;
3256            }
3257            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
3258
3259            if (path.size() > 0) {
3260                Coord last = path.get(path.size() - 1);
3261                if (gradientMap[last.x][last.y] <= gradientMap[currentPos.x][currentPos.y])
3262                    break;
3263            }
3264            path.add(currentPos);
3265            frustration++;
3266            paidLength += costMap[currentPos.x][currentPos.y];
3267            if (paidLength > length - 1.0) {
3268                if (onlyPassable.contains(currentPos)) {
3269
3270                    closed.put(currentPos, WALL);
3271                    impassable2.add(currentPos);
3272                    return findFleePathLarge(size, length, preferLongerPaths, impassable2, onlyPassable, start, fearSources);
3273                }
3274                break;
3275            }
3276        }
3277        frustration = 0;
3278        goals.clear();
3279        return new ArrayList<>(path);
3280    }
3281
3282
3283    /**
3284     * Intended primarily for internal use. Needs scan() to already be called and at least one goal to already be set,
3285     * and does not restrict the length of the path or behave as if the pathfinder has allies or enemies.
3286     * <br>
3287     * This caches its result in a member field, path, which can be fetched after finding a path and will change with
3288     * each call to a pathfinding method.
3289     *
3290     * @param target the target cell
3291     * @return an ArrayList of Coord that make up the best path. Copy of path.
3292     */
3293    public ArrayList<Coord> findPathPreScanned(Coord target) {
3294        if (!initialized || goals == null || goals.isEmpty()) return null;
3295        RNG rng2 = new StatefulRNG(new LightRNG(0xf00d));
3296        path.clear();
3297        Coord currentPos = target;
3298        while (true) {
3299            if (frustration > 2000) {
3300                path.clear();
3301                break;
3302            }
3303            double best = gradientMap[currentPos.x][currentPos.y];
3304            final Direction[] dirs = appendDir(shuffleDirs(rng2), Direction.NONE);
3305            int choice = rng2.nextInt(dirs.length);
3306
3307            for (int d = 0; d < dirs.length; d++) {
3308                Coord pt = Coord.get(currentPos.x + dirs[d].deltaX, currentPos.y + dirs[d].deltaY);
3309                if (gradientMap[pt.x][pt.y] < best) {
3310                    if (dirs[choice] == Direction.NONE || !path.contains(pt)) {
3311                        best = gradientMap[pt.x][pt.y];
3312                        choice = d;
3313                    }
3314                }
3315            }
3316
3317            if (best >= gradientMap[currentPos.x][currentPos.y] || physicalMap[currentPos.x + dirs[choice].deltaX][currentPos.y + dirs[choice].deltaY] > FLOOR) {
3318                path.clear();
3319                break;
3320            }
3321            currentPos = currentPos.translate(dirs[choice].deltaX, dirs[choice].deltaY);
3322            path.add(0, currentPos);
3323            frustration++;
3324
3325            if (gradientMap[currentPos.x][currentPos.y] == 0)
3326                break;
3327        }
3328        frustration = 0;
3329        return new ArrayList<>(path);
3330    }
3331
3332    /**
3333     * A simple limited flood-fill that returns a LinkedHashMap of Coord keys to the Double values in the DijkstraMap, only
3334     * calculating out to a number of steps determined by limit. This can be useful if you need many flood-fills and
3335     * don't need a large area for each, or if you want to have an effect spread to a certain number of cells away.
3336     *
3337     * @param radius the number of steps to take outward from each starting position.
3338     * @param starts a vararg group of Points to step outward from; this often will only need to be one Coord.
3339     * @return A LinkedHashMap of Coord keys to Double values; the starts are included in this with the value 0.0.
3340     */
3341    public LinkedHashMap<Coord, Double> floodFill(int radius, Coord... starts) {
3342        if (!initialized) return null;
3343        LinkedHashMap<Coord, Double> fill = new LinkedHashMap<>();
3344
3345        resetMap();
3346        for (Coord goal : starts) {
3347            setGoal(goal.x, goal.y);
3348        }
3349        if (goals.isEmpty())
3350            return fill;
3351
3352        partialScan(radius, null);
3353        double temp;
3354        for (int x = 1; x < width - 1; x++) {
3355            for (int y = 1; y < height - 1; y++) {
3356                temp = gradientMap[x][y];
3357                if (temp < FLOOR) {
3358                    fill.put(Coord.get(x, y), temp);
3359                }
3360            }
3361        }
3362        goals.clear();
3363        return fill;
3364    }
3365
3366    private static final double root2 = Math.sqrt(2.0);
3367
3368    private double heuristic(Direction target) {
3369        switch (measurement) {
3370            case MANHATTAN:
3371            case CHEBYSHEV:
3372                return 1.0;
3373            case EUCLIDEAN:
3374                switch (target) {
3375                    case DOWN_LEFT:
3376                    case DOWN_RIGHT:
3377                    case UP_LEFT:
3378                    case UP_RIGHT:
3379                        return root2;
3380                    default:
3381                        return 1.0;
3382                }
3383        }
3384        return 1.0;
3385    }
3386    
3387    /* For Gwt compatibility */
3388    private Direction[] shuffleDirs(RNG rng) {
3389        final Direction[] src = measurement == Measurement.MANHATTAN
3390                        ? Direction.CARDINALS : Direction.OUTWARDS;
3391        return rng.shuffle(src, new Direction[src.length]);
3392    }
3393
3394    /* For Gwt compatibility */
3395    private static Direction[] appendDir(Direction[] src, Direction additional) {
3396        final Direction[] result = new Direction[src.length + 1];
3397        for (int i = 0; i < src.length; i++)
3398                result[i] = src[i];
3399        result[result.length - 1] = additional;
3400        return result;
3401        }
3402}