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}