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