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