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.9 by root, Fri Jul 2 17:18:04 2010 UTC vs.
Revision 1.17 by root, Sat Jul 3 13:14:35 2010 UTC

34 this->h = h; 34 this->h = h;
35 35
36 // we store the layout in a single contiguous memory layout 36 // we store the layout in a single contiguous memory layout
37 // first part consists of pointers to each column, followed 37 // first part consists of pointers to each column, followed
38 // by the actual columns (not rows!) 38 // by the actual columns (not rows!)
39 int size = (sizeof (cell *) + sizeof (cell) * h) * w; 39 size = (sizeof (cell *) + sizeof (cell) * h) * w;
40
41 data = (cell **)salloc<char> (size); 40 data = (cell **)salloc<char> (size);
42 41
43 cell *p = (cell *)(data + w); 42 cell *p = (cell *)(data + w);
44 43
45 for (int x = w; x--; ) 44 for (int x = 0; x < w; ++x)
46 data [x] = p + x * h; 45 data [x] = p + x * h;
47} 46}
48 47
49layout::layout (int w, int h) 48layout::layout (int w, int h)
50{ 49{
56 alloc (copy.w, copy.h); 55 alloc (copy.w, copy.h);
57 56
58 memcpy (data [0], copy.data [0], sizeof (cell) * h * w); 57 memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
59} 58}
60 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
61layout::~layout () 74layout::~layout ()
62{ 75{
63 int size = (sizeof (cell *) + sizeof (cell) * h) * w;
64
65 sfree ((char *)data, size); 76 sfree ((char *)data, size);
66} 77}
67 78
68void 79void
69layout::fill (char fill) 80layout::fill (char fill)
70{ 81{
71 memset (data [0], fill, w * h); 82 //memset (data [0], fill, w * h); // only when contiguous :/
83 fill_rect (0, 0, w, h, fill);
72} 84}
73 85
74void 86void
75layout::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)
76{ 100{
77 for (; x1 < x2; ++x1) 101 for (; x1 < x2; ++x1)
78 memset (data [x1] + y1, fill, y2 - y1); 102 memset (data [x1] + y1, fill, y2 - y1);
79} 103}
80 104
81void layout::border (char fill) 105void layout::border (char fill)
82{ 106{
83 for (int i = 0; i < w; i++) data [i][0] = data [i][h - 1] = fill; 107 rect (0, 0, w, h, fill);
84 for (int j = 0; j < h; j++) data [0][j] = data [w - 1][j] = fill;
85} 108}
86 109
87void 110void
88layout::fill_rand (int percent) 111layout::fill_rand (int percent)
89{ 112{
171///////////////////////////////////////////////////////////////////////////// 194/////////////////////////////////////////////////////////////////////////////
172// isolation remover - ensures single connected area 195// isolation remover - ensures single connected area
173 196
174typedef fixed_stack<point> pointlist; 197typedef fixed_stack<point> pointlist;
175 198
176static noinline void 199static void noinline
177push_flood_fill (layout &dist, pointlist &seeds, int x, int y) 200push_flood_fill (layout &dist, pointlist &seeds, int x, int y)
178{ 201{
179 if (dist [x][y]) 202 if (dist [x][y])
180 return; 203 return;
181 204
192 ++y; 215 ++y;
193 } 216 }
194 217
195 while (--y >= y0) 218 while (--y >= y0)
196 { 219 {
197 if (x > 0) push_flood_fill (dist, seeds, x - 1, y); 220 if (x > 0 && !dist [x - 1][y]) push_flood_fill (dist, seeds, x - 1, y);
198 if (x < dist.w - 1) 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);
199 } 222 }
200} 223}
201 224
202static inline void 225static inline void
203make_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)
204{ 227{
205 for (;;) 228 for (;;)
206 { 229 {
230 point neigh[4];
231 int ncnt = 0;
232
233 d += perturb > 1;
234
207 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) 235 if (x > 0 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
208 --x;
209 else if (x < dist.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) 236 if (x < dist.w - 1 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y);
210 ++x;
211 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) 237 if (y > 0 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
212 --y;
213 else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) 238 if (y < dist.h - 1 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
214 ++y; 239
215 else 240 if (!ncnt)
216 break; 241 return;
242
243 point &p = neigh [perturb ? rmg_rndm (ncnt) : 0];
244
245 seeds.push (p);
246
247 x = p.x;
248 y = p.y;
217 249
218 d = dist [x][y]; 250 d = dist [x][y];
219 dist [x][y] = 1; 251 dist [x][y] = 1;
220 seeds.push (point (x, y));
221 } 252 }
222} 253}
223 254
224static void inline 255static void inline
225maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d) 256maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d)
232 return; 263 return;
233 264
234 seeds.push (point (x, y)); 265 seeds.push (point (x, y));
235} 266}
236 267
237void 268// isolation remover, works on a "distance" map
238layout::isolation_remover (bool dirty) 269// the map must be initialised with 0 == rooms, 255 = walls
270static void noinline
271isolation_remover (layout &dist, unsigned int perturb = 2)
239{ 272{
240 layout dist (w, h);
241
242 // dist contains 273 // dist contains
243 // 0 == invisited rooms 274 // 0 == invisited rooms
244 // 1 == visited rooms 275 // 1 == visited rooms
245 // 2+ shortest distance to random near room 276 // 2+ shortest distance to random near room
246 277
247 // phase 1, initialise dist array, find seed 278 max_it (perturb, 0);
279 min_it (perturb, 2);
280
281 // phase 1, find seed
248 int cnt = 0; 282 int cnt = 0;
249 int x, y; 283 int x, y;
250 284
251 for (int i = 0; i < w; ++i) 285 for (int i = 0; i < dist.w; ++i)
252 for (int j = 0; j < h; ++j) 286 for (int j = 0; j < dist.h; ++j)
253 { 287 if (!dist [i][j] && !rmg_rndm (++cnt))
254 if (data [i][j] == '#')
255 dist [i][j] = U8 (255);
256 else
257 {
258 dist [i][j] = 0;
259 if (!rmg_rndm (++cnt))
260 x = i, y = j; 288 x = i, y = j;
261 }
262 }
263 289
264 if (!cnt) 290 if (!cnt)
265 { 291 {
266 // map is completely massive, this is not good, 292 // map is completely massive, this is not good,
267 // so make it empty instead. 293 // so make it empty instead.
268 clear (); 294 dist.fill (1);
269 border ();
270 return; 295 return;
271 } 296 }
272 297
273 fixed_stack<point> seeds (w * h * 5); 298 fixed_stack<point> seeds (dist.w * dist.h * 5);
274 299
275 // found first free space - picking the first one gives 300 // found first free space - picking the first one gives
276 // us a slight bias for tunnels, but usually you won't 301 // us a slight bias for tunnels, but usually you won't
277 // notice that in-game 302 // notice that in-game
278 seeds.push (point (x, y)); 303 seeds.push (point (x, y));
290 y = p.y; 315 y = p.y;
291 316
292 if (!dist [x][y]) 317 if (!dist [x][y])
293 { 318 {
294 // found new isolated area, make tunnel 319 // found new isolated area, make tunnel
295 if (!dirty)
296 push_flood_fill (dist, seeds, x, y); 320 push_flood_fill (dist, seeds, x, y);
297
298 make_tunnel (dist, seeds, x, y, 255); 321 make_tunnel (dist, seeds, x, y, 254, perturb);
299
300 if (dirty)
301 push_flood_fill (dist, seeds, x, y);
302 } 322 }
303 else 323 else
304 { 324 {
305 // nothing here, continue to expand 325 // nothing here, continue to expand
306 U8 d = U8 (dist [x][y]) + 1; 326 U8 d = U8 (dist [x][y]) + 1;
309 if (x > 0) maybe_push (dist, seeds, x - 1, y, d); 329 if (x > 0) maybe_push (dist, seeds, x - 1, y, d);
310 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d); 330 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d);
311 if (y > 0) maybe_push (dist, seeds, x, y - 1, d); 331 if (y > 0) maybe_push (dist, seeds, x, y - 1, d);
312 } 332 }
313 } 333 }
334}
335
336void
337layout::isolation_remover (int perturb)
338{
339 layout dist (w - 2, h - 2); // map without border
340
341 for (int x = 1; x < w - 1; ++x)
342 for (int y = 1; y < h - 1; ++y)
343 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
344
345 ::isolation_remover (dist, perturb);
314 346
315 // now copy the tunnels over 347 // now copy the tunnels over
316 for (int x = 0; x < w; ++x) 348 for (int x = 1; x < w - 1; ++x)
317 for (int y = 0; y < h; ++y) 349 for (int y = 1; y < h - 1; ++y)
318 if (data [x][y] == '#' && dist [x][y] == 1) 350 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
319 data [x][y] = 0; 351 data [x][y] = 0;
320}
321
322/////////////////////////////////////////////////////////////////////////////
323
324// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
325void
326layout::gen_cave (int subtype)
327{
328 switch (subtype)
329 {
330 // a rough cave
331 case 0:
332 fill_rand (rmg_rndm (80, 95));
333 break;
334
335 // corridors
336 case 1:
337 fill_rand (rmg_rndm (5, 40));
338 erode_1_2 (5, 2, 10);
339 erode_1_2 (5, -1, 10);
340 erode_1_2 (5, 2, 1);
341 break;
342
343 // somewhat open, roundish
344 case 2:
345 fill_rand (45);
346 erode_1_2 (5, 0, 5);
347 erode_1_2 (5, 1, 1);
348 break;
349
350 // wide open, some room-like structures
351 case 3:
352 fill_rand (45);
353 erode_1_2 (5, 2, 4);
354 erode_1_2 (5, -1, 3);
355 break;
356 }
357
358 border ();
359 isolation_remover ();
360} 352}
361 353
362///////////////////////////////////////////////////////////////////////////// 354/////////////////////////////////////////////////////////////////////////////
363 355
364//+GPL 356//+GPL
785 make_wall (*this, dx, dy, 1); 777 make_wall (*this, dx, dy, 1);
786 } 778 }
787} 779}
788 780
789///////////////////////////////////////////////////////////////////////////// 781/////////////////////////////////////////////////////////////////////////////
782
783// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
784void
785layout::gen_cave (int subtype)
786{
787 switch (subtype)
788 {
789 // a rough cave
790 case 0:
791 fill_rand (rmg_rndm (85, 97));
792 break;
793
794 // corridors
795 case 1:
796 fill_rand (rmg_rndm (5, 40));
797 erode_1_2 (5, 2, 10);
798 erode_1_2 (5, -1, 10);
799 erode_1_2 (5, 2, 1);
800 break;
801
802 // somewhat open, roundish
803 case 2:
804 fill_rand (45);
805 erode_1_2 (5, 0, 5);
806 erode_1_2 (5, 1, 1);
807 break;
808
809 // wide open, some room-like structures
810 case 3:
811 fill_rand (45);
812 erode_1_2 (5, 2, 4);
813 erode_1_2 (5, -1, 3);
814 break;
815 }
816
817 border ();
818 isolation_remover ();
819}
820
821void
822layout::gen_castle ()
823{
824 fill ('#');
825
826 for (int n = w * h / 30 + 1; n--; )
827 {
828 int rw = rmg_rndm (6, 10);
829 int rh = rmg_rndm (6, 10);
830
831 int rx = rmg_rndm (0, w - rw);
832 int ry = rmg_rndm (0, h - rh);
833
834 rect (rx, ry, rx + rw, ry + rh, '#');
835 fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0);
836 }
837
838 border ();
839 isolation_remover (0);
840}
841
842static void
843gen_mixed_ (layout &maze, random_map_params *RP, int dir)
844{
845 if (maze.w < 20 && maze.h < 20 && !rmg_rndm (3))
846 dir = 2; // stop recursion randomly
847
848 if (dir == 0 && maze.w > 16)
849 {
850 int m = rmg_rndm (8, maze.w - 8);
851
852 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP, !dir);
853 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP, !dir);
854 }
855 else if (dir == 1 && maze.h > 16)
856 {
857 int m = rmg_rndm (8, maze.h - 8);
858
859 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP, !dir);
860 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP, !dir);
861 }
862 else
863 {
864 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
865
866 if (RP->map_layout_style == LAYOUT_MULTIPLE)
867 ++RP->map_layout_style;
868
869 maze.generate (RP);
870 }
871}
872
873// recursive subdivision with random sublayouts
874static void
875gen_mixed (layout &maze, random_map_params *RP)
876{
877 random_map_params &rp = *new random_map_params (RP);
878 gen_mixed_ (maze, &rp, rmg_rndm (2));
879 delete &rp;
880
881 maze.border ();
882 maze.isolation_remover ();
883}
790 884
791/* function selects the maze function and gives it whatever 885/* function selects the maze function and gives it whatever
792 arguments it needs. */ 886 arguments it needs. */
793void 887void
794layout::generate (random_map_params *RP) 888layout::generate (random_map_params *RP)
854 if (rmg_rndm (2)) 948 if (rmg_rndm (2))
855 doorify (); 949 doorify ();
856 950
857 break; 951 break;
858 952
953 case LAYOUT_CASTLE:
954 gen_castle ();
955
956 if (rmg_rndm (2))
957 doorify ();
958
959 break;
960
961 case LAYOUT_MULTIPLE:
962 gen_mixed (*this, RP);
963 break;
964
859 default: 965 default:
860 abort (); 966 abort ();
861 } 967 }
862
863 /* rotate the maze randomly */
864 rotate (rmg_rndm (4));
865
866 symmetrize (RP->symmetry_used);
867
868#if 0
869 print ();//D
870#endif
871
872 if (RP->expand2x)
873 expand2x ();
874} 968}
875 969
876//-GPL 970//-GPL
877 971
878#if 0 972#if 0
880{ 974{
881 demo () 975 demo ()
882 { 976 {
883 rmg_rndm.seed (time (0)); 977 rmg_rndm.seed (time (0));
884 978
885 for(int i=1;i<10;i) 979 for(int i=1;i<100;i++)
886 { 980 {
887 layout maze (10, 10); 981 layout maze (40, 25);
888 maze.fill_rand (90); 982 maze.gen_castle ();
889 maze.border ();
890 maze.isolation_remover ();
891 maze.doorify (); 983 maze.doorify ();
892 maze.symmetrize (rmg_rndm (2, 4));
893 maze.rotate (rmg_rndm (4));
894 maze.expand2x ();
895 maze.print (); 984 maze.print ();
985 exit(0);
896 } 986 }
897 987
898 exit (1); 988 exit (1);
899 } 989 }
900} demo; 990} demo;

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines