1 /* src/server/field_of_view.c */
3 #include "field_of_view.h"
4 #include <stdint.h> /* uint8_t, uint16_t, uint32_t, int32_t */
5 #include <stdlib.h> /* free() */
6 #include <string.h> /* memset() */
7 #include "../common/rexit.h" /* exit_trouble() */
8 #include "../common/try_malloc.h" /* try_malloc() */
9 #include "things.h" /* Thing, ThingInMemory, add_thing_to_memory_map() */
10 #include "yx_uint8.h" /* yx_uint8 */
11 #include "world.h" /* world */
15 /* Number of degrees a circle is divided into. The greater it is, the greater
16 * the angle precision. But make it one whole zero larger and bizarre FOV bugs
17 * appear on large maps, probably due to value overflows (TODO: more research!).
19 #define CIRCLE 3600000
23 /* Angle of a shadow. */
26 struct shadow_angle * next;
33 /* Move "yx" into hex direction "d". */
34 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx);
36 /* Move "yx" into hex direction "d". If this moves "yx" beyond the minimal (0)
37 * or maximal (UINT8_MAX) column or row, it wraps to the opposite side. Such
38 * wrapping is returned as a wraps enum value and stored, so that further calls
39 * to move "yx" back into the opposite direction may unwrap it again. Pass an
40 * "unwrap" of !0 to re-set the internal wrap memory to 0.
42 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap);
44 /* Wrapper to mv_yx_in_dir_wrap(), returns 1 if the wrapped function moved "yx"
45 * within the wrap borders and the map size, else 0.
47 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx);
49 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
50 static uint32_t correct_angle(int32_t angle);
52 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
53 * it meets the shadow from the right or the left. Returns 1 on success, else 0.
55 static uint8_t try_merge(struct shadow_angle * shadow,
56 uint32_t left_angle, uint32_t right_angle);
58 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
59 * existing shadow angle in "shadows". On success, see if this leads to any
60 * additional shadow angle overlaps and merge these accordingly. Return 1 on
63 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
64 struct shadow_angle ** shadows);
66 /* Test whether angle between "left_angle" and "right_angle", or at least
67 * "middle_angle", is captured inside one of the shadow angles in "shadows". If
68 * so, set hex in "fov_map" indexed by "pos_in_map" to 'H'. If the whole angle
69 * and not just "middle_angle" is captured, return 1. Any other case: 0.
71 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
72 uint32_t middle_angle, struct shadow_angle ** shadows,
73 uint16_t pos_in_map, char * fov_map);
75 /* Free shadow angles list "angles". */
76 static void free_angles(struct shadow_angle * angles);
78 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
79 * on the circle of that distance to the origin on hex "hex_i" (as counted from
80 * the circle's rightmost point), for setting shaded hexes in "fov_map" and
81 * potentially adding a new shadow to linked shadow angle list "shadows".
83 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
84 struct yx_uint8 * test_pos,
85 struct shadow_angle ** shadows);
87 /* Update "t"'s .mem_map memory with what's in its current FOV, remove from its
88 * .t_mem all memorized things in FOV and add inanimiate things in FOV to it.
90 static void update_map_memory(struct Thing * t, uint32_t map_size);
94 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx)
98 yx->x = yx->x + (yx->y % 2);
107 yx->x = yx->x + (yx->y % 2);
112 yx->x = yx->x - !(yx->y % 2);
121 yx->x = yx->x - !(yx->y % 2);
128 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
130 static int8_t wrap_west_east = 0;
131 static int8_t wrap_north_south = 0;
134 wrap_west_east = wrap_north_south = 0;
137 struct yx_uint8 original;
140 mv_yx_in_hex_dir(d, yx);
141 if (strchr("edc", d) && yx->x < original.x)
145 else if (strchr("xsw", d) && yx->x > original.x)
149 if (strchr("we", d) && yx->y > original.y)
153 else if (strchr("xc", d) && yx->y < original.y)
157 return (wrap_west_east != 0) + (wrap_north_south != 0);
162 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
164 uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
165 if (!wraptest && yx->x < world.map.length && yx->y < world.map.length)
174 static uint32_t correct_angle(int32_t angle)
178 angle = angle + CIRCLE;
180 while (angle > CIRCLE)
182 angle = angle - CIRCLE;
189 static uint8_t try_merge(struct shadow_angle * shadow,
190 uint32_t left_angle, uint32_t right_angle)
192 if ( shadow->right_angle <= left_angle + 1
193 && shadow->right_angle >= right_angle)
195 shadow->right_angle = right_angle;
197 else if ( shadow->left_angle + 1 >= right_angle
198 && shadow->left_angle <= left_angle)
200 shadow->left_angle = left_angle;
211 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
212 struct shadow_angle ** shadows)
214 uint8_t angle_merge = 0;
215 struct shadow_angle * shadow;
216 for (shadow = *shadows; shadow; shadow = shadow->next)
218 if (try_merge(shadow, left_angle, right_angle))
225 struct shadow_angle * shadow1;
226 for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
228 struct shadow_angle * last_shadow = NULL;
229 struct shadow_angle * shadow2;
230 for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
232 if ( shadow1 != shadow2
233 && try_merge(shadow1, shadow2->left_angle,
234 shadow2->right_angle))
236 struct shadow_angle * to_free = shadow2;
239 last_shadow->next = shadow2->next;
240 shadow2 = last_shadow;
244 *shadows = shadow2->next;
249 last_shadow = shadow2;
258 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
259 uint32_t middle_angle, struct shadow_angle ** shadows,
260 uint16_t pos_in_map, char * fov_map)
262 struct shadow_angle * shadow_i;
263 if (fov_map[pos_in_map] == 'v')
265 for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
267 if ( left_angle <= shadow_i->left_angle
268 && right_angle >= shadow_i->right_angle)
270 fov_map[pos_in_map] = 'H';
273 if ( middle_angle < shadow_i->left_angle
274 && middle_angle > shadow_i->right_angle)
276 fov_map[pos_in_map] = 'H';
285 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
286 * new entry or as part of an existing shadow (swallowed whole or extending it).
288 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
289 struct shadow_angle ** shadows)
291 struct shadow_angle * shadow_i;
292 if (!try_merging_angles(left_angle, right_angle, shadows))
294 struct shadow_angle * shadow;
295 shadow = try_malloc(sizeof(struct shadow_angle), __func__);
296 shadow->left_angle = left_angle;
297 shadow->right_angle = right_angle;
301 for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
305 shadow_i->next = shadow;
316 static void free_angles(struct shadow_angle * angles)
320 free_angles(angles->next);
327 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
328 struct yx_uint8 * test_pos,
329 struct shadow_angle ** shadows)
331 int32_t left_angle_uncorrected = ((CIRCLE / 12) / dist)
332 - (hex_i * (CIRCLE / 6) / dist);
333 int32_t right_angle_uncorrected = left_angle_uncorrected
334 - (CIRCLE / (6 * dist));
335 uint32_t left_angle = correct_angle(left_angle_uncorrected);
336 uint32_t right_angle = correct_angle(right_angle_uncorrected);
337 uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
338 uint32_t middle_angle = 0;
341 middle_angle = right_angle + ((left_angle - right_angle) / 2);
343 uint16_t pos_in_map = test_pos->y * world.map.length + test_pos->x;
344 uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
345 shadows, pos_in_map, fov_map);
346 if (!all_shaded && 'X' == world.map.cells[pos_in_map])
348 set_shadow(left_angle, right_angle_1st, shadows);
349 if (right_angle_1st != right_angle)
352 set_shadow(left_angle, right_angle, shadows);
359 static void update_map_memory(struct Thing * t_eye, uint32_t map_size)
363 t_eye->mem_map = try_malloc(map_size, __func__);
364 memset(t_eye->mem_map, ' ', map_size);
367 for (i = 0; i < map_size; i++)
369 if (' ' == t_eye->mem_map[i] && t_eye->fov_map[i] == 'v')
371 t_eye->mem_map[i] = world.map.cells[i];
374 struct ThingInMemory * tm = t_eye->t_mem;
375 struct ThingInMemory * tm_prev = NULL;
376 struct ThingInMemory * tm_next = NULL;
377 for (; tm != NULL; tm = tm_next)
380 if ('v' == t_eye->fov_map[tm->pos.y * world.map.length + tm->pos.x])
384 tm_prev->next = tm->next;
388 t_eye->t_mem = tm->next;
395 struct Thing * t = world.things;
396 for (; t != NULL; t = t->next)
399 && 'v' == t_eye->fov_map[t->pos.y * world.map.length + t->pos.x])
401 add_thing_to_memory_map(t_eye, t->type, t->pos.y, t->pos.x);
408 extern void build_fov_map(struct Thing * t)
410 uint32_t map_size = world.map.length * world.map.length;
411 t->fov_map = t->fov_map ? t->fov_map : try_malloc(map_size, __func__);
412 memset(t->fov_map, 'v', map_size);
413 struct yx_uint8 test_pos = t->pos;
414 struct shadow_angle * shadows = NULL;
415 char * circle_dirs = "xswedc";
417 uint8_t first_round, circle_on_map;
418 for (first_round = 1, dist = 1, circle_on_map = 1; circle_on_map; dist++)
422 mv_yx_in_dir_legal('c', &test_pos);
425 uint8_t i_dir = first_round = circle_on_map = 0;
426 uint16_t i_dist, hex_i;
427 for (hex_i = 0, i_dist = 1; hex_i < 6 * dist; i_dist++, hex_i++)
429 if (mv_yx_in_dir_legal(dir, &test_pos))
431 eval_position(dist, hex_i, t->fov_map, &test_pos, &shadows);
434 dir = circle_dirs[i_dir];
442 mv_yx_in_dir_wrap(0, NULL, 1);
443 free_angles(shadows);
444 update_map_memory(t, map_size);