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

Diff Legend

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