001package squidpony.squidmath; 002 003import squidpony.squidai.AimLimit; 004import squidpony.squidai.Reach; 005import squidpony.squidgrid.Direction; 006import squidpony.squidgrid.Radius; 007 008import java.util.ArrayList; 009import java.util.Arrays; 010import java.util.Collection; 011import java.util.List; 012 013 014/** 015 * Provides static methods to encode Coords as single primitive ints in various ways, hence the namesake, but also 016 * provides advanced methods to encode 2D arrays of various sorts produced by SquidLib in extremely memory-efficient 017 * representations, and decode those representations to various types of 2D array on-demand. IMPORTANT: you must call 018 * {@link #init()} before using this class if you do not already use a SquidLib class that does so. It is a good habit 019 * to call init() in your main() method or primary game entry point if you use CoordPacker. Failure to call init() will 020 * not result in exceptions, but will make results inaccurate. 021 * 022 * There's a detailed introduction 023 * <a href="https://github.com/SquidPony/SquidLib/wiki/Handling-Map-Regions-with-CoordPacker">on the SquidLib wiki</a>, 024 * which is probably the best way to learn the techniques possible with this class. Most methods in this aren't useful 025 * on their own, but can be mixed and matched to get specific regions from a map, such as all floors not adjacent to a 026 * wall, or all grass within 3 squares of deep or shallow water, with walls blocking the distance measurement. You can 027 * also use packed data that this class produces as keys for {@link RegionMap} to associate values with regions. 028 * <br> 029 * NOTE: Internally, this class is atypically complex and low-level for SquidLib because it is attempting to attain some 030 * very challenging performance gains. You should not consider it idiomatic SquidLib code or start modifying it unless 031 * you have a good grasp of bitwise operations and the performance implications, particularly in regard to memory 032 * consumption, that higher-level and more convenient Java programming techniques have. 033 * <br> 034 * NOTE 2: This class fills a role that is very similar to {@link GreasedRegion}, and there are times when code will do 035 * better using CoordPacker than GreasedRegion and vice versa. GreasedRegion uses objects and tries to change them 036 * in-place whenever possible instead of allocating new data; CoordPacker uses short[] values that it never changes 037 * in-place and frequently allocates new short[] values to represent data. GreasedRegion stores the full map without any 038 * compression beyond "one bit per cell" and always needs to store all cells on the map (sometimes slightly more); 039 * CoordPacker can compress some data to significantly less than one bit per cell, and doesn't care about the maximum 040 * bounds of the map as long as it fits inside a 256x256 square. GreasedRegion is significantly faster than CoordPacker 041 * when performing any operations that move, shrink, or expand an area, such as {@link #expand(short[], int, int, int)}, 042 * {@link #retract(short[], int, int, int)}, and {@link #translate(short[], int, int, int, int)}. CoordPacker usually 043 * (not always) uses somewhat less memory than GreasedRegion, though both use very little unless the maps are very 044 * large or very numerous. Both can do essentially the same things, except that GreasedRegion has no equivalent to the 045 * {@link #packMulti(byte[][], int)} and other Multi kinds of method, no {@link #radiate(short[], short[], int)}, and no 046 * {@link #reachable(short[], short[], Reach)}, while CoordPacker has no equivalent to 047 * {@link GreasedRegion#expandSeriesToLimit()} and other ToLimit kinds of method, no 048 * {@link GreasedRegion#toggle(int, int)}, no {@link GreasedRegion#deteriorate(RandomnessSource, int)}, no 049 * {@link GreasedRegion#insert(int, int, GreasedRegion)} (though CoordPacker can generally use 050 * {@link #unionPacked(short[], short[])} for that), and several other methods don't have equivalents. In general, you 051 * will probably find GreasedRegion more intuitive because it involves working with objects instead of a short[] that is 052 * treated like a particular kind of data, and the methods are also somewhat more clearly-named. GreasedRegion also 053 * implements Collection of Coord, while the short[] data can't implement anything. A way around this for CoordPacker is 054 * the {@link squidpony.squidgrid.zone.CoordPackerZone} class; both that and GreasedRegion implement the 055 * {@link squidpony.squidgrid.zone.Zone} interface, which ensures a way to get a List of Coord from the Zone. 056 * <br> 057 * The pack() methods in this class take a 2D array with a clear division between cells in an "on" state and cells in an 058 * "off" state, and they produce a very tightly compressed short array that can be losslessly decompressed with the 059 * unpack() methods to a boolean 2D array that stores equivalent on/off data to the input. The packMulti() method in 060 * this class takes a double 2D array that has more than two states that may need to be encoded, such as an FOV map that 061 * stores light level as a value between 0.0 and 1.0 instead of just on or off, and an additional double array that 062 * defines what states should be distinguished in the result (for example, if the FOV can store values that differ by 063 * 0.1 for a FOV radius of 10, you could pass the array of 10 levels: 0.1, 0.2, 0.3, ... 0.9, 1.0). The value returned 064 * by packMulti() is a short[][], but with different array lengths for each sub-array (a jagged array); the length of 065 * the short[][] is the same as the length of the levels array, and each sub-array corresponds to a different level of 066 * FOV lighting or other gradation as defined in levels. This short[][] can be passed to the unpackMultiByte() method in 067 * this class to produce a byte 2D array where the original levels correspond to progressively greater bytes, with 0 068 * used for cells that were less than the smallest value in levels, 1 for values that were only greater than the 069 * smallest value, and no others, in levels, then 2 for larger values, etc. until it places a byte with a value equal to 070 * the length of levels in the cells that are the highest. There is also the unpackMultiDouble() method in this class 071 * that takes the same short[][] unpackMultiByte() can take, but also takes a levels double array that should be the 072 * same as the one used to compress short[][]. It will return a double 2D array with any cells that were smaller than 073 * the smallest value in levels assigned 0.0, and any other cells will be assigned a double that corresponds to the 074 * highest value in levels that does not exceed the original double at that location in the unpacked data. To make this 075 * more clear, if you have 4 levels: [0.25, 0.5, 0.75, 1.0] and you packMulti() on an FOV with a large radius and 076 * sample values 0.1, 0.45, 0.8, 1.0, you will get a packed short[][] with 4 sub-arrays to match the 4 levels. If you 077 * then pass the short[][] and levels to unpackMultiDouble later, much of the same radius will be filled, but because 078 * the sample value 0.1 was less than the smallest value in levels, its cell will be given 0.0. What was originally 0.45 079 * will be given the next-lower levels value, 0.25; 0.8 will be given 0.75, and 1.0 will remain 1.0. 080 * <br> 081 * This compression is meant to produce a short[] or short[][] that uses as little memory as possible for the specific 082 * case of compressing maps with these qualities: 083 * <ul> 084 * <li>Maps are not especially large for a grid-based game; the maximum size is 256x256 cells.</li> 085 * <li>The vast majority of that 256x256 space is either unused or filled with cells no greater than 0.</li> 086 * <li>The cells that are greater than 0 are mostly near each other, though separate areas are possible.</li> 087 * </ul> 088 * These properties are all shared by typical roguelike FOV maps, and the specificity of these circumstances mean 089 * extraordinarily dense compression can be achieved using the right combination of algorithms. In early testing, 090 * using dungeon maps generated by {@link squidpony.squidgrid.mapping.DungeonGenerator} that should be typical of 091 * roguelike maps and a diamond-shaped FOV with radius 8, compression of the short[] returned by pack() vs. 092 * the original double[][] (which wastefully represents 2 states with 8 bytes) yields average memory usage ratios 093 * between (with relatively optimal parameters) 0.0001237905030818498 in one of the best cases, and (with some very 094 * poor parameters for the dungeon, but still using a realistic FOV map) 0.003135985198889917 in one of the worst. 095 * <br> 096 * This table shows the results for the average of 100 runs of pack() in a map with a "good size" and 100 runs in a map 097 * with a "bad size." Both the compression ratio vs. a double[][] that stores only whether a cell is on or off and a 098 * boolean[][] that stores the same information are provided. 099 * <table BORDER CELLPADDING=3 CELLSPACING=1> 100 * <caption>Memory Performance of CoordPacker</caption> 101 * <tr> 102 * <th></th> 103 * <th>Bytes of RAM used, double 2D array</th> 104 * <th>Bytes of RAM used, boolean 2D array</th> 105 * <th>Average Bytes of RAM used, short 1D array (packed)</th> 106 * <th>Compression ratio, packed vs. doubles</th> 107 * <th>Compression ratio, packed vs. booleans</th> 108 * </tr> 109 * <tr> 110 * <td>240x240 dungeon map (good size)</td> 111 * <td>464656</td> 112 * <td>61456</td> 113 * <td>57.52</td> 114 * <td>0.0001237905030818498</td> 115 * <td>0.000935954178599323</td> 116 * </tr> 117 * <tr> 118 * <td>30x70 dungeon map (bad size)</td> 119 * <td>17296</td> 120 * <td>2656</td> 121 * <td>54.24</td> 122 * <td>0.003135985198889917</td> 123 * <td>0.020421686746987953</td> 124 * </tr> 125 * </table> 126 * In the best-case scenario of packing a 240x240 double array to a short array encoding two states, the result 127 * uses less than 1/8000 the memory that the input uses. Writing to disk can store both input and output more 128 * efficiently, but the method used here should ensure that even encoding the input FOV map as a flat sequence of 129 * single bits and compressing the file should still be on par with the output of pack() due to optimization to 130 * ensure nearby cells on a map are compressed together. 131 * <br> 132 * The technique used by this class is to walk along a Hilbert Curve, storing whether the walk is traveling through 133 * "on" or "off" cells, which can be determined by a comparison to a number or a boolean, then encoding alternate shorts 134 * into the short[] to be returned, with even-number indices (starting at 0) in the array corresponding to the number of 135 * contiguous cells walked through in the "off" state, and odd-number indices corresponding to the number of 136 * contiguous cells walked through in the "on" state. A user of this library does not need to understand the details 137 * and properties of this algorithm unless they want to generate maps that will compress more optimally. In short: 138 * <ul> 139 * <li>Smaller maps tend to be processed faster by pack(), since the nature of a Hilbert Curve means a map that 140 * fits in one half the width and one half the height of the curve only needs to walk one quarter of the Curve to 141 * get all the needed information.</li> 142 * <li>Smaller maps also compress less optimally ratio-wise than larger maps with the same area of "on" cells. The 143 * compression ratio approaches its best when using very large maps, such as 240x240, and encoding just a few 144 * cells on that map (such as for a small FOV radius or a cramped room). A map that is entirely "off" uses only 16 145 * bytes of RAM (the minimum for any array on the JVM).</li> 146 * <li>Unusually shaped maps can cause compression problems by forcing adjacent cells to sometimes require walking 147 * more cells than needed to get to an adjacent cell. For example, a map greater than 64 cells tall, but less than 148 * 33 cells wide, has properties that require walking through a large empty area to get to sometimes only a few 149 * cells that are "on" before it walks back through empty space. Similarly, a map that is greater than 128 cells 150 * tall but is otherwise narrow has the same property of requiring walking through empty space, but also requires 151 * the entire Curve to be walked even if the map's width is only a tiny fraction of the Curve's 256 cells.</li> 152 * </ul> 153 * <b>In shorter-than-short</b>, you'll get particularly good results for compression speed and compressed size with 154 * maps approximately these sizes: 240x240, 240x120, 120x120, 60x120, 60x60, 60x30, 30x30. The biggest maps have the 155 * best relative gain on compressed memory usage, and the smallest maps have the best compression speed. 156 *<br> 157 * The details of the algorithm are not terribly complex once you understand the Hilbert Curve. The simplified 158 * version of the Hilbert Curve that SquidLib employs is essentially a path through a square grid (it must have side 159 * lengths that are powers of 2, and SquidLib always uses 256), starting in the corner cell (x=0,y=0), ending in the 160 * corner cell (x=0,y=255), and traversing every other cell on the grid along its path without ever traveling in a 161 * loop, crossing the path it walked, or moving in any direction but one cell up, down, left, or right. The shape 162 * of the path this takes has the useful property of keeping most groups of cells walked through with similar x and 163 * y at similar distances traveled from the start of the curve, and most groups of cells with very dissimilar x and 164 * y at very different distances traveled. Since FOV and several other things you might want to encode with CoordPacker 165 * tends to be clustered in small areas and occupy more complicated shapes than straight lines due to dungeon layout 166 * blocking sections of FOV, the simplest paths of a wide zigzag from side-to-side, or an outward-going-in spiral, have 167 * rather poor behavior when determining how much of an area they pass through contiguously. The contiguous area trait 168 * is important because of the next step: Run-Length Encoding. 169 *<br> 170 * Run-Length Encoding is much simpler to explain than the Hilbert Curve, especially without visual aids. In the version 171 * SquidLib uses, only on or off states need to be recorded, so the method used here is smaller and more efficient than 172 * most methods that need to store repeated characters in strings (and letters, numbers, and punctuation clearly have 173 * more than 2 states). The technique works like this: 174 *<br> 175 * Start in the "off" state, walk down the Hilbert Curve counting how many cells you walk through that are still "off," 176 * and when you encounter a cell that is "on," you write down how many cells were off, transition to the "on" state. Now 177 * keep walking the Hilbert Curve, but counting how many cells you walk through that are still "on." When you reach 178 * an "off" cell, write down how many were "on," then start walking and counting again, with your count starting at 0. 179 * Repeat until you reach the end of the Hilbert Curve, but if you reach the end while counting "off" cells, you don't 180 * need to write down that number (a shortcut allows many maps to stop sooner than the 65,536th element of the Curve). 181 *<br> 182 * There are some additional traits that relate to the edge of the map being treated as "off" even though no 183 * calculations are done for cells out of map bounds, and some optimizations that ensure that maps that are smaller than 184 * a half, a quarter, or an eighth of the 256x256 curve in both dimensions (and sometimes just one) only need to walk a 185 * portion of the Hilbert Curve and simply skip the rest without walking it. 186 *<br> 187 * The Hilbert Curve has not been definitively proven to be the best possible path to ensure 1D distance and 2D location 188 * are similar, but it has been extensively used for tasks that require similar locations for similar distances (in 189 * particular, it has become useful in supercomputing clusters for allocating related work to physically nearby 190 * machines), and since there hasn't been anything with better spatial properties discovered yet, this technique should 191 * remain useful for some time. 192 * <br> 193 * Created by Tommy Ettinger on 10/1/2015. 194 * @author Tommy Ettinger 195 */ 196public class CoordPacker { 197 public static final int DEPTH = 8; 198 private static final int BITS = DEPTH << 1; 199 200 public static short[] hilbertX = new short[0x10000], hilbertY = new short[0x10000], 201 hilbertDistances = new short[0x10000], mooreX = new short[0x100], mooreY = new short[0x100], 202 mooreDistances = new short[0x100], hilbert3X = new short[0x200], hilbert3Y = new short[0x200], 203 hilbert3Z = new short[0x200], hilbert3Distances = new short[0x200], 204 ALL_WALL = new short[0], ALL_ON = new short[]{0, -1}; 205 private static boolean initialized; 206 public static void init() { 207 if(initialized) return; 208 /* 209 Coord c; 210 for (int i = 0; i < 0x10000; i++) { 211 c = hilbertToCoordNoLUT(i); 212 hilbertX[i] = (short) c.x; 213 hilbertY[i] = (short) c.y; 214 hilbertDistances[c.x + (c.y << 8)] = (short) i; 215 }*/ 216 for (int x = 0; x < 256; x++) { 217 for (int y = 0; y < 256; y++) { 218 computeHilbert2D(x, y); 219 } 220 } 221 222 for (int x = 0; x < 8; x++) { 223 for (int y = 0; y < 8; y++) { 224 for (int z = 0; z < 8; z++) { 225 computeHilbert3D(x, y, z); 226 } 227 } 228 } 229 230 for (int i = 64; i < 128; i++) { 231 mooreX[i - 64] = hilbertX[i]; 232 mooreY[i - 64] = hilbertY[i]; 233 mooreDistances[mooreX[i - 64] + (mooreY[i - 64] << 4)] = (short)(i - 64); 234 235 mooreX[i] = hilbertX[i]; 236 mooreY[i] = (short)(hilbertY[i] + 8); 237 mooreDistances[mooreX[i] + (mooreY[i] << 4)] = (short)(i); 238 239 mooreX[i + 64] = (short)(15 - hilbertX[i]); 240 mooreY[i + 64] = (short)(15 - hilbertY[i]); 241 mooreDistances[mooreX[i + 64] + (mooreY[i + 64] << 4)] = (short)(i + 64); 242 243 mooreX[i + 128] = (short)(15 - hilbertX[i]); 244 mooreY[i + 128] = (short)(7 - hilbertY[i]); 245 mooreDistances[mooreX[i + 128] + (mooreY[i + 128] << 4)] = (short)(i + 128); 246 } 247 initialized = true; 248 } 249 250 private CoordPacker() 251 { 252 } 253 /** 254 * Compresses a double[][] (typically one generated by {@link squidpony.squidgrid.FOV}) that only stores two 255 * relevant states (one of which should be 0 or less, the other greater than 0), returning a short[] as described in 256 * the {@link CoordPacker} class documentation. This short[] can be passed to CoordPacker.unpack() to restore the 257 * relevant states and their positions as a boolean[][] (with false meaning 0 or less and true being any double 258 * greater than 0). As stated in the class documentation, the compressed result is intended to use as little memory 259 * as possible for most roguelike FOV maps. To avoid floating-point number comparison issues, this actually needs 260 * doubles to be greater than 0.0001, which should never cause incorrect behavior with FOV's double[][] maps. 261 * <br> 262 * <b>To store more than two states</b>, you should use packMulti(). 263 * 264 * @param map a double[][] that probably was returned by FOV. If you obtained a double[][] from DijkstraMap, it 265 * will not meaningfully compress with this method. 266 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 267 */ 268 public static short[] pack(double[][] map) 269 { 270 if(map == null || map.length == 0) 271 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 272 int xSize = map.length, ySize = map[0].length; 273 if(xSize > 256 || ySize > 256) 274 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 275 ShortVLA packing = new ShortVLA(64); 276 boolean on = false, anyAdded = false, current; 277 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 278 if(ySize <= 128) { 279 limit >>= 1; 280 if (xSize <= 128) { 281 limit >>= 1; 282 if (xSize <= 64) { 283 limit >>= 1; 284 if (ySize <= 64) { 285 limit >>= 1; 286 if (ySize <= 32) { 287 limit >>= 1; 288 if (xSize <= 32) { 289 limit >>= 1; 290 } 291 } 292 } 293 } 294 } 295 } 296 297 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 298 { 299 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 300 if(on) { 301 on = false; 302 packing.add((short) skip); 303 skip = 0; 304 anyAdded = true; 305 } 306 continue; 307 } 308 ml++; 309 current = map[hilbertX[i]][hilbertY[i]] > 0.0001; 310 if(current != on) 311 { 312 packing.add((short) skip); 313 skip = 0; 314 on = current; 315 anyAdded = true; 316 } 317 } 318 if(on) 319 packing.add((short)skip); 320 else if(!anyAdded) 321 return ALL_WALL; 322 return packing.toArray(); 323 } 324 325 /** 326 * Compresses a double[][] (typically one generated by {@link squidpony.squidai.DijkstraMap}) that only stores two 327 * relevant states (one of which should be equal to or less than threshold, the other greater than threshold), 328 * returning a short[] as described in the {@link CoordPacker} class documentation. This short[] can be passed to 329 * CoordPacker.unpack() to restore the relevant states and their positions as a boolean[][] (with true meaning 330 * threshold or less and false being any double greater than threshold). As stated in the class documentation, the 331 * compressed result is intended to use as little memory as possible for most roguelike FOV maps, but here is also 332 * useful for compressing physical maps and gradient maps from DijkstraMap. 333 * <br> 334 * <b>To store more than two states</b>, you should use packMulti(). 335 * 336 * @param map a double[][] that probably relates in some way to DijkstraMap. 337 * @param threshold upper inclusive; any double greater than this will be off, any equal or less will be on 338 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 339 */ 340 public static short[] pack(double[][] map, double threshold) 341 { 342 if(map == null || map.length == 0) 343 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 344 int xSize = map.length, ySize = map[0].length; 345 if(xSize > 256 || ySize > 256) 346 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 347 ShortVLA packing = new ShortVLA(64); 348 boolean on = false, anyAdded = false, current; 349 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 350 if(ySize <= 128) { 351 limit >>= 1; 352 if (xSize <= 128) { 353 limit >>= 1; 354 if (xSize <= 64) { 355 limit >>= 1; 356 if (ySize <= 64) { 357 limit >>= 1; 358 if (ySize <= 32) { 359 limit >>= 1; 360 if (xSize <= 32) { 361 limit >>= 1; 362 } 363 } 364 } 365 } 366 } 367 } 368 369 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 370 { 371 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 372 if(on) { 373 on = false; 374 packing.add((short) skip); 375 skip = 0; 376 anyAdded = true; 377 } 378 continue; 379 } 380 ml++; 381 current = map[hilbertX[i]][hilbertY[i]] <= threshold; 382 if(current != on) 383 { 384 packing.add((short) skip); 385 skip = 0; 386 on = current; 387 anyAdded = true; 388 } 389 } 390 if(on) 391 packing.add((short)skip); 392 else if(!anyAdded) 393 return ALL_WALL; 394 return packing.toArray(); 395 } 396 397 398 /** 399 * Compresses a double[][] (typically one generated by {@link squidpony.squidai.DijkstraMap}) that only stores two 400 * relevant states (a state for values between lowerBound (inclusive) and upperBound (exclusive), and another state 401 * for anything else), returning a short[] as described in the {@link CoordPacker} class documentation. This short[] 402 * can be passed to CoordPacker.unpack() to restore the relevant states and their positions as a boolean[][] (with 403 * true meaning between the bounds and false being anything outside them). As stated in the class documentation, the 404 * compressed result is intended to use as little memory as possible for most roguelike FOV maps, but here is also 405 * useful for compressing physical maps and gradient maps from DijkstraMap. 406 * <br> 407 * <b>To store more than two states</b>, you should use packMulti(). 408 * 409 * @param map a double[][] that probably relates in some way to DijkstraMap. 410 * @param lowerBound lower inclusive; any double lower than this will be off, any equal to or greater than this, 411 * but less than upper, will be on 412 * @param upperBound upper exclusive; any double greater than this will be off, any doubles both less than this 413 * and equal to or greater than lower will be on 414 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 415 */ 416 public static short[] pack(double[][] map, double lowerBound, double upperBound) 417 { 418 if(map == null || map.length == 0) 419 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 420 int xSize = map.length, ySize = map[0].length; 421 if(xSize > 256 || ySize > 256) 422 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 423 ShortVLA packing = new ShortVLA(64); 424 boolean on = false, anyAdded = false, current; 425 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 426 if(ySize <= 128) { 427 limit >>= 1; 428 if (xSize <= 128) { 429 limit >>= 1; 430 if (xSize <= 64) { 431 limit >>= 1; 432 if (ySize <= 64) { 433 limit >>= 1; 434 if (ySize <= 32) { 435 limit >>= 1; 436 if (xSize <= 32) { 437 limit >>= 1; 438 } 439 } 440 } 441 } 442 } 443 } 444 445 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 446 { 447 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 448 if(on) { 449 on = false; 450 packing.add((short) skip); 451 skip = 0; 452 anyAdded = true; 453 } 454 continue; 455 } 456 ml++; 457 current = map[hilbertX[i]][hilbertY[i]] >= lowerBound && map[hilbertX[i]][hilbertY[i]] < upperBound; 458 if(current != on) 459 { 460 packing.add((short) skip); 461 skip = 0; 462 on = current; 463 anyAdded = true; 464 } 465 } 466 if(on) 467 packing.add((short)skip); 468 else if(!anyAdded) 469 return ALL_WALL; 470 return packing.toArray(); 471 } 472 473 /** 474 * Compresses a byte[][] (typically one generated by an FOV-like method) that only stores two 475 * relevant states (one of which should be 0 or less, the other greater than 0), returning a short[] as described in 476 * the {@link CoordPacker} class documentation. This short[] can be passed to CoordPacker.unpack() to restore the 477 * relevant states and their positions as a boolean[][] (with false meaning 0 or less and true being any byte 478 * greater than 0). As stated in the class documentation, the compressed result is intended to use as little memory 479 * as possible for most roguelike FOV maps. 480 *<br> 481 * <b>To store more than two states</b>, you should use packMulti(). 482 * 483 * @param map a byte[][] that probably was returned by an FOV-like method. 484 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 485 */ 486 public static short[] pack(byte[][] map) 487 { 488 if(map == null || map.length == 0) 489 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 490 int xSize = map.length, ySize = map[0].length; 491 if(xSize > 256 || ySize > 256) 492 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 493 ShortVLA packing = new ShortVLA(64); 494 boolean on = false, anyAdded = false, current; 495 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 496 if(ySize <= 128) { 497 limit >>= 1; 498 if (xSize <= 128) { 499 limit >>= 1; 500 if (xSize <= 64) { 501 limit >>= 1; 502 if (ySize <= 64) { 503 limit >>= 1; 504 if (ySize <= 32) { 505 limit >>= 1; 506 if (xSize <= 32) { 507 limit >>= 1; 508 } 509 } 510 } 511 } 512 } 513 } 514 515 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 516 { 517 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 518 if(on) { 519 on = false; 520 packing.add((short) skip); 521 skip = 0; 522 anyAdded = true; 523 } 524 continue; 525 } 526 ml++; 527 current = map[hilbertX[i]][hilbertY[i]] > 0; 528 if(current != on) 529 { 530 packing.add((short) skip); 531 skip = 0; 532 on = current; 533 anyAdded = true; 534 } 535 } 536 if(on) 537 packing.add((short)skip); 538 else if(!anyAdded) 539 return ALL_WALL; 540 return packing.toArray(); 541 } 542 543 /** 544 * Compresses a boolean[][], returning a short[] as described in the {@link CoordPacker} class documentation. This 545 * short[] can be passed to CoordPacker.unpack() to restore the relevant states and their positions as a boolean[][] 546 * As stated in the class documentation, the compressed result is intended to use as little memory as possible for 547 * most roguelike FOV maps. 548 * 549 * @param map a boolean[][] that should ideally be mostly false. 550 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 551 */ 552 public static short[] pack(boolean[][] map) 553 { 554 if(map == null || map.length == 0) 555 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 556 int xSize = map.length, ySize = map[0].length; 557 if(xSize > 256 || ySize > 256) 558 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 559 ShortVLA packing = new ShortVLA(64); 560 boolean on = false, anyAdded = false, current; 561 short skip = 0, hx, hy; 562 int limit = 0x10000, mapLimit = xSize * ySize; 563 if(ySize <= 128) { 564 limit >>= 1; 565 if (xSize <= 128) { 566 limit >>= 1; 567 if (xSize <= 64) { 568 limit >>= 1; 569 if (ySize <= 64) { 570 limit >>= 1; 571 if (ySize <= 32) { 572 limit >>= 1; 573 if (xSize <= 32) { 574 limit >>= 1; 575 } 576 } 577 } 578 } 579 } 580 } 581 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 582 { 583 hx = hilbertX[i]; 584 hy = hilbertY[i]; 585 if(hx >= xSize || hy >= ySize) { 586 if(on) { 587 on = false; 588 packing.add(skip); 589 skip = 0; 590 anyAdded = true; 591 } 592 continue; 593 } 594 ml++; 595 current = map[hx][hy]; 596 if(current != on) 597 { 598 packing.add(skip); 599 skip = 0; 600 on = current; 601 anyAdded = true; 602 } 603 } 604 if(on) 605 packing.add(skip); 606 else if(!anyAdded) 607 return ALL_WALL; 608 return packing.toArray(); 609 } 610 611 /** 612 * Compresses a char[][] (typically one generated by a map generating method) so only the cells that equal the yes 613 * parameter will be encoded as "on", returning a short[] as described in 614 * the {@link CoordPacker} class documentation. This short[] can be passed to CoordPacker.unpack() to restore the 615 * positions of chars that equal the parameter yes as a boolean[][] (with false meaning not equal and true equal to 616 * yes). As stated in the class documentation, the compressed result is intended to use as little memory 617 * as possible for most roguelike FOV maps, but this will typically not be used for FOV (more typical uses are for 618 * walls, floors, and so on). This can still be useful for certain kinds of processing that can be done more 619 * efficiently on packed data than on 2D arrays, like unions, intersections, and random elements or subsets. 620 * 621 * @param map a char[][] that may contain some area of cells that you want stored as packed data 622 * @param yes the char to encode as "on" in the result; all others are encoded as "off" 623 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 624 */ 625 public static short[] pack(char[][] map, char yes) 626 { 627 if(map == null || map.length == 0) 628 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 629 int xSize = map.length, ySize = map[0].length; 630 if(xSize > 256 || ySize > 256) 631 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 632 ShortVLA packing = new ShortVLA(64); 633 boolean on = false, anyAdded = false, current; 634 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 635 if(ySize <= 128) { 636 limit >>= 1; 637 if (xSize <= 128) { 638 limit >>= 1; 639 if (xSize <= 64) { 640 limit >>= 1; 641 if (ySize <= 64) { 642 limit >>= 1; 643 if (ySize <= 32) { 644 limit >>= 1; 645 if (xSize <= 32) { 646 limit >>= 1; 647 } 648 } 649 } 650 } 651 } 652 } 653 654 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 655 { 656 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 657 if(on) { 658 on = false; 659 packing.add((short) skip); 660 skip = 0; 661 anyAdded = true; 662 } 663 continue; 664 } 665 ml++; 666 current = map[hilbertX[i]][hilbertY[i]] == yes; 667 if(current != on) 668 { 669 packing.add((short) skip); 670 skip = 0; 671 on = current; 672 anyAdded = true; 673 } 674 } 675 if(on) 676 packing.add((short)skip); 677 else if(!anyAdded) 678 return ALL_WALL; 679 return packing.toArray(); 680 } 681 682 /** 683 * Compresses a char[][] (typically one generated by a map generating method) so only the cells that are contained 684 * in the yes parameter will be encoded as "on", returning a short[] as described in 685 * the {@link CoordPacker} class documentation. This short[] can be passed to CoordPacker.unpack() to restore the 686 * positions of chars that equal the parameter yes as a boolean[][] (with false meaning not equal and true equal to 687 * yes). As stated in the class documentation, the compressed result is intended to use as little memory 688 * as possible for most roguelike FOV maps, but this will typically not be used for FOV (more typical uses are for 689 * walls, floors, and so on). This can still be useful for certain kinds of processing that can be done more 690 * efficiently on packed data than on 2D arrays, like unions, intersections, and random elements or subsets. 691 * 692 * @param map a char[][] that may contain some area of cells that you want stored as packed data 693 * @param yes the vararg or array of chars to encode as "on" in the result; all others are encoded as "off" 694 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 695 */ 696 public static short[] pack(char[][] map, char... yes) 697 { 698 if(yes == null || yes.length == 0) 699 return ALL_WALL; 700 if(yes.length == 1) 701 return pack(map, yes[0]); 702 if(map == null || map.length == 0) 703 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 704 int xSize = map.length, ySize = map[0].length; 705 if(xSize > 256 || ySize > 256) 706 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 707 ShortVLA packing = new ShortVLA(64); 708 boolean on = false, anyAdded = false, current; 709 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 710 if(ySize <= 128) { 711 limit >>= 1; 712 if (xSize <= 128) { 713 limit >>= 1; 714 if (xSize <= 64) { 715 limit >>= 1; 716 if (ySize <= 64) { 717 limit >>= 1; 718 if (ySize <= 32) { 719 limit >>= 1; 720 if (xSize <= 32) { 721 limit >>= 1; 722 } 723 } 724 } 725 } 726 } 727 } 728 char c; 729 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 730 { 731 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 732 if(on) { 733 on = false; 734 packing.add((short) skip); 735 skip = 0; 736 anyAdded = true; 737 } 738 continue; 739 } 740 ml++; 741 c = map[hilbertX[i]][hilbertY[i]]; 742 current = false; 743 for (int j = 0; j < yes.length; j++) { 744 if(yes[j] == c) 745 { 746 current = true; 747 break; 748 } 749 } 750 if(current != on) 751 { 752 packing.add((short) skip); 753 skip = 0; 754 on = current; 755 anyAdded = true; 756 } 757 } 758 if(on) 759 packing.add((short)skip); 760 else if(!anyAdded) 761 return ALL_WALL; 762 return packing.toArray(); 763 } 764 /** 765 * Compresses a int[][] (typically one generated by MixedGenerator.getEnvironment()) so only the cells that equal 766 * the yes parameter will be encoded as "on", returning a short[] as described in 767 * the {@link CoordPacker} class documentation. This short[] can be passed to CoordPacker.unpack() to restore the 768 * positions of ints that equal the parameter yes as a boolean[][] (with false meaning not equal and true equal to 769 * yes). As stated in the class documentation, the compressed result is intended to use as little memory 770 * as possible for most roguelike FOV maps, but this will typically not be used for FOV (more typical uses are for 771 * walls, floors, and so on). This can still be useful for certain kinds of processing that can be done more 772 * efficiently on packed data than on 2D arrays, like unions, intersections, and random elements or subsets. 773 * 774 * @param map a int[][] that may contain some area of cells that you want stored as packed data 775 * @param yes the int to encode as "on" in the result; all others are encoded as "off" 776 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 777 */ 778 public static short[] pack(int[][] map, int yes) 779 { 780 if(map == null || map.length == 0) 781 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 782 int xSize = map.length, ySize = map[0].length; 783 if(xSize > 256 || ySize > 256) 784 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 785 ShortVLA packing = new ShortVLA(64); 786 boolean on = false, anyAdded = false, current; 787 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 788 if(ySize <= 128) { 789 limit >>= 1; 790 if (xSize <= 128) { 791 limit >>= 1; 792 if (xSize <= 64) { 793 limit >>= 1; 794 if (ySize <= 64) { 795 limit >>= 1; 796 if (ySize <= 32) { 797 limit >>= 1; 798 if (xSize <= 32) { 799 limit >>= 1; 800 } 801 } 802 } 803 } 804 } 805 } 806 807 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 808 { 809 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 810 if(on) { 811 on = false; 812 packing.add((short) skip); 813 skip = 0; 814 anyAdded = true; 815 } 816 continue; 817 } 818 ml++; 819 current = map[hilbertX[i]][hilbertY[i]] == yes; 820 if(current != on) 821 { 822 packing.add((short) skip); 823 skip = 0; 824 on = current; 825 anyAdded = true; 826 } 827 } 828 if(on) 829 packing.add((short)skip); 830 else if(!anyAdded) 831 return ALL_WALL; 832 return packing.toArray(); 833 } 834 835 /** 836 * Compresses a int[][] (typically one generated by MixedGenerator.getEnvironment()) so only the cells that are 837 * contained in the yes parameter will be encoded as "on", returning a short[] as described in 838 * the {@link CoordPacker} class documentation. This short[] can be passed to CoordPacker.unpack() to restore the 839 * positions of ints that equal the parameter yes as a boolean[][] (with false meaning not equal and true equal to 840 * yes). As stated in the class documentation, the compressed result is intended to use as little memory 841 * as possible for most roguelike FOV maps, but this will typically not be used for FOV (more typical uses are for 842 * walls, floors, and so on). This can still be useful for certain kinds of processing that can be done more 843 * efficiently on packed data than on 2D arrays, like unions, intersections, and random elements or subsets. 844 * 845 * @param map a int[][] that may contain some area of cells that you want stored as packed data 846 * @param yes the vararg or array of ints to encode as "on" in the result; all others are encoded as "off" 847 * @return a packed short[] that should, in most circumstances, be passed to unpack() when it needs to be used. 848 */ 849 public static short[] pack(int[][] map, int... yes) 850 { 851 if(map == null || map.length == 0) 852 throw new ArrayIndexOutOfBoundsException("CoordPacker.pack() must be given a non-empty array"); 853 int xSize = map.length, ySize = map[0].length; 854 if(xSize > 256 || ySize > 256) 855 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 856 ShortVLA packing = new ShortVLA(64); 857 boolean on = false, anyAdded = false, current; 858 int skip = 0, limit = 0x10000, mapLimit = xSize * ySize; 859 if(ySize <= 128) { 860 limit >>= 1; 861 if (xSize <= 128) { 862 limit >>= 1; 863 if (xSize <= 64) { 864 limit >>= 1; 865 if (ySize <= 64) { 866 limit >>= 1; 867 if (ySize <= 32) { 868 limit >>= 1; 869 if (xSize <= 32) { 870 limit >>= 1; 871 } 872 } 873 } 874 } 875 } 876 } 877 int c; 878 for(int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip++) 879 { 880 if(hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 881 if(on) { 882 on = false; 883 packing.add((short) skip); 884 skip = 0; 885 anyAdded = true; 886 } 887 continue; 888 } 889 ml++; 890 c = map[hilbertX[i]][hilbertY[i]]; 891 current = false; 892 for (int j = 0; j < yes.length; j++) { 893 if(yes[j] == c) 894 { 895 current = true; 896 break; 897 } 898 } 899 if(current != on) 900 { 901 packing.add((short) skip); 902 skip = 0; 903 on = current; 904 anyAdded = true; 905 } 906 } 907 if(on) 908 packing.add((short)skip); 909 else if(!anyAdded) 910 return ALL_WALL; 911 return packing.toArray(); 912 } 913 914 /** 915 * Given a number of total levels to consider separate in a double[][] such as an FOV result, this produces a levels 916 * array that can be passed to packMulti() to ensure that you have the requested number of separate levels in the 917 * multi-packed result. For example, if you pass 6 to this method, it will return a length-6 double array, and if 918 * you pass that as the levels parameter to packMulti(), then that method will return a length-6 array of short 919 * arrays that each encode a region that met a different minimum value in the originally packed double[][]. 920 * The behavior of this method causes any doubles that are closer to 1.0 / totalLevels than they are to 0.0 to be 921 * packed as "on" in at least one of packMulti()'s resultant sub-arrays. This allows Radius.CIRCLE or similar FOV 922 * that produces cells with values that aren't evenly distributed between 0.0 and 1.0 to be used without causing an 923 * explosion in the number of required levels. 924 * <br> 925 * <b>This method should not be used to generate levels for unpacking; it is only intended for packing.</b> Use the 926 * similar method generateLightLevels() to generate a levels array that is suitable for unpacking FOV. 927 * @param totalLevels the number of separate levels to group doubles into 928 * @return a double[] suitable as a levels parameter for packMulti() 929 */ 930 public static double[] generatePackingLevels(int totalLevels) 931 { 932 if (totalLevels > 63 || totalLevels <= 0) 933 throw new UnsupportedOperationException( 934 "Bad totalLevels; should be 0 < totalLevels < 64 but was given " + 935 totalLevels); 936 937 double[] levels = new double[totalLevels]; 938 for (int i = 0; i < totalLevels; i++) { 939 levels[i] = (i + 0.5) / totalLevels; 940 } 941 return levels; 942 } 943 944 /** 945 * Given a number of total levels to consider separate in a double[][] such as an FOV result, this produces a levels 946 * array that can be passed to unpackMultiDouble() to ensure that the minimum double returned for an "on" cell is 947 * 1.0 / totalLevels, and every progressively tighter level in the short[][] being unpacked will be close to a 948 * multiple of that minimum double value. This only applies to "on" cells; any cells that did not meet a minimum 949 * value when packed will still be 0.0. For example, if you pass 6 to this method, it will return a length-6 double 950 * array, and if you pass that as the levels parameter to unpackMultiDouble(), then that method will return a 951 * double[][] with no more than totalLevels + 1 used values, ranging from 0.0 to 1.0 with evenly spaced values, all 952 * multiples of 1.0 / totalLevels, in between. 953 * <br> 954 * <b>This method should not be used to generate levels for packing; it is only intended for unpacking.</b> Use the 955 * similar method generatePackingLevels() to generate a levels array that is suitable for packing double[][] values. 956 * @param totalLevels the number of separate levels to assign doubles; this MUST match the size of the levels 957 * parameter used to pack a double[][] with packMulti() if this is used to unpack that data 958 * @return a double[] suitable as a levels parameter for unpackMultiDouble() 959 */ 960 public static double[] generateLightLevels(int totalLevels) 961 { 962 if (totalLevels > 63 || totalLevels <= 0) 963 throw new UnsupportedOperationException( 964 "Bad totalLevels; should be 0 < totalLevels < 64 but was given " + 965 totalLevels); 966 967 double[] levels = new double[totalLevels]; 968 for (int i = 0; i < totalLevels; i++) { 969 levels[i] = (i + 1.0) / totalLevels; 970 } 971 return levels; 972 } 973 974 /** 975 * Compresses a double[][] (typically one generated by {@link squidpony.squidgrid.FOV}) that stores any number of 976 * states and a double[] storing up to 63 states, ordered from lowest to highest, returning a short[][] as described 977 * in the {@link CoordPacker} class documentation. This short[][] can be passed to CoordPacker.unpackMultiDouble() 978 * to restore the state at a position to the nearest state in levels, rounded down, and return a double[][] that 979 * should preserve the states as closely as intended for most purposes. <b>For compressing FOV, you should generate 980 * levels with CoordPacker.generatePackingLevels()</b> instead of manually creating the array, because some 981 * imprecision is inherent in floating point math and comparisons are often incorrect between FOV with multiple 982 * levels and exact levels generated as simply as possible. generatePackingLevels() adds a small correction to the 983 * levels to compensate for floating-point math issues, which shouldn't affect the correctness of the results for 984 * FOV radii under 100. 985 *<br> 986 * As stated in the class documentation, the compressed result is intended to use as little memory as possible for 987 * most roguelike FOV maps. 988 *<br> 989 * <b>To store only two states</b>, you should use pack(), unless the double[][] divides data into on and off based 990 * on a relationship to some number other than 0.0. To (probably poorly) pack all the walls (and any cells with 991 * values higher than DijkstraMap.WALL) in a DijkstraMap's 2D array of doubles called dijkstraArray, you could call 992 * <code>packMulti(dijkstraArray, new double[]{DijkstraMap.WALL});</code> 993 * Then, you would use only the one sub-element of the returned short[][]. 994 * 995 * @param map a double[][] that probably was returned by FOV. If you obtained a double[][] from DijkstraMap, it 996 * will not meaningfully compress with this method unless you have very specific needs. 997 * @param levels a double[] starting with the lowest value that should be counted as "on" (the outermost cells of 998 * an FOV map that has multiple grades of brightness would be counted by this) and ascending until the 999 * last value; the last value should be highest (commonly 1.0 for FOV), and will be used for any cells 1000 * higher than all the other levels values. An example is an array of: 0.25, 0.5, 0.75, 1.0 1001 * @return a packed short[][] that should, in most circumstances, be passed to unpackMultiDouble() or 1002 * unpackMultiByte() when it needs to be used. The 2D array will be jagged with an outer length equal 1003 * to the length of levels and sub-arrays that go from having longer lengths early on to very compact 1004 * lengths by the end of the short[][]. 1005 */ 1006 public static short[][] packMulti(double[][] map, double[] levels) { 1007 if (levels == null || levels.length == 0) 1008 throw new UnsupportedOperationException("Must be given at least one level"); 1009 if (levels.length > 63) 1010 throw new UnsupportedOperationException( 1011 "Too many levels to efficiently pack; should be less than 64 but was given " + 1012 levels.length); 1013 if (map == null || map.length == 0) 1014 throw new ArrayIndexOutOfBoundsException("CoordPacker.packMulti() must be given a non-empty array"); 1015 int xSize = map.length, ySize = map[0].length; 1016 if (xSize > 256 || ySize > 256) 1017 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 1018 int limit = 0x10000, llen = levels.length, mapLimit = xSize * ySize; 1019 long on = 0, current = 0; 1020 ShortVLA[] packing = new ShortVLA[llen]; 1021 int[] skip = new int[llen]; 1022 1023 if(ySize <= 128) { 1024 limit >>= 1; 1025 if (xSize <= 128) { 1026 limit >>= 1; 1027 if (xSize <= 64) { 1028 limit >>= 1; 1029 if (ySize <= 64) { 1030 limit >>= 1; 1031 if (ySize <= 32) { 1032 limit >>= 1; 1033 if (xSize <= 32) { 1034 limit >>= 1; 1035 } 1036 } 1037 } 1038 } 1039 } 1040 } 1041 short[][] packed = new short[llen][]; 1042 for(int l = 0; l < llen; l++) { 1043 packing[l] = new ShortVLA(64); 1044 boolean anyAdded = false; 1045 for (int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip[l]++) { 1046 if (hilbertX[i] >= xSize || hilbertY[i] >= ySize) { 1047 if ((on & (1L << l)) != 0L) { 1048 on ^= (1L << l); 1049 packing[l].add((short) skip[l]); 1050 skip[l] = 0; 1051 anyAdded = true; 1052 } 1053 continue; 1054 } 1055 ml++; 1056 // sets the bit at position l in current to 1 if the following is true, 0 if it is false: 1057 // map[hilbertX[i]][hilbertY[i]] > levels[l] 1058 // looks more complicated than it is. 1059 current ^= ((map[hilbertX[i]][hilbertY[i]] > levels[l] ? -1 : 0) ^ current) & (1 << l); 1060 if (((current >> l) & 1L) != ((on >> l) & 1L)) { 1061 packing[l].add((short) skip[l]); 1062 skip[l] = 0; 1063 on = current; 1064 1065 // sets the bit at position l in on to the same as the bit at position l in current. 1066 on ^= (-((current >> l) & 1L) ^ on) & (1L << l); 1067 1068 anyAdded = true; 1069 } 1070 } 1071 1072 if (((on >> l) & 1L) == 1L) { 1073 packing[l].add((short) skip[l]); 1074 anyAdded = true; 1075 } 1076 if(!anyAdded) 1077 packed[l] = ALL_WALL; 1078 else 1079 packed[l] = packing[l].toArray(); 1080 } 1081 return packed; 1082 } 1083 1084 /** 1085 * Compresses a byte[][] that stores any number of states, and an int no more than 63, returning a short[][] as 1086 * described in the {@link CoordPacker} class documentation. This short[][] can be passed to 1087 * {@link #unpackMultiByte(short[][], int, int)} to restore the state at a position to the nearest state possible, 1088 * capped at levelCount, and return a byte[][] that should preserve the states as closely as intended for most 1089 * purposes. 1090 *<br> 1091 * As stated in the class documentation, the compressed result is intended to use as little memory as possible for 1092 * most roguelike FOV maps. 1093 *<br> 1094 * <b>To store only two states</b>, you should use pack(). 1095 * 1096 * @param map a byte[][] that probably was returned by a specialized FOV. 1097 * @param levelCount an int expressing how many levels should be present in the output; values greater than 1098 * levelCount in map will be treated as the highest level. 1099 * @return a packed short[][] that should, in most circumstances, be passed to unpackMultiDouble() or 1100 * unpackMultiByte() when it needs to be used. The 2D array will be jagged with an outer length equal 1101 * to the length of levels and sub-arrays that go from having longer lengths early on to very compact 1102 * lengths by the end of the short[][]. 1103 */ 1104 public static short[][] packMulti(byte[][] map, int levelCount) { 1105 if (map == null || map.length == 0) 1106 throw new ArrayIndexOutOfBoundsException("CoordPacker.packMulti() must be given a non-empty array"); 1107 if (levelCount > 63) 1108 throw new UnsupportedOperationException( 1109 "Too many levels to efficiently pack; should be less than 64 but was given " + 1110 levelCount); 1111 int xSize = map.length, ySize = map[0].length; 1112 if (xSize > 256 || ySize > 256) 1113 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 1114 int limit = 0x10000, mapLimit = xSize * ySize; 1115 long on = 0, current = 0; 1116 ShortVLA[] packing = new ShortVLA[levelCount]; 1117 int[] skip = new int[levelCount]; 1118 1119 if(ySize <= 128) { 1120 limit >>= 1; 1121 if (xSize <= 128) { 1122 limit >>= 1; 1123 if (xSize <= 64) { 1124 limit >>= 1; 1125 if (ySize <= 64) { 1126 limit >>= 1; 1127 if (ySize <= 32) { 1128 limit >>= 1; 1129 if (xSize <= 32) { 1130 limit >>= 1; 1131 } 1132 } 1133 } 1134 } 1135 } 1136 } 1137 short[][] packed = new short[levelCount][]; 1138 short x, y; 1139 for(int l = 0; l < levelCount; l++) { 1140 packing[l] = new ShortVLA(64); 1141 boolean anyAdded = false; 1142 for (int i = 0, ml = 0; i < limit && ml < mapLimit; i++, skip[l]++) { 1143 x = hilbertX[i]; 1144 y = hilbertY[i]; 1145 if (x >= xSize || y >= ySize) { 1146 if ((on & (1L << l)) != 0L) { 1147 on ^= (1L << l); 1148 packing[l].add((short) skip[l]); 1149 skip[l] = 0; 1150 anyAdded = true; 1151 } 1152 continue; 1153 } 1154 ml++; 1155 // sets the bit at position l in current to 1 if the following is true, 0 if it is false: 1156 // map[x][y] > l 1157 // looks more complicated than it is. 1158 current ^= ((map[x][y] > l ? -1L : 0L) ^ current) & (1L << l); 1159 if (((current >> l) & 1L) != ((on >> l) & 1L)) { 1160 packing[l].add((short) skip[l]); 1161 skip[l] = 0; 1162 on = current; 1163 1164 // sets the bit at position l in on to the same as the bit at position l in current. 1165 on ^= (-((current >> l) & 1L) ^ on) & (1L << l); 1166 1167 anyAdded = true; 1168 } 1169 } 1170 1171 if (((on >> l) & 1L) == 1L) { 1172 packing[l].add((short) skip[l]); 1173 anyAdded = true; 1174 } 1175 if(!anyAdded) 1176 packed[l] = ALL_WALL; 1177 else 1178 packed[l] = packing[l].toArray(); 1179 } 1180 return packed; 1181 } 1182 1183 /** 1184 * Decompresses a short[] returned by pack() or a sub-array of a short[][] returned by packMulti(), as described in 1185 * the {@link CoordPacker} class documentation. This returns a boolean[][] that stores the same values that were 1186 * packed if the overload of pack() taking a boolean[][] was used. If a double[][] was compressed with pack(), the 1187 * boolean[][] this returns will have true for all values greater than 0 and false for all others. If this is one 1188 * of the sub-arrays compressed by packMulti(), the index of the sub-array will correspond to an index in the levels 1189 * array passed to packMulti(), and any cells that were at least equal to the corresponding value in levels will be 1190 * true, while all others will be false. Width and height do not technically need to match the dimensions of the 1191 * original 2D array, but under most circumstances where they don't match, the data produced will be junk. 1192 * @param packed a short[] encoded by calling one of this class' packing methods on a 2D array. 1193 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1194 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1195 * @return a boolean[][] storing which cells encoded by packed are on (true) or off (false). 1196 */ 1197 public static boolean[][] unpack(short[] packed, int width, int height) 1198 { 1199 if(packed == null) 1200 throw new NullPointerException("CoordPacker.unpack() must be given a non-null array"); 1201 boolean[][] unpacked = new boolean[width][height]; 1202 if(packed.length == 0) 1203 return unpacked; 1204 boolean on = false; 1205 int idx = 0; 1206 short x, y; 1207 for(int p = 0; p < packed.length; p++, on = !on) { 1208 if (on) { 1209 for (int toSkip = idx +(packed[p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1210 x = hilbertX[idx]; 1211 y = hilbertY[idx]; 1212 if(x >= width || y >= height) 1213 continue; 1214 unpacked[x][y] = true; 1215 } 1216 } else { 1217 idx += packed[p] & 0xffff; 1218 } 1219 } 1220 return unpacked; 1221 } 1222 1223 /** 1224 * Decompresses a short[] returned by pack() or a sub-array of a short[][] returned by packMulti(), as described in 1225 * the {@link CoordPacker} class documentation. This returns a double[][] that stores 1.0 for true and 0.0 for 1226 * false if the overload of pack() taking a boolean[][] was used. If a double[][] was compressed with pack(), the 1227 * double[][] this returns will have 1.0 for all values greater than 0 and 0.0 for all others. If this is one 1228 * of the sub-arrays compressed by packMulti(), the index of the sub-array will correspond to an index in the levels 1229 * array passed to packMulti(), and any cells that were at least equal to the corresponding value in levels will be 1230 * 1.0, while all others will be 0.0. Width and height do not technically need to match the dimensions of the 1231 * original 2D array, but under most circumstances where they don't match, the data produced will be junk. 1232 * @param packed a short[] encoded by calling one of this class' packing methods on a 2D array. 1233 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1234 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1235 * @return a double[][] storing which cells encoded by packed are on (1.0) or off (0.0). 1236 */ 1237 public static double[][] unpackDouble(short[] packed, int width, int height) 1238 { 1239 if(packed == null) 1240 throw new NullPointerException("CoordPacker.unpack() must be given a non-null array"); 1241 double[][] unpacked = new double[width][height]; 1242 if(packed.length == 0) 1243 return unpacked; 1244 boolean on = false; 1245 int idx = 0; 1246 short x, y; 1247 for(int p = 0; p < packed.length; p++, on = !on) { 1248 if (on) { 1249 for (int toSkip = idx +(packed[p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1250 x = hilbertX[idx]; 1251 y = hilbertY[idx]; 1252 if(x >= width || y >= height) 1253 continue; 1254 unpacked[x][y] = 1.0; 1255 } 1256 } else { 1257 idx += packed[p] & 0xffff; 1258 } 1259 } 1260 return unpacked; 1261 } 1262 1263 /** 1264 * Decompresses a short[] returned by pack() or a sub-array of a short[][] returned by packMulti(), as described in 1265 * the {@link CoordPacker} class documentation. This returns a double[][] that stores 1.0 for true and 0.0 for 1266 * false if the overload of pack() taking a boolean[][] was used. If a double[][] was compressed with pack(), the 1267 * double[][] this returns will have 1.0 for all values greater than 0 and 0.0 for all others. If this is one 1268 * of the sub-arrays compressed by packMulti(), the index of the sub-array will correspond to an index in the levels 1269 * array passed to packMulti(), and any cells that were at least equal to the corresponding value in levels will be 1270 * 1.0, while all others will be 0.0. Width and height do not technically need to match the dimensions of the 1271 * original 2D array, but under most circumstances where they don't match, the data produced will be junk. 1272 * @param packed a short[] encoded by calling one of this class' packing methods on a 2D array. 1273 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1274 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1275 * @return a double[][] storing which cells encoded by packed are on (1.0) or off (0.0). 1276 */ 1277 public static double[][] unpackDoubleConical(short[] packed, int width, int height, int centerX, int centerY, 1278 double angle, double span) 1279 { 1280 if(packed == null) 1281 throw new NullPointerException("CoordPacker.unpack() must be given a non-null array"); 1282 double[][] unpacked = new double[width][height]; 1283 if(packed.length == 0) 1284 return unpacked; 1285 boolean on = false; 1286 int idx = 0; 1287 short x, y; 1288 double angle2 = Math.toRadians((angle > 360.0 || angle < 0.0) ? MathExtras.remainder(angle, 360.0) : angle); 1289 double span2 = Math.toRadians(span) * 0.5; 1290 1291 for(int p = 0; p < packed.length; p++, on = !on) { 1292 if (on) { 1293 for (int toSkip = idx +(packed[p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1294 x = hilbertX[idx]; 1295 y = hilbertY[idx]; 1296 if(x >= width || y >= height) 1297 continue; 1298 double newAngle = NumberTools.atan2(y - centerY, x - centerX) + Math.PI * 2; 1299 if(Math.abs(MathExtras.remainder(angle2 - newAngle, Math.PI * 2) - Math.PI) > span2) 1300 unpacked[x][y] = 0.0; 1301 else 1302 unpacked[x][y] = 1.0; 1303 } 1304 } else { 1305 idx += packed[p] & 0xffff; 1306 } 1307 } 1308 return unpacked; 1309 } 1310 1311 /** 1312 * Decompresses a short[][] returned by packMulti() and produces an approximation of the double[][] it compressed 1313 * using the given levels double[] as the values to assign, as described in the {@link CoordPacker} class 1314 * documentation. The length of levels and the length of the outer array of packed must be equal. However, the 1315 * levels array passed to this method should not be identical to the levels array passed to packMulti(); for FOV 1316 * compression, you should get an array for levels using generatePackingLevels(), but for decompression, you should 1317 * create levels using generateLightLevels(), which should more appropriately fit the desired output. Reusing the 1318 * levels array used to pack the FOV will usually produce values at the edge of FOV that are less than 0.01 but 1319 * greater than 0, and will have a maximum value somewhat less than 1.0; neither are usually desirable, but using a 1320 * different array made with generateLightLevels() will produce doubles ranging from 1.0 / levels.length to 1.0 at 1321 * the highest. Width and height do not technically need to match the dimensions of the original 2D array, but under 1322 * most circumstances where they don't match, the data produced will be junk. 1323 * @param packed a short[][] encoded by calling this class' packMulti() method on a 2D array. 1324 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1325 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1326 * @param levels a double[] that must have the same length as packed, and will be used to assign cells in the 1327 * returned double[][] based on what levels parameter was used to compress packed 1328 * @return a double[][] where the values that corresponded to the nth value in the levels parameter used to 1329 * compress packed will now correspond to the nth value in the levels parameter passed to this method. 1330 */ 1331 public static double[][] unpackMultiDouble(short[][] packed, int width, int height, double[] levels) 1332 { 1333 if(packed == null || packed.length == 0) 1334 throw new ArrayIndexOutOfBoundsException( 1335 "CoordPacker.unpackMultiDouble() must be given a non-empty array"); 1336 if (levels == null || levels.length != packed.length) 1337 throw new UnsupportedOperationException("The lengths of packed and levels must be equal"); 1338 if (levels.length > 63) 1339 throw new UnsupportedOperationException( 1340 "Too many levels to be packed by CoordPacker; should be less than 64 but was given " + 1341 levels.length); 1342 double[][] unpacked = new double[width][height]; 1343 short x, y; 1344 for(int l = 0; l < packed.length; l++) { 1345 boolean on = false; 1346 int idx = 0; 1347 for (int p = 0; p < packed[l].length; p++, on = !on) { 1348 if (on) { 1349 for (int toSkip = idx + (packed[l][p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1350 x = hilbertX[idx]; 1351 y = hilbertY[idx]; 1352 if(x >= width || y >= height) 1353 continue; 1354 unpacked[x][y] = levels[l]; 1355 } 1356 } else { 1357 idx += packed[l][p] & 0xffff; 1358 } 1359 } 1360 } 1361 return unpacked; 1362 } 1363 1364 /** 1365 * Decompresses a short[][] returned by packMulti() and produces an approximation of the double[][] it compressed 1366 * using the given levels double[] as the values to assign, but only using the innermost indices up to limit, as 1367 * described in the {@link CoordPacker} class documentation. The length of levels and the length of the outer array 1368 * of packed do not have to be equal. However, the levels array passed to this method should not be identical to the 1369 * levels array passed to packMulti(); for FOV compression, you should get an array for levels using 1370 * generatePackingLevels(), but for decompression, you should create levels using generateLightLevels(), which 1371 * should more appropriately fit the desired output. Reusing the levels array used to pack the FOV will usually 1372 * produce values at the edge of FOV that are less than 0.01 but greater than 0, and will have a maximum value 1373 * somewhat less than 1.0; neither are usually desirable, but using a different array made with 1374 * generateLightLevels() will produce doubles ranging from 1.0 / levels.length to 1.0 at the highest. Width and 1375 * height do not technically need to match the dimensions of the original 2D array, but under most circumstances 1376 * where they don't match, the data produced will be junk. 1377 * @param packed a short[][] encoded by calling this class' packMulti() method on a 2D array. 1378 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1379 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1380 * @param levels a double[] that must have the same length as packed, and will be used to assign cells in the 1381 * returned double[][] based on what levels parameter was used to compress packed 1382 * @param limit the number of elements to consider from levels and packed, starting from the innermost. 1383 * @return a double[][] where the values that corresponded to the nth value in the levels parameter used to 1384 * compress packed will now correspond to the nth value in the levels parameter passed to this method. 1385 */ 1386 public static double[][] unpackMultiDoublePartial(short[][] packed, int width, int height, double[] levels, 1387 int limit) 1388 { 1389 if(packed == null || packed.length == 0) 1390 throw new ArrayIndexOutOfBoundsException( 1391 "CoordPacker.unpackMultiDouble() must be given a non-empty array"); 1392 if (levels == null || levels.length != packed.length) 1393 throw new UnsupportedOperationException("The lengths of packed and levels must be equal"); 1394 if (levels.length > 63) 1395 throw new UnsupportedOperationException( 1396 "Too many levels to be packed by CoordPacker; should be less than 64 but was given " + 1397 levels.length); 1398 if(limit > levels.length) 1399 limit = levels.length; 1400 double[][] unpacked = new double[width][height]; 1401 short x, y; 1402 for(int l = packed.length - limit; l < packed.length; l++) { 1403 boolean on = false; 1404 int idx = 0; 1405 for (int p = 0; p < packed[l].length; p++, on = !on) { 1406 if (on) { 1407 for (int toSkip = idx + (packed[l][p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1408 x = hilbertX[idx]; 1409 y = hilbertY[idx]; 1410 if(x >= width || y >= height) 1411 continue; 1412 unpacked[x][y] = levels[l]; 1413 } 1414 } else { 1415 idx += packed[l][p] & 0xffff; 1416 } 1417 } 1418 } 1419 return unpacked; 1420 } 1421 1422 /** 1423 * Decompresses a short[][] returned by packMulti() and produces an approximation of the double[][] it compressed 1424 * using the given levels double[] as the values to assign, but only using the innermost indices up to limit, as 1425 * described in the {@link CoordPacker} class documentation. The length of levels and the length of the outer array 1426 * of packed do not have to be equal. However, the levels array passed to this method should not be identical to the 1427 * levels array passed to packMulti(); for FOV compression, you should get an array for levels using 1428 * generatePackingLevels(), but for decompression, you should create levels using generateLightLevels(), which 1429 * should more appropriately fit the desired output. Reusing the levels array used to pack the FOV will usually 1430 * produce values at the edge of FOV that are less than 0.01 but greater than 0, and will have a maximum value 1431 * somewhat less than 1.0; neither are usually desirable, but using a different array made with 1432 * generateLightLevels() will produce doubles ranging from 1.0 / levels.length to 1.0 at the highest. This method 1433 * takes an angle and span as well as a centerX and centerY; the only values that will be greater than 0.0 in the 1434 * result will be within the round-based conical section that could be produced by traveling from (centerX,centerY) 1435 * along angle in a limitless line and expanding the cone to be span degrees broad (circularly), centered on angle. 1436 * Width and height do not technically need to match the dimensions of the original 2D array, but under most 1437 * circumstances where they don't match, the data produced will be junk. 1438 * @param packed a short[][] encoded by calling this class' packMulti() method on a 2D array. 1439 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1440 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1441 * @param levels a double[] that must have the same length as packed, and will be used to assign cells in the 1442 * returned double[][] based on what levels parameter was used to compress packed 1443 * @param limit the number of elements to consider from levels and packed, starting from the innermost. 1444 * @param centerX the x position of the corner or origin of the conical FOV 1445 * @param centerY the y position of the corner or origin of the conical FOV 1446 * @param angle the center of the conical area to limit this to, in degrees 1447 * @param span the total span of the conical area to limit this to, in degrees 1448 * @return a double[][] where the values that corresponded to the nth value in the levels parameter used to 1449 * compress packed will now correspond to the nth value in the levels parameter passed to this method. 1450 */ 1451 public static double[][] unpackMultiDoublePartialConical(short[][] packed, int width, int height, double[] levels, 1452 int limit, int centerX, int centerY, double angle, double span) 1453 { 1454 if(packed == null || packed.length == 0) 1455 throw new ArrayIndexOutOfBoundsException( 1456 "CoordPacker.unpackMultiDouble() must be given a non-empty array"); 1457 if (levels == null || levels.length != packed.length) 1458 throw new UnsupportedOperationException("The lengths of packed and levels must be equal"); 1459 if (levels.length > 63) 1460 throw new UnsupportedOperationException( 1461 "Too many levels to be packed by CoordPacker; should be less than 64 but was given " + 1462 levels.length); 1463 if(limit > levels.length) 1464 limit = levels.length; 1465 1466 double angle2 = Math.toRadians((angle > 360.0 || angle < 0.0) ? MathExtras.remainder(angle, 360.0) : angle); 1467 double span2 = Math.toRadians(span); 1468 double[][] unpacked = new double[width][height]; 1469 short x, y; 1470 for(int l = packed.length - limit; l < packed.length; l++) { 1471 boolean on = false; 1472 int idx = 0; 1473 for (int p = 0; p < packed[l].length; p++, on = !on) { 1474 if (on) { 1475 for (int toSkip = idx + (packed[l][p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1476 x = hilbertX[idx]; 1477 y = hilbertY[idx]; 1478 if(x >= width || y >= height) 1479 continue; 1480 double newAngle = NumberTools.atan2(y - centerY, x - centerX) + Math.PI * 2; 1481 if(Math.abs(MathExtras.remainder(angle2 - newAngle, Math.PI * 2) - Math.PI) > span2 * 0.5) 1482 unpacked[x][y] = 0.0; 1483 else 1484 unpacked[x][y] = levels[l]; 1485 } 1486 } else { 1487 idx += packed[l][p] & 0xffff; 1488 } 1489 } 1490 } 1491 return unpacked; 1492 } 1493 1494 /** 1495 * Decompresses a short[][] returned by packMulti() and produces a simple 2D array where the values are bytes 1496 * corresponding to 1 + the highest index into levels (that is, the original levels parameter passed to packMulti) 1497 * matched by a cell, or 0 if the cell didn't match any levels during compression, as described in the 1498 * {@link CoordPacker} class documentation. Width and height do not technically need to match the dimensions of 1499 * the original 2D array, but under most circumstances where they don't match, the data produced will be junk. 1500 * @param packed a short[][] encoded by calling this class' packMulti() method on a 2D array. 1501 * @param width the width of the 2D array that will be returned; should match the unpacked array's width. 1502 * @param height the height of the 2D array that will be returned; should match the unpacked array's height. 1503 * @return a byte[][] where the values that corresponded to the nth value in the levels parameter used to 1504 * compress packed will now correspond to bytes with the value n+1, or 0 if they were "off" in the original array. 1505 */ 1506 public static byte[][] unpackMultiByte(short[][] packed, int width, int height) 1507 { 1508 if(packed == null || packed.length == 0) 1509 throw new ArrayIndexOutOfBoundsException( 1510 "CoordPacker.unpackMultiByte() must be given a non-empty array"); 1511 byte[][] unpacked = new byte[width][height]; 1512 byte lPlus = 1; 1513 short x, y; 1514 for(int l = 0; l < packed.length; l++, lPlus++) { 1515 boolean on = false; 1516 int idx = 0; 1517 for (int p = 0; p < packed[l].length; p++, on = !on) { 1518 if (on) { 1519 for (int toSkip = idx + (packed[l][p] & 0xffff); idx < toSkip && idx <= 0xffff; idx++) { 1520 x = hilbertX[idx]; 1521 y = hilbertY[idx]; 1522 if(x >= width || y >= height) 1523 continue; 1524 unpacked[x][y] = lPlus; 1525 } 1526 } else { 1527 idx += packed[l][p] & 0xffff; 1528 } 1529 } 1530 } 1531 return unpacked; 1532 } 1533 1534 /** 1535 * Given a piece of packed data defining a region to use from that map, a char to use for "on" cells and a char to use 1536 * for "off" cells, produces a 2D char array where all positions that are "off" in packed are filled with the char 1537 * passed as f, and the cells that are "on" are filled with the char passed as t. Finds the bounding rectangle starting 1538 * at the origin and extending to the highest x and highest y values encoded in packed, and uses that to determine the 1539 * width and height of the returned 2D array. 1540 * @param packed a packed short array, as produced by pack() 1541 * @param t the char to use for "on" positions in packed 1542 * @param f the char to use for "off" positions in packed 1543 * @return a 2D char array, with dimensions determined by the bounds of packed, where any "on" cells equal t and anything else equals f. 1544 */ 1545 public static char[][] unpackChar(short[] packed, char t, char f) 1546 { 1547 if(packed == null || packed.length <= 1) 1548 throw new UnsupportedOperationException("packed has no contents in unpackChar"); 1549 1550 Coord max = bounds(packed)[1]; 1551 int width = max.x+1, height = max.y+1; 1552 if(width <= 0 || height <= 0) 1553 throw new UnsupportedOperationException("Height and width must both be positive in unpackChar"); 1554 1555 char[][] c = new char[width][height]; 1556 1557 for (int i = 0; i < width; i++) { 1558 Arrays.fill(c[i], f); 1559 } 1560 boolean on = false; 1561 int idx = 0, x, y; 1562 for(int p = 0; p < packed.length; p++, on = !on) { 1563 if (on) { 1564 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 1565 x = hilbertX[i]; 1566 y = hilbertY[i]; 1567 if(x >= width || y >= height) 1568 continue; 1569 c[x][y] = t; 1570 } 1571 } 1572 idx += packed[p] & 0xffff; 1573 } 1574 return c; 1575 } 1576 /** 1577 * Given a piece of packed data defining a region to use from that map, a desired width and height, a char to use for 1578 * "on" cells and a char to use for "off" cells, produces a 2D char array where all positions that are "off" in packed 1579 * are filled with the char passed as f, and the cells that are "on" are filled with the char passed as t. 1580 * @param packed a packed short array, as produced by pack() 1581 * @param width the desired 2D array width 1582 * @param height the desired 2D array height 1583 * @param t the char to use for "on" positions in packed 1584 * @param f the char to use for "off" positions in packed 1585 * @return a 2D char array, width by height in dimensions, where any "on" cells equal t and anything else equals f. 1586 */ 1587 public static char[][] unpackChar(short[] packed, int width, int height, char t, char f) 1588 { 1589 if(width <= 0 || height <= 0) 1590 throw new UnsupportedOperationException("Height and width must both be positive in unpackChar"); 1591 1592 char[][] c = new char[width][height]; 1593 1594 if(packed.length <= 1) 1595 return c; 1596 for (int i = 0; i < width; i++) { 1597 Arrays.fill(c[i], f); 1598 } 1599 boolean on = false; 1600 int idx = 0, x, y; 1601 for(int p = 0; p < packed.length; p++, on = !on) { 1602 if (on) { 1603 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 1604 x = hilbertX[i]; 1605 y = hilbertY[i]; 1606 if(x >= width || y >= height) 1607 continue; 1608 c[x][y] = t; 1609 } 1610 } 1611 idx += packed[p] & 0xffff; 1612 } 1613 return c; 1614 } 1615 1616 /** 1617 * Utility method that constructs a GreasedRegion (a faster but more-memory-hungry way to encode regions) 1618 * from a short array of packed data. 1619 * @param packed a packed short array, as produced by pack() 1620 * @param width the desired GreasedRegion's width 1621 * @param height the desired GreasedRegion's height 1622 * @return a GreasedRegion that contains the same data as packed, with the specified width and height 1623 */ 1624 public static GreasedRegion unpackGreasedRegion(short[] packed, int width, int height) 1625 { 1626 if(packed == null) 1627 throw new NullPointerException("CoordPacker.unpackGreasedRegion() must be given a non-null array"); 1628 GreasedRegion unpacked = new GreasedRegion(width, height); 1629 if(packed.length == 0) 1630 return unpacked; 1631 boolean on = false; 1632 int idx = 0; 1633 short x, y; 1634 for(int p = 0; p < packed.length; p++, on = !on) { 1635 if (on) { 1636 for (int toSkip = idx +(packed[p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1637 x = hilbertX[idx]; 1638 y = hilbertY[idx]; 1639 unpacked.insert(x, y); 1640 } 1641 } else { 1642 idx += packed[p] & 0xffff; 1643 } 1644 } 1645 return unpacked; 1646 } 1647 1648 /** 1649 * Utility method that fills an existing GreasedRegion {@code target} with any "on" cells in the packed short array 1650 * {@code packed}. This method doesn't allocate unless an argument is null (then it throws a new Exception). It also 1651 * won't insert any "on" cells in packed that are outside the width and height of target. 1652 * @param packed a packed short array, as produced by pack() 1653 * @param target a GreasedRegion that will be modified in-place to include "on" cells from packed 1654 * @return target, after modifications to try to include any and all "on" cells in packed 1655 */ 1656 public static GreasedRegion unpackIntoGreasedRegion(short[] packed, GreasedRegion target) 1657 { 1658 return unpackIntoGreasedRegion(packed, target, 0, 0); 1659 } 1660 /** 1661 * Utility method that fills an existing GreasedRegion {@code target} with any "on" cells in the packed short array 1662 * {@code packed}, inserting cells from packed at an offset when they go into target. This method doesn't allocate 1663 * unless an argument is null (then it throws a new Exception). It also won't insert any "on" cells in packed that 1664 * are outside the width and height of target. 1665 * @param packed a packed short array, as produced by pack() 1666 * @param target a GreasedRegion that will be modified in-place to include "on" cells from packed 1667 * @param offsetX how much to offset x positions in packed by when they are placed into target 1668 * @param offsetY how much to offset y positions in packed by when they are placed into target 1669 * @return target, after modifications to try to include any and all "on" cells in packed 1670 */ 1671 public static GreasedRegion unpackIntoGreasedRegion(short[] packed, GreasedRegion target, int offsetX, int offsetY) 1672 { 1673 if(packed == null) 1674 throw new NullPointerException("CoordPacker.unpackIntoGreasedRegion() must be given a non-null array"); 1675 if(target == null) 1676 throw new NullPointerException("CoordPacker.unpackIntoGreasedRegion() must be given a non-null GreasedRegion"); 1677 if(packed.length == 0) 1678 return target; 1679 boolean on = false; 1680 int idx = 0; 1681 for(int p = 0; p < packed.length; p++, on = !on) { 1682 if (on) { 1683 for (int toSkip = idx +(packed[p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 1684 target.insert(hilbertX[idx] + offsetX, hilbertY[idx] + offsetY); 1685 } 1686 } else { 1687 idx += packed[p] & 0xffff; 1688 } 1689 } 1690 return target; 1691 } 1692 1693 /** 1694 * Quickly determines if an x,y position is true or false in the given packed array, without unpacking it. 1695 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 1696 * not be null (this method does not check due to very tight performance constraints). 1697 * @param x between 0 and 255, inclusive 1698 * @param y between 0 and 255, inclusive 1699 * @return true if the packed data stores true at the given x,y location, or false in any other case. 1700 */ 1701 public static boolean queryPacked(short[] packed, int x, int y) 1702 { 1703 int hilbertDistance = posToHilbert(x, y), total = 0; 1704 boolean on = false; 1705 for(int p = 0; p < packed.length; p++, on = !on) 1706 { 1707 total += packed[p] & 0xffff; 1708 if(hilbertDistance < total) 1709 return on; 1710 } 1711 return false; 1712 } 1713 /** 1714 * Quickly determines if a Hilbert Curve index corresponds to true or false in the given packed array, without 1715 * unpacking it. 1716 * <br> 1717 * Typically this method will not be needed by library-consuming code unless that code deals with Hilbert Curves in 1718 * a frequent and deeply involved manner. It does have the potential to avoid converting to and from x,y coordinates 1719 * and Hilbert Curve indices unnecessarily, which could matter for high-performance code. 1720 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 1721 * not be null (this method does not check due to very tight performance constraints). 1722 * @param hilbert a Hilbert Curve index, such as one taken directly from a packed short[] without extra processing 1723 * @return true if the packed data stores true at the given Hilbert Curve index, or false in any other case. 1724 */ 1725 public static boolean queryPackedHilbert(short[] packed, short hilbert) 1726 { 1727 int hilbertDistance = hilbert & 0xffff, total = 0; 1728 boolean on = false; 1729 for(int p = 0; p < packed.length; p++, on = !on) 1730 { 1731 total += packed[p] & 0xffff; 1732 if(hilbertDistance < total) 1733 return on; 1734 } 1735 return false; 1736 } 1737 1738 /** 1739 * Quickly determines if an x,y position is true or false in one of the given packed arrays, without unpacking them, 1740 * and returns a List of all packed arrays that contain the position. 1741 * @param x between 0 and 255, inclusive 1742 * @param y between 0 and 255, inclusive 1743 * @param packed an array or vararg of short[], such as those returned by pack() or one of the sub-arrays in what is 1744 * returned by packMulti(); null elements in packed will be skipped. 1745 * @return an OrderedSet of all packed arrays that store true at the given x,y location. 1746 */ 1747 public static OrderedSet<short[]> findManyPacked(int x, int y, short[] ... packed) 1748 { 1749 OrderedSet<short[]> packs = new OrderedSet<>(packed.length, CrossHash.shortHasher); 1750 int hilbertDistance = posToHilbert(x, y); 1751 for (int a = 0; a < packed.length; a++) { 1752 if(packed[a] == null) continue; 1753 int total = 0; 1754 boolean on = false; 1755 for (int p = 0; p < packed[a].length; p++, on = !on) { 1756 total += packed[a][p] & 0xffff; 1757 if (hilbertDistance < total) 1758 { 1759 if(on) 1760 packs.add(packed[a]); 1761 break; 1762 } 1763 } 1764 } 1765 return packs; 1766 } 1767 /** 1768 * Quickly determines if an x,y position is true or false in one of the given packed arrays, without unpacking them, 1769 * and returns a List of all packed arrays that contain the position. 1770 * @param x between 0 and 255, inclusive 1771 * @param y between 0 and 255, inclusive 1772 * @param packed a Collection of short[] (as encoded by this class); null elements in packed will be skipped. 1773 * @return an OrderedSet of all packed arrays that store true at the given x,y location. 1774 */ 1775 public static OrderedSet<short[]> findManyPacked(int x, int y, Collection<short[]> packed) 1776 { 1777 OrderedSet<short[]> packs = new OrderedSet<>(packed.size(), CrossHash.shortHasher); 1778 int hilbertDistance = posToHilbert(x, y); 1779 for (short[] current : packed) { 1780 if(current == null) continue; 1781 int total = 0; 1782 boolean on = false; 1783 for (int p = 0; p < current.length; p++, on = !on) { 1784 total += current[p] & 0xffff; 1785 if (hilbertDistance < total) 1786 { 1787 if(on) 1788 packs.add(current); 1789 break; 1790 } 1791 } 1792 } 1793 return packs; 1794 } 1795 1796 /** 1797 * Quickly determines if a region is contained in one of the given packed arrays, without unpacking them, and 1798 * returns true if the region checking has some overlap with any of the packed arrays, or false otherwise. 1799 * @param checking the packed data to check for overlap with the other regions 1800 * @param packed an array or vararg of short[], such as those returned by pack() or one of the sub-arrays in what is 1801 * returned by packMulti(); null elements in packed will be skipped 1802 * @return true if checking overlaps with any of the packed arrays, or false otherwise 1803 */ 1804 public static boolean regionsContain(short[] checking, short[] ... packed) 1805 { 1806 OrderedSet<short[]> packs = new OrderedSet<>(packed.length, CrossHash.shortHasher); 1807 for (int a = 0; a < packed.length; a++) { 1808 if(packed[a] == null) continue; 1809 if(intersects(checking, packed[a])) 1810 return true; 1811 } 1812 return false; 1813 } 1814 /** 1815 * Quickly determines if a region is contained in one of the given packed arrays, without unpacking them, and 1816 * returns true if the region checking has some overlap with any of the packed arrays, or false otherwise. 1817 * @param checking the packed data to check for overlap with the other regions 1818 * @param packed a Collection of short[], as encoded by this class; null elements in packed will be skipped 1819 * @return true if checking overlaps with any of the packed arrays, or false otherwise 1820 */ 1821 public static boolean regionsContain(short[] checking, Collection<short[]> packed) 1822 { 1823 OrderedSet<short[]> packs = new OrderedSet<>(packed.size(), CrossHash.shortHasher); 1824 for (short[] current : packed) { 1825 if(current == null) continue; 1826 if(intersects(checking, current)) 1827 return true; 1828 } 1829 return false; 1830 } 1831 /** 1832 * Quickly determines if a Hilbert Curve index corresponds to true or false in one of the given packed arrays, 1833 * without unpacking them, and returns a List of all packed arrays that contain the position. 1834 * <br> 1835 * Typically this method will not be needed by library-consuming code unless that code deals with Hilbert Curves in 1836 * a frequent and deeply involved manner. It does have the potential to avoid converting to and from x,y coordinates 1837 * and Hilbert Curve indices unnecessarily, which could matter for high-performance code. 1838 * @param hilbert a Hilbert Curve index, such as one taken directly from a packed short[] without extra processing 1839 * @param packed an array or vararg of short[], such as those returned by pack() or one of the sub-arrays in what is 1840 * returned by packMulti(); null elements in packed will be skipped. 1841 * @return an ArrayList of all packed arrays that store true at the given x,y location. 1842 */ 1843 public static ArrayList<short[]> findManyPackedHilbert(short hilbert, short[] ... packed) 1844 { 1845 ArrayList<short[]> packs = new ArrayList<>(packed.length); 1846 int hilbertDistance = hilbert & 0xffff; 1847 for (int a = 0; a < packed.length; a++) { 1848 int total = 0; 1849 boolean on = false; 1850 for (int p = 0; p < packed[a].length; p++, on = !on) { 1851 total += packed[a][p] & 0xffff; 1852 if (hilbertDistance < total) 1853 { 1854 if(on) 1855 packs.add(packed[a]); 1856 break; 1857 } 1858 } 1859 } 1860 return packs; 1861 } 1862 1863 /** 1864 * Gets all positions that are "on" in the given packed array, without unpacking it, and returns them as a Coord[]. 1865 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 1866 * not be null (this method does not check due to very tight performance constraints). 1867 * @return a Coord[], ordered by distance along the Hilbert Curve, corresponding to all "on" cells in packed. 1868 */ 1869 public static Coord[] allPacked(short[] packed) 1870 { 1871 ShortVLA vla = new ShortVLA(64); 1872 boolean on = false; 1873 int idx = 0; 1874 for(int p = 0; p < packed.length; p++, on = !on) { 1875 if (on) { 1876 vla.addRange(idx, idx + (packed[p] & 0xffff)); 1877 } 1878 idx += packed[p] & 0xffff; 1879 } 1880 int[] distances = vla.asInts(); 1881 Coord[] cs = new Coord[distances.length]; 1882 for (int i = 0; i < distances.length; i++) { 1883 cs[i] = Coord.get(hilbertX[distances[i]], hilbertY[distances[i]]); 1884 } 1885 return cs; 1886 } 1887 1888 /** 1889 * Gets all positions that are "on" in the given packed array, without unpacking it, and returns them as an array of 1890 * Hilbert Curve indices. 1891 * <br> 1892 * Typically this method will not be needed by library-consuming code unless that code deals with Hilbert Curves in 1893 * a frequent and deeply involved manner. It does have the potential to avoid converting to and from x,y coordinates 1894 * and Hilbert Curve indices unnecessarily, which could matter for high-performance code. 1895 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 1896 * not be null (this method does not check due to very tight performance constraints). 1897 * @return a Hilbert Curve index array, in ascending distance order, corresponding to all "on" cells in packed. 1898 */ 1899 public static short[] allPackedHilbert(short[] packed) 1900 { 1901 ShortVLA vla = new ShortVLA(64); 1902 boolean on = false; 1903 int idx = 0; 1904 for(int p = 0; p < packed.length; p++, on = !on) { 1905 if (on) { 1906 vla.addRange(idx, idx + (packed[p] & 0xffff)); 1907 } 1908 idx += packed[p] & 0xffff; 1909 } 1910 return vla.toArray(); 1911 } 1912 1913 /** 1914 * Gets the nth position that is "on" in the given packed array, without unpacking it, and returns it as a Coord. 1915 * Uses Hilbert Curve ordering for the exact Hilbert Curve CoordPacker uses, so any two given Coords will always 1916 * have the same before-after relationship. Returns null if n is not between 0 (inclusive) and the count of packed 1917 * (exclusive), as by {@code CoordPacker.count()}. 1918 * 1919 * You can technically use nth to iterate over only the Coords that are defined in some packed data, but it's 1920 * drastically more efficient to store a Coord array once with allPacked(). Using nth() as an iterator is 1921 * essentially running a growing portion of what allPacked() does, over and over again, until the last Coord encoded 1922 * in packed takes almost as long to process as one call to allPacked(). That said, for a single Coord this can be 1923 * significantly faster than getting an array with allPacked() and fetching only one item from it. 1924 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 1925 * not be null (this method does not check due to very tight performance constraints). 1926 * @param n the index to get in packed 1927 * @return the nth Coord encoded as "on" by packed, ordered by distance along the Hilbert Curve, or null if n is out of bounds 1928 */ 1929 public static Coord nth(final short[] packed, final int n) 1930 { 1931 if(n < 0) 1932 return null; 1933 boolean on = false; 1934 int idx = 0, ct = n, tmp; 1935 for(int p = 0; p < packed.length; p++, on = !on) { 1936 tmp = (packed[p] & 0xffff); 1937 if (on) { 1938 if(ct - tmp < 0) 1939 { 1940 idx += ct; 1941 ct -= tmp; 1942 break; 1943 } 1944 ct -= tmp; 1945 } 1946 idx += tmp; 1947 } 1948 if(ct >= 0) 1949 return null; 1950 return Coord.get(hilbertX[idx], hilbertY[idx]); 1951 } 1952 /** 1953 * Gets the positions that are "on" in the given packed array, without unpacking it, repeatedly goes through a 1954 * number of "on" cells equal to fraction and stores one of those cells as a Coord, and returns the accumulated 1955 * portion of positions as a Coord[]. 1956 * <br> 1957 * For purposes of finding mostly cells with a similar distance to each other but without obvious patterns, a value 1958 * of 5, 6, or 7 for fraction works well for relatively-close Coords, but larger values are better for packed data 1959 * with wide, expansive areas. If you want to make the regular pattern this uses impossible to discern, you can use 1960 * {@code randomSeparated()} to keep distance between Coords and sample most areas of some packed data. Values for 1961 * fraction that are multiples of 4 are likely to show a pattern in large open spaces more easily. 1962 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 1963 * not be null (this method does not check due to very tight performance constraints). 1964 * @param fraction the denominator of the approximate fraction of "on" cells to use 1965 * @return a Coord[] corresponding to a fraction of the "on" cells in packed. 1966 */ 1967 public static Coord[] fractionPacked(short[] packed, int fraction) 1968 { 1969 if(fraction <= 1) 1970 return allPacked(packed); 1971 ShortVLA vla = new ShortVLA(64); 1972 boolean on = false; 1973 int idx = 0, ctr = 0; 1974 for(int p = 0; p < packed.length; p++, on = !on) { 1975 if (on) { 1976 for (int i = idx; i < idx + (packed[p] & 0xffff); i++, ctr = (ctr + 1) % fraction) { 1977 if(ctr == 0) 1978 vla.add((short)i); 1979 } 1980 } 1981 idx += packed[p] & 0xffff; 1982 } 1983 int[] distances = vla.asInts(); 1984 Coord[] cs = new Coord[distances.length]; 1985 for (int i = 0; i < distances.length; i++) { 1986 cs[i] = Coord.get(hilbertX[distances[i]], hilbertY[distances[i]]); 1987 } 1988 return cs; 1989 } 1990 1991 /** 1992 * Gets the positions that are "on" in the given packed array, without unpacking it, repeatedly goes through a 1993 * number of "on" cells equal to fraction and stores a random one of those cells as a Coord, and returns the 1994 * accumulated random portion of positions as a Coord[]. Because of how this works, it is much more likely that the 1995 * Coords will be dispersed so that there's a good amount of minimum distance between most Coords, while methods 1996 * like randomPortion() do not make such dispersal a priority and may return tight clusters of Coords. 1997 * <br> 1998 * For purposes of finding mostly cells with a similar distance to each other but without obvious patterns, a value 1999 * of at least 7 for fraction works well. 2000 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 2001 * not be null (this method does not check due to very tight performance constraints). 2002 * @param separation the denominator of the approximate fraction of "on" cells to use 2003 * @param rng the {@link IRNG}, such as an {@link RNG} or {@link GWTRNG}, to use to randomize retrieval 2004 * @return a Coord[] corresponding to a fraction of the "on" cells in packed. 2005 */ 2006 public static Coord[] randomSeparated(short[] packed, int separation, IRNG rng) 2007 { 2008 if(separation <= 1) 2009 return allPacked(packed); 2010 ShortVLA vla = new ShortVLA(64); 2011 boolean on = false; 2012 int idx = 0, ctr = 0, tgt = rng.nextInt(separation); 2013 for(int p = 0; p < packed.length; p++, on = !on) { 2014 if (on) { 2015 for (int i = idx; i < idx + (packed[p] & 0xffff); i++, ctr++) { 2016 if(ctr >= separation) 2017 { 2018 ctr %= separation; 2019 tgt = rng.nextInt(separation); 2020 } 2021 if(ctr == tgt) 2022 vla.add((short)i); 2023 } 2024 } 2025 idx += packed[p] & 0xffff; 2026 } 2027 int[] distances = vla.asInts(); 2028 Coord[] cs = new Coord[distances.length]; 2029 for (int i = 0; i < distances.length; i++) { 2030 cs[i] = Coord.get(hilbertX[distances[i]], hilbertY[distances[i]]); 2031 } 2032 return cs; 2033 } 2034 2035 /** 2036 * Gets the positions that are "on" in the given packed array, without unpacking it, repeatedly goes through a 2037 * number of "on" cells equal to fraction and stores one of those cells as a Coord, and returns the accumulated 2038 * portion of positions as an array of Hilbert Curve indices. 2039 * <br> 2040 * For purposes of finding mostly cells with a similar distance to each other but without obvious patterns, a value 2041 * of 5, 6, or 7 for fraction works well. 2042 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 2043 * not be null (this method does not check due to very tight performance constraints). 2044 * @param fraction the approximate fraction of "on" cells to use 2045 * @return a Hilbert Curve index array corresponding to a fraction of the "on" cells in packed. 2046 */ 2047 public static short[] fractionPackedHilbert(short[] packed, int fraction) 2048 { 2049 if(fraction <= 1) 2050 return allPackedHilbert(packed); 2051 ShortVLA vla = new ShortVLA(64); 2052 boolean on = false; 2053 int idx = 0, ctr = 0; 2054 for(int p = 0; p < packed.length; p++, on = !on) { 2055 if (on) { 2056 for (int i = idx; i < idx + (packed[p] & 0xffff); i++, ctr = (ctr + 1) % fraction) { 2057 if(ctr == 0) 2058 vla.add((short)i); 2059 } 2060 } 2061 idx += packed[p] & 0xffff; 2062 } 2063 return vla.toArray(); 2064 } 2065 2066 /** 2067 * Gets the positions that are "on" in the given packed array, without unpacking it, keeps only positions that are 2068 * at least minDistance apart from other positions this will return, and returns the positions as a Coord[]. 2069 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 2070 * not be null (this method does not check due to very tight performance constraints). 2071 * @param minDistance the minimum distance (measured 8-way, Chebyshev) between any positions this returns 2072 * @return a Coord[] corresponding to a portion of the "on" cells in packed. 2073 */ 2074 public static Coord[] apartPacked(short[] packed, int minDistance) 2075 { 2076 if(minDistance < 1) 2077 return allPacked(packed); 2078 ShortVLA vla = new ShortVLA(64); 2079 boolean on = false; 2080 int idx = 0; 2081 IntSet ss = new IntSet(256); 2082 for(int p = 0; p < packed.length; p++, on = !on) { 2083 if (on) { 2084 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2085 int x = hilbertX[i], y = hilbertY[i], dist = hilbertDistances[x + (y << 8)]; 2086 if (ss.add(dist)) { 2087 for (int xx = Math.max(0, x - minDistance); xx <= Math.min(255, x + minDistance); xx++) { 2088 for (int yy = Math.max(0, y - minDistance); yy <= Math.min(255, y + minDistance); yy++) { 2089 dist = hilbertDistances[xx + (yy << 8)]; 2090 if(dist >= i) 2091 ss.add(dist); 2092 } 2093 } 2094 vla.add((short) i); 2095 } 2096 } 2097 } 2098 idx += packed[p] & 0xffff; 2099 } 2100 int[] distances = vla.asInts(); 2101 Coord[] cs = new Coord[distances.length]; 2102 for (int i = 0; i < distances.length; i++) { 2103 cs[i] = Coord.get(hilbertX[distances[i]], hilbertY[distances[i]]); 2104 } 2105 return cs; 2106 } 2107 /** 2108 * Gets the positions that are "on" in the given packed array, without unpacking it, keeps only positions that are 2109 * at least minDistance apart from other positions this will return, and returns the positions as a Coord[]. 2110 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 2111 * not be null (this method does not check due to very tight performance constraints). 2112 * @param minDistance the minimum distance (measurement depends on eightWay) between any positions this returns 2113 * @param eightWay true if distance should be measured equally in 8 directions, false to use 4 directions 2114 * @return a Coord[] corresponding to a portion of the "on" cells in packed. 2115 */ 2116 public static Coord[] apartPacked(short[] packed, int minDistance, boolean eightWay) 2117 { 2118 if(minDistance < 1) 2119 return allPacked(packed); 2120 if(eightWay) 2121 return apartPacked(packed, minDistance); 2122 2123 ShortVLA vla = new ShortVLA(64); 2124 boolean on = false; 2125 int idx = 0; 2126 IntSet ss = new IntSet(256); 2127 int xx, yy; 2128 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2129 for(int p = 0; p < packed.length; p++, on = !on) { 2130 if (on) { 2131 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2132 int x = hilbertX[i], y = hilbertY[i], dist = hilbertDistances[x + (y << 8)]; 2133 if (ss.add(dist)) { 2134 for (int d = 0; d < 4; d++) { 2135 for (int e = 1; e <= minDistance; e++) { 2136 for (int e2 = 0; e2 < minDistance; e2++) { 2137 xx = Math.min(255, Math.max(0, x + xOffsets[d] * e + yOffsets[d + 1] * e2)); 2138 yy = Math.min(255, Math.max(0, y + yOffsets[d] * e + xOffsets[d + 1] * e2)); 2139 dist = hilbertDistances[xx + (yy << 8)]; 2140 if (dist >= i) 2141 ss.add(dist); 2142 } 2143 } 2144 } 2145 vla.add((short) i); 2146 } 2147 } 2148 } 2149 idx += packed[p] & 0xffff; 2150 } 2151 int[] distances = vla.asInts(); 2152 Coord[] cs = new Coord[distances.length]; 2153 for (int i = 0; i < distances.length; i++) { 2154 cs[i] = Coord.get(hilbertX[distances[i]], hilbertY[distances[i]]); 2155 } 2156 return cs; 2157 } 2158 2159 /** 2160 * Gets the positions that are "on" in the given packed array, without unpacking it, keeps only positions that are 2161 * at least minDistance apart from other positions this will return, and returns the positions as an array of 2162 * Hilbert Curve indices. 2163 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 2164 * not be null (this method does not check due to very tight performance constraints). 2165 * @param minDistance the minimum distance (measured 8-way, Chebyshev) between any positions this returns 2166 * @return a Hilbert Curve index array corresponding to a portion of the "on" cells in packed. 2167 */ 2168 public static short[] apartPackedHilbert(short[] packed, int minDistance) 2169 { 2170 if(minDistance < 1) 2171 return allPackedHilbert(packed); 2172 ShortVLA vla = new ShortVLA(64); 2173 boolean on = false; 2174 int idx = 0; 2175 IntSet ss = new IntSet(256); 2176 for(int p = 0; p < packed.length; p++, on = !on) { 2177 if (on) { 2178 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2179 int x = hilbertX[i], y = hilbertY[i], dist = hilbertDistances[x + (y << 8)]; 2180 if (ss.add(dist)) { 2181 for (int xx = Math.max(0, x - minDistance); xx <= Math.min(255, x + minDistance); xx++) { 2182 for (int yy = Math.max(0, y - minDistance); yy <= Math.min(255, y + minDistance); yy++) { 2183 dist = hilbertDistances[xx + (yy << 8)]; 2184 if(dist >= i) 2185 ss.add(dist); 2186 } 2187 } 2188 vla.add((short) i); 2189 } 2190 } 2191 } 2192 idx += packed[p] & 0xffff; 2193 } 2194 return vla.toArray(); 2195 } 2196 2197 /** 2198 * Gets the positions that are "on" in the given packed array, without unpacking it, keeps only positions that are 2199 * at least minDistance apart from other positions this will return, and returns the positions as an array of 2200 * Hilbert Curve indices. 2201 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 2202 * not be null (this method does not check due to very tight performance constraints). 2203 * @param minDistance the minimum distance (measurement depends on eightWay) between any positions this returns 2204 * @param eightWay true if distance should be measured equally in 8 directions, false to use 4 directions 2205 * @return a Hilbert Curve index array corresponding to a portion of the "on" cells in packed. 2206 */ 2207 public static short[] apartPackedHilbert(short[] packed, int minDistance, boolean eightWay) 2208 { 2209 if(minDistance < 1) 2210 return allPackedHilbert(packed); 2211 if(eightWay) 2212 return apartPackedHilbert(packed, minDistance); 2213 2214 ShortVLA vla = new ShortVLA(64); 2215 boolean on = false; 2216 int idx = 0; 2217 IntSet ss = new IntSet(256); 2218 int xx, yy; 2219 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2220 for(int p = 0; p < packed.length; p++, on = !on) { 2221 if (on) { 2222 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2223 int x = hilbertX[i], y = hilbertY[i], dist = hilbertDistances[x + (y << 8)]; 2224 if (ss.add(dist)) { 2225 for (int d = 0; d < 4; d++) { 2226 for (int e = 1; e <= minDistance; e++) { 2227 for (int e2 = 0; e2 < minDistance; e2++) { 2228 xx = Math.min(255, Math.max(0, x + xOffsets[d] * e + yOffsets[d + 1] * e2)); 2229 yy = Math.min(255, Math.max(0, y + yOffsets[d] * e + xOffsets[d + 1] * e2)); 2230 dist = hilbertDistances[xx + (yy << 8)]; 2231 if (dist >= i) 2232 ss.add(dist); 2233 } 2234 } 2235 } 2236 vla.add((short) i); 2237 } 2238 } 2239 } 2240 idx += packed[p] & 0xffff; 2241 } 2242 return vla.toArray(); 2243 } 2244 private static int clamp(int n, int min, int max) 2245 { 2246 return Math.min(Math.max(min, n), max - 1); 2247 } 2248 2249 /** 2250 * Move all "on" positions in packed by the number of cells given in xMove and yMove, unless the move 2251 * would take them further than 0, width - 1 (for xMove) or height - 1 (for yMove), in which case that 2252 * cell is stopped at the edge (moving any shape by an xMove greater than width or yMove greater than 2253 * height will move all "on" cells to that edge, in a 1-cell thick line). Returns a new packed short[] 2254 * and does not modify packed. 2255 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2256 * @param xMove distance to move the x-coordinate; can be positive or negative 2257 * @param yMove distance to move the y-coordinate; can be positive or negative 2258 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2259 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2260 * @return a packed array that encodes "on" for cells that were moved from cells that were "on" in packed 2261 */ 2262 public static short[] translate(short[] packed, int xMove, int yMove, int width, int height) 2263 { 2264 if(packed == null || packed.length <= 1) 2265 { 2266 return ALL_WALL; 2267 } 2268 ShortVLA vla = new ShortVLA(256); 2269 boolean on = false; 2270 int idx = 0, x, y; 2271 for(int p = 0; p < packed.length; p++, on = !on) { 2272 if (on) { 2273 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2274 x = clamp(hilbertX[i] + xMove, 0, width); 2275 y = clamp(hilbertY[i] + yMove, 0, height); 2276 vla.add(hilbertDistances[x + (y << 8)]); 2277 } 2278 } 2279 idx += packed[p] & 0xffff; 2280 } 2281 if(vla.size < 1) 2282 return ALL_WALL; 2283 int[] indices = vla.asInts(); 2284 Arrays.sort(indices); 2285 vla.clear(); 2286 int current, past = indices[0], skip = 0; 2287 2288 vla.add((short)indices[0]); 2289 for (int i = 1; i < indices.length; i++) { 2290 current = indices[i]; 2291 if (current - past > 1) 2292 { 2293 vla.add((short) (skip+1)); 2294 skip = 0; 2295 vla.add((short)(current - past - 1)); 2296 } 2297 else if(current != past) 2298 skip++; 2299 past = current; 2300 } 2301 vla.add((short)(skip+1)); 2302 2303 return vla.toArray(); 2304 } 2305 2306 /** 2307 * Expand each "on" position in packed to cover a a square with side length equal to 1 + expansion * 2, 2308 * centered on the original "on" position, unless the expansion would take a cell further than 0, 2309 * width - 1 (for xMove) or height - 1 (for yMove), in which case that cell is stopped at the edge. 2310 * Uses 8-way movement (Chebyshev distance) unless the overload of this function that takes a boolean argument 2311 * eightWay is used and that argument is false. 2312 * Returns a new packed short[] and does not modify packed. 2313 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2314 * @param expansion the positive (square) radius, in cells, to expand each cell out by 2315 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2316 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2317 * @return a packed array that encodes "on" for packed and cells that expanded from cells that were "on" in packed 2318 */ 2319 public static short[] expand(short[] packed, int expansion, int width, int height) 2320 { 2321 if(packed == null || packed.length <= 1) 2322 { 2323 return ALL_WALL; 2324 } 2325 ShortVLA vla = new ShortVLA(256); 2326 IntSet ss = new IntSet(256); 2327 boolean on = false; 2328 int idx = 0, x, y; 2329 short dist; 2330 for(int p = 0; p < packed.length; p++, on = !on) { 2331 if (on) { 2332 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2333 x = hilbertX[i]; 2334 y = hilbertY[i]; 2335 for (int j = Math.max(0, x - expansion); j <= Math.min(width - 1, x + expansion); j++) { 2336 for (int k = Math.max(0, y - expansion); k <= Math.min(height - 1, y + expansion); k++) { 2337 dist = hilbertDistances[j + (k << 8)]; 2338 if (ss.add(dist)) 2339 vla.add(dist); 2340 } 2341 } 2342 } 2343 } 2344 idx += packed[p] & 0xffff; 2345 } 2346 2347 int[] indices = vla.asInts(); 2348 if(indices.length < 1) 2349 return ALL_WALL; 2350 Arrays.sort(indices); 2351 2352 vla.clear(); 2353 int current, past = indices[0], skip = 0; 2354 2355 vla.add((short)indices[0]); 2356 for (int i = 1; i < indices.length; i++) { 2357 current = indices[i]; 2358 if (current - past > 1) 2359 { 2360 vla.add((short) (skip+1)); 2361 skip = 0; 2362 vla.add((short)(current - past - 1)); 2363 } 2364 else if(current != past) 2365 skip++; 2366 past = current; 2367 } 2368 vla.add((short)(skip+1)); 2369 return vla.toArray(); 2370 } 2371 2372 2373 /** 2374 * Expand each "on" position in packed to cover a a square with side length equal to 1 + expansion * 2, 2375 * centered on the original "on" position, unless the expansion would take a cell further than 0, 2376 * width - 1 (for xMove) or height - 1 (for yMove), in which case that cell is stopped at the edge. 2377 * Returns a new packed short[] and does not modify packed. 2378 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2379 * @param expansion the positive (square) radius, in cells, to expand each cell out by 2380 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2381 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2382 * @param eightWay true if the expansion should be both diagonal and orthogonal; false for just orthogonal 2383 * @return a packed array that encodes "on" for packed and cells that expanded from cells that were "on" in packed 2384 */ 2385 public static short[] expand(short[] packed, int expansion, int width, int height, boolean eightWay) 2386 { 2387 if(eightWay) 2388 return expand(packed, expansion, width, height); 2389 if(packed == null || packed.length <= 1) 2390 { 2391 return ALL_WALL; 2392 } 2393 ShortVLA vla = new ShortVLA(256); 2394 IntSet ss = new IntSet(256); 2395 boolean on = false; 2396 int idx = 0, x, y, j, k; 2397 short dist; 2398 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2399 for(int p = 0; p < packed.length; p++, on = !on) { 2400 if (on) { 2401 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2402 x = hilbertX[i]; 2403 y = hilbertY[i]; 2404 dist = hilbertDistances[x + (y << 8)]; 2405 if (ss.add(dist)) 2406 vla.add(dist); 2407 for (int d = 0; d < 4; d++) { 2408 for (int e = 1; e <= expansion; e++) { 2409 for (int e2 = 0; e2 <= expansion - e; e2++) { 2410 j = Math.min(width - 1, Math.max(0, x + xOffsets[d] * e + yOffsets[d + 1] * e2)); 2411 k = Math.min(height - 1, Math.max(0, y + yOffsets[d] * e + xOffsets[d + 1] * e2)); 2412 dist = hilbertDistances[j + (k << 8)]; 2413 if (ss.add(dist)) 2414 vla.add(dist); 2415 } 2416 } 2417 } 2418 } 2419 } 2420 idx += packed[p] & 0xffff; 2421 } 2422 2423 int[] indices = vla.asInts(); 2424 if(indices.length < 1) 2425 return ALL_WALL; 2426 Arrays.sort(indices); 2427 2428 vla.clear(); 2429 int current, past = indices[0], skip = 0; 2430 2431 vla.add((short)indices[0]); 2432 for (int i = 1; i < indices.length; i++) { 2433 current = indices[i]; 2434 if (current - past > 1) 2435 { 2436 vla.add((short) (skip+1)); 2437 skip = 0; 2438 vla.add((short)(current - past - 1)); 2439 } 2440 else if(current != past) 2441 skip++; 2442 past = current; 2443 } 2444 vla.add((short)(skip+1)); 2445 2446 return vla.toArray(); 2447 } 2448 2449 /** 2450 * Finds the area made by removing the "on" positions in packed that are within the specified retraction distance of 2451 * an "off" position or the edge of the map. This essentially finds a shrunken version of packed. 2452 * Uses 8-way movement (Chebyshev distance) unless the overload of this function that takes a boolean argument 2453 * eightWay is used and that argument is false. 2454 * Returns a new packed short[] and does not modify packed. 2455 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2456 * @param retraction the positive (square) radius, in cells, to pull each cell in by 2457 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2458 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2459 * @return a short[] that encodes "on" for cells that were "on" in packed and were far enough from an "off" cell 2460 */ 2461 public static short[] retract(short[] packed, int retraction, int width, int height) 2462 { 2463 return differencePacked(packed, expand(negatePacked(packed), retraction, width, height, true)); 2464 } 2465/* public static short[] retract(short[] packed, int retraction, int width, int height) 2466 { 2467 if(packed == null || packed.length <= 1) 2468 { 2469 return ALL_WALL; 2470 } 2471 ShortVLA vla = new ShortVLA(256); 2472 boolean on = false; 2473 int idx = 0, x, y; 2474 for(int p = 0; p < packed.length; p++, on = !on) { 2475 if (on) { 2476 INDICES: 2477 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) 2478 { 2479 x = hilbertX[i]; 2480 y = hilbertY[i]; 2481 for (int j = x - retraction; j <= x + retraction; j++) { 2482 for (int k = y - retraction; k <= y + retraction; k++) { 2483 if(j < 0 || k < 0 || j >= width || k >= height || 2484 !queryPackedHilbert(packed, hilbertDistances[j + (k << 8)])) 2485 continue INDICES; 2486 } 2487 } 2488 2489 vla.add((short)i); 2490 } 2491 } 2492 idx += packed[p] & 0xffff; 2493 } 2494 2495 int[] indices = vla.asInts(); 2496 if(indices.length < 1) 2497 return ALL_WALL; 2498 Arrays.sort(indices); 2499 2500 vla.clear(); 2501 int current, past = indices[0], skip = 0; 2502 2503 vla.add((short)indices[0]); 2504 for (int i = 1; i < indices.length; i++) { 2505 current = indices[i]; 2506 if (current - past > 1) 2507 { 2508 vla.add((short) (skip+1)); 2509 skip = 0; 2510 vla.add((short)(current - past - 1)); 2511 } 2512 else if(current != past) 2513 skip++; 2514 past = current; 2515 } 2516 vla.add((short)(skip+1)); 2517 return vla.toArray(); 2518 } 2519 */ 2520 /** 2521 * Finds the area made by removing the "on" positions in packed that are within the specified retraction distance of 2522 * an "off" position or the edge of the map. This essentially finds a shrunken version of packed. 2523 * Returns a new packed short[] and does not modify packed. 2524 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2525 * @param retraction the positive (square) radius, in cells, to pull each cell in by 2526 * @param width the maximum width; cells outside this are considered "off" for this method's purposes 2527 * @param height the maximum height; cells outside this are considered "off" for this method's purposes 2528 * @param eightWay true if the retraction should be both diagonal and orthogonal; false for just orthogonal 2529 * @return a packed array that encodes "on" for packed and cells that expanded from cells that were "on" in packed 2530 */ 2531 public static short[] retract(short[] packed, int retraction, int width, int height, boolean eightWay) 2532 { 2533 return differencePacked(packed, expand(negatePacked(packed), retraction, width, height, eightWay)); 2534 } 2535 /* 2536 { 2537 if(eightWay) 2538 return retract(packed, retraction, width, height); 2539 if(packed == null || packed.length <= 1) 2540 { 2541 return ALL_WALL; 2542 } 2543 ShortVLA vla = new ShortVLA(256); 2544 boolean on = false; 2545 int idx = 0, x, y, j, k; 2546 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2547 for(int p = 0; p < packed.length; p++, on = !on) { 2548 if (on) { 2549 INDICES: 2550 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) 2551 { 2552 x = hilbertX[i]; 2553 y = hilbertY[i]; 2554 for (int d = 0; d < 4; d++) { 2555 for (int e = 1; e <= retraction; e++) { 2556 for (int e2 = 0; e2 < retraction; e2++) { 2557 j = x + xOffsets[d] * e + yOffsets[d + 1] * e2; 2558 k = y + yOffsets[d] * e + xOffsets[d + 1] * e2; 2559 if (j < 0 || k < 0 || j >= width || k >= height || 2560 !queryPackedHilbert(packed, hilbertDistances[j + (k << 8)])) 2561 continue INDICES; 2562 } 2563 } 2564 } 2565 vla.add((short)i); 2566 } 2567 } 2568 idx += packed[p] & 0xffff; 2569 } 2570 2571 int[] indices = vla.asInts(); 2572 if(indices.length < 1) 2573 return ALL_WALL; 2574 Arrays.sort(indices); 2575 2576 vla.clear(); 2577 int current, past = indices[0], skip = 0; 2578 2579 vla.add((short)indices[0]); 2580 for (int i = 1; i < indices.length; i++) { 2581 current = indices[i]; 2582 if (current - past > 1) 2583 { 2584 vla.add((short) (skip+1)); 2585 skip = 0; 2586 vla.add((short)(current - past - 1)); 2587 } 2588 else if(current != past) 2589 skip++; 2590 past = current; 2591 } 2592 vla.add((short)(skip+1)); 2593 return vla.toArray(); 2594 } 2595 */ 2596 2597 2598 2599 /** 2600 * Finds the area around the cells encoded in packed, without including those cells. For each "on" 2601 * position in packed, expand it to cover a a square with side length equal to 1 + expansion * 2, 2602 * centered on the original "on" position, unless the expansion would take a cell further than 0, 2603 * width - 1 (for xMove) or height - 1 (for yMove), in which case that cell is stopped at the edge. 2604 * If a cell is "on" in packed, it will always be "off" in the result. 2605 * Uses 8-way movement (Chebyshev distance) unless the overload of this function that takes a boolean argument 2606 * eightWay is used and that argument is false. 2607 * Returns a new packed short[] and does not modify packed. 2608 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2609 * @param expansion the positive (square-shaped) radius, in cells, to expand each cell out by 2610 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2611 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2612 * @return a packed array that encodes "on" for cells that were pushed from the edge of packed's "on" cells 2613 */ 2614 public static short[] fringe(short[] packed, int expansion, int width, int height) 2615 { 2616 if(packed == null || packed.length <= 1) 2617 { 2618 return ALL_WALL; 2619 } 2620 ShortVLA vla = new ShortVLA(256); 2621 IntSet ss = new IntSet(256); 2622 boolean on = false; 2623 int idx = 0; 2624 short x, y, dist; 2625 for(int p = 0; p < packed.length; p++, on = !on) { 2626 if (on) { 2627 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2628 ss.add(i); 2629 } 2630 } 2631 idx += packed[p] & 0xffff; 2632 } 2633 on = false; 2634 idx = 0; 2635 for(int p = 0; p < packed.length; p++, on = !on) { 2636 if (on) { 2637 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2638 x = hilbertX[i]; 2639 y = hilbertY[i]; 2640 for (int j = Math.max(0, x - expansion); j <= Math.min(width - 1, x + expansion); j++) { 2641 for (int k = Math.max(0, y - expansion); k <= Math.min(height - 1, y + expansion); k++) { 2642 dist = hilbertDistances[j + (k << 8)]; 2643 if (ss.add(dist)) 2644 vla.add(dist); 2645 } 2646 } 2647 } 2648 } 2649 idx += packed[p] & 0xffff; 2650 } 2651 int[] indices = vla.asInts(); 2652 if(indices.length < 1) 2653 return ALL_WALL; 2654 Arrays.sort(indices); 2655 2656 vla.clear(); 2657 int current, past = indices[0], skip = 0; 2658 2659 vla.add((short)indices[0]); 2660 for (int i = 1; i < indices.length; i++) { 2661 current = indices[i]; 2662 if (current - past > 1) 2663 { 2664 vla.add((short) (skip+1)); 2665 skip = 0; 2666 vla.add((short)(current - past - 1)); 2667 } 2668 else if(current != past) 2669 skip++; 2670 past = current; 2671 } 2672 vla.add((short)(skip+1)); 2673 2674 return vla.toArray(); 2675 } 2676 2677 /** 2678 * Finds the area around the cells encoded in packed, without including those cells. For each "on" 2679 * position in packed, expand it to cover a a square with side length equal to 1 + expansion * 2, 2680 * centered on the original "on" position, unless the expansion would take a cell further than 0, 2681 * width - 1 (for xMove) or height - 1 (for yMove), in which case that cell is stopped at the edge. 2682 * If a cell is "on" in packed, it will always be "off" in the result. 2683 * Returns a new packed short[] and does not modify packed. 2684 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2685 * @param expansion the positive (square-shaped) radius, in cells, to expand each cell out by 2686 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2687 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2688 * @param eightWay true if the expansion should be both diagonal and orthogonal; false for just orthogonal 2689 * @return a packed array that encodes "on" for cells that were pushed from the edge of packed's "on" cells 2690 */ 2691 public static short[] fringe(short[] packed, int expansion, int width, int height, boolean eightWay) 2692 { 2693 if(eightWay) 2694 return fringe(packed, expansion, width, height); 2695 if(packed == null || packed.length <= 1) 2696 { 2697 return ALL_WALL; 2698 } 2699 ShortVLA vla = new ShortVLA(256); 2700 IntSet ss = new IntSet(256); 2701 boolean on = false; 2702 int idx = 0; 2703 short x, y, dist; 2704 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2705 for(int p = 0; p < packed.length; p++, on = !on) { 2706 if (on) { 2707 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2708 ss.add(i); 2709 } 2710 } 2711 idx += packed[p] & 0xffff; 2712 } 2713 on = false; 2714 idx = 0; 2715 for(int p = 0; p < packed.length; p++, on = !on) { 2716 if (on) { 2717 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2718 x = hilbertX[i]; 2719 y = hilbertY[i]; 2720 for (int d = 0; d < 4; d++) { 2721 for (int e = 1; e <= expansion; e++) { 2722 for (int e2 = 0; e2 <= expansion - e; e2++) { 2723 int j = Math.min(width - 1, Math.max(0, x + xOffsets[d] * e + yOffsets[d + 1] * e2)); 2724 int k = Math.min(height - 1, Math.max(0, y + yOffsets[d] * e + xOffsets[d + 1] * e2)); 2725 dist = hilbertDistances[j + (k << 8)]; 2726 if (ss.add(dist)) 2727 vla.add(dist); 2728 } 2729 } 2730 } 2731 2732 } 2733 } 2734 idx += packed[p] & 0xffff; 2735 } 2736 int[] indices = vla.asInts(); 2737 if(indices.length < 1) 2738 return ALL_WALL; 2739 Arrays.sort(indices); 2740 2741 vla.clear(); 2742 int current, past = indices[0], skip = 0; 2743 2744 vla.add((short)indices[0]); 2745 for (int i = 1; i < indices.length; i++) { 2746 current = indices[i]; 2747 if (current - past > 1) 2748 { 2749 vla.add((short) (skip+1)); 2750 skip = 0; 2751 vla.add((short)(current - past - 1)); 2752 } 2753 else if(current != past) 2754 skip++; 2755 past = current; 2756 } 2757 vla.add((short)(skip+1)); 2758 2759 return vla.toArray(); 2760 } 2761 /** 2762 * Finds the area around the cells encoded in packed, without including those cells. For each "on" 2763 * position in packed, expand it to cover a a square with side length equal to 1 + expansion * 2, 2764 * centered on the original "on" position, unless the expansion would take a cell further than 0, 2765 * width - 1 (for xMove) or height - 1 (for yMove), in which case that cell is removed if drop is 2766 * true, or stopped at the edge if drop is false. 2767 * If a cell is "on" in packed, it will always be "off" in the result. 2768 * Returns a new packed short[] and does not modify packed. 2769 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2770 * @param expansion the positive (square-shaped) radius, in cells, to expand each cell out by 2771 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2772 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2773 * @param eightWay true if the expansion should be both diagonal and orthogonal; false for just orthogonal 2774 * @param drop true to drop cells that would expand into negative coordinates or past width/height, false to stop 2775 * their expansion early 2776 * @return a packed array that encodes "on" for cells that were pushed from the edge of packed's "on" cells 2777 */ 2778 public static short[] fringe(short[] packed, int expansion, int width, int height, boolean eightWay, boolean drop) 2779 { 2780 if(!drop) 2781 return fringe(packed, expansion, width, height, eightWay); 2782 if(packed == null || packed.length <= 1) 2783 { 2784 return ALL_WALL; 2785 } 2786 ShortVLA vla = new ShortVLA(256); 2787 IntSet ss = new IntSet(256); 2788 boolean on = false; 2789 int idx = 0; 2790 short x, y, dist; 2791 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2792 for(int p = 0; p < packed.length; p++, on = !on) { 2793 if (on) { 2794 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2795 ss.add(i); 2796 } 2797 } 2798 idx += packed[p] & 0xffff; 2799 } 2800 on = false; 2801 idx = 0; 2802 for(int p = 0; p < packed.length; p++, on = !on) { 2803 if (on) { 2804 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2805 x = hilbertX[i]; 2806 y = hilbertY[i]; 2807 if (eightWay) { 2808 for (int j = x - expansion; j <= x + expansion; j++) { 2809 for (int k = y - expansion; k <= y + expansion; k++) { 2810 if (j >= 0 && k >= 0 && j < width && k < height) { 2811 dist = hilbertDistances[j + (k << 8)]; 2812 if (ss.add(dist)) 2813 vla.add(dist); 2814 } 2815 } 2816 } 2817 } else { 2818 for (int d = 0; d < 4; d++) { 2819 for (int e = 1; e <= expansion; e++) { 2820 for (int e2 = 0; e2 <= expansion - e; e2++) { 2821 int j = x + xOffsets[d] * e + yOffsets[d + 1] * e2; 2822 int k = y + yOffsets[d] * e + xOffsets[d + 1] * e2; 2823 2824 if (j >= 0 && k >= 0 && j < width && k < height) { 2825 dist = hilbertDistances[j + (k << 8)]; 2826 if (ss.add(dist)) 2827 vla.add(dist); 2828 } 2829 } 2830 } 2831 } 2832 } 2833 2834 } 2835 } 2836 idx += packed[p] & 0xffff; 2837 } 2838 int[] indices = vla.asInts(); 2839 if(indices.length < 1) 2840 return ALL_WALL; 2841 Arrays.sort(indices); 2842 2843 vla.clear(); 2844 int current, past = indices[0], skip = 0; 2845 2846 vla.add((short)indices[0]); 2847 for (int i = 1; i < indices.length; i++) { 2848 current = indices[i]; 2849 if (current - past > 1) 2850 { 2851 vla.add((short) (skip+1)); 2852 skip = 0; 2853 vla.add((short)(current - past - 1)); 2854 } 2855 else if(current != past) 2856 skip++; 2857 past = current; 2858 } 2859 vla.add((short)(skip+1)); 2860 2861 return vla.toArray(); 2862 } 2863 2864 /** 2865 * Finds the concentric areas around the cells encoded in packed, without including those cells. For each "on" 2866 * position in packed, expand it to cover a a square with side length equal to 1 + n * 2, where n starts at 1 and 2867 * goes up to include the expansions parameter, with each expansion centered on the original "on" position, unless 2868 * the expansion would take a cell further than 0, width - 1 (for xMove) or height - 1 (for yMove), in which case 2869 * that cell is stopped at the edge. If a cell is "on" in packed, it will always be "off" in the results. 2870 * Returns a new packed short[][] where the outer array has length equal to expansions and the inner arrays are 2871 * packed data encoding a one-cell-wide concentric fringe region. Uses 8-way measurement. Does not modify packed. 2872 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2873 * @param expansions the positive (square-shaped) radius, in cells, to expand each cell out by, also the length 2874 * of the outer array returned by this method 2875 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2876 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2877 * @return an array of packed arrays that encode "on" for cells that were pushed from the edge of packed's "on" 2878 * cells; the outer array will have length equal to expansions, and inner arrays will normal packed data 2879 */ 2880 public static short[][] fringes(short[] packed, int expansions, int width, int height) { 2881 short[][] finished = new short[expansions][]; 2882 if (packed == null || packed.length <= 1) { 2883 Arrays.fill(finished, ALL_WALL); 2884 return finished; 2885 } 2886 IntSet ss = new IntSet(256); 2887 boolean on = false; 2888 int idx = 0; 2889 short x, y, dist; 2890 for (int p = 0; p < packed.length; p++, on = !on) { 2891 if (on) { 2892 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2893 ss.add(i); 2894 } 2895 } 2896 idx += packed[p] & 0xffff; 2897 } 2898 for (int expansion = 1; expansion <= expansions; expansion++) { 2899 ShortVLA vla = new ShortVLA(256); 2900 on = false; 2901 idx = 0; 2902 for (int p = 0; p < packed.length; p++, on = !on) { 2903 if (on) { 2904 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2905 x = hilbertX[i]; 2906 y = hilbertY[i]; 2907 for (int j = Math.max(0, x - expansion); j <= Math.min(width - 1, x + expansion); j++) { 2908 for (int k = Math.max(0, y - expansion); k <= Math.min(height - 1, y + expansion); k++) { 2909 dist = hilbertDistances[j + (k << 8)]; 2910 if (ss.add(dist)) 2911 vla.add(dist); 2912 } 2913 } 2914 } 2915 } 2916 idx += packed[p] & 0xffff; 2917 } 2918 int[] indices = vla.asInts(); 2919 if(indices.length < 1) 2920 { 2921 finished[expansion - 1] = ALL_WALL; 2922 continue; 2923 } 2924 Arrays.sort(indices); 2925 2926 vla.clear(); 2927 int current, past = indices[0], skip = 0; 2928 2929 vla.add((short) indices[0]); 2930 for (int i = 1; i < indices.length; i++) { 2931 current = indices[i]; 2932 if (current - past > 1) 2933 { 2934 vla.add((short) (skip+1)); 2935 skip = 0; 2936 vla.add((short)(current - past - 1)); 2937 } 2938 else if(current != past) 2939 skip++; 2940 past = current; 2941 } 2942 vla.add((short) (skip + 1)); 2943 2944 finished[expansion-1] = vla.toArray(); 2945 } 2946 return finished; 2947 } 2948 2949 2950 /** 2951 * Finds the concentric areas around the cells encoded in packed, without including those cells. For each "on" 2952 * position in packed, expand it to cover a a square or diamond with radius equal to n, where n starts at 1 and 2953 * goes up to include the expansions parameter, with each expansion centered on the original "on" position, unless 2954 * the expansion would take a cell further than 0, width - 1 (for xMove) or height - 1 (for yMove), in which case 2955 * that cell is stopped at the edge. If a cell is "on" in packed, it will always be "off" in the results. 2956 * Returns a new packed short[][] where the outer array has length equal to expansions and the inner arrays are 2957 * packed data encoding a one-cell-wide concentric fringe region. Does not modify packed. 2958 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 2959 * @param expansions the positive (square-shaped) radius, in cells, to expand each cell out by, also the length 2960 * of the outer array returned by this method 2961 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 2962 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 2963 * @param eightWay true if the expansion should be both diagonal and orthogonal; false for just orthogonal 2964 * @return an array of packed arrays that encode "on" for cells that were pushed from the edge of packed's "on" 2965 * cells; the outer array will have length equal to expansions, and inner arrays will normal packed data 2966 */ 2967 public static short[][] fringes(short[] packed, int expansions, int width, int height, boolean eightWay) { 2968 if(eightWay) 2969 return fringes(packed, expansions, width, height); 2970 short[][] finished = new short[expansions][]; 2971 if (packed == null || packed.length <= 1) { 2972 Arrays.fill(finished, ALL_WALL); 2973 return finished; 2974 } 2975 IntSet ss = new IntSet(256); 2976 boolean on = false; 2977 int idx = 0; 2978 short x, y, dist; 2979 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 2980 for (int p = 0; p < packed.length; p++, on = !on) { 2981 if (on) { 2982 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2983 ss.add(i); 2984 } 2985 } 2986 idx += packed[p] & 0xffff; 2987 } 2988 for (int expansion = 1; expansion <= expansions; expansion++) { 2989 ShortVLA vla = new ShortVLA(256); 2990 on = false; 2991 idx = 0; 2992 for (int p = 0; p < packed.length; p++, on = !on) { 2993 if (on) { 2994 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 2995 x = hilbertX[i]; 2996 y = hilbertY[i]; 2997 for (int d = 0; d < 4; d++) { 2998 for (int e = 1; e <= expansion; e++) { 2999 for (int e2 = 0; e2 <= expansion - e; e2++) { 3000 int j = Math.min(width - 1, Math.max(0, x + xOffsets[d] * e + yOffsets[d + 1] * e2)); 3001 int k = Math.min(height - 1, Math.max(0, y + yOffsets[d] * e + xOffsets[d + 1] * e2)); 3002 dist = hilbertDistances[j + (k << 8)]; 3003 if (ss.add(dist)) 3004 vla.add(dist); 3005 } 3006 } 3007 } 3008 } 3009 } 3010 idx += packed[p] & 0xffff; 3011 } 3012 int[] indices = vla.asInts(); 3013 if(indices.length < 1) 3014 { 3015 finished[expansion - 1] = ALL_WALL; 3016 continue; 3017 } 3018 Arrays.sort(indices); 3019 3020 vla.clear(); 3021 int current, past = indices[0], skip = 0; 3022 3023 vla.add((short) indices[0]); 3024 for (int i = 1; i < indices.length; i++) { 3025 current = indices[i]; 3026 if (current - past > 1) 3027 { 3028 vla.add((short) (skip+1)); 3029 skip = 0; 3030 vla.add((short)(current - past - 1)); 3031 } 3032 else if(current != past) 3033 skip++; 3034 past = current; 3035 } 3036 vla.add((short) (skip + 1)); 3037 3038 finished[expansion-1] = vla.toArray(); 3039 } 3040 return finished; 3041 } 3042 3043 /** 3044 * Finds the area consisting of the "on" positions in packed that are within the specified depth distance of an 3045 * "off" position or the edge of the map. This essentially finds the part of packed that is close to its edge. 3046 * Uses 8-way movement (Chebyshev distance) unless the overload of this function that takes a boolean argument 3047 * eightWay is used and that argument is false. 3048 * Returns a new packed short[] and does not modify packed. 3049 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 3050 * @param depth the positive (square) radius, in cells, to go inward from an "off" cell into the "in" cells 3051 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 3052 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 3053 * @return a short[] that encodes "on" for cells that were "on" in packed and were close enough to an "off" cell 3054 */ 3055 public static short[] surface(short[] packed, int depth, int width, int height) 3056 { 3057 return intersectPacked(packed, expand(negatePacked(packed), depth, width, height, true)); 3058 } 3059 /*{ 3060 if(packed == null || packed.length <= 1) 3061 { 3062 return ALL_WALL; 3063 } 3064 ShortVLA vla = new ShortVLA(256); 3065 boolean on = false; 3066 int idx = 0, x, y; 3067 for(int p = 0; p < packed.length; p++, on = !on) { 3068 if (on) { 3069 INDICES: 3070 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) 3071 { 3072 x = hilbertX[i]; 3073 y = hilbertY[i]; 3074 for (int j = Math.max(0, x - depth); j <= Math.min(width - 1, x + depth); j++) { 3075 for (int k = Math.max(0, y - depth); k <= Math.min(height - 1, y + depth); k++) { 3076 if(!queryPackedHilbert(packed, hilbertDistances[j + (k << 8)])) 3077 { 3078 vla.add((short)i); 3079 continue INDICES; 3080 } 3081 } 3082 } 3083 } 3084 } 3085 idx += packed[p] & 0xffff; 3086 } 3087 3088 int[] indices = vla.asInts(); 3089 if(indices.length < 1) 3090 return ALL_WALL; 3091 Arrays.sort(indices); 3092 3093 vla.clear(); 3094 int current, past = indices[0], skip = 0; 3095 3096 vla.add((short)indices[0]); 3097 for (int i = 1; i < indices.length; i++) { 3098 current = indices[i]; 3099 if (current - past > 1) 3100 { 3101 vla.add((short) (skip+1)); 3102 skip = 0; 3103 vla.add((short)(current - past - 1)); 3104 } 3105 else if(current != past) 3106 skip++; 3107 past = current; 3108 } 3109 vla.add((short)(skip+1)); 3110 return vla.toArray(); 3111 } 3112 */ 3113 /** 3114 * Finds the area consisting of the "on" positions in packed that are within the specified depth distance of an 3115 * "off" position or the edge of the map. This essentially finds the part of packed that is close to its edge. 3116 * Returns a new packed short[] and does not modify packed. 3117 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 3118 * @param depth the positive (square) radius, in cells, to go inward from an "off" cell into the "in" cells 3119 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 3120 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 3121 * @param eightWay true if the retraction should be both diagonal and orthogonal; false for just orthogonal 3122 * @return a short[] that encodes "on" for cells that were "on" in packed and were close enough to an "off" cell 3123 */ 3124 public static short[] surface(short[] packed, int depth, int width, int height, boolean eightWay) 3125 { 3126 return intersectPacked(packed, expand(negatePacked(packed), depth, width, height, eightWay)); 3127 } 3128 /** 3129 * Finds the concentric, progressively-smaller surfaces of packed as if packed was shrinking with each iteration. 3130 * Essentially, this is the inverse of fringes, where fringe finds a ring around packed and fringes finds concentric 3131 * rings around growing versions of packed, while surface finds a ring at the edge and surfaces finds rings at the 3132 * edge of shrinking versions of packed. 3133 * Returns a new packed short[] and does not modify packed. 3134 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 3135 * @param depth the positive (square) radius, in cells, to go inward from an "off" cell into the "in" cells 3136 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 3137 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 3138 * @return an array of packed short[] that each encodes "on" for cells that were "on" in packed and were at a 3139 * distance between 1 and depth to an "off" cell 3140 */ 3141 public static short[][] surfaces(short[] packed, int depth, int width, int height) 3142 { 3143 short[][] sfs = new short[depth][], frs = fringes(negatePacked(packed), depth, width, height); 3144 for (int i = 0; i < depth; i++) { 3145 sfs[i] = intersectPacked(packed, frs[i]); 3146 } 3147 return sfs; 3148 } 3149 /** 3150 * Finds the concentric, progressively-smaller surfaces of packed as if packed was shrinking with each iteration. 3151 * Essentially, this is the inverse of fringes, where fringe finds a ring around packed and fringes finds concentric 3152 * rings around growing versions of packed, while surface finds a ring at the edge and surfaces finds rings at the 3153 * edge of shrinking versions of packed. 3154 * Returns a new packed short[] and does not modify packed. 3155 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti() 3156 * @param depth the positive (square) radius, in cells, to go inward from an "off" cell into the "in" cells 3157 * @param width the maximum width; if a cell would move to x at least equal to width, it stops at width - 1 3158 * @param height the maximum height; if a cell would move to y at least equal to height, it stops at height - 1 3159 * @param eightWay true if the retraction should be both diagonal and orthogonal; false for just orthogonal 3160 * @return an array of packed short[] that each encodes "on" for cells that were "on" in packed and were at a 3161 * distance between 1 and depth to an "off" cell 3162 */ 3163 public static short[][] surfaces(short[] packed, int depth, int width, int height, boolean eightWay) 3164 { 3165 short[][] sfs = new short[depth][], frs = fringes(negatePacked(packed), depth, width, height, eightWay); 3166 for (int i = 0; i < depth; i++) { 3167 sfs[i] = intersectPacked(packed, frs[i]); 3168 } 3169 return sfs; 3170 } 3171 3172 /*{ 3173 if(eightWay) 3174 return surface(packed, depth, width, height); 3175 if(packed == null || packed.length <= 1) 3176 { 3177 return ALL_WALL; 3178 } 3179 ShortVLA vla = new ShortVLA(256); 3180 boolean on = false; 3181 int idx = 0, x, y, j, k; 3182 int[] xOffsets = new int[]{0, 1, 0, -1, 0}, yOffsets = new int[]{1, 0, -1, 0, 1}; 3183 for(int p = 0; p < packed.length; p++, on = !on) { 3184 if (on) { 3185 INDICES: 3186 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) 3187 { 3188 x = hilbertX[i]; 3189 y = hilbertY[i]; 3190 for (int d = 0; d < 4; d++) { 3191 for (int e = 1; e <= depth; e++) { 3192 for (int e2 = 0; e2 < depth; e2++) { 3193 j = x + xOffsets[d] * e + yOffsets[d + 1] * e2; 3194 k = y + yOffsets[d] * e + xOffsets[d + 1] * e2; 3195 if (j < 0 || k < 0 || j >= width || k >= height || 3196 !queryPackedHilbert(packed, hilbertDistances[j + (k << 8)])) { 3197 vla.add((short)i); 3198 continue INDICES; 3199 } 3200 } 3201 } 3202 } 3203 } 3204 } 3205 idx += packed[p] & 0xffff; 3206 } 3207 3208 int[] indices = vla.asInts(); 3209 if(indices.length < 1) 3210 return ALL_WALL; 3211 Arrays.sort(indices); 3212 3213 vla.clear(); 3214 int current, past = indices[0], skip = 0; 3215 3216 vla.add((short)indices[0]); 3217 for (int i = 1; i < indices.length; i++) { 3218 current = indices[i]; 3219 if (current - past > 1) 3220 { 3221 vla.add((short) (skip+1)); 3222 skip = 0; 3223 vla.add((short)(current - past - 1)); 3224 } 3225 else if(current != past) 3226 skip++; 3227 past = current; 3228 } 3229 vla.add((short)(skip+1)); 3230 return vla.toArray(); 3231 }*/ 3232 3233 3234 /** 3235 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, and an 3236 * amount of expansion, expands each cell in start by a Manhattan (diamond) radius equal to expansion, limiting any 3237 * expansion to within bounds and returning the final expanded (limited) packed data. Notably, if a small area is 3238 * not present within bounds, then the flood will move around the "hole" similarly to DijkstraMap's behavior; 3239 * essentially, it needs to expand around the hole to get to the other side, and this takes more steps of expansion 3240 * than crossing straight over. 3241 * Returns a new packed short[] and does not modify bounds or start. 3242 * @param bounds packed data representing the maximum extent of the region to flood-fill; often floors 3243 * @param start a packed array that encodes position(s) that the flood will spread outward from 3244 * @param expansion the positive (square) radius, in cells, to expand each cell out by 3245 * @return a packed array that encodes "on" for cells that are "on" in bounds and are within expansion Manhattan 3246 * distance from a Coord in start 3247 */ 3248 public static short[] flood(short[] bounds, short[] start, int expansion) 3249 { 3250 if(bounds == null || bounds.length <= 1) 3251 { 3252 return ALL_WALL; 3253 } 3254 int boundSize = count(bounds); 3255 ShortVLA vla = new ShortVLA(256); 3256 IntSet ss = new IntSet(boundSize), quickBounds = new IntSet(boundSize); 3257 boolean on = false, justAdded; 3258 int idx = 0; 3259 short x, y, dist; 3260 for(int p = 0; p < bounds.length; p++, on = !on) { 3261 if (on) { 3262 for (int i = idx; i < idx + (bounds[p] & 0xffff); i++) { 3263 quickBounds.add((short) i); 3264 } 3265 } 3266 idx += bounds[p] & 0xffff; 3267 } 3268 short[] s2 = allPackedHilbert(start); 3269 ss.addAll(s2); 3270 vla.addAll(s2); 3271 int[] xOffsets = new int[]{0, 1, 0, -1}, yOffsets = new int[]{1, 0, -1, 0}; 3272 for (int e = 0; e < expansion; e++) { 3273 justAdded = false; 3274 ShortVLA edge = new ShortVLA(128); 3275 for (int s = 0; s < s2.length; s++) { 3276 int i = s2[s] & 0xffff; 3277 x = hilbertX[i]; 3278 y = hilbertY[i]; 3279 3280 for (int d = 0; d < 4; d++) { 3281 int j = Math.min(255, Math.max(0, x + xOffsets[d])); 3282 int k = Math.min(255, Math.max(0, y + yOffsets[d])); 3283 dist = hilbertDistances[j + (k << 8)]; 3284 if (quickBounds.contains(dist)) { 3285 if (ss.add(dist)) { 3286 vla.add(dist); 3287 edge.add(dist); 3288 justAdded = true; 3289 } 3290 } 3291 } 3292 } 3293 if(!justAdded) 3294 break; 3295 s2 = edge.toArray(); 3296 } 3297 3298 int[] indices = vla.asInts(); 3299 if(indices.length < 1) 3300 return ALL_WALL; 3301 Arrays.sort(indices); 3302 3303 vla.clear(); 3304 int current, past = indices[0], skip = 0; 3305 3306 vla.add((short)indices[0]); 3307 for (int i = 1; i < indices.length; i++) { 3308 current = indices[i]; 3309 if (current - past > 1) 3310 { 3311 vla.add((short) (skip+1)); 3312 skip = 0; 3313 vla.add((short)(current - past - 1)); 3314 } 3315 else if(current != past) 3316 skip++; 3317 past = current; 3318 } 3319 vla.add((short)(skip+1)); 3320 3321 return vla.toArray(); 3322 } 3323 3324 3325 /** 3326 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, and an 3327 * amount of expansion, expands each cell in start by a radius (if eightWay is true, it uses Chebyshev distance; if 3328 * it is false, it uses Manhattan distance) equal to expansion, limiting any expansion to within bounds and 3329 * returning the final expanded (limited) packed data. Notably, if a small area is not present within bounds, then 3330 * the flood will move around the "hole" similarly to DijkstraMap's behavior; essentially, it needs to expand around 3331 * the hole to get to the other side, and this takes more steps of expansion than crossing straight over. 3332 * Returns a new packed short[] and does not modify bounds or start. 3333 * @param bounds packed data representing the maximum extent of the region to flood-fill; often floors 3334 * @param start a packed array that encodes position(s) that the flood will spread outward from 3335 * @param expansion the positive (square) radius, in cells, to expand each cell out by 3336 * @param eightWay true to flood-fill out in all eight directions at each step, false for just orthogonal 3337 * @return a packed array that encodes "on" for cells that are "on" in bounds and are within expansion either 3338 * Chebyshev (if eightWay is true) or Manhattan (otherwise) distance from a Coord in start 3339 */ 3340 public static short[] flood(short[] bounds, short[] start, int expansion, boolean eightWay) 3341 { 3342 if(!eightWay) 3343 return flood(bounds, start, expansion); 3344 if(bounds == null || bounds.length <= 1) 3345 { 3346 return ALL_WALL; 3347 } 3348 int boundSize = count(bounds); 3349 ShortVLA vla = new ShortVLA(256); 3350 IntSet ss = new IntSet(boundSize), quickBounds = new IntSet(boundSize); 3351 boolean on = false, justAdded; 3352 int idx = 0; 3353 short x, y, dist; 3354 for(int p = 0; p < bounds.length; p++, on = !on) { 3355 if (on) { 3356 for (int i = idx; i < idx + (bounds[p] & 0xffff); i++) { 3357 quickBounds.add((short) i); 3358 } 3359 } 3360 idx += bounds[p] & 0xffff; 3361 } 3362 short[] s2 = allPackedHilbert(start); 3363 ss.addAll(s2); 3364 vla.addAll(s2); 3365 int[] xOffsets = new int[]{-1, 0, 1, -1, 1, -1, 0, 1}, yOffsets = new int[]{-1, -1, -1, 0, 0, 1, 1, 1}; 3366 for (int e = 0; e < expansion; e++) { 3367 justAdded = false; 3368 ShortVLA edge = new ShortVLA(128); 3369 for (int s = 0; s < s2.length; s++) { 3370 int i = s2[s] & 0xffff; 3371 x = hilbertX[i]; 3372 y = hilbertY[i]; 3373 for (int d = 0; d < 8; d++) { 3374 int j = Math.min(255, Math.max(0, x + xOffsets[d])); 3375 int k = Math.min(255, Math.max(0, y + yOffsets[d])); 3376 dist = hilbertDistances[j + (k << 8)]; 3377 if (quickBounds.contains(dist)) { 3378 if (ss.add(dist)) { 3379 vla.add(dist); 3380 edge.add(dist); 3381 justAdded = true; 3382 } 3383 } 3384 } 3385 } 3386 if(!justAdded) 3387 break; 3388 s2 = edge.toArray(); 3389 } 3390 3391 int[] indices = vla.asInts(); 3392 if(indices.length < 1) 3393 return ALL_WALL; 3394 Arrays.sort(indices); 3395 3396 vla.clear(); 3397 int current, past = indices[0], skip = 0; 3398 3399 vla.add((short)indices[0]); 3400 for (int i = 1; i < indices.length; i++) { 3401 current = indices[i]; 3402 if (current - past > 1) 3403 { 3404 vla.add((short) (skip+1)); 3405 skip = 0; 3406 vla.add((short)(current - past - 1)); 3407 } 3408 else if(current != past) 3409 skip++; 3410 past = current; 3411 } 3412 vla.add((short)(skip+1)); 3413 3414 return vla.toArray(); 3415 } 3416 3417 3418 /** 3419 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, an IRNG, 3420 * and a volume in cells, expands a random cell in start in a random Manhattan (diamond) direction equal, then 3421 * continues to expand from random cells in start or the expanded area until it has filled volume cells, limiting 3422 * any expansion to within bounds and returning the final expanded (limited) packed data. Notably, if a small area 3423 * is not present within bounds, then the spill will move around the "hole" similarly to DijkstraMap's behavior; 3424 * essentially, it needs to expand around the hole to get to the other side, and this takes more steps of expansion 3425 * than crossing straight over. 3426 * <br> 3427 * Could also be given a name like randomizedFlood(), but spill() is used by the Spill class that does this too. 3428 * <br> 3429 * Returns a new packed short[] and does not modify bounds or start. 3430 * @param bounds packed data representing the maximum extent of the region to random-flood-fill; often floors 3431 * @param start a packed array that encodes position(s) that the random-flood will spread outward from 3432 * @param volume the total number of cells to try to fill 3433 * @param rng the {@link IRNG}, such as an {@link RNG} or {@link GWTRNG}, used to generate random numbers for the flooding 3434 * @return a packed array that encodes "on" for cells that are "on" in bounds and are within expansion Manhattan 3435 * distance from a Coord in start 3436 */ 3437 public static short[] spill(short[] bounds, short[] start, int volume, IRNG rng) 3438 { 3439 if(bounds == null || bounds.length <= 1) 3440 { 3441 return ALL_WALL; 3442 } 3443 int boundSize = count(bounds); 3444 ShortVLA vla = new ShortVLA(256); 3445 IntSet ss = new IntSet(boundSize), edge = new IntSet(boundSize), quickBounds = new IntSet(boundSize); 3446 boolean on = false; 3447 int idx = 0; 3448 short x, y, dist; 3449 for(int p = 0; p < bounds.length; p++, on = !on) { 3450 if (on) { 3451 for (int i = idx; i < idx + (bounds[p] & 0xffff); i++) { 3452 quickBounds.add((short) i); 3453 } 3454 } 3455 idx += bounds[p] & 0xffff; 3456 } 3457 short[] s2 = allPackedHilbert(start); 3458 int ct = s2.length; 3459 ss.addAll(s2); 3460 vla.addAll(s2); 3461 edge.addAll(allPackedHilbert(intersectPacked(bounds, fringe(start, 1, 256, 256, false)))); 3462 ss.addAll(edge); 3463 if(edge.size <= 0) 3464 { 3465 if(!intersects(bounds, start)) 3466 return ALL_WALL; 3467 3468 short[] cpy = new short[start.length]; 3469 System.arraycopy(start, 0, cpy, 0, start.length); 3470 return cpy; 3471 } 3472 int[] xOffsets = new int[]{0, 1, 0, -1}, yOffsets = new int[]{1, 0, -1, 0}; 3473 for (int v = ct; v < volume; v++) { 3474 int s = edge.random(rng); 3475 3476 edge.remove(s); 3477 vla.add((short)s); 3478 int i = s & 0xffff; 3479 x = hilbertX[i]; 3480 y = hilbertY[i]; 3481 3482 for (int d = 0; d < 4; d++) { 3483 int j = Math.min(255, Math.max(0, x + xOffsets[d])); 3484 int k = Math.min(255, Math.max(0, y + yOffsets[d])); 3485 dist = hilbertDistances[j + (k << 8)]; 3486 if (quickBounds.contains(dist)) { 3487 if (ss.add(dist)) { 3488 edge.add(dist); 3489 } 3490 } 3491 } 3492 3493 if(edge.size <= 0) 3494 break; 3495 } 3496 3497 int[] indices = vla.asInts(); 3498 if(indices.length < 1) 3499 return ALL_WALL; 3500 Arrays.sort(indices); 3501 3502 vla.clear(); 3503 int current, past = indices[0], skip = 0; 3504 3505 vla.add((short)indices[0]); 3506 for (int i = 1; i < indices.length; i++) { 3507 current = indices[i]; 3508 if (current - past > 1) 3509 { 3510 vla.add((short) (skip+1)); 3511 skip = 0; 3512 vla.add((short)(current - past - 1)); 3513 } 3514 else if(current != past) 3515 skip++; 3516 past = current; 3517 } 3518 vla.add((short)(skip+1)); 3519 3520 return vla.toArray(); 3521 } 3522 3523 private static void modifiedShadowFOV(int expansion, int viewerX, int viewerY, Radius metric, IntSet bounds, IntSet storedSet, ShortVLA vla) 3524 { 3525 if(expansion < 1) 3526 return; 3527 short start = hilbertDistances[viewerX + (viewerY << 8)]; 3528 if(storedSet.add(start)) 3529 vla.add(start); 3530 3531 for (Direction d : Direction.DIAGONALS) { 3532 modifiedShadowCast(expansion, 1, 1.0, 0.0, 0, d.deltaX, d.deltaY, 0, viewerX, viewerY, metric, bounds, storedSet, vla); 3533 modifiedShadowCast(expansion, 1, 1.0, 0.0, d.deltaX, 0, 0, d.deltaY, viewerX, viewerY, metric, bounds, storedSet, vla); 3534 } 3535 } 3536 3537 private static void modifiedShadowCast(int expansion, int row, double start, double end, int xx, int xy, int yx, int yy, 3538 int viewerX, int viewerY, Radius metric, IntSet bounds, IntSet storedSet, ShortVLA vla) { 3539 double newStart = 0; 3540 if (start < end) { 3541 return; 3542 } 3543 3544 boolean blocked = false; 3545 int dist; 3546 short currentPos; 3547 for (int distance = row; distance <= expansion && !blocked; distance++) { 3548 int deltaY = -distance; 3549 for (int deltaX = -distance; deltaX <= 0; deltaX++) { 3550 int currentX = viewerX + deltaX * xx + deltaY * xy; 3551 int currentY = viewerY + deltaX * yx + deltaY * yy; 3552 double leftSlope = (deltaX - 0.5f) / (deltaY + 0.5f); 3553 double rightSlope = (deltaX + 0.5f) / (deltaY - 0.5f); 3554 currentPos = hilbertDistances[currentX + (currentY << 8)]; 3555 3556 /* 3557 if (!bounds.contains(currentPos)) { 3558 newStart = rightSlope; 3559 continue; 3560 } 3561 else 3562 */ 3563 if(!(currentX - viewerX + expansion >= 0 && currentX - viewerX <= expansion 3564 && currentY - viewerY + expansion >= 0 && currentY - viewerY <= expansion) 3565 || start < rightSlope) { 3566 continue; 3567 } else if (end > leftSlope) { 3568 break; 3569 } 3570 3571 if (blocked) { //previous cell was a blocking one 3572 if (!bounds.contains(currentPos)) {//hit a wall 3573 newStart = rightSlope; 3574 } else { 3575 blocked = false; 3576 start = newStart; 3577 dist = metric.roughDistance(currentX - viewerX, currentY - viewerY); 3578 //check if it's within the lightable area and light if needed 3579 if (dist <= expansion * 2) { 3580 if(storedSet.add(currentPos)) 3581 vla.add(currentPos); 3582 } 3583 } 3584 } else { 3585 if (!bounds.contains(currentPos) && distance < expansion) {//hit a wall within sight line 3586 blocked = true; 3587 modifiedShadowCast(expansion, distance + 1, start, leftSlope, xx, xy, yx, yy, viewerX, viewerY, metric, bounds, storedSet, vla); 3588 newStart = rightSlope; 3589 } 3590 else 3591 { 3592 if(bounds.contains(currentPos)) { 3593 dist = metric.roughDistance(currentX - viewerX, currentY - viewerY); 3594 //check if it's within the lightable area and light if needed 3595 if (dist <= expansion * 2) { 3596 if (storedSet.add(currentPos)) 3597 vla.add(currentPos); 3598 } 3599 } 3600 } 3601 } 3602 } 3603 } 3604 } 3605 3606 /** 3607 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, and an 3608 * amount of expansion, expands each cell in start by a Manhattan (diamond) radius equal to expansion, limiting any 3609 * expansion to within bounds and returning the final expanded (limited) packed data. 3610 * Though this is otherwise similar to flood(), radiate() behaves like FOV and will not move around obstacles and 3611 * will instead avoid expanding if it would go into any cell that cannot be reached by a straight line (drawn 3612 * directly, not in grid steps) that is mostly unobstructed. 3613 * Returns a new packed short[] and does not modify bounds or start. 3614 * @param bounds packed data representing the maximum extent of the region to flood-fill; often floors 3615 * @param start a packed array that encodes position(s) that the flood will spread outward from 3616 * @param expansion the positive (square) radius, in cells, to expand each cell out by 3617 * @return a packed array that encodes "on" for cells that are "on" in bounds and are within expansion Manhattan 3618 * distance from a Coord in start 3619 */ 3620 public static short[] radiate(short[] bounds, short[] start, int expansion) 3621 { 3622 return radiate(bounds, start, expansion, Radius.DIAMOND); 3623 } 3624 /** 3625 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, and an 3626 * amount of expansion, expands each cell in start by a radius, with a shape determined by metric, equal to 3627 * expansion, limiting any expansion to within bounds and returning the final expanded (limited) packed data. 3628 * Though this is otherwise similar to flood(), radiate() behaves like FOV and will not move around obstacles and 3629 * will instead avoid expanding if it would go into any cell that cannot be reached by a straight line (drawn 3630 * directly, not in grid steps) that is mostly unobstructed. 3631 * Returns a new packed short[] and does not modify bounds or start. 3632 * @param bounds packed data representing the maximum extent of the region to flood-fill; often floors 3633 * @param start a packed array that encodes position(s) that the flood will spread outward from 3634 * @param expansion the positive (square) radius, in cells, to expand each cell out by 3635 * @param metric a Radius that defines how this should expand, SQUARE for 8-way, DIAMOND for 4-way, CIRCLE for 3636 * Euclidean expansion (not guaranteed to be perfectly circular) 3637 * @return a packed array that encodes "on" for cells that are "on" in bounds and are within expansion Manhattan 3638 * distance from a Coord in start 3639 */ 3640 public static short[] radiate(short[] bounds, short[] start, int expansion, Radius metric) 3641 { 3642 if(bounds == null || bounds.length <= 1) 3643 { 3644 return ALL_WALL; 3645 } 3646 int boundSize = count(bounds); 3647 ShortVLA vla = new ShortVLA(256); 3648 IntSet storedSet = new IntSet(boundSize), quickBounds = new IntSet(boundSize); 3649 boolean on = false; 3650 int idx = 0, i; 3651 short x, y; 3652 for(int p = 0; p < bounds.length; p++, on = !on) { 3653 if (on) { 3654 for (i = idx; i < idx + (bounds[p] & 0xffff); i++) { 3655 quickBounds.add(i); 3656 } 3657 } 3658 idx += bounds[p] & 0xffff; 3659 } 3660 short[] s2 = allPackedHilbert(start); 3661 for (int s = 0; s < s2.length; s++) { 3662 i = s2[s] & 0xffff; 3663 x = hilbertX[i]; 3664 y = hilbertY[i]; 3665 3666 modifiedShadowFOV(expansion, x, y, metric, quickBounds, storedSet, vla); 3667 } 3668 3669 int[] indices = vla.asInts(); 3670 if(indices.length < 1) 3671 return ALL_WALL; 3672 Arrays.sort(indices); 3673 3674 vla.clear(); 3675 int current, past = indices[0], skip = 0; 3676 3677 vla.add((short)indices[0]); 3678 for (i = 1; i < indices.length; i++) { 3679 current = indices[i]; 3680 if (current - past > 1) 3681 { 3682 vla.add((short) (skip+1)); 3683 skip = 0; 3684 vla.add((short)(current - past - 1)); 3685 } 3686 else if(current != past) 3687 skip++; 3688 past = current; 3689 } 3690 vla.add((short)(skip+1)); 3691 3692 return vla.toArray(); 3693 } 3694 3695 3696 /** 3697 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, and an 3698 * amount of expansion, expands each cell in start by a radius, with a square shape if eightWay is true or a diamond 3699 * otherwise, equal to expansion, limiting any expansion to within bounds and returning the final expanded (limited) 3700 * packed data. Though this is otherwise similar to flood(), radiate() behaves like FOV and will not move around 3701 * obstacles and will instead avoid expanding if it would go into any cell that cannot be reached by a straight line 3702 * (drawn directly, not in grid steps) that is mostly unobstructed. 3703 * Returns a new packed short[] and does not modify bounds or start. 3704 * @param bounds packed data representing the maximum extent of the region to flood-fill; often floors 3705 * @param start a packed array that encodes position(s) that the flood will spread outward from 3706 * @param expansion the positive (square) radius, in cells, to expand each cell out by 3707 * @param eightWay true to flood-fill out in all eight directions at each step, false for just orthogonal 3708 * @return a packed array that encodes "on" for cells that are "on" in bounds and are within expansion either 3709 * Chebyshev (if eightWay is true) or Manhattan (otherwise) distance from a Coord in start 3710 */ 3711 public static short[] radiate(short[] bounds, short[] start, int expansion, boolean eightWay) 3712 { 3713 if(eightWay) 3714 return radiate(bounds, start, expansion, Radius.SQUARE); 3715 return radiate(bounds, start, expansion, Radius.DIAMOND); 3716 } 3717 3718 /** 3719 * Given a packed array encoding a larger area, a packed array encoding one or more points inside bounds, and a 3720 * Reach object that determines targeting constraints, gets all cells contained within bounds that can be targeted 3721 * from a cell in start using the rules defined by reach. 3722 * Though this is otherwise similar to flood(), reachable() behaves like FOV and will not move around obstacles and 3723 * will instead avoid expanding if it would go into any cell that cannot be reached by a straight line (drawn 3724 * directly, not in grid steps) that is mostly unobstructed. This does not behave quite like FOV if an AimLimit has 3725 * been set in reach to any value other than null or AimLimit.FREE; in these cases it requires an exactly straight 3726 * orthogonal or diagonal line without obstructions, checking only cells along the precise path. For diagonals and 3727 * eight-way targeting, this means it can target through walls that only meet at a perpendicular diagonal, such as 3728 * an X shape where one line is a one-cell-thick diagonal wall and the other is the targeting line. This is normally 3729 * only allowed in some games and only if they use Chebyshev (Radius.SQUARE) distance, so be advised that it may not 3730 * be desirable behavior. 3731 * Returns a new packed short[] and does not modify bounds or start. 3732 * @param bounds packed data representing the max extent of the region to check for reach-ability; often floors 3733 * @param start a packed array that encodes position(s) that the flood will spread outward from 3734 * @param reach a {@link Reach} object that determines minimum and maximum range, distance metric, and AimLimit 3735 * @return a packed array that encodes "on" for cells that are "on" in bounds and can be targeted from a cell in 3736 * start using the given Reach 3737 */ 3738 public static short[] reachable(short[] bounds, short[] start, Reach reach) 3739 { 3740 if(bounds == null || bounds.length <= 1) 3741 { 3742 return ALL_WALL; 3743 } 3744 int boundSize = count(bounds); 3745 ShortVLA vla = new ShortVLA(256), discard = new ShortVLA(128); 3746 IntSet storedSet = new IntSet(boundSize), quickBounds = new IntSet(boundSize); 3747 boolean on = false; 3748 int idx = 0, i; 3749 short x, y; 3750 for(int p = 0; p < bounds.length; p++, on = !on) { 3751 if (on) { 3752 for (i = idx; i < idx + (bounds[p] & 0xffff); i++) { 3753 quickBounds.add(i); 3754 } 3755 } 3756 idx += bounds[p] & 0xffff; 3757 } 3758 short[] s2 = allPackedHilbert(start); 3759 if(reach.limit == null || reach.limit == AimLimit.FREE) { 3760 for (int s = 0; s < s2.length; s++) { 3761 i = s2[s] & 0xffff; 3762 x = hilbertX[i]; 3763 y = hilbertY[i]; 3764 //add all cells at less than minimum distance to storedSet. 3765 modifiedShadowFOV(reach.minDistance - 1, x, y, reach.metric, quickBounds, storedSet, discard); 3766 discard.clear(); 3767 modifiedShadowFOV(reach.maxDistance, x, y, reach.metric, quickBounds, storedSet, vla); 3768 } 3769 } 3770 else 3771 { 3772 for (int s = 0; s < s2.length; s++) { 3773 i = s2[s] & 0xffff; 3774 x = hilbertX[i]; 3775 y = hilbertY[i]; 3776 Direction[] dirs; 3777 switch (reach.limit) 3778 { 3779 case ORTHOGONAL: dirs = Direction.CARDINALS; 3780 break; 3781 case DIAGONAL: dirs = Direction.DIAGONALS; 3782 break; 3783 default: dirs = Direction.OUTWARDS; 3784 } 3785 Direction dir; 3786 DIRECTIONAL: 3787 for (int which = 0; which < dirs.length; which++) { 3788 dir = dirs[which]; 3789 int d; 3790 //add all cells at less than minimum distance to storedSet. 3791 for (d = 1; d < reach.minDistance; d++) { 3792 int extended = (x + dir.deltaX * d) + ((y + dir.deltaY * d) << 8); 3793 if (extended < 0 || extended > 0xffff) 3794 continue DIRECTIONAL; 3795 short next = hilbertDistances[extended]; 3796 if (quickBounds.contains(next)) 3797 storedSet.add(next); 3798 else 3799 continue DIRECTIONAL; 3800 } 3801 for (; d <= reach.maxDistance; d++) { 3802 int extended = (x + dir.deltaX * d) + ((y + dir.deltaY * d) << 8); 3803 if (extended < 0 || extended > 0xffff) 3804 continue DIRECTIONAL; 3805 short next = hilbertDistances[extended]; 3806 if (quickBounds.contains(next)) { 3807 if (storedSet.add(next)) 3808 vla.add(next); 3809 } 3810 else 3811 continue DIRECTIONAL; 3812 } 3813 } 3814 } 3815 } 3816 if(vla.size == 0) 3817 return ALL_WALL; 3818 int[] indices = vla.asInts(); 3819 Arrays.sort(indices); 3820 3821 vla.clear(); 3822 int current, past = indices[0], skip = 0; 3823 3824 vla.add((short)indices[0]); 3825 for (i = 1; i < indices.length; i++) { 3826 current = indices[i]; 3827 if (current - past > 1) 3828 { 3829 vla.add((short) (skip+1)); 3830 skip = 0; 3831 vla.add((short)(current - past - 1)); 3832 } 3833 else if(current != past) 3834 skip++; 3835 past = current; 3836 } 3837 vla.add((short)(skip+1)); 3838 3839 return vla.toArray(); 3840 } 3841 /** 3842 * Given a width and height, returns a packed array that encodes "on" for the rectangle from (0,0) to 3843 * (width - 1, height - 1). Primarily useful with intersectPacked() to ensure things like negatePacked() that can 3844 * encode "on" cells in any position are instead limited to the bounds of the map. 3845 * @param width the width of the rectangle 3846 * @param height the height of the rectangle 3847 * @return a packed short[] encoding "on" for all cells with x less than width and y less than height. 3848 */ 3849 public static short[] rectangle(int width, int height) 3850 { 3851 if(width > 256 || height > 256) 3852 throw new UnsupportedOperationException("Map size is too large to efficiently pack, aborting"); 3853 boolean[][] rect = new boolean[width][height]; 3854 for (int i = 0; i < width; i++) { 3855 Arrays.fill(rect[i], true); 3856 } 3857 return pack(rect); 3858 } 3859 /** 3860 * Given x, y, width and height, returns a packed array that encodes "on" for the rectangle from (x,y) to 3861 * (width + x - 1, height + y - 1). Primarily useful with intersectPacked() to ensure things like negatePacked() that 3862 * can encode "on" cells in any position are instead limited to the bounds of the map, but also handy for basic "box 3863 * drawing" for other uses. 3864 * @param x the minimum x coordinate 3865 * @param y the minimum y coordinate 3866 * @param width the width of the rectangle 3867 * @param height the height of the rectangle 3868 * @return a packed short[] encoding "on" for all cells between (x,y) and (x+width-1,y+height-1). 3869 */ 3870 public static short[] rectangle(int x, int y, int width, int height) 3871 { 3872 int width2 = width, height2 = height; 3873 if(x + width >= 256) 3874 width2 = 255 - x; 3875 if(y + height >= 256) 3876 height2 = 255 - y; 3877 if(width2 < 0 || height2 < 0 || x < 0 || y < 0) 3878 return ALL_WALL; 3879 boolean[][] rect = new boolean[x + width2][y + height2]; 3880 for (int i = x; i < x + width2; i++) { 3881 Arrays.fill(rect[i], y, y + height2, true); 3882 } 3883 return pack(rect); 3884 } 3885 /** 3886 * Given x, y, width and height, returns an array of all Hilbert distance within the rectangle from (x,y) to 3887 * (width + x - 1, height + y - 1). 3888 * @param x the minimum x coordinate 3889 * @param y the minimum y coordinate 3890 * @param width the width of the rectangle 3891 * @param height the height of the rectangle 3892 * @return a short[] that is not packed, and instead stores individual Hilbert distances in the rectangle 3893 */ 3894 public static short[] rectangleHilbert(int x, int y, int width, int height) 3895 { 3896 int width2 = width, height2 = height; 3897 if(x + width >= 256) 3898 width2 = 256 - x; 3899 if(y + height >= 256) 3900 height2 = 256 - y; 3901 if(width2 <= 0 || height2 <= 0 || x < 0 || y < 0) 3902 return new short[0]; 3903 short[] hilberts = new short[width2 * height2]; 3904 int idx = 0; 3905 for (int i = x; i < x + width2; i++) { 3906 for (int j = y; j < y + height2; j++) { 3907 hilberts[idx++] = hilbertDistances[i + (j << 8)]; 3908 } 3909 } 3910 return hilberts; 3911 } 3912 3913 /** 3914 * Given a center and radius for a circle, plus the width and height for the map boundaries, returns the packed data 3915 * that encodes the circle. 3916 * @param center center position of the circle 3917 * @param radius radius to extend in all directions from center 3918 * @param width the maximum width of the map (exclusive); the circle will not extend past this or below 0 3919 * @param height the maximum height of the map (exclusive); the circle will not extend past this or below 0 3920 * @return a packed short[] encoding "on" for all elements inside the circle 3921 */ 3922 public static short[] circle(Coord center, int radius, int width, int height) 3923 { 3924 return packSeveral(Radius.CIRCLE.pointsInside(center, radius, false, width, height)); 3925 } 3926 /** 3927 * Counts the number of "on" cells encoded in a packed array without unpacking it. 3928 * @param packed a packed short array, as produced by pack() 3929 * @return the number of "on" cells. 3930 */ 3931 public static int count(short[] packed) 3932 { 3933 return count(packed, true); 3934 } 3935 3936 /** 3937 * Counts the number of cells encoding a boolean equal to wanted in a packed array without unpacking it. 3938 * @param packed a packed short array, as produced by pack() 3939 * @param wanted the boolean you want to count, true for "on" and false for "off" 3940 * @return the number of cells that encode a value equal to wanted. 3941 */ 3942 public static int count(short[] packed, boolean wanted) 3943 { 3944 int c = 0; 3945 boolean on = false; 3946 for (int i = 0; i < packed.length; i++, on = !on) { 3947 if(on == wanted) 3948 c += packed[i] & 0xffff; 3949 } 3950 return c; 3951 } 3952 /** 3953 * Finds how many cells are encoded in a packed array (both on and off) without unpacking it. 3954 * @param packed a packed short array, as produced by pack() 3955 * @return the number of cells that are encoded explicitly in the packed data as either on or off. 3956 */ 3957 public static int covered(short[] packed) 3958 { 3959 int c = 0; 3960 for (int i = 0; i < packed.length; i++) { 3961 c += packed[i] & 0xffff; 3962 } 3963 return c; 3964 } 3965 3966 /** 3967 * Finds the minimum bounding rectangle for a packed array without unpacking it. Returns a Coord array with 2 3968 * elements: the minimum-x/minimum-y Coord corner of the bounds, then the maximum-x/maximum-y Coord corner. Both 3969 * array elements will be the Coord (-1,-1) if the packed array does not encode any "on" values (all empty). 3970 * @param packed a packed short array, as produced by pack() 3971 * @return a 2-element Coord array starting with the bounds' minimum corner and followed by the maximum corner 3972 */ 3973 public static Coord[] bounds(short[] packed) 3974 { 3975 Coord[] c = new Coord[]{Coord.get(-1,-1), Coord.get(-1,-1)}; 3976 boolean on = false; 3977 int idx = 0, min_x = 256, min_y = 256, max_x = -1, max_y = -1, x, y; 3978 for(int p = 0; p < packed.length; p++, on = !on) { 3979 if (on) { 3980 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 3981 x = hilbertX[i]; 3982 y = hilbertY[i]; 3983 if(min_x > x) 3984 min_x = x; 3985 if(min_y > y) 3986 min_y = y; 3987 if(max_x < x) 3988 max_x = x; 3989 if(max_y < y) 3990 max_y = y; 3991 } 3992 } 3993 idx += packed[p] & 0xffff; 3994 } 3995 if(min_x < 256) { 3996 c[0] = Coord.get(min_x, min_y); 3997 c[1] = Coord.get(max_x, max_y); 3998 } 3999 return c; 4000 } 4001 4002 /** 4003 * Given a 2D char array for a map, a piece of packed data defining a region to use from that map, and a filler 4004 * char, produces a 2D char array where all positions that are "off" in packed are filled with filler, and the rest 4005 * are the same as in map. 4006 * @param map a 2D char array that will not be modified 4007 * @param packed a packed short array, as produced by pack() 4008 * @param filler the char to use for "off" positions in packed 4009 * @return a 2D char array similar to map but with any "off" positions in packed replaced with filler 4010 */ 4011 public static char[][] mask(char[][] map, short[] packed, char filler) 4012 { 4013 if(map.length <= 0) 4014 return map; 4015 char[][] c = new char[map.length][map[0].length]; 4016 for (int i = 0; i < map.length; i++) { 4017 Arrays.fill(c[i], filler); 4018 } 4019 boolean on = false; 4020 int idx = 0, x, y; 4021 for(int p = 0; p < packed.length; p++, on = !on) { 4022 if (on) { 4023 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 4024 x = hilbertX[i]; 4025 y = hilbertY[i]; 4026 if(x >= map.length || y >= map[x].length) 4027 continue; 4028 c[x][y] = map[x][y]; 4029 } 4030 } 4031 idx += packed[p] & 0xffff; 4032 } 4033 return c; 4034 } 4035 4036 /** 4037 * Given two packed short arrays, left and right, this produces a packed short array that encodes "on" for any cell 4038 * that was "on" in either left or in right, and only encodes "off" for cells that were off in both. This method 4039 * does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly preferred 4040 * when merging two pieces of packed data. 4041 * @param left A packed array such as one produced by pack() 4042 * @param right A packed array such as one produced by pack() 4043 * @return A packed array that encodes "on" for all cells that were "on" in either left or right 4044 */ 4045 public static short[] unionPacked(short[] left, short[] right) 4046 { 4047 if(left.length == 0) 4048 return right; 4049 if(right.length == 0) 4050 return left; 4051 ShortVLA packing = new ShortVLA(64); 4052 boolean on = false, onLeft = false, onRight = false; 4053 int idx = 0, skip = 0, elemLeft = 0, elemRight = 0, totalLeft = 0, totalRight = 0; 4054 while ((elemLeft < left.length || elemRight < right.length) && idx <= 0xffff) { 4055 if (elemLeft >= left.length) { 4056 totalLeft = 0x20000; 4057 onLeft = false; 4058 } 4059 else if(totalLeft <= idx) { 4060 totalLeft += left[elemLeft] & 0xffff; 4061 } 4062 if(elemRight >= right.length) { 4063 totalRight = 0x20000; 4064 onRight = false; 4065 } 4066 else if(totalRight <= idx) { 4067 totalRight += right[elemRight] & 0xffff; 4068 } 4069 // 300, 5, 6, 8, 2, 4 4070 // 290, 12, 9, 1 4071 // = 4072 // 290, 15, 6, 8, 2, 4 4073 // 290 off in both, 10 in right, 2 in both, 3 in left, 6 off in both, 1 on in both, 7 on in left, 2 off in 4074 // both, 4 on in left 4075 if(totalLeft < totalRight) 4076 { 4077 onLeft = !onLeft; 4078 skip += totalLeft - idx; 4079 idx = totalLeft; 4080 if(on != (onLeft || onRight)) { 4081 packing.add((short) skip); 4082 skip = 0; 4083 on = !on; 4084 } 4085 elemLeft++; 4086 } 4087 else if(totalLeft == totalRight) 4088 { 4089 onLeft = !onLeft; 4090 onRight = !onRight; 4091 skip += totalLeft - idx; 4092 idx = totalLeft; 4093 if(on != (onLeft || onRight)) { 4094 packing.add((short) skip); 4095 skip = 0; 4096 on = !on; 4097 } 4098 elemLeft++; 4099 elemRight++; 4100 4101 } 4102 else 4103 { 4104 onRight = !onRight; 4105 skip += totalRight - idx; 4106 idx = totalRight; 4107 if(on != (onLeft || onRight)) { 4108 packing.add((short) skip); 4109 skip = 0; 4110 on = !on; 4111 } 4112 elemRight++; 4113 } 4114 } 4115 return packing.toArray(); 4116 } 4117 4118 /** 4119 * Given two packed short arrays, left and right, this produces a packed short array that encodes "on" for any cell 4120 * that was "on" in both left and in right, and encodes "off" for cells that were off in either array. This method 4121 * does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly preferred 4122 * when finding the intersection of two pieces of packed data. 4123 * @param left A packed array such as one produced by pack() 4124 * @param right A packed array such as one produced by pack() 4125 * @return A packed array that encodes "on" for all cells that were "on" in both left and right 4126 */ 4127 public static short[] intersectPacked(short[] left, short[] right) 4128 { 4129 if(left.length == 0 || right.length == 0) 4130 return ALL_WALL; 4131 ShortVLA packing = new ShortVLA(64); 4132 boolean on = false, onLeft = false, onRight = false; 4133 int idx = 0, skip = 0, elemLeft = 0, elemRight = 0, totalLeft = 0, totalRight = 0; 4134 while ((elemLeft < left.length && elemRight < right.length) && idx <= 0xffff) { 4135 if(totalLeft <= idx) { 4136 totalLeft += left[elemLeft] & 0xffff; 4137 } 4138 if(totalRight <= idx) { 4139 totalRight += right[elemRight] & 0xffff; 4140 } 4141 // 300, 5, 6, 8, 2, 4 4142 // 290, 12, 9, 1 4143 // = 4144 // 300, 2, 9, 1 4145 // 300 off, 2 on, 9 off, 1 on 4146 if(totalLeft < totalRight) 4147 { 4148 onLeft = !onLeft; 4149 skip += totalLeft - idx; 4150 idx = totalLeft; 4151 if(on != (onLeft && onRight)) { 4152 packing.add((short) skip); 4153 skip = 0; 4154 on = !on; 4155 } 4156 elemLeft++; 4157 } 4158 else if(totalLeft == totalRight) 4159 { 4160 onLeft = !onLeft; 4161 onRight = !onRight; 4162 skip += totalLeft - idx; 4163 idx = totalLeft; 4164 if(on != (onLeft && onRight)) { 4165 packing.add((short) skip); 4166 skip = 0; 4167 on = !on; 4168 } 4169 elemLeft++; 4170 elemRight++; 4171 4172 } 4173 else 4174 { 4175 onRight = !onRight; 4176 skip += totalRight - idx; 4177 idx = totalRight; 4178 if(on != (onLeft && onRight)) { 4179 packing.add((short) skip); 4180 skip = 0; 4181 on = !on; 4182 } 4183 elemRight++; 4184 } 4185 } 4186 return packing.toArray(); 4187 } 4188 4189 /** 4190 * Checks if no cells are encoded as "on" in packed. 4191 * @param packed a packed array such as one produced by pack() 4192 * @return false if there is at least one "on" cell in packed; true if there are no "on" cells 4193 */ 4194 public static boolean isEmpty(short[] packed) 4195 { 4196 return packed == null || packed.length <= 1; 4197 } 4198 /** 4199 * Given two packed short arrays, left and right, this returns true if they encode any overlapping area (their areas 4200 * intersect), or false if they do not overlap at all (they don't intersect). This is more efficient than calculating 4201 * the intersection with intersectPacked() just to check if it is non-empty, since this method can short-circuit and 4202 * return true the moment it finds an intersection, plus it needs less overhead (slightly) to do so. 4203 * @param left A packed array such as one produced by pack() 4204 * @param right A packed array such as one produced by pack() 4205 * @return The boolean true if left and right overlap at all, or false if they lack any intersecting area 4206 */ 4207 public static boolean intersects(short[] left, short[] right) 4208 { 4209 if(left.length == 0 || right.length == 0) 4210 return false; 4211 boolean onLeft = false, onRight = false; 4212 int idx = 0, elemLeft = 0, elemRight = 0, totalLeft = 0, totalRight = 0; 4213 while ((elemLeft < left.length && elemRight < right.length) && idx <= 0xffff) { 4214 if(totalLeft <= idx) { 4215 totalLeft += left[elemLeft] & 0xffff; 4216 } 4217 if(totalRight <= idx) { 4218 totalRight += right[elemRight] & 0xffff; 4219 } 4220 // 300, 5, 6, 8, 2, 4 4221 // 290, 12, 9, 1 4222 // = 4223 // 300, 2, 9, 1 4224 // 300 off, 2 on, 9 off, 1 on 4225 if(totalLeft < totalRight) 4226 { 4227 onLeft = !onLeft; 4228 idx = totalLeft; 4229 if(onLeft && onRight) return true; 4230 elemLeft++; 4231 } 4232 else if(totalLeft == totalRight) 4233 { 4234 onLeft = !onLeft; 4235 onRight = !onRight; 4236 idx = totalLeft; 4237 if(onLeft && onRight) return true; 4238 elemLeft++; 4239 elemRight++; 4240 4241 } 4242 else 4243 { 4244 onRight = !onRight; 4245 idx = totalRight; 4246 if(onLeft && onRight) return true; 4247 elemRight++; 4248 } 4249 } 4250 return false; 4251 } 4252 4253 /** 4254 * Given one packed short array, this produces a packed short array that is the exact opposite of the one passed in, 4255 * that is, every "on" cell becomes "off" and every "off" cell becomes "on", including cells that were "off" because 4256 * they were beyond the boundaries of the original 2D array passed to pack() or a similar method. This method does 4257 * not do any unpacking (which can be somewhat computationally expensive), and actually requires among the lowest 4258 * amounts of computation to get a result of any methods in CoordPacker. However, because it will cause cells to be 4259 * considered "on" that would cause an exception if directly converted to x,y positions and accessed in the source 4260 * 2D array, this method should primarily be used in conjunction with operations such as intersectPacked(), or have 4261 * the checking for boundaries handled internally by unpack() or related methods such as unpackMultiDouble(). 4262 * @param original A packed array such as one produced by pack() 4263 * @return A packed array that encodes "on" all cells that were "off" in original 4264 */ 4265 public static short[] negatePacked(short[] original) { 4266 if (original.length <= 1) { 4267 return ALL_ON; 4268 } 4269 if (original[0] == 0) { 4270 short[] copy = new short[original.length - 2]; 4271 System.arraycopy(original, 1, copy, 0, original.length - 2); 4272 //copy[original.length - 3] = (short) (0xFFFF - covered(copy)); 4273 return copy; 4274 } 4275 short[] copy = new short[original.length + 2]; 4276 copy[0] = 0; 4277 System.arraycopy(original, 0, copy, 1, original.length); 4278 copy[copy.length - 1] = (short) (0xFFFF - covered(copy)); 4279 return copy; 4280 } 4281 4282 /** 4283 * Given two packed short arrays, left and right, this produces a packed short array that encodes "on" for any cell 4284 * that was "on" in left but "off" in right, and encodes "off" for cells that were "on" in right or "off" in left. 4285 * This method does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly 4286 * preferred when finding a region of one packed array that is not contained in another packed array. 4287 * @param left A packed array such as one produced by pack() 4288 * @param right A packed array such as one produced by pack() 4289 * @return A packed array that encodes "on" for all cells that were "on" in left and "off" in right 4290 */ 4291 public static short[] differencePacked(short[] left, short[] right) 4292 { 4293 if(left.length <= 1) 4294 return ALL_WALL; 4295 if(right.length <= 1) 4296 return left; 4297 ShortVLA packing = new ShortVLA(64); 4298 boolean on = false, onLeft = false, onRight = false; 4299 int idx = 0, skip = 0, elemLeft = 0, elemRight = 0, totalLeft = 0, totalRight = 0; 4300 while ((elemLeft < left.length || elemRight < right.length) && idx <= 0xffff) { 4301 if (elemLeft >= left.length) { 4302 totalLeft = 0x20000; 4303 onLeft = false; 4304 } 4305 else if(totalLeft <= idx) { 4306 totalLeft += left[elemLeft] & 0xffff; 4307 } 4308 if(elemRight >= right.length) { 4309 totalRight = 0x20000; 4310 onRight = false; 4311 } 4312 else if(totalRight <= idx) { 4313 totalRight += right[elemRight] & 0xffff; 4314 } 4315 if(totalLeft < totalRight) 4316 { 4317 onLeft = !onLeft; 4318 skip += totalLeft - idx; 4319 idx = totalLeft; 4320 if(on != (onLeft && !onRight)) { 4321 packing.add((short) skip); 4322 skip = 0; 4323 on = !on; 4324 } 4325 elemLeft++; 4326 } 4327 else if(totalLeft == totalRight) 4328 { 4329 onLeft = !onLeft; 4330 onRight = !onRight; 4331 skip += totalLeft - idx; 4332 idx = totalLeft; 4333 if(on != (onLeft && !onRight)) { 4334 packing.add((short) skip); 4335 skip = 0; 4336 on = !on; 4337 } 4338 elemLeft++; 4339 elemRight++; 4340 4341 } 4342 else 4343 { 4344 onRight = !onRight; 4345 skip += totalRight - idx; 4346 idx = totalRight; 4347 if(on != (onLeft && !onRight)) { 4348 packing.add((short) skip); 4349 skip = 0; 4350 on = !on; 4351 } 4352 elemRight++; 4353 } 4354 } 4355 return packing.toArray(); 4356 } 4357 4358 /** 4359 * Given two packed short arrays, left and right, this produces a packed short array that encodes "on" for any cell 4360 * that was "on" only in left or only in right, but not a cell that was "off" in both or "on" in both. This method 4361 * does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly preferred 4362 * when performing an exclusive-or operation on two pieces of packed data. 4363 * <br> 4364 * Could more-correctly be called exclusiveDisjunctionPacked to match the other terms, but... seriously? 4365 * @param left A packed array such as one produced by pack() 4366 * @param right A packed array such as one produced by pack() 4367 * @return A packed array that encodes "on" for all cells such that left's cell ^ right's cell returns true 4368 */ 4369 public static short[] xorPacked(short[] left, short[] right) 4370 { 4371 if(left.length == 0) 4372 return right; 4373 if(right.length == 0) 4374 return left; 4375 ShortVLA packing = new ShortVLA(64); 4376 boolean on = false, onLeft = false, onRight = false; 4377 int idx = 0, skip = 0, elemLeft = 0, elemRight = 0, totalLeft = 0, totalRight = 0; 4378 while ((elemLeft < left.length || elemRight < right.length) && idx <= 0xffff) { 4379 if (elemLeft >= left.length) { 4380 totalLeft = 0x20000; 4381 onLeft = false; 4382 } 4383 else if(totalLeft <= idx) { 4384 totalLeft += left[elemLeft] & 0xffff; 4385 } 4386 if(elemRight >= right.length) { 4387 totalRight = 0x20000; 4388 onRight = false; 4389 } 4390 else if(totalRight <= idx) { 4391 totalRight += right[elemRight] & 0xffff; 4392 } 4393 // 300, 5, 6, 8, 2, 4 4394 // 290, 12, 9, 1 4395 // = 4396 // 290, 15, 6, 8, 2, 4 4397 // 290 off in both, 10 in right, 2 in both, 3 in left, 6 off in both, 1 on in both, 7 on in left, 2 off in 4398 // both, 4 on in left 4399 if(totalLeft < totalRight) 4400 { 4401 onLeft = !onLeft; 4402 skip += totalLeft - idx; 4403 idx = totalLeft; 4404 if(on != (onLeft ^ onRight)) { 4405 packing.add((short) skip); 4406 skip = 0; 4407 on = !on; 4408 } 4409 elemLeft++; 4410 } 4411 else if(totalLeft == totalRight) 4412 { 4413 onLeft = !onLeft; 4414 onRight = !onRight; 4415 skip += totalLeft - idx; 4416 idx = totalLeft; 4417 if(on != (onLeft ^ onRight)) { 4418 packing.add((short) skip); 4419 skip = 0; 4420 on = !on; 4421 } 4422 elemLeft++; 4423 elemRight++; 4424 4425 } 4426 else 4427 { 4428 onRight = !onRight; 4429 skip += totalRight - idx; 4430 idx = totalRight; 4431 if(on != (onLeft ^ onRight)) { 4432 packing.add((short) skip); 4433 skip = 0; 4434 on = !on; 4435 } 4436 elemRight++; 4437 } 4438 } 4439 return packing.toArray(); 4440 } 4441 4442 /** 4443 * Returns a new packed short[] containing the Hilbert distance hilbert as "on", and all other cells "off". 4444 * Much more efficient than packSeveral called with only one argument. 4445 * @param hilbert a Hilbert distance that will be encoded as "on" 4446 * @return the point given to this encoded as "on" in a packed short array 4447 */ 4448 public static short[] packOne(int hilbert) 4449 { 4450 return new short[]{(short) hilbert, 1}; 4451 } 4452 /** 4453 * Returns a new packed short[] containing the Coord point as "on", and all other cells "off". 4454 * Much more efficient than packSeveral called with only one argument. 4455 * @param point a Coord that will be encoded as "on" 4456 * @return the point given to this encoded as "on" in a packed short array 4457 */ 4458 public static short[] packOne(Coord point) 4459 { 4460 return new short[]{(short) coordToHilbert(point), 1}; 4461 } 4462 /** 4463 * Returns a new packed short[] containing the given x,y cell as "on", and all other cells "off". 4464 * Much more efficient than packSeveral called with only one argument. 4465 * @param x the x component of the point that will be encoded as "on" 4466 * @param y the y component of the point that will be encoded as "on" 4467 * @return the point given to this encoded as "on" in a packed short array 4468 */ 4469 public static short[] packOne(int x, int y) 4470 { 4471 return new short[]{(short) posToHilbert(x, y), 1}; 4472 } 4473 /** 4474 * Returns a new packed short[] containing the Hilbert distances in hilbert as "on" cells, and all other cells "off" 4475 * @param hilbert a vararg or array of Hilbert distances that will be encoded as "on" 4476 * @return the points given to this encoded as "on" in a packed short array 4477 */ 4478 public static short[] packSeveral(int... hilbert) 4479 { 4480 if(hilbert == null || hilbert.length == 0) 4481 return ALL_WALL; 4482 Arrays.sort(hilbert); 4483 ShortVLA vla = new ShortVLA(128); 4484 int current, past = hilbert[0], skip = 0; 4485 4486 vla.add((short)hilbert[0]); 4487 for (int i = 1; i < hilbert.length; i++) { 4488 current = hilbert[i]; 4489 if (current - past > 1) 4490 { 4491 vla.add((short) (skip+1)); 4492 skip = 0; 4493 vla.add((short)(current - past - 1)); 4494 } 4495 else if(current != past) 4496 skip++; 4497 past = current; 4498 } 4499 vla.add((short)(skip+1)); 4500 return vla.toArray(); 4501 } 4502 4503 /** 4504 * Returns a new packed short[] containing the Coords in points as "on" cells, and all other cells "off" 4505 * @param points a vararg or array of Coords that will be encoded as "on" 4506 * @return the points given to this encoded as "on" in a packed short array 4507 */ 4508 public static short[] packSeveral(Coord... points) 4509 { 4510 if(points == null || points.length == 0) 4511 return ALL_WALL; 4512 int[] hilbert = new int[points.length]; 4513 for (int i = 0; i < points.length; i++) { 4514 if(points[i] == null) return ALL_WALL; 4515 hilbert[i] = coordToHilbert(points[i]); 4516 } 4517 4518 Arrays.sort(hilbert); 4519 ShortVLA vla = new ShortVLA(128); 4520 int current, past = hilbert[0], skip = 0; 4521 4522 vla.add((short)hilbert[0]); 4523 for (int i = 1; i < hilbert.length; i++) { 4524 current = hilbert[i]; 4525 if (current - past > 1) 4526 { 4527 vla.add((short) (skip+1)); 4528 skip = 0; 4529 vla.add((short)(current - past - 1)); 4530 } 4531 else if(current != past) 4532 skip++; 4533 past = current; 4534 } 4535 vla.add((short)(skip+1)); 4536 return vla.toArray(); 4537 } 4538 /** 4539 * Returns a new packed short[] containing the Coords in points as "on" cells, and all other cells "off" 4540 * @param points a Collection of Coords that will be encoded as "on" 4541 * @return the points given to this encoded as "on" in a packed short array 4542 */ 4543 public static short[] packSeveral(Collection<Coord> points) 4544 { 4545 if(points == null || points.isEmpty()) 4546 return ALL_WALL; 4547 int sz = points.size(); 4548 int[] hilbert = new int[sz]; 4549 int idx = 0; 4550 for(Coord c : points) 4551 { 4552 if(c == null) return ALL_WALL; 4553 hilbert[idx++] = coordToHilbert(c); 4554 } 4555 Arrays.sort(hilbert); 4556 ShortVLA vla = new ShortVLA(128); 4557 int current, past = hilbert[0], skip = 0; 4558 4559 vla.add((short)hilbert[0]); 4560 for (int i = 1; i < hilbert.length; i++) { 4561 current = hilbert[i]; 4562 if (current - past > 1) 4563 { 4564 vla.add((short) (skip+1)); 4565 skip = 0; 4566 vla.add((short)(current - past - 1)); 4567 } 4568 else if(current != past) 4569 skip++; 4570 past = current; 4571 } 4572 vla.add((short)(skip+1)); 4573 return vla.toArray(); 4574 } 4575 /** 4576 * Given one packed short array, original, and a Hilbert Curve index, hilbert, this produces a packed short array 4577 * that encodes "on" for any cell that was "on" in original, always encodes "on" for the position referred 4578 * to by hilbert, and encodes "off" for cells that were "off" in original and are not the cell hilbert refers to. 4579 * This method does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly 4580 * preferred when finding a region of one packed array that is not contained in another packed array. 4581 * @param original A packed array such as one produced by pack() 4582 * @param hilbert A Hilbert Curve index that should be inserted into the result 4583 * @return A packed array that encodes "on" for all cells that are "on" in original or correspond to hilbert 4584 */ 4585 public static short[] insertPacked(short[] original, short hilbert) 4586 { 4587 return unionPacked(original, new short[]{hilbert, 1}); 4588 } 4589 /** 4590 * Given one packed short array, original, and a position as x,y numbers, this produces a packed short array 4591 * that encodes "on" for any cell that was "on" in original, always encodes "on" for the position referred 4592 * to by x and y, and encodes "off" for cells that were "off" in original and are not the cell x and y refer to. 4593 * This method does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly 4594 * preferred when finding a region of one packed array that is not contained in another packed array. 4595 * @param original A packed array such as one produced by pack() 4596 * @param x The x position at which to insert the "on" cell 4597 * @param y The y position at which to insert the "on" cell 4598 * @return A packed array that encodes "on" for all cells that are "on" in original or correspond to x,y 4599 */ 4600 public static short[] insertPacked(short[] original, int x, int y) 4601 { 4602 return unionPacked(original, new short[]{(short)posToHilbert(x, y), 1}); 4603 } 4604 4605 /** 4606 * Given one packed short array, original, and a number of Hilbert Curve indices, hilbert, this produces a packed 4607 * short array that encodes "on" for any cell that was "on" in original, always encodes "on" for the position 4608 * referred to by any element of hilbert, and encodes "off" for cells that were "off" in original and are not in any 4609 * cell hilbert refers to. This method does not do any unpacking (which can be somewhat computationally expensive) 4610 * and so should be strongly preferred when you have several Hilbert Curve indices, possibly nearby each other but 4611 * just as possibly not, that you need inserted into a packed array. 4612 * @param original A packed array such as one produced by pack() 4613 * @param hilbert an array or vararg of Hilbert Curve indices that should be inserted into the result 4614 * @return A packed array that encodes "on" for all cells that are "on" in original or are contained in hilbert 4615 */ 4616 public static short[] insertSeveralPacked(short[] original, int... hilbert) 4617 { 4618 return unionPacked(original, packSeveral(hilbert)); 4619 } 4620 /** 4621 * Given one packed short array, original, and a number of Coords, points, this produces a packed 4622 * short array that encodes "on" for any cell that was "on" in original, always encodes "on" for the position 4623 * referred to by any element of points, and encodes "off" for cells that were "off" in original and are not in any 4624 * cell points refers to. This method does not do any unpacking (which can be somewhat computationally expensive) 4625 * and so should be strongly preferred when you have several Coords, possibly nearby each other but 4626 * just as possibly not, that you need inserted into a packed array. 4627 * @param original A packed array such as one produced by pack() 4628 * @param points an array or vararg of Coords that should be inserted into the result 4629 * @return A packed array that encodes "on" for all cells that are "on" in original or are contained in hilbert 4630 */ 4631 public static short[] insertSeveralPacked(short[] original, Coord... points) 4632 { 4633 return unionPacked(original, packSeveral(points)); 4634 } 4635 /** 4636 * Given one packed short array, original, and a Collection of Coords, points, this produces a packed 4637 * short array that encodes "on" for any cell that was "on" in original, always encodes "on" for the position 4638 * referred to by any element of points, and encodes "off" for cells that were "off" in original and are not in any 4639 * cell points refers to. This method does not do any unpacking (which can be somewhat computationally expensive) 4640 * and so should be strongly preferred when you have several Coords, possibly nearby each other but 4641 * just as possibly not, that you need inserted into a packed array. 4642 * @param original A packed array such as one produced by pack() 4643 * @param points an array or vararg of Coords that should be inserted into the result 4644 * @return A packed array that encodes "on" for all cells that are "on" in original or are contained in hilbert 4645 */ 4646 public static short[] insertSeveralPacked(short[] original, Collection<Coord> points) 4647 { 4648 return unionPacked(original, packSeveral(points)); 4649 } 4650 /** 4651 * Given one packed short array, original, and a Hilbert Curve index, hilbert, this produces a packed short array 4652 * that encodes "on" for any cell that was "on" in original, unless it was the position referred to by hilbert, and 4653 * encodes "off" for cells that were "off" in original or are the cell hilbert refers to. 4654 * This method does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly 4655 * preferred when finding a region of one packed array that is not contained in another packed array. 4656 * @param original A packed array such as one produced by pack() 4657 * @param hilbert A Hilbert Curve index that should be removed from the result 4658 * @return A packed array that encodes "on" for all cells that are "on" in original and don't correspond to hilbert 4659 */ 4660 public static short[] removePacked(short[] original, short hilbert) 4661 { 4662 return differencePacked(original, new short[]{hilbert, 1}); 4663 } 4664 /** 4665 * Given one packed short array, original, and a position as x,y numbers, this produces a packed short array that 4666 * encodes "on" for any cell that was "on" in original, unless it was the position referred to by x and y, and 4667 * encodes "off" for cells that were "off" in original or are the cell x and y refer to. 4668 * This method does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly 4669 * preferred when finding a region of one packed array that is not contained in another packed array. 4670 * @param original A packed array such as one produced by pack() 4671 * @param x The x position at which to remove any "on" cell 4672 * @param y The y position at which to remove any "on" cell 4673 * @return A packed array that encodes "on" for all cells that are "on" in original and don't correspond to x,y 4674 */ 4675 public static short[] removePacked(short[] original, int x, int y) 4676 { 4677 int dist = posToHilbert(x, y); 4678 return differencePacked(original, new short[]{(short)dist, 1}); 4679 } 4680 4681 /** 4682 * Given one packed short array, original, and a number of Hilbert Curve indices, hilbert, this produces a packed 4683 * short array that encodes "on" for any cell that was "on" in original, unless it was a position referred to by 4684 * hilbert, and encodes "off" for cells that were "off" in original and are a cell hilbert refers to. This method 4685 * does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly preferred 4686 * when you have several Hilbert Curve indices, possibly nearby each other but just as possibly not, that you need 4687 * removed from a packed array. 4688 * @param original A packed array such as one produced by pack() 4689 * @param hilbert an array or vararg of Hilbert Curve indices that should be inserted into the result 4690 * @return A packed array that encodes "on" for all cells that are "on" in original and aren't contained in hilbert 4691 */ 4692 public static short[] removeSeveralPacked(short[] original, int... hilbert) 4693 { 4694 return differencePacked(original, packSeveral(hilbert)); 4695 } 4696 4697 /** 4698 * Given one packed short array, original, and a number of Coords, points, this produces a packed short 4699 * array that encodes "on" for any cell that was "on" in original, unless it was a position referred to by an element 4700 * in points, and encodes "off" for cells that were "off" in original and are a cell points refers to. This method 4701 * does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly preferred 4702 * when you have several Hilbert Curve indices, possibly nearby each other but just as possibly not, that you need 4703 * removed from a packed array. 4704 * @param original A packed array such as one produced by pack() 4705 * @param points an array or vararg of Coords that should be removed from the result 4706 * @return A packed array that encodes "on" for all cells that are "on" in original and aren't contained in points 4707 */ 4708 public static short[] removeSeveralPacked(short[] original, Coord... points) 4709 { 4710 return differencePacked(original, packSeveral(points)); 4711 } 4712 4713 /** 4714 * Given one packed short array, original, and a number of Coords, points, this produces a packed short 4715 * array that encodes "on" for any cell that was "on" in original, unless it was a position referred to by an element 4716 * in points, and encodes "off" for cells that were "off" in original and are a cell points refers to. This method 4717 * does not do any unpacking (which can be somewhat computationally expensive) and so should be strongly preferred 4718 * when you have several Hilbert Curve indices, possibly nearby each other but just as possibly not, that you need 4719 * removed from a packed array. 4720 * @param original A packed array such as one produced by pack() 4721 * @param points a Collection of Coords that should be removed from the result 4722 * @return A packed array that encodes "on" for all cells that are "on" in original and aren't contained in points 4723 */ 4724 public static short[] removeSeveralPacked(short[] original, Collection<Coord> points) 4725 { 4726 return differencePacked(original, packSeveral(points)); 4727 } 4728 4729 /** 4730 * Given a packed data array that encodes multiple unconnected "on" areas, this finds each isolated area (areas that 4731 * are only adjacent diagonally are considered separate from each other) and returns it as an element in an 4732 * ArrayList of short[], with one short[] array per isolated area. Useful when you have, for example, all the rooms 4733 * in a dungeon with their connecting corridors removed, but want to separate the rooms. You can get the 4734 * aforementioned data assuming a bare dungeon called map with WIDTH and HEIGHT constants using: 4735 * <br> 4736 * {@code short[] floors = pack(map, '.'), 4737 * rooms = flood(floors, retract(floors, 1, WIDTH, HEIGHT, true), 2, false), 4738 * corridors = differencePacked(floors, rooms), 4739 * doors = intersectPacked(rooms, fringe(corridors, 1, WIDTH, HEIGHT, false));} 4740 * <br> 4741 * You can then get all rooms as separate regions with {@code List<short[]> apart = split(rooms);}, or substitute 4742 * {@code split(corridors)} to get the corridors. The room-finding technique works by shrinking floors by a radius 4743 * of 1 (8-way), which causes thin areas like corridors of 2 or less width to be removed, then flood-filling the 4744 * floors out from the area that produces by 2 cells (4-way this time) to restore the original size of non-corridor 4745 * areas (plus some extra to ensure odd shapes are kept). Corridors are obtained by removing the rooms from floors. 4746 * The example code also gets the doors (which overlap with rooms, not corridors) by finding where the a room and a 4747 * corridor are adjacent. This technique is used with some enhancements in the RoomFinder class. 4748 * @see squidpony.squidgrid.mapping.RoomFinder for a class that uses this technique without exposing CoordPacker 4749 * @param packed a packed data array that probably encodes multiple unconnected "on" areas 4750 * @return an ArrayList of short[] containing each unconnected area from packed as a short[] element 4751 */ 4752 public static ArrayList<short[]> split(short[] packed) 4753 { 4754 ArrayList<short[]> arrays = new ArrayList<>(32); 4755 short[] remaining = new short[packed.length]; 4756 System.arraycopy(packed, 0, remaining, 0, packed.length); 4757 while (remaining.length > 1) { 4758 boolean on = false; 4759 int idx = 0; 4760 for (int p = 0; p < remaining.length; p++, on = true) { 4761 if (on) { 4762 short[] area = flood(packed, packOne((short) idx), 512, false); 4763 arrays.add(area); 4764 remaining = differencePacked(remaining, area); 4765 break; 4766 } 4767 idx += remaining[p] & 0xffff; 4768 } 4769 } 4770 return arrays; 4771 } 4772 4773 public static short[] removeIsolated(short[] packed) 4774 { 4775 short[] remaining = new short[packed.length], viable = new short[packed.length]; 4776 System.arraycopy(packed, 0, remaining, 0, packed.length); 4777 System.arraycopy(packed, 0, viable, 0, packed.length); 4778 while (remaining.length > 1) { 4779 boolean on = false; 4780 int idx = 0; 4781 for (int p = 0; p < remaining.length; p++, on = true) { 4782 if (on) { 4783 short[] area = flood(packed, packOne((short) idx), 512, false); 4784 if(count(area) <= 4) 4785 viable = differencePacked(viable, area); 4786 remaining = differencePacked(remaining, area); 4787 break; 4788 } 4789 idx += remaining[p] & 0xffff; 4790 } 4791 } 4792 return viable; 4793 } 4794 /** 4795 * Gets a random subset of positions that are "on" in the given packed array, without unpacking it, and returns 4796 * them as a Coord[]. Random numbers are generated by the rng parameter. 4797 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 4798 * not be null (this method does not check). 4799 * @param fraction the likelihood to return one of the "on" cells, from 0.0 to 1.0 4800 * @param rng the random number generator used to decide random factors. 4801 * @return a Coord[], ordered by distance along the Hilbert Curve, corresponding to a random section of "on" cells 4802 * in packed that has a random length approximately equal to the count of all "on" cells in packed times fraction. 4803 */ 4804 public static Coord[] randomSample(short[] packed, double fraction, IRNG rng) 4805 { 4806 int counted = count(packed); 4807 ShortVLA vla = new ShortVLA((int)(counted * fraction) + 1); 4808 boolean on = false; 4809 int idx = 0; 4810 for(int p = 0; p < packed.length; p++, on = !on) { 4811 if (on) { 4812 for (int i = idx; i < idx + (packed[p] & 0xffff); i++) { 4813 if(rng.nextDouble() < fraction) 4814 vla.add((short)i); 4815 } 4816 } 4817 idx += packed[p] & 0xffff; 4818 } 4819 int[] distances = vla.asInts(); 4820 Coord[] cs = new Coord[distances.length]; 4821 for (int i = 0; i < distances.length; i++) { 4822 cs[i] = Coord.get(hilbertX[distances[i]], hilbertY[distances[i]]); 4823 } 4824 return cs; 4825 } 4826 /** 4827 * Gets a single randomly chosen position that is "on" in the given packed array, without unpacking it, and returns 4828 * it as a Coord or returns null of the array is empty. Random numbers are generated by the rng parameter. 4829 * More efficient in most cases than randomSample(), and will always return at least one Coord for non-empty arrays. 4830 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 4831 * not be null (this method does not check). 4832 * @param rng the random number generator used to decide random factors 4833 * @return a Coord corresponding to a random "on" cell in packed, or the Coord (-1, -1) if packed is empty 4834 */ 4835 public static Coord singleRandom(short[] packed, IRNG rng) 4836 { 4837 int counted = count(packed); 4838 if(counted == 0) 4839 return Coord.get(-1,-1); 4840 int r = rng.nextInt(counted); 4841 int c = 0, idx = 0; 4842 boolean on = false; 4843 for (int i = 0; i < packed.length; on = !on, idx += packed[i] & 0xFFFF, i++) { 4844 if (on) { 4845 if(c + (packed[i] & 0xFFFF) > r) 4846 { 4847 idx += r - c; 4848 return Coord.get(hilbertX[idx], hilbertY[idx]); 4849 } 4850 c += packed[i] & 0xFFFF; 4851 } 4852 } 4853 return Coord.get(-1,-1); 4854 4855 } 4856 /** 4857 * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements. 4858 * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative). 4859 * 4860 * @param start the start of the range of numbers to potentially use (inclusive) 4861 * @param end the end of the range of numbers to potentially use (exclusive) 4862 * @param count the total number of elements to use; will be less if the range is smaller than count 4863 * @return an int array that contains at most one of each number in the range 4864 */ 4865 private static int[] randomRange(IRNG random, int start, int end, int count) { 4866 if (end <= start || start < 0) 4867 return new int[0]; 4868 4869 int n = end - start; 4870 final int[] data = new int[n]; 4871 4872 for (int e = start, i = 0; e < end; e++) { 4873 data[i++] = e; 4874 } 4875 4876 for (int i = 0; i < n - 1; i++) { 4877 final int r = i + random.nextInt(n - i), t = data[r]; 4878 data[r] = data[i]; 4879 data[i] = t; 4880 } 4881 final int[] array = new int[Math.min(count, n)]; 4882 System.arraycopy(data, 0, array, 0, Math.min(count, n)); 4883 return array; 4884 } 4885 4886 /** 4887 * Gets a fixed number of randomly chosen positions that are "on" in the given packed array, without unpacking it, 4888 * and returns a List of Coord with a count equal to size (or less if there aren't enough "on" cells). Random 4889 * numbers are generated by the rng parameter. This orders the returned array in the order the Hilbert Curve takes, 4890 * and you may want to call {@link IRNG#shuffleInPlace(List)} with it as a parameter to randomize the order. 4891 * 4892 * @param packed a short[] returned by pack() or one of the sub-arrays in what is returned by packMulti(); must 4893 * not be null (this method does not check). 4894 * @param size the desired size of the List to return; may be smaller if there aren't enough elements 4895 * @param rng the random number generator used to decide random factors. 4896 * @return a List of Coords, ordered by distance along the Hilbert Curve, corresponding to randomly "on" cells in 4897 * packed, with a length equal to the smaller of size and the count of all "on" cells in packed 4898 */ 4899 public static ArrayList<Coord> randomPortion(short[] packed, int size, IRNG rng) 4900 { 4901 int counted = count(packed); 4902 ArrayList<Coord> coords = new ArrayList<>(Math.min(counted, size)); 4903 if(counted == 0 || size == 0) 4904 return coords; 4905 int[] data = randomRange(rng, 0, counted, Math.min(counted, size)); 4906 Arrays.sort(data); 4907 int r = data[0]; 4908 int c = 0, idx = 0; 4909 boolean on = false; 4910 for (int i = 0, ri = 0; i < packed.length; on = !on, idx += packed[i] & 0xffff, i++) { 4911 if (on) { 4912 while (c + (packed[i] & 0xffff) > r) 4913 { 4914 int n = idx + r - c; 4915 coords.add(Coord.get(hilbertX[n], hilbertY[n])); 4916 if(++ri < data.length) 4917 r = data[ri]; 4918 else 4919 return coords; 4920 } 4921 c += packed[i] & 0xffff; 4922 } 4923 } 4924 return coords; 4925 } 4926 4927 4928 /** 4929 * Takes multiple pieces of packed data as short[], encoded by pack() or another similar method of this class, and 4930 * generates a 2D int array with the specified width and height and a starting value of 0 for all elements, then 4931 * where every occurrence of a cell as "on" in a piece of packed data increments the cell's value in the returned 4932 * array. Width and height do not technically need to match the dimensions of the original 2D array, but under most 4933 * circumstances where they don't match, the data produced will be junk. 4934 * @param width the width of the 2D array that will be returned; should match the unpacked array's width 4935 * @param height the height of the 2D array that will be returned; should match the unpacked array's height 4936 * @param many a vararg or array of short[] encoded by calling one of this class' packing methods on a 2D array 4937 * @return an int[][] storing at least 0 for all cells, plus 1 for every element of packed that has that cell "on" 4938 */ 4939 public static int[][] sumMany(int width, int height, short[] ... many) 4940 { 4941 if(many == null) 4942 throw new ArrayIndexOutOfBoundsException("CoordPacker.sumMany() must be given a non-null many arg"); 4943 int[][] unpacked = new int[width][height]; 4944 for (int e = 0; e < many.length; e++) { 4945 boolean on = false; 4946 int idx = 0; 4947 short x, y; 4948 for(int p = 0; p < many[e].length; p++, on = !on) { 4949 if (on) { 4950 for (int toSkip = idx + (many[e][p] & 0xffff); idx < toSkip && idx < 0x10000; idx++) { 4951 x = hilbertX[idx]; 4952 y = hilbertY[idx]; 4953 if(x >= width || y >= height) 4954 continue; 4955 unpacked[x][y]++; 4956 } 4957 } else { 4958 idx += many[e][p] & 0xffff; 4959 } 4960 } 4961 } 4962 return unpacked; 4963 } 4964 4965 /** 4966 * Quick utility method for printing packed data as a grid of 1 (on) and/or 0 (off). Useful primarily for debugging. 4967 * @param packed a packed short[] such as one produced by pack() 4968 * @param width the width of the packed 2D array 4969 * @param height the height of the packed 2D array 4970 */ 4971 public static void printPacked(short[] packed, int width, int height) 4972 { 4973 boolean[][] unpacked = unpack(packed, width, height); 4974 for (int y = 0; y < height; y++) { 4975 for (int x = 0; x < width; x++) { 4976 System.out.print(unpacked[x][y] ? '1' : '0'); 4977 } 4978 System.out.println(); 4979 } 4980 } 4981 4982 public static void printCompressedData(short[] packed) 4983 { 4984 if(packed == null || packed.length == 0) 4985 { 4986 System.out.println("[]"); 4987 return; 4988 } 4989 System.out.print("[" + packed[0]); 4990 for (int i = 1; i < packed.length; i++) { 4991 System.out.print(", " + packed[i]); 4992 } 4993 System.out.println("]"); 4994 } 4995 4996 /** 4997 * Encodes a short array of packed data as a (larger, more memory-hungry) ASCII string, which can be decoded using 4998 * CoordPacker.decodeASCII() . Uses 64 printable chars, from '?' (ASCII 63) to '~' (ASCII 126). 4999 * @param packed a packed data item produced by pack() or some other method from this class. 5000 * @return a printable String, which can be decoded with CoordPacker.decodeASCII() 5001 */ 5002 public static String encodeASCII(short[] packed) 5003 { 5004 int len = packed.length * 3; 5005 char[] chars = new char[len]; 5006 for (int i = 0, c = 0; c < len; i++, c += 3) { 5007 chars[c] = (char)((packed[i] & 31) + 63); 5008 chars[c+1] = (char)(((packed[i] >> 5) & 31) + 63); 5009 chars[c+2] = (char)(((packed[i] >>> 10) & 63) + 63); 5010 } 5011 return new String(chars); 5012 } 5013 /** 5014 * Given a String specifically produced by CoordPacker.encodeASCII(), this will produce a packed data array. 5015 * @param text a String produced by CoordPacker.encodeASCII(); this will almost certainly fail on other strings. 5016 * @return the packed data as a short array that was originally used to encode text 5017 */ 5018 public static short[] decodeASCII(String text) 5019 { 5020 int len = text.length(); 5021 if(len % 3 != 0) 5022 return ALL_WALL; 5023 char[] chars = text.toCharArray(); 5024 short[] packed = new short[len / 3]; 5025 for (int c = 0, i = 0; c < len; i++, c += 3) { 5026 packed[i] = (short)(((chars[c] - 63) & 31) | (((chars[c+1] - 63) & 31) << 5) | (((chars[c+2] - 63) & 63) << 10)); 5027 } 5028 return packed; 5029 } 5030 5031 /** 5032 * Encodes a short array of packed data as a (larger, slightly more memory-hungry) Unicode string using only Braille 5033 * characters, which can be decoded using CoordPacker.decodeBraille(). Uses 256 semi-printable chars, from 0x2800 5034 * to 0x28FF, which allows UTF-8 encoding (and some other encodings) to more efficiently store the data. These are 5035 * only semi-printable because many fonts do not support Braille, and 0x2800 is sometimes printed equivalently to a 5036 * space char (or sometimes as 8 small dots or open circles, which is preferable). Braille was chosen because it's 5037 * available as a full Unicode block of 256 characters with no gaps or chars that require special treatment, like 5038 * newlines and carriage returns. 5039 * @param packed a packed data item produced by pack() or some other method from this class. 5040 * @return a semi-printable String, which can be decoded with CoordPacker.decodeBraille() 5041 */ 5042 public static String encodeBraille(short[] packed) 5043 { 5044 int len = packed.length * 2; 5045 char[] chars = new char[len]; 5046 for (int i = 0, c = 0; c < len; i++, c += 2) { 5047 chars[c] = (char) ((packed[i] & 0xff) | 0x2800); 5048 chars[c+1] = (char)((packed[i] >>> 8) | 0x2800); 5049 } 5050 return new String(chars); 5051 } 5052 /** 5053 * Given a String specifically produced by CoordPacker.encodeBraille(), this will produce a packed data array. 5054 * Uses 256 semi-printable chars, from 0x2800 to 0x28FF, which allows UTF-8 encoding (and some other encodings) to 5055 * more efficiently store the data. These are only semi-printable because many fonts do not support Braille, and 5056 * 0x2800 is sometimes printed equivalently to a space char (or sometimes as 8 small dots or open circles, which is 5057 * preferable). Braille was chosen because it's available as a full Unicode block of 256 characters with no gaps or 5058 * chars that require special treatment, like newlines and carriage returns. 5059 * @param text a String produced by CoordPacker.encodeBraille(); this will almost certainly fail on other strings. 5060 * @return the packed data as a short array that was originally used to encode text 5061 */ 5062 public static short[] decodeBraille(String text) 5063 { 5064 int len = text.length(); 5065 if((len & 1) != 0 || len == 0) 5066 return ALL_WALL; 5067 char[] chars = text.toCharArray(); 5068 short[] packed = new short[len >> 1]; 5069 for (int c = 0, i = 0; c < len; i++, c += 2) { 5070 packed[i] = (short)((chars[c] ^ 0x2800) | ((chars[c+1] ^ 0x2800) << 8)); 5071 } 5072 return packed; 5073 } 5074 5075 5076 5077 /** 5078 * Encode a number n as a Gray code; Gray codes have a relation to the Hilbert curve and may be useful. 5079 * Source: http://xn--2-umb.com/15/hilbert , http://aggregate.org/MAGIC/#Gray%20Code%20Conversion 5080 * @param n any int 5081 * @return the gray code for n 5082 */ 5083 public static int grayEncode(int n){ 5084 return n ^ (n >> 1); 5085 } 5086 5087 /** 5088 * Decode a number from a Gray code n; Gray codes have a relation to the Hilbert curve and may be useful. 5089 * Source: http://xn--2-umb.com/15/hilbert , http://aggregate.org/MAGIC/#Gray%20Code%20Conversion 5090 * @param n a gray code, as produced by grayEncode 5091 * @return the decoded int 5092 */ 5093 public static int grayDecode(int n) { 5094 int p = n; 5095 while ((n >>= 1) != 0) 5096 p ^= n; 5097 return p; 5098 } 5099 5100 /** 5101 * Takes an x, y position and returns the length to travel along the 256x256 Hilbert curve to reach that position. 5102 * This assumes x and y are between 0 and 255, inclusive. 5103 * This uses a lookup table for the 256x256 Hilbert Curve, which should make it faster than calculating the 5104 * distance along the Hilbert Curve repeatedly. 5105 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5106 * @param x between 0 and 255 inclusive 5107 * @param y between 0 and 255 inclusive 5108 * @return the distance to travel along the 256x256 Hilbert Curve to get to the given x, y point. 5109 */ 5110 public static int posToHilbert( final int x, final int y ) { 5111 //int dist = posToHilbertNoLUT(x, y); 5112 //return dist; 5113 return hilbertDistances[x + (y << 8)] & 0xffff; 5114 } 5115 /** 5116 * Takes an x, y, z position and returns the length to travel along the 8x8x8 Hilbert curve to reach that 5117 * position. This assumes x, y, and z are between 0 and 7, inclusive. 5118 * This uses a lookup table for the 8x8x8 Hilbert Curve, which should make it faster than calculating the 5119 * distance along the Hilbert Curve repeatedly. 5120 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5121 * @param x between 0 and 7 inclusive 5122 * @param y between 0 and 7 inclusive 5123 * @param z between 0 and 7 inclusive 5124 * @return the distance to travel along the 8x8x8 Hilbert Curve to get to the given x, y, z point. 5125 */ 5126 public static int posToHilbert3D( final int x, final int y, final int z ) { 5127 return hilbert3Distances[x | y << 3 | z << 6]; 5128 } 5129 /** 5130 * Takes an x, y position and returns the length to travel along the 16x16 Moore curve to reach that position. 5131 * This assumes x and y are between 0 and 15, inclusive. 5132 * This uses a lookup table for the 16x16 Moore Curve, which should make it faster than calculating the 5133 * distance along the Moore Curve repeatedly. 5134 * @param x between 0 and 15 inclusive 5135 * @param y between 0 and 15 inclusive 5136 * @return the distance to travel along the 16x16 Moore Curve to get to the given x, y point. 5137 */ 5138 public static int posToMoore( final int x, final int y ) { 5139 return mooreDistances[x + (y << 4)] & 0xff; 5140 } 5141 /* 5142 * Takes an x, y position and returns the length to travel along the 256x256 Hilbert curve to reach that position. 5143 * This assumes x and y are between 0 and 255, inclusive. 5144 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5145 * @param x between 0 and 255 inclusive 5146 * @param y between 0 and 255 inclusive 5147 * @return the distance to travel along the 256x256 Hilbert Curve to get to the given x, y point. 5148 */ 5149 5150 private static int posToHilbertNoLUT( final int x, final int y ) 5151 { 5152 int hilbert = 0, remap = 0xb4, mcode, hcode; 5153 /* 5154 while( block > 0 ) 5155 { 5156 --block; 5157 mcode = ( ( x >> block ) & 1 ) | ( ( ( y >> ( block ) ) & 1 ) << 1); 5158 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5159 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5160 hilbert = ( ( hilbert << 2 ) + hcode ); 5161 } 5162 */ 5163 5164 mcode = ( ( x >> 7 ) & 1 ) | ( ( ( y >> ( 7 ) ) & 1 ) << 1); 5165 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5166 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5167 hilbert = ( (0) + hcode ); 5168 5169 mcode = ( ( x >> 6 ) & 1 ) | ( ( ( y >> ( 6 ) ) & 1 ) << 1); 5170 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5171 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5172 hilbert = ( ( hilbert << 2 ) + hcode ); 5173 5174 mcode = ( ( x >> 5 ) & 1 ) | ( ( ( y >> ( 5 ) ) & 1 ) << 1); 5175 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5176 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5177 hilbert = ( ( hilbert << 2 ) + hcode ); 5178 5179 mcode = ( ( x >> 4 ) & 1 ) | ( ( ( y >> ( 4 ) ) & 1 ) << 1); 5180 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5181 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5182 hilbert = ( ( hilbert << 2 ) + hcode ); 5183 5184 mcode = ( ( x >> 3 ) & 1 ) | ( ( ( y >> ( 3 ) ) & 1 ) << 1); 5185 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5186 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5187 hilbert = ( ( hilbert << 2 ) + hcode ); 5188 5189 mcode = ( ( x >> 2 ) & 1 ) | ( ( ( y >> ( 2 ) ) & 1 ) << 1); 5190 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5191 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5192 hilbert = ( ( hilbert << 2 ) + hcode ); 5193 5194 mcode = ( ( x >> 1 ) & 1 ) | ( ( ( y >> ( 1 ) ) & 1 ) << 1); 5195 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5196 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5197 hilbert = ( ( hilbert << 2 ) + hcode ); 5198 5199 mcode = ( x & 1 ) | ( ( y & 1 ) << 1); 5200 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5201 5202 hilbert = ( ( hilbert << 2 ) + hcode ); 5203 5204 return hilbert; 5205 } 5206 5207 /** 5208 * Takes a position as a Morton code, with interleaved x and y bits and x in the least significant bit, and returns 5209 * the length to travel along the 256x256 Hilbert Curve to reach that position. 5210 * This uses 16 bits of the Morton code and requires that the code is non-negative. 5211 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5212 * @param morton a Morton code that interleaves two 8-bit unsigned numbers, with x as index1 and y as index2. 5213 * @return a distance to travel down the Hilbert Curve to reach the location that can be decoded from morton. 5214 */ 5215 public static int mortonToHilbert( final int morton ) 5216 { 5217 int hilbert = 0; 5218 int remap = 0xb4; 5219 int block = BITS; 5220 while( block > 0 ) 5221 { 5222 block -= 2; 5223 int mcode = ( ( morton >> block ) & 3 ); 5224 int hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5225 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5226 hilbert = ( ( hilbert << 2 ) + hcode ); 5227 } 5228 return hilbert; 5229 } 5230 5231 /** 5232 * Takes a distance to travel along the 256x256 Hilbert curve and returns a Morton code representing the position 5233 * in 2D space that corresponds to that point on the Hilbert Curve; the Morton code will have interleaved x and y 5234 * bits and x in the least significant bit. This uses a lookup table for the 256x256 Hilbert curve, which should 5235 * make it faster than calculating the position repeatedly. 5236 * The parameter hilbert is an int but only 16 unsigned bits are used. 5237 * @param hilbert a distance to travel down the Hilbert Curve 5238 * @return a Morton code that stores x and y interleaved; can be converted to a Coord with other methods. 5239 */ 5240 5241 public static int hilbertToMorton( final int hilbert ) 5242 { 5243 return mortonEncode(hilbertX[hilbert], hilbertY[hilbert]); 5244 } 5245 5246 /** 5247 * Takes a distance to travel along the 256x256 Hilbert curve and returns a Coord representing the position 5248 * in 2D space that corresponds to that point on the Hilbert curve. This uses a lookup table for the 5249 * 256x256 Hilbert curve, which should make it faster than calculating the position repeatedly. 5250 * The parameter hilbert is an int but only 16 unsigned bits are used. 5251 * @param hilbert a distance to travel down the Hilbert Curve 5252 * @return a Coord corresponding to the position in 2D space at the given distance down the Hilbert Curve 5253 */ 5254 public static Coord hilbertToCoord( final int hilbert ) 5255 { 5256 return Coord.get(hilbertX[hilbert], hilbertY[hilbert]); 5257 } 5258 5259 /** 5260 * Takes a distance to travel along the 16x16 Hilbert curve and returns a Coord representing the position 5261 * in 2D space that corresponds to that point on the Hilbert curve. This uses a lookup table for the 5262 * 16x16 Hilbert curve, which should make it faster than calculating the position repeatedly. 5263 * The parameter moore is an int but only 8 unsigned bits are used, and since the Moore Curve loops, it is 5264 * calculated as {@code moore & 255}. 5265 * @param moore a distance to travel down the Moore Curve 5266 * @return a Coord corresponding to the position in 2D space at the given distance down the Hilbert Curve 5267 */ 5268 public static Coord mooreToCoord( final int moore ) 5269 { 5270 return Coord.get(mooreX[moore & 255], mooreY[moore & 255]); 5271 } 5272 5273 5274 /* 5275 * Takes a distance to travel along the 256x256 Hilbert curve and returns a Morton code representing the position 5276 * in 2D space that corresponds to that point on the Hilbert curve; the Morton code will have interleaved x and y 5277 * bits and x in the least significant bit. This variant does not use a lookup table, and is likely slower. 5278 * The parameter hilbert is an int but only 16 unsigned bits are used. 5279 * @param hilbert 5280 * @return 5281 */ 5282 /* 5283 public static int hilbertToMortonNoLUT( final int hilbert ) 5284 { 5285 int morton = 0; 5286 int remap = 0xb4; 5287 int block = BITS; 5288 while( block > 0 ) 5289 { 5290 block -= 2; 5291 int hcode = ( ( hilbert >> block ) & 3 ); 5292 int mcode = ( ( remap >> ( hcode << 1 ) ) & 3 ); 5293 remap ^= ( 0x330000cc >> ( hcode << 3 ) ); 5294 morton = ( ( morton << 2 ) + mcode ); 5295 } 5296 return morton; 5297 } 5298 */ 5299 /* 5300 * Takes a distance to travel along the 256x256 Hilbert curve and returns a Coord representing the position 5301 * in 2D space that corresponds to that point on the Hilbert curve. This variant does not use a lookup table, 5302 * and is likely slower. 5303 * The parameter hilbert is an int but only 16 unsigned bits are used. 5304 * @param hilbert 5305 * @return 5306 */ 5307 /* 5308 private static Coord hilbertToCoordNoLUT( final int hilbert ) 5309 { 5310 int x = 0, y = 0; 5311 int remap = 0xb4; 5312 int block = BITS; 5313 while( block > 0 ) 5314 { 5315 block -= 2; 5316 int hcode = ( ( hilbert >> block ) & 3 ); 5317 int mcode = ( ( remap >> ( hcode << 1 ) ) & 3 ); 5318 remap ^= ( 0x330000cc >> ( hcode << 3 ) ); 5319 x = (x << 1) + (mcode & 1); 5320 y = (y << 1) + ((mcode & 2) >> 1); 5321 } 5322 return Coord.get(x, y); 5323 } 5324 */ 5325 /** 5326 * Takes a position as a Coord called pt and returns the length to travel along the 256x256 Hilbert curve to reach 5327 * that position. 5328 * This assumes pt.x and pt.y are between 0 and 255, inclusive. 5329 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5330 * @param pt a Coord with values between 0 and 255, inclusive 5331 * @return a distance from the start of the 256x256 Hilbert curve to get to the position of pt 5332 */ 5333 public static int coordToHilbert(final Coord pt) 5334 { 5335 return posToHilbert(pt.x, pt.y); 5336 } 5337 5338 /** 5339 * Takes a position as a Coord called pt and returns the length to travel along the 16x16 Moore curve to reach 5340 * that position. 5341 * This assumes pt.x and pt.y are between 0 and 15, inclusive. 5342 * @param pt a Coord with values between 0 and 15, inclusive 5343 * @return a distance from the "start" of the 16x16 Moore curve to get to the position of pt 5344 */ 5345 public static int coordToMoore(final Coord pt) 5346 { 5347 return posToMoore(pt.x, pt.y); 5348 } 5349 5350 public static int mortonEncode3D( int index1, int index2, int index3 ) 5351 { // pack 3 5-bit indices into a 15-bit Morton code 5352 index1 &= 0x0000001f; 5353 index2 &= 0x0000001f; 5354 index3 &= 0x0000001f; 5355 index1 *= 0x01041041; 5356 index2 *= 0x01041041; 5357 index3 *= 0x01041041; 5358 index1 &= 0x10204081; 5359 index2 &= 0x10204081; 5360 index3 &= 0x10204081; 5361 index1 *= 0x00011111; 5362 index2 *= 0x00011111; 5363 index3 *= 0x00011111; 5364 index1 &= 0x12490000; 5365 index2 &= 0x12490000; 5366 index3 &= 0x12490000; 5367 return( ( index1 >> 16 ) | ( index2 >> 15 ) | ( index3 >> 14 ) ); 5368 } 5369 public static Coord3D mortonDecode3D( int morton ) 5370 { // unpack 3 5-bit indices from a 15-bit Morton code 5371 int value1 = morton; 5372 int value2 = ( value1 >>> 1 ); 5373 int value3 = ( value1 >>> 2 ); 5374 value1 &= 0x00001249; 5375 value2 &= 0x00001249; 5376 value3 &= 0x00001249; 5377 value1 |= ( value1 >>> 2 ); 5378 value2 |= ( value2 >>> 2 ); 5379 value3 |= ( value3 >>> 2 ); 5380 value1 &= 0x000010c3; 5381 value2 &= 0x000010c3; 5382 value3 &= 0x000010c3; 5383 value1 |= ( value1 >>> 4 ); 5384 value2 |= ( value2 >>> 4 ); 5385 value3 |= ( value3 >>> 4 ); 5386 value1 &= 0x0000100f; 5387 value2 &= 0x0000100f; 5388 value3 &= 0x0000100f; 5389 value1 |= ( value1 >>> 8 ); 5390 value2 |= ( value2 >>> 8 ); 5391 value3 |= ( value3 >>> 8 ); 5392 value1 &= 0x0000001f; 5393 value2 &= 0x0000001f; 5394 value3 &= 0x0000001f; 5395 return new Coord3D(value1, value2, value3); 5396 } 5397 public static int mortonBitDecode3D( int morton ) 5398 { // unpack 3 5-bit indices from a 15-bit Morton code 5399 int value1 = morton; 5400 int value2 = ( value1 >>> 1 ); 5401 int value3 = ( value1 >>> 2 ); 5402 value1 &= 0x00001249; 5403 value2 &= 0x00001249; 5404 value3 &= 0x00001249; 5405 value1 |= ( value1 >>> 2 ); 5406 value2 |= ( value2 >>> 2 ); 5407 value3 |= ( value3 >>> 2 ); 5408 value1 &= 0x000010c3; 5409 value2 &= 0x000010c3; 5410 value3 &= 0x000010c3; 5411 value1 |= ( value1 >>> 4 ); 5412 value2 |= ( value2 >>> 4 ); 5413 value3 |= ( value3 >>> 4 ); 5414 value1 &= 0x0000100f; 5415 value2 &= 0x0000100f; 5416 value3 &= 0x0000100f; 5417 value1 |= ( value1 >>> 8 ); 5418 value2 |= ( value2 >>> 8 ); 5419 value3 |= ( value3 >>> 8 ); 5420 value1 &= 0x0000001f; 5421 value2 &= 0x0000001f; 5422 value3 &= 0x0000001f; 5423 return value1 | (value2 << 5) | (value3 << 10); 5424 } 5425 5426 private static void computeHilbert2D(int x, int y) 5427 { 5428 int hilbert = 0, remap = 0xb4, mcode, hcode; 5429 5430 mcode = ( ( x >> 7 ) & 1 ) | ( ( ( y >> ( 7 ) ) & 1 ) << 1); 5431 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5432 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5433 hilbert = ( (0) + hcode ); 5434 5435 mcode = ( ( x >> 6 ) & 1 ) | ( ( ( y >> ( 6 ) ) & 1 ) << 1); 5436 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5437 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5438 hilbert = ( ( hilbert << 2 ) + hcode ); 5439 5440 mcode = ( ( x >> 5 ) & 1 ) | ( ( ( y >> ( 5 ) ) & 1 ) << 1); 5441 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5442 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5443 hilbert = ( ( hilbert << 2 ) + hcode ); 5444 5445 mcode = ( ( x >> 4 ) & 1 ) | ( ( ( y >> ( 4 ) ) & 1 ) << 1); 5446 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5447 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5448 hilbert = ( ( hilbert << 2 ) + hcode ); 5449 5450 mcode = ( ( x >> 3 ) & 1 ) | ( ( ( y >> ( 3 ) ) & 1 ) << 1); 5451 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5452 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5453 hilbert = ( ( hilbert << 2 ) + hcode ); 5454 5455 mcode = ( ( x >> 2 ) & 1 ) | ( ( ( y >> ( 2 ) ) & 1 ) << 1); 5456 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5457 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5458 hilbert = ( ( hilbert << 2 ) + hcode ); 5459 5460 mcode = ( ( x >> 1 ) & 1 ) | ( ( ( y >> ( 1 ) ) & 1 ) << 1); 5461 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5462 remap ^= ( 0x82000028 >> ( hcode << 3 ) ); 5463 hilbert = ( ( hilbert << 2 ) + hcode ); 5464 5465 mcode = ( x & 1 ) | ( ( y & 1 ) << 1); 5466 hcode = ( ( remap >> ( mcode << 1 ) ) & 3 ); 5467 5468 hilbertDistances[x | (y << 8)] = (short) ( hilbert = ( hilbert << 2 ) + hcode ); 5469 hilbertX[hilbert] = (short)x; 5470 hilbertY[hilbert] = (short)y; 5471 } 5472 5473 private static void computeHilbert3D(int x, int y, int z) 5474 { 5475 int hilbert = mortonEncode3D(x, y, z); 5476 int block = 6; 5477 int hcode = ( ( hilbert >> block ) & 7 ); 5478 int mcode, shift, signs; 5479 shift = signs = 0; 5480 while( block > 0 ) 5481 { 5482 block -= 3; 5483 hcode <<= 2; 5484 mcode = ( ( 0x20212021 >> hcode ) & 3 ); 5485 shift = ( ( 0x48 >> ( 7 - shift - mcode ) ) & 3 ); 5486 signs = ( ( signs | ( signs << 3 ) ) >> mcode ); 5487 signs = ( ( signs ^ ( 0x53560300 >> hcode ) ) & 7 ); 5488 mcode = ( ( hilbert >> block ) & 7 ); 5489 hcode = mcode; 5490 hcode = ( ( ( hcode | ( hcode << 3 ) ) >> shift ) & 7 ); 5491 hcode ^= signs; 5492 hilbert ^= ( ( mcode ^ hcode ) << block ); 5493 } 5494 5495 hilbert ^= ( ( hilbert >> 1 ) & 0x92492492 ); 5496 hilbert ^= ( ( hilbert & 0x92492492 ) >> 1 ); 5497 5498 hilbert3X[hilbert] = (short)x; 5499 hilbert3Y[hilbert] = (short)y; 5500 hilbert3Z[hilbert] = (short)z; 5501 hilbert3Distances[x | y << 3 | z << 6] = (short)hilbert; 5502 } 5503 5504 /** 5505 * Gets the x coordinate for a given index into the 16x16x(8*n) Moore curve. Expects indices to touch the following 5506 * corners of the 16x16x(8*n) cube in this order, using x,y,z syntax: 5507 * (0,0,0) (0,0,(8*n)) (0,16,(8*n)) (0,16,0) (16,16,0) (16,16,(8*n)) (16,0,(8*n)) (16,0,0) 5508 * @param index the index into the 3D 16x16x(8*n) Moore Curve, must be less than 0x1000 5509 * @param n the number of 8-deep layers to use as part of the box shape this travels through 5510 * @return the x coordinate of the given distance traveled through the 3D 16x16x(8*n) Moore Curve 5511 */ 5512 public static int getXMoore3D(final int index, final int n) { 5513 int hilbert = index & 0x1ff; 5514 int sector = index >> 9; 5515 if (sector < 2 * n) 5516 return 7 - hilbert3X[hilbert]; 5517 else 5518 return 8 + hilbert3X[hilbert]; 5519 } 5520 5521 /** 5522 * Gets the y coordinate for a given index into the 16x16x(8*n) Moore curve. Expects indices to touch the following 5523 * corners of the 16x16x(8*n) cube in this order, using x,y,z syntax: 5524 * (0,0,0) (0,0,(8*n)) (0,16,(8*n)) (0,16,0) (16,16,0) (16,16,(8*n)) (16,0,(8*n)) (16,0,0) 5525 * @param index the index into the 3D 16x16x(8*n) Moore Curve, must be less than 0x1000 5526 * @param n the number of 8-deep layers to use as part of the box shape this travels through 5527 * @return the y coordinate of the given distance traveled through the 3D 16x16x(8*n) Moore Curve 5528 */ 5529 public static int getYMoore3D(final int index, final int n) 5530 { 5531 int hilbert = index & 0x1ff; 5532 int sector = index >> 9; 5533 if (sector < n || sector >= 3 * n) 5534 return 7 - hilbert3Y[hilbert]; 5535 else 5536 return 8 + hilbert3Y[hilbert]; 5537 5538 } 5539 /** 5540 * Gets the z coordinate for a given index into the 16x16x(8*n) Moore curve. Expects indices to touch the following 5541 * corners of the 16x16x(8*n) cube in this order, using x,y,z syntax: 5542 * (0,0,0) (0,0,(8*n)) (0,16,(8*n)) (0,16,0) (16,16,0) (16,16,(8*n)) (16,0,(8*n)) (16,0,0) 5543 * @param index the index into the 3D 16x16x(8*n) Moore Curve, must be less than 0x1000 5544 * @param n the number of 8-deep layers to use as part of the box shape this travels through 5545 * @return the z coordinate of the given distance traveled through the 3D 16x16x(8*n) Moore Curve 5546 */ 5547 public static int getZMoore3D(final int index, final int n) { 5548 int hilbert = index & 0x1ff; 5549 int sector = index >> 9; 5550 if (((sector / n) & 1) == 0) 5551 return hilbert3Z[hilbert] + ((sector % n) << 3); 5552 else 5553 return (n << 3) - 1 - hilbert3Z[hilbert] - ((sector % n) << 3); 5554 } 5555 5556 5557 5558 /** 5559 * Takes two 8-bit unsigned integers index1 and index2, and returns a Morton code, with interleaved index1 and 5560 * index2 bits and index1 in the least significant bit. With this method, index1 and index2 can have up to 8 bits. 5561 * This returns a 16-bit Morton code and WILL encode information in the sign bit if the inputs are large enough. 5562 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5563 * @param index1 a non-negative integer using at most 8 bits, to be placed in the "x" slots 5564 * @param index2 a non-negative integer using at most 8 bits, to be placed in the "y" slots 5565 * @return a Morton code/Z-Code that interleaves the two numbers into one 16-bit short 5566 */ 5567 public static short zEncode(short index1, short index2) 5568 { // pack 2 8-bit (unsigned) indices into a 16-bit (signed...) Morton code/Z-Code 5569 index1 &= 0x000000ff; 5570 index2 &= 0x000000ff; 5571 index1 |= ( index1 << 4 ); 5572 index2 |= ( index2 << 4 ); 5573 index1 &= 0x00000f0f; 5574 index2 &= 0x00000f0f; 5575 index1 |= ( index1 << 2 ); 5576 index2 |= ( index2 << 2 ); 5577 index1 &= 0x00003333; 5578 index2 &= 0x00003333; 5579 index1 |= ( index1 << 1 ); 5580 index2 |= ( index2 << 1 ); 5581 index1 &= 0x00005555; 5582 index2 &= 0x00005555; 5583 return (short)(index1 | ( index2 << 1 )); 5584 } 5585 /** 5586 * Takes two 8-bit unsigned integers index1 and index2, and returns a Morton code, with interleaved index1 and 5587 * index2 bits and index1 in the least significant bit. With this method, index1 and index2 can have up to 8 bits. 5588 * This returns a 32-bit Morton code but only uses 16 bits, and will not encode information in the sign bit. 5589 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5590 * @param index1 a non-negative integer using at most 8 bits, to be placed in the "x" slots 5591 * @param index2 a non-negative integer using at most 8 bits, to be placed in the "y" slots 5592 * @return a Morton code that interleaves the two numbers as one 32-bit int, but only in 16 bits of it 5593 */ 5594 public static int mortonEncode(int index1, int index2) 5595 { // pack 2 8-bit (unsigned) indices into a 32-bit (signed...) Morton code 5596 index1 &= 0x000000ff; 5597 index2 &= 0x000000ff; 5598 index1 |= ( index1 << 4 ); 5599 index2 |= ( index2 << 4 ); 5600 index1 &= 0x00000f0f; 5601 index2 &= 0x00000f0f; 5602 index1 |= ( index1 << 2 ); 5603 index2 |= ( index2 << 2 ); 5604 index1 &= 0x00003333; 5605 index2 &= 0x00003333; 5606 index1 |= ( index1 << 1 ); 5607 index2 |= ( index2 << 1 ); 5608 index1 &= 0x00005555; 5609 index2 &= 0x00005555; 5610 return index1 | ( index2 << 1 ); 5611 } 5612 5613 /** 5614 * Takes a Morton code, with interleaved x and y bits and x in the least significant bit, and returns the Coord 5615 * representing the same x, y position. 5616 * This uses 16 bits of the Morton code and requires that the code is non-negative. 5617 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5618 * @param morton an int containing two interleaved numbers, from 0 to 255 each 5619 * @return a Coord matching the x and y extracted from the Morton code 5620 */ 5621 public static Coord mortonDecode( final int morton ) 5622 { // unpack 2 8-bit (unsigned) indices from a 32-bit (signed...) Morton code 5623 int value1 = morton; 5624 int value2 = ( value1 >> 1 ); 5625 value1 &= 0x5555; 5626 value2 &= 0x5555; 5627 value1 |= ( value1 >> 1 ); 5628 value2 |= ( value2 >> 1 ); 5629 value1 &= 0x3333; 5630 value2 &= 0x3333; 5631 value1 |= ( value1 >> 2 ); 5632 value2 |= ( value2 >> 2 ); 5633 value1 &= 0x0f0f; 5634 value2 &= 0x0f0f; 5635 value1 |= ( value1 >> 4 ); 5636 value2 |= ( value2 >> 4 ); 5637 value1 &= 0x00ff; 5638 value2 &= 0x00ff; 5639 return Coord.get(value1, value2); 5640 } 5641 5642 /** 5643 * Takes a Morton code, with interleaved x and y bits and x in the least significant bit, and returns the Coord 5644 * representing the same x, y position. 5645 * This takes a a 16-bit Z-Code with data in the sign bit, as returned by zEncode(). 5646 * Source: http://and-what-happened.blogspot.com/2011/08/fast-2d-and-3d-hilbert-curves-and.html 5647 * @param morton a short containing two interleaved numbers, from 0 to 255 each 5648 * @return a Coord matching the x and y extracted from the Morton code 5649 */ 5650 public static Coord zDecode( final short morton ) 5651 { // unpack 2 8-bit (unsigned) indices from a 32-bit (signed...) Morton code 5652 int value1 = morton & 0xffff; 5653 int value2 = ( value1 >> 1 ); 5654 value1 &= 0x5555; 5655 value2 &= 0x5555; 5656 value1 |= ( value1 >> 1 ); 5657 value2 |= ( value2 >> 1 ); 5658 value1 &= 0x3333; 5659 value2 &= 0x3333; 5660 value1 |= ( value1 >> 2 ); 5661 value2 |= ( value2 >> 2 ); 5662 value1 &= 0x0f0f; 5663 value2 &= 0x0f0f; 5664 value1 |= ( value1 >> 4 ); 5665 value2 |= ( value2 >> 4 ); 5666 value1 &= 0x00ff; 5667 value2 &= 0x00ff; 5668 return Coord.get(value1, value2); 5669 } 5670}