001package squidpony.squidgrid.mapping; 002 003import squidpony.squidmath.Coord; 004import squidpony.squidmath.CoordPacker; 005import squidpony.squidmath.DDALine; 006import squidpony.squidmath.RNG; 007 008import java.util.ArrayList; 009import java.util.LinkedHashMap; 010import java.util.List; 011 012/** 013 * Generate dungeons with between 1 and 3 primary "lanes" going from the upper left "base" to the bottom right "base" 014 * (and vice versa, since this is symmetrical). Also fills the area not covered by lanes with "jungle" (random, but 015 * symmetrical, room or cave connections). Dungeons are produced by MixedGenerator, like those SerpentMapGenerator 016 * makes, but include the wide lanes going from corner to corner. You can call different methods like putCaveCarvers(), 017 * putBoxRoomCarvers(), putWalledRoundRoomCarvers(), etc. to affect the "jungle", which defaults to caves unless one or 018 * more of the putXXXCarvers methods was called. The lanes are always 5 floor cells wide, measured 8-way. This supports 019 * the getEnvironment() method, which can be used in conjunction with RoomFinder to find where separate room, corridor, 020 * and cave areas have been placed. 021 * <br> 022 * A preview can be seen here https://gist.github.com/tommyettinger/4f57cff23eead11b17bf , with dungeons created with 023 * one, two, and three lanes, and only using box-shaped rooms for "jungle." Currently, the two-lane dungeon seems to be 024 * ideal for maps that aren't incredibly large; the samples are 80x80, but larger maps may have better jungle layout 025 * with three lanes than those three-lane maps can manage on smaller sizes. Another potential advantage of the two-lane 026 * approach is that it can be used to generate a "ring" of wide paths around a central "core" of jungle, which wasn't 027 * originally intended as a use of this generator but could be very useful for games that, for instance, want guards 028 * patrolling an obvious ring, while the player, monsters, and/or other prisoners start in the jungle. 029 * Created by Tommy Ettinger on 10/24/2015. 030 */ 031public class LanesMapGenerator { 032 protected SymmetryDungeonGenerator mix; 033 protected int[] columns, rows; 034 protected RNG random; 035 protected int lanes; 036 /** 037 * This prepares a map generator that will generate a map with the given width and height, using the given RNG. 038 * The dungeon will have the specified number of wide lanes going from upper left to lower right, possibly taking a 039 * longer path to approach the other corners. You call the different carver-adding methods to affect what the 040 * non-lane portion of the dungeon will look like, putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers(), 041 * defaulting to only caves if none are called. You call generate() after adding carvers, which returns a char[][] 042 * for a map. 043 * @param width the width of the final map in cells 044 * @param height the height of the final map in cells 045 * @param rng an RNG object to use for random choices; this make a lot of random choices. 046 * @param lanes between 1 and 3; the number of wide paths to generate going from upper left to lower right. 047 * @see MixedGenerator 048 */ 049 public LanesMapGenerator(int width, int height, RNG rng, int lanes) 050 { 051 if(width <= 8 || height <= 8) 052 throw new IllegalArgumentException("width and height must be greater than 8"); 053 this.lanes = (lanes < 1 || lanes > 3) ? 1 : lanes; 054 random = rng; 055 /* 056 long columnAlterations = random.nextLong(); 057 float columnBase = width / (Long.bitCount(columnAlterations) + 16.0f); 058 long rowAlterations = random.nextLong(); 059 float rowBase = height / (Long.bitCount(rowAlterations) + 16.0f); 060 061 columns = new int[32]; 062 rows = new int[32]; 063 int csum = 0, rsum = 0; 064 long b = 3; 065 for (int i = 0; i < 32; i++, b <<= 2) { 066 columns[i] = csum + (int)(columnBase * 0.5f * (1 + Long.bitCount(columnAlterations & b))); 067 csum += (int)(columnBase * (1 + Long.bitCount(columnAlterations & b))); 068 rows[i] = rsum + (int)(rowBase * 0.5f * (1 + Long.bitCount(rowAlterations & b))); 069 rsum += (int)(rowBase * (1 + Long.bitCount(rowAlterations & b))); 070 } 071 int cs = (width - csum); 072 int rs = (height - rsum); 073 int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs; 074 for (int i = 15; i >= 0; i--) { 075 cs2= cs2 * i / 15; 076 rs2 = rs2 * i / 15; 077 columns[i] -= cs2; 078 rows[i] -= rs2; 079 } 080 for (int i = 15; i >= 16; i--) { 081 cs3 = cs3 * (i - 16) / 16; 082 rs3 = rs3 * (i - 16) / 16; 083 columns[i] += cs3; 084 rows[i] += rs3; 085 } 086 */ 087 long columnAlterations = random.nextLong(0x1000000000000L); 088 float columnBase = width / (Long.bitCount(columnAlterations) + 48.0f); 089 long rowAlterations = random.nextLong(0x1000000000000L); 090 float rowBase = height / (Long.bitCount(rowAlterations) + 48.0f); 091 092 columns = new int[16]; 093 rows = new int[16]; 094 int csum = 0, rsum = 0; 095 long b = 7; 096 for (int i = 0; i < 16; i++, b <<= 3) { 097 columns[i] = csum + (int)(columnBase * 0.5f * (3 + Long.bitCount(columnAlterations & b))); 098 csum += (int)(columnBase * (3 + Long.bitCount(columnAlterations & b))); 099 rows[i] = rsum + (int)(rowBase * 0.5f * (3 + Long.bitCount(rowAlterations & b))); 100 rsum += (int)(rowBase * (3 + Long.bitCount(rowAlterations & b))); 101 } 102 int cs = (width - csum); 103 int rs = (height - rsum); 104 int cs2 = cs, rs2 = rs, cs3 = cs, rs3 = rs; 105 for (int i = 0; i <= 7; i++) { 106 cs2= cs2 * i / 7; 107 rs2 = rs2 * i / 7; 108 columns[i] -= cs2; 109 rows[i] -= rs2; 110 } 111 for (int i = 15; i >= 8; i--) { 112 cs3 = cs3 * (i - 8) / 8; 113 rs3 = rs3 * (i - 8) / 8; 114 columns[i] += cs3; 115 rows[i] += rs3; 116 } 117 118 119 LinkedHashMap<Coord, List<Coord>> connections = new LinkedHashMap<>(80); 120 Coord temp, t; 121 int m = random.nextInt(32), r = random.between(8, 24); 122 temp = CoordPacker.hilbertToCoord(m); 123 Coord starter = CoordPacker.hilbertToCoord(m); 124 m += r; 125 for (int i = r; i < 256 && m < 256 - 9; i += r, m += r) { 126 List<Coord> cl = new ArrayList<>(4); 127 cl.add(Coord.get(columns[temp.x], rows[temp.y])); 128 temp = CoordPacker.hilbertToCoord(m); 129 r = random.between(8, 24); 130 for (int j = 0, p = r - 1; 131 j < 3 && p > 2 && Math.min(random.nextDouble(), random.nextDouble()) < 0.2; 132 j++, p -= random.between(1, p)) { 133 t = CoordPacker.hilbertToCoord(m + p); 134 cl.add(Coord.get(columns[t.x], rows[t.y])); 135 } 136 connections.put(Coord.get(columns[temp.x], rows[temp.y]), cl); 137 } 138 connections.get(Coord.get(columns[temp.x], rows[temp.y])).add( 139 Coord.get(columns[starter.x], rows[starter.y])); 140 mix = new SymmetryDungeonGenerator(width, height, random, connections, 0.6f); 141 boolean[][] fixed = new boolean[width][height]; 142 143 if(lanes != 2) 144 { 145 List<Coord> path = DDALine.line(3, 3, width - 4, height - 4); 146 for(Coord c : path) 147 { 148 for (int x = c.x - 2; x <= c.x + 2; x++) { 149 for (int y = c.y - 2; y <= c.y + 2; y++) { 150 fixed[x][y] = true; 151 } 152 } 153 } 154 } 155 if(lanes > 1) 156 { 157 List<Coord> path = DDALine.line(3, 3, 3, height - 4); 158 path.addAll(DDALine.line(3, 3, width - 4, 3)); 159 for(Coord c : path) 160 { 161 for (int x = c.x - 2; x <= c.x + 2; x++) { 162 for (int y = c.y - 2; y <= c.y + 2; y++) { 163 fixed[x][y] = true; 164 } 165 } 166 } 167 } 168 mix.setFixedRooms(fixed); 169 } 170 171 172 /** 173 * Changes the number of "carvers" that will create caves from one room to the next. If count is 0 or less, no caves 174 * will be made. If count is at least 1, caves are possible, and higher numbers relative to the other carvers make 175 * caves more likely. Carvers are shuffled when used, then repeat if exhausted during generation. Since typically 176 * about 30-40 rooms are carved, large totals for carver count aren't really needed; aiming for a total of 10 177 * between the count of putCaveCarvers(), putBoxRoomCarvers(), and putRoundRoomCarvers() is reasonable. 178 * @see MixedGenerator 179 * @param count the number of carvers making caves between rooms; only matters in relation to other carvers 180 */ 181 public void putCaveCarvers(int count) 182 { 183 mix.putCaveCarvers(count); 184 } 185 /** 186 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 187 * 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 188 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 189 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 190 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 191 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 192 * and putRoundRoomCarvers() is reasonable. 193 * @see MixedGenerator 194 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 195 * to other carvers 196 */ 197 public void putBoxRoomCarvers(int count) 198 { 199 mix.putBoxRoomCarvers(count); 200 } 201 /** 202 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 203 * 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 204 * ensures walls will be placed around the room, only allowing corridors and small cave openings to pass. If count 205 * is 0 or less, no box-shaped rooms will be made. If count is at least 1, box-shaped rooms are possible, and higher 206 * numbers relative to the other carvers make box-shaped rooms more likely. Carvers are shuffled when used, then 207 * repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 208 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 209 * and putRoundRoomCarvers() is reasonable. 210 * @see MixedGenerator 211 * @param count the number of carvers making box-shaped rooms and corridors between them; only matters in relation 212 * to other carvers 213 */ 214 public void putWalledBoxRoomCarvers(int count) 215 { 216 mix.putWalledBoxRoomCarvers(count); 217 } 218 /** 219 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 220 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 221 * one. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 222 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 223 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 224 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 225 * and putRoundRoomCarvers() is reasonable. 226 * @see MixedGenerator 227 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 228 * to other carvers 229 */ 230 public void putRoundRoomCarvers(int count) 231 { 232 mix.putRoundRoomCarvers(count); 233 } 234 235 /** 236 * Changes the number of "carvers" that will create right-angle corridors from one room to the next, create rooms 237 * with a random size in a circle shape at the start and end, and a small circular room at the corner if there is 238 * one. This also ensures walls will be placed around the room, only allowing corridors and small cave openings to 239 * pass. If count is 0 or less, no circular rooms will be made. If count is at least 1, circular rooms are possible, 240 * and higher numbers relative to the other carvers make circular rooms more likely. Carvers are shuffled when used, 241 * then repeat if exhausted during generation. Since typically about 30-40 rooms are carved, large totals for carver 242 * count aren't really needed; aiming for a total of 10 between the count of putCaveCarvers(), putBoxRoomCarvers(), 243 * and putRoundRoomCarvers() is reasonable. 244 * @see MixedGenerator 245 * @param count the number of carvers making circular rooms and corridors between them; only matters in relation 246 * to other carvers 247 */ 248 public void putWalledRoundRoomCarvers(int count) 249 { 250 mix.putWalledRoundRoomCarvers(count); 251 } 252 253 /** 254 * This generates a new map by stretching a 16x16 grid of potential rooms to fit the width and height passed to the 255 * constructor, randomly expanding columns and rows before contracting the whole to fit perfectly. This uses the 256 * Moore Curve, a space-filling curve that loops around on itself, to guarantee that the rooms will always have a 257 * long path through the dungeon that, if followed completely, will take you back to your starting room. Some small 258 * branches are possible, and large rooms may merge with other rooms nearby. This uses MixedGenerator. 259 * @see MixedGenerator 260 * @return a char[][] where '#' is a wall and '.' is a floor or corridor; x first y second 261 */ 262 public char[][] generate() 263 { 264 return mix.generate(); 265 } 266 267 /** 268 * Gets a 2D array of int constants, each representing a type of environment corresponding to a static field of 269 * MixedGenerator. This array will have the same size as the last char 2D array prduced by generate(), and the value 270 * of this method if called before generate() is undefined, but probably will be a 2D array of all 0 (UNTOUCHED). 271 * <ul> 272 * <li>MixedGenerator.UNTOUCHED, equal to 0, is used for any cells that aren't near a floor.</li> 273 * <li>MixedGenerator.ROOM_FLOOR, equal to 1, is used for floor cells inside wide room areas.</li> 274 * <li>MixedGenerator.ROOM_WALL, equal to 2, is used for wall cells around wide room areas.</li> 275 * <li>MixedGenerator.CAVE_FLOOR, equal to 3, is used for floor cells inside rough cave areas.</li> 276 * <li>MixedGenerator.CAVE_WALL, equal to 4, is used for wall cells around rough cave areas.</li> 277 * <li>MixedGenerator.CORRIDOR_FLOOR, equal to 5, is used for floor cells inside narrow corridor areas.</li> 278 * <li>MixedGenerator.CORRIDOR_WALL, equal to 6, is used for wall cells around narrow corridor areas.</li> 279 * </ul> 280 * @return a 2D int array where each element is an environment type constant in MixedGenerator 281 */ 282 public int[][] getEnvironment() 283 { 284 return mix.getEnvironment(); 285 } 286}