plomlompom.com Git - plomrogue/blob - 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 "yx_uint8.h" /* mv_yx_in_dir_wrap(), */
  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 * circle_dirs = "xswedc";
 322     uint16_t dist;
 323     uint8_t circle_on_map;
 324     for (dist = 1, circle_on_map = 1; circle_on_map; dist++)
 325     {
 326         if (1 != dist)
 327         {
 328             mv_yx_in_dir_legal('c', &test_pos);
 329         }
 330         char dir = 'd';
 331         uint8_t i_dir = circle_on_map = 0;
 332         uint16_t i_dist, hex_i;
 333         for (hex_i = 0, i_dist = 1; hex_i < 6 * dist; i_dist++, hex_i++)
 334         {
 335             if (mv_yx_in_dir_legal(dir, &test_pos))
 336             {
 337                 eval_position(dist, hex_i, t->fov_map, &test_pos, &shadows);
 338                 circle_on_map = 1;
 339             }
 340             dir = circle_dirs[i_dir];
 341             if (dist == i_dist)
 342             {
 343                 i_dist = 0;
 344                 i_dir++;
 345             }
 346         }
 347     }
 348     mv_yx_in_dir_wrap(0, NULL, 1);
 349     free_angles(shadows);
 350     update_map_memory(t, map_size);
 351 }