server/random_maps/rogue_layout.c

/* generate a rogue/nethack-like layout */
#include <global.h>
#include <random_map.h>
#include <math.h>

typedef struct {
  int x;
  int y;  /* coordinates of room centers */

  int sx;
  int sy;  /* sizes */
  int ax,ay,zx,zy;  /* coordinates of extrema of the rectangle */

  int rtype;  /* circle or rectangular */
} Room;

static int roguelike_place_room(Room *Rooms,int xsize, int ysize,int nrooms);
static void roguelike_make_rooms(Room *Rooms,char **maze, int options);
static void roguelike_link_rooms(Room *Rooms,char **maze,int xsize,int ysize);


int surround_check(char **layout,int i,int j,int Xsize, int Ysize){
  /* 1 = wall to left,
          2 = wall to right,
          4 = wall above
          8 = wall below */
  int surround_index = 0;
  if((i > 0) && (layout[i-1][j]!=0&&layout[i-1][j]!='.')) surround_index +=1;
  if((i < Xsize-1) && (layout[i+1][j]!=0&&layout[i+1][j]!='.')) surround_index +=2;
  if((j > 0) && (layout[i][j-1]!=0&&layout[i][j-1]!='.')) surround_index +=4;
  if((j < Ysize-1) && (layout[i][j+1]!=0&&layout[i][j+1]!='.')) surround_index +=8;
  return surround_index;
}


/* actually make the layout:  we work by a reduction process:
 * first we make everything a wall, then we remove areas to make rooms 
 */

char **roguelike_layout_gen(int xsize, int ysize, int options) {
  int i,j;
  Room * Rooms = 0;
  Room *walk;
  int nrooms=0;
  int tries=0;

  /* allocate that array, write walls everywhere up */
  char **maze = (char **)malloc(sizeof(char*)*xsize);
  for(i=0;i<xsize;i++) {
    maze[i] = (char *) malloc(sizeof(char)*ysize);
    for(j=0;j<ysize;j++) maze[i][j] = '#';
  }

  /* minimum room size is basically 5x5:  if xsize/ysize is
     less than 3x that then hollow things out, stick in
     a stairsup and stairs down, and exit */

  if(xsize < 11 || ysize < 11) {
    for(i=1;i<xsize-1;i++)
      for(j=1;j<ysize-1;j++)
        maze[i][j]=0;
    maze[(xsize-1)/2][(ysize-1)/2]='>';
    maze[(xsize-1)/2][(ysize-1)/2+1]='<';
    return maze;
  }

  /* decide on the number of rooms */
  nrooms = RANDOM() % 10 + 6;
  Rooms = (Room *) calloc(nrooms +1 , sizeof(Room)); 

  /* actually place the rooms */
  i=0;
  while( tries < 450 && i < nrooms ) {
    /* try to place the room */
    if(!roguelike_place_room(Rooms,xsize,ysize,nrooms)) tries++;
    else i++;
  }
  
  if(i==0) { /* no can do! */
    for(i=1;i<xsize-1;i++)
      for(j=1;j<ysize-1;j++)
        maze[i][j]=0;
    maze[(xsize-1)/2][(ysize-1)/2]='>';
    maze[(xsize-1)/2][(ysize-1)/2+1]='<';
    free(Rooms);
    return maze;
  }
    
  
  /* erase the areas occupied by the rooms */
  roguelike_make_rooms(Rooms,maze,options);

  roguelike_link_rooms(Rooms,maze,xsize,ysize);

  /* put in the stairs */
  
  maze[Rooms->x][Rooms->y] = '<';
  /* get the last one */
  for(walk=Rooms;walk->x!=0;walk++);
  /* back up one */
  walk--;
  if (walk == Rooms) {
    /* In this case, there is only a single room.  We don't want to
     * clobber are up exit (above) with a down exit, so put the
     * other exit one space up/down, depending which is a space
     * and not a wall.
     */
    if (maze[walk->x][walk->y+1] == '.')
        maze[walk->x][walk->y+1] = '>';
    else
        maze[walk->x][walk->y-1] = '>';
  }
  else
    maze[walk->x][walk->y] = '>';

  /* convert all the '.' to 0, we're through with the '.' */
  for(i=0;i<xsize;i++)
    for(j=0;j<ysize;j++) {
      if(maze[i][j]=='.') maze[i][j]=0;
      if(maze[i][j]=='D') {  /* remove bad door. */
        int si = surround_check(maze,i,j,xsize,ysize);
        if(si!=3 && si!=12) { 
          maze[i][j]=0;
          /* back up and recheck any nearby doors */
          i=0;j=0;
        }
      }
    }
        
  free(Rooms);
  return maze;
}


