Crossfire Server, Trunk
rogue_layout.c
Go to the documentation of this file.
1 /*
2  * Crossfire -- cooperative multi-player graphical RPG and adventure game
3  *
4  * Copyright (c) 1999-2013 Mark Wedel and the Crossfire Development Team
5  * Copyright (c) 1992 Frank Tore Johansen
6  *
7  * Crossfire is free software and comes with ABSOLUTELY NO WARRANTY. You are
8  * welcome to redistribute it under certain conditions. For details, please
9  * see COPYING and LICENSE.
10  *
11  * The authors can be reached via e-mail at <crossfire@metalforge.org>.
12  */
13 
19 #include "global.h"
20 
21 #include <assert.h>
22 #include <math.h>
23 #include <stdlib.h>
24 
25 #include "random_map.h"
26 
27 typedef struct {
29  int x, y;
30 
32  int sx, sy;
33 
35  int ax, ay, zx, zy;
36 
37  /* Room type (circular or rectangular) */
38  int rtype;
39 } Room;
40 
53 static int roguelike_place_room(Room *Rooms, int xsize, int ysize, int nrooms) {
54  int tx, ty; /* trial center locations */
55  int sx, sy; /* trial sizes */
56  int ax, ay; /* min coords of rect */
57  int zx, zy; /* max coords of rect */
58  int x_basesize;
59  int y_basesize;
60  Room *walk;
61 
62  int nrooms_sqrt = isqrt(nrooms);
63  assert(nrooms_sqrt != 0);
64 
65  /* decide on the base x and y sizes */
66  x_basesize = xsize / nrooms_sqrt;
67  y_basesize = ysize / nrooms_sqrt;
68 
69  tx = RANDOM()%xsize;
70  ty = RANDOM()%ysize;
71 
72  /* generate a distribution of sizes centered about basesize */
73  sx = (RANDOM()%x_basesize)+(RANDOM()%x_basesize)+(RANDOM()%x_basesize);
74  sy = (RANDOM()%y_basesize)+(RANDOM()%y_basesize)+(RANDOM()%y_basesize);
75  sy = (int)(sy*.5); /* renormalize */
76 
77  /* find the corners */
78  ax = tx-sx/2;
79  zx = tx+sx/2+sx%2;
80 
81  ay = ty-sy/2;
82  zy = ty+sy/2+sy%2;
83 
84  /* check to see if it's in the map */
85  if (zx > xsize-1 || ax < 1) {
86  return 0;
87  }
88  if (zy > ysize-1 || ay < 1) {
89  return 0;
90  }
91 
92  /* no small fish */
93  if (sx < 3 || sy < 3) {
94  return 0;
95  }
96 
97  /* check overlap with existing rooms */
98  for (walk = Rooms; walk->x != 0; walk++) {
99  int dx = abs(tx-walk->x);
100  int dy = abs(ty-walk->y);
101 
102  if ((dx < (walk->sx+sx)/2+2) && (dy < (walk->sy+sy)/2+2)) {
103  return 0;
104  }
105  }
106 
107  /* if we've got here, presumably the room is OK. */
108 
109  /* get a pointer to the first free room */
110  for (walk = Rooms; walk->x != 0; walk++)
111  ;
112  walk->x = tx;
113  walk->y = ty;
114  walk->sx = sx;
115  walk->sy = sy;
116  walk->ax = ax;
117  walk->ay = ay;
118  walk->zx = zx;
119  walk->zy = zy;
120  return 1; /* success */
121 }
122 
132 static void roguelike_make_rooms(Room *Rooms, char **maze, int options) {
133  int making_circle = 0;
134  int i, j;
135  int R;
136  Room *walk;
137 
138  for (walk = Rooms; walk->x != 0; walk++) {
139  /* first decide what shape to make */
140  switch (options) {
141  case 1:
142  making_circle = 0;
143  break;
144 
145  case 2:
146  making_circle = 1;
147  break;
148 
149  default:
150  making_circle = ((RANDOM()%3 == 0) ? 1 : 0);
151  break;
152  }
153 
154  if (walk->sx < walk->sy) {
155  R = walk->sx/2;
156  } else {
157  R = walk->sy/2;
158  }
159 
160  /* enscribe a rectangle or a circle */
161  for (i = walk->ax; i < walk->zx; i++)
162  for (j = walk->ay; j < walk->zy; j++) {
163  if (!making_circle || ((int)(0.5+hypot(walk->x-i, walk->y-j))) <= R) {
164  maze[i][j] = '.';
165  }
166  }
167  }
168 }
169 
177 static void roguelike_link_rooms(Room *Rooms, char **maze) {
178  Room *walk;
179  int i, j;
180 
181  /* link each room to the previous room */
182  if (Rooms[1].x == 0) {
183  return; /* only 1 room */
184  }
185 
186  for (walk = Rooms+1; walk->x != 0; walk++) {
187  int x1 = walk->x;
188  int y1 = walk->y;
189  int x2 = (walk-1)->x;
190  int y2 = (walk-1)->y;
191  int in_wall = 0;
192 
193  if (RANDOM()%2) { /* connect in x direction first */
194  /* horizontal connect */
195  /* swap (x1,y1) (x2,y2) if necessary */
196 
197  if (x2 < x1) {
198  int tx = x2, ty = y2;
199  x2 = x1;
200  y2 = y1;
201  x1 = tx;
202  y1 = ty;
203  }
204 
205  j = y1;
206  for (i = x1; i < x2; i++) {
207  if (in_wall == 0 && maze[i][j] == '#') {
208  in_wall = 1;
209  maze[i][j] = 'D';
210  } else if (in_wall && maze[i][j] == '.') {
211  in_wall = 0;
212  maze[i-1][j] = 'D';
213  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
214  maze[i][j] = 0;
215  }
216  }
217  j = MIN(y1, y2);
218  if (maze[i][j] == '.') {
219  in_wall = 0;
220  }
221  if (maze[i][j] == 0 || maze[i][j] == '#') {
222  in_wall = 1;
223  }
224  for (/* j set already */; j < MAX(y1, y2); j++) {
225  if (in_wall == 0 && maze[i][j] == '#') {
226  in_wall = 1;
227  maze[i][j] = 'D';
228  } else if (in_wall && maze[i][j] == '.') {
229  in_wall = 0;
230  maze[i][j-1] = 'D';
231  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
232  maze[i][j] = 0;
233  }
234  }
235  } else { /* connect in y direction first */
236  in_wall = 0;
237  /* swap if necessary */
238  if (y2 < y1) {
239  int tx = x2, ty = y2;
240  x2 = x1;
241  y2 = y1;
242  x1 = tx;
243  y1 = ty;
244  }
245  i = x1;
246  /* vertical connect */
247  for (j = y1; j < y2; j++) {
248  if (in_wall == 0 && maze[i][j] == '#') {
249  in_wall = 1;
250  maze[i][j] = 'D';
251  } else if (in_wall && maze[i][j] == '.') {
252  in_wall = 0;
253  maze[i][j-1] = 'D';
254  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
255  maze[i][j] = 0;
256  }
257  }
258 
259  i = MIN(x1, x2);
260  if (maze[i][j] == '.') {
261  in_wall = 0;
262  }
263  if (maze[i][j] == 0 || maze[i][j] == '#') {
264  in_wall = 1;
265  }
266  for (/* i set already */; i < MAX(x1, x2); i++) {
267  if (in_wall == 0 && maze[i][j] == '#') {
268  in_wall = 1;
269  maze[i][j] = 'D';
270  } else if (in_wall && maze[i][j] == '.') {
271  in_wall = 0;
272  maze[i-1][j] = 'D';
273  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
274  maze[i][j] = 0;
275  }
276  }
277  }
278  }
279 }
280 
300 int surround_check(char **layout, int i, int j, int Xsize, int Ysize) {
301  int surround_index = 0;
302 
303  if ((i > 0) && (layout[i-1][j] != 0 && layout[i-1][j] != '.')) {
304  surround_index += 1;
305  }
306  if ((i < Xsize-1) && (layout[i+1][j] != 0 && layout[i+1][j] != '.')) {
307  surround_index += 2;
308  }
309  if ((j > 0) && (layout[i][j-1] != 0 && layout[i][j-1] != '.')) {
310  surround_index += 4;
311  }
312  if ((j < Ysize-1) && (layout[i][j+1] != 0 && layout[i][j+1] != '.')) {
313  surround_index += 8;
314  }
315  return surround_index;
316 }
317 
329 char **roguelike_layout_gen(int xsize, int ysize, int options, int _unused_layers) {
330  int i, j;
331  Room *Rooms = NULL;
332  Room *walk;
333  int nrooms = 0;
334  int tries = 0;
335 
336  (void)_unused_layers;
337 
338  /* allocate that array, write walls everywhere up */
339  char **maze = (char **)malloc(sizeof(char *)*xsize);
340  for (i = 0; i < xsize; i++) {
341  maze[i] = (char *)malloc(sizeof(char)*ysize);
342  for (j = 0; j < ysize; j++) {
343  maze[i][j] = '#';
344  }
345  }
346 
347  /* minimum room size is basically 5x5: if xsize/ysize is
348  less than 3x that then hollow things out, stick in
349  a stairsup and stairs down, and exit */
350 
351  if (xsize < 11 || ysize < 11) {
352  for (i = 1; i < xsize-1; i++)
353  for (j = 1; j < ysize-1; j++) {
354  maze[i][j] = 0;
355  }
356  maze[(xsize-1)/2][(ysize-1)/2] = '>';
357  maze[(xsize-1)/2][(ysize-1)/2+1] = '<';
358  return maze;
359  }
360 
361  /* decide on the number of rooms */
362  nrooms = RANDOM()%10+6;
363  Rooms = (Room *)calloc(nrooms+1, sizeof(Room));
364 
365  /* actually place the rooms */
366  i = 0;
367  while (tries < 450 && i < nrooms) {
368  /* try to place the room */
369  if (!roguelike_place_room(Rooms, xsize, ysize, nrooms)) {
370  tries++;
371  } else {
372  i++;
373  }
374  }
375 
376  if (i == 0) { /* no can do! */
377  for (i = 1; i < xsize-1; i++)
378  for (j = 1; j < ysize-1; j++) {
379  maze[i][j] = 0;
380  }
381  maze[(xsize-1)/2][(ysize-1)/2] = '>';
382  maze[(xsize-1)/2][(ysize-1)/2+1] = '<';
383  free(Rooms);
384  return maze;
385  }
386 
387  /* erase the areas occupied by the rooms */
388  roguelike_make_rooms(Rooms, maze, options);
389 
390  roguelike_link_rooms(Rooms, maze);
391 
392  /* put in the stairs */
393 
394  maze[Rooms->x][Rooms->y] = '<';
395  /* get the last one */
396  for (walk = Rooms; walk->x != 0; walk++)
397  ;
398  /* back up one */
399  walk--;
400  if (walk == Rooms) {
401  /* In this case, there is only a single room. We don't want to
402  * clobber are up exit (above) with a down exit, so put the
403  * other exit one space up/down, depending which is a space
404  * and not a wall.
405  */
406  if (maze[walk->x][walk->y+1] == '.') {
407  maze[walk->x][walk->y+1] = '>';
408  } else {
409  maze[walk->x][walk->y-1] = '>';
410  }
411  } else {
412  maze[walk->x][walk->y] = '>';
413  }
414 
415  /* convert all the '.' to 0, we're through with the '.' */
416  for (i = 0; i < xsize; i++)
417  for (j = 0; j < ysize; j++) {
418  if (maze[i][j] == '.') {
419  maze[i][j] = 0;
420  }
421  if (maze[i][j] == 'D') { /* remove bad door. */
422  int si = surround_check(maze, i, j, xsize, ysize);
423 
424  if (si != 3 && si != 12) {
425  maze[i][j] = 0;
426  /* back up and recheck any nearby doors */
427  i = 0;
428  j = 0;
429  }
430  }
431  }
432 
433  free(Rooms);
434  return maze;
435 }
global.h
random_map.h
layout
Definition: main.c:85
Room::ax
int ax
Definition: rogue_layout.c:35
diamondslots.x
x
Definition: diamondslots.py:15
MIN
#define MIN(x, y)
Definition: compat.h:21
Room::sx
int sx
Definition: rogue_layout.c:32
Room::sy
int sy
Definition: rogue_layout.c:32
Room::rtype
int rtype
Definition: rogue_layout.c:38
roguelike_place_room
static int roguelike_place_room(Room *Rooms, int xsize, int ysize, int nrooms)
Definition: rogue_layout.c:53
isqrt
int isqrt(int n)
Definition: utils.c:586
MAX
#define MAX(x, y)
Definition: compat.h:24
roguelike_link_rooms
static void roguelike_link_rooms(Room *Rooms, char **maze)
Definition: rogue_layout.c:177
roguelike_make_rooms
static void roguelike_make_rooms(Room *Rooms, char **maze, int options)
Definition: rogue_layout.c:132
roguelike_layout_gen
char ** roguelike_layout_gen(int xsize, int ysize, int options, int _unused_layers)
Definition: rogue_layout.c:329
nlohmann::detail::void
j template void())
Definition: json.hpp:4099
RANDOM
#define RANDOM()
Definition: define.h:642
Room::ay
int ay
Definition: rogue_layout.c:35
Room::zy
int zy
Definition: rogue_layout.c:35
options
static struct Command_Line_Options options[]
Definition: init.c:379
diamondslots.y
y
Definition: diamondslots.py:16
guild_entry.x1
int x1
Definition: guild_entry.py:33
Room::zx
int zx
Definition: rogue_layout.c:35
make_face_from_files.int
int
Definition: make_face_from_files.py:26
Room::y
int y
Definition: rogue_layout.c:29
Room::x
int x
Definition: rogue_layout.c:29
Room
Definition: rogue_layout.c:27
surround_check
int surround_check(char **layout, int i, int j, int Xsize, int Ysize)
Definition: rogue_layout.c:300
guild_entry.y1
int y1
Definition: guild_entry.py:34