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 */
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).
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);
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.
35 static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score);
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.
40 static char get_dir_to_nearest_enemy(struct MapObj * mo_target);
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)
49 memset(neighbor_scores, max_score, len_dirs);
51 for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
53 if ('N' == dirs[i_dirs] && pos_yx.y > 0)
55 neighbor_scores[i_dirs] = score_map[pos_i - world.map.size.x];
57 else if ('E' == dirs[i_dirs] && pos_yx.x < world.map.size.x - 1)
59 neighbor_scores[i_dirs] = score_map[pos_i + 1];
61 else if ('S' == dirs[i_dirs] && pos_yx.y < world.map.size.y - 1)
63 neighbor_scores[i_dirs] = score_map[pos_i + world.map.size.x];
65 else if ('W' == dirs[i_dirs] && pos_yx.x > 0)
67 neighbor_scores[i_dirs] = score_map[pos_i - 1];
74 static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score)
76 uint8_t len_dirs = strlen(dirs);
77 uint8_t neighbor_scores[len_dirs];
78 struct yx_uint16 pos_yx;
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++)
84 scores_still_changing = 0;
85 for (pos_yx.y = 0, pos_i = 0; pos_yx.y < world.map.size.y; pos_yx.y++)
87 for (pos_yx.x = 0; pos_yx.x < world.map.size.x; pos_yx.x++, pos_i++)
89 if ('.' == world.map.cells[pos_i])
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++)
97 if (min_neighbor_score > neighbor_scores[i_dirs])
99 min_neighbor_score = neighbor_scores[i_dirs];
102 if (local_score > min_neighbor_score + 1)
104 score_map[pos_i] = min_neighbor_score + 1;
105 scores_still_changing = 1;
115 static char get_dir_to_nearest_enemy(struct MapObj * mo_target)
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.)
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)
128 if (!mo->lifepoints || mo == mo_target)
132 score_map[(mo->pos.y * world.map.size.x) + mo->pos.x] = 0;
134 dijkstra_map(dirs, score_map, max_score);
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;
145 for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
147 if (min_neighbor_score > neighbor_scores[i_dirs])
149 min_neighbor_score = neighbor_scores[i_dirs];
150 dir_to_nearest_enemy = dirs[i_dirs];
153 return dir_to_nearest_enemy;
158 extern void ai(struct MapObj * mo)
160 mo->command = get_moa_id_by_name("wait");
161 char sel = get_dir_to_nearest_enemy(mo);
164 mo->command = get_moa_id_by_name("move");