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

   1 /* src/server/ai.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 "ai.h"
   9 #include <stdint.h> /* uint8_t, uint16_t, uint32_t, int16_t, UINT16_MAX */
  10 #include <stdlib.h> /* free() */
  11 #include "../common/try_malloc.h" /* try_malloc() */
  12 #include "hardcoded_strings.h" /* s */
  13 #include "thing_actions.h" /* get_thing_action_id_by_name() */
  14 #include "things.h" /* Thing, ThingType, ThingInMemory, get_thing_type() */
  15 #include "world.h" /* world */
  16
  17 #define N_DIRS 6
  18
  19
  20
  21 /* Return "score_map"["pos"] unless "check_inhabitant" and cell is inhabited. */
  22 static uint16_t set_neighbor_val(uint16_t * score_map, uint8_t check_inhabitant,
  23                                  uint16_t kill_score, uint16_t pos);
  24
  25 /* Write into "neighbors" scores of the N_DIRS immediate neighbors of the
  26  * "score_map" cell at "pos_i" (array index), as found in the directions
  27  * north-east, east, south-east etc. (clockwise order). Use "kill_score" for
  28  * illegal neighborhoods (i.e. if direction would lead beyond the map's border,
  29  * or, if "check_inhabitants" is non-zero, into animate-inhabited cell).
  30  */
  31 static void get_neighbor_scores(uint16_t * score_map, uint16_t pos_i,
  32                                 uint16_t kill_score, uint16_t * neighbors,
  33                                 uint8_t check_inhabitants);
  34
  35 /* Iterate over scored cells in "score_map" of world.map's geometry. Compare
  36  * each cell's score against the score of its immediate neighbors in N_DIRS
  37  * directions. If any neighbor's score is at least two points lower than the
  38  * current cell's score, re-set it to 1 point higher than its lowest-scored
  39  * neighbor. Repeat this whole process until all cells have settled on their
  40  * final score. Ignore cells whose score is greater than "max_score". Expect
  41  * "max_score" to be the maximum score for cells, marking them as unreachable.
  42  */
  43 static void dijkstra_map(uint16_t * score_map, uint16_t max_score);
  44
  45 /* Helpers to init_score_map(), realizing individual filters. */
  46 static uint8_t score_map_filter_attack(uint8_t filter, uint16_t * score_map,
  47                                        struct Thing * t_eye);
  48 static uint8_t score_map_filter_flee(uint8_t filter, uint16_t * score_map,
  49                                      struct Thing * t_eye);
  50 static uint8_t score_map_filter_consume(uint8_t filter, uint16_t * score_map,
  51                                         struct Thing * t_eye);
  52 static uint8_t score_map_filter_search(uint8_t filter, uint16_t * score_map,
  53                                        struct Thing * t_eye);
  54
  55 /* get_dir_to_nearest_target() helper: Prepare "score_map" for dijkstra_map(). */
  56 static void init_score_map(char filter, uint16_t * score_map, uint32_t map_size,
  57                            struct Thing * t_eye);
  58
  59 /* Helper to get_dir_to_nearest_target(). */
  60 static char get_dir_from_neighbors(char filter, struct Thing * t_eye,
  61                                    uint16_t * score_map);
  62
  63 /* Set (if possible) as "t_eye"'s command a move to the path to the path-wise
  64  * nearest target that is not "t_eye" and fits criteria set by "filter". On
  65  * success, return !0, else 0. Values for "filter":
  66  * "a": thing in FOV is animate, but of a type that is not "t_eye"'s, and
  67  *      starts out weaker than it is; build path as avoiding things of "t_eye"'s
  68  *      type
  69  * "f": neighbor cell (not inhabited by any animate thing) further away from
  70  *      animate thing not further than x steps away and in FOV and of a type
  71  *      that is not "t_eye"'s, and starts out stronger or as strong as "t_eye"
  72  *      is currently; or (cornered), if no such flight cell, but thing of above
  73  *      criteria is in neighbor cell, that cell
  74  * "c": thing in memorized map is consumable
  75  * "s": memory map cell with greatest-reachable degree of unexploredness
  76  */
  77 static uint8_t get_dir_to_nearest_target(struct Thing * t_eye, char filter);
  78
  79 /* Return 1 if any thing not "t_eye" is known and fulfills some criteria defined
  80  * by "filter", else 0. Values for "filter":
  81  * "a" or "f": thing in FOV is animate, but of type that not that of "t_eye",
  82  *             and starts out weaker ("a") / stronger ("f") than "t_eye" is
  83  * "c"       : thing in memorized map is consumable
  84  */
  85 static uint8_t seeing_thing(struct Thing * t_eye, char filter);
  86
  87 /* Return slot ID of strongest consumable in "t_owner"'s inventory, else -1. */
  88 static int16_t get_inventory_slot_to_consume(struct Thing * t_owner);
  89
  90 /* Return 1 if "t_standing" is standing on a consumable, else 0. */
  91 static uint8_t standing_on_consumable(struct Thing * t_standing);
  92
  93
  94
  95 static uint16_t set_neighbor_val(uint16_t * score_map, uint8_t check_inhabitant,
  96                                  uint16_t kill_score, uint16_t pos)
  97 {
  98     if (check_inhabitant)
  99     {
 100         struct Thing * t = world.things;
 101         for (; t; t = t->next)
 102         {
 103             if (t->lifepoints && pos == t->pos.y * world.map.length + t->pos.x)
 104             {
 105                 return kill_score;
 106             }
 107         }
 108     }
 109     return score_map[pos];
 110 }
 111
 112
 113
 114 static void get_neighbor_scores(uint16_t * score_map, uint16_t pos_i,
 115                                 uint16_t kill_score, uint16_t * neighbors,
 116                                 uint8_t check_inhabitants)
 117 {
 118     uint32_t map_size = world.map.length * world.map.length;
 119     uint8_t open_north     = pos_i >= world.map.length;
 120     uint8_t open_east      = pos_i + 1 % world.map.length;
 121     uint8_t open_south     = pos_i + world.map.length < map_size;
 122     uint8_t open_west      = pos_i % world.map.length;
 123     uint8_t is_indented    = (pos_i / world.map.length) % 2;
 124     uint8_t open_diag_west = is_indented || open_west;
 125     uint8_t open_diag_east = !is_indented || open_east;
 126     neighbors[0] = !(open_north && open_diag_east) ? kill_score :
 127                    set_neighbor_val(score_map, check_inhabitants, kill_score,
 128                                     pos_i - world.map.length + is_indented);
 129     neighbors[1] = !(open_east) ? kill_score :
 130                    set_neighbor_val(score_map, check_inhabitants, kill_score,
 131                                     pos_i + 1);
 132     neighbors[2] = !(open_south && open_diag_east) ? kill_score :
 133                    set_neighbor_val(score_map, check_inhabitants, kill_score,
 134                                     pos_i + world.map.length + is_indented);
 135     neighbors[3] = !(open_south && open_diag_west) ? kill_score :
 136                    set_neighbor_val(score_map, check_inhabitants, kill_score,
 137                                     pos_i + world.map.length - !is_indented);
 138     neighbors[4] = !(open_west) ? kill_score :
 139                    set_neighbor_val(score_map, check_inhabitants, kill_score,
 140                                     pos_i - 1);
 141     neighbors[5] = !(open_north && open_diag_west) ? kill_score :
 142                    set_neighbor_val(score_map, check_inhabitants, kill_score,
 143                                     pos_i - world.map.length - !is_indented);
 144 }
 145
 146
 147
 148 static void dijkstra_map(uint16_t * score_map, uint16_t max_score)
 149 {
 150     uint32_t map_size = world.map.length * world.map.length;
 151     uint32_t pos;
 152     uint16_t i_scans, neighbors[N_DIRS], min_neighbor;
 153     uint8_t scores_still_changing = 1;
 154     uint8_t i_dirs;
 155     for (i_scans = 0; scores_still_changing; i_scans++)
 156     {
 157         scores_still_changing = 0;
 158         for (pos = 0; pos < map_size; pos++)
 159         {
 160             if (score_map[pos] <= max_score)
 161             {
 162                 get_neighbor_scores(score_map, pos, max_score, neighbors, 0);
 163                 min_neighbor = max_score;
 164                 for (i_dirs = 0; i_dirs < N_DIRS; i_dirs++)
 165                 {
 166                     if (min_neighbor > neighbors[i_dirs])
 167                     {
 168                         min_neighbor = neighbors[i_dirs];
 169                     }
 170                 }
 171                 if (score_map[pos] > min_neighbor + 1)
 172                 {
 173                     score_map[pos] = min_neighbor + 1;
 174                     scores_still_changing = 1;
 175                 }
 176             }
 177         }
 178     }
 179 }
 180
 181
 182
 183 static uint8_t score_map_filter_attack(uint8_t filter, uint16_t * score_map,
 184                                        struct Thing * t_eye)
 185 {
 186     if ('a' != filter)
 187     {
 188         return 0;
 189     }
 190     struct Thing * t = world.things;
 191     for (; t; t = t->next)
 192     {
 193         if (   t != t_eye && t->lifepoints && t->type != t_eye->type
 194             && 'v' == t_eye->fov_map[t->pos.y*world.map.length + t->pos.x]
 195             && get_thing_type(t->type)->lifepoints < t_eye->lifepoints)
 196         {
 197             score_map[t->pos.y * world.map.length + t->pos.x] = 0;
 198         }
 199         else if (t->type == t_eye->type)
 200         {
 201             score_map[t->pos.y * world.map.length + t->pos.x] = UINT16_MAX;
 202         }
 203     }
 204     return 1;
 205 }
 206
 207
 208
 209 static uint8_t score_map_filter_flee(uint8_t filter, uint16_t * score_map,
 210                                      struct Thing * t_eye)
 211 {
 212     if ('f' != filter)
 213     {
 214         return 0;
 215     }
 216     struct Thing * t = world.things;
 217     for (; t; t = t->next)
 218     {
 219         if (   t->lifepoints && t->type != t_eye->type
 220             && 'v' == t_eye->fov_map[t->pos.y*world.map.length + t->pos.x]
 221             && get_thing_type(t->type)->lifepoints >= t_eye->lifepoints)
 222         {
 223             score_map[t->pos.y * world.map.length + t->pos.x] = 0;
 224         }
 225     }
 226     return 1;
 227 }
 228
 229
 230
 231 static uint8_t score_map_filter_consume(uint8_t filter, uint16_t * score_map,
 232                                         struct Thing * t_eye)
 233 {
 234     if ('c' != filter)
 235     {
 236         return 0;
 237     }
 238     struct ThingInMemory * tm = t_eye->t_mem;
 239     for (; tm; tm = tm->next)
 240     {
 241         if (   ' ' != t_eye->mem_map[tm->pos.y * world.map.length + tm->pos.x]
 242             && get_thing_type(tm->type)->consumable)
 243         {
 244             score_map[tm->pos.y * world.map.length + tm->pos.x] = 0;
 245         }
 246     }
 247     return 1;
 248 }
 249
 250
 251
 252 static uint8_t score_map_filter_search(uint8_t filter, uint16_t * score_map,
 253                                        struct Thing * t_eye)
 254 {
 255     if (!(('0' < filter && '9' >= filter) || ' ' == filter))
 256     {
 257         return 0;
 258     }
 259     uint32_t i;
 260     for (i = 0; i < (uint32_t) (world.map.length * world.map.length); i++)
 261     {
 262         score_map[i] = filter == t_eye->mem_depth_map[i] ? 0 : score_map[i];
 263     }
 264     return 1;
 265 }
 266
 267
 268
 269 static void init_score_map(char filter, uint16_t * score_map, uint32_t map_size,
 270                            struct Thing * t_eye)
 271 {
 272     uint32_t i;
 273     for (i = 0; i < map_size; i++)
 274     {
 275         score_map[i] = UINT16_MAX;
 276         if ('.' == t_eye->mem_map[i])
 277         {
 278             score_map[i] = UINT16_MAX-1;
 279         }
 280     }
 281     if (   score_map_filter_attack(filter, score_map, t_eye)
 282         || score_map_filter_flee(filter, score_map, t_eye)
 283         || score_map_filter_consume(filter, score_map, t_eye)
 284         || score_map_filter_search(filter, score_map, t_eye))
 285     {
 286     }
 287 }
 288
 289
 290 static char get_dir_from_neighbors(char filter, struct Thing * t_eye,
 291                                    uint16_t * score_map)
 292 {
 293     char dir_to_nearest_target = 0;
 294     uint16_t pos_i = (t_eye->pos.y * world.map.length) + t_eye->pos.x;
 295     char * dirs = "edcxsw";   /* get_neighbor_scores()'s clockwise dir order. */
 296     uint16_t neighbors[N_DIRS];
 297     get_neighbor_scores(score_map, pos_i, UINT16_MAX, neighbors, 'f'==filter);
 298     uint16_t minmax_neighbor = 'f' == filter ? 0 : UINT16_MAX-1;
 299     uint8_t i;
 300     for (i = 0; i < N_DIRS; i++)
 301     {
 302         if (   (   'f' == filter && score_map[pos_i] < neighbors[i]
 303                 && minmax_neighbor < neighbors[i] && UINT16_MAX != neighbors[i])
 304             || ('f' != filter && minmax_neighbor > neighbors[i]))
 305         {
 306             minmax_neighbor = neighbors[i];
 307             dir_to_nearest_target = dirs[i];
 308         }
 309     }
 310     if ('f' == filter)
 311     {
 312         if (!dir_to_nearest_target && 1 == score_map[pos_i])
 313         {
 314             get_neighbor_scores(score_map, pos_i, UINT16_MAX, neighbors, 0);
 315             for (i = 0; i < N_DIRS; i++)
 316             {
 317                 if (!neighbors[i])
 318                 {
 319                     dir_to_nearest_target = dirs[i];
 320                     break;
 321                 }
 322             }
 323         }
 324         else if (dir_to_nearest_target && minmax_neighbor > 3)
 325         {
 326             dir_to_nearest_target = 0;
 327         }
 328     }
 329     return dir_to_nearest_target;
 330 }
 331
 332
 333
 334 static uint8_t get_dir_to_nearest_target(struct Thing * t_eye, char filter)
 335 {
 336     char dir_to_nearest_target = 0;
 337     uint8_t mem_depth_char = ' ';
 338     uint8_t run_i = 's' == filter ? 9 /* max explored mem depth age */ + 1 : 1;
 339     while (    run_i && !dir_to_nearest_target
 340            && ('s' == filter || seeing_thing(t_eye, filter)))
 341     {
 342         run_i--;
 343         uint32_t map_size = world.map.length * world.map.length;
 344         uint16_t * score_map = try_malloc(map_size * sizeof(uint16_t),__func__);
 345         init_score_map('s' == filter ? mem_depth_char : filter,
 346                        score_map, map_size, t_eye);
 347         mem_depth_char = ' ' == mem_depth_char ? '9' : mem_depth_char - 1;
 348         dijkstra_map(score_map, UINT16_MAX-1);
 349         dir_to_nearest_target = get_dir_from_neighbors(filter,t_eye,score_map);
 350         free(score_map);
 351         if (dir_to_nearest_target)
 352         {
 353             t_eye->command = get_thing_action_id_by_name(s[S_CMD_MOVE]);
 354             t_eye->arg = dir_to_nearest_target;
 355         }
 356     }
 357     return dir_to_nearest_target;
 358 }
 359
 360
 361
 362 static uint8_t seeing_thing(struct Thing * t_eye, char filter)
 363 {
 364     if (t_eye->fov_map && ('a' == filter || 'f' == filter))
 365     {
 366         struct Thing * t = world.things;
 367         for (; t; t = t->next)
 368         {
 369             if (   t != t_eye && t->lifepoints && t->type != t_eye->type
 370                 && 'v' == t_eye->fov_map[t->pos.y*world.map.length + t->pos.x])
 371             {
 372                 struct ThingType * tt = get_thing_type(t->type);
 373                 if (   ('f' == filter && tt->lifepoints >= t_eye->lifepoints)
 374                     || ('a' == filter && tt->lifepoints <  t_eye->lifepoints))
 375                 {
 376                     return 1;
 377                 }
 378             }
 379         }
 380     }
 381     else if (t_eye->mem_map && 'c' == filter)
 382     {
 383         struct ThingInMemory * tm = t_eye->t_mem;
 384         for (; tm; tm = tm->next)
 385         {
 386             if (     ' ' != t_eye->mem_map[tm->pos.y*world.map.length+tm->pos.x]
 387                 && get_thing_type(tm->type)->consumable)
 388             {
 389                 return 1;
 390             }
 391         }
 392     }
 393     return 0;
 394 }
 395
 396
 397
 398 static int16_t get_inventory_slot_to_consume(struct Thing * t_owner)
 399 {
 400     uint8_t compare_consumability = 0;
 401     int16_t selection = -1;
 402     struct Thing * t = t_owner->owns;;
 403     uint8_t i;
 404     for (i = 0; t; t = t->next, i++)
 405     {
 406         struct ThingType * tt = get_thing_type(t->type);
 407         if (tt->consumable > compare_consumability)
 408         {
 409             compare_consumability = tt->consumable;
 410             selection = i;
 411         }
 412     }
 413     return selection;
 414 }
 415
 416
 417
 418 static uint8_t standing_on_consumable(struct Thing * t_standing)
 419 {
 420     struct Thing * t = world.things;
 421     for (; t; t = t->next)
 422     {
 423         if (   t != t_standing
 424             && t->pos.y == t_standing->pos.y && t->pos.x == t_standing->pos.x
 425             && get_thing_type(t->type)->consumable)
 426         {
 427             return 1;
 428         }
 429     }
 430     return 0;
 431 }
 432
 433
 434
 435 extern void ai(struct Thing * t)
 436 {
 437     t->command = get_thing_action_id_by_name(s[S_CMD_WAIT]);
 438     if (!get_dir_to_nearest_target(t, 'f'))
 439     {
 440         int16_t sel = get_inventory_slot_to_consume(t);
 441         if (-1 != sel)
 442         {
 443             t->command = get_thing_action_id_by_name(s[S_CMD_USE]);
 444             t->arg = (uint8_t) sel;
 445         }
 446         else if (standing_on_consumable(t))
 447         {
 448             t->command = get_thing_action_id_by_name(s[S_CMD_PICKUP]);
 449         }
 450         else if (   !get_dir_to_nearest_target(t, 'c')
 451                  && !get_dir_to_nearest_target(t, 'a'))
 452         {
 453             get_dir_to_nearest_target(t, 's');
 454         }
 455     }
 456 }