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.19 by root, Sat Jul 3 19:22:21 2010 UTC vs.
Revision 1.29 by root, Tue Jan 3 11:25:33 2012 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,2011,2012 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice) 5 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
6 * 6 *
7 * 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
8 * 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
9 * 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
10 * option) any later version. 10 * option) any later version.
… …
20 * 20 *
21 * 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>
22 */ 22 */
23 23
24#include <global.h> 24#include <global.h>
25#include <random_map.h> 25#include <rmg.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, int perturb) 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];
… …
302 seeds.push (point (x, y)); 312 seeds.push (point (x, y));
303 313
304 // phase 2, while we have seeds, if 314 // phase 2, while we have seeds, if
305 // seed is empty, floodfill, else grow 315 // seed is empty, floodfill, else grow
306 316
317 int rem_index = 0; // used to remove "somewhat ordered"
318
307 while (seeds.size) 319 while (seeds.size)
308 { 320 {
309 coroapi::cede_to_tick (); 321 coroapi::cede_to_tick ();
310 322
323 int i = perturb
324 ? rmg_rndm (max (0, seeds.size - 8), seeds.size - 1)
325 : rem_index ++ % seeds.size;
326
311 point p = seeds.remove (rmg_rndm (seeds.size)); 327 point p = seeds.remove (i);
312 328
313 x = p.x; 329 x = p.x;
314 y = p.y; 330 y = p.y;
315 331
316 if (!dist [x][y]) 332 if (!dist [x][y])
… …
358void 374void
359layout::doorify () 375layout::doorify ()
360{ 376{
361 int ndoors = w * h / 60; /* reasonable number of doors. */ 377 int ndoors = w * h / 60; /* reasonable number of doors. */
362 378
379 coroapi::cede_to_tick ();
380
363 fixed_stack<point> doorloc (w * h); 381 fixed_stack<point> doorloc (w * h);
364 382
365 /* make a list of possible door locations */ 383 /* make a list of possible door locations */
366 for (int i = 1; i < w - 1; i++) 384 for (int i = 1; i < w - 1; i++)
367 for (int j = 1; j < h - 1; j++) 385 for (int j = 1; j < h - 1; j++)
… …
449//-GPL 467//-GPL
450 468
451void 469void
452layout::rotate (int rotation) 470layout::rotate (int rotation)
453{ 471{
472 coroapi::cede_to_tick ();
473
454 switch (rotation & 3) 474 switch (rotation & 3)
455 { 475 {
456 case 2: /* a reflection */ 476 case 2: /* a reflection */
457 { 477 {
458 layout new_layout (w, h); 478 layout new_layout (w, h);
… …
610{ 630{
611 layout new_layout (w * 2 - 1, h * 2 - 1); 631 layout new_layout (w * 2 - 1, h * 2 - 1);
612 632
613 new_layout.clear (); 633 new_layout.clear ();
614 634
635 coroapi::cede_to_tick ();
636
615 for (int i = 0; i < w; i++) 637 for (int i = 0; i < w; i++)
616 for (int j = 0; j < h; j++) 638 for (int j = 0; j < h; j++)
617 switch (data [i][j]) 639 switch (data [i][j])
618 { 640 {
619 case '#': expand_wall (new_layout, i, j, *this); break; 641 case '#': expand_wall (new_layout, i, j, *this); break;
… …
701 723
702 return -1; 724 return -1;
703} 725}
704 726
705int 727int
706make_wall (char **maze, int x, int y, int dir) 728make_wall (layout &maze, int x, int y, int dir)
707{ 729{
708 maze[x][y] = 'D'; /* mark a door */ 730 maze[x][y] = 'D'; /* mark a door */
709 731
710 switch (dir) 732 switch (dir)
711 { 733 {
… …
728 750
729void 751void
730layout::roomify () 752layout::roomify ()
731{ 753{
732 int tries = w * h / 30; 754 int tries = w * h / 30;
755
756 coroapi::cede_to_tick ();
733 757
734 for (int ti = 0; ti < tries; ti++) 758 for (int ti = 0; ti < tries; ti++)
735 { 759 {
736 /* starting location for looking at creating a door */ 760 /* starting location for looking at creating a door */
737 int dx = rmg_rndm (w); 761 int dx = rmg_rndm (w);
… …
812 for (int n = w * h / 30 + 1; n--; ) 836 for (int n = w * h / 30 + 1; n--; )
813 { 837 {
814 int rw = rmg_rndm (6, 10); 838 int rw = rmg_rndm (6, 10);
815 int rh = rmg_rndm (6, 10); 839 int rh = rmg_rndm (6, 10);
816 840
841 if (rw > w || rh > h)
842 continue;
843
817 int rx = rmg_rndm (0, w - rw); 844 int rx = rmg_rndm (0, w - rw);
818 int ry = rmg_rndm (0, h - rh); 845 int ry = rmg_rndm (0, h - rh);
819 846
820 rect (rx, ry, rx + rw, ry + rh, '#'); 847 rect (rx, ry, rx + rw, ry + rh, '#');
821 fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0); 848 fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0);
… …
824 border (); 851 border ();
825 isolation_remover (0); 852 isolation_remover (0);
826} 853}
827 854
828static void 855static void
829gen_mixed_ (layout &maze, random_map_params *RP, int dir) 856gen_mixed_ (layout &maze, random_map_params *RP)
830{ 857{
831 if (maze.w < 20 && maze.h < 20 && !rmg_rndm (3)) 858 if (maze.w > maze.h && maze.w > 16)
832 dir = 2; // stop recursion randomly
833
834 if (dir == 0 && maze.w > 16)
835 { 859 {
836 int m = rmg_rndm (8, maze.w - 8); 860 int m = rmg_rndm (8, maze.w - 8);
837 861
838 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP, !dir); 862 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP);
839 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP, !dir); 863 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP);
840 } 864 }
841 else if (dir == 1 && maze.h > 16) 865 else if (maze.h > 16)
842 { 866 {
843 int m = rmg_rndm (8, maze.h - 8); 867 int m = rmg_rndm (8, maze.h - 8);
844 868
845 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP, !dir); 869 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP);
846 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP, !dir); 870 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP);
847 } 871 }
848 else 872 else
849 { 873 {
850 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1; 874 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
851 875
852 if (RP->map_layout_style == LAYOUT_MULTIPLE) 876 if (RP->map_layout_style == LAYOUT_MULTIPLE)
853 ++RP->map_layout_style; 877 ++RP->map_layout_style;
854 878
855 maze.generate (RP); 879 maze.generate (RP);
856 } 880 }
881
882 coroapi::cede_to_tick ();
857} 883}
858 884
859// recursive subdivision with random sublayouts 885// recursive subdivision with random sublayouts
860static void 886static void
861gen_mixed (layout &maze, random_map_params *RP) 887gen_mixed (layout &maze, random_map_params *RP)
862{ 888{
863 random_map_params &rp = *new random_map_params (RP); 889 random_map_params &rp = *new random_map_params (RP);
864 gen_mixed_ (maze, &rp, rmg_rndm (2)); 890 gen_mixed_ (maze, &rp);
865 delete &rp; 891 delete &rp;
866 892
867 maze.border (); 893 maze.border ();
894
895 // exits currently do not work so well, as they
896 // are currently often found together, so nuke entrances
897 maze.replace ('<', ' ');
898
868 maze.isolation_remover (0); 899 maze.isolation_remover (0);
869} 900}
870 901
871//+GPL 902//+GPL
872 903
… …
982static struct demo 1013static struct demo
983{ 1014{
984 demo () 1015 demo ()
985 { 1016 {
986 rmg_rndm.seed (time (0)); 1017 rmg_rndm.seed (time (0));
1018 extern void hack();hack ();
987 1019
988 for(int i=1;i<100;i++) 1020 for(int i=1;i<100;i++)
989 { 1021 {
990 layout maze (40, 30); 1022 layout maze (40, 30);
991 gen_village (maze); 1023 maze.fill_rand (99);
992 maze.doorify (); 1024 maze.border ();
1025 maze.isolation_remover (2);
993 maze.print (); 1026 maze.print ();
994 exit(0);
995 } 1027 }
996 1028
997 exit (1); 1029 exit (1);
998 } 1030 }
999} demo; 1031} demo;

Diff Legend

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