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

Diff Legend

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