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