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.15 by root, Sat Jul 3 03:09:27 2010 UTC vs.
Revision 1.24 by root, Mon Jul 5 00:07:21 2010 UTC

… …
23 23
24#include <global.h> 24#include <global.h>
25#include <random_map.h> 25#include <random_map.h>
26#include <rproto.h> 26#include <rproto.h>
27 27
28void 28void noinline
29layout::alloc (int w, int h) 29layout::alloc (int w, int h)
30{ 30{
31 assert (sizeof (cell) == 1); 31 assert (sizeof (cell) == 1);
32 32
33 this->w = w; 33 this->w = w;
… …
74layout::~layout () 74layout::~layout ()
75{ 75{
76 sfree ((char *)data, size); 76 sfree ((char *)data, size);
77} 77}
78 78
79void 79void noinline
80layout::fill (char fill) 80layout::fill (char fill)
81{ 81{
82 //memset (data [0], fill, w * h); // only when contiguous :/ 82 //memset (data [0], fill, w * h); // only when contiguous :/
83 fill_rect (0, 0, w, h, fill); 83 fill_rect (0, 0, w, h, fill);
84} 84}
85 85
86void 86void noinline
87layout::replace (char from, char to)
88{
89 for (int x = 0; x < w; ++x)
90 for (int y = 0; y < h; ++y)
91 if (data [x][y] == from)
92 data [x][y] = to;
93}
94
95void noinline
87layout::rect (int x1, int y1, int x2, int y2, char fill) 96layout::rect (int x1, int y1, int x2, int y2, char fill)
88{ 97{
89 --x2; 98 --x2;
90 99
91 memset (data [x1] + y1, fill, y2 - y1); 100 memset (data [x1] + y1, fill, y2 - y1);
… …
93 102
94 while (++x1 < x2) 103 while (++x1 < x2)
95 data [x1][y1] = data [x1][y2 - 1] = fill; 104 data [x1][y1] = data [x1][y2 - 1] = fill;
96} 105}
97 106
98void 107void noinline
99layout::fill_rect (int x1, int y1, int x2, int y2, char fill) 108layout::fill_rect (int x1, int y1, int x2, int y2, char fill)
100{ 109{
101 for (; x1 < x2; ++x1) 110 for (; x1 < x2; ++x1)
102 memset (data [x1] + y1, fill, y2 - y1); 111 memset (data [x1] + y1, fill, y2 - y1);
103} 112}
104 113
114void
105void layout::border (char fill) 115layout::border (char fill)
106{ 116{
107 rect (0, 0, w, h, fill); 117 rect (0, 0, w, h, fill);
108} 118}
109 119
110void 120void noinline
111layout::fill_rand (int percent) 121layout::fill_rand (int percent)
112{ 122{
113 percent = lerp (percent, 0, 100, 0, 256); 123 percent = lerp (percent, 0, 100, 0, 256);
114 124
115 for (int x = w - 1; --x > 0; ) 125 for (int x = 0; x < w; ++x)
116 for (int y = h - 1; --y > 0; ) 126 for (int y = 0; y < h; ++y)
117 data [x][y] = rmg_rndm (256) > percent ? 0 : '#'; 127 data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
118} 128}
119 129
120///////////////////////////////////////////////////////////////////////////// 130/////////////////////////////////////////////////////////////////////////////
121 131
122// erode by cellular automata 132// erode by cellular automata
123void 133void noinline
124layout::erode_1_2 (int c1, int c2, int repeat) 134layout::erode_1_2 (int c1, int c2, int repeat)
125{ 135{
126 layout neu (w, h); 136 layout neu (w, h);
127 137
128 while (repeat--) 138 while (repeat--)
… …
220 if (x > 0 && !dist [x - 1][y]) push_flood_fill (dist, seeds, x - 1, y); 230 if (x > 0 && !dist [x - 1][y]) 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); 231 if (x < dist.w - 1 && !dist [x + 1][y]) push_flood_fill (dist, seeds, x + 1, y);
222 } 232 }
223} 233}
224 234
225static inline void 235static void inline
226make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d) 236make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb)
227{ 237{
228 for (;;) 238 for (;;)
229 { 239 {
230 point neigh[4]; 240 point neigh[4];
231 int ncnt = 0; 241 int ncnt = 0;
232 242
243 d += perturb > 1;
244
233 if (x > 0 && U8 (dist [x - 1][y]) <= d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y); 245 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); 246 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); 247 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); 248 if (y < dist.h - 1 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
237 249
238 if (!ncnt) 250 if (!ncnt)
239 return; 251 return;
240 252
241 point &p = neigh [rmg_rndm (ncnt)]; 253 point p = neigh [perturb ? rmg_rndm (ncnt) : 0];
242 254
243 seeds.push (p); 255 seeds.push (p);
244 256
245 x = p.x; 257 x = p.x;
246 y = p.y; 258 y = p.y;
… …
264} 276}
265 277
266// isolation remover, works on a "distance" map 278// isolation remover, works on a "distance" map
267// the map must be initialised with 0 == rooms, 255 = walls 279// the map must be initialised with 0 == rooms, 255 = walls
268static void noinline 280static void noinline
269isolation_remover (layout &dist) 281isolation_remover (layout &dist, unsigned int perturb = 2)
270{ 282{
271 // dist contains 283 // dist contains
272 // 0 == invisited rooms 284 // 0 == invisited rooms
273 // 1 == visited rooms 285 // 1 == visited rooms
274 // 2+ shortest distance to random near room 286 // 2+ shortest distance to random near room
275 287
288 clamp_it (perturb, 0, 2);
289
276 // phase 1, find seed 290 // phase 1, find seed
277 int cnt = 0; 291 int cnt = 0;
278 int x, y; 292 int x, y;
279 293
280 for (int i = 0; i < dist.w; ++i) 294 for (int i = 0; i < dist.w; ++i)
… …
311 325
312 if (!dist [x][y]) 326 if (!dist [x][y])
313 { 327 {
314 // found new isolated area, make tunnel 328 // found new isolated area, make tunnel
315 push_flood_fill (dist, seeds, x, y); 329 push_flood_fill (dist, seeds, x, y);
316 make_tunnel (dist, seeds, x, y, 255); 330 make_tunnel (dist, seeds, x, y, 254, perturb);
317 } 331 }
318 else 332 else
319 { 333 {
320 // nothing here, continue to expand 334 // nothing here, continue to expand
321 U8 d = U8 (dist [x][y]) + 1; 335 U8 d = U8 (dist [x][y]) + 1;
… …
327 } 341 }
328 } 342 }
329} 343}
330 344
331void 345void
332layout::isolation_remover () 346layout::isolation_remover (int perturb)
333{ 347{
334 layout dist (w - 2, h - 2); // map without border 348 layout dist (w - 2, h - 2); // map without border
335 349
336 for (int x = 1; x < w - 1; ++x) 350 for (int x = 1; x < w - 1; ++x)
337 for (int y = 1; y < h - 1; ++y) 351 for (int y = 1; y < h - 1; ++y)
338 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0; 352 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
339 353
340 ::isolation_remover (dist); 354 ::isolation_remover (dist, perturb);
341 355
342 // now copy the tunnels over 356 // now copy the tunnels over
343 for (int x = 1; x < w - 1; ++x) 357 for (int x = 1; x < w - 1; ++x)
344 for (int y = 1; y < h - 1; ++y) 358 for (int y = 1; y < h - 1; ++y)
345 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1) 359 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
346 data [x][y] = 0; 360 data [x][y] = 0;
347} 361}
348 362
349///////////////////////////////////////////////////////////////////////////// 363/////////////////////////////////////////////////////////////////////////////
350 364
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 365//+GPL
392 366
393/* puts doors at appropriate locations in a maze. */ 367/* puts doors at appropriate locations in a maze. */
394void 368void
395layout::doorify () 369layout::doorify ()
396{ 370{
397 int ndoors = w * h / 60; /* reasonable number of doors. */ 371 int ndoors = w * h / 60; /* reasonable number of doors. */
398 int doorlocs = 0; /* # of available doorlocations */
399 372
400 uint16 *doorlist_x = salloc<uint16> (w * h); 373 coroapi::cede_to_tick ();
401 uint16 *doorlist_y = salloc<uint16> (w * h); 374
375 fixed_stack<point> doorloc (w * h);
402 376
403 /* make a list of possible door locations */ 377 /* make a list of possible door locations */
404 for (int i = 1; i < w - 1; i++) 378 for (int i = 1; i < w - 1; i++)
405 for (int j = 1; j < h - 1; j++) 379 for (int j = 1; j < h - 1; j++)
406 { 380 {
407 int sindex = surround_flag (*this, i, j); 381 int sindex = surround_flag (*this, i, j);
408 382
409 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 383 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
410 { 384 doorloc.push (point (i, j));
411 doorlist_x [doorlocs] = i;
412 doorlist_y [doorlocs] = j;
413 doorlocs++;
414 }
415 } 385 }
416 386
417 while (ndoors > 0 && doorlocs > 0) 387 while (ndoors && doorloc.size)
418 { 388 {
419 int di = rmg_rndm (doorlocs); 389 point p = doorloc.remove (rmg_rndm (doorloc.size));
420 int i = doorlist_x [di]; 390
421 int j = doorlist_y [di];
422 int sindex = surround_flag (*this, i, j); 391 int sindex = surround_flag (*this, p.x, p.y);
423 392
424 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 393 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
425 { 394 {
426 data [i][j] = 'D'; 395 data [p.x][p.y] = 'D';
427 ndoors--; 396 --ndoors;
428 } 397 }
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 } 398 }
435
436 sfree (doorlist_x, w * h);
437 sfree (doorlist_y, w * h);
438} 399}
439 400
440/* takes a map and makes it symmetric: adjusts Xsize and 401/* takes a map and makes it symmetric: adjusts Xsize and
441 * Ysize to produce a symmetric map. 402 * Ysize to produce a symmetric map.
442 */ 403 */
… …
500//-GPL 461//-GPL
501 462
502void 463void
503layout::rotate (int rotation) 464layout::rotate (int rotation)
504{ 465{
466 coroapi::cede_to_tick ();
467
505 switch (rotation & 3) 468 switch (rotation & 3)
506 { 469 {
507 case 2: /* a reflection */ 470 case 2: /* a reflection */
508 { 471 {
509 layout new_layout (w, h); 472 layout new_layout (w, h);
… …
661{ 624{
662 layout new_layout (w * 2 - 1, h * 2 - 1); 625 layout new_layout (w * 2 - 1, h * 2 - 1);
663 626
664 new_layout.clear (); 627 new_layout.clear ();
665 628
629 coroapi::cede_to_tick ();
630
666 for (int i = 0; i < w; i++) 631 for (int i = 0; i < w; i++)
667 for (int j = 0; j < h; j++) 632 for (int j = 0; j < h; j++)
668 switch (data [i][j]) 633 switch (data [i][j])
669 { 634 {
670 case '#': expand_wall (new_layout, i, j, *this); break; 635 case '#': expand_wall (new_layout, i, j, *this); break;
… …
752 717
753 return -1; 718 return -1;
754} 719}
755 720
756int 721int
757make_wall (char **maze, int x, int y, int dir) 722make_wall (layout &maze, int x, int y, int dir)
758{ 723{
759 maze[x][y] = 'D'; /* mark a door */ 724 maze[x][y] = 'D'; /* mark a door */
760 725
761 switch (dir) 726 switch (dir)
762 { 727 {
… …
779 744
780void 745void
781layout::roomify () 746layout::roomify ()
782{ 747{
783 int tries = w * h / 30; 748 int tries = w * h / 30;
749
750 coroapi::cede_to_tick ();
784 751
785 for (int ti = 0; ti < tries; ti++) 752 for (int ti = 0; ti < tries; ti++)
786 { 753 {
787 /* starting location for looking at creating a door */ 754 /* starting location for looking at creating a door */
788 int dx = rmg_rndm (w); 755 int dx = rmg_rndm (w);
… …
811 else 778 else
812 make_wall (*this, dx, dy, 1); 779 make_wall (*this, dx, dy, 1);
813 } 780 }
814} 781}
815 782
783//-GPL
784
816///////////////////////////////////////////////////////////////////////////// 785/////////////////////////////////////////////////////////////////////////////
817 786
787// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
788void
789layout::gen_cave (int subtype)
790{
791 switch (subtype)
792 {
793 // a rough cave
794 case 0:
795 fill_rand (rmg_rndm (85, 97));
796 break;
797
798 // corridors
799 case 1:
800 fill_rand (rmg_rndm (5, 40));
801 erode_1_2 (5, 2, 10);
802 erode_1_2 (5, -1, 10);
803 erode_1_2 (5, 2, 1);
804 break;
805
806 // somewhat open, some room-like structures
807 case 2:
808 fill_rand (45);
809 erode_1_2 (5, 2, 4);
810 erode_1_2 (5, -1, 3);
811 break;
812
813 // wide open, roundish
814 case 3:
815 fill_rand (45);
816 erode_1_2 (5, 0, 5);
817 erode_1_2 (5, 1, 1);
818 break;
819 }
820
821 border ();
822 isolation_remover (1);
823}
824
825void
826layout::gen_castle ()
827{
828 fill ('#');
829
830 for (int n = w * h / 30 + 1; n--; )
831 {
832 int rw = rmg_rndm (6, 10);
833 int rh = rmg_rndm (6, 10);
834
835 if (rw > w || rh > h)
836 continue;
837
838 int rx = rmg_rndm (0, w - rw);
839 int ry = rmg_rndm (0, h - rh);
840
841 rect (rx, ry, rx + rw, ry + rh, '#');
842 fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0);
843 }
844
845 border ();
846 isolation_remover (0);
847}
848
818static void 849static void
819gen_mixed_ (layout &maze, random_map_params *RP, int dir) 850gen_mixed_ (layout &maze, random_map_params *RP)
820{ 851{
821 if (maze.w < 20 && maze.h < 20 && !rmg_rndm (3)) 852 if (maze.w > maze.h && maze.w > 16)
822 dir = 2; // stop recursion randomly
823
824 if (dir == 0 && maze.w > 16)
825 { 853 {
826 int m = rmg_rndm (8, maze.w - 8); 854 int m = rmg_rndm (8, maze.w - 8);
827 855
828 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP, !dir); 856 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP);
829 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP, !dir); 857 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP);
830 } 858 }
831 else if (dir == 1 && maze.h > 16) 859 else if (maze.h > 16)
832 { 860 {
833 int m = rmg_rndm (8, maze.h - 8); 861 int m = rmg_rndm (8, maze.h - 8);
834 862
835 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP, !dir); 863 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP);
836 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP, !dir); 864 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP);
837 } 865 }
838 else 866 else
839 { 867 {
840 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1; 868 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
841 869
842 if (RP->map_layout_style == LAYOUT_MULTIPLE) 870 if (RP->map_layout_style == LAYOUT_MULTIPLE)
843 ++RP->map_layout_style; 871 ++RP->map_layout_style;
844 872
845 maze.generate (RP); 873 maze.generate (RP);
846 } 874 }
847}
848 875
876 coroapi::cede_to_tick ();
877}
878
879// recursive subdivision with random sublayouts
849static void 880static void
850gen_mixed (layout &maze, random_map_params *RP) 881gen_mixed (layout &maze, random_map_params *RP)
851{ 882{
852 random_map_params &rp = *new random_map_params (RP); 883 random_map_params &rp = *new random_map_params (RP);
853 gen_mixed_ (maze, &rp, rmg_rndm (2)); 884 gen_mixed_ (maze, &rp);
854 delete &rp; 885 delete &rp;
855 886
856 maze.border (); 887 maze.border ();
888
889 // exits currently do not work so well, as they
890 // are currently often found together, so nuke entrances
891 maze.replace ('<', ' ');
892
857 maze.isolation_remover (); 893 maze.isolation_remover (0);
858} 894}
895
896//+GPL
859 897
860/* function selects the maze function and gives it whatever 898/* function selects the maze function and gives it whatever
861 arguments it needs. */ 899 arguments it needs. */
862void 900void
863layout::generate (random_map_params *RP) 901layout::generate (random_map_params *RP)
… …
923 if (rmg_rndm (2)) 961 if (rmg_rndm (2))
924 doorify (); 962 doorify ();
925 963
926 break; 964 break;
927 965
966 case LAYOUT_CASTLE:
967 gen_castle ();
968
969 if (rmg_rndm (2))
970 doorify ();
971
972 break;
973
928 case LAYOUT_MULTIPLE: 974 case LAYOUT_MULTIPLE:
929 gen_mixed (*this, RP); 975 gen_mixed (*this, RP);
930 break; 976 break;
931 977
932 default: 978 default:
… …
935} 981}
936 982
937//-GPL 983//-GPL
938 984
939#if 0 985#if 0
986static void
987gen_village (layout &maze)
988{
989 maze.clear ();
990 maze.border ();
991
992 for (int n = maze.w * maze.h / 200 + 1; n--; )
993 {
994 int rw = rmg_rndm (6, 10);
995 int rh = rmg_rndm (6, 10);
996
997 int rx = rmg_rndm (2, maze.w - rw - 2);
998 int ry = rmg_rndm (2, maze.h - rh - 2);
999
1000 maze.rect (rx, ry, rx + rw, ry + rh, '#');
1001 }
1002
1003 maze.border ();
1004 maze.isolation_remover (2);
1005}
1006
940static struct demo 1007static struct demo
941{ 1008{
942 demo () 1009 demo ()
943 { 1010 {
944 rmg_rndm.seed (time (0)); 1011 rmg_rndm.seed (time (0));
945 1012
946 for(int i=1;i<100;i++) 1013 for(int i=1;i<100;i++)
947 { 1014 {
948 layout maze (40, 25); 1015 layout maze (40, 30);
949 maze.fill_rand (85); 1016 gen_village (maze);
950 maze.border (); 1017 maze.doorify ();
951 maze.isolation_remover ();
952 maze.print (); 1018 maze.print ();
1019 exit(0);
953 } 1020 }
954 1021
955 exit (1); 1022 exit (1);
956 } 1023 }
957} demo; 1024} demo;

Diff Legend

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