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

Diff Legend

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