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

Diff Legend

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