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