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