Atrinik Server  4.0
los.c
Go to the documentation of this file.
1 /*************************************************************************
2  * Atrinik, a Multiplayer Online Role Playing Game *
3  * *
4  * Copyright (C) 2009-2014 Alex Tokar and Atrinik Development Team *
5  * *
6  * Fork from Crossfire (Multiplayer game for X-windows). *
7  * *
8  * This program is free software; you can redistribute it and/or modify *
9  * it under the terms of the GNU General Public License as published by *
10  * the Free Software Foundation; either version 2 of the License, or *
11  * (at your option) any later version. *
12  * *
13  * This program is distributed in the hope that it will be useful, *
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16  * GNU General Public License for more details. *
17  * *
18  * You should have received a copy of the GNU General Public License *
19  * along with this program; if not, write to the Free Software *
20  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
21  * *
22  * The author can be reached at admin@atrinik.org *
23  ************************************************************************/
24 
30 #include <global.h>
31 #include <toolkit/bresenham.h>
32 #include <player.h>
33 #include <object.h>
34 
42 #define SPACE_BLOCK 0.5
43 
44 typedef struct blstr {
45  int x[4], y[4];
46  int index;
47 } blocks;
48 
49 static blocks block[MAP_CLIENT_X][MAP_CLIENT_Y];
50 
51 static void expand_sight(object *op);
52 
63 void init_block(void)
64 {
65  int x, y, dx, dy, i;
66  static const int block_x[3] = {-1, -1, 0}, block_y[3] = {-1, 0, -1};
67 
68  for (x = 0; x < MAP_CLIENT_X; x++) {
69  for (y = 0; y < MAP_CLIENT_Y; y++) {
70  block[x][y].index = 0;
71  }
72  }
73 
74  /* The table should be symmetric, so only do the upper left
75  * quadrant - makes the processing easier. */
76  for (x = 1; x <= MAP_CLIENT_X / 2; x++) {
77  for (y = 1; y <= MAP_CLIENT_Y / 2; y++) {
78  for (i = 0; i < 3; i++) {
79  dx = x + block_x[i];
80  dy = y + block_y[i];
81 
82  /* Center space never blocks */
83  if (x == MAP_CLIENT_X / 2 && y == MAP_CLIENT_Y / 2) {
84  continue;
85  }
86 
87  /* If its a straight line, it's blocked */
88  if ((dx == x && x == MAP_CLIENT_X / 2) || (dy == y && y == MAP_CLIENT_Y / 2)) {
89  /* For simplicity, we mirror the coordinates to block the
90  * other
91  * quadrants. */
92  set_block(x, y, dx, dy);
93 
94  if (x == MAP_CLIENT_X / 2) {
95  set_block(x, MAP_CLIENT_Y - y - 1, dx, MAP_CLIENT_Y - dy - 1);
96  } else if (y == MAP_CLIENT_Y / 2) {
97  set_block(MAP_CLIENT_X - x - 1, y, MAP_CLIENT_X - dx - 1, dy);
98  }
99  } else {
100  float d1, s, l;
101 
102  /* We use the algorithm that found out how close the point
103  * (x, y) is to the line from dx, dy to the center of the
104  * viewable
105  * area. l is the distance from x, y to the line.
106  * r is more a curiosity - it lets us know what direction
107  * (left/right)
108  * the line is off */
109  d1 = (float) (pow(MAP_CLIENT_X / 2 - dx, 2) + pow(MAP_CLIENT_Y / 2 - dy, 2));
110  s = (float) ((dy - y) * (MAP_CLIENT_X / 2 - dx) - (dx - x) * (MAP_CLIENT_Y / 2 - dy)) / d1;
111  l = (float) FABS(sqrt(d1) * s);
112 
113  if (l <= SPACE_BLOCK) {
114  /* For simplicity, we mirror the coordinates to block
115  * the other
116  * quadrants. */
117  set_block(x, y, dx, dy);
118  set_block(MAP_CLIENT_X - x - 1, y, MAP_CLIENT_X - dx - 1, dy);
119  set_block(x, MAP_CLIENT_Y - y - 1, dx, MAP_CLIENT_Y - dy - 1);
120  set_block(MAP_CLIENT_X - x - 1, MAP_CLIENT_Y - y - 1, MAP_CLIENT_X - dx - 1, MAP_CLIENT_Y - dy - 1);
121  }
122  }
123  }
124  }
125  }
126 }
127 
145 void set_block(int x, int y, int bx, int by)
146 {
147  int idx = block[x][y].index, i;
148 
149  /* Due to flipping, we may get duplicates - better safe than sorry. */
150  for (i = 0; i < idx; i++) {
151  if (block[x][y].x[i] == bx && block[x][y].y[i] == by) {
152  return;
153  }
154  }
155 
156  block[x][y].x[idx] = bx;
157  block[x][y].y[idx] = by;
158  block[x][y].index++;
159 }
160 
177 static void set_wall(object *op, int x, int y)
178 {
179  int i, xt, yt;
180 
181  xt = (MAP_CLIENT_X - CONTR(op)->cs->mapx) / 2;
182  yt = (MAP_CLIENT_Y - CONTR(op)->cs->mapy) / 2;
183 
184  for (i = 0; i < block[x][y].index; i++) {
185  int dx = block[x][y].x[i], dy = block[x][y].y[i], ax, ay;
186 
187  /* ax, ay are the values as adjusted to be in the
188  * socket look structure. */
189  ax = dx - xt;
190  ay = dy - yt;
191 
192  if (ax < 0 || ax >= CONTR(op)->cs->mapx || ay < 0 || ay >= CONTR(op)->cs->mapy) {
193  continue;
194  }
195 
196  /* We need to adjust to the fact that the socket
197  * code wants the los to start from the 0, 0
198  * and not be relative to middle of los array. */
199 
200  /* This tile can't be seen */
201  if (!(CONTR(op)->blocked_los[ax][ay] & BLOCKED_LOS_OUT_OF_MAP)) {
202  CONTR(op)->blocked_los[ax][ay] |= BLOCKED_LOS_BLOCKED;
203  }
204 
205  set_wall(op, dx, dy);
206  }
207 }
208 
221 static void check_wall(object *op, int x, int y)
222 {
223  int ax, ay, flags;
224 
225  /* ax, ay are coordinates as indexed into the look window */
226  ax = x - (MAP_CLIENT_X - CONTR(op)->cs->mapx) / 2;
227  ay = y - (MAP_CLIENT_Y - CONTR(op)->cs->mapy) / 2;
228 
229  /* this skips the "edges" of view area, the border tiles.
230  * Naturally, this tiles can't block any view - there is
231  * nothing behind them. */
232  if (!block[x][y].index) {
233  /* to handle the "blocksview update" right, we give this special
234  * tiles a "never use it to trigger a los_update()" flag.
235  * blockview changes to this tiles will have no effect. */
236 
237  /* mark the space as OUT_OF_MAP. */
238  if (blocks_view(op->map, op->x + x - MAP_CLIENT_X / 2, op->y + y - MAP_CLIENT_Y / 2) & P_OUT_OF_MAP) {
239  CONTR(op)->blocked_los[ax][ay] = BLOCKED_LOS_OUT_OF_MAP;
240  } else {
241  /* ignore means ignore for LOS */
242  CONTR(op)->blocked_los[ax][ay] |= BLOCKED_LOS_IGNORE;
243  }
244 
245  return;
246  }
247 
248 
249  /* If the converted coordinates are outside the viewable
250  * area for the client, return now. */
251  if (ax < 0 || ay < 0 || ax >= CONTR(op)->cs->mapx || ay >= CONTR(op)->cs->mapy) {
252  return;
253  }
254 
255  /* If this space is already blocked, prune the processing - presumably
256  * whatever has set this space to be blocked has done the work and already
257  * done the dependency chain.
258  * but check for get_map_from_coord to speedup our client map draw function.
259  * */
260  if (CONTR(op)->blocked_los[ax][ay] & (BLOCKED_LOS_BLOCKED | BLOCKED_LOS_OUT_OF_MAP)) {
261  if (CONTR(op)->blocked_los[ax][ay] & BLOCKED_LOS_BLOCKED) {
262  if ((flags = blocks_view(op->map, op->x + x - MAP_CLIENT_X / 2, op->y + y - MAP_CLIENT_Y / 2))) {
263  /* mark the space as OUT_OF_MAP. */
264  if (flags & P_OUT_OF_MAP) {
265  CONTR(op)->blocked_los[ax][ay] = BLOCKED_LOS_OUT_OF_MAP;
266  } else {
267  CONTR(op)->blocked_los[ax][ay] |= BLOCKED_LOS_BLOCKSVIEW;
268  }
269  }
270  }
271  return;
272  }
273 
274  if ((flags = blocks_view(op->map, op->x + x - MAP_CLIENT_X / 2, op->y + y - MAP_CLIENT_Y / 2))) {
275  set_wall(op, x, y);
276 
277  /* out of map clears all other flags! */
278 
279  /* Mark the space as OUT_OF_MAP. */
280  if (flags & P_OUT_OF_MAP) {
281  CONTR(op)->blocked_los[ax][ay] = BLOCKED_LOS_OUT_OF_MAP;
282  } else {
283  CONTR(op)->blocked_los[ax][ay] |= BLOCKED_LOS_BLOCKSVIEW;
284  }
285  }
286 }
287 
295 static void blinded_sight(object *op)
296 {
297  int x, y;
298 
299  for (x = 0; x < CONTR(op)->cs->mapx; x++) {
300  for (y = 0; y < CONTR(op)->cs->mapy; y++) {
301  CONTR(op)->blocked_los[x][y] |= BLOCKED_LOS_BLOCKED;
302  }
303  }
304 
305  CONTR(op)->blocked_los[CONTR(op)->cs->mapx / 2][CONTR(op)->cs->mapy / 2] &= ~BLOCKED_LOS_BLOCKED;
306 }
307 
314 void update_los(object *op)
315 {
316  int dx = CONTR(op)->cs->mapx_2, dy = CONTR(op)->cs->mapy_2, x, y;
317 
318  if (QUERY_FLAG(op, FLAG_REMOVED)) {
319  return;
320  }
321 
322  clear_los(op);
323 
324  if (CONTR(op)->tls) {
325  return;
326  }
327 
328  /* For larger maps, this is more efficient than the old way which
329  * used the chaining of the block array. Since many space views could
330  * be blocked by different spaces in front, this mean that a lot of spaces
331  * could be examined multile times, as each path would be looked at. */
332  for (x = (MAP_CLIENT_X - CONTR(op)->cs->mapx) / 2; x < (MAP_CLIENT_X + CONTR(op)->cs->mapx) / 2; x++) {
333  for (y = (MAP_CLIENT_Y - CONTR(op)->cs->mapy) / 2; y < (MAP_CLIENT_Y + CONTR(op)->cs->mapy) / 2; y++) {
334  check_wall(op, x, y);
335  }
336  }
337 
338  if (QUERY_FLAG(op, FLAG_BLIND)) {
339  blinded_sight(op);
340  } else {
341  expand_sight(op);
342 
343  /* Give us an area we can look through when we have xray - this
344  * stacks to normal LOS. */
345  if (QUERY_FLAG(op, FLAG_XRAYS)) {
346  for (x = -3; x <= 3; x++) {
347  for (y = -3; y <= 3; y++) {
348  if (CONTR(op)->blocked_los[dx + x][dy + y] & BLOCKED_LOS_BLOCKED) {
349  CONTR(op)->blocked_los[dx + x][dy + y] &= ~BLOCKED_LOS_BLOCKED;
350  }
351  }
352  }
353  }
354  }
355 }
356 
363 void clear_los(object *op)
364 {
365  (void) memset(CONTR(op)->blocked_los, BLOCKED_LOS_VISIBLE, sizeof(CONTR(op)->blocked_los));
366 }
367 
368 #define BLOCKED_LOS_EXPAND 0x20
369 
380 static void expand_sight(object *op)
381 {
382  int i, x, y, dx, dy;
383 
384  /* loop over inner squares */
385  for (x = 1; x < CONTR(op)->cs->mapx - 1; x++) {
386  for (y = 1; y < CONTR(op)->cs->mapy - 1; y++) {
387  /* if visible and not blocksview */
388  if (CONTR(op)->blocked_los[x][y] <= BLOCKED_LOS_BLOCKSVIEW && !(CONTR(op)->blocked_los[x][y] & BLOCKED_LOS_BLOCKSVIEW)) {
389  /* mark all directions */
390  for (i = 1; i <= 8; i += 1) {
391  dx = x + freearr_x[i];
392  dy = y + freearr_y[i];
393 
394  if (dx < 0 || dy < 0 || dx > CONTR(op)->cs->mapx || dy > CONTR(op)->cs->mapy) {
395  continue;
396  }
397 
398  if (CONTR(op)->blocked_los[dx][dy] & BLOCKED_LOS_BLOCKED) {
399  CONTR(op)->blocked_los[dx][dy] |= BLOCKED_LOS_EXPAND;
400  }
401  }
402  }
403  }
404  }
405 
406  for (x = 0; x < CONTR(op)->cs->mapx; x++) {
407  for (y = 0; y < CONTR(op)->cs->mapy; y++) {
408  if (CONTR(op)->blocked_los[x][y] & BLOCKED_LOS_EXPAND) {
409  CONTR(op)->blocked_los[x][y] &= ~(BLOCKED_LOS_BLOCKED | BLOCKED_LOS_EXPAND);
410  }
411  }
412  }
413 }
414 
428 {
429  /* Bresenham variables */
430  int fraction, dx2, dy2, stepx, stepy;
431  /* Stepping variables */
432  mapstruct *m = rv->part->map;
433  int x = rv->part->x, y = rv->part->y;
434 
435  BRESENHAM_INIT(rv->distance_x, rv->distance_y, fraction, stepx, stepy, dx2, dy2);
436 
437  while (1) {
438  if (x == obj->x && y == obj->y && m == obj->map) {
439  return 1;
440  }
441 
442  if (m == NULL || GET_MAP_FLAGS(m, x, y) & P_BLOCKSVIEW) {
443  return 0;
444  }
445 
446  BRESENHAM_STEP(x, y, fraction, stepx, stepy, dx2, dy2);
447 
448  m = get_map_from_coord(m, &x, &y);
449  }
450 }
#define BLOCKED_LOS_BLOCKED
Definition: define.h:95
Definition: object.h:94
static void blinded_sight(object *op)
Definition: los.c:295
void init_block(void)
Definition: los.c:63
int blocks_view(mapstruct *m, int x, int y)
Definition: map.c:507
#define BLOCKED_LOS_BLOCKSVIEW
Definition: define.h:93
mapstruct * get_map_from_coord(mapstruct *m, int *x, int *y)
Definition: map.c:1869
int distance_x
Definition: map.h:778
static void expand_sight(object *op)
Definition: los.c:380
#define FLAG_BLIND
Definition: define.h:884
#define P_OUT_OF_MAP
Definition: map.h:305
int obj_in_line_of_sight(object *obj, rv_vector *rv)
Definition: los.c:427
static void check_wall(object *op, int x, int y)
Definition: los.c:221
#define QUERY_FLAG(xyz, p)
Definition: define.h:761
int distance_y
Definition: map.h:781
Definition: los.c:44
#define P_BLOCKSVIEW
Definition: map.h:250
int16_t y
Definition: object.h:276
#define BLOCKED_LOS_IGNORE
Definition: define.h:91
#define BLOCKED_LOS_VISIBLE
Definition: define.h:89
struct mapdef * map
Definition: object.h:139
static void set_wall(object *op, int x, int y)
Definition: los.c:177
#define SPACE_BLOCK
Definition: los.c:42
void clear_los(object *op)
Definition: los.c:363
int16_t x
Definition: object.h:273
#define FLAG_REMOVED
Definition: define.h:930
#define MAP_CLIENT_X
Definition: config.h:62
void set_block(int x, int y, int bx, int by)
Definition: los.c:145
#define FLAG_XRAYS
Definition: define.h:1110
int freearr_x[SIZEOFFREE]
Definition: object.c:84
object * part
Definition: map.h:790
void update_los(object *op)
Definition: los.c:314
#define BLOCKED_LOS_OUT_OF_MAP
Definition: define.h:97
Definition: map.h:536
int freearr_y[SIZEOFFREE]
Definition: object.c:99