home · contact · privacy
177143a26389758d053f93d3121321f453eb29dc
[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 "map.h" /* yx_to_map_pos() */
10 #include "things.h" /* Thing */
11 #include "yx_uint8.h" /* yx_uint8 */
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 /* Move "yx" into hex direction "d". */
35 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx);
36
37 /* Move "yx" into hex direction "d". If this moves "yx" beyond the minimal (0)
38  * or maximal (UINT8_MAX) column or row, it wraps to the opposite side. Such
39  * wrapping is returned as a wraps enum value and stored, so that further calls
40  * to move "yx" back into the opposite direction may unwrap it again. Pass an
41  * "unwrap" of !0 to re-set the internal wrap memory to 0.
42  */
43 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap);
44
45 /* Wrapper to "mv_yx_in_dir_wrap()", returns 1 if the wrapped function moved
46  * "yx" within the wrap borders and the map size, else 0.
47  */
48 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx);
49
50 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
51 static uint32_t correct_angle(int32_t angle);
52
53 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
54  * it meets the shadow from the right or the left. Returns 1 on success, else 0.
55  */
56 static uint8_t try_merge(struct shadow_angle * shadow,
57                          uint32_t left_angle, uint32_t right_angle);
58
59 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
60  * existing shadow angle in "shadows". On success, see if this leads to any
61  * additional shadow angle overlaps and merge these accordingly. Return 1 on
62  * success, else 0.
63  */
64 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
65                                   struct shadow_angle ** shadows);
66
67 /* If "pos_in_map" in angle between"left_angle" to "right_angle" to the viewing
68  * actor is in a shadow from the shadow list "shadows", mark it as HIDDEN on the
69  * "fov_map"; else, if the world map features a viewing obstacle on the world
70  * map, calculate its shadow angle to the viewer and add it to "shadows".
71  */
72 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
73                        struct shadow_angle ** shadows, uint16_t pos_in_map,
74                        uint8_t * fov_map);
75
76 /* Free shadow angles list "angles". */
77 static void free_angles(struct shadow_angle * angles);
78
79 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
80  * on the circle of that distance to the origin on hex "hex_i" (as counted from
81  * the circle's rightmost point), for setting shaded cells in "fov_map" and
82  * potentially adding a new shadow to linked shadow angle list "shadows".
83  */
84 static void eval_position(uint16_t dist, uint16_t hex_i, uint8_t * fov_map,
85                           struct yx_uint8 * test_pos,
86                           struct shadow_angle ** shadows);
87
88
89
90 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx)
91 {
92     if     (d == 'e')
93     {
94         yx->x = yx->x + (yx->y % 2);
95         yx->y--;
96     }
97     else if (d == 'd')
98     {
99         yx->x++;
100     }
101     else if (d == 'c')
102     {
103         yx->x = yx->x + (yx->y % 2);
104         yx->y++;
105     }
106     else if (d == 'x')
107     {
108         yx->x = yx->x - !(yx->y % 2);
109         yx->y++;
110     }
111     else if (d == 's')
112     {
113         yx->x--;
114     }
115     else if (d == 'w')
116     {
117         yx->x = yx->x - !(yx->y % 2);
118         yx->y--;
119     }
120 }
121
122
123
124 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
125 {
126     static int8_t wrap_west_east   = 0;
127     static int8_t wrap_north_south = 0;
128     if (unwrap)
129     {
130         wrap_west_east = wrap_north_south = 0;
131         return 0;
132     }
133     struct yx_uint8 original;
134     original.y = yx->y;
135     original.x = yx->x;
136     mv_yx_in_hex_dir(d, yx);
137     if      (strchr("edc", d) && yx->x < original.x)
138     {
139         wrap_west_east++;
140     }
141     else if (strchr("xsw", d) && yx->x > original.x)
142     {
143         wrap_west_east--;
144     }
145     if      (strchr("we", d) && yx->y > original.y)
146     {
147         wrap_north_south--;
148     }
149     else if (strchr("xc", d) && yx->y < original.y)
150     {
151         wrap_north_south++;
152     }
153     return (wrap_west_east != 0) + (wrap_north_south != 0);
154 }
155
156
157
158 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
159 {
160     uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
161     if (!wraptest && yx->x < world.map.length && yx->y < world.map.length)
162     {
163         return 1;
164     }
165     return 0;
166 }
167
168
169
170 static uint32_t correct_angle(int32_t angle)
171 {
172     while (angle < 0)
173     {
174         angle = angle + CIRCLE;
175     }
176     while (angle > CIRCLE)
177     {
178         angle = angle - CIRCLE;
179     }
180     return angle;
181 }
182
183
184
185 static uint8_t try_merge(struct shadow_angle * shadow,
186                          uint32_t left_angle, uint32_t right_angle)
187 {
188     if      (   shadow->right_angle <= left_angle + 1
189              && shadow->right_angle >= right_angle)
190     {
191         shadow->right_angle = right_angle;
192     }
193     else if (   shadow->left_angle + 1 >= right_angle
194              && shadow->left_angle     <= left_angle)
195     {
196         shadow->left_angle = left_angle;
197     }
198     else
199     {
200         return 0;
201     }
202     return 1;
203 }
204
205
206
207 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
208                                   struct shadow_angle ** shadows)
209 {
210     uint8_t angle_merge = 0;
211     struct shadow_angle * shadow;
212     for (shadow = *shadows; shadow; shadow = shadow->next)
213     {
214         if (try_merge(shadow, left_angle, right_angle))
215         {
216             angle_merge = 1;
217         }
218     }
219     if (angle_merge)
220     {
221         struct shadow_angle * shadow1;
222         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
223         {
224             struct shadow_angle * last_shadow = NULL;
225             struct shadow_angle * shadow2;
226             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
227             {
228                 if (   shadow1 != shadow2
229                     && try_merge(shadow1, shadow2->left_angle,
230                                           shadow2->right_angle))
231                 {
232                     struct shadow_angle * to_free = shadow2;
233                     if (last_shadow)
234                     {
235                         last_shadow->next = shadow2->next;
236                         shadow2 = last_shadow;
237                     }
238                     else
239                     {
240                         *shadows = shadow2->next;
241                         shadow2 = *shadows;
242                     }
243                     free(to_free);
244                 }
245                 last_shadow = shadow2;
246             }
247         }
248     }
249     return angle_merge;
250 }
251
252
253
254 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
255                        struct shadow_angle ** shadows, uint16_t pos_in_map,
256                        uint8_t * fov_map)
257 {
258     char * f_name = "set_shadow()";
259     struct shadow_angle * shadow_i;
260     if (fov_map[pos_in_map] & VISIBLE)
261     {
262         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
263         {
264             if (   left_angle <=  shadow_i->left_angle
265                 && right_angle >= shadow_i->right_angle)
266             {
267                 fov_map[pos_in_map] = HIDDEN;
268                 return;
269             }
270         }
271     }
272     if ('X' == world.map.cells[pos_in_map])
273     {
274         if (!try_merging_angles(left_angle, right_angle, shadows))
275         {
276             struct shadow_angle * shadow;
277             shadow = try_malloc(sizeof(struct shadow_angle), f_name);
278             shadow->left_angle  = left_angle;
279             shadow->right_angle = right_angle;
280             shadow->next = NULL;
281             if (*shadows)
282             {
283                 for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
284                 {
285                     if (!shadow_i->next)
286                     {
287                         shadow_i->next = shadow;
288                         return;
289                     }
290                 }
291             }
292             *shadows = shadow;
293         }
294     }
295 }
296
297
298
299 static void free_angles(struct shadow_angle * angles)
300 {
301     if (angles->next)
302     {
303         free_angles(angles->next);
304     }
305     free(angles);
306 }
307
308
309
310 static void eval_position(uint16_t dist, uint16_t hex_i, uint8_t * fov_map,
311                           struct yx_uint8 * test_pos,
312                           struct shadow_angle ** shadows)
313 {
314     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
315                                      - ((hex_i * (CIRCLE / 6)) / dist);
316     int32_t right_angle_uncorrected =   left_angle_uncorrected
317                                       - (CIRCLE / (6 * dist));
318     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
319     uint32_t right_angle = correct_angle(right_angle_uncorrected);
320     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
321     uint16_t pos_in_map = yx_to_map_pos(test_pos);
322     set_shadow(left_angle, right_angle_1st, shadows, pos_in_map, fov_map);
323     if (right_angle_1st != right_angle)
324     {
325         left_angle = CIRCLE;
326         set_shadow(left_angle, right_angle, shadows, pos_in_map, fov_map);
327     }
328 }
329
330
331
332 extern uint8_t * build_fov_map(struct Thing * eye)
333 {
334     char * f_name = "build_fov_map()";
335     uint32_t map_size = world.map.length * world.map.length;
336     uint8_t * fov_map = try_malloc(map_size, f_name);
337     memset(fov_map, VISIBLE, map_size);
338     struct yx_uint8 test_pos = eye->pos;
339     struct shadow_angle * shadows = NULL;
340     char * circle_dirs = "xswedc";
341     uint16_t dist;
342     uint8_t first_round, circle_on_map;
343     for (first_round = 1, dist = 1, circle_on_map = 1; circle_on_map; dist++)
344     {
345         if (!first_round)
346         {
347             mv_yx_in_dir_legal('c', &test_pos);
348         }
349         char dir = 'd';
350         uint8_t i_dir = first_round = circle_on_map = 0;
351         uint16_t i_dist, hex_i;
352         for (hex_i = 0, i_dist = 1; hex_i < 6 * dist; i_dist++, hex_i++)
353         {
354             if (mv_yx_in_dir_legal(dir, &test_pos))
355             {
356                 eval_position(dist, hex_i, fov_map, &test_pos, &shadows);
357                 circle_on_map = 1;
358             }
359             dir = circle_dirs[i_dir];
360             if (dist == i_dist)
361             {
362                 i_dist = 0;
363                 i_dir++;
364             }
365         }
366     }
367     mv_yx_in_dir_wrap(0, NULL, 1);
368     free_angles(shadows);
369     return fov_map;
370 }