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

   1 /* src/server/ai.c */
   2
   3 #include "ai.h"
   4 #include <stdint.h> /* uint8_t, uint32_t, UINT8_MAX */
   5 #include <string.h> /* strlen(), memset() */
   6 #include "../common/yx_uint16.h" /* struct yx_uint16 */
   7 #include "map_object_actions.h" /* get_moa_id_by_name() */
   8 #include "map_objects.h" /* struct MapObj */
   9 #include "world.h" /* global world */
  10
  11
  12
  13 /* Write into "neighbor_scores" scores for immediate neighbors to cell at
  14  * "pos_yx" (YX coordinates) and "pos_i" (arry_index) in "score_map". Directions
  15  * determining neighborhood are defined by the letters of "dir"; their order
  16  * also determines in what order scores are written into "neighbor_score".
  17  * "len_dirs" is to store the result of a previous strlen(dir) (so it does not
  18  * have to be called repeatedly and costly in dijkstra_map(); same reason for
  19  * "pos_i"'s redundancy.). "max_score" is written into "neighbor_scores" for
  20  * illegal directions (that from "pos_yx" would lead beyond the map's border).
  21  */
  22 static void get_neighbor_scores(char * dirs, uint8_t len_dirs,
  23                                 uint8_t * score_map, struct yx_uint16 pos_yx,
  24                                 uint32_t pos_i, uint8_t max_score,
  25                                 uint8_t * neighbor_scores);
  26
  27 /* Iterate over scored cells in "score_map" of world.map's 2D geometry. Compare
  28  * each cell's score against the scores of its immediate neighbors in "dirs"
  29  * directions; if at least one of these is lower, re-set the current cell's
  30  * score to one higher than its lowest neighbor score. Repeat this whole process
  31  * until all cells have settled on their final score. Ignore cells whose
  32  * position in "score_map" fits a non-island cell in world.map.cells. Expect
  33  * "max_score" to be the maximum score for cells, marking them as unreachable.
  34  */
  35 static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score);
  36
  37 /* Return char of direction ("N", "E", "S" or "W") of enemy with the shortest
  38  * path to "mo_target". If no enemy is around, return 0.
  39  */
  40 static char get_dir_to_nearest_enemy(struct MapObj * mo_target);
  41
  42
  43
  44 static void get_neighbor_scores(char * dirs, uint8_t len_dirs,
  45                                 uint8_t * score_map, struct yx_uint16 pos_yx,
  46                                 uint32_t pos_i, uint8_t max_score,
  47                                 uint8_t * neighbor_scores)
  48 {
  49     memset(neighbor_scores, max_score, len_dirs);
  50     uint8_t i_dirs;
  51     for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
  52     {
  53         if      ('N' == dirs[i_dirs] && pos_yx.y > 0)
  54         {
  55             neighbor_scores[i_dirs] = score_map[pos_i - world.map.size.x];
  56         }
  57         else if ('E' == dirs[i_dirs] && pos_yx.x < world.map.size.x - 1)
  58         {
  59             neighbor_scores[i_dirs] = score_map[pos_i + 1];
  60         }
  61         else if ('S' == dirs[i_dirs] && pos_yx.y < world.map.size.y - 1)
  62         {
  63             neighbor_scores[i_dirs] = score_map[pos_i + world.map.size.x];
  64         }
  65         else if ('W' == dirs[i_dirs] && pos_yx.x > 0)
  66         {
  67             neighbor_scores[i_dirs] = score_map[pos_i - 1];
  68         }
  69     }
  70 }
  71
  72
  73
  74 static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score)
  75 {
  76     uint8_t len_dirs = strlen(dirs);
  77     uint8_t neighbor_scores[len_dirs];
  78     struct yx_uint16 pos_yx;
  79     uint32_t pos_i;
  80     uint8_t i_scans, i_dirs, local_score, min_neighbor_score;
  81     uint8_t scores_still_changing = 1;
  82     for (i_scans = 0; scores_still_changing; i_scans++)
  83     {
  84         scores_still_changing = 0;
  85         for (pos_yx.y = 0, pos_i = 0; pos_yx.y < world.map.size.y; pos_yx.y++)
  86         {
  87             for (pos_yx.x = 0; pos_yx.x < world.map.size.x; pos_yx.x++, pos_i++)
  88             {
  89                 if ('.' == world.map.cells[pos_i])
  90                 {
  91                     local_score = score_map[pos_i];
  92                     get_neighbor_scores(dirs, len_dirs, score_map, pos_yx,
  93                                         pos_i, max_score, neighbor_scores);
  94                     min_neighbor_score = max_score;
  95                     for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
  96                     {
  97                         if (min_neighbor_score > neighbor_scores[i_dirs])
  98                         {
  99                             min_neighbor_score = neighbor_scores[i_dirs];
 100                         }
 101                     }
 102                     if (local_score > min_neighbor_score + 1)
 103                     {
 104                         score_map[pos_i] = min_neighbor_score + 1;
 105                         scores_still_changing = 1;
 106                     }
 107                 }
 108             }
 109         }
 110     }
 111 }
 112
 113
 114
 115 static char get_dir_to_nearest_enemy(struct MapObj * mo_target)
 116 {
 117     /* Calculate for each cell the distance to the nearest map actor that is
 118      * not "mo_target", with movement only possible in the directions of "dir".
 119      * (Actors' own cells start with a distance of 0 towards themselves.)
 120      */
 121     uint8_t max_score = UINT8_MAX; /* Score for cells treated as unreachable. */
 122     char * dirs = "NESW";
 123     uint8_t score_map[world.map.size.y * world.map.size.x];
 124     memset(score_map, max_score, world.map.size.y * world.map.size.x);
 125     struct MapObj * mo = world.map_objs;
 126     for (; mo != NULL; mo = mo->next)
 127     {
 128         if (!mo->lifepoints || mo == mo_target)
 129         {
 130             continue;
 131         }
 132         score_map[(mo->pos.y * world.map.size.x) + mo->pos.x] = 0;
 133     }
 134     dijkstra_map(dirs, score_map, max_score);
 135
 136     /* Return direction of "mo_target"'s lowest-scored neighbor cell. */
 137     uint8_t len_dirs = strlen(dirs);
 138     uint32_t pos_i = (mo_target->pos.y * world.map.size.x) + mo_target->pos.x;
 139     uint8_t neighbor_scores[len_dirs];
 140     get_neighbor_scores(dirs, len_dirs, score_map, mo_target->pos, pos_i,
 141                         max_score, neighbor_scores);
 142     char dir_to_nearest_enemy = 0;
 143     uint8_t min_neighbor_score = max_score;
 144     uint8_t i_dirs;
 145     for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
 146     {
 147         if (min_neighbor_score > neighbor_scores[i_dirs])
 148         {
 149             min_neighbor_score = neighbor_scores[i_dirs];
 150             dir_to_nearest_enemy = dirs[i_dirs];
 151         }
 152     }
 153     return dir_to_nearest_enemy;
 154 }
 155
 156
 157
 158 extern void ai(struct MapObj * mo)
 159 {
 160     mo->command = get_moa_id_by_name("wait");
 161     char sel = get_dir_to_nearest_enemy(mo);
 162     if (0 != sel)
 163     {
 164         mo->command = get_moa_id_by_name("move");
 165         mo->arg = sel;
 166     }
 167 }