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