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