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 "things.h" /* Thing */
  10 #include "yx_uint8.h" /* yx_uint8 */
  11 #include "world.h" /* world  */
  12
  13
  14
  15 /* Number of degrees a circle is divided into. The greater it is, the greater
  16  * the angle precision. But make it one whole zero larger and bizarre FOV bugs
  17  * appear on large maps, probably due to value overflows (TODO: more research!).
  18  */
  19 #define CIRCLE 3600000
  20
  21
  22
  23 /* Angle of a shadow. */
  24 struct shadow_angle
  25 {
  26     struct shadow_angle * next;
  27     uint32_t left_angle;
  28     uint32_t right_angle;
  29 };
  30
  31
  32
  33 /* Move "yx" into hex direction "d". */
  34 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx);
  35
  36 /* Move "yx" into hex direction "d". If this moves "yx" beyond the minimal (0)
  37  * or maximal (UINT8_MAX) column or row, it wraps to the opposite side. Such
  38  * wrapping is returned as a wraps enum value and stored, so that further calls
  39  * to move "yx" back into the opposite direction may unwrap it again. Pass an
  40  * "unwrap" of !0 to re-set the internal wrap memory to 0.
  41  */
  42 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap);
  43
  44 /* Wrapper to mv_yx_in_dir_wrap(), returns 1 if the wrapped function moved "yx"
  45  * within the wrap borders and the map size, else 0.
  46  */
  47 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx);
  48
  49 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
  50 static uint32_t correct_angle(int32_t angle);
  51
  52 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
  53  * it meets the shadow from the right or the left. Returns 1 on success, else 0.
  54  */
  55 static uint8_t try_merge(struct shadow_angle * shadow,
  56                          uint32_t left_angle, uint32_t right_angle);
  57
  58 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
  59  * existing shadow angle in "shadows". On success, see if this leads to any
  60  * additional shadow angle overlaps and merge these accordingly. Return 1 on
  61  * success, else 0.
  62  */
  63 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
  64                                   struct shadow_angle ** shadows);
  65
  66 /* Test whether angle between "left_angle" and "right_angle", or at least
  67  * "middle_angle", is captured inside one of the shadow angles in "shadows". If
  68  * so, set hex in "fov_map" indexed by "pos_in_map" to HIDDEN. If the whole
  69  * angle and not just "middle_angle" is captured, return 1. Any other case: 0.
  70  */
  71 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
  72                          uint32_t middle_angle, struct shadow_angle ** shadows,
  73                          uint16_t pos_in_map, uint8_t * fov_map);
  74
  75 /* Test whether angle between "left_angle" and "right_angle", or at least
  76  * "middle_angle", is captured inside one of the shadow angles in "shadows". If
  77  * so, set hex in "fov_map" indexed by "pos_in_map" to HIDDEN. If the whole
  78  * angle and not just "middle_angle" is captured, return 1. Any other case: 0.
  79  */
  80 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
  81                          uint32_t middle_angle, struct shadow_angle ** shadows,
  82                          uint16_t pos_in_map, uint8_t * fov_map);
  83
  84 /* Free shadow angles list "angles". */
  85 static void free_angles(struct shadow_angle * angles);
  86
  87 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
  88  * on the circle of that distance to the origin on hex "hex_i" (as counted from
  89  * the circle's rightmost point), for setting shaded hexes in "fov_map" and
  90  * potentially adding a new shadow to linked shadow angle list "shadows".
  91  */
  92 static void eval_position(uint16_t dist, uint16_t hex_i, uint8_t * fov_map,
  93                           struct yx_uint8 * test_pos,
  94                           struct shadow_angle ** shadows);
  95
  96 /* Update "t"'s .mem_map memory with what's in its current field of view. */
  97 static void update_map_memory(struct Thing * t, uint32_t map_size);
  98
  99
 100
 101 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx)
 102 {
 103     if     (d == 'e')
 104     {
 105         yx->x = yx->x + (yx->y % 2);
 106         yx->y--;
 107     }
 108     else if (d == 'd')
 109     {
 110         yx->x++;
 111     }
 112     else if (d == 'c')
 113     {
 114         yx->x = yx->x + (yx->y % 2);
 115         yx->y++;
 116     }
 117     else if (d == 'x')
 118     {
 119         yx->x = yx->x - !(yx->y % 2);
 120         yx->y++;
 121     }
 122     else if (d == 's')
 123     {
 124         yx->x--;
 125     }
 126     else if (d == 'w')
 127     {
 128         yx->x = yx->x - !(yx->y % 2);
 129         yx->y--;
 130     }
 131 }
 132
 133
 134
 135 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
 136 {
 137     static int8_t wrap_west_east   = 0;
 138     static int8_t wrap_north_south = 0;
 139     if (unwrap)
 140     {
 141         wrap_west_east = wrap_north_south = 0;
 142         return 0;
 143     }
 144     struct yx_uint8 original;
 145     original.y = yx->y;
 146     original.x = yx->x;
 147     mv_yx_in_hex_dir(d, yx);
 148     if      (strchr("edc", d) && yx->x < original.x)
 149     {
 150         wrap_west_east++;
 151     }
 152     else if (strchr("xsw", d) && yx->x > original.x)
 153     {
 154         wrap_west_east--;
 155     }
 156     if      (strchr("we", d) && yx->y > original.y)
 157     {
 158         wrap_north_south--;
 159     }
 160     else if (strchr("xc", d) && yx->y < original.y)
 161     {
 162         wrap_north_south++;
 163     }
 164     return (wrap_west_east != 0) + (wrap_north_south != 0);
 165 }
 166
 167
 168
 169 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
 170 {
 171     uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
 172     if (!wraptest && yx->x < world.map.length && yx->y < world.map.length)
 173     {
 174         return 1;
 175     }
 176     return 0;
 177 }
 178
 179
 180
 181 static uint32_t correct_angle(int32_t angle)
 182 {
 183     while (angle < 0)
 184     {
 185         angle = angle + CIRCLE;
 186     }
 187     while (angle > CIRCLE)
 188     {
 189         angle = angle - CIRCLE;
 190     }
 191     return angle;
 192 }
 193
 194
 195
 196 static uint8_t try_merge(struct shadow_angle * shadow,
 197                          uint32_t left_angle, uint32_t right_angle)
 198 {
 199     if      (   shadow->right_angle <= left_angle + 1
 200              && shadow->right_angle >= right_angle)
 201     {
 202         shadow->right_angle = right_angle;
 203     }
 204     else if (   shadow->left_angle + 1 >= right_angle
 205              && shadow->left_angle     <= left_angle)
 206     {
 207         shadow->left_angle = left_angle;
 208     }
 209     else
 210     {
 211         return 0;
 212     }
 213     return 1;
 214 }
 215
 216
 217
 218 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
 219                                   struct shadow_angle ** shadows)
 220 {
 221     uint8_t angle_merge = 0;
 222     struct shadow_angle * shadow;
 223     for (shadow = *shadows; shadow; shadow = shadow->next)
 224     {
 225         if (try_merge(shadow, left_angle, right_angle))
 226         {
 227             angle_merge = 1;
 228         }
 229     }
 230     if (angle_merge)
 231     {
 232         struct shadow_angle * shadow1;
 233         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
 234         {
 235             struct shadow_angle * last_shadow = NULL;
 236             struct shadow_angle * shadow2;
 237             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
 238             {
 239                 if (   shadow1 != shadow2
 240                     && try_merge(shadow1, shadow2->left_angle,
 241                                           shadow2->right_angle))
 242                 {
 243                     struct shadow_angle * to_free = shadow2;
 244                     if (last_shadow)
 245                     {
 246                         last_shadow->next = shadow2->next;
 247                         shadow2 = last_shadow;
 248                     }
 249                     else
 250                     {
 251                         *shadows = shadow2->next;
 252                         shadow2 = *shadows;
 253                     }
 254                     free(to_free);
 255                 }
 256                 last_shadow = shadow2;
 257             }
 258         }
 259     }
 260     return angle_merge;
 261 }
 262
 263
 264
 265 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
 266                          uint32_t middle_angle, struct shadow_angle ** shadows,
 267                          uint16_t pos_in_map, uint8_t * fov_map)
 268 {
 269     struct shadow_angle * shadow_i;
 270     if (fov_map[pos_in_map] & VISIBLE)
 271     {
 272         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 273         {
 274             if (   left_angle <=  shadow_i->left_angle
 275                 && right_angle >= shadow_i->right_angle)
 276             {
 277                 fov_map[pos_in_map] = HIDDEN;
 278                 return 1;
 279             }
 280             if (   middle_angle < shadow_i->left_angle
 281                 && middle_angle > shadow_i->right_angle)
 282             {
 283                 fov_map[pos_in_map] = HIDDEN;
 284             }
 285         }
 286     }
 287     return 0;
 288 }
 289
 290
 291
 292 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
 293  * new entry or as part of an existing shadow (swallowed whole or extending it).
 294  */
 295 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
 296                        struct shadow_angle ** shadows)
 297 {
 298     struct shadow_angle * shadow_i;
 299     if (!try_merging_angles(left_angle, right_angle, shadows))
 300     {
 301         struct shadow_angle * shadow;
 302         shadow = try_malloc(sizeof(struct shadow_angle), __func__);
 303         shadow->left_angle  = left_angle;
 304         shadow->right_angle = right_angle;
 305         shadow->next = NULL;
 306         if (*shadows)
 307         {
 308             for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 309             {
 310                 if (!shadow_i->next)
 311                 {
 312                     shadow_i->next = shadow;
 313                     return;
 314                 }
 315             }
 316         }
 317         *shadows = shadow;
 318     }
 319 }
 320
 321
 322
 323 static void free_angles(struct shadow_angle * angles)
 324 {
 325     if (angles->next)
 326     {
 327         free_angles(angles->next);
 328     }
 329     free(angles);
 330 }
 331
 332
 333
 334 static void eval_position(uint16_t dist, uint16_t hex_i, uint8_t * fov_map,
 335                           struct yx_uint8 * test_pos,
 336                           struct shadow_angle ** shadows)
 337 {
 338     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
 339                                      - (hex_i * (CIRCLE / 6) / dist);
 340     int32_t right_angle_uncorrected =   left_angle_uncorrected
 341                                       - (CIRCLE / (6 * dist));
 342     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
 343     uint32_t right_angle = correct_angle(right_angle_uncorrected);
 344     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
 345     uint32_t middle_angle = 0;
 346     if (right_angle_1st)
 347     {
 348         middle_angle = right_angle + ((left_angle - right_angle) / 2);
 349     }
 350     uint16_t pos_in_map = test_pos->y * world.map.length + test_pos->x;
 351     uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
 352                                    shadows, pos_in_map, fov_map);
 353     if (!all_shaded && 'X' == world.map.cells[pos_in_map])
 354     {
 355         set_shadow(left_angle, right_angle_1st, shadows);
 356         if (right_angle_1st != right_angle)
 357         {
 358             left_angle = CIRCLE;
 359             set_shadow(left_angle, right_angle, shadows);
 360         }
 361     }
 362 }
 363
 364
 365
 366 static void update_map_memory(struct Thing * t, uint32_t map_size)
 367 {
 368     if (!t->mem_map)
 369     {
 370         t->mem_map = try_malloc(map_size, __func__);
 371         memset(t->mem_map, ' ', map_size);
 372     }
 373     uint32_t i;
 374     for (i = 0; i < map_size; i++)
 375     {
 376         if (' ' == t->mem_map[i] && t->fov_map[i] & VISIBLE)
 377         {
 378             t->mem_map[i] = world.map.cells[i];
 379         }
 380     }
 381 }
 382
 383
 384
 385 extern void build_fov_map(struct Thing * t)
 386 {
 387     uint32_t map_size = world.map.length * world.map.length;
 388     t->fov_map = t->fov_map ? t->fov_map : try_malloc(map_size, __func__);
 389     memset(t->fov_map, VISIBLE, map_size);
 390     struct yx_uint8 test_pos = t->pos;
 391     struct shadow_angle * shadows = NULL;
 392     char * circle_dirs = "xswedc";
 393     uint16_t dist;
 394     uint8_t first_round, circle_on_map;
 395     for (first_round = 1, dist = 1, circle_on_map = 1; circle_on_map; dist++)
 396     {
 397         if (!first_round)
 398         {
 399             mv_yx_in_dir_legal('c', &test_pos);
 400         }
 401         char dir = 'd';
 402         uint8_t i_dir = first_round = circle_on_map = 0;
 403         uint16_t i_dist, hex_i;
 404         for (hex_i = 0, i_dist = 1; hex_i < 6 * dist; i_dist++, hex_i++)
 405         {
 406             if (mv_yx_in_dir_legal(dir, &test_pos))
 407             {
 408                 eval_position(dist, hex_i, t->fov_map, &test_pos, &shadows);
 409                 circle_on_map = 1;
 410             }
 411             dir = circle_dirs[i_dir];
 412             if (dist == i_dist)
 413             {
 414                 i_dist = 0;
 415                 i_dir++;
 416             }
 417         }
 418     }
 419     mv_yx_in_dir_wrap(0, NULL, 1);
 420     free_angles(shadows);
 421     update_map_memory(t, map_size);
 422 }