From e430e9baabcde0c5ee373928ffb363bb452f6bb7 Mon Sep 17 00:00:00 2001 From: Christian Heller Date: Fri, 31 Jan 2014 23:37:15 +0100 Subject: [PATCH] Heavily improved enemy path-finding. Also corrected errors in turn_over() and map object action handling found on the way. --- README | 6 +- confserver/map_object_actions | 10 +- src/server/ai.c | 185 +++++++++++++++++++------------- src/server/ai.h | 10 +- src/server/map_object_actions.h | 6 +- src/server/map_objects.h | 2 +- src/server/run.c | 9 +- 7 files changed, 133 insertions(+), 95 deletions(-) diff --git a/README b/README index 7b71967..722ce9d 100644 --- a/README +++ b/README @@ -12,9 +12,9 @@ become dirt, skeletons or "magic meat"--such objects can be collected, and "magic meat" can be consumed to gain hitpoints. Note that different kinds of movements/actions take different numbers of turns to finish. -Enemies' AI is very dumb so far: Each turn, they try to move in the (beeline) -direction of the nearest enemy, so they often bump into, and get stuck behind, -obstacles. You can use that for your advantage. +Enemies' AI is very dumb so far: Each turn, they try to move towards their +path-wise nearest enemy. If no enemy is found in their surroundings, they just +wait. Once you start a new world, every move of yours is recorded in a file called "record". Once you re-start the game, all of your previous moves are replayed diff --git a/confserver/map_object_actions b/confserver/map_object_actions index da514e6..54dc543 100644 --- a/confserver/map_object_actions +++ b/confserver/map_object_actions @@ -1,20 +1,20 @@ -0 +1 1 wait %% -1 +2 3 move %% -2 +3 10 pick_up %% -3 +4 3 drop %% -4 +5 30 use %% 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"); diff --git a/src/server/ai.h b/src/server/ai.h index 7e5a145..4b9b776 100644 --- a/src/server/ai.h +++ b/src/server/ai.h @@ -10,13 +10,11 @@ struct MapObj; -/* Determine next non-player actor command / arguments by the actor's AI. - * - * The AI is pretty dumb so far. Actors basically try to move towards their - * nearest neighbor in a straight line, easily getting stuck behind obstacles or - * ending up in endless chase circles with each other. +/* Determine next non-player actor command / arguments by the actor's AI. It's + * pretty dumb so far. Actors will try to move towards their path-wise nearest + * neighbor. If no one else is found in the neighborhood, they will simply wait. */ -extern void pretty_dumb_ai(struct MapObj * mo); +extern void ai(struct MapObj * mo); diff --git a/src/server/map_object_actions.h b/src/server/map_object_actions.h index 983f1aa..d3b88a3 100644 --- a/src/server/map_object_actions.h +++ b/src/server/map_object_actions.h @@ -17,9 +17,9 @@ struct MapObjAct { struct MapObjAct * next; void (* func) (struct MapObj *); /* function called after .effort turns */ - char * name; /* human-readable identifier */ - uint8_t id; /* unique id of map object action */ - uint8_t effort; /* how many turns the action takes */ + char * name; /* human-readable identifier */ + uint8_t id; /* unique id of map object action; must be >0 */ + uint8_t effort; /* how many turns the action takes */ }; diff --git a/src/server/map_objects.h b/src/server/map_objects.h index 0796c3c..7b6c6b2 100644 --- a/src/server/map_objects.h +++ b/src/server/map_objects.h @@ -20,7 +20,7 @@ struct MapObj uint8_t id; /* individual map object's unique identifier */ uint8_t type; /* ID of appropriate map object definition */ uint8_t lifepoints; /* 0: object is inanimate; >0: hitpoints */ - uint8_t command; /* map object's current action */ + uint8_t command; /* map object's current action; 0 if none */ uint8_t arg; /* optional field for .command argument */ uint8_t progress; /* turns already passed to realize .command */ }; diff --git a/src/server/run.c b/src/server/run.c index 540f025..1df4b63 100644 --- a/src/server/run.c +++ b/src/server/run.c @@ -12,7 +12,7 @@ * textfile_sizes(), try_fputc() */ #include "../common/rexit.h" /* exit_trouble() */ -#include "ai.h" /* pretty_dumb_ai() */ +#include "ai.h" /* ai() */ #include "init.h" /* remake_world() */ #include "io.h" /* io_round() */ #include "map_object_actions.h" /* get_moa_id_by_name() */ @@ -40,7 +40,6 @@ static void turn_over() struct MapObj * player = get_player(); struct MapObj * map_object = player; uint16_t start_turn = world.turn; - uint8_t first_round = 1; while ( 0 < player->lifepoints || (0 == player->lifepoints && start_turn == world.turn)) { @@ -51,15 +50,14 @@ static void turn_over() } if (0 < map_object->lifepoints) { - if (0 == first_round && 0 == map_object->progress) + if (0 == map_object->command) { if (map_object == player) { break; } - pretty_dumb_ai(map_object); + ai(map_object); } - first_round = 0; map_object->progress++; struct MapObjAct * moa = world.map_obj_acts; while (moa->id != map_object->command) @@ -69,6 +67,7 @@ static void turn_over() if (map_object->progress == moa->effort) { moa->func(map_object); + map_object->command = 0; map_object->progress = 0; } } -- 2.30.2