home · contact · privacy
Server: Add explanatory comments to build_fov_map().
[plomrogue] / src / server / field_of_view.c
1 /* src/server/field_of_view.c */
2
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 "../common/yx_uint8.h" /* yx_uint8 */
10 #include "map.h" /* mv_yx_in_dir_legal() */
11 #include "things.h" /* Thing, ThingInMemory, add_thing_to_memory_map() */
12 #include "world.h" /* world  */
13
14
15
16 /* Number of degrees a circle is divided into. The greater it is, the greater
17  * the angle precision. But make it one whole zero larger and bizarre FOV bugs
18  * appear on large maps, probably due to value overflows (TODO: more research!).
19  */
20 #define CIRCLE 3600000
21
22
23
24 /* Angle of a shadow. */
25 struct shadow_angle
26 {
27     struct shadow_angle * next;
28     uint32_t left_angle;
29     uint32_t right_angle;
30 };
31
32
33
34 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
35 static uint32_t correct_angle(int32_t angle);
36
37 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
38  * it meets the shadow from the right or the left. Returns 1 on success, else 0.
39  */
40 static uint8_t try_merge(struct shadow_angle * shadow,
41                          uint32_t left_angle, uint32_t right_angle);
42
43 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
44  * existing shadow angle in "shadows". On success, see if this leads to any
45  * additional shadow angle overlaps and merge these accordingly. Return 1 on
46  * success, else 0.
47  */
48 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
49                                   struct shadow_angle ** shadows);
50
51 /* Test whether angle between "left_angle" and "right_angle", or at least
52  * "middle_angle", is captured inside one of the shadow angles in "shadows". If
53  * so, set hex in "fov_map" indexed by "pos_in_map" to 'H'. If the whole angle
54  * and not just "middle_angle" is captured, return 1. Any other case: 0.
55  */
56 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
57                          uint32_t middle_angle, struct shadow_angle ** shadows,
58                          uint16_t pos_in_map, char * fov_map);
59
60 /* Free shadow angles list "angles". */
61 static void free_angles(struct shadow_angle * angles);
62
63 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
64  * on the circle of that distance to the origin on hex "hex_i" (as counted from
65  * the circle's rightmost point), for setting shaded hexes in "fov_map" and
66  * potentially adding a new shadow to linked shadow angle list "shadows".
67  */
68 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
69                           struct yx_uint8 * test_pos,
70                           struct shadow_angle ** shadows);
71
72 /* Update "t"'s .mem_map memory with what's in its current FOV, remove from its
73  * .t_mem all memorized things in FOV and add inanimiate things in FOV to it.
74  */
75 static void update_map_memory(struct Thing * t, uint32_t map_size);
76
77
78
79 static uint32_t correct_angle(int32_t angle)
80 {
81     while (angle < 0)
82     {
83         angle = angle + CIRCLE;
84     }
85     while (angle > CIRCLE)
86     {
87         angle = angle - CIRCLE;
88     }
89     return angle;
90 }
91
92
93
94 static uint8_t try_merge(struct shadow_angle * shadow,
95                          uint32_t left_angle, uint32_t right_angle)
96 {
97     if      (   shadow->right_angle <= left_angle + 1
98              && shadow->right_angle >= right_angle)
99     {
100         shadow->right_angle = right_angle;
101     }
102     else if (   shadow->left_angle + 1 >= right_angle
103              && shadow->left_angle     <= left_angle)
104     {
105         shadow->left_angle = left_angle;
106     }
107     else
108     {
109         return 0;
110     }
111     return 1;
112 }
113
114
115
116 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
117                                   struct shadow_angle ** shadows)
118 {
119     uint8_t angle_merge = 0;
120     struct shadow_angle * shadow;
121     for (shadow = *shadows; shadow; shadow = shadow->next)
122     {
123         if (try_merge(shadow, left_angle, right_angle))
124         {
125             angle_merge = 1;
126         }
127     }
128     if (angle_merge)
129     {
130         struct shadow_angle * shadow1;
131         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
132         {
133             struct shadow_angle * last_shadow = NULL;
134             struct shadow_angle * shadow2;
135             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
136             {
137                 if (   shadow1 != shadow2
138                     && try_merge(shadow1, shadow2->left_angle,
139                                           shadow2->right_angle))
140                 {
141                     struct shadow_angle * to_free = shadow2;
142                     if (last_shadow)
143                     {
144                         last_shadow->next = shadow2->next;
145                         shadow2 = last_shadow;
146                     }
147                     else
148                     {
149                         *shadows = shadow2->next;
150                         shadow2 = *shadows;
151                     }
152                     free(to_free);
153                 }
154                 last_shadow = shadow2;
155             }
156         }
157     }
158     return angle_merge;
159 }
160
161
162
163 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
164                          uint32_t middle_angle, struct shadow_angle ** shadows,
165                          uint16_t pos_in_map, char * fov_map)
166 {
167     struct shadow_angle * shadow_i;
168     if (fov_map[pos_in_map] == 'v')
169     {
170         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
171         {
172             if (   left_angle <=  shadow_i->left_angle
173                 && right_angle >= shadow_i->right_angle)
174             {
175                 fov_map[pos_in_map] = 'H';
176                 return 1;
177             }
178             if (   middle_angle < shadow_i->left_angle
179                 && middle_angle > shadow_i->right_angle)
180             {
181                 fov_map[pos_in_map] = 'H';
182             }
183         }
184     }
185     return 0;
186 }
187
188
189
190 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
191  * new entry or as part of an existing shadow (swallowed whole or extending it).
192  */
193 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
194                        struct shadow_angle ** shadows)
195 {
196     struct shadow_angle * shadow_i;
197     if (!try_merging_angles(left_angle, right_angle, shadows))
198     {
199         struct shadow_angle * shadow;
200         shadow = try_malloc(sizeof(struct shadow_angle), __func__);
201         shadow->left_angle  = left_angle;
202         shadow->right_angle = right_angle;
203         shadow->next = NULL;
204         if (*shadows)
205         {
206             for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
207             {
208                 if (!shadow_i->next)
209                 {
210                     shadow_i->next = shadow;
211                     return;
212                 }
213             }
214         }
215         *shadows = shadow;
216     }
217 }
218
219
220
221 static void free_angles(struct shadow_angle * angles)
222 {
223     if (angles->next)
224     {
225         free_angles(angles->next);
226     }
227     free(angles);
228 }
229
230
231
232 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
233                           struct yx_uint8 * test_pos,
234                           struct shadow_angle ** shadows)
235 {
236     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
237                                      - (hex_i * (CIRCLE / 6) / dist);
238     int32_t right_angle_uncorrected =   left_angle_uncorrected
239                                       - (CIRCLE / (6 * dist));
240     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
241     uint32_t right_angle = correct_angle(right_angle_uncorrected);
242     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
243     uint32_t middle_angle = 0;
244     if (right_angle_1st)
245     {
246         middle_angle = right_angle + ((left_angle - right_angle) / 2);
247     }
248     uint16_t pos_in_map = test_pos->y * world.map.length + test_pos->x;
249     uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
250                                    shadows, pos_in_map, fov_map);
251     if (!all_shaded && 'X' == world.map.cells[pos_in_map])
252     {
253         set_shadow(left_angle, right_angle_1st, shadows);
254         if (right_angle_1st != right_angle)
255         {
256             left_angle = CIRCLE;
257             set_shadow(left_angle, right_angle, shadows);
258         }
259     }
260 }
261
262
263
264 static void update_map_memory(struct Thing * t_eye, uint32_t map_size)
265 {
266     if (!t_eye->mem_map)
267     {
268         t_eye->mem_map = try_malloc(map_size, __func__);
269         memset(t_eye->mem_map, ' ', map_size);
270     }
271     uint32_t i;
272     for (i = 0; i < map_size; i++)
273     {
274         if (' ' == t_eye->mem_map[i] && t_eye->fov_map[i] == 'v')
275         {
276             t_eye->mem_map[i] = world.map.cells[i];
277         }
278     }
279     struct ThingInMemory * tm = t_eye->t_mem;
280     struct ThingInMemory * tm_prev = NULL;
281     struct ThingInMemory * tm_next = NULL;
282     for (; tm; tm = tm_next)
283     {
284         tm_next = tm->next;
285         if ('v' == t_eye->fov_map[tm->pos.y * world.map.length + tm->pos.x])
286         {
287             if (tm_prev)
288             {
289                 tm_prev->next = tm->next;
290             }
291             else
292             {
293                 t_eye->t_mem = tm->next;
294             }
295             free(tm);
296             continue;
297         }
298         tm_prev = tm;
299     }
300     struct Thing * t = world.things;
301     for (; t; t = t->next)
302     {
303         if (   !t->lifepoints
304             && 'v' == t_eye->fov_map[t->pos.y * world.map.length + t->pos.x])
305         {
306             add_thing_to_memory_map(t_eye, t->type, t->pos.y, t->pos.x);
307         }
308     }
309 }
310
311
312
313 extern void build_fov_map(struct Thing * t)
314 {
315     uint32_t map_size = world.map.length * world.map.length;
316     t->fov_map = t->fov_map ? t->fov_map : try_malloc(map_size, __func__);
317     memset(t->fov_map, 'v', map_size);
318     struct shadow_angle * shadows = NULL;
319     struct yx_uint8 test_pos = t->pos;
320     char * circledirs_string = "xswedc";
321     uint16_t circle_i;
322     uint8_t circle_is_on_map;
323     for (circle_i = 1, circle_is_on_map = 1; circle_is_on_map; circle_i++)
324     {
325         circle_is_on_map = 0;
326         if (1 < circle_i)                      /* All circles but the 1st are */
327         {                                      /* moved into starting from a  */
328             mv_yx_in_dir_legal('c', &test_pos);/* previous circle's last hex, */
329         }                                      /* i.e. from the upper left.   */
330         uint8_t dir_char_pos_in_circledirs_string = 0;
331         char dir_char = 'd'; /* Circle's 1st hex is entered by rightward move.*/
332         uint16_t dist_i, hex_i;
333         for (hex_i = 0, dist_i = 1; hex_i < 6 * circle_i; dist_i++, hex_i++)
334         {
335             if (mv_yx_in_dir_legal(dir_char, &test_pos))
336             {
337                 eval_position(circle_i, hex_i, t->fov_map, &test_pos, &shadows);
338                 circle_is_on_map = 1;
339             }
340             dir_char = circledirs_string[dir_char_pos_in_circledirs_string];
341             if (circle_i == dist_i)                 /* Number of steps into   */
342             {                                       /* one direction before   */
343                 dist_i = 0;                         /* direction change is    */
344                 dir_char_pos_in_circledirs_string++;/* equal to distance to   */
345             }                                       /* center / circle number.*/
346         }
347     }
348     mv_yx_in_dir_legal(0, NULL);
349     free_angles(shadows);
350     update_map_memory(t, map_size);
351 }