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     memset(neighbor_scores, max_score, len_dirs);
  28     uint8_t i_dirs;
  29     for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
  30     {
  31         if      ('N' == dirs[i_dirs] && pos_yx.y > 0)
  32         {
  33             neighbor_scores[i_dirs] = score_map[pos_i - world.map.size.x];
  34         }
  35         else if ('E' == dirs[i_dirs] && pos_yx.x < world.map.size.x - 1)
  36         {
  37             neighbor_scores[i_dirs] = score_map[pos_i + 1];
  38         }
  39         else if ('S' == dirs[i_dirs] && pos_yx.y < world.map.size.y - 1)
  40         {
  41             neighbor_scores[i_dirs] = score_map[pos_i + world.map.size.x];
  42         }
  43         else if ('W' == dirs[i_dirs] && pos_yx.x > 0)
  44         {
  45             neighbor_scores[i_dirs] = score_map[pos_i - 1];
  46         }
  47     }
  48 }
  49
  50
  51
  52 /* Iterate over scored cells in "score_map" of world.map's 2D geometry. Compare
  53  * each cell's score against the scores of its immediate neighbors in "dirs"
  54  * directions; if at least one of these is lower, re-set the current cell's
  55  * score to one higher than its lowest neighbor score. Repeat this whole process
  56  * until all cells have settled on their final score. Ignore cells whose
  57  * position in "score_map" fits a non-island cell in world.map.cells. Expect
  58  * "max_score" to be the maximum score for cells, marking them as unreachable.
  59  */
  60 static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score)
  61 {
  62     uint8_t len_dirs = strlen(dirs);
  63     uint8_t neighbor_scores[len_dirs];
  64     struct yx_uint16 pos_yx;
  65     uint32_t pos_i;
  66     uint8_t i_scans, i_dirs, local_score, min_neighbor_score;
  67     uint8_t scores_still_changing = 1;
  68     for (i_scans = 0; scores_still_changing; i_scans++)
  69     {
  70         scores_still_changing = 0;
  71         for (pos_yx.y = 0, pos_i = 0; pos_yx.y < world.map.size.y; pos_yx.y++)
  72         {
  73             for (pos_yx.x = 0; pos_yx.x < world.map.size.x; pos_yx.x++, pos_i++)
  74             {
  75                 if ('.' == world.map.cells[pos_i])
  76                 {
  77                     local_score = score_map[pos_i];
  78                     get_neighbor_scores(dirs, len_dirs, score_map, pos_yx,
  79                                         pos_i, max_score, neighbor_scores);
  80                     min_neighbor_score = max_score;
  81                     for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
  82                     {
  83                         if (min_neighbor_score > neighbor_scores[i_dirs])
  84                         {
  85                             min_neighbor_score = neighbor_scores[i_dirs];
  86                         }
  87                     }
  88                     if (local_score > min_neighbor_score + 1)
  89                     {
  90                         score_map[pos_i] = min_neighbor_score + 1;
  91                         scores_still_changing = 1;
  92                     }
  93                 }
  94             }
  95         }
  96     }
  97 }
  98
  99
 100
 101 /* Return char of direction ("N", "E", "S" or "W") of enemy with the shortest
 102  * path to "mo_target". If no enemy is around, return 0.
 103  */
 104 static char get_dir_to_nearest_enemy(struct MapObj * mo_target)
 105 {
 106     /* Calculate for each cell the distance to the nearest map actor that is
 107      * not "mo_target", with movement only possible in the directions of "dir".
 108      * (Actor's own cells start with a distance of 0 towards themselves.)
 109      */
 110     uint8_t max_score = UINT8_MAX; /* Score for cells treated as unreachable. */
 111     char * dirs = "NESW";
 112     uint8_t score_map[world.map.size.y * world.map.size.x];
 113     memset(score_map, max_score, world.map.size.y * world.map.size.x);
 114     struct MapObj * mo = world.map_objs;
 115     for (; mo != NULL; mo = mo->next)
 116     {
 117         if (!mo->lifepoints || mo == mo_target)
 118         {
 119             continue;
 120         }
 121         score_map[(mo->pos.y * world.map.size.x) + mo->pos.x] = 0;
 122     }
 123     dijkstra_map(dirs, score_map, max_score);
 124
 125     /* Return direction of "mo_target"'s lowest-scored neighbor cell. */
 126     uint8_t len_dirs = strlen(dirs);
 127     uint32_t pos_i = (mo_target->pos.y * world.map.size.x) + mo_target->pos.x;
 128     uint8_t neighbor_scores[len_dirs];
 129     get_neighbor_scores(dirs, len_dirs, score_map, mo_target->pos, pos_i,
 130                         max_score, neighbor_scores);
 131     char dir_to_nearest_enemy = 0;
 132     uint8_t min_neighbor_score = max_score;
 133     uint8_t i_dirs;
 134     for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
 135     {
 136         if (min_neighbor_score > neighbor_scores[i_dirs])
 137         {
 138             min_neighbor_score = neighbor_scores[i_dirs];
 139             dir_to_nearest_enemy = dirs[i_dirs];
 140         }
 141     }
 142     return dir_to_nearest_enemy;
 143 }
 144
 145
 146
 147 extern void ai(struct MapObj * mo)
 148 {
 149     mo->command = get_moa_id_by_name("wait");
 150     char sel = get_dir_to_nearest_enemy(mo);
 151     if (0 != sel)
 152     {
 153         mo->command = get_moa_id_by_name("move");
 154         mo->arg = sel;
 155     }
 156 }