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.2 by root, Tue Aug 29 08:01:36 2006 UTC vs.
Revision 1.13 by root, Wed Jun 30 20:51:02 2010 UTC

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

Diff Legend

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