ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/random_maps/layout.C
(Generate patch)

Comparing deliantra/server/random_maps/layout.C (file contents):
Revision 1.3 by root, Thu Jul 1 01:22:44 2010 UTC vs.
Revision 1.34 by root, Sat Nov 17 23:40:02 2018 UTC

1/* 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG. 2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 * 3 *
4 * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team 4 * Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
5 * Copyright (©) 2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
6 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
5 * 7 *
6 * Deliantra is free software: you can redistribute it and/or modify it under 8 * Deliantra is free software: you can redistribute it and/or modify it under
7 * the terms of the Affero GNU General Public License as published by the 9 * the terms of the Affero GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or (at your 10 * Free Software Foundation, either version 3 of the License, or (at your
9 * option) any later version. 11 * option) any later version.
10 * 12 *
11 * This program is distributed in the hope that it will be useful, 13 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details. 16 * GNU General Public License for more details.
15 * 17 *
16 * You should have received a copy of the Affero GNU General Public License 18 * You should have received a copy of the Affero GNU General Public License
17 * and the GNU General Public License along with this program. If not, see 19 * and the GNU General Public License along with this program. If not, see
18 * <http://www.gnu.org/licenses/>. 20 * <http://www.gnu.org/licenses/>.
19 * 21 *
20 * The authors can be reached via e-mail to <support@deliantra.net> 22 * The authors can be reached via e-mail to <support@deliantra.net>
21 */ 23 */
22 24
23#include <global.h> 25#include <global.h>
24#include <random_map.h> 26#include <rmg.h>
27#include <rproto.h>
25 28
29ecb_noinline void
30layout::alloc (int w, int h)
31{
32 assert (sizeof (cell) == 1);
33
34 this->w = w;
35 this->h = h;
36
37 // we store the layout in a single contiguous memory layout
38 // first part consists of pointers to each column, followed
39 // by the actual columns (not rows!)
40 size = (sizeof (cell *) + sizeof (cell) * h) * w;
41 data = (cell **)salloc<char> (size);
42
43 cell *p = (cell *)(data + w);
44
45 for (int x = 0; x < w; ++x)
46 data [x] = p + x * h;
47}
48
26Layout::Layout (int w, int h) 49layout::layout (int w, int h)
27: w(w), h(h)
28{ 50{
29 int size = (sizeof (char *) + sizeof (char) * h) * w; 51 alloc (w, h);
52}
30 53
54layout::layout (layout &copy)
55{
56 alloc (copy.w, copy.h);
57
58 memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
59}
60
61layout::layout (layout &orig, int x1, int y1, int x2, int y2)
62{
63 w = x2 - x1;
64 h = y2 - y1;
65
66 // we only allocate space for the pointers
67 size = sizeof (cell *) * w;
31 col = (char **)salloc<char> (size); 68 data = (cell **)salloc<char> (size);
32 69
33 char *data = (char *)(col + w); 70 // and now we point back into the original layout
34
35 for (int x = w; x--; ) 71 for (int x = 0; x < w; ++x)
36 col [x] = data + x * h; 72 data [x] = orig.data [x + x1] + y1;
37} 73}
38 74
39Layout::~Layout () 75layout::~layout ()
40{ 76{
41 int size = (sizeof (char *) + sizeof (char) * h) * w;
42
43 sfree ((char *)col, size); 77 sfree ((char *)data, size);
78}
79
80ecb_noinline void
81layout::fill (char fill)
82{
83 //memset (data [0], fill, w * h); // only when contiguous :/
84 fill_rect (0, 0, w, h, fill);
85}
86
87ecb_noinline void
88layout::replace (char from, char to)
89{
90 for (int x = 0; x < w; ++x)
91 for (int y = 0; y < h; ++y)
92 if (data [x][y] == from)
93 data [x][y] = to;
94}
95
96ecb_noinline void
97layout::rect (int x1, int y1, int x2, int y2, char fill)
98{
99 --x2;
100
101 memset (data [x1] + y1, fill, y2 - y1);
102 memset (data [x2] + y1, fill, y2 - y1);
103
104 while (++x1 < x2)
105 data [x1][y1] = data [x1][y2 - 1] = fill;
106}
107
108ecb_noinline void
109layout::fill_rect (int x1, int y1, int x2, int y2, char fill)
110{
111 for (; x1 < x2; ++x1)
112 memset (data [x1] + y1, fill, y2 - y1);
44} 113}
45 114
46void 115void
47Layout::fill (char fill)
48{
49 memset (col [0], fill, w * h);
50}
51
52void
53Layout::rect (int x1, int y1, int x2, int y2, char fill)
54{
55 for (; x1 < x2; ++x1)
56 memset (col [x1] + y1, fill, y2 - y1);
57}
58
59void Layout::border (char fill) 116layout::border (char fill)
60{ 117{
61 for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill; 118 rect (0, 0, w, h, fill);
62 for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill;
63} 119}
64 120
65void 121ecb_noinline void
66Layout::fill_rand (int percent) 122layout::fill_rand (int percent)
67{ 123{
68 percent = lerp (percent, 0, 100, 0, 256); 124 percent = lerp (percent, 0, 100, 0, 256);
69 125
70 for (int x = w - 1; --x > 0; ) 126 for (int x = 0; x < w; ++x)
71 for (int y = h - 1; --y > 0; ) 127 for (int y = 0; y < h; ++y)
72 col [x][y] = rmg_rndm (256) > percent ? 0 : '#'; 128 data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
73} 129}
74 130
75///////////////////////////////////////////////////////////////////////////// 131/////////////////////////////////////////////////////////////////////////////
76 132
77// erode by cellular automata 133// erode by cellular automata
78void 134ecb_noinline void
79Layout::erode_1_2 (int c1, int c2, int repeat) 135layout::erode_1_2 (int c1, int c2, int repeat)
80{ 136{
81 Layout neu (w, h); 137 layout neu (w, h);
82 138
83 while (repeat--) 139 while (repeat--)
84 { 140 {
85 for (int x = 0; x < w; ++x) 141 for (int x = 0; x < w; ++x)
86 { 142 {
… …
90 { 146 {
91 int n1 = 0, n2 = 0; 147 int n1 = 0, n2 = 0;
92 148
93 // a 5x5 area, dx, dy, distance (1 == <= 1, 0 <= 2) 149 // a 5x5 area, dx, dy, distance (1 == <= 1, 0 <= 2)
94 static I8 dds[][3] = { 150 static I8 dds[][3] = {
95 { -2, -1, 0 }, 151 { -2, -1, 0 }, { -2, 0, 0 }, { -2, 1, 0 },
96 { -2, 0, 0 }, 152 { -1, -2, 0 }, { -1, -1, 1 }, { -1, 0, 1 }, { -1, 1, 1 }, { -1, 2, 0 },
97 { -2, 1, 0 }, 153 { 0, -2, 0 }, { 0, -1, 1 }, { 0, 0, 1 }, { 0, 1, 1 }, { 0, 2, 0 },
98 154 { 1, -2, 0 }, { 1, -1, 1 }, { 1, 0, 1 }, { 1, 1, 1 }, { 1, 2, 0 },
99 { -1, -2, 0 }, 155 { 2, -1, 0 }, { 2, 0, 0 }, { 2, 1, 0 },
100 { -1, -1, 1 },
101 { -1, 0, 1 },
102 { -1, 1, 1 },
103 { -1, 2, 0 },
104
105 { 0, -2, 0 },
106 { 0, -1, 1 },
107 { 0, 0, 1 },
108 { 0, 1, 1 },
109 { 0, 2, 0 },
110
111 { 1, -2, 0 },
112 { 1, -1, 1 },
113 { 1, 0, 1 },
114 { 1, 1, 1 },
115 { 1, 2, 0 },
116
117 { 2, -1, 0 },
118 { 2, 0, 0 },
119 { 2, 1, 0 },
120 }; 156 };
121 157
122 for (int i = array_length (dds); i--; ) 158 for (int i = array_length (dds); i--; )
123 { 159 {
124 int nx = x + dds [i][0]; 160 int nx = x + dds [i][0];
125 int ny = y + dds [i][1]; 161 int ny = y + dds [i][1];
126 162
127 if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !col [nx][ny]) 163 if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !data [nx][ny])
128 { 164 {
129 n1 += dds [i][2]; 165 n1 += dds [i][2];
130 n2++; 166 n2++;
131 } 167 }
132 } 168 }
… …
140} 176}
141 177
142///////////////////////////////////////////////////////////////////////////// 178/////////////////////////////////////////////////////////////////////////////
143 179
144void 180void
145Layout::print () 181layout::print () const
146{ 182{
147 for (int y = 0; y < h; y++) 183 for (int y = 0; y < h; y++)
148 { 184 {
149 for (int x = 0; x < w; x++) 185 for (int x = 0; x < w; x++)
150 { 186 {
151 U8 c = (U8)col [x][y]; 187 U8 c = (U8)data [x][y];
152 188
153 if (!c) 189 if (!c)
154 c = ' '; 190 c = ' ';
155 else if (c < 10) 191 else if (c < 10)
156 c += '0'; 192 c += '0';
… …
169///////////////////////////////////////////////////////////////////////////// 205/////////////////////////////////////////////////////////////////////////////
170// isolation remover - ensures single connected area 206// isolation remover - ensures single connected area
171 207
172typedef fixed_stack<point> pointlist; 208typedef fixed_stack<point> pointlist;
173 209
174static noinline void 210ecb_noinline static void
175push_flood_fill (Layout &dist, pointlist &seeds, int x, int y) 211push_flood_fill (layout &dist, pointlist &seeds, int x, int y)
176{ 212{
177 if (dist [x][y]) 213 if (dist [x][y])
178 return; 214 return;
179 215
180 while (y > 0 && !dist [x][y - 1]) 216 while (y > 0 && !dist [x][y - 1])
… …
190 ++y; 226 ++y;
191 } 227 }
192 228
193 while (--y >= y0) 229 while (--y >= y0)
194 { 230 {
195 if (x > 0) push_flood_fill (dist, seeds, x - 1, y); 231 if (x > 0 && !dist [x - 1][y]) push_flood_fill (dist, seeds, x - 1, y);
196 if (x < dist.w - 1) push_flood_fill (dist, seeds, x + 1, y); 232 if (x < dist.w - 1 && !dist [x + 1][y]) push_flood_fill (dist, seeds, x + 1, y);
197 } 233 }
198} 234}
199 235
200static inline void 236static void inline
201make_tunnel (Layout &dist, pointlist &seeds, int x, int y, U8 d) 237make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb)
202{ 238{
203 for (;;) 239 for (;;)
204 { 240 {
241 point neigh[4];
242 int ncnt = 0;
243
244 d += perturb > 1;
245
205 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) 246 if (x > 0 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
206 --x;
207 else if (x < dist.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) 247 if (x < dist.w - 1 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y);
208 ++x;
209 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) 248 if (y > 0 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
210 --y;
211 else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) 249 if (y < dist.h - 1 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
212 ++y; 250
213 else 251 if (!ncnt)
214 break; 252 return;
253
254 point p = neigh [perturb ? rmg_rndm (ncnt) : 0];
255
256 seeds.push (p);
257
258 x = p.x;
259 y = p.y;
215 260
216 d = dist [x][y]; 261 d = dist [x][y];
217 dist [x][y] = 1; 262 dist [x][y] = 1;
218 seeds.push (point (x, y));
219 } 263 }
220} 264}
221 265
222static void inline 266static void inline
223maybe_push (Layout &dist, pointlist &seeds, int x, int y, U8 d) 267maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d)
224{ 268{
225 char &D = dist [x][y]; 269 char &D = dist [x][y];
226 270
227 if (U8 (D) > d) // if wall and higher distance, lower distance 271 if (U8 (D) > d) // if wall and higher distance, lower distance
228 D = d; 272 D = d;
… …
230 return; 274 return;
231 275
232 seeds.push (point (x, y)); 276 seeds.push (point (x, y));
233} 277}
234 278
235static void 279// isolation remover, works on a "distance" map
236isolation_remover (Layout &maze, bool dirty) 280// the map must be initialised with 0 == rooms, 255 = walls
281ecb_noinline static void
282isolation_remover (layout &dist, unsigned int perturb = 2)
237{ 283{
238 Layout dist (maze.w, maze.h);
239
240 // dist contains 284 // dist contains
241 // 0 == invisited rooms 285 // 0 == invisited rooms
242 // 1 == visited rooms 286 // 1 == visited rooms
243 // 2+ shortest distance to random near room 287 // 2+ shortest distance to random near room
244 288
245 // phase 1, initialise dist array, find seed 289 clamp_it (perturb, 0, 2);
290
291 // phase 1, find seed
246 int cnt = 0; 292 int cnt = 0;
247 int x, y; 293 int x, y;
248 294
249 for (int i = 0; i < maze.w; ++i) 295 for (int i = 0; i < dist.w; ++i)
250 for (int j = 0; j < maze.h; ++j) 296 for (int j = 0; j < dist.h; ++j)
251 { 297 if (!dist [i][j] && !rmg_rndm (++cnt))
252 if (maze [i][j] == '#')
253 dist [i][j] = U8 (255);
254 else
255 {
256 dist [i][j] = 0;
257 if (!rmg_rndm (++cnt))
258 x = i, y = j; 298 x = i, y = j;
259 }
260 }
261 299
262 if (!cnt) 300 if (!cnt)
301 {
302 // map is completely massive, this is not good,
303 // so make it empty instead.
304 dist.fill (1);
263 return; 305 return;
306 }
264 307
265 fixed_stack<point> seeds (maze.w * maze.h * 5); 308 fixed_stack<point> seeds (dist.w * dist.h * 5);
266 309
267 // found first free space - picking the first one gives 310 // found first free space - picking the first one gives
268 // us a slight bias for tunnels, but usually you won't 311 // us a slight bias for tunnels, but usually you won't
269 // notice that in-game 312 // notice that in-game
270 seeds.push (point (x, y)); 313 seeds.push (point (x, y));
271 314
272 // phase 2, while we have seeds, if 315 // phase 2, while we have seeds, if
273 // seed is empty, floodfill, else grow 316 // seed is empty, floodfill, else grow
274 317
318 int rem_index = 0; // used to remove "somewhat ordered"
319
275 while (seeds.size) 320 while (seeds.size)
276 { 321 {
277 coroapi::cede_to_tick (); 322 coroapi::cede_to_tick ();
278 323
324 int i = perturb
325 ? rmg_rndm (max (0, seeds.size - 8), seeds.size - 1)
326 : rem_index ++ % seeds.size;
327
279 point p = seeds.remove (rmg_rndm (seeds.size)); 328 point p = seeds.remove (i);
280 329
281 x = p.x; 330 x = p.x;
282 y = p.y; 331 y = p.y;
283 332
284 if (!dist [x][y]) 333 if (!dist [x][y])
285 { 334 {
286 // found new isolated area, make tunnel 335 // found new isolated area, make tunnel
287 if (!dirty)
288 push_flood_fill (dist, seeds, x, y); 336 push_flood_fill (dist, seeds, x, y);
289
290 make_tunnel (dist, seeds, x, y, 255); 337 make_tunnel (dist, seeds, x, y, 254, perturb);
291
292 if (dirty)
293 push_flood_fill (dist, seeds, x, y);
294 } 338 }
295 else 339 else
296 { 340 {
297 // nothing here, continue to expand 341 // nothing here, continue to expand
298 U8 d = U8 (dist [x][y]) + 1; 342 U8 d = U8 (dist [x][y]) + 1;
… …
301 if (x > 0) maybe_push (dist, seeds, x - 1, y, d); 345 if (x > 0) maybe_push (dist, seeds, x - 1, y, d);
302 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d); 346 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d);
303 if (y > 0) maybe_push (dist, seeds, x, y - 1, d); 347 if (y > 0) maybe_push (dist, seeds, x, y - 1, d);
304 } 348 }
305 } 349 }
350}
351
352void
353layout::isolation_remover (int perturb)
354{
355 layout dist (w - 2, h - 2); // map without border
356
357 for (int x = 1; x < w - 1; ++x)
358 for (int y = 1; y < h - 1; ++y)
359 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
360
361 ::isolation_remover (dist, perturb);
306 362
307 // now copy the tunnels over 363 // now copy the tunnels over
308 for (int x = 0; x < maze.w; ++x) 364 for (int x = 1; x < w - 1; ++x)
309 for (int y = 0; y < maze.h; ++y) 365 for (int y = 1; y < h - 1; ++y)
310 if (maze [x][y] == '#' && dist [x][y] == 1) 366 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
311 maze [x][y] = 0; 367 data [x][y] = 0;
312} 368}
313 369
370/////////////////////////////////////////////////////////////////////////////
371
372//+GPL
373
374/* puts doors at appropriate locations in a maze. */
314void 375void
315Layout::isolation_remover (bool dirty) 376layout::doorify ()
316{ 377{
317 ::isolation_remover (*this, dirty); 378 int ndoors = w * h / 60; /* reasonable number of doors. */
379
380 coroapi::cede_to_tick ();
381
382 fixed_stack<point> doorloc (w * h);
383
384 /* make a list of possible door locations */
385 for (int i = 1; i < w - 1; i++)
386 for (int j = 1; j < h - 1; j++)
387 {
388 int sindex = surround_flag (*this, i, j);
389
390 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
391 doorloc.push (point (i, j));
392 }
393
394 while (ndoors && doorloc.size)
395 {
396 point p = doorloc.remove (rmg_rndm (doorloc.size));
397
398 int sindex = surround_flag (*this, p.x, p.y);
399
400 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
401 {
402 data [p.x][p.y] = 'D';
403 --ndoors;
404 }
405 }
318} 406}
407
408/* takes a map and makes it symmetric: adjusts Xsize and
409 * Ysize to produce a symmetric map.
410 */
411void
412layout::symmetrize (int symmetry)
413{
414 if (symmetry == SYMMETRY_NONE)
415 return;
416
417 layout sym_layout (
418 symmetry == SYMMETRY_X || symmetry == SYMMETRY_XY ? w * 2 - 3 : w,
419 symmetry == SYMMETRY_Y || symmetry == SYMMETRY_XY ? h * 2 - 3 : h
420 );
421
422 if (symmetry == SYMMETRY_X)
423 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
424 for (int j = 0; j < sym_layout.h; j++)
425 {
426 sym_layout[i ][j] =
427 sym_layout[sym_layout.w - i - 1][j] = data [i][j];
428 }
429
430 if (symmetry == SYMMETRY_Y)
431 for (int i = 0; i < sym_layout.w; i++)
432 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
433 {
434 sym_layout[i][j ] =
435 sym_layout[i][sym_layout.h - j - 1] = data [i][j];
436 }
437
438 if (symmetry == SYMMETRY_XY)
439 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
440 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
441 {
442 sym_layout[i ][j ] =
443 sym_layout[i ][sym_layout.h - j - 1] =
444 sym_layout[sym_layout.w - i - 1][j ] =
445 sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = data [i][j];
446 }
447
448 /* need to run the isolation remover for some layouts */
449#if 0
450 switch (RP->map_layout_style)
451 {
452 case LAYOUT_ONION:
453 case LAYOUT_SNAKE:
454 case LAYOUT_SQUARE_SPIRAL:
455 // safe
456 break;
457
458 default:
459 sym_layout.isolation_remover ();
460 break;
461 }
462#endif
463 sym_layout.isolation_remover ();
464
465 swap (sym_layout);
466}
467
468//-GPL
469
470void
471layout::rotate (int rotation)
472{
473 coroapi::cede_to_tick ();
474
475 switch (rotation & 3)
476 {
477 case 2: /* a reflection */
478 {
479 layout new_layout (w, h);
480
481 for (int i = 0; i < w; i++) /* copy a reflection back */
482 for (int j = 0; j < h; j++)
483 new_layout [i][j] = data [w - i - 1][h - j - 1];
484
485 swap (new_layout);
486 }
487 break;
488
489 case 1:
490 case 3:
491 {
492 layout new_layout (h, w);
493
494 if (rotation == 1) /* swap x and y */
495 for (int i = 0; i < w; i++)
496 for (int j = 0; j < h; j++)
497 new_layout [j][i] = data [i][j];
498
499 if (rotation == 3) /* swap x and y */
500 for (int i = 0; i < w; i++)
501 for (int j = 0; j < h; j++)
502 new_layout [j][i] = data [w - i - 1][h - j - 1];
503
504 swap (new_layout);
505 }
506 break;
507 }
508}
509
510/////////////////////////////////////////////////////////////////////////////
511
512//+GPL
513
514/*
515 * Expands a maze by 2x in each dimension.
516 * H. S. Teoh
517 */
518
519/* Copy the old tile X into the new one at location (i*2, j*2) and
520 * fill up the rest of the 2x2 result with \0:
521 * X ---> X \0
522 * \0 \0
523 */
524static void inline
525expand_misc (layout &newlayout, int i, int j, layout &maze)
526{
527 newlayout[i * 2 + rmg_rndm (1)][j * 2 + rmg_rndm (1)] = maze[i][j];
528 /* (Note: no need to reset rest of 2x2 area to \0 because calloc does that
529 * for us.) */
530}
531
532/* Returns a bitmap that represents which squares on the right and bottom
533 * edges of a square (i,j) match the given character:
534 * 1 match on (i+1, j)
535 * 2 match on (i, j+1)
536 * 4 match on (i+1, j+1)
537 * and the possible combinations thereof.
538 */
539ecb_noinline static int
540calc_pattern (char ch, layout &maze, int i, int j)
541{
542 int pattern = 0;
543
544 if (i + 1 < maze.w && maze[i + 1][j] == ch)
545 pattern |= 1;
546
547 if (j + 1 < maze.h)
548 {
549 if (maze[i][j + 1] == ch)
550 pattern |= 2;
551
552 if (i + 1 < maze.w && maze[i + 1][j + 1] == ch)
553 pattern |= 4;
554 }
555
556 return pattern;
557}
558
559/* Expand a wall. This function will try to sensibly connect the resulting
560 * wall to adjacent wall squares, so that the result won't have disconnected
561 * walls.
562 */
563static void inline
564expand_wall (layout &newlayout, int i, int j, layout &maze)
565{
566 int wall_pattern = calc_pattern ('#', maze, i, j);
567 int door_pattern = calc_pattern ('D', maze, i, j);
568 int both_pattern = wall_pattern | door_pattern;
569
570 newlayout[i * 2][j * 2] = '#';
571
572 if (i + 1 < maze.w)
573 {
574 if (both_pattern & 1)
575 { /* join walls/doors to the right */
576/* newlayout[i*2+1][j*2] = '#'; */
577 newlayout[i * 2 + 1][j * 2] = maze[i + 1][j];
578 }
579 }
580
581 if (j + 1 < maze.h)
582 {
583 if (both_pattern & 2)
584 { /* join walls/doors to the bottom */
585/* newlayout[i*2][j*2+1] = '#'; */
586 newlayout[i * 2][j * 2 + 1] = maze[i][j + 1];
587 }
588
589 if (wall_pattern == 7)
590 { /* if orig maze is a 2x2 wall block,
591 * we fill the result with walls. */
592 newlayout[i * 2 + 1][j * 2 + 1] = '#';
593 }
594 }
595}
596
597/* This function will try to sensibly connect doors so that they meet up with
598 * adjacent walls. Note that it will also presumptuously delete (ignore) doors
599 * that it doesn't know how to correctly expand.
600 */
601static void inline
602expand_door (layout &newlayout, int i, int j, layout &maze)
603{
604 int wall_pattern = calc_pattern ('#', maze, i, j);
605 int door_pattern = calc_pattern ('D', maze, i, j);
606 int join_pattern;
607
608 /* Doors "like" to connect to walls more than other doors. If there is
609 * a wall and another door, this door will connect to the wall and
610 * disconnect from the other door. */
611 if (wall_pattern & 3)
612 join_pattern = wall_pattern;
613 else
614 join_pattern = door_pattern;
615
616 newlayout[i * 2][j * 2] = 'D';
617
618 if (i + 1 < maze.w)
619 if (join_pattern & 1)
620 /* there is a door/wall to the right */
621 newlayout[i * 2 + 1][j * 2] = 'D';
622
623 if (j + 1 < maze.h)
624 if (join_pattern & 2)
625 /* there is a door/wall below */
626 newlayout[i * 2][j * 2 + 1] = 'D';
627}
628
629void
630layout::expand2x ()
631{
632 layout new_layout (w * 2 - 1, h * 2 - 1);
633
634 new_layout.clear ();
635
636 coroapi::cede_to_tick ();
637
638 for (int i = 0; i < w; i++)
639 for (int j = 0; j < h; j++)
640 switch (data [i][j])
641 {
642 case '#': expand_wall (new_layout, i, j, *this); break;
643 case 'D': expand_door (new_layout, i, j, *this); break;
644 default: expand_misc (new_layout, i, j, *this); break;
645 }
646
647 swap (new_layout);
648}
649
650/////////////////////////////////////////////////////////////////////////////
651
652/* checks the maze to see if I can stick a horizontal(dir = 0) wall
653 (or vertical, dir == 1)
654 here which ends up on other walls sensibly. */
655static int
656can_make_wall (const layout &maze, int dx, int dy, int dir)
657{
658 int i1;
659 int length = 0;
660
661 /* dont make walls if we're on the edge. */
662 if (dx == 0 || dx == (maze.w - 1) || dy == 0 || dy == (maze.h - 1))
663 return -1;
664
665 /* don't make walls if we're ON a wall. */
666 if (maze [dx][dy] != 0)
667 return -1;
668
669 if (dir == 0) /* horizontal */
670 {
671 int y = dy;
672
673 for (i1 = dx - 1; i1 > 0; i1--)
674 {
675 int sindex = surround_flag2 (maze, i1, y);
676
677 if (sindex == 1) break;
678 if (sindex != 0) return -1; /* can't make horiz. wall here */
679 if (maze[i1][y] != 0) return -1; /* can't make horiz. wall here */
680
681 length++;
682 }
683
684 for (i1 = dx + 1; i1 < maze.w - 1; i1++)
685 {
686 int sindex = surround_flag2 (maze, i1, y);
687
688 if (sindex == 2) break;
689 if (sindex != 0) return -1; /* can't make horiz. wall here */
690 if (maze[i1][y] != 0) return -1; /* can't make horiz. wall here */
691
692 length++;
693 }
694 return length;
695 }
696 else
697 { /* vertical */
698 int x = dx;
699
700 for (i1 = dy - 1; i1 > 0; i1--)
701 {
702 int sindex = surround_flag2 (maze, x, i1);
703
704 if (sindex == 4) break;
705 if (sindex != 0) return -1; /* can't make vert. wall here */
706 if (maze[x][i1] != 0) return -1; /* can't make horiz. wall here */
707
708 length++;
709 }
710
711 for (i1 = dy + 1; i1 < maze.h - 1; i1++)
712 {
713 int sindex = surround_flag2 (maze, x, i1);
714
715 if (sindex == 8) break;
716 if (sindex != 0) return -1; /* can't make verti. wall here */
717 if (maze[x][i1] != 0) return -1; /* can't make horiz. wall here */
718
719 length++;
720 }
721
722 return length;
723 }
724
725 return -1;
726}
727
728int
729make_wall (layout &maze, int x, int y, int dir)
730{
731 maze[x][y] = 'D'; /* mark a door */
732
733 switch (dir)
734 {
735 case 0: /* horizontal */
736 {
737 for (int i1 = x - 1; maze[i1][y] == 0; --i1) maze[i1][y] = '#';
738 for (int i1 = x + 1; maze[i1][y] == 0; ++i1) maze[i1][y] = '#';
739 break;
740 }
741 case 1: /* vertical */
742 {
743 for (int i1 = y - 1; maze[x][i1] == 0; --i1) maze[x][i1] = '#';
744 for (int i1 = y + 1; maze[x][i1] == 0; ++i1) maze[x][i1] = '#';
745 break;
746 }
747 }
748
749 return 0;
750}
751
752void
753layout::roomify ()
754{
755 int tries = w * h / 30;
756
757 coroapi::cede_to_tick ();
758
759 for (int ti = 0; ti < tries; ti++)
760 {
761 /* starting location for looking at creating a door */
762 int dx = rmg_rndm (w);
763 int dy = rmg_rndm (h);
764
765 /* results of checking on creating walls. */
766 int cx = can_make_wall (*this, dx, dy, 0); /* horizontal */
767 int cy = can_make_wall (*this, dx, dy, 1); /* vertical */
768
769 if (cx == -1)
770 {
771 if (cy != -1)
772 make_wall (*this, dx, dy, 1);
773
774 continue;
775 }
776
777 if (cy == -1)
778 {
779 make_wall (*this, dx, dy, 0);
780 continue;
781 }
782
783 if (cx < cy)
784 make_wall (*this, dx, dy, 0);
785 else
786 make_wall (*this, dx, dy, 1);
787 }
788}
789
790//-GPL
319 791
320///////////////////////////////////////////////////////////////////////////// 792/////////////////////////////////////////////////////////////////////////////
321 793
322// inspired mostly by http://www.jimrandomh.org/misc/caves.txt 794// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
323void 795void
324Layout::gen_cave (int subtype) 796layout::gen_cave (int subtype)
325{ 797{
326 switch (subtype) 798 switch (subtype)
327 { 799 {
328 // a rough cave 800 // a rough cave
329 case 0: 801 case 0:
330 fill_rand (rmg_rndm (80, 95)); 802 fill_rand (rmg_rndm (85, 97));
331 break; 803 break;
332 804
333 // corridors 805 // corridors
334 case 1: 806 case 1:
335 fill_rand (rmg_rndm (5, 40)); 807 fill_rand (rmg_rndm (5, 40));
336 erode_1_2 (5, 2, 10); 808 erode_1_2 (5, 2, 10);
337 erode_1_2 (5, -1, 10); 809 erode_1_2 (5, -1, 10);
338 erode_1_2 (5, 2, 1); 810 erode_1_2 (5, 2, 1);
339 break; 811 break;
340 812
341 // somewhat open, roundish 813 // somewhat open, some room-like structures
342 case 2: 814 case 2:
815 fill_rand (45);
816 erode_1_2 (5, 2, 4);
817 erode_1_2 (5, -1, 3);
818 break;
819
820 // wide open, roundish
821 case 3:
343 fill_rand (45); 822 fill_rand (45);
344 erode_1_2 (5, 0, 5); 823 erode_1_2 (5, 0, 5);
345 erode_1_2 (5, 1, 1); 824 erode_1_2 (5, 1, 1);
346 break; 825 break;
347
348 // wide open, some room-like structures
349 case 3:
350 fill_rand (45);
351 erode_1_2 (5, 2, 4);
352 erode_1_2 (5, -1, 3);
353 break;
354 } 826 }
355 827
356 border (); 828 border ();
357 isolation_remover (); 829 isolation_remover (1);
358} 830}
831
832void
833layout::gen_castle ()
834{
835 fill ('#');
836
837 for (int n = w * h / 30 + 1; n--; )
838 {
839 int rw = rmg_rndm (6, 10);
840 int rh = rmg_rndm (6, 10);
841
842 if (rw > w || rh > h)
843 continue;
844
845 int rx = rmg_rndm (0, w - rw);
846 int ry = rmg_rndm (0, h - rh);
847
848 rect (rx, ry, rx + rw, ry + rh, '#');
849 fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0);
850 }
851
852 border ();
853 isolation_remover (0);
854}
855
856static void
857gen_mixed_ (layout &maze, random_map_params *RP)
858{
859 if (maze.w > maze.h && maze.w > 16)
860 {
861 int m = rmg_rndm (8, maze.w - 8);
862
863 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP);
864 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP);
865 }
866 else if (maze.h > 16)
867 {
868 int m = rmg_rndm (8, maze.h - 8);
869
870 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP);
871 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP);
872 }
873 else
874 {
875 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
876
877 if (RP->map_layout_style == LAYOUT_MULTIPLE)
878 ++RP->map_layout_style;
879
880 maze.generate (RP);
881 }
882
883 coroapi::cede_to_tick ();
884}
885
886// recursive subdivision with random sublayouts
887static void
888gen_mixed (layout &maze, random_map_params *RP)
889{
890 random_map_params &rp = *new random_map_params (RP);
891 gen_mixed_ (maze, &rp);
892 delete &rp;
893
894 maze.border ();
895
896 // exits currently do not work so well, as they
897 // are currently often found together, so nuke entrances
898 maze.replace ('<', ' ');
899
900 maze.isolation_remover (0);
901}
902
903//+GPL
904
905/* function selects the maze function and gives it whatever
906 arguments it needs. */
907void
908layout::generate (random_map_params *RP)
909{
910 switch (RP->map_layout_style)
911 {
912 case LAYOUT_ONION:
913 map_gen_onion (*this, RP->layoutoptions1, RP->layoutoptions2);
914
915 if (!(rmg_rndm (3)) && !(RP->layoutoptions1 & (RMOPT_WALLS_ONLY | RMOPT_WALL_OFF)))
916 roomify ();
917
918 break;
919
920 case LAYOUT_MAZE:
921 maze_gen (*this, RP->get_iv ("maze_type", rmg_rndm (4)));
922
923 if (rmg_rndm (2))
924 doorify ();
925
926 break;
927
928 case LAYOUT_SPIRAL:
929 map_gen_spiral (*this, RP->layoutoptions1);
930
931 if (rmg_rndm (2))
932 doorify ();
933
934 break;
935
936 case LAYOUT_ROGUELIKE:
937 /* Don't put symmetry in rogue maps. There isn't much reason to
938 * do so in the first place (doesn't make it any more interesting),
939 * but more importantly, the symmetry code presumes we are symmetrizing
940 * spirals, or maps with lots of passages - making a symmetric rogue
941 * map fails because its likely that the passages the symmetry process
942 * creates may not connect the rooms.
943 */
944 RP->symmetry_used = SYMMETRY_NONE;
945 roguelike_layout_gen (*this, RP->layoutoptions1);
946 /* no doorifying... done already */
947 break;
948
949 case LAYOUT_SNAKE:
950 make_snake_layout (*this, RP->layoutoptions1);
951
952 if (rmg_rndm (2))
953 roomify ();
954
955 break;
956
957 case LAYOUT_SQUARE_SPIRAL:
958 make_square_spiral_layout (*this, RP->layoutoptions1);
959
960 if (rmg_rndm (2))
961 roomify ();
962
963 break;
964
965 case LAYOUT_CAVE:
966 gen_cave (RP->get_iv ("cave_type", rmg_rndm (4)));
967
968 if (rmg_rndm (2))
969 doorify ();
970
971 break;
972
973 case LAYOUT_CASTLE:
974 gen_castle ();
975
976 if (rmg_rndm (2))
977 doorify ();
978
979 break;
980
981 case LAYOUT_MULTIPLE:
982 gen_mixed (*this, RP);
983 break;
984
985 default:
986 abort ();
987 }
988}
989
990//-GPL
359 991
360#if 0 992#if 0
993static void
994gen_village (layout &maze)
995{
996 maze.clear ();
997 maze.border ();
998
999 for (int n = maze.w * maze.h / 200 + 1; n--; )
1000 {
1001 int rw = rmg_rndm (6, 10);
1002 int rh = rmg_rndm (6, 10);
1003
1004 int rx = rmg_rndm (2, maze.w - rw - 2);
1005 int ry = rmg_rndm (2, maze.h - rh - 2);
1006
1007 maze.rect (rx, ry, rx + rw, ry + rh, '#');
1008 }
1009
1010 maze.border ();
1011 maze.isolation_remover (2);
1012}
1013
361static struct demo 1014static struct demo
362{ 1015{
363 demo () 1016 demo ()
364 { 1017 {
365 Layout maze (40, 25);
366 rmg_rndm.seed (time (0)); 1018 rmg_rndm.seed (time (0));
1019 extern void hack();hack ();
367 1020
368 for(int i=1;i<10;i) 1021 for(int i=1;i<100;i++)
369 { 1022 {
1023 layout maze (40, 30);
370 maze.fill_rand (97); 1024 maze.fill_rand (99);
371 maze.border (); 1025 maze.border ();
372 maze.isolation_remover (); 1026 maze.isolation_remover (2);
373 maze.print (); 1027 maze.print ();
374 } 1028 }
375 1029
376 exit (1); 1030 exit (1);
377 } 1031 }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines