[freeciv-ai] (PR#8992) Patch: Centralised ferry building
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
<URL: http://rt.freeciv.org/Ticket/Display.html?id=8992 >
Attached is an altered version of Gregory Berkolaiko's patch for
centralised ferry building. This is applicable to the CVS development
branch as of 2004-10-22.
This differs from the previous patch I submitted, as follows.
* Updated from the CVS development version of 2004-10-08.
* The AI decides how many ferries to build by performing a cost-benefit
analysis, and choosing the number that should yield the greatest profit.
* The AI might choose to build more than one ferry.
* The AI prefers building ferries in cities with port facilities.
* The AI prefers building ferries in cities that are building
non-military units.
* The AI notes how many enemy and its own warships there are on an ocean.
* The ferry building code respects AI fuzziness and handicaps.
* If the AI is ignorant (because of the H_MAP or H_FOG handicaps), it
will make an intelligent guess for the number of enemy warships on an ocean.
* The AI makes use of geographical information to help make a good decision.
* Fixed a bug in the assignment of is_building_unit.
* The code adjusts the 'want' scores, so the AI can later make good
choices about spending gold to help ferry production.
The cost-benefit analysis uses a simple 0-dimensional model of the
shipping activity. The model accounts for journey lengths and shipping
losses because of enemy warships. The estimation of journey lengths
should produce reasonable values for a wide range of maps.
This version produces copious logging output, which is suitable while
testing but not after application to a CVS version. To correct that,
change the line
#define LOGLEVEL_BUILDFERRY LOG_NORMAL
to
#define LOGLEVEL_BUILDFERRY LOG_DEBUG
This version does not estimate shipping losses because of air attacks.
Note that this version, as for Gregory's original version, incorrectly
accounts for oceans that are connected through channels. It correctly
assumes that our ferries can move through cities belonging to us or our
allies, but it incorrectly assumes that enemy warships can do likewise.
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/advdomestic.c
freeciv.PR8992/ai/advdomestic.c
--- vendor.freeciv.current/ai/advdomestic.c 2004-10-22 23:16:36.000000000
+0100
+++ freeciv.PR8992/ai/advdomestic.c 2004-10-23 18:03:45.000000000 +0100
@@ -204,7 +204,6 @@
choice->type = CT_NONMIL;
choice->choice = unit_type; /* default */
choice->need_boat = TRUE;
- ai_choose_role_unit(pplayer, pcity, choice, L_FERRYBOAT, -want);
}
}
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/advmilitary.c
freeciv.PR8992/ai/advmilitary.c
--- vendor.freeciv.current/ai/advmilitary.c 2004-10-22 23:16:37.000000000
+0100
+++ freeciv.PR8992/ai/advmilitary.c 2004-10-23 18:03:47.000000000 +0100
@@ -768,7 +768,7 @@
kill_something_with send it some more variables for it to meddle with.
-- Syela
- (x,y) is location of the target.
+ ptile is location of the target (?)
best_choice is pre-filled with our current choice, we only
consider units of the same move_type as best_choice
**************************************************************************/
@@ -955,12 +955,84 @@
}
/**************************************************************************
+Guess information about the kind of ferry we can expect to transport an
+attacker to its target.
+
+Although we do not force a boat to the city (that is done by the
+boat dispatcher), we still need to know some information about the kind of boat
+we can expect to have, so we can select suitable targets.
+We want to estimate how long it will take for the boat to get there
+(if we will use an existing boat) and the sailing speed after we board it.
+
+*go_by_boat: expect to need a ferry
+*ferryboat: expect to get this ferry. NULL indicates to expect
+ to get a new boat instead, in which case use *boattype to
+ determine the characterisitics of the new ferry.
+*boattype: expect to get this type of ferry
+
+TODO: combined go_by_boat and boattype into ferryboat,
+but returning a virtual unit if we expect a new boat,
+and NULL if we do not expect to need a ferry.
+*************************************************************************/
+static void guess_attacker_ferry(struct player *pplayer, struct unit *myunit,
+ int move_rate, struct tile *destination,
+ bool *go_by_boat,
+ struct unit **ferryboat,
+ Unit_Type_id *boattype)
+{
+ if (is_ground_unit(myunit)) {
+
+ /* Are there free boats nearby?*/
+ struct tile *boat_tile = NULL;
+ int boatid = find_boat(pplayer, &boat_tile, 2); /*quick but unreliable*/
+ *ferryboat = player_find_unit_by_id(pplayer, boatid);
+
+ if (*ferryboat) { /*there is a free boat nearby*/
+ /* Assume we will get a boat like this existing free nearby boat.*/
+ /* This is a good assumption if we have many free boats*/
+ *boattype = (*ferryboat)->type;
+ } else {
+ /* Assume we will get a shiny new boat.*/
+ /* Because find_boat() is unreliable, we will make this assumption
+ * unrealisitically often. When the unit is finally built, it might
+ * have to make do with a low tech boat from our old fleet,
+ * but this optimism is probably not too bad for most games.
+ */
+ *boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
+ if (*boattype == U_LAST) {
+ /* We pretend that we can have the simplest boat --
+ to stimulate tech */
+ *boattype = get_role_unit(L_FERRYBOAT, 0);
+ /*TODO: stimulate the technology!*/
+ }
+ }
+
+ *go_by_boat = !(WARMAP_COST(destination) <= (MIN(6, move_rate) * THRESHOLD)
+ && goto_is_sane(myunit, destination, TRUE));
+ } else {/*never needs a boat*/
+ *go_by_boat = FALSE;
+ *ferryboat = NULL;
+ *boattype = U_LAST;
+ }
+
+ /*Only ground units ever need boats:*/
+ assert(!(!is_ground_unit(myunit) && *go_by_boat));
+ /*If we will go by boat, it will be on a ferry of some kind:*/
+ assert(!(*go_by_boat) || *boattype != U_LAST);
+ assert(!(*go_by_boat) || SEA_MOVING == unit_types[*boattype].move_type);
+ /*Provide consistent output data:*/
+ assert(0 == *ferryboat || (*ferryboat)->type == *boattype);
+}
+
+/**************************************************************************
This function
1. receives (in myunit) a first estimate of what we would like to build.
2. finds a potential victim for it.
3. calculates the relevant stats of the victim.
4. finds the best attacker for this type of victim (in process_attacker_want)
5. if we still want to attack, records the best attacker in choice.
+If the target is overseas, the function might suggest using a ferry
+to carry a land attack unit.
**************************************************************************/
static void kill_something_with(struct player *pplayer, struct city *pcity,
struct unit *myunit, struct ai_choice *choice)
@@ -974,17 +1046,15 @@
Unit_Type_id def_type;
/* Target coordinates */
struct tile *ptile;
- /* Our transport */
+ /* The ferry we expect to use, if using an existing ferry*/
struct unit *ferryboat = NULL;
/* Out target */
struct city *acity;
/* Defender of the target city/tile */
struct unit *pdef;
- /* Coordinates of the boat */
- struct tile *boat_tile = NULL;
- /* Type of the boat (real or a future one) */
+ /* Type of the ferry we expect to use(real or a future one) */
Unit_Type_id boattype = U_LAST;
- bool go_by_boat;
+ bool go_by_boat = FALSE;
/* Is the defender veteran? */
int def_vet;
struct ai_choice best_choice;
@@ -1007,21 +1077,6 @@
return;
}
- if (is_ground_unit(myunit)) {
- int boatid = find_boat(pplayer, &boat_tile, 2);
- ferryboat = player_find_unit_by_id(pplayer, boatid);
- }
-
- if (ferryboat) {
- boattype = ferryboat->type;
- } else {
- boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
- if (boattype == U_LAST) {
- /* We pretend that we can have the simplest boat -- to stimulate tech */
- boattype = get_role_unit(L_FERRYBOAT, 0);
- }
- }
-
best_choice.want = find_something_to_kill(pplayer, myunit, &ptile);
acity = map_get_city(ptile);
@@ -1055,8 +1110,8 @@
return;
}
- go_by_boat = !(goto_is_sane(myunit, acity->tile, TRUE)
- && WARMAP_COST(ptile) <= (MIN(6, move_rate) * THRESHOLD));
+ guess_attacker_ferry(pplayer, myunit, move_rate, ptile,
+ &go_by_boat, &ferryboat, &boattype);
move_time = turns_to_enemy_city(myunit->type, acity, move_rate,
go_by_boat, ferryboat, boattype);
@@ -1105,24 +1160,18 @@
/* end dealing with units */
}
- if (!go_by_boat) {
- process_attacker_want(pcity, benefit, def_type, def_vet, ptile,
- &best_choice, NULL, U_LAST);
- } else {
- /* Attract a boat to our city or retain the one that's already here */
- best_choice.need_boat = TRUE;
- process_attacker_want(pcity, benefit, def_type, def_vet, ptile,
- &best_choice, ferryboat, boattype);
- }
+ best_choice.need_boat = go_by_boat;
+ process_attacker_want(pcity, benefit, def_type, def_vet, ptile,
+ &best_choice, ferryboat, boattype);
+ /*Only ground units ever need boats:*/
+ assert(!(!is_ground_unit(myunit) && best_choice.need_boat));
if (best_choice.want > choice->want) {
/* We want attacker more that what we have selected before */
copy_if_better_choice(&best_choice, choice);
- if (go_by_boat && !ferryboat) {
- ai_choose_role_unit(pplayer, pcity, choice, L_FERRYBOAT, choice->want);
- }
- freelog(LOG_DEBUG, "%s has chosen attacker, %s, want=%d",
- pcity->name, unit_types[choice->choice].name, choice->want);
+ CITY_LOG(LOG_DEBUG, pcity, "has chosen attacker, %s, want=%d%s",
+ unit_types[choice->choice].name, choice->want,
+ (best_choice.need_boat ? "(need boat)" : ""));
}
}
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aicity.c
freeciv.PR8992/ai/aicity.c
--- vendor.freeciv.current/ai/aicity.c 2004-10-22 23:16:37.000000000 +0100
+++ freeciv.PR8992/ai/aicity.c 2004-10-23 18:03:46.000000000 +0100
@@ -46,6 +46,7 @@
#include "advdomestic.h"
#include "advmilitary.h"
#include "aidata.h"
+#include "aiferry.h"
#include "aihand.h"
#include "ailog.h"
#include "aitools.h"
@@ -980,6 +981,8 @@
ai_city_choose_build(pplayer, pcity);
} city_list_iterate_end;
+ aiferry_choose_build_global(pplayer);
+
ai_spend_gold(pplayer);
}
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aiferry.c
freeciv.PR8992/ai/aiferry.c
--- vendor.freeciv.current/ai/aiferry.c 2004-10-22 23:16:36.000000000 +0100
+++ freeciv.PR8992/ai/aiferry.c 2004-10-23 18:03:45.000000000 +0100
@@ -16,22 +16,28 @@
#endif
#include "log.h"
+#include "mem.h"
+#include "rand.h"
#include "unit.h"
#include "path_finding.h"
#include "pf_tools.h"
#include "hand_gen.h"
+#include "maphand.h"
#include "unithand.h"
#include "unittools.h"
#include "aidata.h"
#include "aiexplorer.h"
+#include "aihand.h"
+#include "aihunt.h"
#include "ailog.h"
#include "aitools.h"
#include "aiunit.h"
#include "aiferry.h"
+#include "settlers.h" /*for amortize*/
/* =================== constants with special meaning =================== */
@@ -51,6 +57,7 @@
/* Logging in ferry management functions */
#define LOGLEVEL_FERRY LOG_DEBUG
+#define LOGLEVEL_BUILDFERRY LOG_NORMAL
/* Logging in go_by_boat functions */
#define LOGLEVEL_GOBYBOAT LOG_DEBUG
/* Logging in find_ferry functions */
@@ -58,7 +65,6 @@
/* Extra consistency checks */
#define DEBUG_FERRY_STATS 0
-
/* ========= managing statistics and boat/passanger assignments ======== */
/**************************************************************************
@@ -73,7 +79,7 @@
ai->stats.available_boats = 0;
unit_list_iterate(pplayer->units, punit) {
- if (is_sailing_unit(punit) && is_ground_units_transport(punit)) {
+ if (unit_has_role(punit->type, L_FERRYBOAT)) {
ai->stats.boats++;
if (punit->ai.passenger == FERRY_AVAILABLE) {
ai->stats.available_boats++;
@@ -95,8 +101,8 @@
struct ai_data *ai = ai_data_get(pplayer);
int n = 1;
- freelog(LOG_NORMAL, "Boat stats for %s[%d]",
- pplayer->name, pplayer->player_no);
+ freelog(LOG_NORMAL, "Boat stats for %s[%d] in turn %d",
+ pplayer->name, pplayer->player_no, game.turn);
freelog(LOG_NORMAL, "Registered: %d free out of total %d",
ai->stats.available_boats, ai->stats.boats);
unit_list_iterate(pplayer->units, punit) {
@@ -867,3 +873,734 @@
return;
}
+
+/**************************************************************************
+ A cost function for a sea unit which allows going one step into the land.
+
+ Things to remember: we should prevent going from land to anywhere, unless
+ we are leaving a city, in which case we can move into the ocean but not
+ into the land.
+**************************************************************************/
+static int overlap_move(const struct tile *ptile, enum direction8 dir,
+ const struct tile *ptile1, struct pf_parameter *param)
+{
+ if (is_ocean(map_get_terrain(ptile))) {
+ return SINGLE_MOVE;
+ } else if (is_allied_city_tile(ptile, param->owner)
+ && is_ocean(map_get_terrain(ptile1))) {
+ return SINGLE_MOVE;
+ }
+
+ return PF_IMPOSSIBLE_MC;
+}
+
+/* Least Common Multiple of 2,3,..,8 (a very divisible number) */
+#define DENOM 840
+
+/*
+ * Constants for the shipping model used by estimate_cost.
+ * These values are chosen to produce a reasonably accurate simulation
+ * for a wide range of games.
+ *
+ * HUNT_RATE:
+ * How rapidly hunters can sink ferries (100==about as rapidly as ferries
+ * can deliver, all other factors equal).
+ * Should be <100 because a ferry can deliver and be sunk in one turn.
+ * Important when there are many hunters.
+ * BATTLE_RATE:
+ * How rapidly hunters and escorts can sink each other
+ * (100==about as rapidly as ferries can deliver, all other factors equal).
+ * Important when there are many escorts.
+ */
+#define HUNT_RATE 70
+#define BATTLE_RATE 70
+
+/*
+ * Constants for the cost model used by estimate_cost.
+ * These values are harder to decide than the constants used for the shipping
+ * model, being somewhat subjective.
+ * The costs are in arbitrary units, so it is the relative values that matter.
+ *
+ * BUILD_COST:
+ * The cost of building a ferry.
+ * Fix this at 100 and vary the other costs relative to it.
+ * PASSENGER_COST:
+ * The cost of a passenger being sunk while on a ferry.
+ * WAIT_COST:
+ * The cost of having a passenger waiting to arrive for one turn.
+ * IDLE_COST:
+ * The cost of having a ferry idle (that is, not carrying a passenger)
+ * for one turn.
+ *
+ * The value BUILD_COST/WAIT_COST is roughly the maximum number of turns
+ * that a unit may await a ferry; if a unit would wait longer than that,
+ * the AI would be better off building another ferry to shorten the waiting
+ * time.
+ * The value 100%*IDLE_COST/(IDLE_COST+WAIT_COST) is roughly the minimum
+ * acceptable utilisation of the ferries; if the utilisation is lower than
+ * that, the AI would be better off with fewer ferries. If ferries are
+ * only 'exporting', which is the usual case, the ferries will be empty
+ * for their return journeys and utilisation greater than 50% difficult,
+ * therefore have IDLE_COST<=WAIT_COST.
+ */
+#define BUILD_COST 100
+#define PASSENGER_COST 100
+#define WAIT_COST 33
+#define IDLE_COST 22
+/**************************************************************************
+ Estimate the total cost of starting to build a given number of ferries
+ this turn.
+ The total cost is the cost of the new ferries, plus the subsequent costs
+ due to waiting passengers, idle passengers and idle ferries.
+ The estimation uses two models: a 'shipping model' for estimating movement
+ and combat of ships, and a 'cost model' for estimating the cost of the
+ ship movements.
+
+ Building more ferries decreases the costs of waiting passengers,
+ hence there will be an optimum number of ferries to build.
+
+ The calcualtion uses numbers scaled by factor DENOM.
+**************************************************************************/
+static int estimate_cost(unsigned int psngrs, unsigned int boats,
+ unsigned int avail_boats,
+ Unit_Type_id boattype,
+ unsigned int turns_horizon,
+ const unsigned int extra_passengers[],
+ const unsigned int extra_escorts[],
+ unsigned int journey_length,
+ unsigned int n_straits,
+ unsigned int hunters, unsigned int escorts,
+ unsigned int build)
+{
+ /* Assess the capabilities of the boats, assuming:
+ * *all boats have the same movement rate
+ * *the ferries are vulnerable to hunting
+ * *hunters and escorts are vulnerable to each other
+ */
+ unsigned int move_rate = get_unit_type(boattype)->move_rate;
+ unsigned int base_rate = (DENOM*DENOM*move_rate)
+ /(journey_length * SINGLE_MOVE);
+ unsigned int ferry_rate = base_rate;
+ unsigned int hunt_rate = base_rate*HUNT_RATE/100;
+ unsigned int battle_rate = base_rate*BATTLE_RATE/100;
+
+ assert(1 <= n_straits);
+
+ int cost = 0;
+ {/* Run a simple simulation of the ferries in this sea, making the following
+ * assumptions:
+ * *all journeys take the same time
+ * *maximum of 1 passenger per boat
+ * *we can discount future costs at the usual amortisation rate
+ * *all passengers are equally valuable
+ * *we can treat numbers as continuous variables
+ * *all ships are uniformly distributed
+ * *each hunter can sink at most one ferry each turn
+ * *each warship can sink at most one warship each turn
+ * *ferries cross between straits, and hunters lurk at straits
+ * *new ferries appear instantly
+ * (that is, gold is likely to be spent to buy them)
+ * *each extra ferry we build replaces one passenger we might have built
+ * *we will build additional ferries to replace losses
+ */
+ unsigned int deflate = DENOM;
+ unsigned int t;
+ unsigned int used_boats;
+ unsigned int lost_psngrs = 0;
+ /*future passengers replaced by ferries:*/
+ unsigned int extra_skipped = build;
+
+
+ {/*rescale, so can use integer arithmetic for continuous variables*/
+ boats *= DENOM;
+ psngrs *= DENOM;
+ avail_boats *= DENOM;
+ hunters *= DENOM;
+ escorts *= DENOM;
+ build *= DENOM;
+ extra_skipped *= DENOM;
+ }
+ {/*build the new boats*/
+ boats += build;
+ avail_boats += build;
+ }
+ /*spread the hunters out to attack all shipping, not only ours:*/
+ hunters /= n_straits;
+
+ used_boats = boats - avail_boats;
+
+ for(t = 0; t < turns_horizon; t++) {
+ unsigned int sinkings;
+ int turn_cost = WAIT_COST * (psngrs + used_boats)
+ + IDLE_COST * avail_boats
+ + BUILD_COST * build
+ + PASSENGER_COST * lost_psngrs;
+ turn_cost = (turn_cost * deflate)/DENOM;
+ cost += turn_cost;
+ freelog(LOGLEVEL_BUILDFERRY,
+ "Ferries sim.: t=%d b=%d a=%d p=%d h=%d e=%d D=%d C=%d",
+ t, boats, avail_boats, psngrs, hunters, escorts,
+ deflate, turn_cost);
+
+ {/*pick up and put down some passengers*/
+ /* Calculate together so a boat can not pick up and deliver
+ * in one turn*/
+ unsigned int deliveries =
+ MIN(used_boats, (used_boats * ferry_rate)/DENOM);
+ unsigned int pairs = MIN(psngrs, avail_boats);
+ unsigned int pickups = MIN(pairs, (pairs * ferry_rate)/DENOM);
+ avail_boats += deliveries;
+ avail_boats -= pickups;
+ used_boats += pickups;
+ used_boats -= deliveries;
+ psngrs -= pickups;
+ }
+ {/*sink some ferries*/
+ unsigned int pairs = MIN(boats, hunters);
+ sinkings = MIN(pairs, (pairs * hunt_rate)/DENOM);
+ boats -= sinkings;
+ /*target loaded ferries first*/
+ if (used_boats < sinkings) {
+ /*sink them all*/
+ sinkings -= used_boats;
+ lost_psngrs = used_boats;
+ used_boats = 0;
+ /*now target the empty ferries*/
+ assert(sinkings <= avail_boats);
+ avail_boats -= sinkings;
+ }else{/*empty ferries ignored this turn*/
+ lost_psngrs = sinkings;
+ used_boats -= sinkings;
+ }
+ }
+ {/*fight naval battles*/
+ unsigned int pairs = MIN(escorts, hunters);
+ unsigned int battle_sinkings = MIN(pairs, (pairs * battle_rate)/DENOM);
+ escorts -= battle_sinkings;
+ hunters -= battle_sinkings;
+ }
+ {/*replace sunk ferries*/
+ extra_skipped += sinkings;
+ build = sinkings;
+ boats += build;
+ avail_boats += build;
+ }
+ {/*build more passengers*/
+ unsigned int extra = extra_passengers[t] * DENOM;
+ if (extra_skipped && extra <= extra_skipped) {
+ /*We built ferries instead of all the passengers
+ *we might have built this turn*/
+ extra_skipped -= extra;
+ } else if (extra_skipped && extra) {
+ /*We built ferries instead of some of the passengers
+ *we might have built this turn*/
+ psngrs += extra - extra_skipped;
+ extra_skipped = 0;
+ } else {
+ psngrs += extra;
+ }
+ }
+ /*build escorts*/
+ escorts += DENOM*extra_escorts[t];
+
+ /*adjust for inflation*/
+ deflate = (deflate * (MORT - 1)) / MORT;
+
+ assert(used_boats == boats - avail_boats);
+ }
+ }
+
+ return cost;
+}
+
+/****************************************************************************
+ Calculate some geography metrics that are useful for assessing ferry needs.
+ Calculating these, rather than using constants, is important for unusual
+ maps.
+
+ SPRAWL:
+ This adjusts the distances to account for peninsulas,
+ which narrow the straits between islands.
+ Assumed to be the same for all map generators.
+ COAST_LEGS:
+ A typical journey is considered to consist of a leg across a strait
+ plus one or two legs along a coast. This constant is the total length
+ of the coastal legs, relative to the size of a typical island.
+
+ *n_straits:
+ the number of straits across which we will be ferrying passengers;
+ less than the actual number of straits, assuming our nation will be
+ expanding at its borders.
+ *journey_length:
+ the length of a typical sea journey, multiplied by DENOM
+****************************************************************************/
+#define SPRAWL 1.8
+#define COAST_LEGS 0.7
+static void ferry_geography(unsigned int *journey_length,
+ unsigned int *n_straits)
+{
+ /*
+ * Just like the human players, the AI uses meta game information
+ * to help decide its strategy.
+ */
+ double globe_area = map.xsize*map.ysize;
+ double n_islands = map.num_continents;
+ double territory_area, territory_size;
+ double square_island_size, island_size, straits_size;
+
+ *n_straits = sqrt(n_islands);
+
+ /*The size of a single island, including territorial waters:*/
+ territory_area = globe_area/n_islands;
+ territory_size = sqrt(territory_area);
+
+ square_island_size = sqrt(territory_area*map.landpercent/100.0);
+ island_size = SPRAWL*square_island_size;
+ straits_size = MAX(1.0, territory_size - square_island_size*sqrt(SPRAWL));
+
+ *journey_length = (straits_size + island_size*COAST_LEGS)*DENOM;
+
+ freelog(LOGLEVEL_BUILDFERRY,
+ "Seas: islands %3.1fX%3.1f, straits %3.1fX%d, journey %d",
+ island_size, n_islands, straits_size, *n_straits, *journey_length);
+ assert(0 < island_size);
+ assert(0 < straits_size);
+ assert(0 < journey_length);
+ assert(0 < n_straits);
+}
+#undef DENOM
+
+/****************************************************************************
+ Convert facts about a sea into an opinion about how many boats to build
+ for that sea.
+
+ Desiradata for building more boats:
+ * if we have many passengers waiting,
+ * if our boats are slow and have far to travel
+ * if we expect many more passengers in the future
+ * if we expect heavy losses from enemy hunters
+
+ The function does a cost-benefit analysis for several values for the number
+ of boats to build, and returns the value that gives the greatest profit.
+ The implementation exploits the fact that the cost function has a well defined
+ minimum and we expect the optimum to be a small value.
+ However, it overides that calculation to prevent building boats on ponds
+ and to prevent passengers waiting forever.
+****************************************************************************/
+static unsigned int new_boats_to_build(unsigned int psngrs, unsigned int boats,
+ unsigned int avail_boats,
+ Unit_Type_id boattype,
+ unsigned int turns_horizon,
+ const unsigned int extra_passengers[],
+ const unsigned int extra_escorts[],
+ unsigned int journey_length,
+ unsigned int n_straits,
+ unsigned int area,
+ unsigned int hunters,
+ unsigned int escorts)
+{
+ bool force_no_build = (area < 49);/*no boats on ponds*/
+ bool force_build = !force_no_build && (0 == boats && 0 < psngrs);
+ unsigned int build = 0;
+ int previous_cost, cost = FC_INFINITY;
+
+ /*Build the number of boats that minimises the total cost*/
+ do {
+ previous_cost = cost;
+ cost = estimate_cost(psngrs, boats, avail_boats, boattype,
+ turns_horizon, extra_passengers, extra_escorts,
+ journey_length, n_straits,
+ hunters, escorts,
+ build);
+ freelog(LOGLEVEL_BUILDFERRY, "Ferries: building %d costs %d",
+ build, cost);
+ build++;
+ }while(cost < previous_cost);
+ build -= 2;
+
+ if (0 == build && force_build) {
+ /*Ensure we will always have at least one ferry
+ *for each sea that has passengers.
+ *Prevents passengers waiting forever*/
+ build = 1;
+ } else if (force_no_build) {
+ build = 0;
+ }
+
+ return build;
+}
+
+/****************************************************************************
+ Evaluate how suitable a city is as a ferry builder.
+ Larger values mean more suitable. Non negative, 0 means unsuitable.
+
+ Desiradata:
+ * Only cities on the shore of the current ocean are suitable.
+ * Only cities not already building ferries are suitable.
+ * Cities that can complete a boat sooner are better.
+ * Cities that want a boat themselves are better.
+ * Cities building defenders are unsuitable.
+ * Cities with port facilities are better.
+****************************************************************************/
+static int ferry_builder_score(struct player *pplayer, struct city *acity,
+ Unit_Type_id boattype,
+ unsigned int turns_horizon)
+{
+ int score = 0;
+ if (acity->ai.founder_want == 1 && acity->ai.choice.need_boat) {
+ Impr_Type_id port_facility;
+ int turns = city_turns_to_build(acity, boattype, TRUE, TRUE);
+ assert(can_build_unit(acity, boattype));
+
+ /*Prefer building veteran units (resistant to hunters)*/
+ port_facility = ai_find_source_building(pplayer, EFT_SEA_VETERAN);
+ if (port_facility != B_LAST && city_got_building(acity, port_facility)) {
+ turns -= turns/4;
+ }
+
+ /* A ferry is a non military unit, so prefer selecting a city that is
+ * building a non military unit anyway*/
+ if (acity->ai.choice.type == CT_NONMIL) {
+ turns -= turns/3;
+ }
+
+ /* Sooner is better, but if it will take longer than turns_horizon to
+ * build, our deicision making process will be too poor,
+ * and we might as well wait until we have better information.
+ */
+ score = MAX(0, (int)turns_horizon - turns);
+ }
+ return score;
+}
+
+/****************************************************************************
+ Whether a unit type is suitable as a convoy raider or convoy escort
+****************************************************************************/
+static bool is_warship_type(Unit_Type_id type_id)
+{
+ struct unit_type *type = get_unit_type(type_id);
+ int attack_power = type->attack_strength * type->hp * type->firepower;
+
+ return (SEA_MOVING == type->move_type)
+ && (2 * SINGLE_MOVE <= type->move_rate)
+ && 1 < attack_power
+ && (unit_type_flag(type_id, F_PARTIAL_INVIS)
+ || type->transport_capacity < type->attack_strength);
+}
+
+/*
+ * The extra 'want' for each currently waiting passenger.
+ */
+#define PASSENGER_FERRY_WANT 200
+/*
+ * The maximum number of turns to look ahead.
+ * For each city, the code looks ahead no further than the completion of the
+ * item currently being built. This shoudl therefore not be much longer
+ * than a typical build time.
+ */
+#define MAX_TURNS_HORIZON 10
+
+/****************************************************************************
+ A global ferry build selector. Estimates our want for the boats and finds
+ cities who will build them.
+
+ FIXME: Gross hack, uses pcity->ai.founder_want field for its local
+ calculations.
+ 0: unprocessed or non-coastal
+ 1: on the coast of the current ocean and
+ future need for boats has been counted
+ 2: on the coast of the current ocean and
+ future need for boats has been counted and
+ is building a ferry
+ 3: processed
+****************************************************************************/
+void aiferry_choose_build_global(struct player *pplayer)
+{
+ struct city *pcity;
+ /* The worst case is that each of our cities
+ * is on the coast of a different ocean:*/
+ int inf_loop_guard = city_list_size(&pplayer->cities);
+
+ /*The harder the AI, the further ahead it looks:*/
+ unsigned int turns_horizon = MAX(2, MAX_TURNS_HORIZON
+ - (2*MAX_TURNS_HORIZON
+ *pplayer->ai.fuzzy/1000));
+ /*extra_passengers[t] = increment in passengers in turn t from now*/
+ unsigned int extra_passengers[MAX_TURNS_HORIZON];
+ /*extra_escorts[t] = increment in escorts in turn t from now*/
+ unsigned int extra_escorts[MAX_TURNS_HORIZON];
+ /* Path-finding stuff */
+ struct pf_map *pfmap;
+ struct pf_parameter parameter;
+
+ /*Choose type of boats to build*/
+ Unit_Type_id boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
+
+ /*Geographical information*/
+ unsigned int journey_length;
+ unsigned int n_straits;
+
+
+
+ if (boattype == U_LAST) {
+ freelog(LOGLEVEL_BUILDFERRY,
+ "Ferries: %s lacks the technology to build boats",
+ pplayer->name);
+ return;
+ }
+
+ ferry_geography(&journey_length, &n_straits);
+
+ /* Initialize */
+ city_list_iterate(pplayer->cities, acity) {
+ acity->ai.founder_want = 0;
+ } city_list_iterate_end;
+
+ parameter.turn_mode = TM_NONE;
+ parameter.get_MC = overlap_move; /*an ocean and its shore*/
+ parameter.get_TB = NULL;
+ parameter.get_EC = NULL;
+ parameter.get_costs = NULL;
+ parameter.get_zoc = NULL;
+ parameter.is_pos_dangerous = NULL;
+ BV_CLR_ALL(parameter.unit_flags);
+ parameter.owner = pplayer;
+ parameter.omniscience = TRUE; /*this code handles ignorance itself*/
+ /* These don't matter */
+ parameter.moves_left_initially = 0;
+ parameter.move_rate = 3;
+
+ do {/*each ocean for which we have coastal cities*/
+ unsigned int future_psngrs = 0, psngrs = 0;
+ unsigned int future_escorts = 0, escorts = 0;
+ unsigned int boats = 0, avail_boats = 0;
+ unsigned int hunters_seen = 0, sea_area = 0, n_cities = 0;
+ /*Nuber of locations that can hold enemy hunters:*/
+ unsigned int danger_area = 0, danger_area_known = 0, danger_area_seen = 0;
+ int ferry_want = 0;
+ unsigned int boats_to_be_built, t, hunters_guess;
+
+ /* Find an unprocessed coastal city;
+ * such a city is on the shore of an unprocessed ocean. */
+ pcity = NULL;
+ city_list_iterate(pplayer->cities, acity) {
+ if (acity->ai.founder_want == 0
+ && is_ocean_near_tile(acity->tile)) {
+ pcity = acity;
+ break;
+ }
+ } city_list_iterate_end;
+
+ if (!pcity) {/*no more oceans*/
+ break;
+ }
+
+ /* Get a map of the sea plus shore accessible from pcity*/
+ /* If the city is adjacent to more than one ocean,
+ * or oceans are accessible from the city through channels in allied
+ * cities, this processes all those oceans as one sea.*/
+ parameter.start_tile = pcity->tile;
+ pfmap = pf_create_map(¶meter);
+
+ /* Part 1: measure the demand for boats for this ocean*/
+
+ for(t = 0; t < turns_horizon; t++) {
+ extra_passengers[t] = 0;
+ extra_escorts[t] = 0;
+ }
+
+ /* We want to consider the place we are currently in too, hence the
+ * do-while loop */
+ do {/*all tiles in the sea or on its shore*/
+ struct pf_position pos;
+ struct city *acity;
+ bool ocean, is_danger_area;
+
+ pf_next_get_position(pfmap, &pos);
+ acity = map_get_city(pos.tile);
+ ocean = is_ocean(map_get_terrain(pos.tile));
+ is_danger_area = ocean || (acity
+ && DS_WAR == pplayer_get_diplstate(
+ get_player(acity->owner), pplayer)->type);
+ if (ocean) {
+ sea_area++;
+ }
+ if (is_danger_area) {
+ danger_area++;
+ };
+
+ if (ai_handicap(pplayer, H_MAP) && !map_is_known(pos.tile, pplayer)) {
+ /* The tile is unknown */
+ continue;
+ }
+
+ if (is_danger_area) {
+ danger_area_known++;
+ };
+
+ if (ai_handicap(pplayer, H_FOG)
+ && !map_is_known_and_seen(pos.tile, pplayer)) {
+ /* The tile is fogged */
+ continue;
+ }
+ if (is_danger_area) {
+ danger_area_seen++;
+ };
+
+ /* Examine cities on the shore of this sea that are building units
+ * that will affect sea transport on this sea.*/
+ if (acity && acity->owner == pplayer->player_no) {
+ bool is_building_unit = is_unit_choice_type(acity->ai.choice.type);
+ int turns_to_build =
+ is_building_unit?
+ city_turns_to_build(acity, acity->ai.choice.choice, is_building_unit,
+ TRUE)
+ :FC_INFINITY;
+ unsigned int te = MIN(turns_to_build, turns_horizon-1);
+ assert(0 < turns_to_build);
+
+ assert(acity->ai.founder_want == 0);
+ acity->ai.founder_want = 1;
+
+ n_cities++;
+ if (acity->ai.choice.need_boat) {
+ future_psngrs++;
+ extra_passengers[te]++;
+ ferry_want += acity->ai.choice.want;
+ } else if (is_building_unit
+ && is_warship_type(acity->ai.choice.choice)) {
+ future_escorts++;
+ extra_escorts[te]++;
+ }
+ }
+
+ /* Update information about sea units in and around this sea,
+ * for the units on this tile*/
+ unit_list_iterate(pos.tile->units, aunit) {
+ struct player *owner = get_player(aunit->owner);
+ bool warship = is_warship_type(aunit->type);
+ if (warship && DS_WAR == pplayer_get_diplstate(owner, pplayer)->type) {
+ /*a danger to our shipping*/
+ hunters_seen++;
+ }
+ if (owner != pplayer) {
+ continue;
+ } else if (unit_has_role(aunit->type, L_FERRYBOAT)) {
+ boats++;
+ if (aunit->ai.passenger == FERRY_AVAILABLE) {
+ avail_boats++;
+ } else if (aunit->ai.passenger == 0) {
+ freelog(LOG_ERROR, "Passenger field set to 0");
+ avail_boats++;
+ }
+ } else if (aunit->ai.ferryboat == FERRY_WANTED) {
+ psngrs++;
+ ferry_want += PASSENGER_FERRY_WANT;
+ } else if (warship) {
+ escorts++;
+ }
+ } unit_list_iterate_end;
+ } while (pf_next(pfmap));
+ pf_destroy_map(pfmap);
+
+ /*FIXME: also consider air units in or around the sea*/
+
+ /*convert total to average*/
+ ferry_want = ferry_want/MAX(1, psngrs+future_psngrs);
+
+ {/*extrapolate from the known to the unknown (non omniscient AI)*/
+ assert(danger_area_known <= danger_area);
+ assert(danger_area_seen <= danger_area_known);
+ if (danger_area_known < danger_area) {/*ignorant of geography*/
+ /*The AI guesses, but the guess is more accurate the more it knows.*/
+ unsigned int unknown = danger_area - danger_area_known;
+ unsigned int danger_area_guess = danger_area_known + myrand(2*unknown);
+ hunters_guess = (hunters_seen * danger_area_guess)/danger_area_seen;
+ } else if (danger_area_seen < danger_area) {
+ /*ignorant of current dispositions*/
+ hunters_guess = (hunters_seen * danger_area)/danger_area_seen;
+ } else {/*knows all*/
+ hunters_guess = hunters_seen;
+ }
+ assert(hunters_seen <= hunters_guess);
+ }
+
+ freelog(LOGLEVEL_BUILDFERRY,
+ "Sea near %s's %s: %d/%d hunters, %d+%d escorts",
+ pplayer->name, pcity->name, hunters_seen, hunters_guess,
+ escorts, future_escorts);
+ freelog(LOGLEVEL_BUILDFERRY, "Sea near %s's %s: %d/%d boats, "
+ "%d+%d/%d waiting, want %d", pplayer->name, pcity->name,
+ avail_boats, boats, psngrs, future_psngrs, n_cities, ferry_want);
+ assert(avail_boats <= boats);
+
+ /* Part 2: Decide how many boats we want built */
+ boats_to_be_built = new_boats_to_build(psngrs, boats, avail_boats,
+ boattype,
+ turns_horizon, extra_passengers,
+ extra_escorts,
+ journey_length, n_straits, sea_area,
+ hunters_guess, escorts);
+ freelog(LOGLEVEL_BUILDFERRY,
+ "Sea near %s's %s: should build %d boats",
+ pplayer->name, pcity->name, boats_to_be_built);
+
+ /* Part 3: Decide where to build the boats */
+ while (boats_to_be_built > 0) {
+ int best = 0;
+ struct city *bestcity = NULL;
+
+ /*Find the best city to build trhe next ferry*/
+ city_list_iterate(pplayer->cities, acity) {
+ int score = ferry_builder_score(pplayer, acity, boattype,
+ turns_horizon);
+ if (best < score) {
+ assert(is_ocean_near_tile(pcity->tile));
+ best = score;
+ bestcity = acity;
+ }
+ } city_list_iterate_end;
+
+ if (!bestcity) {
+ break;
+ }
+
+ /* FIXME: separate a function ai_set_build from
+ * aicity.c:ai_city_choose_build and use it here */
+ CITY_LOG(LOGLEVEL_BUILDFERRY, bestcity, "will build a boat");
+ bestcity->currently_building = boattype;
+ bestcity->is_building_unit = TRUE;
+ bestcity->ai.founder_want = 2; /*can not build another ferry here*/
+ boats_to_be_built--;
+ }
+
+ if (0 < boats_to_be_built) {
+ freelog(LOGLEVEL_BUILDFERRY,
+ "Sea near %s's %s: unable to build %d boats",
+ pplayer->name, pcity->name, boats_to_be_built);
+ }
+
+ {/*Adjust wants in the cities needing or building ferries*/
+ city_list_iterate(pplayer->cities, acity) {
+ if (acity->ai.founder_want == 2) {
+ /*Building a ferry here.*/
+ acity->ai.choice.want = ferry_want;
+ } else if(0 < boats_to_be_built && acity->ai.founder_want == 1
+ && acity->ai.choice.need_boat && ai_fuzzy(pplayer, TRUE)) {
+ /*We have a shortage, and this city will make the shortage worse,
+ so spending gold here would be foolish*/
+ acity->ai.choice.want /= 2;
+ }
+ } city_list_iterate_end;
+ }
+
+ /* Part 4: Cleanup */
+ city_list_iterate(pplayer->cities, acity) {
+ if (acity->ai.founder_want == 1 || acity->ai.founder_want == 2) {
+ acity->ai.founder_want = 3;
+ }
+ } city_list_iterate_end;
+
+ inf_loop_guard--;
+ } while(inf_loop_guard > 0);
+}
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aiferry.h
freeciv.PR8992/ai/aiferry.h
--- vendor.freeciv.current/ai/aiferry.h 2004-10-22 23:16:36.000000000 +0100
+++ freeciv.PR8992/ai/aiferry.h 2004-10-23 18:03:45.000000000 +0100
@@ -48,4 +48,10 @@
*/
void ai_manage_ferryboat(struct player *pplayer, struct unit *punit);
+/*
+ * A function for a centralized (i.e. per-civilization rather than per-city
+ * estimation of need to build more ferries and where to build them
+ */
+void aiferry_choose_build_global(struct player *pplayer);
+
#endif /* FC__AIFERRY_H */
Only in vendor.freeciv.current/data/nation: Makefile.am
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/diff_ignore
freeciv.PR8992/diff_ignore
--- vendor.freeciv.current/diff_ignore 2004-10-22 23:16:37.000000000 +0100
+++ freeciv.PR8992/diff_ignore 2004-10-23 18:03:47.000000000 +0100
@@ -17,6 +17,7 @@
*~
.#*
.deps
+.svn
CVS
Freeciv.h
Makefile
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Benedict Adamson, 2004/10/06
- [freeciv-ai] (PR#8992) Patch: Centralised ferry building, Benedict Adamson, 2004/10/12
- [freeciv-ai] (PR#8992) Patch: Centralised ferry building,
Benedict Adamson <=
- [freeciv-ai] (PR#8992) Patch: Building ferries, Jason Short, 2004/10/24
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Benedict Adamson, 2004/10/30
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Per I. Mathisen, 2004/10/30
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Benedict Adamson, 2004/10/30
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Per I. Mathisen, 2004/10/30
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Benoit Hudson, 2004/10/30
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Benedict Adamson, 2004/10/31
- [freeciv-ai] Re: (PR#8992) Patch: Building ferries, Benedict Adamson, 2004/10/31
|
|
