ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/random_maps/rogue_layout.C
(Generate patch)

Comparing deliantra/server/random_maps/rogue_layout.C (file contents):
Revision 1.5 by root, Thu Jan 18 19:42:10 2007 UTC vs.
Revision 1.11 by root, Sat Nov 7 18:30:05 2009 UTC

1
2/* generate a rogue/nethack-like layout */ 1/* generate a rogue/nethack-like layout */
3#include <global.h> 2#include <global.h>
4#include <random_map.h> 3#include <random_map.h>
5#include <math.h> 4#include <rproto.h>
6 5
7typedef struct 6typedef struct
8{ 7{
9 int x; 8 int x;
10 int y; /* coordinates of room centers */ 9 int y; /* coordinates of room centers */
14 int ax, ay, zx, zy; /* coordinates of extrema of the rectangle */ 13 int ax, ay, zx, zy; /* coordinates of extrema of the rectangle */
15 14
16 int rtype; /* circle or rectangular */ 15 int rtype; /* circle or rectangular */
17} Room; 16} Room;
18 17
19static int roguelike_place_room (Room * Rooms, int xsize, int ysize, int nrooms); 18static int roguelike_place_room (Room *rooms, int xsize, int ysize, int nrooms);
20static void roguelike_make_rooms (Room * Rooms, char **maze, int options); 19static void roguelike_make_rooms (Room *rooms, char **maze, int options);
21static void roguelike_link_rooms (Room * Rooms, char **maze, int xsize, int ysize); 20static void roguelike_link_rooms (Room *rooms, char **maze, int xsize, int ysize);
22
23 21
24int 22int
25surround_check (char **layout, int i, int j, int Xsize, int Ysize) 23surround_check (char **layout, int i, int j, int Xsize, int Ysize)
26{ 24{
27 /* 1 = wall to left, 25 /* 1 = wall to left,
28 2 = wall to right, 26 2 = wall to right,
29 4 = wall above 27 4 = wall above
30 8 = wall below */ 28 8 = wall below */
31 int surround_index = 0; 29 int surround_index = 0;
32 30
33 if ((i > 0) && (layout[i - 1][j] != 0 && layout[i - 1][j] != '.')) 31 if ((i > 0) && (layout[i - 1][j] != 0 && layout[i - 1][j] != '.')) surround_index |= 1;
34 surround_index += 1;
35 if ((i < Xsize - 1) && (layout[i + 1][j] != 0 && layout[i + 1][j] != '.')) 32 if ((i < Xsize - 1) && (layout[i + 1][j] != 0 && layout[i + 1][j] != '.')) surround_index |= 2;
36 surround_index += 2;
37 if ((j > 0) && (layout[i][j - 1] != 0 && layout[i][j - 1] != '.')) 33 if ((j > 0) && (layout[i][j - 1] != 0 && layout[i][j - 1] != '.')) surround_index |= 4;
38 surround_index += 4;
39 if ((j < Ysize - 1) && (layout[i][j + 1] != 0 && layout[i][j + 1] != '.')) 34 if ((j < Ysize - 1) && (layout[i][j + 1] != 0 && layout[i][j + 1] != '.')) surround_index |= 8;
40 surround_index += 8; 35
41 return surround_index; 36 return surround_index;
42} 37}
43
44 38
45/* actually make the layout: we work by a reduction process: 39/* actually make the layout: we work by a reduction process:
46 * first we make everything a wall, then we remove areas to make rooms 40 * first we make everything a wall, then we remove areas to make rooms
47 */ 41 */
48 42void
49char ** 43roguelike_layout_gen (Layout maze, int options)
50roguelike_layout_gen (int xsize, int ysize, int options)
51{ 44{
52 int i, j; 45 int i, j;
53 Room *Rooms = 0;
54 Room *walk; 46 Room *walk;
55 int nrooms = 0; 47 int nrooms = 0;
56 int tries = 0; 48 int tries = 0;
57 49
58 /* allocate that array, write walls everywhere up */ 50 int xsize = maze->w;
59 char **maze = (char **) malloc (sizeof (char *) * xsize); 51 int ysize = maze->h;
60
61 for (i = 0; i < xsize; i++)
62 {
63 maze[i] = (char *) malloc (sizeof (char) * ysize);
64 for (j = 0; j < ysize; j++)
65 maze[i][j] = '#';
66 }
67 52
68 /* minimum room size is basically 5x5: if xsize/ysize is 53 /* minimum room size is basically 5x5: if xsize/ysize is
69 less than 3x that then hollow things out, stick in 54 less than 3x that then hollow things out, stick in
70 a stairsup and stairs down, and exit */ 55 a stairsup and stairs down, and exit */
71
72 if (xsize < 11 || ysize < 11) 56 if (xsize < 11 || ysize < 11)
73 { 57 {
74 for (i = 1; i < xsize - 1; i++) 58 maze->clear ();
75 for (j = 1; j < ysize - 1; j++) 59 maze->border ();
76 maze[i][j] = 0; 60
77 maze[(xsize - 1) / 2][(ysize - 1) / 2] = '>'; 61 maze[(xsize - 1) / 2][(ysize - 1) / 2 ] = '>';
78 maze[(xsize - 1) / 2][(ysize - 1) / 2 + 1] = '<'; 62 maze[(xsize - 1) / 2][(ysize - 1) / 2 + 1] = '<';
63
79 return maze; 64 return;
80 } 65 }
66
67 maze->clear ('#');
81 68
82 /* decide on the number of rooms */ 69 /* decide on the number of rooms */
83 nrooms = rndm (10) + 6; 70 nrooms = rmg_rndm (10) + 6;
84 Rooms = (Room *) calloc (nrooms + 1, sizeof (Room)); 71 Room *rooms = salloc0<Room> (nrooms + 1);
85 72
86 /* actually place the rooms */ 73 /* actually place the rooms */
87 i = 0; 74 i = 0;
88 while (tries < 450 && i < nrooms) 75 while (tries < 450 && i < nrooms)
89 { 76 {
90 /* try to place the room */ 77 /* try to place the room */
91 if (!roguelike_place_room (Rooms, xsize, ysize, nrooms)) 78 if (!roguelike_place_room (rooms, xsize, ysize, nrooms))
92 tries++; 79 tries++;
93 else 80 else
94 i++; 81 i++;
95 } 82 }
96 83
97 if (i == 0) 84 if (i == 0) /* no can do! */
98 { /* no can do! */ 85 {
99 for (i = 1; i < xsize - 1; i++) 86 maze->clear ();
100 for (j = 1; j < ysize - 1; j++) 87 maze->border ();
101 maze[i][j] = 0; 88
102 maze[(xsize - 1) / 2][(ysize - 1) / 2] = '>'; 89 maze [(xsize - 1) / 2][(ysize - 1) / 2 ] = '>';
103 maze[(xsize - 1) / 2][(ysize - 1) / 2 + 1] = '<'; 90 maze [(xsize - 1) / 2][(ysize - 1) / 2 + 1] = '<';
104 free (Rooms); 91
92 sfree (rooms, nrooms + 1);
105 return maze; 93 return;
106 } 94 }
107
108 95
109 /* erase the areas occupied by the rooms */ 96 /* erase the areas occupied by the rooms */
110 roguelike_make_rooms (Rooms, maze, options); 97 roguelike_make_rooms (rooms, maze, options);
111 98
112 roguelike_link_rooms (Rooms, maze, xsize, ysize); 99 roguelike_link_rooms (rooms, maze, xsize, ysize);
113 100
114 /* put in the stairs */ 101 /* put in the stairs */
115 102
116 maze[Rooms->x][Rooms->y] = '<'; 103 maze[rooms->x][rooms->y] = '<';
104
117 /* get the last one */ 105 /* get the last one */
118 for (walk = Rooms; walk->x != 0; walk++); 106 for (walk = rooms; walk->x != 0; walk++)
107 ;
108
119 /* back up one */ 109 /* back up one */
120 walk--; 110 walk--;
111
121 if (walk == Rooms) 112 if (walk == rooms)
122 { 113 {
123 /* In this case, there is only a single room. We don't want to 114 /* In this case, there is only a single room. We don't want to
124 * clobber are up exit (above) with a down exit, so put the 115 * clobber are up exit (above) with a down exit, so put the
125 * other exit one space up/down, depending which is a space 116 * other exit one space up/down, depending which is a space
126 * and not a wall. 117 * and not a wall.
137 for (i = 0; i < xsize; i++) 128 for (i = 0; i < xsize; i++)
138 for (j = 0; j < ysize; j++) 129 for (j = 0; j < ysize; j++)
139 { 130 {
140 if (maze[i][j] == '.') 131 if (maze[i][j] == '.')
141 maze[i][j] = 0; 132 maze[i][j] = 0;
133
142 if (maze[i][j] == 'D') 134 if (maze[i][j] == 'D')
143 { /* remove bad door. */ 135 { /* remove bad door. */
144 int si = surround_check (maze, i, j, xsize, ysize); 136 int si = surround_check (maze, i, j, xsize, ysize);
145 137
146 if (si != 3 && si != 12) 138 if (si != 3 && si != 12)
151 j = 0; 143 j = 0;
152 } 144 }
153 } 145 }
154 } 146 }
155 147
156 free (Rooms); 148 sfree (rooms, nrooms + 1);
157 return maze;
158} 149}
159
160
161 150
162static int 151static int
163roguelike_place_room (Room * Rooms, int xsize, int ysize, int nrooms) 152roguelike_place_room (Room *rooms, int xsize, int ysize, int nrooms)
164{ 153{
165
166 int tx, ty; /* trial center locations */ 154 int tx, ty; /* trial center locations */
167 int sx, sy; /* trial sizes */ 155 int sx, sy; /* trial sizes */
168 int ax, ay; /* min coords of rect */ 156 int ax, ay; /* min coords of rect */
169 int zx, zy; /* max coords of rect */ 157 int zx, zy; /* max coords of rect */
170 int x_basesize; 158 int x_basesize;
171 int y_basesize; 159 int y_basesize;
172 Room *walk; 160 Room *walk;
173 161
174 /* decide on the base x and y sizes */ 162 /* decide on the base x and y sizes */
175
176 x_basesize = xsize / isqrt (nrooms); 163 x_basesize = xsize / isqrt (nrooms);
177 y_basesize = ysize / isqrt (nrooms); 164 y_basesize = ysize / isqrt (nrooms);
178 165
179 166 tx = rmg_rndm (xsize);
180 tx = RANDOM () % xsize; 167 ty = rmg_rndm (ysize);
181 ty = RANDOM () % ysize;
182 168
183 /* generate a distribution of sizes centered about basesize */ 169 /* generate a distribution of sizes centered about basesize */
184 sx = (RANDOM () % x_basesize) + (RANDOM () % x_basesize) + (RANDOM () % x_basesize); 170 sx = rmg_rndm (x_basesize) + rmg_rndm (x_basesize) + rmg_rndm (x_basesize);
185 sy = (RANDOM () % y_basesize) + (RANDOM () % y_basesize) + (RANDOM () % y_basesize); 171 sy = rmg_rndm (y_basesize) + rmg_rndm (y_basesize) + rmg_rndm (y_basesize);
186 sy = (int) (sy * .5); /* renormalize */ 172 sy = (int) (sy * .5); /* renormalize */
187 173
188 /* find the corners */ 174 /* find the corners */
189 ax = tx - sx / 2; 175 ax = tx - sx / 2;
190 zx = tx + sx / 2 + sx % 2; 176 zx = tx + sx / 2 + sx % 2;
191 177
192 ay = ty - sy / 2; 178 ay = ty - sy / 2;
193 zy = ty + sy / 2 + sy % 2; 179 zy = ty + sy / 2 + sy % 2;
194 180
195 /* check to see if it's in the map */ 181 /* check to see if it's in the map */
196 if (zx > xsize - 1 || ax < 1) 182 if (zx > xsize - 1 || ax < 1) return 0;
197 return 0;
198 if (zy > ysize - 1 || ay < 1) 183 if (zy > ysize - 1 || ay < 1) return 0;
199 return 0;
200 184
201 /* no small fish */ 185 /* no small fish */
202 if (sx < 3 || sy < 3) 186 if (sx < 3 || sy < 3)
203 return 0; 187 return 0;
204 188
205 /* check overlap with existing rooms */ 189 /* check overlap with existing rooms */
206 for (walk = Rooms; walk->x != 0; walk++) 190 for (walk = rooms; walk->x != 0; walk++)
207 { 191 {
208 int dx = abs (tx - walk->x); 192 int dx = abs (tx - walk->x);
209 int dy = abs (ty - walk->y); 193 int dy = abs (ty - walk->y);
210 194
211 if ((dx < (walk->sx + sx) / 2 + 2) && (dy < (walk->sy + sy) / 2 + 2)) 195 if ((dx < (walk->sx + sx) / 2 + 2) && (dy < (walk->sy + sy) / 2 + 2))
213 } 197 }
214 198
215 /* if we've got here, presumably the room is OK. */ 199 /* if we've got here, presumably the room is OK. */
216 200
217 /* get a pointer to the first free room */ 201 /* get a pointer to the first free room */
218 for (walk = Rooms; walk->x != 0; walk++); 202 for (walk = rooms; walk->x != 0; walk++)
203 ;
204
219 walk->x = tx; 205 walk->x = tx;
220 walk->y = ty; 206 walk->y = ty;
221 walk->sx = sx; 207 walk->sx = sx;
222 walk->sy = sy; 208 walk->sy = sy;
223 walk->ax = ax; 209 walk->ax = ax;
224 walk->ay = ay; 210 walk->ay = ay;
225 walk->zx = zx; 211 walk->zx = zx;
226 walk->zy = zy; 212 walk->zy = zy;
213
227 return 1; /* success */ 214 return 1; /* success */
228
229} 215}
230
231 216
232/* write all the rooms into the maze */ 217/* write all the rooms into the maze */
233static void 218static void
234roguelike_make_rooms (Room * Rooms, char **maze, int options) 219roguelike_make_rooms (Room *rooms, char **maze, int options)
235{ 220{
236 int making_circle = 0; 221 int making_circle = 0;
237 int i, j; 222 int i, j;
238 int R; 223 int R;
239 Room *walk; 224 Room *walk;
240 225
241 for (walk = Rooms; walk->x != 0; walk++) 226 for (walk = rooms; walk->x != 0; walk++)
242 { 227 {
243 /* first decide what shape to make */ 228 /* first decide what shape to make */
244 switch (options) 229 switch (options)
245 { 230 {
246 case 1: 231 case 1:
248 break; 233 break;
249 case 2: 234 case 2:
250 making_circle = 1; 235 making_circle = 1;
251 break; 236 break;
252 default: 237 default:
253 making_circle = ((rndm (3) == 0) ? 1 : 0); 238 making_circle = ((rmg_rndm (3) == 0) ? 1 : 0);
254 break; 239 break;
255 } 240 }
256 241
257 if (walk->sx < walk->sy) 242 if (walk->sx < walk->sy)
258 R = walk->sx / 2; 243 R = walk->sx / 2;
260 R = walk->sy / 2; 245 R = walk->sy / 2;
261 246
262 /* enscribe a rectangle */ 247 /* enscribe a rectangle */
263 for (i = walk->ax; i < walk->zx; i++) 248 for (i = walk->ax; i < walk->zx; i++)
264 for (j = walk->ay; j < walk->zy; j++) 249 for (j = walk->ay; j < walk->zy; j++)
265 {
266 if (!making_circle || ((int) (0.5 + hypot (walk->x - i, walk->y - j))) <= R) 250 if (!making_circle || ((int) (0.5 + hypot (walk->x - i, walk->y - j))) <= R)
267 maze[i][j] = '.'; 251 maze[i][j] = '.';
268 }
269 } 252 }
270} 253}
271
272
273 254
274static void 255static void
275roguelike_link_rooms (Room * Rooms, char **maze, int xsize, int ysize) 256roguelike_link_rooms (Room *rooms, char **maze, int xsize, int ysize)
276{ 257{
277 Room *walk; 258 Room *walk;
278 int i, j; 259 int i, j;
279 260
280 /* link each room to the previous room */ 261 /* link each room to the previous room */
281 if (Rooms[1].x == 0) 262 if (rooms[1].x == 0)
282 return; /* only 1 room */ 263 return; /* only 1 room */
283 264
284 for (walk = Rooms + 1; walk->x != 0; walk++) 265 for (walk = rooms + 1; walk->x != 0; walk++)
285 { 266 {
286 int x1 = walk->x; 267 int x1 = walk->x;
287 int y1 = walk->y; 268 int y1 = walk->y;
288 int x2 = (walk - 1)->x; 269 int x2 = (walk - 1)->x;
289 int y2 = (walk - 1)->y; 270 int y2 = (walk - 1)->y;
290 int in_wall = 0; 271 int in_wall = 0;
291 272
292 if (rndm (2)) 273 if (rmg_rndm (2))
293 { /* connect in x direction first */ 274 { /* connect in x direction first */
294 /* horizontal connect */ 275 /* horizontal connect */
295 /* swap (x1,y1) (x2,y2) if necessary */ 276 /* swap (x1,y1) (x2,y2) if necessary */
296 277
297 if (x2 < x1) 278 if (x2 < x1)
319 maze[i - 1][j] = 'D'; 300 maze[i - 1][j] = 'D';
320 } 301 }
321 else if (maze[i][j] != 'D' && maze[i][j] != '.') 302 else if (maze[i][j] != 'D' && maze[i][j] != '.')
322 maze[i][j] = 0; 303 maze[i][j] = 0;
323 } 304 }
305
324 j = MIN (y1, y2); 306 j = min (y1, y2);
307
325 if (maze[i][j] == '.') 308 if (maze[i][j] == '.')
326 in_wall = 0; 309 in_wall = 0;
310
327 if (maze[i][j] == 0 || maze[i][j] == '#') 311 if (maze[i][j] == 0 || maze[i][j] == '#')
328 in_wall = 1; 312 in_wall = 1;
313
329 for ( /* j set already */ ; j < MAX (y1, y2); j++) 314 for ( /* j set already */ ; j < max (y1, y2); j++)
330 { 315 {
331 if (in_wall == 0 && maze[i][j] == '#') 316 if (in_wall == 0 && maze[i][j] == '#')
332 { 317 {
333 in_wall = 1; 318 in_wall = 1;
334 maze[i][j] = 'D'; 319 maze[i][j] = 'D';
372 } 357 }
373 else if (maze[i][j] != 'D' && maze[i][j] != '.') 358 else if (maze[i][j] != 'D' && maze[i][j] != '.')
374 maze[i][j] = 0; 359 maze[i][j] = 0;
375 } 360 }
376 361
377 i = MIN (x1, x2); 362 i = min (x1, x2);
363
378 if (maze[i][j] == '.') 364 if (maze[i][j] == '.')
379 in_wall = 0; 365 in_wall = 0;
366
380 if (maze[i][j] == 0 || maze[i][j] == '#') 367 if (maze[i][j] == 0 || maze[i][j] == '#')
381 in_wall = 1; 368 in_wall = 1;
369
382 for ( /* i set already */ ; i < MAX (x1, x2); i++) 370 for ( /* i set already */ ; i < max (x1, x2); i++)
383 { 371 {
384 if (in_wall == 0 && maze[i][j] == '#') 372 if (in_wall == 0 && maze[i][j] == '#')
385 { 373 {
386 in_wall = 1; 374 in_wall = 1;
387 maze[i][j] = 'D'; 375 maze[i][j] = 'D';
398 386
399 } 387 }
400 388
401 } 389 }
402} 390}
391

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines