? unfog_fix1.diff ? greg.diff ? find_a_direction_cleanup1.diff Index: common/map.c =================================================================== RCS file: /home/freeciv/CVS/freeciv/common/map.c,v retrieving revision 1.103 diff -u -r1.103 map.c --- common/map.c 2001/12/13 19:13:16 1.103 +++ common/map.c 2002/02/02 12:55:25 @@ -1404,17 +1404,34 @@ } /************************************************************************** +Return true and sets dir to the direction of the step if (end_x,end_y) +can be reached from (start_x,start_y) in one step. Return false +otherwise (value of dir unchanged). +**************************************************************************/ +int base_get_direction_for_step(int start_x, int start_y, int end_x, + int end_y, int *dir) +{ + adjc_dir_iterate(start_x, start_y, x1, y1, dir2) { + if (x1 == end_x && y1 == end_y) { + *dir = dir2; + return 1; + } + } adjc_dir_iterate_end; + + return 0; +} + +/************************************************************************** Return the direction which is needed for a step on the map from (start_x,start_y) to (end_x,end_y). **************************************************************************/ int get_direction_for_step(int start_x, int start_y, int end_x, int end_y) { - assert(is_tiles_adjacent(start_x, start_y, end_x, end_y)); + int dir; - adjc_dir_iterate(start_x, start_y, x1, y1, dir) { - if (x1 == end_x && y1 == end_y) - return dir; - } adjc_dir_iterate_end; + if (base_get_direction_for_step(start_x, start_y, end_x, end_y, &dir)) { + return dir; + } assert(0); return -1; Index: common/map.h =================================================================== RCS file: /home/freeciv/CVS/freeciv/common/map.h,v retrieving revision 1.109 diff -u -r1.109 map.h --- common/map.h 2002/01/06 16:43:26 1.109 +++ common/map.h 2002/02/02 12:55:26 @@ -192,6 +192,8 @@ int real_map_distance(int x0, int y0, int x1, int y1); int sq_map_distance(int x0, int y0, int x1, int y1); int same_pos(int x1, int y1, int x2, int y2); +int base_get_direction_for_step(int start_x, int start_y, int end_x, + int end_y, int *dir); int get_direction_for_step(int start_x, int start_y, int end_x, int end_y); void map_set_continent(int x, int y, int val); Index: server/gotohand.c =================================================================== RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v retrieving revision 1.127 diff -u -r1.127 gotohand.c --- server/gotohand.c 2002/01/31 22:48:24 1.127 +++ server/gotohand.c 2002/02/02 12:55:27 @@ -861,41 +861,59 @@ } /************************************************************************** -This is used to choose among the valid directions marked on the warmap by -the find_the_shortest_path() function. -Returns a direction as used in DIR_DX[] and DIR_DY[] arrays, or -1 if none could be -found. +This is used to choose among the valid directions marked on the warmap +by the find_the_shortest_path() function. Returns a direction or -1 if +none could be found. Notes on the implementation: -1. d[8] contains "goodness" of the directions. Bigger number means safer -direction. It takes into account: how well the unit will be defended at -the next tile, how many possible attackers there are around it, whether it -is likely to sink there (for triremes). + +1. fitness[8] contains the fitness of the directions. Bigger number means + safer direction. It takes into account: how well the unit will be + defended at the next tile, how many possible attackers there are + around it, whether it is likely to sink there (for triremes). + 2. This function does not check for loops, which we currently rely on -find_the_shortest_path() to make sure there are none of. If the warmap did -contain a loop repeated calls of this function may result in the unit going -in cycles forever. -3. It doesn't check for ZOC as it has been done in find_the_shortest_path -(which is called every turn). + find_the_shortest_path() to make sure there are none of. If the + warmap did contain a loop repeated calls of this function may result + in the unit going in cycles forever. + +3. It doesn't check for ZOC as it has been done in + find_the_shortest_path (which is called every turn). + **************************************************************************/ static int find_a_direction(struct unit *punit, enum goto_move_restriction restriction, const int dest_x, const int dest_y) { - int k; /* direction we're interested in at a given point */ - int d[8], best = 0; - int defence_multiplier, tmp; - int defence_of_unit, defence_of_ally, hp_of_unit, hp_of_ally, num_of_units; - int base_move_cost; - struct tile *ptile; - struct city *pcity; +#define UNIT_DEFENSE(punit, x, y, defence_multiplier) \ + ((get_simple_defense_power((punit)->type, (x), (y)) * \ + (defence_multiplier)) / 2) + +#define UNIT_RATING(punit, x, y, defence_multiplier) \ + (UNIT_DEFENSE(punit, x, y, defence_multiplier) * (punit)->hp) + + /* + * 6% of the fitness value is substracted for directions where the + * destination is unknown and we don't have enough move points. + */ +#define UNKNOWN_FITNESS_PENALTY_PERCENT 6 + + /* + * Use this if you want to indicate that this direction shouldn't be + * selected. + */ +#define DONT_SELECT_ME_FITNESS (-1) + + int fitness[8], best_fitness = DONT_SELECT_ME_FITNESS; struct unit *passenger; struct player *pplayer = unit_owner(punit); int afraid_of_sinking = (unit_flag(punit, F_TRIREME) && !player_owns_active_wonder(pplayer, B_LIGHTHOUSE)); - int do_full_check = afraid_of_sinking; /* if the destination is one step - * away, look around first or just - * go there? */ + /* + * If the destination is one step away, look around first or just go + * there? + */ + int do_full_check = afraid_of_sinking; if (map_get_terrain(punit->x, punit->y) == T_OCEAN) { passenger = other_passengers(punit); @@ -903,36 +921,57 @@ passenger = NULL; } - /* If we can get to the destination right away there is nothing to be gained - * from going round in little circles to move across desirable squares */ - /* Actually there are things to gain, in AI case, - * like the safety checks -- GB */ + /* + * If we can get to the destination right away there is nothing to + * be gained from going round in little circles to move across + * desirable squares. + * + * Actually there are things to gain, in AI case, like the safety + * checks -- GB + */ if (!do_full_check) { - adjc_dir_iterate(punit->x, punit->y, x, y, dir) { - if ((x == dest_x && y == dest_y) - && warmap.vector[punit->x][punit->y] & (1 << dir) - && !(restriction == GOTO_MOVE_CARDINAL_ONLY - && !DIR_IS_CARDINAL(dir))) { - return dir; - } - } adjc_dir_iterate_end; + int dir; + + if (base_get_direction_for_step(punit->x, punit->y, dest_x, dest_y, + &dir) + && warmap.vector[punit->x][punit->y] & (1 << dir) + && !(restriction == GOTO_MOVE_CARDINAL_ONLY + && !DIR_IS_CARDINAL(dir))) { + return dir; + } } - - memset(d, 0, sizeof(d)); - adjc_dir_iterate(punit->x, punit->y, x, y, k) { - /* is it an allowed direction? is it marked on the warmap? */ - if (!(warmap.vector[punit->x][punit->y] & (1 << k)) - || ((restriction == GOTO_MOVE_CARDINAL_ONLY) && !DIR_IS_CARDINAL(k))) { + memset(fitness, 0, sizeof(fitness)); + + /* + * Loop over all directions, fill the fitness array and update + * best_fitness. + */ + adjc_dir_iterate(punit->x, punit->y, x, y, dir) { + int defence_multiplier, num_of_allied_units, best_friendly_defence, + base_move_cost; + struct tile *ptile = map_get_tile(x, y); + struct city *pcity = map_get_city(x, y); + struct unit *best_ally; + + /* + * Is it an allowed direction? is it marked on the warmap? + */ + if (!(warmap.vector[punit->x][punit->y] & (1 << dir)) + || ((restriction == GOTO_MOVE_CARDINAL_ONLY) + && !DIR_IS_CARDINAL(dir))) { /* make sure we don't select it later */ - d[k] = -1; + fitness[dir] = DONT_SELECT_ME_FITNESS; continue; } - /* determine the cost of the proposed move */ + /* + * Determine the cost of the proposed move. + */ if (is_ground_unit(punit)) { - /* assuming move is valid, but what if unit is trying to board? -- GB */ - base_move_cost = map_get_tile(punit->x, punit->y)->move_cost[k]; + /* assuming move is valid, but what if unit is trying to board? + -- GB */ + base_move_cost = map_get_tile(punit->x, punit->y)->move_cost[dir]; } else { base_move_cost = SINGLE_MOVE; } @@ -944,144 +983,226 @@ freelog(LOG_DEBUG, "%d@(%d,%d) evaluating (%d,%d)[%d/%d]", punit->id, punit->x, punit->y, x, y, base_move_cost, punit->moves_left); - /* find everybody's defence stats */ - ptile = map_get_tile(x, y); - defence_of_unit = get_simple_defense_power(punit->type, x, y); - pcity = map_get_city(x, y); + /* + * Calculate the defence multiplier of this tile. Both the unit + * itself and its ally benefit from it. + */ defence_multiplier = 2; - if (pcity) { /* this code block inspired by David Pfitzner -- Syela */ - if (city_got_citywalls(pcity)) defence_multiplier += 2; - if (city_got_building(pcity, B_SDI)) defence_multiplier++; - if (city_got_building(pcity, B_SAM)) defence_multiplier++; - if (city_got_building(pcity, B_COASTAL)) defence_multiplier++; - } - defence_of_unit = (defence_of_unit * defence_multiplier) / 2; - hp_of_unit = punit->hp; - /* find the best friendly defensive unit at the target tile */ - hp_of_ally = 0; - defence_of_ally = 0; - num_of_units = 1; - unit_list_iterate(ptile->units, aunit) { - if (!pplayers_allied(unit_owner(aunit), unit_owner(punit))) { - /* MINIMUM priority */ - defence_of_ally = -1; - } else { - num_of_units++; - tmp = (get_simple_defense_power(aunit->type, x, y) * - defence_multiplier) / 2; - if (tmp * aunit->hp > defence_of_ally * hp_of_ally) { - defence_of_ally = tmp; - hp_of_ally = aunit->hp; - } + if (pcity) { + if (city_got_citywalls(pcity)) { + defence_multiplier += 2; } - } unit_list_iterate_end; + if (city_got_building(pcity, B_SDI)) { + defence_multiplier++; + } + if (city_got_building(pcity, B_SAM)) { + defence_multiplier++; + } + if (city_got_building(pcity, B_COASTAL)) { + defence_multiplier++; + } + } + /* + * Find the best ally unit at the target tile. + */ + best_ally = NULL; + num_of_allied_units = 0; { + /* + * Initialization only for the compiler since it is guarded by + * best_ally. + */ + int rating_of_best_ally = 0; + + unit_list_iterate(ptile->units, aunit) { + if (pplayers_allied(unit_owner(aunit), unit_owner(punit))) { + int rating_of_current_ally = + UNIT_RATING(aunit, x, y, defence_multiplier); + num_of_allied_units++; + + if (!best_ally || rating_of_current_ally > rating_of_best_ally) { + best_ally = aunit; + rating_of_best_ally = rating_of_current_ally; + } + } + } unit_list_iterate_end; + } + + if (best_ally) { + best_friendly_defence = + MAX(UNIT_DEFENSE(punit, x, y, defence_multiplier), + UNIT_DEFENSE(best_ally, x, y, defence_multiplier)); + } else { + best_friendly_defence = + UNIT_DEFENSE(punit, x, y, defence_multiplier); + } + + /* + * Fill fitness[dir] based on the rating of punit and best_ally. + */ + { /* calculate some clever weights basing on defence stats */ - int rating_of_unit = defence_of_unit * hp_of_unit; - int rating_of_ally = defence_of_ally * hp_of_ally; - if (num_of_units == 1) { - d[k] = rating_of_unit; + int rating_of_ally, rating_of_unit = + UNIT_RATING(punit, x, y, defence_multiplier); + + assert((best_ally != NULL) == (num_of_allied_units > 0)); + + if (best_ally) { + rating_of_ally = UNIT_RATING(best_ally, x, y, defence_multiplier); + } else { + rating_of_ally = 0; /* equivalent of having 0 HPs */ + } + + if (num_of_allied_units == 0) { + fitness[dir] = rating_of_unit; } else if (pcity || ptile->special & S_FORTRESS) { - d[k] = MAX(rating_of_unit, rating_of_ally); + fitness[dir] = MAX(rating_of_unit, rating_of_ally); } else if (rating_of_unit <= rating_of_ally) { - d[k] = rating_of_ally * (num_of_units - 1) / num_of_units; + fitness[dir] = rating_of_ally * (num_of_allied_units / + (num_of_allied_units + 1)); } else { - d[k] = MIN(rating_of_unit * num_of_units, - rating_of_unit * rating_of_unit * (num_of_units - 1) / - MAX(num_of_units, (rating_of_ally * num_of_units))); + fitness[dir] = MIN(rating_of_unit * (num_of_allied_units + 1), + rating_of_unit * rating_of_unit * + (num_of_allied_units / + MAX((num_of_allied_units + 1), + (rating_of_ally * + (num_of_allied_units + 1))))); } } - - /* in case we change directions next turn, roads are nice */ - if ((ptile->special & S_ROAD) || (ptile->special & S_RAILROAD)) - d[k] += 10; - defence_of_ally = MAX(defence_of_unit, defence_of_ally); - /* what is around the tile we are about to step to? */ + /* + * In case we change directions next turn, roads and railroads are + * nice. + */ + if ((ptile->special & S_ROAD) || (ptile->special & S_RAILROAD)) { + fitness[dir] += 10; + } + + /* + * What is around the tile we are about to step to? + */ adjc_iterate(x, y, tmp_x, tmp_y) { struct tile *adjtile = map_get_tile(tmp_x, tmp_y); - if (!map_get_known(tmp_x, tmp_y, unit_owner(punit))) { - if (punit->moves_left <= base_move_cost) { - /* Avoid the unknown (16 is experimentally(?) determined) */ - d[k] -= (d[k] / 16); - } else { + + if (!map_get_known(tmp_x, tmp_y, pplayer)) { + if (punit->moves_left < base_move_cost) { + /* Avoid the unknown */ + fitness[dir] -= + (fitness[dir] * UNKNOWN_FITNESS_PENALTY_PERCENT) / 100; + } else { /* nice but not important */ - d[k]++; + fitness[dir]++; } } else { - /* NOTE: Not being omniscient here!! -- Syela */ /* lookin for trouble */ - int attack_of_enemy; - unit_list_iterate(adjtile->units, aunit) - if (pplayers_at_war(unit_owner(aunit), unit_owner(punit)) - && (attack_of_enemy = get_attack_power(aunit))) { - if (punit->moves_left < base_move_cost + SINGLE_MOVE) { - /* can't fight */ - if (passenger && !is_ground_unit(aunit)) { - /* really don't want that direction */ - d[k] = -99; - } else { - d[k] -= defence_of_ally * (aunit->hp * attack_of_enemy * - attack_of_enemy / (attack_of_enemy * attack_of_enemy + - defence_of_ally * defence_of_ally)); - } + if (punit->moves_left < base_move_cost + SINGLE_MOVE) { + /* can't fight */ + unit_list_iterate(adjtile->units, aunit) { + int attack_of_enemy; + + if (!pplayers_at_war(unit_owner(aunit), unit_owner(punit))) { + continue; } - } - unit_list_iterate_end; + + attack_of_enemy = get_attack_power(aunit); + if (!attack_of_enemy) { + continue; + } + + if (passenger && !is_ground_unit(aunit)) { + /* really don't want that direction */ + fitness[dir] = DONT_SELECT_ME_FITNESS; + } else { + fitness[dir] -= + best_friendly_defence * (aunit->hp * attack_of_enemy * + attack_of_enemy / + (attack_of_enemy * + attack_of_enemy + + best_friendly_defence * + best_friendly_defence)); + } + } unit_list_iterate_end; + } } /* end this-tile-is-seen else */ } adjc_iterate_end; - /* Try to make triremes safe */ + /* + * Try to make triremes safe + */ if (afraid_of_sinking && !is_coast_seen(x, y, pplayer)) { if (punit->moves_left < 2 * SINGLE_MOVE) { - /* Tired of Kaput!! -- Syela */ - d[k] = -1; + fitness[dir] = DONT_SELECT_ME_FITNESS; continue; - } else { - /* we have enough moves and will be able to get back, - * if gotomap was generated in the right way */ - d[k] = 1; } + + /* We have enough moves and will be able to get back. */ + fitness[dir] = 1; } - - if (d[k] < 1 && (!unit_owner(punit)->ai.control + + /* + * Clip the fitness value. + */ + if (fitness[dir] < 1 && (!unit_owner(punit)->ai.control || !punit->ai.passenger || punit->moves_left >= 2 * SINGLE_MOVE)) { - d[k] = 1; + fitness[dir] = 1; + } + if (fitness[dir] < 0) { + fitness[dir] = DONT_SELECT_ME_FITNESS; } - if (d[k] > best) { - best = d[k]; + + /* + * Better than the best known? + */ + if (fitness[dir] != DONT_SELECT_ME_FITNESS + && fitness[dir] > best_fitness) { + best_fitness = fitness[dir]; freelog(LOG_DEBUG, "New best = %d: (%d, %d) -> (%d, %d)", - best, punit->x, punit->y, x, y); + best_fitness, punit->x, punit->y, x, y); } } adjc_dir_iterate_end; - if (!best && afraid_of_sinking && !is_coastline(punit->x, punit->y)) { - /* we've got a trireme in the middle of the sea. - * With !best, it'll end its turn right there and - * could very well die. we'll try to rescue. */ - freelog(LOG_DEBUG, "%s's trireme in trouble at (%d,%d), looking for coast", + if (best_fitness == DONT_SELECT_ME_FITNESS && afraid_of_sinking + && !is_coastline(punit->x, punit->y)) { + /* + * We've got a trireme in the middle of the sea. With + * best_fitness==DONT_SELECT_ME_FITNESS, it'll end its turn right + * there and could very well die. We'll try to rescue. + */ + freelog(LOG_DEBUG, + "%s's trireme in trouble at (%d,%d), looking for coast", pplayer->name, punit->x, punit->y); - adjc_dir_iterate(punit->x, punit->y, x, y, k) { + + adjc_dir_iterate(punit->x, punit->y, x, y, dir) { if (is_coast_seen(x, y, pplayer)) { - d[k] = 1; - best = 1; + fitness[dir] = 1; + best_fitness = 1; freelog(LOG_DEBUG, "found coast"); } } adjc_dir_iterate_end; } - if (!best) { + if (best_fitness == DONT_SELECT_ME_FITNESS) { freelog(LOG_DEBUG, "find_a_direction: no good direction found"); return -1; } + + /* + * Find random direction out of the best ones selected. + */ + for (;;) { + int dir = myrand(8); + + if (fitness[dir] == best_fitness) { + return dir; + } + } - /* find random direction out of the best ones selected */ - do { - k = myrand(8); - } while (d[k] < best); - return k; +#undef UNIT_DEFENSE +#undef UNIT_RATING +#undef UNKNOWN_FITNESS_PENALTY_PERCENT +#undef DONT_SELECT_ME_FITNESS } /**************************************************************************