static int roguelike_place_room(Room *Rooms,int xsize, int ysize,int nrooms) {

  int tx,ty;  /* trial center locations */
  int sx,sy;  /* trial sizes */
  int ax,ay;  /* min coords of rect */
  int zx,zy;  /* max coords of rect */
  int x_basesize;
  int y_basesize;
  Room *walk;

  /* decide on the base x and y sizes */

  x_basesize = xsize / isqrt(nrooms);
  y_basesize = ysize / isqrt(nrooms);


  tx = RANDOM() %xsize;
  ty = RANDOM() %ysize;
 
  /* generate a distribution of sizes centered about basesize */
  sx = (RANDOM() % x_basesize) + (RANDOM() % x_basesize)+ (RANDOM() % x_basesize);
  sy = (RANDOM() % y_basesize) + (RANDOM() % y_basesize)+ (RANDOM() % y_basesize);
  sy = (int) (sy *.5);  /* renormalize */

  /* find the corners */
  ax = tx - sx / 2;
  zx = tx + sx / 2 +sx % 2;

  ay = ty - sy / 2;
  zy = ty + sy / 2 +sy % 2;

  /* check to see if it's in the map */
  if(zx > xsize - 1 || ax < 1) return 0;
  if(zy > ysize - 1 || ay < 1) return 0;
  
  /* no small fish */
  if(sx < 3 || sy < 3) return 0;

  /* check overlap with existing rooms */
  for(walk=Rooms;walk->x!=0;walk++) {
    int dx = abs(tx - walk->x);
    int dy = abs(ty - walk->y);
    if( (dx < (walk->sx + sx)/2 + 2) &&
        (dy < (walk->sy + sy)/2 + 2))
      return 0;
  }

  /* if we've got here, presumably the room is OK. */

  /* get a pointer to the first free room */
  for(walk=Rooms;walk->x!=0;walk++);
  walk->x = tx;
  walk->y = ty;
  walk->sx = sx;
  walk->sy = sy;
  walk->ax = ax;
  walk->ay = ay;
  walk->zx = zx;
  walk->zy = zy;
  return 1;  /* success */

}
    

/* write all the rooms into the maze */
static void roguelike_make_rooms(Room *Rooms,char **maze, int options) {
  int making_circle=0;
  int i,j;
  int R;
  Room *walk;

  for(walk=Rooms;walk->x!=0;walk++) {
    /* first decide what shape to make */
    switch(options) {
    case 1:
      making_circle=0;
      break;
    case 2:
      making_circle = 1;
      break;
    default:
      making_circle = ((RANDOM()%3 == 0)? 1:0);
      break;
    }

    if(walk->sx < walk->sy)
      R = walk->sx/2;
    else
      R = walk->sy/2;

  /* enscribe a rectangle */
    for(i=walk->ax;i<walk->zx;i++)
      for(j=walk->ay;j<walk->zy;j++) {
        if(!making_circle || ((int)(0.5+hypot(walk->x-i,walk->y-j))) <=R) 
          maze[i][j]='.';
      }
  }
}


