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.7 by root, Fri Jul 2 15:03:57 2010 UTC vs.
Revision 1.13 by root, Sat Jul 3 01:52:52 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
29layout::alloc (int w, int h)
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!)
39 int size = (sizeof (cell *) + sizeof (cell) * h) * w;
40
41 data = (cell **)salloc<char> (size);
42
43 cell *p = (cell *)(data + w);
44
45 for (int x = w; x--; )
46 data [x] = p + x * h;
47}
48
28layout::layout (int w, int h) 49layout::layout (int w, int h)
29: w(w), h(h)
30{ 50{
31 int size = (sizeof (char *) + sizeof (char) * h) * w; 51 alloc (w, h);
52}
32 53
33 col = (char **)salloc<char> (size); 54layout::layout (layout &copy)
55{
56 alloc (copy.w, copy.h);
34 57
35 char *data = (char *)(col + w); 58 memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
36
37 for (int x = w; x--; )
38 col [x] = data + x * h;
39} 59}
40 60
41layout::~layout () 61layout::~layout ()
42{ 62{
43 int size = (sizeof (char *) + sizeof (char) * h) * w; 63 int size = (sizeof (cell *) + sizeof (cell) * h) * w;
44 64
45 sfree ((char *)col, size); 65 sfree ((char *)data, size);
46} 66}
47 67
48void 68void
49layout::fill (char fill) 69layout::fill (char fill)
50{ 70{
51 memset (col [0], fill, w * h); 71 memset (data [0], fill, w * h);
52} 72}
53 73
54void 74void
55layout::rect (int x1, int y1, int x2, int y2, char fill) 75layout::rect (int x1, int y1, int x2, int y2, char fill)
56{ 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)
88{
57 for (; x1 < x2; ++x1) 89 for (; x1 < x2; ++x1)
58 memset (col [x1] + y1, fill, y2 - y1); 90 memset (data [x1] + y1, fill, y2 - y1);
59} 91}
60 92
61void layout::border (char fill) 93void layout::border (char fill)
62{ 94{
63 for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill; 95 rect (0, 0, w, h, fill);
64 for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill;
65} 96}
66 97
67void 98void
68layout::fill_rand (int percent) 99layout::fill_rand (int percent)
69{ 100{
70 percent = lerp (percent, 0, 100, 0, 256); 101 percent = lerp (percent, 0, 100, 0, 256);
71 102
72 for (int x = w - 1; --x > 0; ) 103 for (int x = w - 1; --x > 0; )
73 for (int y = h - 1; --y > 0; ) 104 for (int y = h - 1; --y > 0; )
74 col [x][y] = rmg_rndm (256) > percent ? 0 : '#'; 105 data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
75} 106}
76 107
77///////////////////////////////////////////////////////////////////////////// 108/////////////////////////////////////////////////////////////////////////////
78 109
79// erode by cellular automata 110// erode by cellular automata
… …
104 for (int i = array_length (dds); i--; ) 135 for (int i = array_length (dds); i--; )
105 { 136 {
106 int nx = x + dds [i][0]; 137 int nx = x + dds [i][0];
107 int ny = y + dds [i][1]; 138 int ny = y + dds [i][1];
108 139
109 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])
110 { 141 {
111 n1 += dds [i][2]; 142 n1 += dds [i][2];
112 n2++; 143 n2++;
113 } 144 }
114 } 145 }
… …
128{ 159{
129 for (int y = 0; y < h; y++) 160 for (int y = 0; y < h; y++)
130 { 161 {
131 for (int x = 0; x < w; x++) 162 for (int x = 0; x < w; x++)
132 { 163 {
133 U8 c = (U8)col [x][y]; 164 U8 c = (U8)data [x][y];
134 165
135 if (!c) 166 if (!c)
136 c = ' '; 167 c = ' ';
137 else if (c < 10) 168 else if (c < 10)
138 c += '0'; 169 c += '0';
… …
151///////////////////////////////////////////////////////////////////////////// 182/////////////////////////////////////////////////////////////////////////////
152// isolation remover - ensures single connected area 183// isolation remover - ensures single connected area
153 184
154typedef fixed_stack<point> pointlist; 185typedef fixed_stack<point> pointlist;
155 186
156static noinline void 187static void noinline
157push_flood_fill (layout &dist, pointlist &seeds, int x, int y) 188push_flood_fill (layout &dist, pointlist &seeds, int x, int y)
158{ 189{
159 if (dist [x][y]) 190 if (dist [x][y])
160 return; 191 return;
161 192
… …
172 ++y; 203 ++y;
173 } 204 }
174 205
175 while (--y >= y0) 206 while (--y >= y0)
176 { 207 {
177 if (x > 0) push_flood_fill (dist, seeds, x - 1, y); 208 if (x > 0 && !dist [x - 1][y]) push_flood_fill (dist, seeds, x - 1, y);
178 if (x < dist.w - 1) push_flood_fill (dist, seeds, x + 1, y); 209 if (x < dist.w - 1 && !dist [x + 1][y]) push_flood_fill (dist, seeds, x + 1, y);
179 } 210 }
180} 211}
181 212
182static inline void 213static inline void
183make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d) 214make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d)
184{ 215{
185 for (;;) 216 for (;;)
186 { 217 {
218 point neigh[4];
219 int ncnt = 0;
220
187 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) 221 if (x > 0 && U8 (dist [x - 1][y]) <= d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
188 --x;
189 else if (x < dist.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) 222 if (x < dist.w - 1 && U8 (dist [x + 1][y]) <= d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y);
190 ++x;
191 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) 223 if (y > 0 && U8 (dist [x][y - 1]) <= d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
192 --y;
193 else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) 224 if (y < dist.h - 1 && U8 (dist [x][y + 1]) <= d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
194 ++y; 225
195 else 226 if (!ncnt)
196 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;
197 235
198 d = dist [x][y]; 236 d = dist [x][y];
199 dist [x][y] = 1; 237 dist [x][y] = 1;
200 seeds.push (point (x, y));
201 } 238 }
202} 239}
203 240
204static void inline 241static void inline
205maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d) 242maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d)
… …
212 return; 249 return;
213 250
214 seeds.push (point (x, y)); 251 seeds.push (point (x, y));
215} 252}
216 253
217void 254// isolation remover, works on a "distance" map
218layout::isolation_remover (bool dirty) 255// the map must be initialised with 0 == rooms, 255 = walls
256static void noinline
257isolation_remover (layout &dist)
219{ 258{
220 layout dist (w, h);
221
222 // dist contains 259 // dist contains
223 // 0 == invisited rooms 260 // 0 == invisited rooms
224 // 1 == visited rooms 261 // 1 == visited rooms
225 // 2+ shortest distance to random near room 262 // 2+ shortest distance to random near room
226 263
227 // phase 1, initialise dist array, find seed 264 // phase 1, find seed
228 int cnt = 0; 265 int cnt = 0;
229 int x, y; 266 int x, y;
230 267
231 for (int i = 0; i < w; ++i) 268 for (int i = 0; i < dist.w; ++i)
232 for (int j = 0; j < h; ++j) 269 for (int j = 0; j < dist.h; ++j)
233 { 270 if (!dist [i][j] && !rmg_rndm (++cnt))
234 if (col [i][j] == '#')
235 dist [i][j] = U8 (255);
236 else
237 {
238 dist [i][j] = 0;
239 if (!rmg_rndm (++cnt))
240 x = i, y = j; 271 x = i, y = j;
241 }
242 }
243 272
244 if (!cnt) 273 if (!cnt)
245 { 274 {
246 // map is completely massive, this is not good, 275 // map is completely massive, this is not good,
247 // so make it empty instead. 276 // so make it empty instead.
248 clear (); 277 dist.fill (1);
249 border ();
250 return; 278 return;
251 } 279 }
252 280
253 fixed_stack<point> seeds (w * h * 5); 281 fixed_stack<point> seeds (dist.w * dist.h * 5);
254 282
255 // found first free space - picking the first one gives 283 // found first free space - picking the first one gives
256 // us a slight bias for tunnels, but usually you won't 284 // us a slight bias for tunnels, but usually you won't
257 // notice that in-game 285 // notice that in-game
258 seeds.push (point (x, y)); 286 seeds.push (point (x, y));
… …
270 y = p.y; 298 y = p.y;
271 299
272 if (!dist [x][y]) 300 if (!dist [x][y])
273 { 301 {
274 // found new isolated area, make tunnel 302 // found new isolated area, make tunnel
275 if (!dirty)
276 push_flood_fill (dist, seeds, x, y); 303 push_flood_fill (dist, seeds, x, y);
277
278 make_tunnel (dist, seeds, x, y, 255); 304 make_tunnel (dist, seeds, x, y, 255);
279
280 if (dirty)
281 push_flood_fill (dist, seeds, x, y);
282 } 305 }
283 else 306 else
284 { 307 {
285 // nothing here, continue to expand 308 // nothing here, continue to expand
286 U8 d = U8 (dist [x][y]) + 1; 309 U8 d = U8 (dist [x][y]) + 1;
… …
289 if (x > 0) maybe_push (dist, seeds, x - 1, y, d); 312 if (x > 0) maybe_push (dist, seeds, x - 1, y, d);
290 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d); 313 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d);
291 if (y > 0) maybe_push (dist, seeds, x, y - 1, d); 314 if (y > 0) maybe_push (dist, seeds, x, y - 1, d);
292 } 315 }
293 } 316 }
317}
318
319void
320layout::isolation_remover ()
321{
322 layout dist (w - 2, h - 2); // map without border
323
324 for (int x = 1; x < w - 1; ++x)
325 for (int y = 1; y < h - 1; ++y)
326 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
327
328 ::isolation_remover (dist);
294 329
295 // now copy the tunnels over 330 // now copy the tunnels over
296 for (int x = 0; x < w; ++x) 331 for (int x = 1; x < w - 1; ++x)
297 for (int y = 0; y < h; ++y) 332 for (int y = 1; y < h - 1; ++y)
298 if (col [x][y] == '#' && dist [x][y] == 1) 333 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
299 col [x][y] = 0; 334 data [x][y] = 0;
300} 335}
301 336
302///////////////////////////////////////////////////////////////////////////// 337/////////////////////////////////////////////////////////////////////////////
303 338
304// inspired mostly by http://www.jimrandomh.org/misc/caves.txt 339// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
… …
307{ 342{
308 switch (subtype) 343 switch (subtype)
309 { 344 {
310 // a rough cave 345 // a rough cave
311 case 0: 346 case 0:
312 fill_rand (rmg_rndm (80, 95)); 347 fill_rand (rmg_rndm (85, 97));
313 break; 348 break;
314 349
315 // corridors 350 // corridors
316 case 1: 351 case 1:
317 fill_rand (rmg_rndm (5, 40)); 352 fill_rand (rmg_rndm (5, 40));
… …
374 int j = doorlist_y [di]; 409 int j = doorlist_y [di];
375 int sindex = surround_flag (*this, i, j); 410 int sindex = surround_flag (*this, i, j);
376 411
377 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 412 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
378 { 413 {
379 col [i][j] = 'D'; 414 data [i][j] = 'D';
380 ndoors--; 415 ndoors--;
381 } 416 }
382 417
383 /* reduce the size of the list */ 418 /* reduce the size of the list */
384 doorlocs--; 419 doorlocs--;
… …
407 if (symmetry == SYMMETRY_X) 442 if (symmetry == SYMMETRY_X)
408 for (int i = 0; i < sym_layout.w / 2 + 1; i++) 443 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
409 for (int j = 0; j < sym_layout.h; j++) 444 for (int j = 0; j < sym_layout.h; j++)
410 { 445 {
411 sym_layout[i ][j] = 446 sym_layout[i ][j] =
412 sym_layout[sym_layout.w - i - 1][j] = col[i][j]; 447 sym_layout[sym_layout.w - i - 1][j] = data [i][j];
413 } 448 }
414 449
415 if (symmetry == SYMMETRY_Y) 450 if (symmetry == SYMMETRY_Y)
416 for (int i = 0; i < sym_layout.w; i++) 451 for (int i = 0; i < sym_layout.w; i++)
417 for (int j = 0; j < sym_layout.h / 2 + 1; j++) 452 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
418 { 453 {
419 sym_layout[i][j ] = 454 sym_layout[i][j ] =
420 sym_layout[i][sym_layout.h - j - 1] = col[i][j]; 455 sym_layout[i][sym_layout.h - j - 1] = data [i][j];
421 } 456 }
422 457
423 if (symmetry == SYMMETRY_XY) 458 if (symmetry == SYMMETRY_XY)
424 for (int i = 0; i < sym_layout.w / 2 + 1; i++) 459 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
425 for (int j = 0; j < sym_layout.h / 2 + 1; j++) 460 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
426 { 461 {
427 sym_layout[i ][j ] = 462 sym_layout[i ][j ] =
428 sym_layout[i ][sym_layout.h - j - 1] = 463 sym_layout[i ][sym_layout.h - j - 1] =
429 sym_layout[sym_layout.w - i - 1][j ] = 464 sym_layout[sym_layout.w - i - 1][j ] =
430 sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = col[i][j]; 465 sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = data [i][j];
431 } 466 }
432 467
433 /* need to run the isolation remover for some layouts */ 468 /* need to run the isolation remover for some layouts */
434#if 0 469#if 0
435 switch (RP->map_layout_style) 470 switch (RP->map_layout_style)
… …
461 { 496 {
462 layout new_layout (w, h); 497 layout new_layout (w, h);
463 498
464 for (int i = 0; i < w; i++) /* copy a reflection back */ 499 for (int i = 0; i < w; i++) /* copy a reflection back */
465 for (int j = 0; j < h; j++) 500 for (int j = 0; j < h; j++)
466 new_layout [i][j] = col [w - i - 1][h - j - 1]; 501 new_layout [i][j] = data [w - i - 1][h - j - 1];
467 502
468 swap (new_layout); 503 swap (new_layout);
469 } 504 }
470 break; 505 break;
471 506
… …
475 layout new_layout (h, w); 510 layout new_layout (h, w);
476 511
477 if (rotation == 1) /* swap x and y */ 512 if (rotation == 1) /* swap x and y */
478 for (int i = 0; i < w; i++) 513 for (int i = 0; i < w; i++)
479 for (int j = 0; j < h; j++) 514 for (int j = 0; j < h; j++)
480 new_layout [j][i] = col [i][j]; 515 new_layout [j][i] = data [i][j];
481 516
482 if (rotation == 3) /* swap x and y */ 517 if (rotation == 3) /* swap x and y */
483 for (int i = 0; i < w; i++) 518 for (int i = 0; i < w; i++)
484 for (int j = 0; j < h; j++) 519 for (int j = 0; j < h; j++)
485 new_layout [j][i] = col [w - i - 1][h - j - 1]; 520 new_layout [j][i] = data [w - i - 1][h - j - 1];
486 521
487 swap (new_layout); 522 swap (new_layout);
488 } 523 }
489 break; 524 break;
490 } 525 }
… …
616 651
617 new_layout.clear (); 652 new_layout.clear ();
618 653
619 for (int i = 0; i < w; i++) 654 for (int i = 0; i < w; i++)
620 for (int j = 0; j < h; j++) 655 for (int j = 0; j < h; j++)
621 switch (col [i][j]) 656 switch (data [i][j])
622 { 657 {
623 case '#': expand_wall (new_layout, i, j, *this); break; 658 case '#': expand_wall (new_layout, i, j, *this); break;
624 case 'D': expand_door (new_layout, i, j, *this); break; 659 case 'D': expand_door (new_layout, i, j, *this); break;
625 default: expand_misc (new_layout, i, j, *this); break; 660 default: expand_misc (new_layout, i, j, *this); break;
626 } 661 }
… …
860{ 895{
861 demo () 896 demo ()
862 { 897 {
863 rmg_rndm.seed (time (0)); 898 rmg_rndm.seed (time (0));
864 899
865 for(int i=1;i<10;i) 900 for(int i=1;i<100;i++)
866 { 901 {
867 layout maze (10, 10); 902 layout maze (40, 25);
868 maze.fill_rand (90); 903 maze.fill_rand (85);
869 maze.border (); 904 maze.border ();
870 maze.isolation_remover (); 905 maze.isolation_remover ();
871 maze.doorify ();
872 maze.symmetrize (rmg_rndm (2, 4));
873 maze.rotate (rmg_rndm (4));
874 maze.expand2x ();
875 maze.print (); 906 maze.print ();
876 } 907 }
877 908
878 exit (1); 909 exit (1);
879 } 910 }

Diff Legend

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