server/random_maps/rogue_layout.C

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 *
 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
 *
 * Deliantra is free software: you can redistribute it and/or modify it under
 * the terms of the Affero GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the Affero GNU General Public License
 * and the GNU General Public License along with this program. If not, see
 * <http://www.gnu.org/licenses/>.
 *
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

/* generate a rogue/nethack-like maze */
#include <global.h>
#include <rmg.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, layout &maze);

int
surround_check (layout &maze, int i, int j)
{
  /* 1 = wall to left,
     2 = wall to right,
     4 = wall above
     8 = wall below */
  int surround_index = 0;

  if ((i >          0) && (maze[i - 1][j] != 0 && maze[i - 1][j] != '.')) surround_index |= 1;
  if ((i < maze.w - 1) && (maze[i + 1][j] != 0 && maze[i + 1][j] != '.')) surround_index |= 2;
  if ((j >          0) && (maze[i][j - 1] != 0 && maze[i][j - 1] != '.')) surround_index |= 4;
  if ((j < maze.h - 1) && (maze[i][j + 1] != 0 && maze[i][j + 1] != '.')) surround_index |= 8;

  return surround_index;
}

/* actually make the maze:  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.fill ('#');

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

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

            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 >>= 1;         /* 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; 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 R;
  Room *walk;

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