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