home · contact · privacy
Maps are always squares, therefore define only their edge lengths.
[plomrogue] / src / server / ai.c
1 /* src/server/ai.c */
2
3 #include "ai.h"
4 #include <stddef.h> /* NULL */
5 #include <stdint.h> /* uint8_t, uint16_t, uint32_t, UINT16_MAX */
6 #include <stdlib.h> /* free() */
7 #include "../common/try_malloc.h" /* try_malloc() */
8 #include "field_of_view.h" /* VISIBLE */
9 #include "map_object_actions.h" /* get_moa_id_by_name() */
10 #include "map_objects.h" /* struct MapObj */
11 #include "world.h" /* global world */
12
13
14
15 #define N_DIRS 6
16
17
18
19 /* Write into "neighbors" scores of the N_DIRS immediate neighbors of the
20  * "score_map" cell at "pos_i" (array index), as found in the directions
21  * north-east, east, south-east etc. (clockwise order). Use "max_score" for
22  * illegal neighborhoods (i.e. if direction would lead beyond the map's border).
23  */
24 static void get_neighbor_scores(uint16_t * score_map, uint16_t pos_i,
25                                 uint16_t max_score, uint16_t * neighbors);
26
27 /* Iterate over scored cells in "score_map" of world.map's geometry. Compare
28  * each cell's score against the score of its immediate neighbors in N_DIRS
29  * directions. If it's neighbors are low enough that the result would be lower
30  * than the current value, re-set it to 1 point higher than its lowest-scored
31  * neighbor. Repeat this whole process until all cells have settled on their
32  * final score. Ignore cells whose position in "score_map" fits cells of
33  * unreachable terrain in world.map.cells or whose score is greater than
34  * "max_score". Expect "max_score" to be the maximum score for cells, marking
35  * them as unreachable.
36  */
37 static void dijkstra_map(uint16_t * score_map, uint16_t max_score);
38
39 /* Return numpad char of direction ("8", "6", "2", "4" etc.) of enemy with the
40  * shortest path visible to "mo_origin". If no enemy is around, return 0.
41  */
42 static char get_dir_to_nearest_enemy(struct MapObj * mo_origin);
43
44
45
46 static void get_neighbor_scores(uint16_t * score_map, uint16_t pos_i,
47                                 uint16_t max_score, uint16_t * neighbors)
48 {
49     uint32_t map_size = world.map.length * world.map.length;
50     uint8_t i_dir;
51     for (i_dir = 0; i_dir < N_DIRS; neighbors[i_dir] = max_score, i_dir++);
52     uint8_t open_north     = pos_i >= world.map.length;
53     uint8_t open_east      = pos_i + 1 % world.map.length;
54     uint8_t open_south     = pos_i + world.map.length < map_size;
55     uint8_t open_west      = pos_i % world.map.length;
56     uint8_t is_indented    = (pos_i / world.map.length) % 2;
57     uint8_t open_diag_west = is_indented || open_west;
58     uint8_t open_diag_east = !is_indented || open_east;
59     if (open_north && open_diag_east)
60     {
61         neighbors[0] = score_map[pos_i - world.map.length + is_indented];
62     }
63     if (open_east)
64     {
65         neighbors[1] = score_map[pos_i + 1];
66     }
67     if (open_south && open_diag_east)
68     {
69         neighbors[2] = score_map[pos_i + world.map.length + is_indented];
70     }
71     if (open_south && open_diag_west)
72     {
73         neighbors[3] = score_map[pos_i + world.map.length - !is_indented];
74     }
75     if (open_west)
76     {
77         neighbors[4] = score_map[pos_i - 1];
78     }
79     if (open_north && open_diag_west)
80     {
81         neighbors[5] = score_map[pos_i - world.map.length - !is_indented];
82     }
83 }
84
85
86
87 static void dijkstra_map(uint16_t * score_map, uint16_t max_score)
88 {
89     uint32_t map_size = world.map.length * world.map.length;
90     uint16_t pos, i_scans, neighbors[N_DIRS], min_neighbor;
91     uint8_t scores_still_changing = 1;
92     uint8_t i_dirs;
93     for (i_scans = 0; scores_still_changing; i_scans++)
94     {
95         scores_still_changing = 0;
96         for (pos = 0; pos < map_size; pos++)
97         {
98             if ('.' == world.map.cells[pos] && score_map[pos] <= max_score)
99             {
100                 get_neighbor_scores(score_map, pos, max_score, neighbors);
101                 min_neighbor = max_score;
102                 for (i_dirs = 0; i_dirs < N_DIRS; i_dirs++)
103                 {
104                     if (min_neighbor > neighbors[i_dirs])
105                     {
106                         min_neighbor = neighbors[i_dirs];
107                     }
108                 }
109                 if (score_map[pos] > min_neighbor + 1)
110                 {
111                     score_map[pos] = min_neighbor + 1;
112                     scores_still_changing = 1;
113                 }
114             }
115         }
116     }
117 }
118
119
120
121 static char get_dir_to_nearest_enemy(struct MapObj * mo_origin)
122 {
123     char * f_name = "get_dir_to_nearest_enemy()";
124
125     /* Calculate for each cell the distance to the visibly nearest map actor not
126      * "mo_origin", with movement only possible in the directions of "dir".
127      * (Actors' own cells start with a distance of 0 towards themselves.)
128      */
129     uint32_t map_size = world.map.length * world.map.length;
130     uint16_t max_score = UINT16_MAX - 1;
131     uint16_t * score_map = try_malloc(map_size * sizeof(uint16_t), f_name);
132     uint32_t i;
133     for (i = 0; i < map_size; i++)
134     {
135         score_map[i] = mo_origin->fov_map[i] & VISIBLE ? max_score : UINT16_MAX;
136     }
137     struct MapObj * mo = world.map_objs;
138     for (; mo != NULL; mo = mo->next)
139     {
140         if (!mo->lifepoints || mo == mo_origin)
141         {
142             continue;
143         }
144         score_map[(mo->pos.y * world.map.length) + mo->pos.x] = 0;
145     }
146     dijkstra_map(score_map, max_score);
147
148     /* Return direction of "mo_origin"'s lowest-scored neighbor cell. */
149     uint16_t neighbors[N_DIRS];
150     uint16_t pos_i = (mo_origin->pos.y * world.map.length) + mo_origin->pos.x;
151     get_neighbor_scores(score_map, pos_i, max_score, neighbors);
152     free(score_map);
153     char dir_to_nearest_enemy = 0;
154     uint16_t min_neighbor = max_score;
155     char * dirs = "edcxsw";    /* get_neighbor_scores()'s clockwise dir order.*/
156     for (i = 0; i < N_DIRS; i++)
157     {
158         if (min_neighbor > neighbors[i])
159         {
160             min_neighbor = neighbors[i];
161             dir_to_nearest_enemy = dirs[i];
162         }
163     }
164     return dir_to_nearest_enemy;
165 }
166
167
168
169 extern void ai(struct MapObj * mo)
170 {
171     mo->command = get_moa_id_by_name("wait");
172     char sel = get_dir_to_nearest_enemy(mo);
173     if (0 != sel)
174     {
175         mo->command = get_moa_id_by_name("move");
176         mo->arg = sel;
177     }
178 }