001package squidpony.squidai;
002
003import squidpony.squidgrid.Direction;
004import squidpony.squidgrid.Radius;
005import squidpony.squidmath.Coord;
006import squidpony.squidmath.CoordPacker;
007import squidpony.squidmath.ShortVLA;
008
009import java.util.*;
010
011/**
012 * Calculates the Zone of Influence, also known as Zone of Control, for different points on a map.
013 * Uses CoordPacker for more efficient storage and manipulation of zones; it's recommended if you use this class to be
014 * somewhat familiar with the methods for manipulating packed data in that class.
015 * Created by Tommy Ettinger on 10/27/2015.
016 */
017public class ZOI {
018    private char[][] map;
019    private DijkstraMap dijkstra;
020    private Coord[][] influences;
021    private short[][] packedGroups;
022    private boolean completed = false;
023    private Radius radius;
024    /**
025     * Constructs a Zone of Influence map. Takes a (quite possibly jagged) array of arrays of Coord influences, where
026     * the elements of the outer array represent different groups of influencing "factions" or groups that exert control
027     * over nearby areas, and the Coord elements of the inner array represent individual spots that are part of those
028     * groups and share influence with all Coord in the same inner array. Also takes a char[][] for a map, which can be
029     * the simplified map with only '#' for walls and '.' for floors, or the final map (with chars like '~' for deep
030     * water as well as walls and floors), and a Radius enum that will be used to determine how distance is calculated.
031     * <br>
032     * Call calculate() when you want information out of this.
033     * @param influences an outer array containing influencing groups, each an array containing Coords that influence
034     * @param map a char[][] that is used as a map; should be bounded
035     * @param measurement a Radius enum that corresponds to how distance should be measured
036     */
037    public ZOI(Coord[][] influences, char[][] map, Radius measurement) {
038        this.influences = influences;
039        packedGroups = new short[influences.length][];
040        this.map = map;
041        radius = measurement;
042        dijkstra = new DijkstraMap(map, DijkstraMap.findMeasurement(measurement));
043    }
044    /**
045     * Constructs a Zone of Influence map. Takes an arrays of Coord influences, where each Coord is treated as both a
046     * one-element group of influencing "factions" or groups that exert control over nearby areas, and the individual
047     * spot that makes up one of those groups and spreads influence. Also takes a char[][] for a map, which can be the
048     * simplified map with only '#' for walls and '.' for floors, or the final map (with chars like '~' for deep water
049     * as well as walls and floors), and a Radius enum that will be used to determine how distance is calculated.
050     * <br>
051     * Essentially, this is the same as constructing a ZOI with a Coord[][] where each inner array has only one element.
052     * <br>
053     * Call calculate() when you want information out of this.
054     * @param influences an array containing Coords that each have their own independent influence
055     * @param map a char[][] that is used as a map; should be bounded
056     * @param measurement a Radius enum that corresponds to how distance should be measured
057     * @see squidpony.squidmath.PoissonDisk for a good way to generate evenly spaced Coords that can be used here
058     */
059    public ZOI(Coord[] influences, char[][] map, Radius measurement) {
060        this.influences = new Coord[influences.length][];
061        for (int i = 0; i < influences.length; i++) {
062            this.influences[i] = new Coord[] { influences[i] };
063        }
064        packedGroups = new short[influences.length][];
065        this.map = map;
066        radius = measurement;
067        dijkstra = new DijkstraMap(map, DijkstraMap.findMeasurement(measurement));
068    }
069
070    /**
071     * Finds the zones of influence for each of the influences (inner arrays of Coord) this was constructed with, and
072     * returns them as packed data (using CoordPacker, which can also be used to unpack the data, merge zones, get
073     * shared borders, and all sorts of other tricks). This has each zone of influence overlap with its neighbors; this
074     * is useful to find borders using CoordPacker.intersectPacked(), and borders are typically between 1 and 2 cells
075     * wide. You can get a different region as packed data if you want region A without the overlapping areas it shares
076     * with region B by using {@code short[] different = CoordPacker.differencePacked(A, B)}. Merging two zones A and B
077     * can be done with {@code short[] merged = CoordPacker.unionPacked(A, B)} . You can unpack the data
078     * into a boolean[][] easily with CoordPacker.unpack(), where true is contained in the zone and false is not.
079     * The CoordPacker methods fringe(), expand(), singleRandom(), randomSample(), and randomPortion() are also
080     * potentially useful for this sort of data. You should save the short[][] for later use if you want to call
081     * nearestInfluences() in this class.
082     * <br>
083     * The first short[] in the returned short[][] will correspond to the area influenced by the first Coord[] in the
084     * nested array passed to the constructor (or the first Coord if a non-nested array was passed); the second will
085     * correspond to the second, and so on. The length of the short[][] this returns will equal the number of influence
086     * groups.
087     * @return an array of short[] storing the zones' areas; each can be used as packed data with CoordPacker
088     */
089    public short[][] calculate()
090    {
091        for (int i = 0; i < influences.length; i++) {
092            for (int j = 0; j < influences[i].length; j++) {
093                dijkstra.setGoal(influences[i][j]);
094            }
095        }
096        double[][] scannedAll = dijkstra.scan(null);
097
098        for (int i = 0; i < influences.length; i++) {
099
100            /*
101            dijkstra.clearGoals();
102            dijkstra.resetMap();
103            for (int j = 0; j < influences[i].length; j++) {
104                dijkstra.setGoal(influences[i][j]);
105            }
106            double[][] factionScanned = dijkstra.scan(null);
107            for (int y = 0; y < map[0].length; y++) {
108                for (int x = 0; x < map.length; x++) {
109                    influenced[x][y] = (scannedAll[x][y] < DijkstraMap.FLOOR) &&
110                            (factionScanned[x][y] - scannedAll[x][y] <= 1);
111                }
112            }*/
113            packedGroups[i] = CoordPacker.pack(increasing(scannedAll, influences[i]));
114        }
115        completed = true;
116        return packedGroups;
117    }
118    protected boolean[][] increasing(double[][] dm, Coord[] inf) {
119        LinkedHashSet<Coord> open = new LinkedHashSet<>(64), fresh = new LinkedHashSet<>(64);
120        Collections.addAll(open, inf);
121        Direction[] dirs = (radius.equals2D(Radius.DIAMOND)) ? Direction.CARDINALS : Direction.OUTWARDS;
122        boolean[][] influenced = new boolean[map.length][map[0].length];
123
124        final int width = dm.length;
125        final int height = width == 0 ? 0 : dm[0].length;
126
127        int numAssigned = open.size();
128        double diff;
129        while (numAssigned > 0) {
130            numAssigned = 0;
131            for (Coord cell : open) {
132                influenced[cell.x][cell.y] = true;
133                for (int d = 0; d < dirs.length; d++) {
134                    Coord adj = cell.translate(dirs[d].deltaX, dirs[d].deltaY);
135                    if (adj.x < 0 || adj.y < 0 || width <= adj.x || height <= adj.y)
136                        /* Outside the map */
137                        continue;
138                    if (!open.contains(adj) && dm[adj.x][adj.y] < DijkstraMap.FLOOR && !influenced[adj.x][adj.y]) {
139                        //h = heuristic(dirs[d]);
140                        diff = dm[adj.x][adj.y] - dm[cell.x][cell.y];
141                        if (diff <= 1.0 && diff >= 0) {
142                            fresh.add(adj);
143                            influenced[adj.x][adj.y] = true;
144                            ++numAssigned;
145                        }
146                    }
147                }
148            }
149
150            open = new LinkedHashSet<>(fresh);
151            fresh.clear();
152        }
153
154        return influenced;
155    }
156
157    /**
158     * Given the zones resulting from this class' calculate method and a Coord to check, finds the indices of all
159     * influencing groups in zones that have the Coord in their area, and returns all such indices as an int array.
160     * @param zones a short[][] returned by calculate; not a multi-packed short[][] from CoordPacker !
161     * @param point the Coord to test
162     * @return an int[] where each element is the index of an influencing group in zones
163     */
164    public int[] nearestInfluences(short[][] zones, Coord point)
165    {
166        ShortVLA found = new ShortVLA(4);
167        for (short i = 0; i < zones.length; i++) {
168            if(CoordPacker.queryPacked(zones[i], point.x, point.y))
169                found.add(i);
170        }
171        return found.asInts();
172    }
173    /**
174     * This can be given a Coord to check in the results of the latest calculate() call. Finds the indices of all
175     * influencing groups in zones that have the Coord in their area, and returns all such indices as an int array.
176     * @param point the Coord to test
177     * @return an int[] where each element is the index of an influencing group in zones
178     */
179    public int[] nearestInfluences(Coord point)
180    {
181        if(!completed)
182            return new int[0];
183        ShortVLA found = new ShortVLA(4);
184        for (short i = 0; i < packedGroups.length; i++) {
185            if(CoordPacker.queryPacked(packedGroups[i], point.x, point.y))
186                found.add(i);
187        }
188        return found.asInts();
189    }
190
191    /**
192     * Gets the influencing groups; ideally the result should not be changed without setting it back with setInfluences.
193     * @return influences a jagged array of Coord arrays, where the inner arrays are groups of influences
194     */
195    public Coord[][] getInfluences() {
196        return influences;
197    }
198
199    /**
200     * Changes the influencing groups. This also invalidates the last calculation for the purposes of nearestInfluences,
201     * at least for the overload that takes only a Coord.
202     * @param influences a jagged array of Coord arrays, where the inner arrays are groups of influences
203     */
204    public void setInfluences(Coord[][] influences) {
205        this.influences = influences;
206        packedGroups = new short[influences.length][];
207        completed = false;
208    }
209}