Crossfire Server, Trunk
rogue_layout.cpp
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 
41 static int rn2(int x) {
42  return RANDOM()%x;
43 }
44 
55 static int roguelike_place_room(Room *Rooms, int xsize, int ysize) {
56  const int xlim = 4;
57  const int ylim = 3;
58 
59  int tx, ty; /* trial center locations */
60  int sx, sy; /* trial sizes */
61  int ax, ay; /* min coords of rect */
62  int zx, zy; /* max coords of rect */
63  Room *walk;
64 
65  tx = RANDOM()%xsize;
66  ty = RANDOM()%ysize;
67 
68  sx = 2 + rn2(8);
69  sy = 2 + rn2(4);
70  if (sx*sy > 50) {
71  sy = 50/sx;
72  }
73 
74  /* find the corners */
75  ax = tx-sx/2;
76  zx = tx+sx/2+sx%2;
77 
78  ay = ty-sy/2;
79  zy = ty+sy/2+sy%2;
80 
81  /* check to see if it's in the map */
82  if (zx > xsize-1 || ax < 1) {
83  return 0;
84  }
85  if (zy > ysize-1 || ay < 1) {
86  return 0;
87  }
88 
89  /* no small fish */
90  if (sx < 3 || sy < 3) {
91  return 0;
92  }
93 
94  /* check overlap with existing rooms */
95  for (walk = Rooms; walk->x != 0; walk++) {
96  int dx = abs(tx-walk->x);
97  int dy = abs(ty-walk->y);
98 
99  if ((dx < (walk->sx+sx)/2+xlim) && (dy < (walk->sy+sy)/2+ylim)) {
100  return 0;
101  }
102  }
103 
104  /* if we've got here, presumably the room is OK. */
105 
106  /* get a pointer to the first free room */
107  for (walk = Rooms; walk->x != 0; walk++)
108  ;
109  walk->x = tx;
110  walk->y = ty;
111  walk->sx = sx;
112  walk->sy = sy;
113  walk->ax = ax;
114  walk->ay = ay;
115  walk->zx = zx;
116  walk->zy = zy;
117  return 1; /* success */
118 }
119 
127 static void roguelike_make_rooms(Room *Rooms, char **maze) {
128  int making_circle = RANDOM() % 2;
129  int i, j;
130  int R;
131  Room *walk;
132 
133  for (walk = Rooms; walk->x != 0; walk++) {
134  if (walk->sx < walk->sy) {
135  R = walk->sx/2;
136  } else {
137  R = walk->sy/2;
138  }
139 
140  /* enscribe a rectangle or a circle */
141  for (i = walk->ax; i < walk->zx; i++)
142  for (j = walk->ay; j < walk->zy; j++) {
143  if (!making_circle || ((int)(0.5+hypot(walk->x-i, walk->y-j))) <= R) {
144  maze[i][j] = '.';
145  }
146  }
147  }
148 }
149 
157 static void roguelike_link_rooms(Room *Rooms, char **maze) {
158  Room *walk;
159  int i, j;
160 
161  /* link each room to the previous room */
162  if (Rooms[1].x == 0) {
163  return; /* only 1 room */
164  }
165 
166  for (walk = Rooms+1; walk->x != 0; walk++) {
167  int x1 = walk->x;
168  int y1 = walk->y;
169  int x2 = (walk-1)->x;
170  int y2 = (walk-1)->y;
171  int in_wall = 0;
172 
173  if (RANDOM()%2) { /* connect in x direction first */
174  /* horizontal connect */
175  /* swap (x1,y1) (x2,y2) if necessary */
176 
177  if (x2 < x1) {
178  int tx = x2, ty = y2;
179  x2 = x1;
180  y2 = y1;
181  x1 = tx;
182  y1 = ty;
183  }
184 
185  j = y1;
186  for (i = x1; i < x2; i++) {
187  if (in_wall == 0 && maze[i][j] == '#') {
188  in_wall = 1;
189  maze[i][j] = 'D';
190  } else if (in_wall && maze[i][j] == '.') {
191  in_wall = 0;
192  maze[i-1][j] = 'D';
193  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
194  maze[i][j] = 0;
195  }
196  }
197  j = MIN(y1, y2);
198  if (maze[i][j] == '.') {
199  in_wall = 0;
200  }
201  if (maze[i][j] == 0 || maze[i][j] == '#') {
202  in_wall = 1;
203  }
204  for (/* j set already */; j < MAX(y1, y2); j++) {
205  if (in_wall == 0 && maze[i][j] == '#') {
206  in_wall = 1;
207  maze[i][j] = 'D';
208  } else if (in_wall && maze[i][j] == '.') {
209  in_wall = 0;
210  maze[i][j-1] = 'D';
211  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
212  maze[i][j] = 0;
213  }
214  }
215  } else { /* connect in y direction first */
216  in_wall = 0;
217  /* swap if necessary */
218  if (y2 < y1) {
219  int tx = x2, ty = y2;
220  x2 = x1;
221  y2 = y1;
222  x1 = tx;
223  y1 = ty;
224  }
225  i = x1;
226  /* vertical connect */
227  for (j = y1; j < y2; j++) {
228  if (in_wall == 0 && maze[i][j] == '#') {
229  in_wall = 1;
230  maze[i][j] = 'D';
231  } else if (in_wall && maze[i][j] == '.') {
232  in_wall = 0;
233  maze[i][j-1] = 'D';
234  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
235  maze[i][j] = 0;
236  }
237  }
238 
239  i = MIN(x1, x2);
240  if (maze[i][j] == '.') {
241  in_wall = 0;
242  }
243  if (maze[i][j] == 0 || maze[i][j] == '#') {
244  in_wall = 1;
245  }
246  for (/* i set already */; i < MAX(x1, x2); i++) {
247  if (in_wall == 0 && maze[i][j] == '#') {
248  in_wall = 1;
249  maze[i][j] = 'D';
250  } else if (in_wall && maze[i][j] == '.') {
251  in_wall = 0;
252  maze[i-1][j] = 'D';
253  } else if (maze[i][j] != 'D' && maze[i][j] != '.') {
254  maze[i][j] = 0;
255  }
256  }
257  }
258  }
259 }
260 
280 int surround_check(char **layout, int i, int j, int Xsize, int Ysize) {
281  int surround_index = 0;
282 
283  if ((i > 0) && (layout[i-1][j] != 0 && layout[i-1][j] != '.')) {
284  surround_index += 1;
285  }
286  if ((i < Xsize-1) && (layout[i+1][j] != 0 && layout[i+1][j] != '.')) {
287  surround_index += 2;
288  }
289  if ((j > 0) && (layout[i][j-1] != 0 && layout[i][j-1] != '.')) {
290  surround_index += 4;
291  }
292  if ((j < Ysize-1) && (layout[i][j+1] != 0 && layout[i][j+1] != '.')) {
293  surround_index += 8;
294  }
295  return surround_index;
296 }
297 
309 char **roguelike_layout_gen(int xsize, int ysize, int _unused_options, int _unused_layers) {
310  int i, j;
311  Room *Rooms = NULL;
312  Room *walk;
313  int nrooms = 0;
314  int tries = 0;
315 
316  (void)_unused_options;
317  (void)_unused_layers;
318 
319  /* allocate that array, write walls everywhere up */
320  char **maze = (char **)malloc(sizeof(char *)*xsize);
321  for (i = 0; i < xsize; i++) {
322  maze[i] = (char *)malloc(sizeof(char)*ysize);
323  for (j = 0; j < ysize; j++) {
324  maze[i][j] = '#';
325  }
326  }
327 
328  /* minimum room size is basically 5x5: if xsize/ysize is
329  less than 3x that then hollow things out, stick in
330  a stairsup and stairs down, and exit */
331 
332  if (xsize < 11 || ysize < 11) {
333  for (i = 1; i < xsize-1; i++)
334  for (j = 1; j < ysize-1; j++) {
335  maze[i][j] = 0;
336  }
337  maze[(xsize-1)/2][(ysize-1)/2] = '>';
338  maze[(xsize-1)/2][(ysize-1)/2+1] = '<';
339  return maze;
340  }
341 
342  /* decide on the number of rooms */
343  nrooms = RANDOM()%10+6;
344  Rooms = (Room *)calloc(nrooms+1, sizeof(Room));
345 
346  /* actually place the rooms */
347  i = 0;
348  while (tries < 450 && i < nrooms) {
349  /* try to place the room */
350  if (!roguelike_place_room(Rooms, xsize, ysize)) {
351  tries++;
352  } else {
353  i++;
354  }
355  }
356 
357  if (i == 0) { /* no can do! */
358  for (i = 1; i < xsize-1; i++)
359  for (j = 1; j < ysize-1; j++) {
360  maze[i][j] = 0;
361  }
362  maze[(xsize-1)/2][(ysize-1)/2] = '>';
363  maze[(xsize-1)/2][(ysize-1)/2+1] = '<';
364  free(Rooms);
365  return maze;
366  }
367 
368  /* erase the areas occupied by the rooms */
369  roguelike_make_rooms(Rooms, maze);
370 
371  roguelike_link_rooms(Rooms, maze);
372 
373  /* put in the stairs */
374 
375  maze[Rooms->x][Rooms->y] = '<';
376  /* get the last one */
377  for (walk = Rooms; walk->x != 0; walk++)
378  ;
379  /* back up one */
380  walk--;
381  if (walk == Rooms) {
382  /* In this case, there is only a single room. We don't want to
383  * clobber are up exit (above) with a down exit, so put the
384  * other exit one space up/down, depending which is a space
385  * and not a wall.
386  */
387  if (maze[walk->x][walk->y+1] == '.') {
388  maze[walk->x][walk->y+1] = '>';
389  } else {
390  maze[walk->x][walk->y-1] = '>';
391  }
392  } else {
393  maze[walk->x][walk->y] = '>';
394  }
395 
396  /* convert all the '.' to 0, we're through with the '.' */
397  for (i = 0; i < xsize; i++)
398  for (j = 0; j < ysize; j++) {
399  if (maze[i][j] == '.') {
400  maze[i][j] = 0;
401  }
402  if (maze[i][j] == 'D') { /* remove bad door. */
403  int si = surround_check(maze, i, j, xsize, ysize);
404 
405  if (si != 3 && si != 12) {
406  maze[i][j] = 0;
407  /* back up and recheck any nearby doors */
408  i = 0;
409  j = 0;
410  }
411  }
412  }
413 
414  free(Rooms);
415  return maze;
416 }
global.h
random_map.h
roguelike_make_rooms
static void roguelike_make_rooms(Room *Rooms, char **maze)
Definition: rogue_layout.cpp:127
layout
Definition: main.cpp:84
Room::ax
int ax
Definition: rogue_layout.cpp:35
diamondslots.x
x
Definition: diamondslots.py:15
MIN
#define MIN(x, y)
Definition: compat.h:21
Room::sx
int sx
Definition: rogue_layout.cpp:32
Room::sy
int sy
Definition: rogue_layout.cpp:32
Room::rtype
int rtype
Definition: rogue_layout.cpp:38
MAX
#define MAX(x, y)
Definition: compat.h:24
roguelike_place_room
static int roguelike_place_room(Room *Rooms, int xsize, int ysize)
Definition: rogue_layout.cpp:55
surround_check
int surround_check(char **layout, int i, int j, int Xsize, int Ysize)
Definition: rogue_layout.cpp:280
rn2
static int rn2(int x)
Definition: rogue_layout.cpp:41
nlohmann::detail::void
j template void())
Definition: json.hpp:4099
RANDOM
#define RANDOM()
Definition: define.h:644
Room::ay
int ay
Definition: rogue_layout.cpp:35
Room::zy
int zy
Definition: rogue_layout.cpp:35
diamondslots.y
y
Definition: diamondslots.py:16
guild_entry.x1
int x1
Definition: guild_entry.py:33
Room::zx
int zx
Definition: rogue_layout.cpp:35
Room::y
int y
Definition: rogue_layout.cpp:29
roguelike_layout_gen
char ** roguelike_layout_gen(int xsize, int ysize, int _unused_options, int _unused_layers)
Definition: rogue_layout.cpp:309
Room::x
int x
Definition: rogue_layout.cpp:29
Room
Definition: rogue_layout.cpp:27
roguelike_link_rooms
static void roguelike_link_rooms(Room *Rooms, char **maze)
Definition: rogue_layout.cpp:157
guild_entry.y1
int y1
Definition: guild_entry.py:34