001package squidpony.squidgrid.mapping;
002
003import squidpony.squidai.DijkstraMap;
004import squidpony.squidmath.Coord;
005import squidpony.squidmath.CoordPacker;
006import squidpony.squidmath.LightRNG;
007import squidpony.squidmath.PerlinNoise;
008import squidpony.squidmath.RNG;
009import squidpony.squidmath.StatefulRNG;
010
011import java.util.Map;
012import java.util.Set;
013
014/**
015 * A static class that can be used to modify the char[][] dungeons that other generators produce.
016 * Includes various utilities for random floor-finding, but also provides ways to take dungeons that use '#'
017 * for walls and make a copy that uses unicode box drawing characters.
018 *
019 * @author Tommy Ettinger - https://github.com/tommyettinger
020 * @see squidpony.squidgrid.mapping.DungeonGenerator
021 * Created by Tommy Ettinger on 4/1/2015.
022 */
023public class DungeonUtility {
024
025    public DungeonUtility() {
026        rng = new StatefulRNG();
027    }
028
029    public DungeonUtility(StatefulRNG rng) {
030        this.rng = rng;
031    }
032
033    public DungeonUtility(RNG rng) {
034        this.rng = new StatefulRNG(new LightRNG(rng.nextLong()));
035    }
036
037    /**
038     * The random number generator that will be used for all methods in this class with a random component.
039     */
040    public StatefulRNG rng;
041
042    /**
043     * Finds a random Coord where the x and y match up to a [x][y] location on map that has '.' as a value.
044     * Uses this class' rng field for pseudo-random number generation.
045     *
046     * @param map a char[][] that should contain a '.' floor tile
047     * @return a Coord that corresponds to a '.' in map, or null if a '.' cannot be found or if map is too small
048     */
049    public Coord randomFloor(char[][] map) {
050        int width = map.length;
051        int height = map[0].length;
052        if (width < 3 || height < 3)
053            return null;
054        int x = rng.nextInt(width - 2) + 1, y = rng.nextInt(height - 2) + 1;
055        for (int i = 0; i < 20; i++) {
056            if (map[x][y] == '.') {
057                return Coord.get(x, y);
058            } else {
059                x = rng.nextInt(width - 2) + 1;
060                y = rng.nextInt(height - 2) + 1;
061            }
062        }
063        x = 1;
064        y = 1;
065        if (map[x][y] == '.')
066            return Coord.get(x, y);
067
068        while (map[x][y] != '.') {
069            x += 1;
070            if (x >= width - 1) {
071                x = 1;
072                y += 1;
073            }
074            if (y >= height - 1)
075                return null;
076        }
077        return Coord.get(x, y);
078    }
079
080    /**
081     * Finds a random Coord where the x and y match up to a [x][y] location that is encoded as "on" in packed.
082     * This is useful when you have used {@code DungeonUtility.packedFloors(char[][] map)} to encode all floors in map,
083     * or {@code CoordPacker.pack(char[][] map, char... yes)} to encode all cells in a char[][] map that match a
084     * particular type, like '.' for floors or '~' for deep water, and want to efficiently get one randomly-chosen tile
085     * from it. Calling pack() is likely slightly less efficient than using randomFloor(), but it only needs to be done
086     * once per map and cell type, and this method should be substantially more efficient when the type of cell is
087     * uncommon on the map.
088     * Uses this class' rng field for pseudo-random number generation.
089     *
090     * @param packed a packed array produced by CoordPacker encoding the cells to choose from as "on"
091     * @return a Coord that corresponds to a '.' in map, or (-1, -1) if a '.' cannot be found or if map is too small
092     */
093    public Coord randomCell(short[] packed) {
094        return CoordPacker.singleRandom(packed, rng);
095    }
096
097    /**
098     * A convenience wrapper for getting a packed-data representation of all floors ('.') in map, for randomCell().
099     * If you want other chars or more chars than just the period, you can use CoordPacker.pack() with a char[][] map
100     * and one or more chars to find as the parameters. This is the same as calling {@code CoordPacker.pack(map, '.')}.
101     * @param map a char[][] that uses '.' to represent floors
102     * @return all floors in map in packed data format (a special short array) that can be given to randomCell()
103     */
104    public static short[] packedFloors(char[][] map)
105    {
106        return CoordPacker.pack(map, '.');
107    }
108
109    /**
110     * Finds a random Coord where the x and y match up to a [x][y] location on map that has the same value as the
111     * parameter tile. Uses this class' rng field for pseudo-random number generation.
112     *
113     * @param map  a char[][] that should contain the desired tile
114     * @param tile the char to search for
115     * @return a Coord that corresponds to a map element equal to tile, or null if tile cannot be found or if map is too small.
116     */
117    public Coord randomMatchingTile(char[][] map, char tile) {
118        int width = map.length;
119        int height = map[0].length;
120        if (width < 3 || height < 3)
121            return null;
122        int x = rng.nextInt(width - 2) + 1, y = rng.nextInt(height - 2) + 1;
123        for (int i = 0; i < 30; i++) {
124            if (map[x][y] == tile) {
125                return Coord.get(x, y);
126            } else {
127                x = rng.nextInt(width - 2) + 1;
128                y = rng.nextInt(height - 2) + 1;
129            }
130        }
131        x = 1;
132        y = 1;
133        if (map[x][y] == tile)
134            return Coord.get(x, y);
135
136        while (map[x][y] != tile) {
137            x += 1;
138            if (x >= width - 1) {
139                x = 1;
140                y += 1;
141            }
142            if (y >= height - 1)
143                return null;
144        }
145        return Coord.get(x, y);
146    }
147
148    /**
149     * Gets a random Coord that is adjacent to start, validating whether the position can exist on the given map.
150     * Adjacency defaults to four-way cardinal directions unless eightWay is true, in which case it uses Chebyshev.
151     * This can step into walls, and should NOT be used for movement.  It is meant for things like sound that can
152     * exist in walls, or for assigning decor to floors or walls that are adjacent to floors.
153     *
154     * @param map      a char[][] map that this will only use for its width and height; contents are ignored
155     * @param start    the starting position
156     * @param eightWay true to choose a random orthogonal or diagonal direction; false to only choose from orthogonal
157     * @return a Coord that is adjacent to start on the map, or null if start is off the map or the map is very small
158     */
159    public Coord randomStep(char[][] map, Coord start, boolean eightWay) {
160        int width = map.length;
161        int height = map[0].length;
162        if (width < 3 || height < 3 || start.x < 0 || start.y < 0 || start.x > width - 1 || start.y > height - 1)
163            return null;
164        Coord stepped = Coord.get(start.x, start.y);
165
166        if (eightWay) {
167            int mv = rng.nextInt(9);
168            return Coord.get(Math.min(Math.max(0, stepped.x + (mv % 3) - 1), height - 1),
169                    Math.min(Math.max(0, stepped.y + (mv / 3) - 1), height - 1));
170        } else {
171            int mv = rng.nextInt(5);
172            switch (mv) {
173                case 0:
174                    return Coord.get(Math.min(Math.max(0, stepped.x - 1), height - 1),
175                            stepped.y);
176                case 1:
177                    return Coord.get(Math.min(Math.max(0, stepped.x + 1), height - 1),
178                            stepped.y);
179                case 2:
180                    return Coord.get(stepped.x,
181                            Math.min(Math.max(0, stepped.y - 1), height - 1));
182                case 3:
183                    return Coord.get(stepped.x,
184                            Math.min(Math.max(0, stepped.y + 1), height - 1));
185                default:
186                    return stepped;
187            }
188        }
189    }
190
191    /**
192     * Finds a random Coord where the x and y match up to a [x][y] location on map that has '.' as a value,
193     * and a square of cells extending in the positive x and y directions with a side length of size must also have
194     * '.' as their values.
195     * Uses this class' rng field for pseudo-random number generation.
196     *
197     * @param map  a char[][] that should contain at least one floor represented by '.'
198     * @param size the side length of a square that must be completely filled with floors for this to return it
199     * @return a Coord that corresponds to a '.' in map, or null if a '.' cannot be found or if map is too small.
200     */
201    public Coord randomFloorLarge(char[][] map, int size) {
202        int width = map.length;
203        int height = map[0].length;
204        if (width < size + 2 || height < size + 2)
205            return null;
206        int x = rng.nextInt(width - size), y = rng.nextInt(height - size);
207        CELL:
208        for (int i = 0; i < 20; i++, x = rng.nextInt(width - size), y = rng.nextInt(height - size)) {
209            if (map[x][y] == '.') {
210                for (int j = 0; j < size; j++) {
211                    for (int k = 0; k < size; k++) {
212                        if (map[x + j][y + k] != '.')
213                            continue CELL;
214                    }
215                }
216                return Coord.get(x, y);
217            }
218        }
219        x = 1;
220        y = 1;
221
222        SLOW:
223        while (true) {
224            x += 1;
225            if (x >= width - size) {
226                x = 1;
227                y += 1;
228            }
229            if (y >= height - size)
230                return null;
231            if (map[x][y] == '.') {
232                for (int j = 0; j < size; j++) {
233                    for (int k = 0; k < size; k++) {
234                        if (map[x + j][y + k] != '.')
235                            continue SLOW;
236                    }
237                }
238                return Coord.get(x, y);
239            }
240        }
241    }
242
243    /**
244     * Takes a char[][] dungeon map that uses '#' to represent walls, and returns a new char[][] that uses unicode box
245     * drawing characters to draw straight, continuous lines for walls, filling regions between walls (that were
246     * filled with more walls before) with space characters, ' '. If the lines "point the wrong way," such as having
247     * multiple horizontally adjacent vertical lines where there should be horizontal lines, call transposeLines() on
248     * the returned map, which will keep the dimensions of the map the same and only change the line chars. You will
249     * also need to call transposeLines if you call hashesToLines on a map that already has "correct" line-drawing
250     * characters, which means hashesToLines should only be called on maps that use '#' for walls. If you have a
251     * jumbled map that contains two or more of the following: "correct" line-drawing characters, "incorrect"
252     * line-drawing characters, and '#' characters for walls, you can reset by calling linesToHashes() and then
253     * potentially calling hashesToLines() again.
254     *
255     * @param map a 2D char array indexed with x,y that uses '#' for walls
256     * @return a copy of the map passed as an argument with box-drawing characters replacing '#' walls
257     */
258    public static char[][] hashesToLines(char[][] map) {
259        return hashesToLines(map, false);
260    }
261
262    private static final char[] wallLookup = new char[]
263            {
264                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
265                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
266                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
267                    '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '┴', '┐', '┤', '┬', '┤',
268                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
269                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
270                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '─', '┴',
271                    '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '┴', '┐', '┤', '─', '┘',
272                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
273                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '─', '┐', '┤', '┬', '┬',
274                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '┤', '┬', '┼',
275                    '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '─', '┐', '┤', '┬', '┐',
276                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '│', '┬', '├',
277                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '─', '┐', '│', '┬', '┌',
278                    '#', '│', '─', '└', '│', '│', '┌', '├', '─', '┘', '─', '┴', '┐', '│', '─', '└',
279                    '#', '│', '─', '└', '│', '│', '┌', '│', '─', '┘', '─', '─', '┐', '│', '─', '\1'
280            };
281
282    /**
283     * Takes a char[][] dungeon map that uses '#' to represent walls, and returns a new char[][] that uses unicode box
284     * drawing characters to draw straight, continuous lines for walls, filling regions between walls (that were
285     * filled with more walls before) with space characters, ' '. If keepSingleHashes is true, then '#' will be used if
286     * a wall has no orthogonal wall neighbors; if it is false, then a horizontal line will be used for stand-alone
287     * wall cells. If the lines "point the wrong way," such as having multiple horizontally adjacent vertical lines
288     * where there should be horizontal lines, call transposeLines() on the returned map, which will keep the dimensions
289     * of the map the same and only change the line chars. You will also need to call transposeLines if you call
290     * hashesToLines on a map that already has "correct" line-drawing characters, which means hashesToLines should only
291     * be called on maps that use '#' for walls. If you have a jumbled map that contains two or more of the following:
292     * "correct" line-drawing characters, "incorrect" line-drawing characters, and '#' characters for walls, you can
293     * reset by calling linesToHashes() and then potentially calling hashesToLines() again.
294     *
295     * @param map              a 2D char array indexed with x,y that uses '#' for walls
296     * @param keepSingleHashes true if walls that are not orthogonally adjacent to other walls should stay as '#'
297     * @return a copy of the map passed as an argument with box-drawing characters replacing '#' walls
298     */
299    public static char[][] hashesToLines(char[][] map, boolean keepSingleHashes) {
300        int width = map.length + 2;
301        int height = map[0].length + 2;
302
303        char[][] dungeon = new char[width][height];
304        for (int i = 1; i < width - 1; i++) {
305            System.arraycopy(map[i - 1], 0, dungeon[i], 1, height - 2);
306        }
307        for (int i = 0; i < width; i++) {
308            dungeon[i][0] = '\1';
309            dungeon[i][height - 1] = '\1';
310        }
311        for (int i = 0; i < height; i++) {
312            dungeon[0][i] = '\1';
313            dungeon[width - 1][i] = '\1';
314        }
315        for (int x = 1; x < width - 1; x++) {
316            for (int y = 1; y < height - 1; y++) {
317                if (map[x - 1][y - 1] == '#') {
318                    int q = 0;
319                    q |= (y <= 1 || map[x - 1][y - 2] == '#' || map[x - 1][y - 2] == '+' || map[x - 1][y - 2] == '/') ? 1 : 0;
320                    q |= (x >= width - 2 || map[x][y - 1] == '#' || map[x][y - 1] == '+' || map[x][y - 1] == '/') ? 2 : 0;
321                    q |= (y >= height - 2 || map[x - 1][y] == '#' || map[x - 1][y] == '+' || map[x - 1][y] == '/') ? 4 : 0;
322                    q |= (x <= 1 || map[x - 2][y - 1] == '#' || map[x - 2][y - 1] == '+' || map[x - 2][y - 1] == '/') ? 8 : 0;
323
324                    q |= (y <= 1 || x >= width - 2 || map[x][y - 2] == '#' || map[x][y - 2] == '+' || map[x][y - 2] == '/') ? 16 : 0;
325                    q |= (y >= height - 2 || x >= width - 2 || map[x][y] == '#' || map[x][y] == '+' || map[x][y] == '/') ? 32 : 0;
326                    q |= (y >= height - 2 || x <= 1 || map[x - 2][y] == '#' || map[x - 2][y] == '+' || map[x - 2][y] == '/') ? 64 : 0;
327                    q |= (y <= 1 || x <= 1 || map[x - 2][y - 2] == '#' || map[x - 2][y - 2] == '+' || map[x - 2][y - 2] == '/') ? 128 : 0;
328                    if (!keepSingleHashes && wallLookup[q] == '#') {
329                        dungeon[x][y] = '─';
330                    } else {
331                        dungeon[x][y] = wallLookup[q];
332                    }
333                }
334            }
335        }
336        char[][] portion = new char[width - 2][height - 2];
337        for (int i = 1; i < width - 1; i++) {
338            for (int j = 1; j < height - 1; j++) {
339                switch (dungeon[i][j]) {
340                    case '\1':
341                        portion[i - 1][j - 1] = ' ';
342                        break;
343                    default: // ┼┌┘
344                        portion[i - 1][j - 1] = dungeon[i][j];
345                }
346            }
347        }
348        return portion;
349    }
350
351    /**
352     * Reverses most of the effects of hashesToLines(). The only things that will not be reversed are the placement of
353     * space characters in unreachable wall-cells-behind-wall-cells, which remain as spaces. This is useful if you
354     * have a modified map that contains wall characters of conflicting varieties, as described in hashesToLines().
355     *
356     * @param map a 2D char array indexed with x,y that uses box-drawing characters for walls
357     * @return a copy of the map passed as an argument with '#' replacing box-drawing characters for walls
358     */
359    public static char[][] linesToHashes(char[][] map) {
360
361        int width = map.length;
362        int height = map[0].length;
363        char[][] portion = new char[width][height];
364        for (int i = 0; i < width; i++) {
365            for (int j = 0; j < height; j++) {
366                switch (map[i][j]) {
367                    case '\1':
368                    case '├':
369                    case '┤':
370                    case '┴':
371                    case '┬':
372                    case '┌':
373                    case '┐':
374                    case '└':
375                    case '┘':
376                    case '│':
377                    case '─':
378                    case '┼':
379                        portion[i][j] = '#';
380                        break;
381                    default:
382                        portion[i][j] = map[i][j];
383                }
384            }
385        }
386        return portion;
387    }
388
389    /**
390     * If you call hashesToLines() on a map that uses [y][x] conventions instead of [x][y], it will have the lines not
391     * connect as you expect. Use this function to change the directions of the box-drawing characters only, without
392     * altering the dimensions in any way. This returns a new char[][], instead of modifying the parameter in place.
393     * transposeLines is also needed if the lines in a map have become transposed when they were already correct;
394     * calling this method on an incorrectly transposed map will change the directions on all of its lines.
395     *
396     * @param map a 2D char array indexed with y,x that uses box-drawing characters for walls
397     * @return a copy of map that uses box-drawing characters for walls that will be correct when indexed with x,y
398     */
399    public static char[][] transposeLines(char[][] map) {
400
401        int width = map[0].length;
402        int height = map.length;
403        char[][] portion = new char[height][width];
404        for (int i = 0; i < height; i++) {
405            for (int j = 0; j < width; j++) {
406                switch (map[i][j]) {
407                    case '\1':
408                        portion[i][j] = ' ';
409                        break;
410                    case '├':
411                        portion[i][j] = '┬';
412                        break;
413                    case '┤':
414                        portion[i][j] = '┴';
415                        break;
416                    case '┴':
417                        portion[i][j] = '┤';
418                        break;
419                    case '┬':
420                        portion[i][j] = '├';
421                        break;
422                    case '┐':
423                        portion[i][j] = '└';
424                        break;
425                    case '└':
426                        portion[i][j] = '┐';
427                        break;
428                    case '│':
429                        portion[i][j] = '─';
430                        break;
431                    case '─':
432                        portion[i][j] = '│';
433                        break;
434//                    case '├ ┤ ┴ ┬ ┌ ┐ └ ┘ │ ─':
435                    default: // ┼┌┘
436                        portion[i][j] = map[i][j];
437                }
438            }
439        }
440        return portion;
441    }
442
443    /**
444     * When a map is generated by DungeonGenerator with addDoors enabled, different chars are used for vertical and
445     * horizontal doors ('+' for vertical and '/' for horizontal).  This makes all doors '+', which is useful if you
446     * want '/' to be used for a different purpose and/or to distinguish open and closed doors.
447     *
448     * @param map a char[][] that may have both '+' and '/' for doors
449     * @return a char[][] that only uses '+' for all doors
450     */
451    public static char[][] closeDoors(char[][] map) {
452
453        int width = map.length;
454        int height = map[0].length;
455        char[][] portion = new char[width][height];
456        for (int i = 0; i < width; i++) {
457            for (int j = 0; j < height; j++) {
458                if (map[i][j] == '/') portion[i][j] = '+';
459                else portion[i][j] = map[i][j];
460
461            }
462        }
463        return portion;
464    }
465
466    /**
467     * When a map is generated by DungeonGenerator with addDoors enabled, different chars are used for vertical and
468     * horizontal doors ('+' for vertical and '/' for horizontal).  This makes all doors '/', which is useful if you
469     * want '+' to be used for a different purpose and/or to distinguish open and closed doors.
470     *
471     * @param map a char[][] that may have both '+' and '/' for doors
472     * @return a char[][] that only uses '/' for all doors
473     */
474    public static char[][] openDoors(char[][] map) {
475
476        int width = map.length;
477        int height = map[0].length;
478        char[][] portion = new char[width][height];
479        for (int i = 0; i < width; i++) {
480            for (int j = 0; j < height; j++) {
481                if (map[i][j] == '+') portion[i][j] = '/';
482                else portion[i][j] = map[i][j];
483            }
484        }
485        return portion;
486    }
487
488
489    /**
490     * Takes a char[][] dungeon map and returns a copy with all box drawing chars, special placeholder chars, or '#'
491     * chars changed to '#' and everything else changed to '.' .
492     *
493     * @param map a char[][] with different characters that can be simplified to "wall" or "floor"
494     * @return a copy of map with all box-drawing, placeholder, wall or space characters as '#' and everything else '.'
495     */
496    public static char[][] simplifyDungeon(char[][] map) {
497
498        int width = map.length;
499        int height = map[0].length;
500        char[][] portion = new char[width][height];
501        for (int i = 0; i < width; i++) {
502            for (int j = 0; j < height; j++) {
503                switch (map[i][j]) {
504                    case '\1':
505                    case '├':
506                    case '┤':
507                    case '┴':
508                    case '┬':
509                    case '┌':
510                    case '┐':
511                    case '└':
512                    case '┘':
513                    case '│':
514                    case '─':
515                    case '┼':
516                    case ' ':
517                    case '#':
518                        portion[i][j] = '#';
519                        break;
520                    default:
521                        portion[i][j] = '.';
522                }
523            }
524        }
525        return portion;
526    }
527
528    /**
529     * Takes a dungeon map with either '#' as the only wall character or the unicode box drawing characters used by
530     * hashesToLines(), and returns a new char[][] dungeon map with two characters per cell, mostly filling the spaces
531     * next to non-walls with space characters, and only doing anything different if a box-drawing character would
532     * continue into an adjacent cell, or if a '#' wall needs another '#' wall next to it. The recommended approach is
533     * to keep both the original non-double-width map and the newly-returned double-width map, since the single-width
534     * maps can be used more easily for pathfinding. If you need to undo this function, call unDoubleWidth().
535     *
536     * @param map a char[][] that uses either '#' or box-drawing characters for walls, but one per cell
537     * @return a widened copy of map that uses two characters for every cell, connecting box-drawing chars correctly
538     */
539    public static char[][] doubleWidth(char[][] map) {
540        int width = map.length;
541        int height = map[0].length;
542        char[][] paired = new char[width * 2][height];
543        for (int y = 0; y < height; y++) {
544            for (int x = 0, px = 0; x < width; x++, px += 2) {
545                paired[px][y] = map[x][y];
546                switch (paired[px][y]) {
547                    //                        case '┼ ├ ┤ ┴ ┬ ┌ ┐ └ ┘ │ ─'
548                    case '┼':
549                    case '├':
550                    case '┴':
551                    case '┬':
552                    case '┌':
553                    case '└':
554                    case '─':
555                        paired[px + 1][y] = '─';
556                        break;
557                    case '#':
558                        paired[px + 1][y] = '#';
559                        break;
560
561                    default:
562                        paired[px + 1][y] = ' ';
563                        break;
564                        /*
565                    case '.':
566                    case '┤':
567                    case '┐':
568                    case '┘':
569                    case '│':
570                         */
571                }
572            }
573        }
574        return paired;
575    }
576
577    /**
578     * Takes a dungeon map that uses two characters per cell, and condenses it to use only the left (lower index)
579     * character in each cell. This should (probably) only be called on the result of doubleWidth(), and will throw an
580     * exception if called on a map with an odd number of characters for width, such as "#...#" .
581     *
582     * @param map a char[][] that has been widened by doubleWidth()
583     * @return a copy of map that uses only one char per cell
584     */
585    public static char[][] unDoubleWidth(char[][] map) {
586        int width = map.length;
587        int height = map[0].length;
588        if (width % 2 != 0)
589            throw new IllegalArgumentException("Argument must be a char[width][height] with an even width.");
590        char[][] unpaired = new char[width / 2][height];
591        for (int y = 0; y < height; y++) {
592            for (int x = 0, px = 0; px < width; x++, px += 2) {
593                unpaired[x][y] = map[px][y];
594            }
595        }
596        return unpaired;
597    }
598
599    /**
600     * Produces an int[][] that can be used with any palette of your choice for methods in SquidPanel or for your own
601     * rendering method. 1 is used as a default and for tiles with nothing in them; if the background is black, then
602     * white would make sense as this default. Other indices used are 2 for walls (this doesn't care if the walls are
603     * hashes or lines), 3 for floors (usually '.'), 4 for doors ('+' and '/' in the map), 5 for water, 6 for traps, and
604     * 20 for grass.
605     *
606     * @param map a char[][] containing foreground characters that you want foreground palette indices for
607     * @return a 2D array of ints that can be used as indices into a palette; palettes are available in related modules
608     */
609    public static int[][] generatePaletteIndices(char[][] map) {
610
611        int width = map.length;
612        int height = map[0].length;
613        int[][] portion = new int[width][height];
614        for (int i = 0; i < width; i++) {
615            for (int j = 0; j < height; j++) {
616                switch (map[i][j]) {
617                    case '\1':
618                    case '├':
619                    case '┤':
620                    case '┴':
621                    case '┬':
622                    case '┌':
623                    case '┐':
624                    case '└':
625                    case '┘':
626                    case '│':
627                    case '─':
628                    case '┼':
629                    case '#':
630                        portion[i][j] = 2;
631                        break;
632                    case '.':
633                    case ':':
634                        portion[i][j] = 3;
635                        break;
636                    case '+':
637                    case '/':
638                        portion[i][j] = 4;
639                        break;
640                    case ',':
641                    case '~':
642                        portion[i][j] = 5;
643                        break;
644                    case '"':
645                        portion[i][j] = 20;
646                        break;
647                    case '^':
648                        portion[i][j] = 6;
649                        break;
650                    default:
651                        portion[i][j] = 1;
652                }
653            }
654        }
655        return portion;
656    }
657
658    /**
659     * Produces an int[][] that can be used with any palette of your choice for methods in SquidPanel or for your own
660     * rendering method. 1 is used as a default and for tiles with nothing in them; if the background is black, then
661     * white would make sense as this default. Other indices used are 2 for walls (this doesn't care if the walls are
662     * hashes or lines), 3 for floors (usually '.'), 4 for doors ('+' and '/' in the map), 5 for water, 6 for traps, and
663     * 20 for grass.
664     *
665     * @param map a char[][] containing foreground characters that you want foreground palette indices for
666     * @return a 2D array of ints that can be used as indices into a palette; palettes are available in related modules
667     */
668    public static int[][] generatePaletteIndices(char[][] map, char deepChar, int deepIndex,
669                                                 char shallowChar, int shallowIndex) {
670
671        int width = map.length;
672        int height = map[0].length;
673        int[][] portion = new int[width][height];
674        for (int i = 0; i < width; i++) {
675            for (int j = 0; j < height; j++) {
676                switch (map[i][j]) {
677                    case '\1':
678                    case '├':
679                    case '┤':
680                    case '┴':
681                    case '┬':
682                    case '┌':
683                    case '┐':
684                    case '└':
685                    case '┘':
686                    case '│':
687                    case '─':
688                    case '┼':
689                    case '#':
690                        portion[i][j] = 2;
691                        break;
692                    case '.':
693                    case ':':
694                        portion[i][j] = 3;
695                        break;
696                    case '+':
697                    case '/':
698                        portion[i][j] = 4;
699                        break;
700                    case ',':
701                    case '~':
702                        portion[i][j] = 5;
703                        break;
704                    case '"':
705                        portion[i][j] = 20;
706                        break;
707                    case '^':
708                        portion[i][j] = 6;
709                        break;
710                    default:
711                        if (map[i][j] == deepChar)
712                            portion[i][j] = deepIndex;
713                        else if (map[i][j] == shallowChar)
714                            portion[i][j] = shallowIndex;
715                        else portion[i][j] = 1;
716                }
717            }
718        }
719        return portion;
720    }
721
722
723    /**
724     * Produces an int[][] that can be used with any palette of your choice for methods in SquidPanel or for your own
725     * rendering method, but meant for the background palette. This will produce 0 for most characters, but deep water
726     * (represented by '~') will produce 24 (in the default palette, this is dark blue-green), shallow water
727     * (represented by ',') will produce 23 (medium blue-green), and grass (represented by '"') will produce 21 (dark
728     * green). If you use SquidLayers, you can cause the lightness of water and grass to vary as if currents or wind
729     * are moving their surface using getLightnessModifiers() and a frame count argument.
730     *
731     * @param map a char[][] containing foreground characters that you want background palette indices for
732     * @return a 2D array of ints that can be used as indices into a palette; palettes are available in related modules
733     */
734    public static int[][] generateBGPaletteIndices(char[][] map) {
735
736        int width = map.length;
737        int height = map[0].length;
738        int[][] portion = new int[width][height];
739        for (int i = 0; i < width; i++) {
740            for (int j = 0; j < height; j++) {
741                switch (map[i][j]) {
742                    case '\1':
743                    case '├':
744                    case '┤':
745                    case '┴':
746                    case '┬':
747                    case '┌':
748                    case '┐':
749                    case '└':
750                    case '┘':
751                    case '│':
752                    case '─':
753                    case '┼':
754                    case '#':
755                        portion[i][j] = 0;
756                        break;
757                    case '.':
758                        portion[i][j] = 0;
759                        break;
760                    case ':':
761                        portion[i][j] = 35;
762                        break;
763                    case '+':
764                    case '/':
765                        portion[i][j] = 0;
766                        break;
767                    case ',':
768                        portion[i][j] = 23;
769                        break;
770                    case '~':
771                        portion[i][j] = 24;
772                        break;
773                    case '"':
774                        portion[i][j] = 21;
775                        break;
776                    case '^':
777                        portion[i][j] = 0;
778                        break;
779                    default:
780                        portion[i][j] = 0;
781                }
782            }
783        }
784        return portion;
785    }
786
787
788    /**
789     * Produces an int[][] that can be used with any palette of your choice for methods in SquidPanel or for your own
790     * rendering method, but meant for the background palette. This will produce 0 for most characters, but deep water
791     * (represented by '~') will produce 24 (in the default palette, this is dark blue-green), shallow water
792     * (represented by ',') will produce 23 (medium blue-green), and grass (represented by '"') will produce 21 (dark
793     * green). If you use SquidLayers, you can cause the lightness of water and grass to vary as if currents or wind
794     * are moving their surface using getLightnessModifiers() and a frame count argument.
795     *
796     * @param map a char[][] containing foreground characters that you want background palette indices for
797     * @return a 2D array of ints that can be used as indices into a palette; palettes are available in related modules
798     */
799    public static int[][] generateBGPaletteIndices(char[][] map, char deepChar, int deepIndex,
800                                                   char shallowChar, int shallowIndex) {
801
802        int width = map.length;
803        int height = map[0].length;
804        int[][] portion = new int[width][height];
805        for (int i = 0; i < width; i++) {
806            for (int j = 0; j < height; j++) {
807                switch (map[i][j]) {
808                    case '\1':
809                    case '├':
810                    case '┤':
811                    case '┴':
812                    case '┬':
813                    case '┌':
814                    case '┐':
815                    case '└':
816                    case '┘':
817                    case '│':
818                    case '─':
819                    case '┼':
820                    case '#':
821                        portion[i][j] = 0;
822                        break;
823                    case '.':
824                        portion[i][j] = 0;
825                        break;
826                    case ':':
827                        portion[i][j] = 35;
828                        break;
829                    case '+':
830                    case '/':
831                        portion[i][j] = 0;
832                        break;
833                    case ',':
834                        portion[i][j] = 23;
835                        break;
836                    case '~':
837                        portion[i][j] = 24;
838                        break;
839                    case '"':
840                        portion[i][j] = 21;
841                        break;
842                    case '^':
843                        portion[i][j] = 0;
844                        break;
845                    default:
846                        if (map[i][j] == deepChar)
847                            portion[i][j] = deepIndex;
848                        else if (map[i][j] == shallowChar)
849                            portion[i][j] = shallowIndex;
850                        else portion[i][j] = 0;
851                }
852            }
853        }
854        return portion;
855    }
856
857    /**
858     * Produces an int[][] that can be used with SquidLayers to alter the background colors.
859     *
860     * @param map a char[][] that you want to be find background lightness modifiers for
861     * @return a 2D array of lightness values from -255 to 255 but usually close to 0; can be passed to SquidLayers
862     */
863    public static int[][] generateLightnessModifiers(char[][] map) {
864        int width = map.length;
865        int height = map[0].length;
866        int[][] portion = new int[width][height];
867        for (int i = 0; i < width; i++) {
868            for (int j = 0; j < height; j++) {
869                switch (map[i][j]) {
870                    case '\1':
871                    case '├':
872                    case '┤':
873                    case '┴':
874                    case '┬':
875                    case '┌':
876                    case '┐':
877                    case '└':
878                    case '┘':
879                    case '│':
880                    case '─':
881                    case '┼':
882                    case '#':
883                        portion[i][j] = 30;
884                        break;
885                    case '.':
886                        portion[i][j] = 0;
887                        break;
888                    case ':':
889                        portion[i][j] = -15;
890                        break;
891                    case '+':
892                    case '/':
893                        portion[i][j] = -10;
894                        break;
895                    case ',':
896                        portion[i][j] = (int) (70 * (PerlinNoise.noise(i / 4.0, j / 4.0) / 2.5 - 0.45));
897                        break;
898                    case '~':
899                        portion[i][j] = (int) (100 * (PerlinNoise.noise(i / 4.0, j / 4.0) / 2.5 - 0.65));
900                        break;
901                    case '"':
902                        portion[i][j] = (int) (75 * (PerlinNoise.noise(i / 4.0, j / 4.0) / 4.0 - 1.5));
903                        break;
904                    case '^':
905                        portion[i][j] = 40;
906                        break;
907                    default:
908                        portion[i][j] = 0;
909                }
910            }
911        }
912        return portion;
913    }
914
915    /**
916     * Produces an int[][] that can be used with SquidLayers to alter the background colors, accepting a parameter for
917     * animation frame if rippling water and waving grass using Perlin Noise are desired.
918     *
919     * @param map   a char[][] that you want to be find background lightness modifiers for
920     * @param frame a counter that typically should increase by between 10.0 and 20.0 each second; higher numbers make
921     *              water and grass move more
922     * @return a 2D array of lightness values from -255 to 255 but usually close to 0; can be passed to SquidLayers
923     */
924    public static int[][] generateLightnessModifiers(char[][] map, double frame) {
925        int width = map.length;
926        int height = map[0].length;
927        int[][] portion = new int[width][height];
928        for (int i = 0; i < width; i++) {
929            for (int j = 0; j < height; j++) {
930                switch (map[i][j]) {
931                    case '\1':
932                    case '├':
933                    case '┤':
934                    case '┴':
935                    case '┬':
936                    case '┌':
937                    case '┐':
938                    case '└':
939                    case '┘':
940                    case '│':
941                    case '─':
942                    case '┼':
943                    case '#':
944                        portion[i][j] = 30;
945                        break;
946                    case '.':
947                        portion[i][j] = 0;
948                        break;
949                    case ':':
950                        portion[i][j] = -15;
951                        break;
952                    case '+':
953                    case '/':
954                        portion[i][j] = -10;
955                        break;
956                    case ',':
957                        portion[i][j] = (int) (70 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 25.0) / 2.5 - 0.45));
958                        break;
959                    case '~':
960                        portion[i][j] = (int) (100 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 25.0) / 2.5 - 0.65));
961                        break;
962                    case '"':
963                        portion[i][j] = (int) (75 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 35.0) / 4.0 - 1.5));
964                        break;
965                    case '^':
966                        portion[i][j] = 40;
967                        break;
968                    default:
969                        portion[i][j] = 0;
970                }
971            }
972        }
973        return portion;
974    }
975
976    /**
977     * Produces an int[][] that can be used with SquidLayers to alter the background colors, accepting a parameter for
978     * animation frame if rippling water and waving grass using Perlin Noise are desired. Also allows additional chars
979     * to be treated like deep and shallow water regarding the ripple animation.
980     *
981     * @param map           a char[][] that you want to be find background lightness modifiers for
982     * @param frame         a counter that typically should increase by between 10.0 and 20.0 each second; higher numbers make
983     *                      water and grass move more
984     * @param deepLiquid    a char that will be treated like deep water when animating ripples
985     * @param shallowLiquid a char that will be treated like shallow water when animating ripples
986     * @return a 2D array of lightness values from -255 to 255 but usually close to 0; can be passed to SquidLayers
987     */
988    public static int[][] generateLightnessModifiers(char[][] map, double frame, char deepLiquid, char shallowLiquid) {
989        int width = map.length;
990        int height = map[0].length;
991        int[][] portion = new int[width][height];
992        for (int i = 0; i < width; i++) {
993            for (int j = 0; j < height; j++) {
994                switch (map[i][j]) {
995                    case '\1':
996                    case '├':
997                    case '┤':
998                    case '┴':
999                    case '┬':
1000                    case '┌':
1001                    case '┐':
1002                    case '└':
1003                    case '┘':
1004                    case '│':
1005                    case '─':
1006                    case '┼':
1007                    case '#':
1008                        portion[i][j] = 30;
1009                        break;
1010                    case '.':
1011                        portion[i][j] = 0;
1012                        break;
1013                    case ':':
1014                        portion[i][j] = -15;
1015                        break;
1016                    case '+':
1017                    case '/':
1018                        portion[i][j] = -10;
1019                        break;
1020                    case ',':
1021                        portion[i][j] = (int) (70 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 25.0) / 2.5 - 0.45));
1022                        break;
1023                    case '~':
1024                        portion[i][j] = (int) (100 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 25.0) / 2.5 - 0.65));
1025                        break;
1026                    case '"':
1027                        portion[i][j] = (int) (75 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 35.0) / 4.0 - 1.5));
1028                        break;
1029                    case '^':
1030                        portion[i][j] = 40;
1031                        break;
1032                    default:
1033                        if (map[i][j] == deepLiquid)
1034                            portion[i][j] = (int) (180 * (PerlinNoise.noise(i / 5.0, j / 5.0, frame / 21.0) / 2.5 - 0.7));
1035                        else if (map[i][j] == shallowLiquid)
1036                            portion[i][j] = (int) (110 * (PerlinNoise.noise(i / 4.0, j / 4.0, frame / 30.0) / 2.5 - 0.45));
1037                        else portion[i][j] = 0;
1038                }
1039            }
1040        }
1041        return portion;
1042    }
1043
1044    /**
1045     * Given a char[][] for the map, produces a double[][] that can be used with FOV.calculateFOV(). It expects any
1046     * doors to be represented by '+' if closed or '/' if open (which can be caused by calling
1047     * DungeonUtility.closeDoors() ), any walls to be '#' or line drawing characters, and it doesn't care what other
1048     * chars are used (only doors, including open ones, and walls obscure light and thus have a resistance by default).
1049     *
1050     * @param map a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors()
1051     * @return a resistance map suitable for use with the FOV class
1052     */
1053    public static double[][] generateResistances(char[][] map) {
1054        int width = map.length;
1055        int height = map[0].length;
1056        double[][] portion = new double[width][height];
1057        for (int i = 0; i < width; i++) {
1058            for (int j = 0; j < height; j++) {
1059                switch (map[i][j]) {
1060                    case '\1':
1061                    case '├':
1062                    case '┤':
1063                    case '┴':
1064                    case '┬':
1065                    case '┌':
1066                    case '┐':
1067                    case '└':
1068                    case '┘':
1069                    case '│':
1070                    case '─':
1071                    case '┼':
1072                    case '#':
1073                        portion[i][j] = 1.0;
1074                        break;
1075                    case '/':
1076                    case '"':
1077                        portion[i][j] = 0.15;
1078                        break;
1079                    case '+':
1080                        portion[i][j] = 0.95;
1081                        break;
1082                    case '.':
1083                    case ',':
1084                    case '~':
1085                    case '^':
1086                        portion[i][j] = 0.0;
1087                        break;
1088                    default:
1089                        portion[i][j] = 0.0;
1090                }
1091            }
1092        }
1093        return portion;
1094    }
1095
1096    /**
1097     * Given a char[][] for the map, a Map of Character keys to Double values that will be used to determine costs, and
1098     * a double value for unhandled characters, produces a double[][] that can be used as a costMap by DijkstraMap. It
1099     * expects any doors to be represented by '+' if closed or '/' if open (which can be caused by calling
1100     * DungeonUtility.closeDoors() ) and any walls to be '#' or line drawing characters. In the parameter costs, there
1101     * does not need to be an entry for '#' or any box drawing characters, but if one is present for '#' it will apply
1102     * that cost to both '#' and all box drawing characters, and if one is not present it will default to a very high
1103     * number. For any other entry in costs, a char in the 2D char array that matches the key will correspond
1104     * (at the same x,y position in the returned 2D double array) to that key's value in costs. If a char is used in the
1105     * map but does not have a corresponding key in costs, it will be given the value of the parameter defaultValue.
1106     * <p/>
1107     * The values in costs are multipliers, so should not be negative, should only be 0.0 in cases where you want
1108     * infinite movement across all adjacent squares of that kind, should be higher than 1.0 for difficult terrain (2.0
1109     * and 3.0 are reasonable), should be between 0.0 and 1.0 for easy terrain, and should be 1.0 for normal terrain.
1110     * If a cell should not be possible to enter for this character, 999.0 should be a reasonable value for a cost.
1111     * <p/>
1112     * An example use for this would be to make a creature unable to enter any non-water cell (like a fish),
1113     * unable to enter doorways (like some mythological versions of vampires), or to make a wheeled vehicle take more
1114     * time to move across rubble or rough terrain.
1115     * <p/>
1116     * A potentially common case that needs to be addressed is NPC movement onto staircases in games that have them;
1117     * some games may find it desirable for NPCs to block staircases and others may not, but in either case you should
1118     * give both '&gt;' and '&lt;', the standard characters for staircases, the same value in costs.
1119     *
1120     * @param map          a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() .
1121     * @param costs        a Map of Character keys representing possible elements in map, and Double values for their cost.
1122     * @param defaultValue a double that will be used as the cost for any characters that don't have a key in costs.
1123     * @return a cost map suitable for use with DijkstraMap
1124     */
1125    public static double[][] generateCostMap(char[][] map, Map<Character, Double> costs, double defaultValue) {
1126        int width = map.length;
1127        int height = map[0].length;
1128        double[][] portion = new double[width][height];
1129        char current;
1130        for (int i = 0; i < width; i++) {
1131            for (int j = 0; j < height; j++) {
1132                current = map[i][j];
1133                if (costs.containsKey(current)) {
1134                    portion[i][j] = costs.get(current);
1135                } else {
1136                    switch (current) {
1137                        case '\1':
1138                        case '├':
1139                        case '┤':
1140                        case '┴':
1141                        case '┬':
1142                        case '┌':
1143                        case '┐':
1144                        case '└':
1145                        case '┘':
1146                        case '│':
1147                        case '─':
1148                        case '┼':
1149                        case '#':
1150                            portion[i][j] = (costs.containsKey('#'))
1151                                    ? costs.get('#')
1152                                    : squidpony.squidai.DijkstraMap.WALL;
1153                            break;
1154                        default:
1155                            portion[i][j] = defaultValue;
1156                    }
1157                }
1158            }
1159        }
1160        return portion;
1161    }
1162
1163    /**
1164     * Given a char[][] for the map, a Map of Character keys to Double values that will be used to determine costs, and
1165     * a double value for unhandled characters, produces a double[][] that can be used as a map by AStarSearch. It
1166     * expects any doors to be represented by '+' if closed or '/' if open (which can be caused by calling
1167     * DungeonUtility.closeDoors() ) and any walls to be '#' or line drawing characters. In the parameter costs, there
1168     * does not need to be an entry for '#' or any box drawing characters, but if one is present for '#' it will apply
1169     * that cost to both '#' and all box drawing characters, and if one is not present it will default to a negative
1170     * number, meaning it is impassable for AStarSearch. For any other entry in costs, a char in the 2D char array that
1171     * matches the key will correspond (at the same x,y position in the returned 2D double array) to that key's value in
1172     * costs. If a char is used in the map but does not have a corresponding key in costs, it will be given the value of
1173     * the parameter defaultValue, which is typically 0 unless a creature is limited to only moving in some terrain.
1174     * <p/>
1175     * The values in costs are different from those expected for DijkstraMap; negative numbers are impassable, 0 is the
1176     * cost for a normal walkable tile, and higher numbers are harder to enter.
1177     * <p/>
1178     * An example use for this would be to make a creature unable to enter any non-water cell (like a fish),
1179     * unable to enter doorways (like some mythological versions of vampires), or to make a wheeled vehicle take more
1180     * time to move across rubble or rough terrain.
1181     * <p/>
1182     * A potentially common case that needs to be addressed is NPC movement onto staircases in games that have them;
1183     * some games may find it desirable for NPCs to block staircases and others may not, but in either case you should
1184     * give both '&gt;' and '&lt;', the standard characters for staircases, the same value in costs.
1185     *
1186     * @param map          a dungeon, width by height, with any closed doors as '+' and open doors as '/' as per closeDoors() .
1187     * @param costs        a Map of Character keys representing possible elements in map, and Double values for their cost.
1188     * @param defaultValue a double that will be used as the cost for any characters that don't have a key in costs.
1189     * @return a cost map suitable for use with AStarSearch
1190     */
1191    public static double[][] generateAStarCostMap(char[][] map, Map<Character, Double> costs, double defaultValue) {
1192        int width = map.length;
1193        int height = map[0].length;
1194        double[][] portion = new double[width][height];
1195        char current;
1196        for (int i = 0; i < width; i++) {
1197            for (int j = 0; j < height; j++) {
1198                current = map[i][j];
1199                if (costs.containsKey(current)) {
1200                    portion[i][j] = costs.get(current);
1201                } else {
1202                    switch (current) {
1203                        case '\1':
1204                        case '├':
1205                        case '┤':
1206                        case '┴':
1207                        case '┬':
1208                        case '┌':
1209                        case '┐':
1210                        case '└':
1211                        case '┘':
1212                        case '│':
1213                        case '─':
1214                        case '┼':
1215                        case '#':
1216                            portion[i][j] = (costs.containsKey('#'))
1217                                    ? costs.get('#')
1218                                    : squidpony.squidai.DijkstraMap.WALL;
1219                            break;
1220                        default:
1221                            portion[i][j] = defaultValue;
1222                    }
1223                }
1224            }
1225        }
1226        return portion;
1227    }
1228
1229    public static double[][] translateAStarToDijkstra(double[][] astar)
1230    {
1231        if(astar == null) return null;
1232        if(astar.length <= 0 || astar[0].length <= 0)
1233            return new double[0][0];
1234        double[][] dijkstra = new double[astar.length][astar[0].length];
1235        for (int x = 0; x < astar.length; x++) {
1236            for (int y = 0; y < astar[x].length; y++) {
1237                if(astar[x][y] < 0)
1238                    dijkstra[x][y] = DijkstraMap.WALL;
1239                else
1240                    dijkstra[x][y] = DijkstraMap.FLOOR;
1241            }
1242        }
1243        return dijkstra;
1244    }
1245
1246    public static double[][] translateDijkstraToAStar(double[][] dijkstra)
1247    {
1248        if(dijkstra == null) return null;
1249        if(dijkstra.length <= 0 || dijkstra[0].length <= 0)
1250            return new double[0][0];
1251        double[][] astar = new double[dijkstra.length][dijkstra[0].length];
1252        for (int x = 0; x < dijkstra.length; x++) {
1253            for (int y = 0; y < dijkstra[x].length; y++) {
1254                if(dijkstra[x][y] > DijkstraMap.FLOOR)
1255                    astar[x][y] = -1;
1256                else
1257                    astar[x][y] = 1;
1258            }
1259        }
1260        return astar;
1261    }
1262
1263    /**
1264     * @param rng
1265     * @param map
1266     * @param acceptable
1267     * @param frustration The number of trials that this method can do. Usually 16 or
1268     *                    32.
1269     * @return A random cell in {@code map} whose symbol is in
1270     * {@code acceptable}. Or {@code null} if not found.
1271     */
1272    public static /* @Nullable */Coord getRandomCell(RNG rng, char[][] map, Set<Character> acceptable,
1273                                                     int frustration) {
1274        if (frustration < 0)
1275            throw new IllegalStateException("Frustration should not be negative");
1276        final int width = map.length;
1277        final int height = width == 0 ? 0 : map[0].length;
1278        if (width == 0 || height == 0)
1279            throw new IllegalStateException("Map must be non-empty to get a cell from it");
1280        int i = 0;
1281        while (i < frustration) {
1282            final int x = rng.nextInt(width);
1283            final int y = rng.nextInt(height);
1284            if (acceptable.contains(map[x][y]))
1285                return Coord.get(x, y);
1286            i++;
1287        }
1288        return null;
1289    }
1290
1291    /**
1292     * @param level dungeon/map level as 2D char array. x,y indexed
1293     * @param c     Coord to check
1294     * @return {@code true} if {@code c} is valid in {@code level},
1295     * {@code false} otherwise.
1296     */
1297    public static boolean inLevel(char[][] level, Coord c) {
1298        return inLevel(level, c.x, c.y);
1299    }
1300
1301    /**
1302     * @param level dungeon/map level as 2D char array. x,y indexed
1303     * @param x     x coordinate to check
1304     * @param y     y coordinate to check
1305     * @return {@code true} if {@code c} is valid in {@code level},
1306     * {@code false} otherwise.
1307     */
1308    public static boolean inLevel(char[][] level, int x, int y) {
1309        return 0 <= x && x < level.length && 0 <= y && y < level[x].length;
1310    }
1311
1312    /**
1313     * @param level a dungeon/map level as 2D array. x,y indexed
1314     * @param c     Coord to check
1315     * @return {@code true} if {@code c} is valid in {@code level},
1316     * {@code false} otherwise.
1317     */
1318    public static <T> boolean inLevel(T[][] level, Coord c) {
1319        return inLevel(level, c.x, c.y);
1320    }
1321
1322    /**
1323     * @param level a dungeon/map level as 2D array. x,y indexed
1324     * @param x     x coordinate to check
1325     * @param y     y coordinate to check
1326     * @return {@code true} if {@code c} is valid in {@code level},
1327     * {@code false} otherwise.
1328     */
1329    public static <T> boolean inLevel(T[][] level, int x, int y) {
1330        return 0 <= x && x < level.length && 0 <= y && y < level[x].length;
1331    }
1332
1333    /**
1334     * Quickly counts the number of char elements in level that are equal to match.
1335     *
1336     * @param level the 2D char array to count cells in
1337     * @param match the char to search for
1338     * @return the number of cells that matched
1339     */
1340    public static int countCells(char[][] level, char match) {
1341        if (level == null || level.length == 0)
1342            return 0;
1343        int counter = 0;
1344        for (int x = 0; x < level.length; x++) {
1345            for (int y = 0; y < level[x].length; y++) {
1346                if (level[x][y] == match) counter++;
1347            }
1348        }
1349        return counter;
1350    }
1351
1352    /**
1353     * For when you want to print a 2D char array. Prints on multiple lines, with a trailing newline.
1354     *
1355     * @param level a 2D char array to print with a trailing newline
1356     */
1357    public static void debugPrint(char[][] level) {
1358        if (level == null || level.length == 0 || level[0].length == 0)
1359            System.out.println("INVALID DUNGEON LEVEL");
1360        else {
1361            for (int y = 0; y < level[0].length; y++) {
1362                for (int x = 0; x < level.length; x++) {
1363                    System.out.print(level[x][y]);
1364                }
1365                System.out.println();
1366
1367            }
1368        }
1369    }
1370
1371    /**
1372     * Changes the outer edge of a char[][] to the wall char, '#'.
1373     *
1374     * @param map A char[][] that stores map data; will be modified in place
1375     * @return the modified-in-place map with its edge replaced with '#'
1376     */
1377    public static char[][] wallWrap(char[][] map) {
1378        int upperY = map[0].length - 1;
1379        int upperX = map.length - 1;
1380        for (int i = 0; i < map.length; i++) {
1381            map[i][0] = '#';
1382            map[i][upperY] = '#';
1383        }
1384        for (int i = 0; i < map[0].length; i++) {
1385            map[0][i] = '#';
1386            map[upperX][i] = '#';
1387        }
1388        return map;
1389    }
1390}