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 
 */
Maze
roguelike_layout_gen (int xsize, int ysize, int options)
{
  int i, j;
  Room *walk;
  int nrooms = 0;
  int tries = 0;

  Maze maze (xsize, ysize);

  for (i = 0; i < xsize; i++)
    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 = rndm (10) + 6;
  Room *rooms = salloc0<Room> (nrooms + 1);

  /* 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] = '<';

      sfree (rooms, nrooms + 1);
      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;
              }
          }
      }

  sfree (rooms, nrooms + 1);
  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 = rndm (xsize);
  ty = rndm (ysize);

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