001package squidpony.squidgrid.mapping; 002 003import squidpony.squidmath.*; 004 005import java.util.ArrayList; 006import java.util.List; 007 008/** 009 * Generate dungeons based on a random, winding, looping path through 2D space. Uses techniques from MixedGenerator. 010 * Uses a Moore Curve, which is related to Hilbert Curves but loops back to its starting point, and stretches and 011 * distorts the grid to make sure a visual correlation isn't obvious. This supports the getEnvironment() method, which 012 * can be used in conjunction with RoomFinder to find where separate room, corridor, and cave areas have been placed. 013 * <br> 014 * To get a sense of what kinds of map this generates, you can look at a sample map on 015 * https://gist.github.com/tommyettinger/93b47048fc8a209a9712 , which also includes a snippet of Java code that can 016 * generate that map. 017 * <br> 018 * The name comes from a vivid dream I had about gigantic, multi-colored snakes that completely occupied a roguelike 019 * dungeon. Shortly after, I made the connection to the Australian mythology I'd heard about the Rainbow Serpent, which 020 * in some stories dug water-holes and was similarly gigantic. 021 * Created by Tommy Ettinger on 10/24/2015. 022 */ 023public class SerpentMapGenerator implements IDungeonGenerator { 024 private MixedGenerator mix; 025 private int[] columns, rows; 026 027 /** 028 * This prepares a map generator that will generate a map with the given width and height, using the given IRNG. 029 * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing 030 * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the 031 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 032 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 033 * 034 * @param width the width of the final map in cells 035 * @param height the height of the final map in cells 036 * @param rng an IRNG object to use for random choices; this make a lot of random choices. 037 * @see MixedGenerator 038 */ 039 public SerpentMapGenerator(int width, int height, IRNG rng) { 040 this(width, height, rng, false); 041 } 042 043 /** 044 * This prepares a map generator that will generate a map with the given width and height, using the given IRNG. 045 * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing 046 * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the 047 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 048 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 049 * 050 * @param width the width of the final map in cells 051 * @param height the height of the final map in cells 052 * @param random an IRNG object to use for random choices; this make a lot of random choices. 053 * @param symmetrical true if this should generate a bi-radially symmetric map, false for a typical map 054 * @see MixedGenerator 055 */ 056 public SerpentMapGenerator(int width, int height, IRNG random, boolean symmetrical) { 057 if (width <= 2 || height <= 2) 058 throw new IllegalArgumentException("width and height must be greater than 2"); 059 CoordPacker.init(); 060 long columnAlterations = random.nextLong(0x1000000000000L); 061 float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f); 062 long rowAlterations = random.nextLong(0x1000000000000L); 063 float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f); 064 065 columns = new int[16]; 066 rows = new int[16]; 067 int csum = 0, rsum = 0; 068 long b = 7; 069 for (int i = 0; i < 16; i++, b <<= 3) { 070 columns[i] = csum + (int) (columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b))); 071 csum += (int) (columnBase * (3 + Long.bitCount(columnAlterations & b))); 072 rows[i] = rsum + (int) (rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b))); 073 rsum += (int) (rowBase * (3 + Long.bitCount(rowAlterations & b))); 074 } 075 int cs = width - csum; 076 int rs = height - rsum; 077 int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs; 078 for (int i = 0; i <= 7; i++) { 079 cs2 = 0; 080 rs2 = 0; 081 columns[i] -= cs2; 082 rows[i] -= rs2; 083 } 084 for (int i = 15; i >= 8; i--) { 085 cs3 = cs3 * (i - 8) / 8; 086 rs3 = rs3 * (i - 8) / 8; 087 columns[i] += cs3; 088 rows[i] += rs3; 089 } 090 091 List<Coord> points = new ArrayList<>(80); 092 Coord temp; 093 for (int i = 0, m = random.nextInt(64), r; i < 256; r = random.between(4, 12), i += r, m += r) { 094 temp = CoordPacker.mooreToCoord(m); 095 points.add(Coord.get(columns[temp.x], rows[temp.y])); 096 } 097 points.add(points.get(0)); 098 if (symmetrical) { 099 mix = new SymmetryDungeonGenerator(width, height, random, 100 SymmetryDungeonGenerator.removeSomeOverlap(width, height, points)); 101 } else 102 mix = new MixedGenerator(width, height, random, points); 103 } 104 105 /** 106 * This prepares a map generator that will generate a map with the given width and height, using the given IRNG. 107 * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing 108 * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the 109 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 110 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 111 * 112 * @param width the width of the final map in cells 113 * @param height the height of the final map in cells 114 * @param rng an IRNG object to use for random choices; this make a lot of random choices. 115 * @param branchingChance the chance from 0.0 to 1.0 that each room will branch at least once 116 * @see MixedGenerator 117 */ 118 public SerpentMapGenerator(int width, int height, IRNG rng, double branchingChance) { 119 this(width, height, rng, branchingChance, false); 120 } 121 122 /** 123 * This prepares a map generator that will generate a map with the given width and height, using the given IRNG. 124 * The intended purpose is to carve a long path that loops through the whole dungeon, while hopefully maximizing 125 * the amount of rooms the player encounters. You call the different carver-adding methods to affect what the 126 * dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), defaulting to only 127 * caves if none are called. You call generate() after adding carvers, which returns a char[][] for a map. 128 * 129 * @param width the width of the final map in cells 130 * @param height the height of the final map in cells 131 * @param random an IRNG object to use for random choices; this make a lot of random choices. 132 * @param branchingChance the chance from 0.0 to 1.0 that each room will branch at least once 133 * @param symmetrical true if this should generate a bi-radially symmetric map, false for a typical map 134 * @see MixedGenerator 135 */ 136 public SerpentMapGenerator(int width, int height, IRNG random, double branchingChance, boolean symmetrical) { 137 if (width <= 2 || height <= 2) 138 throw new IllegalArgumentException("width and height must be greater than 2"); 139 CoordPacker.init(); 140 long columnAlterations = random.nextLong(0x1000000000000L); 141 float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f); 142 long rowAlterations = random.nextLong(0x1000000000000L); 143 float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f); 144 145 columns = new int[16]; 146 rows = new int[16]; 147 int csum = 0, rsum = 0; 148 long b = 7; 149 for (int i = 0; i < 16; i++, b <<= 3) { 150 columns[i] = csum + (int) (columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b))); 151 csum += (int) (columnBase * (3 + Long.bitCount(columnAlterations & b))); 152 rows[i] = rsum + (int) (rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b))); 153 rsum += (int) (rowBase * (3 + Long.bitCount(rowAlterations & b))); 154 } 155 int cs = width - csum; 156 int rs = height - rsum; 157 int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs; 158 for (int i = 0; i <= 7; i++) { 159 cs2 = 0; 160 rs2 = 0; 161 columns[i] -= cs2; 162 rows[i] -= rs2; 163 } 164 for (int i = 15; i >= 8; i--) { 165 cs3 = cs3 * (i - 8) / 8; 166 rs3 = rs3 * (i - 8) / 8; 167 columns[i] += cs3; 168 rows[i] += rs3; 169 } 170 171 OrderedMap<Coord, List<Coord>> connections = new OrderedMap<>(80); 172 Coord temp, t; 173 int m = random.nextInt(64), r = random.between(4, 12); 174 temp = CoordPacker.mooreToCoord(m); 175 Coord starter = CoordPacker.mooreToCoord(m); 176 m += r; 177 for (int i = r; i < 256; i += r, m += r) { 178 List<Coord> cl = new ArrayList<>(4); 179 cl.add(Coord.get(columns[temp.x], rows[temp.y])); 180 temp = CoordPacker.mooreToCoord(m); 181 r = random.between(4, 12); 182 for (int j = 0, p = r - 1; 183 j < 3 && p > 2 && Math.min(random.nextDouble(), random.nextDouble()) < branchingChance; 184 j++, p -= random.between(1, p)) { 185 t = CoordPacker.mooreToCoord(m + p); 186 cl.add(Coord.get(columns[t.x], rows[t.y])); 187 } 188 connections.put(Coord.get(columns[temp.x], rows[temp.y]), cl); 189 } 190 connections.get(Coord.get(columns[temp.x], rows[temp.y])).add( 191 Coord.get(columns[starter.x], rows[starter.y])); 192 if (symmetrical) { 193 mix = new SymmetryDungeonGenerator(width, height, random, 194 SymmetryDungeonGenerator.removeSomeOverlap(width, height, connections)); 195 } else 196 mix = new MixedGenerator(width, height, random, connections); 197 198 } 199 200 /** 201 * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves 202 * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make 203 * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically 204 * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10 205 * between the count of putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers() is reasonable. 206 * 207 * @param count the number of carvers making caves between rooms; only matters in relation to other carvers 208 * @see MixedGenerator 209 */ 210 public void putCaveCarvers(int count) { 211 mix.putCaveCarvers(count); 212 } 213 214 /** 215 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 216 * with a random size in a box shape at the start and end, and a small room at the corner if there is one. If count 217 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 218 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 219 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 220 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 221 * and putRoundRoomCarvers() is reasonable. 222 * 223 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 224 * to other carvers 225 * @see MixedGenerator 226 */ 227 public void putBoxRoomCarvers(int count) { 228 mix.putBoxRoomCarvers(count); 229 } 230 231 /** 232 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 233 * with a random size in a box shape at the start and end, and a small room at the corner if there is one. This also 234 * ensures walls will be placed around the room, only allowing corridors and small cave openings to pass. If count 235 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 236 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 237 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 238 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 239 * and putRoundRoomCarvers() is reasonable. 240 * 241 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 242 * to other carvers 243 * @see MixedGenerator 244 */ 245 public void putWalledBoxRoomCarvers(int count) { 246 mix.putWalledBoxRoomCarvers(count); 247 } 248 249 /** 250 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 251 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 252 * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 253 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 254 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 255 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 256 * and putRoundRoomCarvers() is reasonable. 257 * 258 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 259 * to other carvers 260 * @see MixedGenerator 261 */ 262 public void putRoundRoomCarvers(int count) { 263 mix.putRoundRoomCarvers(count); 264 } 265 266 /** 267 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 268 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 269 * one. This also ensures walls will be placed around the room, only allowing corridors and small cave openings to 270 * pass. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 271 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 272 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 273 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 274 * and putRoundRoomCarvers() is reasonable. 275 * 276 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 277 * to other carvers 278 * @see MixedGenerator 279 */ 280 public void putWalledRoundRoomCarvers(int count) { 281 mix.putWalledRoundRoomCarvers(count); 282 } 283 284 /** 285 * This generates a new map by stretching a 16x16 grid of potential rooms to fit the width and height passed to the 286 * constructor, randomly expanding columns and rows before contracting the whole to fit perfectly. This uses the 287 * Moore Curve, a space-filling curve that loops around on itself, to guarantee that the rooms will always have a 288 * long path through the dungeon that, if followed completely, will take you back to your starting room. Some small 289 * branches are possible, and large rooms may merge with other rooms nearby. This uses MixedGenerator. 290 * 291 * @return a char[][] where '#' is a wall and '.' is a floor or corridor; x first y second 292 * @see MixedGenerator 293 */ 294 public char[][] generate() { 295 return mix.generate(); 296 } 297 298 299 /** 300 * Gets a 2D array of int constants, each representing a type of environment corresponding to a static field of 301 * MixedGenerator. This array will have the same size as the last char 2D array produced by generate(); the value 302 * of this method if called before generate() is undefined, but probably will be a 2D array of all 0 (UNTOUCHED). 303 * <ul> 304 * <li>MixedGenerator.UNTOUCHED, equal to 0, is used for any cells that aren't near a floor.</li> 305 * <li>MixedGenerator.ROOM_FLOOR, equal to 1, is used for floor cells inside wide room areas.</li> 306 * <li>MixedGenerator.ROOM_WALL, equal to 2, is used for wall cells around wide room areas.</li> 307 * <li>MixedGenerator.CAVE_FLOOR, equal to 3, is used for floor cells inside rough cave areas.</li> 308 * <li>MixedGenerator.CAVE_WALL, equal to 4, is used for wall cells around rough cave areas.</li> 309 * <li>MixedGenerator.CORRIDOR_FLOOR, equal to 5, is used for floor cells inside narrow corridor areas.</li> 310 * <li>MixedGenerator.CORRIDOR_WALL, equal to 6, is used for wall cells around narrow corridor areas.</li> 311 * </ul> 312 * 313 * @return a 2D int array where each element is an environment type constant in MixedGenerator 314 */ 315 public int[][] getEnvironment() { 316 return mix.getEnvironment(); 317 } 318 319 public char[][] getDungeon() { 320 return mix.getDungeon(); 321 } 322}