server/random_maps/rogue_layout.C

/* generate a rogue/nethack-like layout */
#include <global.h>
#include <random_map.h>
#include <rproto.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 
 */
void
roguelike_layout_gen (Layout maze, int options)
{
  int i, j;
  Room *walk;
  int nrooms = 0;
  int tries = 0;

  int xsize = maze->w;
  int ysize = maze->h;

  /* 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)
    {
      maze->clear ();
      maze->border ();

      maze[(xsize - 1) / 2][(ysize - 1) / 2    ] = '>';
      maze[(xsize - 1) / 2][(ysize - 1) / 2 + 1] = '<';

      return;
    }

  maze->clear ('#');

  /* decide on the number of rooms */
  nrooms = rmg_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! */
    {
      maze->clear ();
      maze->border ();

      maze [(xsize - 1) / 2][(ysize - 1) / 2    ] = '>';
      maze [(xsize - 1) / 2][(ysize - 1) / 2 + 1] = '<';

      sfree (rooms, nrooms + 1);
      return;
    }

  /* 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);
}

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 = rmg_rndm (xsize);
  ty = rmg_rndm (ysize);

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