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 memset(neighbor_scores, max_score, len_dirs);
29 for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
31 if ('N' == dirs[i_dirs] && pos_yx.y > 0)
33 neighbor_scores[i_dirs] = score_map[pos_i - world.map.size.x];
35 else if ('E' == dirs[i_dirs] && pos_yx.x < world.map.size.x - 1)
37 neighbor_scores[i_dirs] = score_map[pos_i + 1];
39 else if ('S' == dirs[i_dirs] && pos_yx.y < world.map.size.y - 1)
41 neighbor_scores[i_dirs] = score_map[pos_i + world.map.size.x];
43 else if ('W' == dirs[i_dirs] && pos_yx.x > 0)
45 neighbor_scores[i_dirs] = score_map[pos_i - 1];
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.
60 static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score)
62 uint8_t len_dirs = strlen(dirs);
63 uint8_t neighbor_scores[len_dirs];
64 struct yx_uint16 pos_yx;
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++)
70 scores_still_changing = 0;
71 for (pos_yx.y = 0, pos_i = 0; pos_yx.y < world.map.size.y; pos_yx.y++)
73 for (pos_yx.x = 0; pos_yx.x < world.map.size.x; pos_yx.x++, pos_i++)
75 if ('.' == world.map.cells[pos_i])
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++)
83 if (min_neighbor_score > neighbor_scores[i_dirs])
85 min_neighbor_score = neighbor_scores[i_dirs];
88 if (local_score > min_neighbor_score + 1)
90 score_map[pos_i] = min_neighbor_score + 1;
91 scores_still_changing = 1;
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.
104 static char get_dir_to_nearest_enemy(struct MapObj * mo_target)
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.)
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)
117 if (!mo->lifepoints || mo == mo_target)
121 score_map[(mo->pos.y * world.map.size.x) + mo->pos.x] = 0;
123 dijkstra_map(dirs, score_map, max_score);
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;
134 for (i_dirs = 0; i_dirs < len_dirs; i_dirs++)
136 if (min_neighbor_score > neighbor_scores[i_dirs])
138 min_neighbor_score = neighbor_scores[i_dirs];
139 dir_to_nearest_enemy = dirs[i_dirs];
142 return dir_to_nearest_enemy;
147 extern void ai(struct MapObj * mo)
149 mo->command = get_moa_id_by_name("wait");
150 char sel = get_dir_to_nearest_enemy(mo);
153 mo->command = get_moa_id_by_name("move");