X-Git-Url: https://plomlompom.com/repos/%7B%7B%20web_path%20%7D%7D/decks/%7B%7Bdeck_id%7D%7D/cards/%7B%7B%20card_id%20%7D%7D/delete?a=blobdiff_plain;f=src%2Fserver%2Fai.c;h=7724c14b8230434899f8bb9917ec5d2854975191;hb=e430e9baabcde0c5ee373928ffb363bb452f6bb7;hp=96e7ac35463ec562a95de8d9757fc6090d74772b;hpb=6052be616897d692fc57ab15b56266b4b3f4668b;p=plomrogue diff --git a/src/server/ai.c b/src/server/ai.c index 96e7ac3..7724c14 100644 --- a/src/server/ai.c +++ b/src/server/ai.c @@ -1,112 +1,153 @@ /* src/server/ai.c */ #include "ai.h" -#include /* uint8_t, uint16_t */ -#include /* free() */ +#include /* uint8_t, uint32_t, UINT8_MAX */ #include /* strlen(), memset() */ -#include "../common/try_malloc.h" /* try_malloc() */ #include "../common/yx_uint16.h" /* struct yx_uint16 */ #include "map_object_actions.h" /* get_moa_id_by_name() */ #include "map_objects.h" /* struct MapObj */ #include "world.h" /* global world */ -#include "yx_uint16.h" /* yx_uint16_cmp(), mv_yx_in_dir() */ -/* Change cardinal direction string ("NNE" etc.) of any length >1 pointed to by - * "path_ptr" one step clockwise ("NNE" -> "NEE", "NEE" -> "EEE" etc.). +/* Write into "neighbor_scores" scores for immediate neighbors to cell at + * "pos_yx" (YX coordinates) and "pos_i" (arry_index) in "score_map". Directions + * determining neighborhood are defined by the letters of "dir"; their order + * also determines in what order scores are written into "neighbor_score". + * "len_dirs" is to store the result of a previous strlen(dir) (so it does not + * have to be called repeatedly and costly in dijkstra_map(); same reason for + * "pos_i"'s redundancy.). "max_score" is written into "neighbor_scores" for + * illegal directions (that from "pos_yx" would lead beyond the map's border). */ -static void clockwise_path(char ** path_ptr); - -/* Return dir char (north = "N" etc.) to enemy nearest to "origin" (beeline). */ -static char nearest_enemy_dir(struct yx_uint16 origin); +static void get_neighbor_scores(char * dirs, uint8_t len_dirs, + uint8_t * score_map, struct yx_uint16 pos_yx, + uint32_t pos_i, uint8_t max_score, + uint8_t * neighbor_scores) +{ + memset(neighbor_scores, max_score, len_dirs); + uint8_t i_dirs; + for (i_dirs = 0; i_dirs < len_dirs; i_dirs++) + { + if ('N' == dirs[i_dirs] && pos_yx.y > 0) + { + neighbor_scores[i_dirs] = score_map[pos_i - world.map.size.x]; + } + else if ('E' == dirs[i_dirs] && pos_yx.x < world.map.size.x - 1) + { + neighbor_scores[i_dirs] = score_map[pos_i + 1]; + } + else if ('S' == dirs[i_dirs] && pos_yx.y < world.map.size.y - 1) + { + neighbor_scores[i_dirs] = score_map[pos_i + world.map.size.x]; + } + else if ('W' == dirs[i_dirs] && pos_yx.x > 0) + { + neighbor_scores[i_dirs] = score_map[pos_i - 1]; + } + } +} -static void clockwise_path(char ** path_ptr) +/* Iterate over scored cells in "score_map" of world.map's 2D geometry. Compare + * each cell's score against the scores of its immediate neighbors in "dirs" + * directions; if at least one of these is lower, re-set the current cell's + * score to one higher than its lowest neighbor score. Repeat this whole process + * until all cells have settled on their final score. Ignore cells whose + * position in "score_map" fits a non-island cell in world.map.cells. Expect + * "max_score" to be the maximum score for cells, marking them as unreachable. + */ +static void dijkstra_map(char * dirs, uint8_t * score_map, uint8_t max_score) { - char * path = * path_ptr; - char old_char = path[0]; - char new_char = 'N'; - if ('N' == old_char) - { - new_char = 'E'; - } - else if ('E' == old_char) - { - new_char = 'S'; - } - else if ('S' == old_char) + uint8_t len_dirs = strlen(dirs); + uint8_t neighbor_scores[len_dirs]; + struct yx_uint16 pos_yx; + uint32_t pos_i; + uint8_t i_scans, i_dirs, local_score, min_neighbor_score; + uint8_t scores_still_changing = 1; + for (i_scans = 0; scores_still_changing; i_scans++) { - new_char = 'W'; - } - uint8_t len = strlen(path); - uint8_t i = 0; - for (; i < len; i++) - { - uint8_t next_i = i + 1; - if (next_i == len || old_char != path[next_i]) + scores_still_changing = 0; + for (pos_yx.y = 0, pos_i = 0; pos_yx.y < world.map.size.y; pos_yx.y++) { - break; + for (pos_yx.x = 0; pos_yx.x < world.map.size.x; pos_yx.x++, pos_i++) + { + if ('.' == world.map.cells[pos_i]) + { + local_score = score_map[pos_i]; + get_neighbor_scores(dirs, len_dirs, score_map, pos_yx, + pos_i, max_score, neighbor_scores); + min_neighbor_score = max_score; + for (i_dirs = 0; i_dirs < len_dirs; i_dirs++) + { + if (min_neighbor_score > neighbor_scores[i_dirs]) + { + min_neighbor_score = neighbor_scores[i_dirs]; + } + } + if (local_score > min_neighbor_score + 1) + { + score_map[pos_i] = min_neighbor_score + 1; + scores_still_changing = 1; + } + } + } } } - path[i] = new_char; } -static char nearest_enemy_dir(struct yx_uint16 origin) +/* Return char of direction ("N", "E", "S" or "W") of enemy with the shortest + * path to "mo_target". If no enemy is around, return 0. + */ +static char get_dir_to_nearest_enemy(struct MapObj * mo_target) { - char * f_name = "nearest_enemy_dir()"; - struct MapObj * mo; - char sel = 0; - uint16_t dist_max = world.map.size.y; - if (world.map.size.x > world.map.size.y) + /* Calculate for each cell the distance to the nearest map actor that is + * not "mo_target", with movement only possible in the directions of "dir". + * (Actor's own cells start with a distance of 0 towards themselves.) + */ + uint8_t max_score = UINT8_MAX; /* Score for cells treated as unreachable. */ + char * dirs = "NESW"; + uint8_t score_map[world.map.size.y * world.map.size.x]; + memset(score_map, max_score, world.map.size.y * world.map.size.x); + struct MapObj * mo = world.map_objs; + for (; mo != NULL; mo = mo->next) { - dist_max = world.map.size.x; + if (!mo->lifepoints || mo == mo_target) + { + continue; + } + score_map[(mo->pos.y * world.map.size.x) + mo->pos.x] = 0; } - uint8_t escape = 0; - uint8_t dist, j; - uint16_t i; - for (dist = 1; !escape && dist <= dist_max; dist++) + dijkstra_map(dirs, score_map, max_score); + + /* Return direction of "mo_target"'s lowest-scored neighbor cell. */ + uint8_t len_dirs = strlen(dirs); + uint32_t pos_i = (mo_target->pos.y * world.map.size.x) + mo_target->pos.x; + uint8_t neighbor_scores[len_dirs]; + get_neighbor_scores(dirs, len_dirs, score_map, mo_target->pos, pos_i, + max_score, neighbor_scores); + char dir_to_nearest_enemy = 0; + uint8_t min_neighbor_score = max_score; + uint8_t i_dirs; + for (i_dirs = 0; i_dirs < len_dirs; i_dirs++) { - char * path = try_malloc(dist + 1, f_name); - memset(path, 'N', dist); - path[dist] = '\0'; - for (i = 0; !escape && i < (dist * 4); i++) + if (min_neighbor_score > neighbor_scores[i_dirs]) { - clockwise_path(&path); - struct yx_uint16 testpos = origin; - for (j = 0; j < dist; j++) - { - testpos = mv_yx_in_dir(path[j], testpos); - } - if (yx_uint16_cmp(&testpos, &origin) || - testpos.y > world.map.size.y || testpos.x > world.map.size.x) - { - continue; - } - for (mo = world.map_objs; mo != 0; mo = mo->next) - { - if (mo->lifepoints && 1 == yx_uint16_cmp(&testpos, &mo->pos)) - { - sel = path[0]; - escape = 1; - break; - } - } + min_neighbor_score = neighbor_scores[i_dirs]; + dir_to_nearest_enemy = dirs[i_dirs]; } - free(path); } - return sel; + return dir_to_nearest_enemy; } -extern void pretty_dumb_ai(struct MapObj * mo) +extern void ai(struct MapObj * mo) { mo->command = get_moa_id_by_name("wait"); - char sel = nearest_enemy_dir(mo->pos); + char sel = get_dir_to_nearest_enemy(mo); if (0 != sel) { mo->command = get_moa_id_by_name("move");