001package squidpony.squidgrid.mapping.styled;
002
003import squidpony.squidmath.LightRNG;
004import squidpony.squidmath.RNG;
005
006import java.util.Random;
007
008/**
009 * Generate a dungeon using Sean T. Barrett's Herringbone Wang Tiles method. http://nothings.org/gamedev/herringbone/
010 * Created by Tommy Ettinger on 3/10/2015.
011 * @author Tommy Ettinger - https://github.com/tommyettinger
012 */
013public class DungeonBoneGen {
014
015    /**
016     * Gets the current RNG.
017     * @return
018     */
019    public RNG getRng() {
020        return rng;
021    }
022
023    /**
024     * Sets the current RNG.
025     * @param rng
026     */
027    public void setRng(RNG rng) {
028        this.rng = rng;
029    }
030
031    /**
032     * The current RNG, a squidpony.squidmath.RNG
033     */
034    public RNG rng;
035    private int[][] c_color, h_color, v_color;
036
037    /**
038     * Returns the width, used as the first coordinate in any char[][] in this class.
039     * @return
040     */
041    public int getWidth() {
042        return wide;
043    }
044
045    /**
046     * Returns the height, used as the second coordinate in any char[][] in this class.
047     * @return
048     */
049    public int getHeight() {
050        return high;
051    }
052
053    private int wide = 0;
054    private int high = 0;
055
056    /**
057     * Get the char[][] dungeon that was last returned by generate(), or null if generate() or setDungeon have not been
058     * called. Uses x,y indexing.
059     * @return
060     */
061    public char[][] getDungeon() {
062        return dungeon;
063    }
064
065    /**
066     * Change the stored char[][] dungeon, using x,y indexing.
067     * @param dungeon
068     */
069    public void setDungeon(char[][] dungeon) {
070        this.dungeon = dungeon;
071        wide = dungeon.length;
072        high = dungeon[0].length;
073    }
074
075    /**
076     * Gets the char at a given x,y position.
077     * @param x
078     * @param y
079     * @return
080     */
081    public char get(int x, int y) {
082        return dungeon[x][y];
083    }
084
085    /**
086     * Sets the char at the given x,y position, storing it in this object. The dungeon this modifies is accessible with
087     * getDungeon() and can be set all at once with setDungeon().
088     * @param elem
089     * @param x
090     * @param y
091     */
092    public void put(char elem, int x, int y) {
093        dungeon[x][y] = elem;
094    }
095
096    /**
097     * The latest result of calling this class' generate() method.
098     */
099    private char[][] dungeon;
100
101    /**
102     * Constructs a DungeonGen that uses the given java.util.Random .
103     *
104     * @param random A Random number generator to be used during the dungeon generation; it will
105     *               be used to generate a seed for the internal RNG this class uses.
106     */
107    public DungeonBoneGen(Random random) {
108        this(new RNG(random.nextLong()));
109    }
110    /**
111     * Constructs a DungeonGen that uses the given squidpony.squidmath.RNG.
112     *
113     * @param random A squidpony.squidmath.RNG to be used during the dungeon generation.
114     */
115    public DungeonBoneGen(RNG random) {
116        rng = random;
117        c_color = new int[1][1];
118                h_color = new int[1][1];
119                v_color = new int[1][1];
120    }
121
122    /**
123     * Constructs a DungeonGen that uses the default RNG.
124     */
125    public DungeonBoneGen() {
126        this(new RNG(new LightRNG()));
127    }
128
129    private char[][] insert(char[][] mat, String[] items, int coord1, int coord2) {
130        if (mat.length == 0 || items.length == 0 || items[0].length() == 0)
131            return mat;
132
133        for (int i = coord1, i1 = 0; i1 < items.length; i++, i1++) {
134            char[] car = items[i1].toCharArray();
135            for (int j = coord2, j2 = 0; j2 < car.length; j++, j2++) {
136                if (i < 0 || j < 0 || i >= mat.length || j >= mat[i].length)
137                    continue;
138                mat[i][j] = car[j2];
139            }
140        }
141        return mat;
142
143    }
144
145    private Tile chooseTile(Tile[] list, int numlist, int[] y_positions, int[] x_positions) {
146        int a = c_color[y_positions[0]][x_positions[0]];
147        int b = c_color[y_positions[1]][x_positions[1]];
148        int c = c_color[y_positions[2]][x_positions[2]];
149        int d = c_color[y_positions[3]][x_positions[3]];
150        int e = c_color[y_positions[4]][x_positions[4]];
151        int f = c_color[y_positions[5]][x_positions[5]];
152        int i, n, match = Integer.MAX_VALUE, pass;
153        for (pass = 0; pass < 2; ++pass) {
154            n = 0;
155            // pass #1:
156            //   count number of variants that match this partial set of constraints
157            // pass #2:
158            //   stop on randomly selected match
159            for (i = 0; i < numlist; ++i) {
160                Tile tile = list[i];
161                if ((a < 0 || a == tile.a_constraint) &&
162                        (b < 0 || b == tile.b_constraint) &&
163                        (c < 0 || c == tile.c_constraint) &&
164                        (d < 0 || d == tile.d_constraint) &&
165                        (e < 0 || e == tile.e_constraint) &&
166                        (f < 0 || f == tile.f_constraint)) {
167                    n += 1;
168                    if (n > match) {
169                        // use list[i]
170                        // update constraints to reflect what we placed
171                        c_color[y_positions[0]][x_positions[0]] = tile.a_constraint;
172                        c_color[y_positions[1]][x_positions[1]] = tile.b_constraint;
173                        c_color[y_positions[2]][x_positions[2]] = tile.c_constraint;
174                        c_color[y_positions[3]][x_positions[3]] = tile.d_constraint;
175                        c_color[y_positions[4]][x_positions[4]] = tile.e_constraint;
176                        c_color[y_positions[5]][x_positions[5]] = tile.f_constraint;
177                        return tile;
178                    }
179                }
180            }
181            if (n == 0) {
182                return null;
183            }
184            match = rng.nextInt(n);
185        }
186        return null;
187    }
188
189    private Tile chooseTile(Tile[] list, int numlist, boolean upright, int[] y_positions, int[] x_positions) {
190        int a, b, c, d, e, f;
191        if (upright) {
192            a = h_color[y_positions[0]][x_positions[0]];
193            b = v_color[y_positions[1]][x_positions[1]];
194            c = v_color[y_positions[2]][x_positions[2]];
195            d = v_color[y_positions[3]][x_positions[3]];
196            e = v_color[y_positions[4]][x_positions[4]];
197            f = h_color[y_positions[5]][x_positions[5]];
198        } else {
199            a = h_color[y_positions[0]][x_positions[0]];
200            b = h_color[y_positions[1]][x_positions[1]];
201            c = v_color[y_positions[2]][x_positions[2]];
202            d = v_color[y_positions[3]][x_positions[3]];
203            e = h_color[y_positions[4]][x_positions[4]];
204            f = h_color[y_positions[5]][x_positions[5]];
205        }
206        int i, n, match = Integer.MAX_VALUE, pass;
207        for (pass = 0; pass < 2; ++pass) {
208            n = 0;
209            // pass #1:
210            //   count number of variants that match this partial set of constraints
211            // pass #2:
212            //   stop on randomly selected match
213            for (i = 0; i < numlist; ++i) {
214                Tile tile = list[i];
215                if ((a < 0 || a == tile.a_constraint) &&
216                        (b < 0 || b == tile.b_constraint) &&
217                        (c < 0 || c == tile.c_constraint) &&
218                        (d < 0 || d == tile.d_constraint) &&
219                        (e < 0 || e == tile.e_constraint) &&
220                        (f < 0 || f == tile.f_constraint)) {
221                    n += 1;
222                    if (n > match) {
223                        // use list[i]
224                        // update constraints to reflect what we placed
225                        if (upright) {
226                            h_color[y_positions[0]][x_positions[0]] = tile.a_constraint;
227                            v_color[y_positions[1]][x_positions[1]] = tile.b_constraint;
228                            v_color[y_positions[2]][x_positions[2]] = tile.c_constraint;
229                            v_color[y_positions[3]][x_positions[3]] = tile.d_constraint;
230                            v_color[y_positions[4]][x_positions[4]] = tile.e_constraint;
231                            h_color[y_positions[5]][x_positions[5]] = tile.f_constraint;
232                        } else {
233                            h_color[y_positions[0]][x_positions[0]] = tile.a_constraint;
234                            h_color[y_positions[1]][x_positions[1]] = tile.b_constraint;
235                            v_color[y_positions[2]][x_positions[2]] = tile.c_constraint;
236                            v_color[y_positions[3]][x_positions[3]] = tile.d_constraint;
237                            h_color[y_positions[4]][x_positions[4]] = tile.e_constraint;
238                            h_color[y_positions[5]][x_positions[5]] = tile.f_constraint;
239                        }
240                        return tile;
241                    }
242                }
243            }
244            if (n == 0) {
245                return null;
246            }
247            match = rng.nextInt(n);
248        }
249        return null;
250    }
251
252    /**
253     * Generate a dungeon given a TilesetType enum.
254     * The main way of generating dungeons with DungeonGen.
255     * Consider using DungeonGen.wallWrap to surround the edges with walls.
256     * Assigns the returned result to a member of this class, 'dungeon'.
257     *
258     * @param tt A TilesetType enum; try lots of these out to see how they look.
259     * @param w  Width of the dungeon to generate in chars.
260     * @param h  Height of the dungeon to generate in chars.
261     * @return A row-major char[][] with h rows and w columns; it will be filled with '#' for walls and '.' for floors.
262     */
263    public char[][] generate(TilesetType tt, int w, int h) {
264        return generate(tt.getTileset(), w, h);
265    }
266
267    /**
268     * Changes the outer edge of a char[][] to the wall char, '#'.
269     *
270     * @param map A char[][] that stores map data.
271     * @return
272     */
273    public static char[][] wallWrap(char[][] map) {
274        int upperY = map[0].length - 1;
275        int upperX = map.length - 1;
276        for (int i = 0; i < map.length; i++) {
277            map[i][0] = '#';
278            map[i][upperY] = '#';
279        }
280        for (int i = 0; i < map[0].length; i++) {
281            map[0][i] = '#';
282            map[upperX][i] = '#';
283        }
284        return map;
285    }
286
287    /**
288     * Changes the outer edge of this dungeon to the wall char, '#'.
289     *
290     * @return The modified dungeon, a char[][].
291     */
292    public char[][] wallWrap() {
293        int upperY = high - 1;
294        int upperX = wide - 1;
295        for (int i = 0; i < wide; i++) {
296            dungeon[i][0] = '#';
297            dungeon[i][upperY] = '#';
298        }
299        for (int i = 0; i < high; i++) {
300            dungeon[0][i] = '#';
301            dungeon[upperX][i] = '#';
302        }
303        return dungeon;
304    }
305
306    private boolean matchingAdjacent(int y, int x)
307    {
308        return c_color[y][x] == c_color[y + 1][x + 1];
309    }
310
311    private int changeColor(int old_color, int num_options) {
312
313        int offset = 1 + rng.nextInt(num_options - 1);
314        return (old_color + offset) % num_options;
315    }
316
317    /**
318     * Generate a dungeon given a Tileset.
319     * If you have your own Tileset gained by parsing your own JSON, use
320     * this to generate a dungeon using it. Consider using DungeonGen.wallWrap
321     * to surround the edges with walls. Assigns the returned result to a member
322     * of this class, 'dungeon'.
323     *
324     * @param ts A Tileset; if you don't have one of these available, use a TilesetType enum instead to select a predefined one.
325     * @param h  Height of the dungeon to generate in chars.
326     * @param w  Width of the dungeon to generate in chars.
327     * @return A row-major char[][] with h rows and w columns; it will be filled with '#' for walls and '.' for floors.
328     */
329    public char[][] generate(Tileset ts, int w, int h) {
330        wide = w;
331        high = h;
332        char[][] trans_output = new char[h][w];
333        int sidelen = ts.config.short_side_length;
334        int xmax = (w / sidelen) + 6;
335        int ymax = (h / sidelen) + 6;
336        if (xmax > 1006) {
337            return null;
338        }
339        if (ymax > 1006) {
340            return null;
341        }
342        if (ts.config.is_corner) {
343            c_color = new int[ymax][xmax];
344            int i = 0, j = 0, ypos = -1 * sidelen;
345            int[] cc = new int[]{ts.config.num_color_0, ts.config.num_color_1, ts.config.num_color_2, ts.config.num_color_3};
346
347            for (j = 0; j < ymax; ++j) {
348                for (i = 0; i < xmax; ++i) {
349                    int p = (i - j + 1) & 3; // corner type
350                    c_color[j][i] = rng.nextInt(cc[p]);
351                }
352            }
353
354            // Repetition reduction
355            // now go back through and make sure we don't have adjacent 3x2 vertices that are identical,
356            // to avoid really obvious repetition (which happens easily with extreme weights)
357            for (j = 0; j < ymax - 3; ++j) {
358                for (i = 0; i < xmax - 3; ++i) {
359                    int p = (i - j + 1) & 3; // corner type
360                    if (i + 3 >= 1006) {
361                        return null;
362                    }
363                    if (j + 3 >= 1006) {
364                        return null;
365                    }
366                    if (matchingAdjacent(j, i) && matchingAdjacent(j + 1, i) && matchingAdjacent(j + 2, i)
367                            && matchingAdjacent(j, i + 1) && matchingAdjacent(j + 1, i + 1) && matchingAdjacent(j + 2, i + 1)) {
368                        p = ((i + 1) - (j + 1) + 1) & 3;
369                        if (cc[p] > 1)
370                            c_color[j + 1][i + 1] = changeColor(c_color[j + 1][i + 1], cc[p]);
371                    }
372
373                    if (matchingAdjacent(j, i) && matchingAdjacent(j, i + 1) && matchingAdjacent(j, i + 2)
374                            && matchingAdjacent(j + 1, i) && matchingAdjacent(j + 1, i + 1) && matchingAdjacent(j + 1, i + 2)) {
375                        p = ((i + 2) - (j + 1) + 1) & 3;
376                        if (cc[p] > 1)
377                            c_color[j + 1][i + 2] = changeColor(c_color[j + 1][i + 2], cc[p]);
378                    }
379                }
380            }
381
382
383            for (j = -1; ypos < h; ++j) {
384                // a general herringbone row consists of:
385                //    horizontal left block, the bottom of a previous vertical, the top of a new vertical
386                int phase = (j & 3);
387                // displace horizontally according to pattern
388                if (phase == 0) {
389                    i = 0;
390                } else {
391                    i = phase - 4;
392                }
393                for (; ; i += 4) {
394                    int xpos = i * sidelen;
395                    if (xpos >= w)
396                        break;
397                    // horizontal left-block
398                    if (xpos + sidelen * 2 >= 0 && ypos >= 0) {
399                        Tile t = chooseTile(
400                                ts.h_tiles, ts.h_tiles.length,
401                                new int[]{j + 2, j + 2, j + 2, j + 3, j + 3, j + 3},
402                                new int[]{i + 2, i + 3, i + 4, i + 2, i + 3, i + 4});
403
404                        if (t == null)
405                            return null;
406
407                        trans_output = insert(trans_output, t.data, ypos, xpos);
408                    }
409                    xpos += sidelen * 2;
410                    // now we're at the end of a previous vertical one
411                    xpos += sidelen;
412                    // now we're at the start of a new vertical one
413                    if (xpos < w) {
414                        Tile t = chooseTile(
415                                ts.v_tiles, ts.v_tiles.length,
416                                new int[]{j + 2, j + 3, j + 4, j + 2, j + 3, j + 4},
417                                new int[]{i + 5, i + 5, i + 5, i + 6, i + 6, i + 6});
418
419                        if (t == null)
420                            return null;
421                        trans_output = insert(trans_output, t.data, ypos, xpos);
422                    }
423                }
424                ypos += sidelen;
425            }
426        } else {
427            int i = 0, j = -1, ypos;
428            v_color = new int[ymax][xmax];
429            h_color = new int[ymax][xmax];
430            for (int yy = 0; yy < ymax; yy++) {
431                for (int xx = 0; xx < xmax; xx++) {
432                    v_color[yy][xx] = -1;
433                    h_color[yy][xx] = -1;
434                }
435            }
436
437            ypos = -1 * sidelen;
438            for (j = -1; ypos < h; ++j) {
439                // a general herringbone row consists of:
440                //    horizontal left block, the bottom of a previous vertical, the top of a new vertical
441                int phase = (j & 3);
442                // displace horizontally according to pattern
443                if (phase == 0) {
444                    i = 0;
445                } else {
446                    i = phase - 4;
447                }
448                for (; ; i += 4) {
449                    int xpos = i * sidelen;
450                    if (xpos >= w)
451                        break;
452                    // horizontal left-block
453                    if (xpos + sidelen * 2 >= 0 && ypos >= 0) {
454                        Tile t = chooseTile(
455                                ts.h_tiles, ts.h_tiles.length, false,
456                                new int[]{j + 2, j + 2, j + 2, j + 2, j + 3, j + 3},
457                                new int[]{i + 2, i + 3, i + 2, i + 4, i + 2, i + 3});
458
459                        if (t == null)
460                            return null;
461                        trans_output = insert(trans_output, t.data, ypos, xpos);
462                    }
463                    xpos += sidelen * 2;
464                    // now we're at the end of a previous vertical one
465                    xpos += sidelen;
466                    // now we're at the start of a new vertical one
467                    if (xpos < w) {
468                        Tile t = chooseTile(
469                                ts.v_tiles, ts.v_tiles.length, true,
470                                new int[]{j + 2, j + 2, j + 2, j + 3, j + 3, j + 4},
471                                new int[]{i + 5, i + 5, i + 6, i + 5, i + 6, i + 5});
472
473                        if (t == null)
474                            return null;
475                        trans_output = insert(trans_output, t.data, ypos, xpos);
476                    }
477                }
478                ypos += sidelen;
479            }
480        }
481        char[][] output = new char[w][h];
482        for (int x = 0; x < w; x++) {
483            for (int y = 0; y < h; y++) {
484                output[x][y] = trans_output[y][x];
485            }
486        }
487        dungeon = output;
488        return output;
489    }
490
491    /**
492     * Provides a string representation of the latest generated dungeon.
493     *
494     * @return
495     */
496    @Override
497        public String toString() {
498        char[][] trans = new char[high][wide];
499        for (int x = 0; x < wide; x++) {
500            for (int y = 0; y < high; y++) {
501                trans[y][x] = dungeon[x][y];
502            }
503        }
504        StringBuffer sb = new StringBuffer();
505        for (int row = 0; row < high; row++) {
506            sb.append(trans[row]);
507            sb.append('\n');
508        }
509        return sb.toString();
510    }
511
512    /**
513     * Gets an array of all herringbone tiles associated with a TilesetType enum.
514     *
515     * @param tt a TilesetType enum
516     * @return an array of 2D char arrays representing tiles
517     */
518    public String[][] getTiles(TilesetType tt) {
519        final Tileset ts = tt.getTileset();
520
521        String[][] result = new String[ts.h_tiles.length + ts.v_tiles.length][];
522        for (int i = 0; i < ts.h_tiles.length; i++) {
523            result[i] = ts.h_tiles[i].data;
524        }
525        for (int i = 0; i < ts.v_tiles.length; i++) {
526            result[ts.h_tiles.length + i] = ts.v_tiles[i].data;
527        }
528        return result;
529    }
530}