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.1.1.1 (vendor branch)
Committed:	Fri Feb 3 07:14:22 2006 UTC (18 years, 3 months ago) by root
Content type:	text/plain
Branch:	UPSTREAM
CVS Tags:	UPSTREAM_2006_03_15, LAST_C_VERSION, UPSTREAM_2006_02_22, difficulty_fix_merge_060810_2300, UPSTREAM_2006_02_03
Branch point for:	difficulty_fix
Changes since 1.1:	+0 -0 lines
Log Message:	initial import
#	User	Rev	Content
1	root	1.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			}