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.14 by root, Sat Jul 3 02:19:10 2010 UTC vs.
Revision 1.21 by root, Sun Jul 4 01:01:42 2010 UTC

77} 77}
78 78
79void 79void
80layout::fill (char fill) 80layout::fill (char fill)
81{ 81{
82 memset (data [0], fill, w * h); 82 //memset (data [0], fill, w * h); // only when contiguous :/
83 fill_rect (0, 0, w, h, fill);
83} 84}
84 85
85void 86void
86layout::rect (int x1, int y1, int x2, int y2, char fill) 87layout::rect (int x1, int y1, int x2, int y2, char fill)
87{ 88{
220 if (x < dist.w - 1 && !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);
221 } 222 }
222} 223}
223 224
224static inline void 225static inline void
225make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d) 226make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb)
226{ 227{
227 for (;;) 228 for (;;)
228 { 229 {
229 point neigh[4]; 230 point neigh[4];
230 int ncnt = 0; 231 int ncnt = 0;
231 232
233 d += perturb > 1;
234
232 if (x > 0 && U8 (dist [x - 1][y]) <= d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y); 235 if (x > 0 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
233 if (x < dist.w - 1 && 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);
234 if (y > 0 && U8 (dist [x][y - 1]) <= d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1); 237 if (y > 0 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
235 if (y < dist.h - 1 && 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);
236 239
237 if (!ncnt) 240 if (!ncnt)
238 return; 241 return;
239 242
240 point &p = neigh [rmg_rndm (ncnt)]; 243 point p = neigh [perturb ? rmg_rndm (ncnt) : 0];
241 244
242 seeds.push (p); 245 seeds.push (p);
243 246
244 x = p.x; 247 x = p.x;
245 y = p.y; 248 y = p.y;
263} 266}
264 267
265// isolation remover, works on a "distance" map 268// isolation remover, works on a "distance" map
266// the map must be initialised with 0 == rooms, 255 = walls 269// the map must be initialised with 0 == rooms, 255 = walls
267static void noinline 270static void noinline
268isolation_remover (layout &dist) 271isolation_remover (layout &dist, unsigned int perturb = 2)
269{ 272{
270 // dist contains 273 // dist contains
271 // 0 == invisited rooms 274 // 0 == invisited rooms
272 // 1 == visited rooms 275 // 1 == visited rooms
273 // 2+ shortest distance to random near room 276 // 2+ shortest distance to random near room
274 277
278 clamp_it (perturb, 0, 2);
279
275 // phase 1, find seed 280 // phase 1, find seed
276 int cnt = 0; 281 int cnt = 0;
277 int x, y; 282 int x, y;
278 283
279 for (int i = 0; i < dist.w; ++i) 284 for (int i = 0; i < dist.w; ++i)
310 315
311 if (!dist [x][y]) 316 if (!dist [x][y])
312 { 317 {
313 // found new isolated area, make tunnel 318 // found new isolated area, make tunnel
314 push_flood_fill (dist, seeds, x, y); 319 push_flood_fill (dist, seeds, x, y);
315 make_tunnel (dist, seeds, x, y, 255); 320 make_tunnel (dist, seeds, x, y, 254, perturb);
316 } 321 }
317 else 322 else
318 { 323 {
319 // nothing here, continue to expand 324 // nothing here, continue to expand
320 U8 d = U8 (dist [x][y]) + 1; 325 U8 d = U8 (dist [x][y]) + 1;
326 } 331 }
327 } 332 }
328} 333}
329 334
330void 335void
331layout::isolation_remover () 336layout::isolation_remover (int perturb)
332{ 337{
333 layout dist (w - 2, h - 2); // map without border 338 layout dist (w - 2, h - 2); // map without border
334 339
335 for (int x = 1; x < w - 1; ++x) 340 for (int x = 1; x < w - 1; ++x)
336 for (int y = 1; y < h - 1; ++y) 341 for (int y = 1; y < h - 1; ++y)
337 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0; 342 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
338 343
339 ::isolation_remover (dist); 344 ::isolation_remover (dist, perturb);
340 345
341 // now copy the tunnels over 346 // now copy the tunnels over
342 for (int x = 1; x < w - 1; ++x) 347 for (int x = 1; x < w - 1; ++x)
343 for (int y = 1; y < h - 1; ++y) 348 for (int y = 1; y < h - 1; ++y)
344 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1) 349 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
345 data [x][y] = 0; 350 data [x][y] = 0;
346} 351}
347 352
348///////////////////////////////////////////////////////////////////////////// 353/////////////////////////////////////////////////////////////////////////////
349 354
350// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
351void
352layout::gen_cave (int subtype)
353{
354 switch (subtype)
355 {
356 // a rough cave
357 case 0:
358 fill_rand (rmg_rndm (85, 97));
359 break;
360
361 // corridors
362 case 1:
363 fill_rand (rmg_rndm (5, 40));
364 erode_1_2 (5, 2, 10);
365 erode_1_2 (5, -1, 10);
366 erode_1_2 (5, 2, 1);
367 break;
368
369 // somewhat open, roundish
370 case 2:
371 fill_rand (45);
372 erode_1_2 (5, 0, 5);
373 erode_1_2 (5, 1, 1);
374 break;
375
376 // wide open, some room-like structures
377 case 3:
378 fill_rand (45);
379 erode_1_2 (5, 2, 4);
380 erode_1_2 (5, -1, 3);
381 break;
382 }
383
384 border ();
385 isolation_remover ();
386}
387
388/////////////////////////////////////////////////////////////////////////////
389
390//+GPL 355//+GPL
391 356
392/* puts doors at appropriate locations in a maze. */ 357/* puts doors at appropriate locations in a maze. */
393void 358void
394layout::doorify () 359layout::doorify ()
395{ 360{
396 int ndoors = w * h / 60; /* reasonable number of doors. */ 361 int ndoors = w * h / 60; /* reasonable number of doors. */
397 int doorlocs = 0; /* # of available doorlocations */
398 362
399 uint16 *doorlist_x = salloc<uint16> (w * h); 363 fixed_stack<point> doorloc (w * h);
400 uint16 *doorlist_y = salloc<uint16> (w * h);
401 364
402 /* make a list of possible door locations */ 365 /* make a list of possible door locations */
403 for (int i = 1; i < w - 1; i++) 366 for (int i = 1; i < w - 1; i++)
404 for (int j = 1; j < h - 1; j++) 367 for (int j = 1; j < h - 1; j++)
405 { 368 {
406 int sindex = surround_flag (*this, i, j); 369 int sindex = surround_flag (*this, i, j);
407 370
408 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 371 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
409 { 372 doorloc.push (point (i, j));
410 doorlist_x [doorlocs] = i;
411 doorlist_y [doorlocs] = j;
412 doorlocs++;
413 }
414 } 373 }
415 374
416 while (ndoors > 0 && doorlocs > 0) 375 while (ndoors && doorloc.size)
417 { 376 {
418 int di = rmg_rndm (doorlocs); 377 point p = doorloc.remove (rmg_rndm (doorloc.size));
419 int i = doorlist_x [di]; 378
420 int j = doorlist_y [di];
421 int sindex = surround_flag (*this, i, j); 379 int sindex = surround_flag (*this, p.x, p.y);
422 380
423 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 381 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
424 { 382 {
425 data [i][j] = 'D'; 383 data [p.x][p.y] = 'D';
426 ndoors--; 384 --ndoors;
427 } 385 }
428
429 /* reduce the size of the list */
430 doorlocs--;
431 doorlist_x[di] = doorlist_x [doorlocs];
432 doorlist_y[di] = doorlist_y [doorlocs];
433 } 386 }
434
435 sfree (doorlist_x, w * h);
436 sfree (doorlist_y, w * h);
437} 387}
438 388
439/* takes a map and makes it symmetric: adjusts Xsize and 389/* takes a map and makes it symmetric: adjusts Xsize and
440 * Ysize to produce a symmetric map. 390 * Ysize to produce a symmetric map.
441 */ 391 */
810 else 760 else
811 make_wall (*this, dx, dy, 1); 761 make_wall (*this, dx, dy, 1);
812 } 762 }
813} 763}
814 764
765//-GPL
766
815///////////////////////////////////////////////////////////////////////////// 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);
829}
830
831static void
832gen_mixed_ (layout &maze, random_map_params *RP)
833{
834 int dir;
835
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;
840
841 if (dir == 0 && maze.w > 16)
842 {
843 int m = rmg_rndm (8, maze.w - 8);
844
845 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP);
846 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP);
847 }
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
816 879
817/* function selects the maze function and gives it whatever 880/* function selects the maze function and gives it whatever
818 arguments it needs. */ 881 arguments it needs. */
819void 882void
820layout::generate (random_map_params *RP) 883layout::generate (random_map_params *RP)
880 if (rmg_rndm (2)) 943 if (rmg_rndm (2))
881 doorify (); 944 doorify ();
882 945
883 break; 946 break;
884 947
948 case LAYOUT_CASTLE:
949 gen_castle ();
950
951 if (rmg_rndm (2))
952 doorify ();
953
954 break;
955
956 case LAYOUT_MULTIPLE:
957 gen_mixed (*this, RP);
958 break;
959
885 default: 960 default:
886 abort (); 961 abort ();
887 } 962 }
963}
888 964
889 /* rotate the maze randomly */ 965//-GPL
890 rotate (rmg_rndm (4));
891
892 symmetrize (RP->symmetry_used);
893 966
894#if 0 967#if 0
895 print ();//D 968static void
896#endif 969gen_village (layout &maze)
970{
971 maze.clear ();
972 maze.border ();
897 973
898 if (RP->expand2x) 974 for (int n = maze.w * maze.h / 200 + 1; n--; )
899 expand2x (); 975 {
900} 976 int rw = rmg_rndm (6, 10);
977 int rh = rmg_rndm (6, 10);
901 978
902//-GPL 979 int rx = rmg_rndm (2, maze.w - rw - 2);
980 int ry = rmg_rndm (2, maze.h - rh - 2);
903 981
904#if 0 982 maze.rect (rx, ry, rx + rw, ry + rh, '#');
983 }
984
985 maze.border ();
986 maze.isolation_remover (2);
987}
988
905static struct demo 989static struct demo
906{ 990{
907 demo () 991 demo ()
908 { 992 {
909 rmg_rndm.seed (time (0)); 993 rmg_rndm.seed (time (0));
910 994
911 for(int i=1;i<100;i++) 995 for(int i=1;i<100;i++)
912 { 996 {
913 layout maze (40, 25); 997 layout maze (40, 30);
914 maze.fill_rand (85); 998 gen_village (maze);
915 maze.border (); 999 maze.doorify ();
916 maze.isolation_remover ();
917 maze.print (); 1000 maze.print ();
1001 exit(0);
918 } 1002 }
919 1003
920 exit (1); 1004 exit (1);
921 } 1005 }
922} demo; 1006} demo;

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines