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, ThingInMemory, add_thing_to_memory_map() */
  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 'H'. If the whole angle
  69  * 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, char * fov_map);
  74
  75 /* Free shadow angles list "angles". */
  76 static void free_angles(struct shadow_angle * angles);
  77
  78 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
  79  * on the circle of that distance to the origin on hex "hex_i" (as counted from
  80  * the circle's rightmost point), for setting shaded hexes in "fov_map" and
  81  * potentially adding a new shadow to linked shadow angle list "shadows".
  82  */
  83 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
  84                           struct yx_uint8 * test_pos,
  85                           struct shadow_angle ** shadows);
  86
  87 /* Update "t"'s .mem_map memory with what's in its current FOV, remove from its
  88  * .t_mem all memorized things in FOV and add inanimiate things in FOV to it.
  89  */
  90 static void update_map_memory(struct Thing * t, uint32_t map_size);
  91
  92
  93
  94 static void mv_yx_in_hex_dir(char d, struct yx_uint8 * yx)
  95 {
  96     if     (d == 'e')
  97     {
  98         yx->x = yx->x + (yx->y % 2);
  99         yx->y--;
 100     }
 101     else if (d == 'd')
 102     {
 103         yx->x++;
 104     }
 105     else if (d == 'c')
 106     {
 107         yx->x = yx->x + (yx->y % 2);
 108         yx->y++;
 109     }
 110     else if (d == 'x')
 111     {
 112         yx->x = yx->x - !(yx->y % 2);
 113         yx->y++;
 114     }
 115     else if (d == 's')
 116     {
 117         yx->x--;
 118     }
 119     else if (d == 'w')
 120     {
 121         yx->x = yx->x - !(yx->y % 2);
 122         yx->y--;
 123     }
 124 }
 125
 126
 127
 128 static uint8_t mv_yx_in_dir_wrap(char d, struct yx_uint8 * yx, uint8_t unwrap)
 129 {
 130     static int8_t wrap_west_east   = 0;
 131     static int8_t wrap_north_south = 0;
 132     if (unwrap)
 133     {
 134         wrap_west_east = wrap_north_south = 0;
 135         return 0;
 136     }
 137     struct yx_uint8 original;
 138     original.y = yx->y;
 139     original.x = yx->x;
 140     mv_yx_in_hex_dir(d, yx);
 141     if      (strchr("edc", d) && yx->x < original.x)
 142     {
 143         wrap_west_east++;
 144     }
 145     else if (strchr("xsw", d) && yx->x > original.x)
 146     {
 147         wrap_west_east--;
 148     }
 149     if      (strchr("we", d) && yx->y > original.y)
 150     {
 151         wrap_north_south--;
 152     }
 153     else if (strchr("xc", d) && yx->y < original.y)
 154     {
 155         wrap_north_south++;
 156     }
 157     return (wrap_west_east != 0) + (wrap_north_south != 0);
 158 }
 159
 160
 161
 162 static uint8_t mv_yx_in_dir_legal(char dir, struct yx_uint8 * yx)
 163 {
 164     uint8_t wraptest = mv_yx_in_dir_wrap(dir, yx, 0);
 165     if (!wraptest && yx->x < world.map.length && yx->y < world.map.length)
 166     {
 167         return 1;
 168     }
 169     return 0;
 170 }
 171
 172
 173
 174 static uint32_t correct_angle(int32_t angle)
 175 {
 176     while (angle < 0)
 177     {
 178         angle = angle + CIRCLE;
 179     }
 180     while (angle > CIRCLE)
 181     {
 182         angle = angle - CIRCLE;
 183     }
 184     return angle;
 185 }
 186
 187
 188
 189 static uint8_t try_merge(struct shadow_angle * shadow,
 190                          uint32_t left_angle, uint32_t right_angle)
 191 {
 192     if      (   shadow->right_angle <= left_angle + 1
 193              && shadow->right_angle >= right_angle)
 194     {
 195         shadow->right_angle = right_angle;
 196     }
 197     else if (   shadow->left_angle + 1 >= right_angle
 198              && shadow->left_angle     <= left_angle)
 199     {
 200         shadow->left_angle = left_angle;
 201     }
 202     else
 203     {
 204         return 0;
 205     }
 206     return 1;
 207 }
 208
 209
 210
 211 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
 212                                   struct shadow_angle ** shadows)
 213 {
 214     uint8_t angle_merge = 0;
 215     struct shadow_angle * shadow;
 216     for (shadow = *shadows; shadow; shadow = shadow->next)
 217     {
 218         if (try_merge(shadow, left_angle, right_angle))
 219         {
 220             angle_merge = 1;
 221         }
 222     }
 223     if (angle_merge)
 224     {
 225         struct shadow_angle * shadow1;
 226         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
 227         {
 228             struct shadow_angle * last_shadow = NULL;
 229             struct shadow_angle * shadow2;
 230             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
 231             {
 232                 if (   shadow1 != shadow2
 233                     && try_merge(shadow1, shadow2->left_angle,
 234                                           shadow2->right_angle))
 235                 {
 236                     struct shadow_angle * to_free = shadow2;
 237                     if (last_shadow)
 238                     {
 239                         last_shadow->next = shadow2->next;
 240                         shadow2 = last_shadow;
 241                     }
 242                     else
 243                     {
 244                         *shadows = shadow2->next;
 245                         shadow2 = *shadows;
 246                     }
 247                     free(to_free);
 248                 }
 249                 last_shadow = shadow2;
 250             }
 251         }
 252     }
 253     return angle_merge;
 254 }
 255
 256
 257
 258 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
 259                          uint32_t middle_angle, struct shadow_angle ** shadows,
 260                          uint16_t pos_in_map, char * fov_map)
 261 {
 262     struct shadow_angle * shadow_i;
 263     if (fov_map[pos_in_map] == 'v')
 264     {
 265         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 266         {
 267             if (   left_angle <=  shadow_i->left_angle
 268                 && right_angle >= shadow_i->right_angle)
 269             {
 270                 fov_map[pos_in_map] = 'H';
 271                 return 1;
 272             }
 273             if (   middle_angle < shadow_i->left_angle
 274                 && middle_angle > shadow_i->right_angle)
 275             {
 276                 fov_map[pos_in_map] = 'H';
 277             }
 278         }
 279     }
 280     return 0;
 281 }
 282
 283
 284
 285 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
 286  * new entry or as part of an existing shadow (swallowed whole or extending it).
 287  */
 288 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
 289                        struct shadow_angle ** shadows)
 290 {
 291     struct shadow_angle * shadow_i;
 292     if (!try_merging_angles(left_angle, right_angle, shadows))
 293     {
 294         struct shadow_angle * shadow;
 295         shadow = try_malloc(sizeof(struct shadow_angle), __func__);
 296         shadow->left_angle  = left_angle;
 297         shadow->right_angle = right_angle;
 298         shadow->next = NULL;
 299         if (*shadows)
 300         {
 301             for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 302             {
 303                 if (!shadow_i->next)
 304                 {
 305                     shadow_i->next = shadow;
 306                     return;
 307                 }
 308             }
 309         }
 310         *shadows = shadow;
 311     }
 312 }
 313
 314
 315
 316 static void free_angles(struct shadow_angle * angles)
 317 {
 318     if (angles->next)
 319     {
 320         free_angles(angles->next);
 321     }
 322     free(angles);
 323 }
 324
 325
 326
 327 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
 328                           struct yx_uint8 * test_pos,
 329                           struct shadow_angle ** shadows)
 330 {
 331     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
 332                                      - (hex_i * (CIRCLE / 6) / dist);
 333     int32_t right_angle_uncorrected =   left_angle_uncorrected
 334                                       - (CIRCLE / (6 * dist));
 335     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
 336     uint32_t right_angle = correct_angle(right_angle_uncorrected);
 337     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
 338     uint32_t middle_angle = 0;
 339     if (right_angle_1st)
 340     {
 341         middle_angle = right_angle + ((left_angle - right_angle) / 2);
 342     }
 343     uint16_t pos_in_map = test_pos->y * world.map.length + test_pos->x;
 344     uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
 345                                    shadows, pos_in_map, fov_map);
 346     if (!all_shaded && 'X' == world.map.cells[pos_in_map])
 347     {
 348         set_shadow(left_angle, right_angle_1st, shadows);
 349         if (right_angle_1st != right_angle)
 350         {
 351             left_angle = CIRCLE;
 352             set_shadow(left_angle, right_angle, shadows);
 353         }
 354     }
 355 }
 356
 357
 358
 359 static void update_map_memory(struct Thing * t_eye, uint32_t map_size)
 360 {
 361     if (!t_eye->mem_map)
 362     {
 363         t_eye->mem_map = try_malloc(map_size, __func__);
 364         memset(t_eye->mem_map, ' ', map_size);
 365     }
 366     uint32_t i;
 367     for (i = 0; i < map_size; i++)
 368     {
 369         if (' ' == t_eye->mem_map[i] && t_eye->fov_map[i] == 'v')
 370         {
 371             t_eye->mem_map[i] = world.map.cells[i];
 372         }
 373     }
 374     struct ThingInMemory * tm = t_eye->t_mem;
 375     struct ThingInMemory * tm_prev = NULL;
 376     struct ThingInMemory * tm_next = NULL;
 377     for (; tm != NULL; tm = tm_next)
 378     {
 379         tm_next = tm->next;
 380         if ('v' == t_eye->fov_map[tm->pos.y * world.map.length + tm->pos.x])
 381         {
 382             if (tm_prev)
 383             {
 384                 tm_prev->next = tm->next;
 385             }
 386             else
 387             {
 388                 t_eye->t_mem = tm->next;
 389             }
 390             free(tm);
 391             continue;
 392         }
 393         tm_prev = tm;
 394     }
 395     struct Thing * t = world.things;
 396     for (; t != NULL; t = t->next)
 397     {
 398         if (   !t->lifepoints
 399             && 'v' == t_eye->fov_map[t->pos.y * world.map.length + t->pos.x])
 400         {
 401             add_thing_to_memory_map(t_eye, t->type, t->pos.y, t->pos.x);
 402         }
 403     }
 404 }
 405
 406
 407
 408 extern void build_fov_map(struct Thing * t)
 409 {
 410     uint32_t map_size = world.map.length * world.map.length;
 411     t->fov_map = t->fov_map ? t->fov_map : try_malloc(map_size, __func__);
 412     memset(t->fov_map, 'v', map_size);
 413     struct yx_uint8 test_pos = t->pos;
 414     struct shadow_angle * shadows = NULL;
 415     char * circle_dirs = "xswedc";
 416     uint16_t dist;
 417     uint8_t first_round, circle_on_map;
 418     for (first_round = 1, dist = 1, circle_on_map = 1; circle_on_map; dist++)
 419     {
 420         if (!first_round)
 421         {
 422             mv_yx_in_dir_legal('c', &test_pos);
 423         }
 424         char dir = 'd';
 425         uint8_t i_dir = first_round = circle_on_map = 0;
 426         uint16_t i_dist, hex_i;
 427         for (hex_i = 0, i_dist = 1; hex_i < 6 * dist; i_dist++, hex_i++)
 428         {
 429             if (mv_yx_in_dir_legal(dir, &test_pos))
 430             {
 431                 eval_position(dist, hex_i, t->fov_map, &test_pos, &shadows);
 432                 circle_on_map = 1;
 433             }
 434             dir = circle_dirs[i_dir];
 435             if (dist == i_dist)
 436             {
 437                 i_dist = 0;
 438                 i_dir++;
 439             }
 440         }
 441     }
 442     mv_yx_in_dir_wrap(0, NULL, 1);
 443     free_angles(shadows);
 444     update_map_memory(t, map_size);
 445 }