plomlompom.com Git - plomrogue/blob - src/server/field_of_view.c

   1 /* src/server/field_of_view.c
   2  *
   3  * This file is part of PlomRogue. PlomRogue is licensed under the GPL version 3
   4  * or any later version. For details on its copyright, license, and warranties,
   5  * see the file NOTICE in the root directory of the PlomRogue source package.
   6  */
   7
   8 #include "field_of_view.h"
   9 #include <math.h> /* pow() */
  10 #include <stddef.h> /* NULL */
  11 #include <stdint.h> /* uint8_t, uint16_t, uint32_t, int32_t, UINT8_MAX */
  12 #include <stdlib.h> /* free() */
  13 #include <string.h> /* memset() */
  14 #include "../common/rexit.h" /* exit_trouble() */
  15 #include "../common/try_malloc.h" /* try_malloc() */
  16 #include "../common/yx_uint8.h" /* yx_uint8 */
  17 #include "map.h" /* mv_yx_in_dir_legal(), init_empty_map() */
  18 #include "rrand.h" /* rrand() */
  19 #include "things.h" /* Thing, ThingInMemory, add_thing_to_memory_map() */
  20 #include "world.h" /* world  */
  21
  22
  23
  24 /* Number of degrees a circle is divided into. The greater it is, the greater
  25  * the angle precision. But make it one whole zero larger and bizarre FOV bugs
  26  * appear on large maps, probably due to value overflows (TODO: more research!).
  27  */
  28 #define CIRCLE 3600000
  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 /* Recalculate angle < 0 or > CIRCLE to a value between these two limits. */
  43 static uint32_t correct_angle(int32_t angle);
  44
  45 /* Try merging the angle between "left_angle" and "right_angle" to "shadow" if
  46  * it meets the shadow from the right or the left. Returns 1 on success, else 0.
  47  */
  48 static uint8_t try_merge(struct shadow_angle * shadow,
  49                          uint32_t left_angle, uint32_t right_angle);
  50
  51 /* Try merging the shadow angle between "left_angle" and "right_angle" into an
  52  * existing shadow angle in "shadows". On success, see if this leads to any
  53  * additional shadow angle overlaps and merge these accordingly. Return 1 on
  54  * success, else 0.
  55  */
  56 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
  57                                   struct shadow_angle ** shadows);
  58
  59 /* Test whether angle between "left_angle" and "right_angle", or at least
  60  * "middle_angle", is captured inside one of the shadow angles in "shadows". If
  61  * so, set hex in "fov_map" indexed by "pos_in_map" to 'H'. If the whole angle
  62  * and not just "middle_angle" is captured, return 1. Any other case: 0.
  63  */
  64 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
  65                          uint32_t middle_angle, struct shadow_angle ** shadows,
  66                          uint16_t pos_in_map, char * fov_map);
  67
  68 /* Free shadow angles list "angles". */
  69 static void free_angles(struct shadow_angle * angles);
  70
  71 /* Evaluate map position "test_pos" in distance "dist" to the view origin, and
  72  * on the circle of that distance to the origin on hex "hex_i" (as counted from
  73  * the circle's rightmost point), for setting shaded hexes in "fov_map" and
  74  * potentially adding a new shadow to linked shadow angle list "shadows".
  75  */
  76 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
  77                           struct yx_uint8 * test_pos,
  78                           struct shadow_angle ** shadows);
  79
  80 /* Update "t_eye"'s things-on-map memory by removing from its .t_mem all
  81  * memorized thing in FOV, and adding inanimate things in FOV to it.
  82  */
  83 static void add_things_to_map_memory(struct Thing * t_eye);
  84
  85
  86
  87 static uint32_t correct_angle(int32_t angle)
  88 {
  89     while (angle < 0)
  90     {
  91         angle = angle + CIRCLE;
  92     }
  93     while (angle > CIRCLE)
  94     {
  95         angle = angle - CIRCLE;
  96     }
  97     return angle;
  98 }
  99
 100
 101
 102 static uint8_t try_merge(struct shadow_angle * shadow,
 103                          uint32_t left_angle, uint32_t right_angle)
 104 {
 105     if      (   shadow->right_angle <= left_angle + 1
 106              && shadow->right_angle >= right_angle)
 107     {
 108         shadow->right_angle = right_angle;
 109     }
 110     else if (   shadow->left_angle + 1 >= right_angle
 111              && shadow->left_angle     <= left_angle)
 112     {
 113         shadow->left_angle = left_angle;
 114     }
 115     else
 116     {
 117         return 0;
 118     }
 119     return 1;
 120 }
 121
 122
 123
 124 static uint8_t try_merging_angles(uint32_t left_angle, uint32_t right_angle,
 125                                   struct shadow_angle ** shadows)
 126 {
 127     uint8_t angle_merge = 0;
 128     struct shadow_angle * shadow;
 129     for (shadow = *shadows; shadow; shadow = shadow->next)
 130     {
 131         if (try_merge(shadow, left_angle, right_angle))
 132         {
 133             angle_merge = 1;
 134         }
 135     }
 136     if (angle_merge)
 137     {
 138         struct shadow_angle * shadow1;
 139         for (shadow1 = *shadows; shadow1; shadow1 = shadow1->next)
 140         {
 141             struct shadow_angle * last_shadow = NULL;
 142             struct shadow_angle * shadow2;
 143             for (shadow2 = *shadows; shadow2; shadow2 = shadow2->next)
 144             {
 145                 if (   shadow1 != shadow2
 146                     && try_merge(shadow1, shadow2->left_angle,
 147                                           shadow2->right_angle))
 148                 {
 149                     struct shadow_angle * to_free = shadow2;
 150                     if (last_shadow)
 151                     {
 152                         last_shadow->next = shadow2->next;
 153                         shadow2 = last_shadow;
 154                     }
 155                     else
 156                     {
 157                         *shadows = shadow2->next;
 158                         shadow2 = *shadows;
 159                     }
 160                     free(to_free);
 161                 }
 162                 last_shadow = shadow2;
 163             }
 164         }
 165     }
 166     return angle_merge;
 167 }
 168
 169
 170
 171 static uint8_t shade_hex(uint32_t left_angle, uint32_t right_angle,
 172                          uint32_t middle_angle, struct shadow_angle ** shadows,
 173                          uint16_t pos_in_map, char * fov_map)
 174 {
 175     struct shadow_angle * shadow_i;
 176     if (fov_map[pos_in_map] == 'v')
 177     {
 178         for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 179         {
 180             if (   left_angle <=  shadow_i->left_angle
 181                 && right_angle >= shadow_i->right_angle)
 182             {
 183                 fov_map[pos_in_map] = 'H';
 184                 return 1;
 185             }
 186             if (   middle_angle < shadow_i->left_angle
 187                 && middle_angle > shadow_i->right_angle)
 188             {
 189                 fov_map[pos_in_map] = 'H';
 190             }
 191         }
 192     }
 193     return 0;
 194 }
 195
 196
 197
 198 /* To "shadows", add shadow defined by "left_angle" and "right_angle", either as
 199  * new entry or as part of an existing shadow (swallowed whole or extending it).
 200  */
 201 static void set_shadow(uint32_t left_angle, uint32_t right_angle,
 202                        struct shadow_angle ** shadows)
 203 {
 204     struct shadow_angle * shadow_i;
 205     if (!try_merging_angles(left_angle, right_angle, shadows))
 206     {
 207         struct shadow_angle * shadow;
 208         shadow = try_malloc(sizeof(struct shadow_angle), __func__);
 209         shadow->left_angle  = left_angle;
 210         shadow->right_angle = right_angle;
 211         shadow->next = NULL;
 212         if (*shadows)
 213         {
 214             for (shadow_i = *shadows; shadow_i; shadow_i = shadow_i->next)
 215             {
 216                 if (!shadow_i->next)
 217                 {
 218                     shadow_i->next = shadow;
 219                     return;
 220                 }
 221             }
 222         }
 223         *shadows = shadow;
 224     }
 225 }
 226
 227
 228
 229 static void free_angles(struct shadow_angle * angles)
 230 {
 231     if (angles->next)
 232     {
 233         free_angles(angles->next);
 234     }
 235     free(angles);
 236 }
 237
 238
 239
 240 static void eval_position(uint16_t dist, uint16_t hex_i, char * fov_map,
 241                           struct yx_uint8 * test_pos,
 242                           struct shadow_angle ** shadows)
 243 {
 244     int32_t left_angle_uncorrected =   ((CIRCLE / 12) / dist)
 245                                      - (hex_i * (CIRCLE / 6) / dist);
 246     int32_t right_angle_uncorrected =   left_angle_uncorrected
 247                                       - (CIRCLE / (6 * dist));
 248     uint32_t left_angle  = correct_angle(left_angle_uncorrected);
 249     uint32_t right_angle = correct_angle(right_angle_uncorrected);
 250     uint32_t right_angle_1st = right_angle > left_angle ? 0 : right_angle;
 251     uint32_t middle_angle = 0;
 252     if (right_angle_1st)
 253     {
 254         middle_angle = right_angle + ((left_angle - right_angle) / 2);
 255     }
 256     uint16_t pos_in_map = test_pos->y * world.map.length + test_pos->x;
 257     uint8_t all_shaded = shade_hex(left_angle, right_angle_1st, middle_angle,
 258                                    shadows, pos_in_map, fov_map);
 259     if (!all_shaded && 'X' == world.map.cells[pos_in_map])
 260     {
 261         set_shadow(left_angle, right_angle_1st, shadows);
 262         if (right_angle_1st != right_angle)
 263         {
 264             left_angle = CIRCLE;
 265             set_shadow(left_angle, right_angle, shadows);
 266         }
 267     }
 268 }
 269
 270
 271
 272 static void add_things_to_map_memory(struct Thing * t_eye)
 273 {
 274     struct ThingInMemory * tm = t_eye->t_mem;
 275     struct ThingInMemory * tm_prev = NULL;
 276     struct ThingInMemory * tm_next = NULL;
 277     for (; tm; tm = tm_next)
 278     {
 279         tm_next = tm->next;
 280         if ('v' == t_eye->fov_map[tm->pos.y * world.map.length + tm->pos.x])
 281         {
 282             if (tm_prev)
 283             {
 284                 tm_prev->next = tm->next;
 285             }
 286             else
 287             {
 288                 t_eye->t_mem = tm->next;
 289             }
 290             free(tm);
 291             continue;
 292         }
 293         tm_prev = tm;
 294     }
 295     struct Thing * t = world.things;
 296     for (; t; t = t->next)
 297     {
 298         if (   !t->lifepoints
 299             && 'v' == t_eye->fov_map[t->pos.y * world.map.length + t->pos.x])
 300         {
 301             add_thing_to_memory_map(t_eye, t->type, t->pos.y, t->pos.x);
 302         }
 303     }
 304 }
 305
 306
 307
 308 extern void update_map_memory(struct Thing * t_eye)
 309 {
 310     if (!t_eye->mem_map)
 311     {
 312         init_empty_map(&(t_eye->mem_map));
 313     }
 314     if (!t_eye->mem_depth_map)
 315     {
 316         init_empty_map(&(t_eye->mem_depth_map));
 317     }
 318     uint32_t i;
 319     for (i = 0; i < (uint32_t) (world.map.length * world.map.length); i++)
 320     {
 321         if ('v' == t_eye->fov_map[i])
 322         {
 323             t_eye->mem_depth_map[i] = '0';
 324             if (' ' == t_eye->mem_map[i])
 325             {
 326                 t_eye->mem_map[i] = world.map.cells[i];
 327             }
 328             continue;
 329         }
 330         if (   '0' <= t_eye->mem_depth_map[i] && '9' > t_eye->mem_depth_map[i]
 331             && !(rrand() % (uint16_t) pow(2, t_eye->mem_depth_map[i] - 48)))
 332         {
 333             t_eye->mem_depth_map[i]++;
 334         }
 335     }
 336     add_things_to_map_memory(t_eye);
 337 }
 338
 339
 340
 341 extern void build_fov_map(struct Thing * t)
 342 {
 343     uint32_t map_size = world.map.length * world.map.length;
 344     t->fov_map = t->fov_map ? t->fov_map : try_malloc(map_size, __func__);
 345     memset(t->fov_map, 'v', map_size);
 346     struct shadow_angle * shadows = NULL;
 347     struct yx_uint8 test_pos = t->pos;
 348     char * circledirs_string = "xswedc";
 349     uint16_t circle_i;
 350     uint8_t circle_is_on_map;
 351     for (circle_i = 1, circle_is_on_map = 1; circle_is_on_map; circle_i++)
 352     {
 353         circle_is_on_map = 0;
 354         if (1 < circle_i)                      /* All circles but the 1st are */
 355         {                                      /* moved into starting from a  */
 356             mv_yx_in_dir_legal('c', &test_pos);/* previous circle's last hex, */
 357         }                                      /* i.e. from the upper left.   */
 358         char dir_char = 'd'; /* Circle's 1st hex is entered by rightward move.*/
 359         uint8_t dir_char_pos_in_circledirs_string = UINT8_MAX;
 360         uint16_t dist_i, hex_i;
 361         for (hex_i=0, dist_i=circle_i; hex_i < 6 * circle_i; dist_i++, hex_i++)
 362         {
 363             if (circle_i < dist_i)
 364             {
 365                 dist_i = 1;
 366                 dir_char=circledirs_string[++dir_char_pos_in_circledirs_string];
 367             }
 368             if (mv_yx_in_dir_legal(dir_char, &test_pos))
 369             {
 370                 eval_position(circle_i, hex_i, t->fov_map, &test_pos, &shadows);
 371                 circle_is_on_map = 1;
 372             }
 373         }
 374     }
 375     mv_yx_in_dir_legal(0, NULL);
 376     free_angles(shadows);
 377 }