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