/********************************************************************** Freeciv - Copyright (C) 2003 - The Freeciv Team This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. ***********************************************************************/ #ifdef HAVE_CONFIG_H #include #endif #include #include #include #include "city.h" #include "game.h" #include "government.h" #include "map.h" #include "mem.h" #include "log.h" #include "packets.h" #include "path_finding.h" #include "pf_tools.h" #include "player.h" #include "support.h" #include "timing.h" #include "citytools.h" #include "gotohand.h" #include "maphand.h" #include "settlers.h" #include "unittools.h" #include "aicity.h" #include "aidata.h" #include "ailog.h" #include "aitools.h" #include "aiunit.h" #include "citymap.h" #include "aisettler.h" /* COMMENTS */ /* This code tries hard to do the right thing, including looking into the future (wrt to government), and also doing this in a modpack friendly manner. However, there are some pieces missing. * A tighter integration into the city management code would give more optimal city placements, since existing cities could move their workers around to give a new city better placement. Occasionally you will see cities being placed sub-optimally because the best city center tile is taken when another tile could have been worked instead by the city that took it. */ static struct { int sum; char food; char trade; char shield; } cachemap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT]; /************************************************************************** Fill cityresult struct with useful info about the city spot. It must contain valid x, y coordinates and total should be zero. We assume whatever best government we are aiming for. We always return valid other_x and other_y if total > 0. **************************************************************************/ static void cityresult_fill(struct player *pplayer, struct ai_data *ai, struct cityresult *result) { struct city *pcity = map_get_city(result->x, result->y); struct tile *ptile = NULL; int sum = 0; bool virtual_city = FALSE; int curr_govt = pplayer->government; pplayer->government = ai->goal.govt.idx; result->best_other = -1; result->other_x = -1; result->other_y = -1; result->o_x = -1; result->o_y = -1; result->remaining = 0; if (!pcity) { pcity = create_city_virtual(pplayer, result->x, result->y, "Virtuaville"); virtual_city = TRUE; } city_map_checked_iterate(result->x, result->y, i, j, map_x, map_y) { int reserved = citymap_read(map_x, map_y); bool city_center = is_city_center(i, j); ptile = map_get_tile(map_x, map_y); if (reserved < 0 || (ai_handicap(pplayer, H_MAP) && !map_get_known(map_x, map_y, pplayer))) { /* Tile is reserved or we can't see it */ sum = 0; } else if (cachemap[map_x][map_y].sum == -1 || city_center) { /* We cannot read city center from cache */ /* Food */ result->tile[i][j].food = base_city_get_food_tile(i, j, pcity, FALSE); /* Shields */ result->tile[i][j].shield =base_city_get_shields_tile(i, j, pcity, FALSE); /* Trade */ result->tile[i][j].trade = base_city_get_trade_tile(i, j, pcity, FALSE); sum = (result->tile[i][j].food * ai->food_priority + result->tile[i][j].trade * ai->science_priority + result->tile[i][j].shield * ai->shield_priority); if (result->tile[i][j].food >= 2) { sum *= 2; /* we need this to grow */ } /* If this tile is in proximity of a city, we don't want it this much. * The more cities it overlaps with, the less we want it. */ sum /= (reserved + 1); if (!city_center) { cachemap[map_x][map_y].sum = sum; cachemap[map_x][map_y].trade = result->tile[i][j].trade; cachemap[map_x][map_y].shield = result->tile[i][j].shield; cachemap[map_x][map_y].food = result->tile[i][j].food; } } else { sum = cachemap[map_x][map_y].sum; result->tile[i][j].shield = cachemap[map_x][map_y].shield; result->tile[i][j].trade = cachemap[map_x][map_y].trade; result->tile[i][j].food = cachemap[map_x][map_y].food; } /* Calculate city center and best other than city center */ if (city_center) { result->city_center = sum; } else if (sum > result->best_other) { result->best_other = sum; result->other_x = map_x; result->other_y = map_y; result->o_x = i; result->o_y = j; } else { /* Save total remaining calculation */ result->remaining += sum; } } city_map_checked_iterate_end; /* City center without lots of food is not good. */ if (result->tile[2][2].food < 2) { result->city_center /= 2; } if (virtual_city) { /* Baseline is a size one city (city center + best extra tile). */ result->total = result->city_center + result->best_other; } else { /* Baseline is best extra tile only. This is why making new cities * is so darn good. */ result->total = result->best_other; } #ifdef NEVER /* Result without shields is not good either. While it makes * perfect sense, this code leads to suboptimal results in many * scenarios. The question is if it will help avoid pathological * cases. */ if (result->tile[2][2].shield + result->tile[result->o_x][result->o_y].shield < 2) { result->total -= result->total / 4; } #endif if (virtual_city) { /* Corruption and waste of a size one city deducted. Notice that we * don't do this if 'fulltradesize' is changed, since then we'd * never make cities. */ if (game.fulltradesize == 1) { result->total -= ai->science_priority * city_corruption(pcity, result->tile[result->o_x][result->o_y].trade + result->tile[2][2].trade); } result->total -= ai->shield_priority * city_waste(pcity, result->tile[result->o_x][result->o_y].shield + result->tile[2][2].shield); } else { /* Deduct difference in corruption and waste for real cities. Note that it * is possible (with notradesize) that we _gain_ value here. */ pcity->size++; result->total -= ai->science_priority * (city_corruption(pcity, result->tile[result->o_x][result->o_y].trade) - pcity->corruption); result->total -= ai->shield_priority * (city_waste(pcity, result->tile[result->o_x][result->o_y].shield) - pcity->shield_waste); pcity->size--; } result->total = MAX(0, result->total); pplayer->government = curr_govt; if (virtual_city) { remove_city_virtual(pcity); } if (result->best_other == 0) { /* Everything taken! */ result->total = 0; return; } assert(result->best_other != -1 && result->other_x != -1 && result->other_y != -1); assert(result->city_center >= 0); assert(result->remaining >= 0); } /************************************************************************** Calculates the desire for founding a new city at (x, y). The citymap ensures that we do not build cities too close to each other. If we return result->total == 0, then no place was found. **************************************************************************/ static void city_desirability(struct player *pplayer, struct ai_data *ai, struct unit *punit, int x, int y, struct cityresult *result) { bool ocean_adjacent = is_terrain_near_tile(x, y, T_OCEAN); struct city *pcity = map_get_city(x, y); int defense_bonus; assert(punit && ai && pplayer && result); result->x = x; result->y = y; result->total = 0; if (!city_can_be_built_here(x, y) || (ai_handicap(pplayer, H_MAP) && !map_get_known(x, y, pplayer))) { return; } if (enemies_at(punit, x, y)) { return; } if (pcity && pcity->size >= game.add_to_size_limit) { return; } if (!pcity && citymap_is_reserved(x, y)) { return; /* reserved, go away */ } cityresult_fill(pplayer, ai, result); /* Burn CPU, burn! */ if (result->total == 0) { /* Failed to find a good spot */ return; } /* If (x, y) is an existing city, consider immigration */ if (pcity && pcity->owner == pplayer->player_no) { return; } /*** Alright: Now consider building a new city ***/ /* Avoid starvation: We must have enough food to grow. */ if (result->tile[2][2].food + result->tile[result->o_x][result->o_y].food < 3) { result->total = 0; return; } /* Avoid resource starvation. */ if (result->tile[2][2].shield + result->tile[result->o_x][result->o_y].shield == 0) { result->total = 0; return; } /* Defense modification (as tie breaker mostly) */ defense_bonus = get_tile_type(map_get_terrain(x, y))->defense_bonus; if (map_has_special(x, y, S_RIVER)) { defense_bonus += (defense_bonus * terrain_control.river_defense_bonus) / 100; } result->total += (result->total * defense_bonus) / ai->defense_emphasis; /* Adjust for ocean adjacency, which is nice */ if (ocean_adjacent) { result->total += (result->total * ai->naval_emphasis) / 100; } /* Add remaining points, which is our potential */ result->total += (result->remaining / ai->growth_potential_emphasis); assert(result->total >= 0); return; } /************************************************************************** Prime settler engine. **************************************************************************/ void ai_settler_init(struct player *pplayer) { memset(&cachemap, -1, sizeof(cachemap)); } /************************************************************************** Find nearest and best city placement. Transparently checks if we should add ourselves to an existing city (TODO). **************************************************************************/ void find_best_city_placement(struct unit *punit, struct cityresult *best) { struct player *pplayer = unit_owner(punit); struct ai_data *ai = ai_data_get(pplayer); struct cityresult result; assert(pplayer && pplayer->ai.control); /* Remove if we ever add a generic freelog anywhere */ logdebug_suppress_warning; best->x = -1; best->y = -1; best->total = 0; /* Uh-huh, we're on board a ship... */ if (map_get_tile(punit->x, punit->y)->terrain == T_OCEAN) { UNIT_LOG(LOG_ERROR, punit, "We're trying to find a place to make a " "city while on board a ship..."); return; } simple_unit_path_iterator(punit, pos) { int turns; struct tile *ptile = map_get_tile(pos.x, pos.y); if (is_ocean(ptile->terrain)) { continue; /* This can happen if there is a ferry near shore. */ } if (ptile->continent != map_get_tile(punit->x,punit->y)->continent) { continue; /* We have an accidential land bridge. Ignore it. */ } /* Calculate worth */ city_desirability(pplayer, ai, punit, pos.x, pos.y, &result); /* This algorithm punishes long treks */ turns = pos.total_MC / unit_type(punit)->move_rate; result.total -= ai->perfection * turns * turns; /* Reduce want by settler cost. Easier than amortize, but still * weeds out very small wants. ie we create a threshold here. */ result.total -= unit_type(punit)->build_cost; /* Find best spot */ if (result.total > best->total) { *best = result; } } simple_unit_path_iterator_end; }