static void roguelike_link_rooms(Room *Rooms,char **maze,int xsize,int ysize){
  Room *walk;
  int i,j;
  /* link each room to the previous room */
  if(Rooms[1].x==0) return;  /* only 1 room */
  
  for(walk = Rooms +1; walk->x !=0; walk++) {
    int x1=walk->x;
    int y1=walk->y;
    int x2=(walk-1)->x;
    int y2=(walk-1)->y;
    int in_wall=0;
    if(RANDOM()%2) {      /* connect in x direction first */
      /* horizontal connect */
      /* swap (x1,y1) (x2,y2) if necessary */

      if(x2 < x1) {
        int tx=x2,ty=y2;
        x2 = x1; y2 = y1;
        x1 = tx; y1 = ty;
      }


      j = y1;
      for(i=x1;i<x2;i++) {
        if(in_wall==0 && maze[i][j]=='#') {
          in_wall=1;
          maze[i][j]='D';
        }
        else if(in_wall && maze[i][j]=='.') {
          in_wall=0;
          maze[i-1][j]='D';
        }
        else if(maze[i][j]!='D' && maze[i][j]!='.')
          maze[i][j]=0;
      }
      j=MIN(y1,y2);
      if(maze[i][j]=='.') in_wall=0;
      if(maze[i][j]==0|| maze[i][j]=='#') in_wall=1;
      for(/* j set already */;j<MAX(y1,y2);j++) {
        if(in_wall==0 && maze[i][j]=='#') {
          in_wall=1;
          maze[i][j]='D';
        }
        else if(in_wall && maze[i][j]=='.') {
          in_wall=0;
          maze[i][j-1]='D';
        }
        else if(maze[i][j]!='D' && maze[i][j]!='.')
          maze[i][j]=0;
      }
       
    }
    else {  /* connect in y direction first */
      in_wall=0;
      /* swap if necessary */
      if(y2 < y1) {
        int tx=x2,ty=y2;
        x2 = x1; y2 = y1;
        x1 = tx; y1 = ty;
      }
      i = x1;
      /* vertical connect */
      for(j=y1;j<y2;j++) {
        if(in_wall==0 && maze[i][j]=='#') {
          in_wall=1;
          maze[i][j]='D';
        }
        else if(in_wall && maze[i][j]=='.') {
          in_wall=0;
          maze[i][j-1]='D';
        }
        else if(maze[i][j]!='D' && maze[i][j]!='.')
          maze[i][j]=0;
      }

      i=MIN(x1,x2);
      if(maze[i][j]=='.') in_wall=0;
      if(maze[i][j]==0|| maze[i][j]=='#') in_wall=1;
      for(/* i set already */;i<MAX(x1,x2);i++) {
        if(in_wall==0 && maze[i][j]=='#') {
          in_wall=1;
          maze[i][j]='D';
        }
        else if(in_wall && maze[i][j]=='.') {
          in_wall=0;
          maze[i-1][j]='D';
        }
        else 
          if(maze[i][j]!='D' && maze[i][j]!='.') 
            maze[i][j]=0;

      }
       
    }

  }
}
Revision:	1.2
Committed:	Sun Aug 13 17:16:03 2006 UTC (17 years, 9 months ago) by elmex
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+0 -0 lines
State:	*FILE REMOVED*
Log Message:	Made server compile with C++. Removed cfanim plugin and crossedit. C++ here we come.
#	Content
1	/* generate a rogue/nethack-like layout */
2	#include <global.h>
3	#include <random_map.h>
4	#include <math.h>
5
6	typedef struct {
7	int x;
8	int y; /* coordinates of room centers */
9
10	int sx;
11	int sy; /* sizes */
12	int ax,ay,zx,zy; /* coordinates of extrema of the rectangle */
13
14	int rtype; /* circle or rectangular */
15	} Room;
16
17	static int roguelike_place_room(Room *Rooms,int xsize, int ysize,int nrooms);
18	static void roguelike_make_rooms(Room Rooms,char *maze, int options);
19	static void roguelike_link_rooms(Room Rooms,char *maze,int xsize,int ysize);
20
21
22	int surround_check(char **layout,int i,int j,int Xsize, int Ysize){
23	/* 1 = wall to left,
24	2 = wall to right,
25	4 = wall above
26	8 = wall below */
27	int surround_index = 0;
28	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;
30	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;
32	return surround_index;
33	}
34
35
36	/* actually make the layout: we work by a reduction process:
37	* first we make everything a wall, then we remove areas to make rooms
38	*/
39
40	char **roguelike_layout_gen(int xsize, int ysize, int options) {
41	int i,j;
42	Room * Rooms = 0;
43	Room *walk;
44	int nrooms=0;
45	int tries=0;
46
47	/* allocate that array, write walls everywhere up */
48	char maze = (char )malloc(sizeof(char)xsize);
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
54	/* minimum room size is basically 5x5: if xsize/ysize is
55	less than 3x that then hollow things out, stick in
56	a stairsup and stairs down, and exit */
57
58	if(xsize < 11 \|\| ysize < 11) {
59	for(i=1;i<xsize-1;i++)
60	for(j=1;j<ysize-1;j++)
61	maze[i][j]=0;
62	maze[(xsize-1)/2][(ysize-1)/2]='>';
63	maze[(xsize-1)/2][(ysize-1)/2+1]='<';
64	return maze;
65	}
66
67	/* decide on the number of rooms */
68	nrooms = RANDOM() % 10 + 6;
69	Rooms = (Room *) calloc(nrooms +1 , sizeof(Room));
70
71	/* actually place the rooms */
72	i=0;
73	while( tries < 450 && i < nrooms ) {
74	/* try to place the room */
75	if(!roguelike_place_room(Rooms,xsize,ysize,nrooms)) tries++;
76	else i++;
77	}
78
79	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
89
90	/* erase the areas occupied by the rooms */
91	roguelike_make_rooms(Rooms,maze,options);
92
93	roguelike_link_rooms(Rooms,maze,xsize,ysize);
94
95	/* put in the stairs */
96
97	maze[Rooms->x][Rooms->y] = '<';
98	/* get the last one */
99	for(walk=Rooms;walk->x!=0;walk++);
100	/* back up one */
101	walk--;
102	if (walk == Rooms) {
103	/* 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
105	* other exit one space up/down, depending which is a space
106	* and not a wall.
107	*/
108	if (maze[walk->x][walk->y+1] == '.')
109	maze[walk->x][walk->y+1] = '>';
110	else
111	maze[walk->x][walk->y-1] = '>';
112	}
113	else
114	maze[walk->x][walk->y] = '>';
115
116	/* convert all the '.' to 0, we're through with the '.' */
117	for(i=0;i<xsize;i++)
118	for(j=0;j<ysize;j++) {
119	if(maze[i][j]=='.') maze[i][j]=0;
120	if(maze[i][j]=='D') { /* remove bad door. */
121	int si = surround_check(maze,i,j,xsize,ysize);
122	if(si!=3 && si!=12) {
123	maze[i][j]=0;
124	/* back up and recheck any nearby doors */
125	i=0;j=0;
126	}
127	}
128	}
129
130	free(Rooms);
131	return maze;
132	}
133
134
135
136	static int roguelike_place_room(Room *Rooms,int xsize, int ysize,int nrooms) {
137
138	int tx,ty; /* trial center locations */
139	int sx,sy; /* trial sizes */
140	int ax,ay; /* min coords of rect */
141	int zx,zy; /* max coords of rect */
142	int x_basesize;
143	int y_basesize;
144	Room *walk;
145
146	/* decide on the base x and y sizes */
147
148	x_basesize = xsize / isqrt(nrooms);
149	y_basesize = ysize / isqrt(nrooms);
150
151
152	tx = RANDOM() %xsize;
153	ty = RANDOM() %ysize;
154
155	/* generate a distribution of sizes centered about basesize */
156	sx = (RANDOM() % x_basesize) + (RANDOM() % x_basesize)+ (RANDOM() % x_basesize);
157	sy = (RANDOM() % y_basesize) + (RANDOM() % y_basesize)+ (RANDOM() % y_basesize);
158	sy = (int) (sy .5); / renormalize */
159
160	/* find the corners */
161	ax = tx - sx / 2;
162	zx = tx + sx / 2 +sx % 2;
163
164	ay = ty - sy / 2;
165	zy = ty + sy / 2 +sy % 2;
166
167	/* check to see if it's in the map */
168	if(zx > xsize - 1 \|\| ax < 1) return 0;
169	if(zy > ysize - 1 \|\| ay < 1) return 0;
170
171	/* no small fish */
172	if(sx < 3 \|\| sy < 3) return 0;
173
174	/* check overlap with existing rooms */
175	for(walk=Rooms;walk->x!=0;walk++) {
176	int dx = abs(tx - walk->x);
177	int dy = abs(ty - walk->y);
178	if( (dx < (walk->sx + sx)/2 + 2) &&
179	(dy < (walk->sy + sy)/2 + 2))
180	return 0;
181	}
182
183	/* if we've got here, presumably the room is OK. */
184
185	/* get a pointer to the first free room */
186	for(walk=Rooms;walk->x!=0;walk++);
187	walk->x = tx;
188	walk->y = ty;
189	walk->sx = sx;
190	walk->sy = sy;
191	walk->ax = ax;
192	walk->ay = ay;
193	walk->zx = zx;
194	walk->zy = zy;
195	return 1; /* success */
196
197	}
198
199
200	/* write all the rooms into the maze */
201	static void roguelike_make_rooms(Room Rooms,char *maze, int options) {
202	int making_circle=0;
203	int i,j;
204	int R;
205	Room *walk;
206
207	for(walk=Rooms;walk->x!=0;walk++) {
208	/* first decide what shape to make */
209	switch(options) {
210	case 1:
211	making_circle=0;
212	break;
213	case 2:
214	making_circle = 1;
215	break;
216	default:
217	making_circle = ((RANDOM()%3 == 0)? 1:0);
218	break;
219	}
220
221	if(walk->sx < walk->sy)
222	R = walk->sx/2;
223	else
224	R = walk->sy/2;
225
226	/* enscribe a rectangle */
227	for(i=walk->ax;i<walk->zx;i++)
228	for(j=walk->ay;j<walk->zy;j++) {
229	if(!making_circle \|\| ((int)(0.5+hypot(walk->x-i,walk->y-j))) <=R)
230	maze[i][j]='.';
231	}
232	}
233	}
234
235
236
237	static void roguelike_link_rooms(Room Rooms,char *maze,int xsize,int ysize){
238	Room *walk;
239	int i,j;
240	/* link each room to the previous room */
241	if(Rooms[1].x==0) return; /* only 1 room */
242
243	for(walk = Rooms +1; walk->x !=0; walk++) {
244	int x1=walk->x;
245	int y1=walk->y;
246	int x2=(walk-1)->x;
247	int y2=(walk-1)->y;
248	int in_wall=0;
249	if(RANDOM()%2) { /* connect in x direction first */
250	/* horizontal connect */
251	/* swap (x1,y1) (x2,y2) if necessary */
252
253	if(x2 < x1) {
254	int tx=x2,ty=y2;
255	x2 = x1; y2 = y1;
256	x1 = tx; y1 = ty;
257	}
258
259
260	j = y1;
261	for(i=x1;i<x2;i++) {
262	if(in_wall==0 && maze[i][j]=='#') {
263	in_wall=1;
264	maze[i][j]='D';
265	}
266	else if(in_wall && maze[i][j]=='.') {
267	in_wall=0;
268	maze[i-1][j]='D';
269	}
270	else if(maze[i][j]!='D' && maze[i][j]!='.')
271	maze[i][j]=0;
272	}
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	}