Freeciv

/************************************************************************//**

Find the best pair-wise trade route, ignoring transit time.

****************************************************************************/

static void caravan_optimize_notransit(const struct unit *caravan,

const struct caravan_parameter *param,

struct caravan_result *best)

{

struct player *pplayer = unit_owner(caravan);

/* Iterate over all cities we own (since the caravan could change its

* home city); iterate over all cities we know about (places the caravan

* can go to); pick out the best trade route. */

city_list_iterate(pplayer->cities, src) {

players_iterate(dest_owner) {

if (does_foreign_trade_param_allow(param, pplayer, dest_owner)) {

city_list_iterate(dest_owner->cities, dest) {

struct caravan_result current;

caravan_result_init(&current, src, dest, 0);

get_discounted_reward(caravan, param, &current);

if (caravan_result_compare(&current, best) > 0) {

*best = current;

}

} city_list_iterate_end;

}

} players_iterate_end;

} city_list_iterate_end;

}

/****************************************************************************

Struct for the caravan_search invocation in

caravan_optimize_withtransit.

****************************************************************************/

struct cowt_data {

const struct caravan_parameter *param;

const struct unit *caravan;

struct caravan_result *best;

bool omniscient;

};

/************************************************************************//**

Callback for the caravan_search invocation in

caravan_optimize_withtransit().

For every city we can reach, use caravan_find_best_destination_withtransit()

as a subroutine.

****************************************************************************/

static bool cowt_callback(const struct civ_map *nmap, void *vdata,

const struct city *pcity,

int arrival_time, int moves_left)

{

struct cowt_data *data = vdata;

const struct unit *caravan = data->caravan;

struct caravan_result current;

caravan_result_init(&current, game_city_by_number(caravan->homecity),

pcity, arrival_time);

/* First, see what benefit we'd get from not changing home city */

get_discounted_reward(caravan, data->param, &current);

if (caravan_result_compare(&current, data->best) > 0) {

*data->best = current;

}

/* Next, try changing home city (if we're allowed to) */

if (city_owner(pcity) == unit_owner(caravan)) {

caravan_find_best_destination_withtransit(

nmap, caravan, data->param, pcity, arrival_time, moves_left, data->omniscient,

&current);

if (caravan_result_compare(&current, data->best) > 0) {

*data->best = current;

}

}

return FALSE; /* Don't stop searching */

}

/************************************************************************//**

Find the best src/dest pair (including possibly changing home city), taking

account of the trip time.

****************************************************************************/

static void caravan_optimize_withtransit(const struct civ_map *nmap,

const struct unit *caravan,

const struct caravan_parameter *param,

struct caravan_result *result,

bool omniscient)

{

struct cowt_data data;

data.param = param;

data.caravan = caravan;

data.best = result;

data.omniscient = omniscient;

caravan_result_init_zero(data.best);

caravan_search_from(nmap, caravan, param, unit_tile(caravan), 0,

caravan->moves_left, omniscient, cowt_callback, &data);

}

/************************************************************************//**

For every city the caravan can change home in, find the best destination.

Return the best src/dest pair by reference (if non-null), and return

the value of that trade route.

****************************************************************************/

void caravan_optimize_allpairs(const struct unit *caravan,

const struct caravan_parameter *param,

struct caravan_result *result, bool omniscient)

{

const struct civ_map *nmap = &(wld.map);

if (param->ignore_transit_time) {

caravan_optimize_notransit(caravan, param, result);

} else {

caravan_optimize_withtransit(nmap, caravan, param, result, omniscient);

}

}

void caravan_optimize_allpairs(const struct unit *caravan,

const struct caravan_parameter *parameter,

struct caravan_result *result, bool omniscient);