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.6 by root, Fri Jul 2 04:05:15 2010 UTC vs.
Revision 1.34 by root, Sat Nov 17 23:40:02 2018 UTC

1/* 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG. 2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 * 3 *
4 * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team 4 * Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
5 * Copyright (©) 2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice) 6 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
6 * 7 *
7 * Deliantra is free software: you can redistribute it and/or modify it under 8 * Deliantra is free software: you can redistribute it and/or modify it under
8 * the terms of the Affero GNU General Public License as published by the 9 * the terms of the Affero GNU General Public License as published by the
9 * Free Software Foundation, either version 3 of the License, or (at your 10 * Free Software Foundation, either version 3 of the License, or (at your
10 * option) any later version. 11 * option) any later version.
11 * 12 *
12 * This program is distributed in the hope that it will be useful, 13 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details. 16 * GNU General Public License for more details.
16 * 17 *
17 * You should have received a copy of the Affero GNU General Public License 18 * You should have received a copy of the Affero GNU General Public License
18 * and the GNU General Public License along with this program. If not, see 19 * and the GNU General Public License along with this program. If not, see
19 * <http://www.gnu.org/licenses/>. 20 * <http://www.gnu.org/licenses/>.
20 * 21 *
21 * The authors can be reached via e-mail to <support@deliantra.net> 22 * The authors can be reached via e-mail to <support@deliantra.net>
22 */ 23 */
23 24
24#include <global.h> 25#include <global.h>
25#include <random_map.h> 26#include <rmg.h>
26#include <rproto.h> 27#include <rproto.h>
27 28
29ecb_noinline void
30layout::alloc (int w, int h)
31{
32 assert (sizeof (cell) == 1);
33
34 this->w = w;
35 this->h = h;
36
37 // we store the layout in a single contiguous memory layout
38 // first part consists of pointers to each column, followed
39 // by the actual columns (not rows!)
40 size = (sizeof (cell *) + sizeof (cell) * h) * w;
41 data = (cell **)salloc<char> (size);
42
43 cell *p = (cell *)(data + w);
44
45 for (int x = 0; 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
54layout::layout (layout &copy)
55{
56 alloc (copy.w, copy.h);
57
58 memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
59}
60
61layout::layout (layout &orig, int x1, int y1, int x2, int y2)
62{
63 w = x2 - x1;
64 h = y2 - y1;
65
66 // we only allocate space for the pointers
67 size = sizeof (cell *) * w;
33 col = (char **)salloc<char> (size); 68 data = (cell **)salloc<char> (size);
34 69
35 char *data = (char *)(col + w); 70 // and now we point back into the original layout
36
37 for (int x = w; x--; ) 71 for (int x = 0; x < w; ++x)
38 col [x] = data + x * h; 72 data [x] = orig.data [x + x1] + y1;
39} 73}
40 74
41Layout::~Layout () 75layout::~layout ()
42{ 76{
43 int size = (sizeof (char *) + sizeof (char) * h) * w;
44
45 sfree ((char *)col, size); 77 sfree ((char *)data, size);
78}
79
80ecb_noinline void
81layout::fill (char fill)
82{
83 //memset (data [0], fill, w * h); // only when contiguous :/
84 fill_rect (0, 0, w, h, fill);
85}
86
87ecb_noinline void
88layout::replace (char from, char to)
89{
90 for (int x = 0; x < w; ++x)
91 for (int y = 0; y < h; ++y)
92 if (data [x][y] == from)
93 data [x][y] = to;
94}
95
96ecb_noinline void
97layout::rect (int x1, int y1, int x2, int y2, char fill)
98{
99 --x2;
100
101 memset (data [x1] + y1, fill, y2 - y1);
102 memset (data [x2] + y1, fill, y2 - y1);
103
104 while (++x1 < x2)
105 data [x1][y1] = data [x1][y2 - 1] = fill;
106}
107
108ecb_noinline void
109layout::fill_rect (int x1, int y1, int x2, int y2, char fill)
110{
111 for (; x1 < x2; ++x1)
112 memset (data [x1] + y1, fill, y2 - y1);
46} 113}
47 114
48void 115void
49Layout::fill (char fill)
50{
51 memset (col [0], fill, w * h);
52}
53
54void
55Layout::rect (int x1, int y1, int x2, int y2, char fill)
56{
57 for (; x1 < x2; ++x1)
58 memset (col [x1] + y1, fill, y2 - y1);
59}
60
61void Layout::border (char fill) 116layout::border (char fill)
62{ 117{
63 for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill; 118 rect (0, 0, w, h, fill);
64 for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill;
65} 119}
66 120
67void 121ecb_noinline void
68Layout::fill_rand (int percent) 122layout::fill_rand (int percent)
69{ 123{
70 percent = lerp (percent, 0, 100, 0, 256); 124 percent = lerp (percent, 0, 100, 0, 256);
71 125
72 for (int x = w - 1; --x > 0; ) 126 for (int x = 0; x < w; ++x)
73 for (int y = h - 1; --y > 0; ) 127 for (int y = 0; y < h; ++y)
74 col [x][y] = rmg_rndm (256) > percent ? 0 : '#'; 128 data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
75} 129}
76 130
77///////////////////////////////////////////////////////////////////////////// 131/////////////////////////////////////////////////////////////////////////////
78 132
79// erode by cellular automata 133// erode by cellular automata
80void 134ecb_noinline void
81Layout::erode_1_2 (int c1, int c2, int repeat) 135layout::erode_1_2 (int c1, int c2, int repeat)
82{ 136{
83 Layout neu (w, h); 137 layout neu (w, h);
84 138
85 while (repeat--) 139 while (repeat--)
86 { 140 {
87 for (int x = 0; x < w; ++x) 141 for (int x = 0; x < w; ++x)
88 { 142 {
… …
104 for (int i = array_length (dds); i--; ) 158 for (int i = array_length (dds); i--; )
105 { 159 {
106 int nx = x + dds [i][0]; 160 int nx = x + dds [i][0];
107 int ny = y + dds [i][1]; 161 int ny = y + dds [i][1];
108 162
109 if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !col [nx][ny]) 163 if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !data [nx][ny])
110 { 164 {
111 n1 += dds [i][2]; 165 n1 += dds [i][2];
112 n2++; 166 n2++;
113 } 167 }
114 } 168 }
… …
122} 176}
123 177
124///////////////////////////////////////////////////////////////////////////// 178/////////////////////////////////////////////////////////////////////////////
125 179
126void 180void
127Layout::print () const 181layout::print () const
128{ 182{
129 for (int y = 0; y < h; y++) 183 for (int y = 0; y < h; y++)
130 { 184 {
131 for (int x = 0; x < w; x++) 185 for (int x = 0; x < w; x++)
132 { 186 {
133 U8 c = (U8)col [x][y]; 187 U8 c = (U8)data [x][y];
134 188
135 if (!c) 189 if (!c)
136 c = ' '; 190 c = ' ';
137 else if (c < 10) 191 else if (c < 10)
138 c += '0'; 192 c += '0';
… …
151///////////////////////////////////////////////////////////////////////////// 205/////////////////////////////////////////////////////////////////////////////
152// isolation remover - ensures single connected area 206// isolation remover - ensures single connected area
153 207
154typedef fixed_stack<point> pointlist; 208typedef fixed_stack<point> pointlist;
155 209
156static noinline void 210ecb_noinline static void
157push_flood_fill (Layout &dist, pointlist &seeds, int x, int y) 211push_flood_fill (layout &dist, pointlist &seeds, int x, int y)
158{ 212{
159 if (dist [x][y]) 213 if (dist [x][y])
160 return; 214 return;
161 215
162 while (y > 0 && !dist [x][y - 1]) 216 while (y > 0 && !dist [x][y - 1])
… …
172 ++y; 226 ++y;
173 } 227 }
174 228
175 while (--y >= y0) 229 while (--y >= y0)
176 { 230 {
177 if (x > 0) push_flood_fill (dist, seeds, x - 1, y); 231 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); 232 if (x < dist.w - 1 && !dist [x + 1][y]) push_flood_fill (dist, seeds, x + 1, y);
179 } 233 }
180} 234}
181 235
182static inline void 236static void inline
183make_tunnel (Layout &dist, pointlist &seeds, int x, int y, U8 d) 237make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb)
184{ 238{
185 for (;;) 239 for (;;)
186 { 240 {
241 point neigh[4];
242 int ncnt = 0;
243
244 d += perturb > 1;
245
187 if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) 246 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) 247 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) 248 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) 249 if (y < dist.h - 1 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
194 ++y; 250
195 else 251 if (!ncnt)
196 break; 252 return;
253
254 point p = neigh [perturb ? rmg_rndm (ncnt) : 0];
255
256 seeds.push (p);
257
258 x = p.x;
259 y = p.y;
197 260
198 d = dist [x][y]; 261 d = dist [x][y];
199 dist [x][y] = 1; 262 dist [x][y] = 1;
200 seeds.push (point (x, y));
201 } 263 }
202} 264}
203 265
204static void inline 266static void inline
205maybe_push (Layout &dist, pointlist &seeds, int x, int y, U8 d) 267maybe_push (layout &dist, pointlist &seeds, int x, int y, U8 d)
206{ 268{
207 char &D = dist [x][y]; 269 char &D = dist [x][y];
208 270
209 if (U8 (D) > d) // if wall and higher distance, lower distance 271 if (U8 (D) > d) // if wall and higher distance, lower distance
210 D = d; 272 D = d;
… …
212 return; 274 return;
213 275
214 seeds.push (point (x, y)); 276 seeds.push (point (x, y));
215} 277}
216 278
217void 279// isolation remover, works on a "distance" map
218Layout::isolation_remover (bool dirty) 280// the map must be initialised with 0 == rooms, 255 = walls
281ecb_noinline static void
282isolation_remover (layout &dist, unsigned int perturb = 2)
219{ 283{
220 Layout dist (w, h);
221
222 // dist contains 284 // dist contains
223 // 0 == invisited rooms 285 // 0 == invisited rooms
224 // 1 == visited rooms 286 // 1 == visited rooms
225 // 2+ shortest distance to random near room 287 // 2+ shortest distance to random near room
226 288
227 // phase 1, initialise dist array, find seed 289 clamp_it (perturb, 0, 2);
290
291 // phase 1, find seed
228 int cnt = 0; 292 int cnt = 0;
229 int x, y; 293 int x, y;
230 294
231 for (int i = 0; i < w; ++i) 295 for (int i = 0; i < dist.w; ++i)
232 for (int j = 0; j < h; ++j) 296 for (int j = 0; j < dist.h; ++j)
233 { 297 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; 298 x = i, y = j;
241 }
242 }
243 299
244 if (!cnt) 300 if (!cnt)
245 { 301 {
246 // map is completely massive, this is not good, 302 // map is completely massive, this is not good,
247 // so make it empty instead. 303 // so make it empty instead.
248 clear (); 304 dist.fill (1);
249 border ();
250 return; 305 return;
251 } 306 }
252 307
253 fixed_stack<point> seeds (w * h * 5); 308 fixed_stack<point> seeds (dist.w * dist.h * 5);
254 309
255 // found first free space - picking the first one gives 310 // found first free space - picking the first one gives
256 // us a slight bias for tunnels, but usually you won't 311 // us a slight bias for tunnels, but usually you won't
257 // notice that in-game 312 // notice that in-game
258 seeds.push (point (x, y)); 313 seeds.push (point (x, y));
259 314
260 // phase 2, while we have seeds, if 315 // phase 2, while we have seeds, if
261 // seed is empty, floodfill, else grow 316 // seed is empty, floodfill, else grow
262 317
318 int rem_index = 0; // used to remove "somewhat ordered"
319
263 while (seeds.size) 320 while (seeds.size)
264 { 321 {
265 coroapi::cede_to_tick (); 322 coroapi::cede_to_tick ();
266 323
324 int i = perturb
325 ? rmg_rndm (max (0, seeds.size - 8), seeds.size - 1)
326 : rem_index ++ % seeds.size;
327
267 point p = seeds.remove (rmg_rndm (seeds.size)); 328 point p = seeds.remove (i);
268 329
269 x = p.x; 330 x = p.x;
270 y = p.y; 331 y = p.y;
271 332
272 if (!dist [x][y]) 333 if (!dist [x][y])
273 { 334 {
274 // found new isolated area, make tunnel 335 // found new isolated area, make tunnel
275 if (!dirty)
276 push_flood_fill (dist, seeds, x, y); 336 push_flood_fill (dist, seeds, x, y);
277
278 make_tunnel (dist, seeds, x, y, 255); 337 make_tunnel (dist, seeds, x, y, 254, perturb);
279
280 if (dirty)
281 push_flood_fill (dist, seeds, x, y);
282 } 338 }
283 else 339 else
284 { 340 {
285 // nothing here, continue to expand 341 // nothing here, continue to expand
286 U8 d = U8 (dist [x][y]) + 1; 342 U8 d = U8 (dist [x][y]) + 1;
… …
289 if (x > 0) maybe_push (dist, seeds, x - 1, y, d); 345 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); 346 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); 347 if (y > 0) maybe_push (dist, seeds, x, y - 1, d);
292 } 348 }
293 } 349 }
350}
351
352void
353layout::isolation_remover (int perturb)
354{
355 layout dist (w - 2, h - 2); // map without border
356
357 for (int x = 1; x < w - 1; ++x)
358 for (int y = 1; y < h - 1; ++y)
359 dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
360
361 ::isolation_remover (dist, perturb);
294 362
295 // now copy the tunnels over 363 // now copy the tunnels over
296 for (int x = 0; x < w; ++x) 364 for (int x = 1; x < w - 1; ++x)
297 for (int y = 0; y < h; ++y) 365 for (int y = 1; y < h - 1; ++y)
298 if (col [x][y] == '#' && dist [x][y] == 1) 366 if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
299 col [x][y] = 0; 367 data [x][y] = 0;
300} 368}
301 369
302///////////////////////////////////////////////////////////////////////////// 370/////////////////////////////////////////////////////////////////////////////
303 371
304// inspired mostly by http://www.jimrandomh.org/misc/caves.txt 372//+GPL
373
374/* puts doors at appropriate locations in a maze. */
305void 375void
306Layout::gen_cave (int subtype)
307{
308 switch (subtype)
309 {
310 // a rough cave
311 case 0:
312 fill_rand (rmg_rndm (80, 95));
313 break;
314
315 // corridors
316 case 1:
317 fill_rand (rmg_rndm (5, 40));
318 erode_1_2 (5, 2, 10);
319 erode_1_2 (5, -1, 10);
320 erode_1_2 (5, 2, 1);
321 break;
322
323 // somewhat open, roundish
324 case 2:
325 fill_rand (45);
326 erode_1_2 (5, 0, 5);
327 erode_1_2 (5, 1, 1);
328 break;
329
330 // wide open, some room-like structures
331 case 3:
332 fill_rand (45);
333 erode_1_2 (5, 2, 4);
334 erode_1_2 (5, -1, 3);
335 break;
336 }
337
338 border ();
339 isolation_remover ();
340}
341
342/////////////////////////////////////////////////////////////////////////////
343
344//+GPL
345
346/* puts doors at appropriate locations in a layout. */
347void
348Layout::doorify () 376layout::doorify ()
349{ 377{
350 int ndoors = w * h / 60; /* reasonable number of doors. */ 378 int ndoors = w * h / 60; /* reasonable number of doors. */
351 int doorlocs = 0; /* # of available doorlocations */
352 379
353 uint16 *doorlist_x = salloc<uint16> (w * h); 380 coroapi::cede_to_tick ();
354 uint16 *doorlist_y = salloc<uint16> (w * h); 381
382 fixed_stack<point> doorloc (w * h);
355 383
356 /* make a list of possible door locations */ 384 /* make a list of possible door locations */
357 for (int i = 1; i < w - 1; i++) 385 for (int i = 1; i < w - 1; i++)
358 for (int j = 1; j < h - 1; j++) 386 for (int j = 1; j < h - 1; j++)
359 { 387 {
360 int sindex = surround_flag (*this, i, j); 388 int sindex = surround_flag (*this, i, j);
361 389
362 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 390 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
363 { 391 doorloc.push (point (i, j));
364 doorlist_x [doorlocs] = i;
365 doorlist_y [doorlocs] = j;
366 doorlocs++;
367 }
368 } 392 }
369 393
370 while (ndoors > 0 && doorlocs > 0) 394 while (ndoors && doorloc.size)
371 { 395 {
372 int di = rmg_rndm (doorlocs); 396 point p = doorloc.remove (rmg_rndm (doorloc.size));
373 int i = doorlist_x [di]; 397
374 int j = doorlist_y [di];
375 int sindex = surround_flag (*this, i, j); 398 int sindex = surround_flag (*this, p.x, p.y);
376 399
377 if (sindex == 3 || sindex == 12) /* these are possible door sindex */ 400 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
378 { 401 {
379 col [i][j] = 'D'; 402 data [p.x][p.y] = 'D';
380 ndoors--; 403 --ndoors;
381 } 404 }
382
383 /* reduce the size of the list */
384 doorlocs--;
385 doorlist_x[di] = doorlist_x [doorlocs];
386 doorlist_y[di] = doorlist_y [doorlocs];
387 } 405 }
388
389 sfree (doorlist_x, w * h);
390 sfree (doorlist_y, w * h);
391} 406}
392 407
393/* takes a map and makes it symmetric: adjusts Xsize and 408/* takes a map and makes it symmetric: adjusts Xsize and
394 * Ysize to produce a symmetric map. 409 * Ysize to produce a symmetric map.
395 */ 410 */
396void 411void
397Layout::symmetrize (int symmetry) 412layout::symmetrize (int symmetry)
398{ 413{
399 if (symmetry == SYMMETRY_NONE) 414 if (symmetry == SYMMETRY_NONE)
400 return; 415 return;
401 416
402 Layout sym_layout ( 417 layout sym_layout (
403 symmetry == SYMMETRY_X || symmetry == SYMMETRY_XY ? w * 2 - 3 : w, 418 symmetry == SYMMETRY_X || symmetry == SYMMETRY_XY ? w * 2 - 3 : w,
404 symmetry == SYMMETRY_Y || symmetry == SYMMETRY_XY ? h * 2 - 3 : h 419 symmetry == SYMMETRY_Y || symmetry == SYMMETRY_XY ? h * 2 - 3 : h
405 ); 420 );
406 421
407 if (symmetry == SYMMETRY_X) 422 if (symmetry == SYMMETRY_X)
408 for (int i = 0; i < sym_layout.w / 2 + 1; i++) 423 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
409 for (int j = 0; j < sym_layout.h; j++) 424 for (int j = 0; j < sym_layout.h; j++)
410 { 425 {
411 sym_layout[i ][j] = 426 sym_layout[i ][j] =
412 sym_layout[sym_layout.w - i - 1][j] = col[i][j]; 427 sym_layout[sym_layout.w - i - 1][j] = data [i][j];
413 } 428 }
414 429
415 if (symmetry == SYMMETRY_Y) 430 if (symmetry == SYMMETRY_Y)
416 for (int i = 0; i < sym_layout.w; i++) 431 for (int i = 0; i < sym_layout.w; i++)
417 for (int j = 0; j < sym_layout.h / 2 + 1; j++) 432 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
418 { 433 {
419 sym_layout[i][j ] = 434 sym_layout[i][j ] =
420 sym_layout[i][sym_layout.h - j - 1] = col[i][j]; 435 sym_layout[i][sym_layout.h - j - 1] = data [i][j];
421 } 436 }
422 437
423 if (symmetry == SYMMETRY_XY) 438 if (symmetry == SYMMETRY_XY)
424 for (int i = 0; i < sym_layout.w / 2 + 1; i++) 439 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
425 for (int j = 0; j < sym_layout.h / 2 + 1; j++) 440 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
426 { 441 {
427 sym_layout[i ][j ] = 442 sym_layout[i ][j ] =
428 sym_layout[i ][sym_layout.h - j - 1] = 443 sym_layout[i ][sym_layout.h - j - 1] =
429 sym_layout[sym_layout.w - i - 1][j ] = 444 sym_layout[sym_layout.w - i - 1][j ] =
430 sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = col[i][j]; 445 sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = data [i][j];
431 } 446 }
432 447
433 /* need to run the isolation remover for some layouts */ 448 /* need to run the isolation remover for some layouts */
434#if 0 449#if 0
435 switch (RP->map_layout_style) 450 switch (RP->map_layout_style)
… …
451} 466}
452 467
453//-GPL 468//-GPL
454 469
455void 470void
456Layout::rotate (int rotation) 471layout::rotate (int rotation)
457{ 472{
473 coroapi::cede_to_tick ();
474
458 switch (rotation & 3) 475 switch (rotation & 3)
459 { 476 {
460 case 2: /* a reflection */ 477 case 2: /* a reflection */
461 { 478 {
462 Layout new_layout (w, h); 479 layout new_layout (w, h);
463 480
464 for (int i = 0; i < w; i++) /* copy a reflection back */ 481 for (int i = 0; i < w; i++) /* copy a reflection back */
465 for (int j = 0; j < h; j++) 482 for (int j = 0; j < h; j++)
466 new_layout [i][j] = col [w - i - 1][h - j - 1]; 483 new_layout [i][j] = data [w - i - 1][h - j - 1];
467 484
468 swap (new_layout); 485 swap (new_layout);
469 } 486 }
470 break; 487 break;
471 488
472 case 1: 489 case 1:
473 case 3: 490 case 3:
474 { 491 {
475 Layout new_layout (h, w); 492 layout new_layout (h, w);
476 493
477 if (rotation == 1) /* swap x and y */ 494 if (rotation == 1) /* swap x and y */
478 for (int i = 0; i < w; i++) 495 for (int i = 0; i < w; i++)
479 for (int j = 0; j < h; j++) 496 for (int j = 0; j < h; j++)
480 new_layout [j][i] = col [i][j]; 497 new_layout [j][i] = data [i][j];
481 498
482 if (rotation == 3) /* swap x and y */ 499 if (rotation == 3) /* swap x and y */
483 for (int i = 0; i < w; i++) 500 for (int i = 0; i < w; i++)
484 for (int j = 0; j < h; j++) 501 for (int j = 0; j < h; j++)
485 new_layout [j][i] = col [w - i - 1][h - j - 1]; 502 new_layout [j][i] = data [w - i - 1][h - j - 1];
486 503
487 swap (new_layout); 504 swap (new_layout);
488 } 505 }
489 break; 506 break;
490 } 507 }
… …
493///////////////////////////////////////////////////////////////////////////// 510/////////////////////////////////////////////////////////////////////////////
494 511
495//+GPL 512//+GPL
496 513
497/* 514/*
498 * Expands a layout by 2x in each dimension. 515 * Expands a maze by 2x in each dimension.
499 * H. S. Teoh 516 * H. S. Teoh
500 */ 517 */
501 518
502/* Copy the old tile X into the new one at location (i*2, j*2) and 519/* Copy the old tile X into the new one at location (i*2, j*2) and
503 * fill up the rest of the 2x2 result with \0: 520 * fill up the rest of the 2x2 result with \0:
504 * X ---> X \0 521 * X ---> X \0
505 * \0 \0 522 * \0 \0
506 */ 523 */
507static void inline 524static void inline
508expand_misc (Layout &newlayout, int i, int j, Layout &layout) 525expand_misc (layout &newlayout, int i, int j, layout &maze)
509{ 526{
510 newlayout[i * 2 + rmg_rndm (1)][j * 2 + rmg_rndm (1)] = layout[i][j]; 527 newlayout[i * 2 + rmg_rndm (1)][j * 2 + rmg_rndm (1)] = maze[i][j];
511 /* (Note: no need to reset rest of 2x2 area to \0 because calloc does that 528 /* (Note: no need to reset rest of 2x2 area to \0 because calloc does that
512 * for us.) */ 529 * for us.) */
513} 530}
514 531
515/* Returns a bitmap that represents which squares on the right and bottom 532/* Returns a bitmap that represents which squares on the right and bottom
… …
517 * 1 match on (i+1, j) 534 * 1 match on (i+1, j)
518 * 2 match on (i, j+1) 535 * 2 match on (i, j+1)
519 * 4 match on (i+1, j+1) 536 * 4 match on (i+1, j+1)
520 * and the possible combinations thereof. 537 * and the possible combinations thereof.
521 */ 538 */
522static int noinline 539ecb_noinline static int
523calc_pattern (char ch, Layout &layout, int i, int j) 540calc_pattern (char ch, layout &maze, int i, int j)
524{ 541{
525 int pattern = 0; 542 int pattern = 0;
526 543
527 if (i + 1 < layout.w && layout[i + 1][j] == ch) 544 if (i + 1 < maze.w && maze[i + 1][j] == ch)
528 pattern |= 1; 545 pattern |= 1;
529 546
530 if (j + 1 < layout.h) 547 if (j + 1 < maze.h)
531 { 548 {
532 if (layout[i][j + 1] == ch) 549 if (maze[i][j + 1] == ch)
533 pattern |= 2; 550 pattern |= 2;
534 551
535 if (i + 1 < layout.w && layout[i + 1][j + 1] == ch) 552 if (i + 1 < maze.w && maze[i + 1][j + 1] == ch)
536 pattern |= 4; 553 pattern |= 4;
537 } 554 }
538 555
539 return pattern; 556 return pattern;
540} 557}
… …
542/* Expand a wall. This function will try to sensibly connect the resulting 559/* Expand a wall. This function will try to sensibly connect the resulting
543 * wall to adjacent wall squares, so that the result won't have disconnected 560 * wall to adjacent wall squares, so that the result won't have disconnected
544 * walls. 561 * walls.
545 */ 562 */
546static void inline 563static void inline
547expand_wall (Layout &newlayout, int i, int j, Layout &layout) 564expand_wall (layout &newlayout, int i, int j, layout &maze)
548{ 565{
549 int wall_pattern = calc_pattern ('#', layout, i, j); 566 int wall_pattern = calc_pattern ('#', maze, i, j);
550 int door_pattern = calc_pattern ('D', layout, i, j); 567 int door_pattern = calc_pattern ('D', maze, i, j);
551 int both_pattern = wall_pattern | door_pattern; 568 int both_pattern = wall_pattern | door_pattern;
552 569
553 newlayout[i * 2][j * 2] = '#'; 570 newlayout[i * 2][j * 2] = '#';
554 571
555 if (i + 1 < layout.w) 572 if (i + 1 < maze.w)
556 { 573 {
557 if (both_pattern & 1) 574 if (both_pattern & 1)
558 { /* join walls/doors to the right */ 575 { /* join walls/doors to the right */
559/* newlayout[i*2+1][j*2] = '#'; */ 576/* newlayout[i*2+1][j*2] = '#'; */
560 newlayout[i * 2 + 1][j * 2] = layout[i + 1][j]; 577 newlayout[i * 2 + 1][j * 2] = maze[i + 1][j];
561 } 578 }
562 } 579 }
563 580
564 if (j + 1 < layout.h) 581 if (j + 1 < maze.h)
565 { 582 {
566 if (both_pattern & 2) 583 if (both_pattern & 2)
567 { /* join walls/doors to the bottom */ 584 { /* join walls/doors to the bottom */
568/* newlayout[i*2][j*2+1] = '#'; */ 585/* newlayout[i*2][j*2+1] = '#'; */
569 newlayout[i * 2][j * 2 + 1] = layout[i][j + 1]; 586 newlayout[i * 2][j * 2 + 1] = maze[i][j + 1];
570 } 587 }
571 588
572 if (wall_pattern == 7) 589 if (wall_pattern == 7)
573 { /* if orig layout is a 2x2 wall block, 590 { /* if orig maze is a 2x2 wall block,
574 * we fill the result with walls. */ 591 * we fill the result with walls. */
575 newlayout[i * 2 + 1][j * 2 + 1] = '#'; 592 newlayout[i * 2 + 1][j * 2 + 1] = '#';
576 } 593 }
577 } 594 }
578} 595}
… …
580/* This function will try to sensibly connect doors so that they meet up with 597/* This function will try to sensibly connect doors so that they meet up with
581 * adjacent walls. Note that it will also presumptuously delete (ignore) doors 598 * adjacent walls. Note that it will also presumptuously delete (ignore) doors
582 * that it doesn't know how to correctly expand. 599 * that it doesn't know how to correctly expand.
583 */ 600 */
584static void inline 601static void inline
585expand_door (Layout &newlayout, int i, int j, Layout &layout) 602expand_door (layout &newlayout, int i, int j, layout &maze)
586{ 603{
587 int wall_pattern = calc_pattern ('#', layout, i, j); 604 int wall_pattern = calc_pattern ('#', maze, i, j);
588 int door_pattern = calc_pattern ('D', layout, i, j); 605 int door_pattern = calc_pattern ('D', maze, i, j);
589 int join_pattern; 606 int join_pattern;
590 607
591 /* Doors "like" to connect to walls more than other doors. If there is 608 /* Doors "like" to connect to walls more than other doors. If there is
592 * a wall and another door, this door will connect to the wall and 609 * a wall and another door, this door will connect to the wall and
593 * disconnect from the other door. */ 610 * disconnect from the other door. */
… …
596 else 613 else
597 join_pattern = door_pattern; 614 join_pattern = door_pattern;
598 615
599 newlayout[i * 2][j * 2] = 'D'; 616 newlayout[i * 2][j * 2] = 'D';
600 617
601 if (i + 1 < layout.w) 618 if (i + 1 < maze.w)
602 if (join_pattern & 1) 619 if (join_pattern & 1)
603 /* there is a door/wall to the right */ 620 /* there is a door/wall to the right */
604 newlayout[i * 2 + 1][j * 2] = 'D'; 621 newlayout[i * 2 + 1][j * 2] = 'D';
605 622
606 if (j + 1 < layout.h) 623 if (j + 1 < maze.h)
607 if (join_pattern & 2) 624 if (join_pattern & 2)
608 /* there is a door/wall below */ 625 /* there is a door/wall below */
609 newlayout[i * 2][j * 2 + 1] = 'D'; 626 newlayout[i * 2][j * 2 + 1] = 'D';
610} 627}
611 628
612void 629void
613Layout::expand2x () 630layout::expand2x ()
614{ 631{
615 Layout new_layout (w * 2 - 1, h * 2 - 1); 632 layout new_layout (w * 2 - 1, h * 2 - 1);
616 633
617 new_layout.clear (); 634 new_layout.clear ();
635
636 coroapi::cede_to_tick ();
618 637
619 for (int i = 0; i < w; i++) 638 for (int i = 0; i < w; i++)
620 for (int j = 0; j < h; j++) 639 for (int j = 0; j < h; j++)
621 switch (col [i][j]) 640 switch (data [i][j])
622 { 641 {
623 case '#': expand_wall (new_layout, i, j, *this); break; 642 case '#': expand_wall (new_layout, i, j, *this); break;
624 case 'D': expand_door (new_layout, i, j, *this); break; 643 case 'D': expand_door (new_layout, i, j, *this); break;
625 default: expand_misc (new_layout, i, j, *this); break; 644 default: expand_misc (new_layout, i, j, *this); break;
626 } 645 }
627 646
628 swap (new_layout); 647 swap (new_layout);
629} 648}
630 649
631///////////////////////////////////////////////////////////////////////////// 650/////////////////////////////////////////////////////////////////////////////
632 651
633/* checks the layout to see if I can stick a horizontal(dir = 0) wall 652/* checks the maze to see if I can stick a horizontal(dir = 0) wall
634 (or vertical, dir == 1) 653 (or vertical, dir == 1)
635 here which ends up on other walls sensibly. */ 654 here which ends up on other walls sensibly. */
636static int 655static int
637can_make_wall (const Layout &maze, int dx, int dy, int dir) 656can_make_wall (const layout &maze, int dx, int dy, int dir)
638{ 657{
639 int i1; 658 int i1;
640 int length = 0; 659 int length = 0;
641 660
642 /* dont make walls if we're on the edge. */ 661 /* dont make walls if we're on the edge. */
… …
705 724
706 return -1; 725 return -1;
707} 726}
708 727
709int 728int
710make_wall (char **maze, int x, int y, int dir) 729make_wall (layout &maze, int x, int y, int dir)
711{ 730{
712 maze[x][y] = 'D'; /* mark a door */ 731 maze[x][y] = 'D'; /* mark a door */
713 732
714 switch (dir) 733 switch (dir)
715 { 734 {
… …
729 748
730 return 0; 749 return 0;
731} 750}
732 751
733void 752void
734Layout::roomify () 753layout::roomify ()
735{ 754{
736 int tries = w * h / 30; 755 int tries = w * h / 30;
756
757 coroapi::cede_to_tick ();
737 758
738 for (int ti = 0; ti < tries; ti++) 759 for (int ti = 0; ti < tries; ti++)
739 { 760 {
740 /* starting location for looking at creating a door */ 761 /* starting location for looking at creating a door */
741 int dx = rmg_rndm (w); 762 int dx = rmg_rndm (w);
… …
764 else 785 else
765 make_wall (*this, dx, dy, 1); 786 make_wall (*this, dx, dy, 1);
766 } 787 }
767} 788}
768 789
790//-GPL
791
769///////////////////////////////////////////////////////////////////////////// 792/////////////////////////////////////////////////////////////////////////////
770 793
794// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
795void
796layout::gen_cave (int subtype)
797{
798 switch (subtype)
799 {
800 // a rough cave
801 case 0:
802 fill_rand (rmg_rndm (85, 97));
803 break;
804
805 // corridors
806 case 1:
807 fill_rand (rmg_rndm (5, 40));
808 erode_1_2 (5, 2, 10);
809 erode_1_2 (5, -1, 10);
810 erode_1_2 (5, 2, 1);
811 break;
812
813 // somewhat open, some room-like structures
814 case 2:
815 fill_rand (45);
816 erode_1_2 (5, 2, 4);
817 erode_1_2 (5, -1, 3);
818 break;
819
820 // wide open, roundish
821 case 3:
822 fill_rand (45);
823 erode_1_2 (5, 0, 5);
824 erode_1_2 (5, 1, 1);
825 break;
826 }
827
828 border ();
829 isolation_remover (1);
830}
831
832void
833layout::gen_castle ()
834{
835 fill ('#');
836
837 for (int n = w * h / 30 + 1; n--; )
838 {
839 int rw = rmg_rndm (6, 10);
840 int rh = rmg_rndm (6, 10);
841
842 if (rw > w || rh > h)
843 continue;
844
845 int rx = rmg_rndm (0, w - rw);
846 int ry = rmg_rndm (0, h - rh);
847
848 rect (rx, ry, rx + rw, ry + rh, '#');
849 fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0);
850 }
851
852 border ();
853 isolation_remover (0);
854}
855
856static void
857gen_mixed_ (layout &maze, random_map_params *RP)
858{
859 if (maze.w > maze.h && maze.w > 16)
860 {
861 int m = rmg_rndm (8, maze.w - 8);
862
863 layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP);
864 layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP);
865 }
866 else if (maze.h > 16)
867 {
868 int m = rmg_rndm (8, maze.h - 8);
869
870 layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP);
871 layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP);
872 }
873 else
874 {
875 RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
876
877 if (RP->map_layout_style == LAYOUT_MULTIPLE)
878 ++RP->map_layout_style;
879
880 maze.generate (RP);
881 }
882
883 coroapi::cede_to_tick ();
884}
885
886// recursive subdivision with random sublayouts
887static void
888gen_mixed (layout &maze, random_map_params *RP)
889{
890 random_map_params &rp = *new random_map_params (RP);
891 gen_mixed_ (maze, &rp);
892 delete &rp;
893
894 maze.border ();
895
896 // exits currently do not work so well, as they
897 // are currently often found together, so nuke entrances
898 maze.replace ('<', ' ');
899
900 maze.isolation_remover (0);
901}
902
903//+GPL
904
771/* function selects the layout function and gives it whatever 905/* function selects the maze function and gives it whatever
772 arguments it needs. */ 906 arguments it needs. */
773void 907void
774Layout::generate (random_map_params *RP) 908layout::generate (random_map_params *RP)
775{ 909{
776 switch (RP->map_layout_style) 910 switch (RP->map_layout_style)
777 { 911 {
778 case LAYOUT_ONION: 912 case LAYOUT_ONION:
779 map_gen_onion (*this, RP->layoutoptions1, RP->layoutoptions2); 913 map_gen_onion (*this, RP->layoutoptions1, RP->layoutoptions2);
… …
834 if (rmg_rndm (2)) 968 if (rmg_rndm (2))
835 doorify (); 969 doorify ();
836 970
837 break; 971 break;
838 972
973 case LAYOUT_CASTLE:
974 gen_castle ();
975
976 if (rmg_rndm (2))
977 doorify ();
978
979 break;
980
981 case LAYOUT_MULTIPLE:
982 gen_mixed (*this, RP);
983 break;
984
839 default: 985 default:
840 abort (); 986 abort ();
841 } 987 }
988}
842 989
843 /* rotate the layout randomly */ 990//-GPL
844 rotate (rmg_rndm (4));
845
846 symmetrize (RP->symmetry_used);
847 991
848#if 0 992#if 0
849 print ();//D 993static void
850#endif 994gen_village (layout &maze)
995{
996 maze.clear ();
997 maze.border ();
851 998
852 if (RP->expand2x) 999 for (int n = maze.w * maze.h / 200 + 1; n--; )
853 expand2x (); 1000 {
854} 1001 int rw = rmg_rndm (6, 10);
1002 int rh = rmg_rndm (6, 10);
855 1003
856//-GPL 1004 int rx = rmg_rndm (2, maze.w - rw - 2);
1005 int ry = rmg_rndm (2, maze.h - rh - 2);
857 1006
858#if 0 1007 maze.rect (rx, ry, rx + rw, ry + rh, '#');
1008 }
1009
1010 maze.border ();
1011 maze.isolation_remover (2);
1012}
1013
859static struct demo 1014static struct demo
860{ 1015{
861 demo () 1016 demo ()
862 { 1017 {
863 rmg_rndm.seed (time (0)); 1018 rmg_rndm.seed (time (0));
1019 extern void hack();hack ();
864 1020
865 for(int i=1;i<10;i) 1021 for(int i=1;i<100;i++)
866 { 1022 {
867 Layout maze (10, 10); 1023 layout maze (40, 30);
868 maze.fill_rand (90); 1024 maze.fill_rand (99);
869 maze.border (); 1025 maze.border ();
870 maze.isolation_remover (); 1026 maze.isolation_remover (2);
871 maze.doorify ();
872 maze.symmetrize (rmg_rndm (2, 4));
873 maze.rotate (rmg_rndm (4));
874 maze.expand2x ();
875 maze.print (); 1027 maze.print ();
876 } 1028 }
877 1029
878 exit (1); 1030 exit (1);
879 } 1031 }

Diff Legend

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