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}