1 /* src/server/field_of_view.c */
3 #define _POSIX_C_SOURCE 200809L /* strdup() */
4 #include "field_of_view.h"
5 #include <stdlib.h> /* free() */
6 #include <stdint.h> /* uint8_t, uint16_t, uint32_t */
7 #include <string.h> /* memset(), strchr(), strdup() */
8 #include "../common/rexit.h" /* exit_trouble() */
9 #include "../common/try_malloc.h" /* try_malloc() */
10 #include "map_objects.h" /* MapObj, MapObjDef, get_player() */
11 #include "yx_uint8.h" /* yx_uint8 */
12 #include "world.h" /* global world */
16 /* States that cells in the fov map may be in. */
17 enum fov_cell_states {
26 /* Values for mv_yx_in_dir_wrap()'s wrapping directory memory. */
35 /* Transform "yx" to an index position in the world map. */
36 static uint16_t yx_to_pos(struct yx_uint8 * yx);
38 /* Move "yx" into hex direction "d". If this moves "yx" beyond the minimal (0)
39 * or maximal (UINT8_MAX) column or row, it wraps to the opposite side. Such
40 * wrapping is returned as a wraps enum value and stored, so that further calls
41 * to move "yx" back into the opposite direction may unwrap it again. Pass an
42 * "unwrap" of UNWRAP to re-set the internal wrap memory to 0.
44 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap);
46 /* Wrapper to "mv_yx_in_dir_wrap()", returns 1 if the wrapped function moved
47 * "yx" within the wrap borders and the map size, else 0.
49 extern uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx);
51 /* Return one by one hex dir characters of walking through a circle of "radius".
52 * The circle is initialized by passing a "new_circle" of 1 and the "radius"
53 * and only returns non-null hex direction characters if "new_circle" is 0.
55 static char next_circle_dir(uint8_t new_circle, uint8_t radius_new);
57 /* Draw circle of hexes flagged LIMIT "radius" away from "yx" to "fov_map". */
58 extern void draw_border_circle(struct yx_uint8 yx, uint8_t radius,
61 /* eye_to_cell_dir_ratio() helper. */
62 static void geometry_to_char_ratio(uint8_t * n1, uint8_t * n2, uint8_t indent,
63 int16_t diff_y, int16_t diff_x,
64 uint8_t vertical, uint8_t variant);
66 /* From the chars in "available_dirs" and the geometry described by the other
67 * parameters return a string of hex direction characters representing the
68 * approximation of a straight line. "variant" marks the direction as either in
69 * the northern, north-eastern or south-western hex neighborhood if 1, or the
72 static char * eye_to_cell_dir_ratio(char * available_dirs, uint8_t indent,
73 int16_t diff_y, int16_t diff_x,
74 uint8_t vertical, uint8_t variant,
77 /* Return string approximating in one or two hex direction chars the direction
78 * that a "diff_y" and "diff_x" lead to in the internal half-indented 2D
79 * encoding of hexagonal maps, with "indent" the movement's start indentation.
81 static char * dir_from_delta(uint8_t indent, int16_t diff_y, int16_t diff_x);
83 /* Return string of hex movement direction characters describing the best
84 * possible hex approximation to a straight line from "yx_eye" to "yx_cell". If
85 * "right" is set and the string is of length two, return it with the direction
86 * strings scarcer character appearing first.
88 static char * eye_to_cell(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
91 /* Return string of hex movement direction characters describing the best
92 * possible hex approximation to a straight line from "yx_eye" to "yx_cell". If
93 * "right" is set and the string is of length two, return it with the direction
94 * strings scarcer character appearing first.
96 static char * eye_to_cell(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
99 /* fill_shadow() helper, determining if map's top left cell starts a shadow. */
100 static uint8_t is_top_left_shaded(uint16_t pos_a, uint16_t pos_b,
101 int16_t a_y_on_left);
103 /* Flag as HIDDEN all cells in "fov_map" that are enclosed by 1) the map's
104 * borders or cells flagged LIMIT and 2) the shadow arms of cells flagged
105 * SHADOW_LEFT and SHADOW_RIGHT extending from "yx_cell", as seen as left and
106 * right as seen from "yx_eye". "pos_a" and "pos_b" store the terminal positions
107 * of these arms in "fov_map" ("pos_a" for the left, "pos_b" for the right one).
109 static void fill_shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
110 uint8_t * fov_map, uint16_t pos_a, uint16_t pos_b);
112 /* Flag with "flag" cells of a path from "yx_start" to the end of the map or (if
113 * closer) the view border circle of the cells flagged as LIMIT, in a direction
114 * parallel to the one determined by walking a path from "yx_eye" to the cell
115 * reachable by moving one step into "dir" from "yx_start". If "shift_right" is
116 * set, choose among the possible paths the one whose starting cell is set most
117 * to the right, else do the opposite.
119 static uint16_t shadow_arm(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
120 uint8_t * fov_map, char dir, uint8_t flag,
121 uint8_t shift_right);
123 /* From "yx_start", draw shadow of what is invisible as seen from "yx_eye" into
124 * "fov_map" by extending shadow arms from "yx_start" as shadow borders until
125 * the edges of the map or, if smaller, the maximum viewing distance, flag these
126 * shadow arms' cells as HIDE_LATER and the area enclosed by them as HIDDEN.
127 * "dir_left" and "dir_right" are hex directions to move to from "yx_start" for
128 * cells whose shortest straight path to "yx_eye" serve as the lines of sight
129 * enclosing the shadow left and right (left and right as seen from "yx_eye").
131 static void shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
132 uint8_t * fov_map, char dir_left, char dir_right);
134 /* In "fov_map", if cell of position "yx_cell" is not HIDDEN, set it as VISIBLE,
135 * and if an obstacle to view is positioned there in the game map, flag cells
136 *behind it, unseen from "yx_eye", as HIDDEN on the interior and HIDE_LATER on
139 * The shape and width of shadows is determined by 1) calculating an approximate
140 * direction of "yx_cell" as seen from "yx_eye" as one hex movement direction,
141 * or two directly neighboring each other (i.e. "east", "east and north-east"),
142 * 2) deriving the two hex movement directions clockwise immediately preceding
143 * the first (or only) direction and immediately succeeding the second (or only)
144 * one and 3) passing the two directions thus gained as shadow arm direction
145 * calibration values to shadow() (after this function's other arguments).
147 static void set_view_of_cell_and_shadows(struct yx_uint8 * yx_cell,
148 struct yx_uint8 * yx_eye,
151 /* Return overlay of world map wherein all cell positions visible from player's
152 * positions have flag VISIBLE set.
154 * This is achieved by spiraling out clock-wise from the player position,
155 * flagging cells as VISIBLE unless they're already marked as HIDDEN, and, on
156 * running into obstacles for view that are not HIDDEN, casting shadows from
157 * these, i.e. drawing cells as HIDDEN that would be hidden by said obstacle,
158 * before continuing the original spiraling path.
160 * Shadowcasting during spiraling is initially lazy, flagging only the shadows'
161 * interior cells as HIDDEN and their border cells as HIDE_LATER. Only at the
162 * end are all cells flagged HIDE_LATER flagged as HIDDEN. This is to handle
163 * cases where obstacles to view sit right at the border of pre-estabilshed
164 * shadows, therefore might be ignored if HIDDEN and not cast shadows on their
165 * own that may slightly extend beyond the pre-established shadows they border.
167 static uint8_t * build_fov_map();
171 static uint16_t yx_to_pos(struct yx_uint8 * yx)
173 return (yx->y * world.map.size.x) + yx->x;
178 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
180 static uint8_t wrap = 0;
186 struct yx_uint8 original;
191 yx->x = yx->x + (yx->y % 2);
200 yx->x = yx->x + (yx->y % 2);
205 yx->x = yx->x - !(yx->y % 2);
214 yx->x = yx->x - !(yx->y % 2);
219 exit_trouble(1, "mv_yx_in_dir_wrap()", "illegal direction");
221 if (strchr("edc", d) && yx->x < original.x)
223 wrap = wrap & WRAP_W ? wrap ^ WRAP_W : wrap | WRAP_E;
225 else if (strchr("xsw", d) && yx->x > original.x)
227 wrap = wrap & WRAP_E ? wrap ^ WRAP_E : wrap | WRAP_W;
229 if (strchr("we", d) && yx->y > original.y)
231 wrap = wrap & WRAP_S ? wrap ^ WRAP_S : wrap | WRAP_N;
233 else if (strchr("xc", d) && yx->y < original.y)
235 wrap = wrap & WRAP_N ? wrap ^ WRAP_N : wrap | WRAP_S;
242 extern uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
244 uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
245 if (!wraptest && yx->x < world.map.size.x && yx->y < world.map.size.y)
254 static char next_circle_dir(uint8_t new_circle, uint8_t radius_new)
256 static uint8_t i_dirs = 0;
257 static uint8_t i_dist = 0;
258 static uint8_t radius = 0;
259 char * dirs = "dcxswe";
267 char ret_dir = dirs[i_dirs];
269 if (i_dist == radius)
279 extern void draw_border_circle(struct yx_uint8 yx, uint8_t radius,
283 for (dist = 1; dist <= radius; dist++)
285 mv_yx_in_dir_wrap('w', &yx, 0);
287 next_circle_dir(1, radius);
289 while ('\0' != (dir = next_circle_dir(0, 0)))
291 if (mv_yx_in_dir_legal(dir, &yx))
293 uint16_t pos = yx_to_pos(&yx);
294 fov_map[pos] = LIMIT;
297 mv_yx_in_dir_wrap(0, NULL, 1);
302 static void geometry_to_char_ratio(uint8_t * n1, uint8_t * n2, uint8_t indent,
303 int16_t diff_y, int16_t diff_x,
304 uint8_t vertical, uint8_t variant)
308 *n1 = (diff_y / 2) - diff_x + ( indent * (diff_y % 2));
309 *n2 = (diff_y / 2) + diff_x + (!indent * (diff_y % 2));
314 *n2 = diff_x - (diff_y / 2) - (indent * (diff_y % 2));
326 static char * eye_to_cell_dir_ratio(char * available_dirs, uint8_t indent,
327 int16_t diff_y, int16_t diff_x,
328 uint8_t vertical, uint8_t variant,
331 char * f_name = "eye_to_cell_dir_ratio()";
333 geometry_to_char_ratio(&n1, &n2, indent, diff_y, diff_x, vertical, variant);
334 uint8_t size_chars = n1 + n2;
335 char * dirs = try_malloc(size_chars + 1, f_name);
336 uint8_t n_strong_char = n1 / n2;
337 uint8_t more_char1 = 0 < n_strong_char;
338 n_strong_char = !more_char1 ? (n2 / n1) : n_strong_char;
340 uint8_t i_of_char = shift_right;
341 for (i = 0, i_alter = 0; i < size_chars; i++)
343 char dirchar = available_dirs[i_of_char];
344 if (more_char1 != i_of_char)
347 if (i_alter == n_strong_char)
350 i_of_char = !i_of_char;
355 i_of_char = !i_of_char;
366 static char * dir_from_delta(uint8_t indent, int16_t diff_y, int16_t diff_x)
368 int16_t double_x = 2 * diff_x;
369 int16_t indent_corrected_double_x_pos = double_x - indent + !indent;
370 int16_t indent_corrected_double_x_neg = -double_x - !indent + indent;
373 if (diff_y == double_x || diff_y == indent_corrected_double_x_pos)
377 if (diff_y == -double_x || diff_y == indent_corrected_double_x_neg)
381 if (diff_y < double_x || diff_y < indent_corrected_double_x_pos)
385 if (diff_y < -double_x || diff_y < indent_corrected_double_x_neg)
393 if (diff_y == double_x || diff_y == indent_corrected_double_x_pos)
397 if (diff_y == -double_x || diff_y == indent_corrected_double_x_neg)
401 if (diff_y > double_x || diff_y > indent_corrected_double_x_pos)
405 if (diff_y > -double_x || diff_y > indent_corrected_double_x_neg)
411 return 0 > diff_x ? "s" : "d";
416 static char * eye_to_cell(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
419 int16_t diff_y = yx_cell->y - yx_eye->y;
420 int16_t diff_x = yx_cell->x - yx_eye->x;
421 uint8_t indent = yx_eye->y % 2;
422 char * dir = dir_from_delta(indent, diff_y, diff_x);
424 if (1 == strlen(dir))
428 else if (!strcmp(dir, "dc"))
430 dirs = eye_to_cell_dir_ratio(dir, indent, diff_y, diff_x, 0,0,right);
432 else if (!strcmp(dir, "xs"))
434 dirs = eye_to_cell_dir_ratio(dir, !indent, diff_y, -diff_x, 0,1,right);
436 else if (!strcmp(dir, "cx"))
438 dirs = eye_to_cell_dir_ratio(dir, indent, diff_y, diff_x, 1,0,right);
440 else if (!strcmp(dir, "sw"))
442 dirs = eye_to_cell_dir_ratio(dir, !indent, -diff_y, -diff_x, 0,0,right);
444 else if (!strcmp(dir, "ed"))
446 dirs = eye_to_cell_dir_ratio(dir, indent, -diff_y, diff_x, 0,1,right);
448 else if (!strcmp(dir, "we"))
450 dirs = eye_to_cell_dir_ratio(dir, indent, -diff_y, diff_x, 1,1,right);
457 static uint8_t is_top_left_shaded(uint16_t pos_a, uint16_t pos_b,
460 uint16_t start_last_row = world.map.size.x * (world.map.size.y - 1);
461 uint8_t a_on_left_or_bottom = 0 <= a_y_on_left
462 || (pos_a >= start_last_row);
463 uint8_t b_on_top_or_right = pos_b < world.map.size.x
464 || pos_b % world.map.size.x==world.map.size.x-1;
465 return pos_a != pos_b && b_on_top_or_right && a_on_left_or_bottom;
470 static void fill_shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
471 uint8_t * fov_map, uint16_t pos_a, uint16_t pos_b)
473 int16_t a_y_on_left = !(pos_a%world.map.size.x)? pos_a/world.map.size.x :-1;
474 int16_t b_y_on_left = !(pos_b%world.map.size.x)? pos_b/world.map.size.x :-1;
475 uint8_t top_left_shaded = is_top_left_shaded(pos_a, pos_b, a_y_on_left);
477 uint8_t y, x, in_shade;
478 for (y = 0; y < world.map.size.y; y++)
480 in_shade = (top_left_shaded || (b_y_on_left >= 0 && y > b_y_on_left))
481 && (a_y_on_left < 0 || y < a_y_on_left);
482 for (x = 0; x < world.map.size.x; x++)
484 pos = (y * world.map.size.x) + x;
485 if (yx_eye->y == yx_cell->y && yx_eye->x < yx_cell->x)
487 uint8_t val = fov_map[pos] & (SHADOW_LEFT | SHADOW_RIGHT);
488 in_shade = 0 < val ? 1 : in_shade;
490 else if (yx_eye->y == yx_cell->y && yx_eye->x > yx_cell->x)
492 uint8_t val = fov_map[pos] & (SHADOW_LEFT | SHADOW_RIGHT);
493 in_shade = 0 < val ? 0 : in_shade;
495 else if (yx_eye->y > yx_cell->y && y <= yx_cell->y)
497 in_shade = 0 < (fov_map[pos] & SHADOW_LEFT) ? 1 : in_shade;
498 in_shade = (fov_map[pos] & SHADOW_RIGHT) ? 0 : in_shade;
500 else if (yx_eye->y < yx_cell->y && y >= yx_cell->y)
502 in_shade = 0 < (fov_map[pos] & SHADOW_RIGHT) ? 1 : in_shade;
503 in_shade = (fov_map[pos] & SHADOW_LEFT) ? 0 : in_shade;
505 if (!(fov_map[pos] & (SHADOW_LEFT | SHADOW_RIGHT))
508 fov_map[pos] = fov_map[pos] | HIDDEN;
516 static uint16_t shadow_arm(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
517 uint8_t * fov_map, char dir, uint8_t flag,
520 struct yx_uint8 yx_border = *yx_start;
522 if (mv_yx_in_dir_legal(dir, &yx_border))
524 uint8_t met_limit = 0;
526 char * dirs = eye_to_cell(yx_eye, &yx_border, shift_right);
527 yx_border = *yx_start;
528 while (!met_limit && mv_yx_in_dir_legal(dirs[i_dirs], &yx_border))
530 pos = yx_to_pos(&yx_border);
531 met_limit = fov_map[pos] & LIMIT;
532 fov_map[pos] = fov_map[pos] | flag;
533 i_dirs = dirs[i_dirs + 1] ? i_dirs + 1 : 0;
537 mv_yx_in_dir_wrap(0, NULL, 1);
543 static void shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
544 uint8_t * fov_map, char dir_left, char dir_right)
546 uint16_t pos_a, pos_b, pos_start, i;
547 pos_a = shadow_arm(yx_eye, yx_start, fov_map, dir_left, SHADOW_LEFT, 0);
548 pos_b = shadow_arm(yx_eye, yx_start, fov_map, dir_right, SHADOW_RIGHT, 1);
549 pos_start = yx_to_pos(yx_start);
550 fov_map[pos_start] = fov_map[pos_start] | SHADOW_LEFT | SHADOW_RIGHT;
551 fill_shadow(yx_eye, yx_start, fov_map, pos_a, pos_b);
552 for (i = 0; i < world.map.size.y * world.map.size.x; i++)
554 if (fov_map[i] & (SHADOW_LEFT | SHADOW_RIGHT) && i != pos_start)
556 fov_map[i] = fov_map[i] | HIDE_LATER;
558 fov_map[i] = fov_map[i] ^ (fov_map[i] & SHADOW_LEFT);
559 fov_map[i] = fov_map[i] ^ (fov_map[i] & SHADOW_RIGHT);
566 static void set_view_of_cell_and_shadows(struct yx_uint8 * yx_cell,
567 struct yx_uint8 * yx_eye,
570 char * dirs = "dcxswe";
571 uint16_t pos = yx_to_pos(yx_cell);
572 if (!(fov_map[pos] & HIDDEN))
574 fov_map[pos] = fov_map[pos] | VISIBLE;
575 if ('X' == world.map.cells[pos])
577 uint8_t last_pos = strlen(dirs) - 1;
578 int16_t diff_y = yx_cell->y - yx_eye->y;
579 int16_t diff_x = yx_cell->x - yx_eye->x;
580 uint8_t indent = yx_eye->y % 2;
581 char * dir = dir_from_delta(indent, diff_y, diff_x);
582 uint8_t start_pos = strchr(dirs, dir[0]) - dirs;
583 char prev = start_pos > 0 ? dirs[start_pos - 1] : dirs[last_pos];
584 char next = start_pos < last_pos ? dirs[start_pos + 1] : dirs[0];
587 uint8_t end_pos = strchr(dirs, dir[1]) - dirs;
588 next = end_pos < last_pos ? dirs[end_pos + 1] : dirs[0];
590 shadow(yx_eye, yx_cell, fov_map, prev, next);
597 static uint8_t * build_fov_map()
599 char * f_name = "build_fov_map()";
600 uint8_t radius = 2 * world.map.size.y;
601 uint32_t map_size = world.map.size.y * world.map.size.x;
602 struct MapObj * player = get_player();
603 struct yx_uint8 yx = player->pos;
604 uint8_t * fov_map = try_malloc(map_size, f_name);
605 memset(fov_map, 0, map_size);
606 draw_border_circle(yx, radius, fov_map);
607 fov_map[yx_to_pos(&yx)] = VISIBLE;
609 for (dist = 1; dist <= radius; dist++)
611 uint8_t first_round = 1;
613 next_circle_dir(1, dist);
614 while ('\0' != (dir = next_circle_dir(0, 0)))
616 char i_dir = first_round ? 'e' : dir;
618 if (mv_yx_in_dir_legal(i_dir, &yx))
620 set_view_of_cell_and_shadows(&yx, &player->pos, fov_map);
625 for (i = 0; i < world.map.size.y * world.map.size.x; i++)
627 if (fov_map[i] & HIDE_LATER)
629 fov_map[i] = fov_map[i] ^ (fov_map[i] & VISIBLE);
637 extern char * build_visible_map()
639 char * f_name = "build_visible_map()";
640 uint8_t * fov_map = build_fov_map();
641 uint32_t map_size = world.map.size.y * world.map.size.x;
642 char * visible_map = try_malloc(map_size, f_name);
643 memset(visible_map, ' ', map_size);
645 for (pos_i = 0; pos_i < map_size; pos_i++)
647 if (fov_map[pos_i] & VISIBLE)
649 visible_map[pos_i] = world.map.cells[pos_i];
653 struct MapObjDef * d;
656 for (i = 0; i < 2; i++)
658 for (o = world.map_objs; o != 0; o = o->next)
660 if ( fov_map[yx_to_pos(&o->pos)] & VISIBLE
661 && ( (0 == i && 0 == o->lifepoints)
662 || (1 == i && 0 < o->lifepoints)))
664 d = get_map_object_def(o->type);
666 visible_map[yx_to_pos(&o->pos)] = c;