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

Diff Legend

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