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.2 by root, Wed Jun 30 23:03:40 2010 UTC

… …
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
66LayoutData::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
67void 78void
68Layout::print () 79LayoutData::erode_1_2 (int c1, int c2, int repeat)
69{ 80{
70 for (int y = 0; y < ptr->h; y++) 81 LayoutData neu (w, h);
82
83 while (repeat--)
71 { 84 {
72 for (int x = 0; x < ptr->w; x++) 85 for (int x = 0; x < w; ++x)
73 { 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
144void
145LayoutData::print ()
146{
147 for (int y = 0; y < h; y++)
148 {
149 for (int x = 0; x < w; x++)
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 (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y)
105{ 176{
106 if (maze [x][y]) 177 if (maze [x][y])
107 return; 178 return;
108 179
109 while (y > 0 && !maze [x][y - 1]) 180 while (y > 0 && !maze [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 < maze.h && !maze [x][y])
115 { 186 {
116 seeds.push (point (x, y)); 187 seeds.push (point (x, y));
117 188
118 maze [x][y] = 1; 189 maze [x][y] = 1;
119 dist [x][y] = 1; 190 dist [x][y] = 1;
120 ++y; 191 ++y;
121 } 192 }
122 193
123 while (--y >= y0) 194 while (--y >= y0)
124 { 195 {
125 if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y); 196 if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y);
126 if (x < maze->w - 1) push_flood_fill (maze, dist, seeds, x + 1, y); 197 if (x < maze.w - 1) push_flood_fill (maze, dist, seeds, x + 1, y);
127 } 198 }
128} 199}
129 200
130static inline void 201static inline void
131make_tunnel (Layout maze, Layout dist, pointlist &seeds, int x, int y, U8 d) 202make_tunnel (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y, U8 d)
132{ 203{
133 for (;;) 204 for (;;)
134 { 205 {
135 seeds.push (point (x, y)); 206 seeds.push (point (x, y));
136 207
137 maze [x][y] = 1; 208 maze [x][y] = 1;
138 dist [x][y] = 1; 209 dist [x][y] = 1;
139 210
140 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) 211 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1)
141 --x; 212 --x;
142 else if (x < maze->w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) 213 else if (x < maze.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1)
143 ++x; 214 ++x;
144 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) 215 else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1)
145 --y; 216 --y;
146 else if (y < maze->h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) 217 else if (y < maze.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1)
147 ++y; 218 ++y;
148 else 219 else
149 break; 220 break;
150 221
151 d = dist [x][y]; 222 d = dist [x][y];
152 } 223 }
153} 224}
154 225
155static void 226static void
156isolation_remover (Layout maze, bool dirty) 227isolation_remover (LayoutData &maze, bool dirty)
157{ 228{
158 Layout dist (maze->w, maze->h); 229 LayoutData dist (maze.w, maze.h);
159 230
160 dist->fill (255); 231 dist.fill (255);
161 232
162 fixed_stack<point> seeds (maze->w * maze->h * 4); 233 fixed_stack<point> seeds (maze.w * maze.h * 4);
163 234
164 // phase 1, find seed 235 // phase 1, find seed
165 for (int x = 1; x < maze->w; ++x) 236 for (int x = 1; x < maze.w; ++x)
166 for (int y = 1; y < maze->h; ++y) 237 for (int y = 1; y < maze.h; ++y)
167 if (!maze [x][y]) 238 if (!maze [x][y])
168 { 239 {
240 // found first free space - picking the first one gives
241 // us a slight bias for tunnels, but usually you won't
242 // notice that in-game
169 seeds.push (point (x, y)); 243 seeds.push (point (x, y));
170 244
171 // phase 2, while we have seeds, if 245 // phase 2, while we have seeds, if
172 // seed is empty, floodfill, else grow 246 // seed is empty, floodfill, else grow
173 247
174 while (seeds.size) 248 while (seeds.size)
175 { 249 {
250 coroapi::cede_to_tick ();
251
176 point p = seeds.remove (rmg_rndm (seeds.size)); 252 point p = seeds.remove (rmg_rndm (seeds.size));
177 253
178 x = p.x; 254 x = p.x;
179 y = p.y; 255 y = p.y;
180 256
… …
191 } 267 }
192 else 268 else
193 { 269 {
194 U8 d = U8 (dist [x][y]) + 1; 270 U8 d = U8 (dist [x][y]) + 1;
195 271
196 if (x < maze->w - 1 && U8 (dist [x + 1][y]) > d) 272 if (x < maze.w - 1 && U8 (dist [x + 1][y]) > d)
197 { 273 {
198 dist [x + 1][y] = d; 274 dist [x + 1][y] = d;
199 seeds.push (point (x + 1, y)); 275 seeds.push (point (x + 1, y));
200 } 276 }
201 277
202 if (x > 0 && U8 (dist [x - 1][y]) > d) 278 if (x > 0 && U8 (dist [x - 1][y]) > d)
203 { 279 {
204 dist [x - 1][y] = d; 280 dist [x - 1][y] = d;
205 seeds.push (point (x - 1, y)); 281 seeds.push (point (x - 1, y));
206 } 282 }
207 283
208 if (y < maze->h - 1 && U8 (dist [x][y + 1]) > d) 284 if (y < maze.h - 1 && U8 (dist [x][y + 1]) > d)
209 { 285 {
210 dist [x][y + 1] = d; 286 dist [x][y + 1] = d;
211 seeds.push (point (x, y + 1)); 287 seeds.push (point (x, y + 1));
212 } 288 }
213 289
214 if (y > 0 && U8 (dist [x][y - 1]) > d) 290 if (y > 0 && U8 (dist [x][y - 1]) > d)
215 { 291 {
216 dist [x][y - 1] = d; 292 dist [x][y - 1] = d;
217 seeds.push (point (x, y - 1)); 293 seeds.push (point (x, y - 1));
218 } 294 }
219 } 295 }
… …
221 297
222 goto success; 298 goto success;
223 } 299 }
224 300
225success: 301success:
226 dist.free ();
227 302
228 // we mark free but visited floors as 1, undo this here 303 // we mark free but visited floors as 1, undo this here
229 for (int x = 0; x < maze->w; ++x) 304 for (int x = 0; x < maze.w; ++x)
230 for (int y = 0; y < maze->h; ++y) 305 for (int y = 0; y < maze.h; ++y)
231 if (maze [x][y] == 1) 306 if (maze [x][y] == 1)
232 maze [x][y] = 0; 307 maze [x][y] = 0;
233} 308}
234 309
235void 310void
236LayoutData::isolation_remover (bool dirty) 311LayoutData::isolation_remover (bool dirty)
237{ 312{
238 Layout maze;
239 maze.ptr = this;
240 ::isolation_remover (maze, dirty); 313 ::isolation_remover (*this, dirty);
314}
315
316/////////////////////////////////////////////////////////////////////////////
317
318// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
319void
320LayoutData::gen_cave (int subtype)
321{
322 switch (subtype)
323 {
324 // a rough cave
325 case 0:
326 fill_rand (rmg_rndm (80, 95));
327 break;
328
329 // corridors
330 case 1:
331 fill_rand (rmg_rndm (5, 40));
332 erode_1_2 (5, 2, 10);
333 erode_1_2 (5, -1, 10);
334 erode_1_2 (5, 2, 1);
335 break;
336
337 // somewhat open, roundish
338 case 2:
339 fill_rand (45);
340 erode_1_2 (5, 0, 5);
341 erode_1_2 (5, 1, 1);
342 break;
343
344 // wide open, some room-like structures
345 case 3:
346 fill_rand (45);
347 erode_1_2 (5, 2, 4);
348 erode_1_2 (5, -1, 3);
349 break;
350 }
351
352 border ();
353 isolation_remover ();
241} 354}
242 355
243#if 0 356#if 0
244static struct demo 357static struct demo
245{ 358{
246 demo () 359 demo ()
247 { 360 {
248 Layout maze (40, 25); 361 Layout maze (40, 25);
249 rmg_rndm.seed (time (0)); 362 rmg_rndm.seed (time (0));
250 363
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) 364 for(int i=1;i<10;i)
271 { 365 {
272 maze_gen (maze, 1); 366 maze->gen_cave (3);
273 maze.print (); 367 maze->print ();
274 } 368 }
275#endif 369
276 exit (1); 370 exit (1);
277 } 371 }
278} demo; 372} demo;
279#endif 373#endif

Diff Legend

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