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.1 by root, Wed Jun 30 20:51:02 2010 UTC vs.
Revision 1.3 by root, Thu Jul 1 01:22:44 2010 UTC

… …
21 */ 21 */
22 22
23#include <global.h> 23#include <global.h>
24#include <random_map.h> 24#include <random_map.h>
25 25
26LayoutData::LayoutData (int w, int h) 26Layout::Layout (int w, int h)
27: w(w), h(h) 27: w(w), h(h)
28{ 28{
29 int size = (sizeof (char *) + sizeof (char) * h) * w; 29 int size = (sizeof (char *) + sizeof (char) * h) * w;
30 30
31 col = (char **)salloc<char> (size); 31 col = (char **)salloc<char> (size);
… …
34 34
35 for (int x = w; x--; ) 35 for (int x = w; x--; )
36 col [x] = data + x * h; 36 col [x] = data + x * h;
37} 37}
38 38
39LayoutData::~LayoutData () 39Layout::~Layout ()
40{ 40{
41 int size = (sizeof (char *) + sizeof (char) * h) * w; 41 int size = (sizeof (char *) + sizeof (char) * h) * w;
42 42
43 sfree ((char *)col, size); 43 sfree ((char *)col, size);
44} 44}
45 45
46void 46void
47LayoutData::fill (char fill) 47Layout::fill (char fill)
48{ 48{
49 memset (col [0], fill, w * h); 49 memset (col [0], fill, w * h);
50} 50}
51 51
52void 52void
53LayoutData::rect (int x1, int y1, int x2, int y2, char fill) 53Layout::rect (int x1, int y1, int x2, int y2, char fill)
54{ 54{
55 for (; x1 < x2; ++x1) 55 for (; x1 < x2; ++x1)
56 memset (col [x1] + y1, fill, y2 - y1); 56 memset (col [x1] + y1, fill, y2 - y1);
57} 57}
58 58
59void LayoutData::border (char fill) 59void Layout::border (char fill)
60{ 60{
61 for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill; 61 for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill;
62 for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill; 62 for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill;
63} 63}
64 64
65void
66Layout::fill_rand (int percent)
67{
68 percent = lerp (percent, 0, 100, 0, 256);
69
70 for (int x = w - 1; --x > 0; )
71 for (int y = h - 1; --y > 0; )
72 col [x][y] = rmg_rndm (256) > percent ? 0 : '#';
73}
74
65///////////////////////////////////////////////////////////////////////////// 75/////////////////////////////////////////////////////////////////////////////
66 76
77// erode by cellular automata
78void
79Layout::erode_1_2 (int c1, int c2, int repeat)
80{
81 Layout neu (w, h);
82
83 while (repeat--)
84 {
85 for (int x = 0; x < w; ++x)
86 {
87 coroapi::cede_to_tick ();
88
89 for (int y = 0; y < h; ++y)
90 {
91 int n1 = 0, n2 = 0;
92
93 // a 5x5 area, dx, dy, distance (1 == <= 1, 0 <= 2)
94 static I8 dds[][3] = {
95 { -2, -1, 0 },
96 { -2, 0, 0 },
97 { -2, 1, 0 },
98
99 { -1, -2, 0 },
100 { -1, -1, 1 },
101 { -1, 0, 1 },
102 { -1, 1, 1 },
103 { -1, 2, 0 },
104
105 { 0, -2, 0 },
106 { 0, -1, 1 },
107 { 0, 0, 1 },
108 { 0, 1, 1 },
109 { 0, 2, 0 },
110
111 { 1, -2, 0 },
112 { 1, -1, 1 },
113 { 1, 0, 1 },
114 { 1, 1, 1 },
115 { 1, 2, 0 },
116
117 { 2, -1, 0 },
118 { 2, 0, 0 },
119 { 2, 1, 0 },
120 };
121
122 for (int i = array_length (dds); i--; )
123 {
124 int nx = x + dds [i][0];
125 int ny = y + dds [i][1];
126
127 if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !col [nx][ny])
128 {
129 n1 += dds [i][2];
130 n2++;
131 }
132 }
133
134 neu [x][y] = n1 >= c1 || n2 <= c2 ? '#' : 0;
135 }
136 }
137
138 swap (neu);
139 }
140}
141
142/////////////////////////////////////////////////////////////////////////////
143
67void 144void
68Layout::print () 145Layout::print ()
69{ 146{
70 for (int y = 0; y < ptr->h; y++) 147 for (int y = 0; y < h; y++)
71 { 148 {
72 for (int x = 0; x < ptr->w; x++) 149 for (int x = 0; x < w; x++)
73 { 150 {
74 U8 c = (U8)ptr->col[x][y]; 151 U8 c = (U8)col [x][y];
75 152
76 if (!c) 153 if (!c)
77 c = ' '; 154 c = ' ';
78 else if (c < 10) 155 else if (c < 10)
79 c += '0'; 156 c += '0';
… …
92///////////////////////////////////////////////////////////////////////////// 169/////////////////////////////////////////////////////////////////////////////
93// isolation remover - ensures single connected area 170// isolation remover - ensures single connected area
94 171
95typedef fixed_stack<point> pointlist; 172typedef fixed_stack<point> pointlist;
96 173
97static void
98room (Layout &layout, int xc, int yc)
99{
100 layout->rect (xc - 2, yc - 2, xc + 3, yc + 3, 0);
101}
102
103static noinline void 174static noinline void
104push_flood_fill (Layout maze, Layout dist, pointlist &seeds, int x, int y) 175push_flood_fill (Layout &dist, pointlist &seeds, int x, int y)
105{ 176{
106 if (maze [x][y]) 177 if (dist [x][y])
107 return; 178 return;
108 179
109 while (y > 0 && !maze [x][y - 1]) 180 while (y > 0 && !dist [x][y - 1])
110 --y; 181 --y;
111 182
112 int y0 = y; 183 int y0 = y;
113 184
114 while (y < maze->h && !maze [x][y]) 185 while (y < dist.h && !dist [x][y])
115 { 186 {
116 seeds.push (point (x, y)); 187 seeds.push (point (x, y));
117 188
118 maze [x][y] = 1;
119 dist [x][y] = 1; 189 dist [x][y] = 1;
120 ++y; 190 ++y;
121 } 191 }
122 192
123 while (--y >= y0) 193 while (--y >= y0)
124 { 194 {
125 if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y); 195 if (x > 0) push_flood_fill (dist, seeds, x - 1, y);
126 if (x < maze->w - 1) push_flood_fill (maze, dist, seeds, x + 1, y); 196 if (x < dist.w - 1) push_flood_fill (dist, seeds, x + 1, y);
127 } 197 }
128} 198}
129 199
130static inline void 200static inline void
131make_tunnel (Layout maze, Layout dist, pointlist &seeds, int x, int y, U8 d) 201make_tunnel (Layout &dist, pointlist &seeds, int x, int y, U8 d)
132{ 202{
133 for (;;) 203 for (;;)
134 { 204 {
135 seeds.push (point (x, y));
136
137 maze [x][y] = 1;
138 dist [x][y] = 1;
139
140 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) 205 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1)
141 --x; 206 --x;
142 else if (x < maze->w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) 207 else if (x < dist.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1)
143 ++x; 208 ++x;
144 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) 209 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1)
145 --y; 210 --y;
146 else if (y < maze->h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) 211 else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1)
147 ++y; 212 ++y;
148 else 213 else
149 break; 214 break;
150 215
151 d = dist [x][y]; 216 d = dist [x][y];
217 dist [x][y] = 1;
218 seeds.push (point (x, y));
152 } 219 }
220}
221
222static void inline
223maybe_push (Layout &dist, pointlist &seeds, int x, int y, U8 d)
224{
225 char &D = dist [x][y];
226
227 if (U8 (D) > d) // if wall and higher distance, lower distance
228 D = d;
229 else if (D) // otherwise, if it's no room, this space is uninteresting
230 return;
231
232 seeds.push (point (x, y));
153} 233}
154 234
155static void 235static void
156isolation_remover (Layout maze, bool dirty) 236isolation_remover (Layout &maze, bool dirty)
157{ 237{
158 Layout dist (maze->w, maze->h); 238 Layout dist (maze.w, maze.h);
159 239
160 dist->fill (255); 240 // dist contains
241 // 0 == invisited rooms
242 // 1 == visited rooms
243 // 2+ shortest distance to random near room
161 244
245 // phase 1, initialise dist array, find seed
246 int cnt = 0;
247 int x, y;
248
249 for (int i = 0; i < maze.w; ++i)
250 for (int j = 0; j < maze.h; ++j)
251 {
252 if (maze [i][j] == '#')
253 dist [i][j] = U8 (255);
254 else
255 {
256 dist [i][j] = 0;
257 if (!rmg_rndm (++cnt))
258 x = i, y = j;
259 }
260 }
261
262 if (!cnt)
263 return;
264
162 fixed_stack<point> seeds (maze->w * maze->h * 4); 265 fixed_stack<point> seeds (maze.w * maze.h * 5);
163 266
164 // phase 1, find seed 267 // found first free space - picking the first one gives
165 for (int x = 1; x < maze->w; ++x) 268 // us a slight bias for tunnels, but usually you won't
166 for (int y = 1; y < maze->h; ++y) 269 // notice that in-game
270 seeds.push (point (x, y));
271
272 // phase 2, while we have seeds, if
273 // seed is empty, floodfill, else grow
274
275 while (seeds.size)
276 {
277 coroapi::cede_to_tick ();
278
279 point p = seeds.remove (rmg_rndm (seeds.size));
280
281 x = p.x;
282 y = p.y;
283
167 if (!maze [x][y]) 284 if (!dist [x][y])
168 { 285 {
169 seeds.push (point (x, y));
170
171 // phase 2, while we have seeds, if
172 // seed is empty, floodfill, else grow
173
174 while (seeds.size)
175 {
176 point p = seeds.remove (rmg_rndm (seeds.size));
177
178 x = p.x;
179 y = p.y;
180
181 if (!maze [x][y])
182 {
183 // found new isolated area, make tunnel? 286 // found new isolated area, make tunnel
184 if (!dirty) 287 if (!dirty)
185 push_flood_fill (maze, dist, seeds, x, y); 288 push_flood_fill (dist, seeds, x, y);
186 289
187 make_tunnel (maze, dist, seeds, x, y, 255); 290 make_tunnel (dist, seeds, x, y, 255);
188 291
189 if (dirty) 292 if (dirty)
190 push_flood_fill (maze, dist, seeds, x, y); 293 push_flood_fill (dist, seeds, x, y);
191 }
192 else
193 {
194 U8 d = U8 (dist [x][y]) + 1;
195
196 if (x < maze->w - 1 && U8 (dist [x + 1][y]) > d)
197 {
198 dist [x + 1][y] = d;
199 seeds.push (point (x + 1, y));
200 }
201
202 if (x > 0 && U8 (dist [x - 1][y]) > d)
203 {
204 dist [x - 1][y] = d;
205 seeds.push (point (x - 1, y));
206 }
207
208 if (y < maze->h - 1 && U8 (dist [x][y + 1]) > d)
209 {
210 dist [x][y + 1] = d;
211 seeds.push (point (x, y + 1));
212 }
213
214 if (y > 0 && U8 (dist [x][y - 1]) > d)
215 {
216 dist [x][y - 1] = d;
217 seeds.push (point (x, y - 1));
218 }
219 }
220 }
221
222 goto success;
223 } 294 }
295 else
296 {
297 // nothing here, continue to expand
298 U8 d = U8 (dist [x][y]) + 1;
224 299
225success: 300 if (x < dist.w - 1) maybe_push (dist, seeds, x + 1, y, d);
226 dist.free (); 301 if (x > 0) maybe_push (dist, seeds, x - 1, y, d);
302 if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d);
303 if (y > 0) maybe_push (dist, seeds, x, y - 1, d);
304 }
305 }
227 306
228 // we mark free but visited floors as 1, undo this here 307 // now copy the tunnels over
229 for (int x = 0; x < maze->w; ++x) 308 for (int x = 0; x < maze.w; ++x)
230 for (int y = 0; y < maze->h; ++y) 309 for (int y = 0; y < maze.h; ++y)
231 if (maze [x][y] == 1) 310 if (maze [x][y] == '#' && dist [x][y] == 1)
232 maze [x][y] = 0; 311 maze [x][y] = 0;
233} 312}
234 313
235void 314void
236LayoutData::isolation_remover (bool dirty) 315Layout::isolation_remover (bool dirty)
237{ 316{
238 Layout maze;
239 maze.ptr = this;
240 ::isolation_remover (maze, dirty); 317 ::isolation_remover (*this, dirty);
318}
319
320/////////////////////////////////////////////////////////////////////////////
321
322// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
323void
324Layout::gen_cave (int subtype)
325{
326 switch (subtype)
327 {
328 // a rough cave
329 case 0:
330 fill_rand (rmg_rndm (80, 95));
331 break;
332
333 // corridors
334 case 1:
335 fill_rand (rmg_rndm (5, 40));
336 erode_1_2 (5, 2, 10);
337 erode_1_2 (5, -1, 10);
338 erode_1_2 (5, 2, 1);
339 break;
340
341 // somewhat open, roundish
342 case 2:
343 fill_rand (45);
344 erode_1_2 (5, 0, 5);
345 erode_1_2 (5, 1, 1);
346 break;
347
348 // wide open, some room-like structures
349 case 3:
350 fill_rand (45);
351 erode_1_2 (5, 2, 4);
352 erode_1_2 (5, -1, 3);
353 break;
354 }
355
356 border ();
357 isolation_remover ();
241} 358}
242 359
243#if 0 360#if 0
244static struct demo 361static struct demo
245{ 362{
246 demo () 363 demo ()
247 { 364 {
248 Layout maze (40, 25); 365 Layout maze (40, 25);
249 rmg_rndm.seed (time (0)); 366 rmg_rndm.seed (time (0));
250 367
251 for (int p = 80; p < 100; p += 1) {
252 maze->fill ('#');
253
254#if 1
255 for (int x = 1; x < maze->w - 1; ++x)
256 for (int y = 1; y < maze->h - 1; ++y)
257 maze [x][y] = rmg_rndm(100) < p ? '#' : 0;
258#else
259 room (maze, 5, 5);
260 room (maze, 30,20);
261 room (maze, 10,20);
262 room (maze, 20,10);
263#endif
264
265 isolation_remover (maze, 1);
266 maze.print ();
267 }
268
269#if 0
270 for(int i=1;i<10;i) 368 for(int i=1;i<10;i)
271 { 369 {
272 maze_gen (maze, 1); 370 maze.fill_rand (97);
371 maze.border ();
372 maze.isolation_remover ();
273 maze.print (); 373 maze.print ();
274 } 374 }
275#endif 375
276 exit (1); 376 exit (1);
277 } 377 }
278} demo; 378} demo;
279#endif 379#endif

Diff Legend

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