home · contact · privacy
Server: Internally, rename "map object" stuff to "thing" stuff.
[plomrogue] / src / server / field_of_view.c
1 /* src/server/field_of_view.c */
2
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.h" /* yx_to_map_pos() */
11 #include "things.h" /* Thing */
12 #include "yx_uint8.h" /* yx_uint8 */
13 #include "world.h" /* global world  */
14
15
16
17 /* Values for mv_yx_in_dir_wrap()'s wrapping directory memory. */
18 enum wraps
19 {
20     WRAP_N = 0x01,
21     WRAP_S = 0x02,
22     WRAP_E = 0x04,
23     WRAP_W = 0x08
24 };
25
26 /* Move "yx" into hex direction "d". If this moves "yx" beyond the minimal (0)
27  * or maximal (UINT8_MAX) column or row, it wraps to the opposite side. Such
28  * wrapping is returned as a wraps enum value and stored, so that further calls
29  * to move "yx" back into the opposite direction may unwrap it again. Pass an
30  * "unwrap" of UNWRAP to re-set the internal wrap memory to 0.
31  */
32 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap);
33
34 /* Wrapper to "mv_yx_in_dir_wrap()", returns 1 if the wrapped function moved
35  * "yx" within the wrap borders and the map size, else 0.
36  */
37 extern uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx);
38
39 /* Return one by one hex dir characters of walking through a circle of "radius".
40  * The circle is initialized by passing a "new_circle" of 1 and the "radius"
41  * and only returns non-null hex direction characters if "new_circle" is 0.
42  */
43 static char next_circle_dir(uint8_t new_circle, uint8_t radius_new);
44
45 /* Draw circle of hexes flagged LIMIT "radius" away from "yx" to "fov_map". */
46 extern void draw_border_circle(struct yx_uint8 yx, uint8_t radius,
47                                uint8_t * fov_map);
48
49 /* eye_to_cell_dir_ratio() helper. */
50 static void geometry_to_char_ratio(uint8_t * n1, uint8_t * n2, uint8_t indent,
51                                    int16_t diff_y, int16_t diff_x,
52                                    uint8_t vertical, uint8_t variant);
53
54 /* From the chars in "available_dirs" and the geometry described by the other
55  * parameters return a string of hex direction characters representing the
56  * approximation of a straight line. "variant" marks the direction as either in
57  * the northern, north-eastern or south-western hex neighborhood if 1, or the
58  * others if 0.
59  */
60 static char * eye_to_cell_dir_ratio(char * available_dirs, uint8_t indent,
61                                     int16_t diff_y, int16_t diff_x,
62                                     uint8_t vertical, uint8_t variant,
63                                     uint8_t shift_right);
64
65 /* Return string approximating in one or two hex direction chars the direction
66  * that a "diff_y" and "diff_x" lead to in the internal half-indented 2D
67  * encoding of hexagonal maps, with "indent" the movement's start indentation.
68  */
69 static char * dir_from_delta(uint8_t indent, int16_t diff_y, int16_t diff_x);
70
71 /* Return string of hex movement direction characters describing the best
72  * possible hex approximation to a straight line from "yx_eye" to "yx_cell". If
73  * "right" is set and the string is of length two, return it with the direction
74  * strings scarcer character appearing first.
75  */
76 static char * eye_to_cell(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
77                           uint8_t right);
78
79 /* Return string of hex movement direction characters describing the best
80  * possible hex approximation to a straight line from "yx_eye" to "yx_cell". If
81  * "right" is set and the string is of length two, return it with the direction
82  * strings scarcer character appearing first.
83  */
84 static char * eye_to_cell(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
85                           uint8_t right);
86
87 /* fill_shadow() helper, determining if map's top left cell starts a shadow. */
88 static uint8_t is_top_left_shaded(uint16_t pos_a, uint16_t pos_b,
89                                   int16_t a_y_on_left);
90
91 /* Flag as HIDDEN all cells in "fov_map" that are enclosed by 1) the map's
92  * borders or cells flagged LIMIT and 2) the shadow arms of cells flagged
93  * SHADOW_LEFT and SHADOW_RIGHT extending from "yx_cell", as seen as left and
94  * right as seen from "yx_eye". "pos_a" and "pos_b" store the terminal positions
95  * of these arms in "fov_map" ("pos_a" for the left, "pos_b" for the right one).
96  */
97 static void fill_shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
98                         uint8_t * fov_map, uint16_t pos_a, uint16_t pos_b);
99
100 /* Flag with "flag" cells of a path from "yx_start" to the end of the map or (if
101  * closer) the view border circle of the cells flagged as LIMIT, in a direction
102  * parallel to the one determined by walking a path from "yx_eye" to the cell
103  * reachable by moving one step into "dir" from "yx_start". If "shift_right" is
104  * set, choose among the possible paths the one whose starting cell is set most
105  * to the right, else do the opposite.
106  */
107 static uint16_t shadow_arm(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
108                            uint8_t * fov_map, char dir, uint8_t flag,
109                            uint8_t shift_right);
110
111 /* From "yx_start", draw shadow of what is invisible as seen from "yx_eye" into
112  * "fov_map" by extending shadow arms from "yx_start" as shadow borders until
113  * the edges of the map or, if smaller, the maximum viewing distance, flag these
114  * shadow arms' cells as HIDE_LATER and the area enclosed by them as HIDDEN.
115  * "dir_left" and "dir_right" are hex directions to move to from "yx_start" for
116  * cells whose shortest straight path to "yx_eye" serve as the lines of sight
117  * enclosing the shadow left and right (left and right as seen from "yx_eye").
118  */
119 static void shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
120                    uint8_t * fov_map, char dir_left, char dir_right);
121
122 /* In "fov_map", if cell of position "yx_cell" is not HIDDEN, set it as VISIBLE,
123  * and if an obstacle to view is positioned there in the game map, flag cells
124  *behind it, unseen from "yx_eye", as HIDDEN on the interior and HIDE_LATER on
125  * their borders.
126  *
127  * The shape and width of shadows is determined by 1) calculating an approximate
128  * direction of "yx_cell" as seen from "yx_eye" as one hex movement direction,
129  * or two directly neighboring each other (i.e. "east", "east and north-east"),
130  * 2) deriving the two hex movement directions clockwise immediately preceding
131  * the first (or only) direction and immediately succeeding the second (or only)
132  * one and 3) passing the two directions thus gained as shadow arm direction
133  * calibration values to shadow() (after this function's other arguments).
134  */
135 static void set_view_of_cell_and_shadows(struct yx_uint8 * yx_cell,
136                                          struct yx_uint8 * yx_eye,
137                                          uint8_t * fov_map);
138
139
140
141 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
142 {
143     static uint8_t wrap = 0;
144     if (unwrap)
145     {
146         wrap = 0;
147         return 0;
148     }
149     struct yx_uint8 original;
150     original.y = yx->y;
151     original.x = yx->x;
152     if     (d == 'e')
153     {
154         yx->x = yx->x + (yx->y % 2);
155         yx->y--;
156     }
157     else if (d == 'd')
158     {
159         yx->x++;
160     }
161     else if (d == 'c')
162     {
163         yx->x = yx->x + (yx->y % 2);
164         yx->y++;
165     }
166     else if (d == 'x')
167     {
168         yx->x = yx->x - !(yx->y % 2);
169         yx->y++;
170     }
171     else if (d == 's')
172     {
173         yx->x--;
174     }
175     else if (d == 'w')
176     {
177         yx->x = yx->x - !(yx->y % 2);
178         yx->y--;
179     }
180     else
181     {
182         exit_trouble(1, "mv_yx_in_dir_wrap()", "illegal direction");
183     }
184     if      (strchr("edc", d) && yx->x < original.x)
185     {
186         wrap = wrap & WRAP_W ? wrap ^ WRAP_W : wrap | WRAP_E;
187     }
188     else if (strchr("xsw", d) && yx->x > original.x)
189     {
190         wrap = wrap & WRAP_E ? wrap ^ WRAP_E : wrap | WRAP_W;
191     }
192     if      (strchr("we", d) && yx->y > original.y)
193     {
194         wrap = wrap & WRAP_S ? wrap ^ WRAP_S : wrap | WRAP_N;
195     }
196     else if (strchr("xc", d) && yx->y < original.y)
197     {
198         wrap = wrap & WRAP_N ? wrap ^ WRAP_N : wrap | WRAP_S;
199     }
200     return wrap;
201 }
202
203
204
205 extern uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
206 {
207     uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
208     if (!wraptest && yx->x < world.map.length && yx->y < world.map.length)
209     {
210         return 1;
211     }
212     return 0;
213 }
214
215
216
217 static char next_circle_dir(uint8_t new_circle, uint8_t radius_new)
218 {
219     static uint8_t i_dirs = 0;
220     static uint8_t i_dist = 0;
221     static uint8_t radius = 0;
222     char * dirs = "dcxswe";
223     if (new_circle)
224     {
225         i_dirs = 0;
226         i_dist = 0;
227         radius = radius_new;
228         return '\0';
229     }
230     char ret_dir = dirs[i_dirs];
231     i_dist++;
232     if (i_dist == radius)
233     {
234         i_dist = 0;
235         i_dirs++;
236     }
237     return ret_dir;
238 }
239
240
241
242 extern void draw_border_circle(struct yx_uint8 yx, uint8_t radius,
243                                uint8_t * fov_map)
244 {
245     uint8_t dist;
246     for (dist = 1; dist <= radius; dist++)
247     {
248         mv_yx_in_dir_wrap('w', &yx, 0);
249     }
250     next_circle_dir(1, radius);
251     char dir;
252     while ('\0' != (dir = next_circle_dir(0, 0)))
253     {
254          if (mv_yx_in_dir_legal(dir, &yx))
255          {
256             uint16_t pos = yx_to_map_pos(&yx);
257             fov_map[pos] = LIMIT;
258         }
259     }
260     mv_yx_in_dir_wrap(0, NULL, 1);
261 }
262
263
264
265 static void geometry_to_char_ratio(uint8_t * n1, uint8_t * n2, uint8_t indent,
266                                    int16_t diff_y, int16_t diff_x,
267                                    uint8_t vertical, uint8_t variant)
268 {
269     if      (vertical)
270     {
271         *n1 = (diff_y / 2) - diff_x + ( indent * (diff_y % 2));
272         *n2 = (diff_y / 2) + diff_x + (!indent * (diff_y % 2));
273     }
274     else if (!vertical)
275     {
276         *n1 = diff_y;
277         *n2 = diff_x - (diff_y / 2) - (indent * (diff_y % 2));
278     }
279     if (!variant)
280     {
281         uint8_t tmp = *n1;
282         *n1 = *n2;
283         *n2 = tmp;
284     }
285 }
286
287
288
289 static char * eye_to_cell_dir_ratio(char * available_dirs, uint8_t indent,
290                                     int16_t diff_y, int16_t diff_x,
291                                     uint8_t vertical, uint8_t variant,
292                                     uint8_t shift_right)
293 {
294     char * f_name = "eye_to_cell_dir_ratio()";
295     uint8_t n1, n2;
296     geometry_to_char_ratio(&n1, &n2, indent, diff_y, diff_x, vertical, variant);
297     uint8_t size_chars = n1 + n2;
298     char * dirs = try_malloc(size_chars + 1, f_name);
299     uint8_t n_strong_char = n1 / n2;
300     uint8_t more_char1 = 0 < n_strong_char;
301     n_strong_char = !more_char1 ? (n2 / n1) : n_strong_char;
302     uint16_t i, i_alter;
303     uint8_t i_of_char = shift_right;
304     for (i = 0, i_alter = 0; i < size_chars; i++)
305     {
306         char dirchar = available_dirs[i_of_char];
307         if (more_char1 != i_of_char)
308         {
309             i_alter++;
310             if (i_alter == n_strong_char)
311             {
312                 i_alter = 0;
313                 i_of_char = !i_of_char;
314             }
315         }
316         else
317         {
318             i_of_char = !i_of_char;
319         }
320
321         dirs[i] = dirchar;
322     }
323     dirs[i] = '\0';
324     return dirs;
325 }
326
327
328
329 static char * dir_from_delta(uint8_t indent, int16_t diff_y, int16_t diff_x)
330 {
331     int16_t double_x = 2 * diff_x;
332     int16_t indent_corrected_double_x_pos =  double_x - indent  + !indent;
333     int16_t indent_corrected_double_x_neg = -double_x - !indent +  indent;
334     if (diff_y > 0)
335     {
336         if (diff_y ==  double_x || diff_y == indent_corrected_double_x_pos)
337         {
338             return "c";
339         }
340         if (diff_y == -double_x || diff_y == indent_corrected_double_x_neg)
341         {
342             return "x";
343         }
344         if (diff_y  <  double_x || diff_y  < indent_corrected_double_x_pos)
345         {
346             return "dc";
347         }
348         if (diff_y  < -double_x || diff_y  < indent_corrected_double_x_neg)
349         {
350             return "xs";
351         }
352         return "cx";
353     }
354     if (diff_y < 0)
355     {
356         if (diff_y ==  double_x || diff_y == indent_corrected_double_x_pos)
357         {
358             return "w";
359         }
360         if (diff_y == -double_x || diff_y == indent_corrected_double_x_neg)
361         {
362             return "e";
363         }
364         if (diff_y  >  double_x || diff_y  > indent_corrected_double_x_pos)
365         {
366             return "sw";
367         }
368         if (diff_y  > -double_x || diff_y  > indent_corrected_double_x_neg)
369         {
370             return "ed";
371         }
372         return "we";
373     }
374     return 0 > diff_x ? "s" : "d";
375 }
376
377
378
379 static char * eye_to_cell(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
380                           uint8_t right)
381 {
382     int16_t diff_y = yx_cell->y - yx_eye->y;
383     int16_t diff_x = yx_cell->x - yx_eye->x;
384     uint8_t indent = yx_eye->y % 2;
385     char * dir = dir_from_delta(indent, diff_y, diff_x);
386     char * dirs = NULL;
387     if (1 == strlen(dir))
388     {
389         return strdup(dir);
390     }
391     else if (!strcmp(dir, "dc"))
392     {
393         dirs = eye_to_cell_dir_ratio(dir, indent,  diff_y,  diff_x,  0,0,right);
394     }
395     else if (!strcmp(dir, "xs"))
396     {
397         dirs = eye_to_cell_dir_ratio(dir, !indent,  diff_y, -diff_x, 0,1,right);
398     }
399     else if (!strcmp(dir, "cx"))
400     {
401         dirs = eye_to_cell_dir_ratio(dir, indent,  diff_y,  diff_x,  1,0,right);
402     }
403     else if (!strcmp(dir, "sw"))
404     {
405         dirs = eye_to_cell_dir_ratio(dir, !indent, -diff_y, -diff_x, 0,0,right);
406     }
407     else if (!strcmp(dir, "ed"))
408     {
409         dirs = eye_to_cell_dir_ratio(dir, indent, -diff_y,  diff_x, 0,1,right);
410     }
411     else if (!strcmp(dir, "we"))
412     {
413         dirs = eye_to_cell_dir_ratio(dir, indent, -diff_y,  diff_x, 1,1,right);
414     }
415     return dirs;
416 }
417
418
419
420 static uint8_t is_top_left_shaded(uint16_t pos_a, uint16_t pos_b,
421                                   int16_t a_y_on_left)
422 {
423     uint16_t start_last_row = world.map.length * (world.map.length - 1);
424     uint8_t a_on_left_or_bottom =    0 <= a_y_on_left
425                                   || (pos_a >= start_last_row);
426     uint8_t b_on_top_or_right =    pos_b < world.map.length
427                                 || pos_b % world.map.length==world.map.length-1;
428     return pos_a != pos_b && b_on_top_or_right && a_on_left_or_bottom;
429 }
430
431
432
433 static void fill_shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_cell,
434                         uint8_t * fov_map, uint16_t pos_a, uint16_t pos_b)
435 {
436     int16_t a_y_on_left = !(pos_a%world.map.length)? pos_a/world.map.length :-1;
437     int16_t b_y_on_left = !(pos_b%world.map.length)? pos_b/world.map.length :-1;
438     uint8_t top_left_shaded = is_top_left_shaded(pos_a, pos_b, a_y_on_left);
439     uint16_t pos;
440     uint8_t y, x, in_shade;
441     for (y = 0; y < world.map.length; y++)
442     {
443         in_shade =    (top_left_shaded || (b_y_on_left >= 0 && y > b_y_on_left))
444                    && (a_y_on_left < 0 || y < a_y_on_left);
445         for (x = 0; x < world.map.length; x++)
446         {
447             pos = (y * world.map.length) + x;
448             if (yx_eye->y == yx_cell->y && yx_eye->x < yx_cell->x)
449             {
450                 uint8_t val = fov_map[pos] & (SHADOW_LEFT | SHADOW_RIGHT);
451                 in_shade = 0 < val ? 1 : in_shade;
452             }
453             else if (yx_eye->y == yx_cell->y && yx_eye->x > yx_cell->x)
454             {
455                 uint8_t val = fov_map[pos] & (SHADOW_LEFT | SHADOW_RIGHT);
456                 in_shade = 0 < val ? 0 : in_shade;
457             }
458             else if (yx_eye->y > yx_cell->y && y <= yx_cell->y)
459             {
460                 in_shade = 0 < (fov_map[pos] & SHADOW_LEFT) ? 1 : in_shade;
461                 in_shade = (fov_map[pos] & SHADOW_RIGHT) ? 0 : in_shade;
462             }
463             else if (yx_eye->y < yx_cell->y && y >= yx_cell->y)
464             {
465                 in_shade = 0 < (fov_map[pos] & SHADOW_RIGHT) ? 1 : in_shade;
466                 in_shade = (fov_map[pos] & SHADOW_LEFT) ? 0 : in_shade;
467             }
468             if (!(fov_map[pos] & (SHADOW_LEFT | SHADOW_RIGHT))
469                 && in_shade)
470             {
471                 fov_map[pos] = fov_map[pos] | HIDDEN;
472             }
473         }
474     }
475 }
476
477
478
479 static uint16_t shadow_arm(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
480                            uint8_t * fov_map, char dir, uint8_t flag,
481                            uint8_t shift_right)
482 {
483     struct yx_uint8 yx_border = *yx_start;
484     uint16_t pos = yx_to_map_pos(&yx_border);
485     if (mv_yx_in_dir_legal(dir, &yx_border))
486     {
487         uint8_t met_limit = 0;
488         uint8_t i_dirs = 0;
489         char * dirs = eye_to_cell(yx_eye, &yx_border, shift_right);
490         yx_border = *yx_start;
491         while (!met_limit && mv_yx_in_dir_legal(dirs[i_dirs], &yx_border))
492         {
493             pos = yx_to_map_pos(&yx_border);
494             met_limit = fov_map[pos] & LIMIT;
495             fov_map[pos] = fov_map[pos] | flag;
496             i_dirs = dirs[i_dirs + 1] ? i_dirs + 1 : 0;
497         }
498         free(dirs);
499     }
500     mv_yx_in_dir_wrap(0, NULL, 1);
501     return pos;
502 }
503
504
505
506 static void shadow(struct yx_uint8 * yx_eye, struct yx_uint8 * yx_start,
507                    uint8_t * fov_map, char dir_left, char dir_right)
508 {
509     uint16_t pos_a, pos_b, pos_start, i;
510     pos_a = shadow_arm(yx_eye, yx_start, fov_map, dir_left, SHADOW_LEFT, 0);
511     pos_b = shadow_arm(yx_eye, yx_start, fov_map, dir_right, SHADOW_RIGHT, 1);
512     pos_start = yx_to_map_pos(yx_start);
513     fov_map[pos_start] = fov_map[pos_start] | SHADOW_LEFT | SHADOW_RIGHT;
514     fill_shadow(yx_eye, yx_start, fov_map, pos_a, pos_b);
515     for (i = 0; i < world.map.length * world.map.length; i++)
516     {
517         if (fov_map[i] & (SHADOW_LEFT | SHADOW_RIGHT) && i != pos_start)
518         {
519             fov_map[i] = fov_map[i] | HIDE_LATER;
520         }
521         fov_map[i] = fov_map[i] ^ (fov_map[i] & SHADOW_LEFT);
522         fov_map[i] = fov_map[i] ^ (fov_map[i] & SHADOW_RIGHT);
523     }
524     return;
525 }
526
527
528
529 static void set_view_of_cell_and_shadows(struct yx_uint8 * yx_cell,
530                                          struct yx_uint8 * yx_eye,
531                                          uint8_t * fov_map)
532 {
533     char * dirs = "dcxswe";
534     uint16_t pos = yx_to_map_pos(yx_cell);
535     if (!(fov_map[pos] & HIDDEN))
536     {
537         fov_map[pos] = fov_map[pos] | VISIBLE;
538         if ('X' == world.map.cells[pos])
539         {
540             uint8_t last_pos = strlen(dirs) - 1;
541             int16_t diff_y = yx_cell->y - yx_eye->y;
542             int16_t diff_x = yx_cell->x - yx_eye->x;
543             uint8_t indent = yx_eye->y % 2;
544             char * dir = dir_from_delta(indent, diff_y, diff_x);
545             uint8_t start_pos = strchr(dirs, dir[0]) - dirs;
546             char prev = start_pos > 0 ? dirs[start_pos - 1] : dirs[last_pos];
547             char next = start_pos < last_pos ? dirs[start_pos + 1] : dirs[0];
548             if (dir[1])
549             {
550                 uint8_t end_pos = strchr(dirs, dir[1]) - dirs;
551                 next = end_pos < last_pos ? dirs[end_pos + 1] : dirs[0];
552             }
553             shadow(yx_eye, yx_cell, fov_map, prev, next);
554         }
555     }
556 }
557
558
559
560 extern uint8_t * build_fov_map(struct Thing * eye)
561 {
562     char * f_name = "build_fov_map()";
563     uint8_t radius = 2 * world.map.length;
564     uint32_t map_size = world.map.length * world.map.length;
565     struct yx_uint8 yx = eye->pos;
566     uint8_t * fov_map = try_malloc(map_size, f_name);
567     memset(fov_map, 0, map_size);
568     draw_border_circle(yx, radius, fov_map);
569     fov_map[yx_to_map_pos(&yx)] = VISIBLE;
570     uint8_t dist;
571     for (dist = 1; dist <= radius; dist++)
572     {
573         uint8_t first_round = 1;
574         char dir;
575         next_circle_dir(1, dist);
576         while ('\0' != (dir = next_circle_dir(0, 0)))
577         {
578             char i_dir = first_round ? 'e' : dir;
579             first_round = 0;
580             if (mv_yx_in_dir_legal(i_dir, &yx))
581             {
582                 set_view_of_cell_and_shadows(&yx, &eye->pos, fov_map);
583             }
584         }
585     }
586     uint16_t i;
587     for (i = 0; i < world.map.length * world.map.length; i++)
588     {
589         if (fov_map[i] & HIDE_LATER)
590         {
591               fov_map[i] = fov_map[i] ^ (fov_map[i] & VISIBLE);
592         }
593     }
594     return fov_map;
595 }