Project

Profile

Help

HostedRedmine.com has moved to the Planio platform. All logins and passwords remained the same. All users will be able to login and use Redmine just as before. *Read more...*

Feature #853665 ยป 0030-Improve-cm.-ch-Coding-Style.patch

Marko Lindqvist, 2019-12-23 01:06 PM

View differences:

common/aicore/cm.c
/*****************************************************************************
defines, structs, globals, forward declarations
Defines, structs, globals, forward declarations
*****************************************************************************/
/* Maximal iterations before the search loop is stoped. */
......
#define CM_DEBUG
#endif
/* whether to print every query, or just at cm_free ; matters only
/* Whether to print every query, or just at cm_free ; matters only
if GATHER_TIME_STATS is on */
#define PRINT_TIME_STATS_EVERY_QUERY
......
*
* Specialists are special types; is_specialist is set, and the tile
* vector is empty. We can never run out of specialists.
*/
*/
struct cm_tile_type {
int production[O_LAST];
double estimated_fitness; /* weighted sum of production */
......
}
}
/***************************************************************************
/****************************************************************************
Functions of tile-types.
***************************************************************************/
****************************************************************************/
/************************************************************************//**
Set all production to zero and initialize the vectors for this tile type.
......
tile_vector_init(&newtype->tiles);
tile_type_vector_init(&newtype->better_types);
tile_type_vector_init(&newtype->worse_types);
return newtype;
}
......
equal.
****************************************************************************/
static bool tile_type_equal(const struct cm_tile_type *a,
const struct cm_tile_type *b)
const struct cm_tile_type *b)
{
output_type_iterate(stat_index) {
if (a->production[stat_index] != b->production[stat_index]) {
......
since we have an unlimited number of them.
****************************************************************************/
static bool tile_type_better(const struct cm_tile_type *a,
const struct cm_tile_type *b)
const struct cm_tile_type *b)
{
output_type_iterate(stat_index) {
if (a->production[stat_index] < b->production[stat_index]) {
......
Equivalence is defined in tile_type_equal().
****************************************************************************/
static int tile_type_vector_find_equivalent(
const struct tile_type_vector *vec,
const struct cm_tile_type *ptype)
const struct tile_type_vector *vec,
const struct cm_tile_type *ptype)
{
int i;
......
/************************************************************************//**
Return the number of tile types that are better than this type.
Note this isn't the same as the number of *tiles* that are better. There
Note this isn't the same as the number of *tiles* that are better. There
may be more than one tile of each type (see tile_type_num_tiles).
****************************************************************************/
static int tile_type_num_prereqs(const struct cm_tile_type *ptype)
......
}
/************************************************************************//**
Retrieve a tile type by index. For a given state there are a certain
Retrieve a tile type by index. For a given state there are a certain
number of tile types, which may be iterated over using this function
as a lookup.
****************************************************************************/
static const struct cm_tile_type *tile_type_get(const struct cm_state *state,
int type)
int type)
{
/* Sanity check the index. */
fc_assert_ret_val(0 <= type, NULL);
fc_assert_ret_val(state->lattice.size > type, NULL);
return state->lattice.p[type];
}
/************************************************************************//**
Retrieve a tile of a particular type by index. For a given tile type
Retrieve a tile of a particular type by index. For a given tile type
there are a certain number of tiles (1 or more), which may be iterated
over using this function for index. Don't call this for is_specialist
over using this function for index. Don't call this for is_specialist
types. See also tile_type_num_tiles().
****************************************************************************/
static const struct cm_tile *tile_get(const struct cm_tile_type *ptype, int j)
......
fc_assert_ret_val(!ptype->is_specialist, NULL);
fc_assert_ret_val(0 <= j, NULL);
fc_assert_ret_val(j < ptype->tiles.size, NULL);
return &ptype->tiles.p[j];
}
/**************************************************************************
/****************************************************************************
Functions on the cm_fitness struct.
**************************************************************************/
****************************************************************************/
/************************************************************************//**
Return TRUE iff fitness A is strictly better than fitness B.
......
according to the weights and minimums given in the parameter.
****************************************************************************/
static struct cm_fitness compute_fitness(const int surplus[],
bool disorder, bool happy,
const struct cm_parameter *parameter)
bool disorder, bool happy,
const struct cm_parameter *parameter)
{
struct cm_fitness fitness;
......
return fitness;
}
/***************************************************************************
/****************************************************************************
Handle struct partial_solution.
- perform a deep copy
- convert to city
- convert to cm_result
***************************************************************************/
****************************************************************************/
/************************************************************************//**
Allocate and initialize an empty solution.
......
}
/************************************************************************//**
Free all storage associated with the solution. This is basically the
Free all storage associated with the solution. This is basically the
opposite of init_partial_solution().
****************************************************************************/
static void destroy_partial_solution(struct partial_solution *into)
......
solution must already be allocated).
****************************************************************************/
static void copy_partial_solution(struct partial_solution *dst,
const struct partial_solution *src,
const struct cm_state *state)
const struct partial_solution *src,
const struct cm_state *state)
{
memcpy(dst->worker_counts, src->worker_counts,
sizeof(*dst->worker_counts) * num_types(state));
sizeof(*dst->worker_counts) * num_types(state));
memcpy(dst->prereqs_filled, src->prereqs_filled,
sizeof(*dst->prereqs_filled) * num_types(state));
sizeof(*dst->prereqs_filled) * num_types(state));
memcpy(dst->production, src->production, sizeof(dst->production));
dst->idle = src->idle;
}
/**************************************************************************
/****************************************************************************
Evaluating a completed solution.
**************************************************************************/
****************************************************************************/
/************************************************************************//**
Apply the solution to state->workers_map.
......
}
/************************************************************************//**
Convert the city's surplus numbers into an array. Get the happy/disorder
values, too. This fills in the surplus array and disorder and happy
Convert the city's surplus numbers into an array. Get the happy/disorder
values, too. This fills in the surplus array and disorder and happy
values based on the city's data.
****************************************************************************/
static void get_city_surplus(const struct city *pcity,
int surplus[],
bool *disorder, bool *happy)
int surplus[],
bool *disorder, bool *happy)
{
output_type_iterate(o) {
surplus[o] = pcity->surplus[o];
......
}
/************************************************************************//**
Compute the fitness of the solution. This is a fairly expensive operation.
Compute the fitness of the solution. This is a fairly expensive operation.
****************************************************************************/
static struct cm_fitness evaluate_solution(struct cm_state *state,
const struct partial_solution *soln)
......
}
/************************************************************************//**
Convert the solution into a cm_result. This is a fairly expensive
Convert the solution into a cm_result. This is a fairly expensive
operation.
****************************************************************************/
static void convert_solution_to_result(struct cm_state *state,
const struct partial_solution *soln,
struct cm_result *result)
const struct partial_solution *soln,
struct cm_result *result)
{
struct cm_fitness fitness;
......
result->found_a_valid = fitness.sufficient;
}
/***************************************************************************
/****************************************************************************
Compare functions to allow sorting lattice vectors.
***************************************************************************/
****************************************************************************/
/************************************************************************//**
All the sorting in this code needs to respect the partial order
......
has already been computed.
****************************************************************************/
static int compare_tile_type_by_lattice_order(const struct cm_tile_type *a,
const struct cm_tile_type *b)
const struct cm_tile_type *b)
{
if (a == b) {
return 0;
......
}
/************************************************************************//**
Sort by fitness. Since fitness is monotone in the production,
Sort by fitness. Since fitness is monotone in the production,
if a has higher fitness than b, then a cannot be a child of b, so
this respects the partial order -- unless a and b have equal fitness.
In that case, use compare_tile_type_by_lattice_order.
......
return compare_tile_type_by_lattice_order(*a, *b);
}
/***************************************************************************
/****************************************************************************
Compute the tile-type lattice.
***************************************************************************/
****************************************************************************/
/************************************************************************//**
Compute the production of tile [x,y] and stuff it into the tile type.
Doesn't touch the other fields.
****************************************************************************/
static void compute_tile_production(const struct city *pcity,
const struct tile *ptile,
struct cm_tile_type *out)
const struct tile *ptile,
struct cm_tile_type *out)
{
bool is_celebrating = base_city_celebrating(pcity);
......
tile_type for each specialist type.
****************************************************************************/
static void init_specialist_lattice_nodes(struct tile_type_vector *lattice,
const struct city *pcity)
const struct city *pcity)
{
struct cm_tile_type type;
......
if (city_can_use_specialist(pcity, i)) {
type.spec = i;
output_type_iterate(output) {
type.production[output] = get_specialist_output(pcity, i, output);
type.production[output] = get_specialist_output(pcity, i, output);
} output_type_iterate_end;
tile_type_lattice_add(lattice, &type, 0);
......
wouldn't save us anything later.
****************************************************************************/
static void clean_lattice(struct tile_type_vector *lattice,
const struct city *pcity)
const struct city *pcity)
{
int i, j; /* i is the index we read, j is the index we write */
struct tile_type_vector tofree;
......
much of the domain-specific knowledge.
****************************************************************************/
static void sort_lattice_by_fitness(const struct cm_state *state,
struct tile_type_vector *lattice)
struct tile_type_vector *lattice)
{
int i;
......
/* sort by it */
qsort(lattice->p, lattice->size, sizeof(*lattice->p),
compare_tile_type_by_fitness);
compare_tile_type_by_fitness);
/* fix the lattice indices */
for (i = 0; i < lattice->size; i++) {
......
static int last_choice(struct cm_state *state)
{
fc_assert_ret_val(!choice_stack_empty(state), -1);
return state->choice.stack[state->choice.size - 1];
}
......
We do lots of sanity checking, since many bugs can get caught here.
****************************************************************************/
static void add_workers(struct partial_solution *soln,
int itype, int number,
const struct cm_state *state)
int itype, int number,
const struct cm_state *state)
{
const struct cm_tile_type *ptype = tile_type_get(state, itype);
int newcount;
......
Add just one worker to the solution.
****************************************************************************/
static void add_worker(struct partial_solution *soln,
int itype, const struct cm_state *state)
int itype, const struct cm_state *state)
{
add_workers(soln, itype, 1, state);
}
......
Remove just one worker from the solution.
****************************************************************************/
static void remove_worker(struct partial_solution *soln,
int itype, const struct cm_state *state)
int itype, const struct cm_state *state)
{
add_workers(soln, itype, -1, state);
}
......
True if all tiles better than this type have been used.
****************************************************************************/
static bool prereqs_filled(const struct partial_solution *soln, int type,
const struct cm_state *state)
const struct cm_state *state)
{
const struct cm_tile_type *ptype = tile_type_get(state, type);
int prereqs = tile_type_num_prereqs(ptype);
......
add_worker(&state->current, newchoice, state);
state->choice.stack[state->choice.size] = newchoice;
state->choice.size++;
return TRUE;
}
/************************************************************************//**
Complete the solution by choosing tiles in order off the given
tile lattice.
......
if (ptype->lattice_index < last_worker_choice) {
/* lex-order: we can't use ptype (some other branch
will check this combination, or already did) */
continue;
continue;
}
if (!prereqs_filled(soln, ptype->lattice_index, state)) {
/* don't bother using this tile before all better tiles are used */
......
}
/************************************************************************//**
return number of specialists used in partial solution
Return number of specialists used in partial solution
****************************************************************************/
static int specialists_in_solution(const struct cm_state *state,
const struct partial_solution *soln)
......
This function computes the max-stats produced by a partial solution.
****************************************************************************/
static void compute_max_stats_heuristic(const struct cm_state *state,
const struct partial_solution *soln,
int production[],
int check_choice, bool negative_ok)
const struct partial_solution *soln,
int production[],
int check_choice, bool negative_ok)
{
struct partial_solution solnplus; /* will be soln, plus some tiles */
......
city_tile_iterate(city_map_radius_sq_get(pcity), pcenter, ptile) {
if (is_free_worked(pcity, ptile)) {
base += city_tile_output(pcity, ptile, is_celebrating, stat_index);
base += city_tile_output(pcity, ptile, is_celebrating, stat_index);
}
} city_tile_iterate_end;
pcity->citizen_base[stat_index] = base;
......
= MAX(specialists_amount + state->current.idle - max_content, 0);
int max_luxury = production[O_LUXURY]
+ game.info.happy_cost * specialists_suppress_unhappy;
if (max_luxury < state->min_luxury ) {
log_base(LOG_PRUNE_BRANCH, "--- pruning: disorder (%d + %d*%d < %d)",
production[O_LUXURY],
......
if (!beats_best) {
log_base(LOG_PRUNE_BRANCH, "--- pruning: best is better in all important ways");
}
return beats_best;
}
......
}
/************************************************************************//**
get the tax rates, see city.c
Get the tax rates, see city.c
****************************************************************************/
static void get_tax_rates(const struct player *pplayer, int rates[])
{
const int SCIENCE = 0, TAX = 1, LUXURY = 2;
if (game.info.changable_tax) {
rates[SCIENCE] = pplayer->economic.science;
rates[LUXURY] = pplayer->economic.luxury;
......
rates[LUXURY] = game.info.forced_luxury;
rates[TAX] = game.info.forced_gold;
}
/* ANARCHY */
if (government_of_player(pplayer) == game.government_during_revolution) {
rates[SCIENCE] = 0;
......
The only fields of the state used are the city and parameter.
****************************************************************************/
static double estimate_fitness(const struct cm_state *state,
const int production[])
const int production[])
{
const int SCIENCE = 0, TAX = 1, LUXURY = 2;
const struct city *pcity = state->pcity;
......
sum += estimates[stat_index] * state->parameter.factor[stat_index];
} output_type_iterate_end;
sum += estimates[O_LUXURY];
return sum;
}
/************************************************************************//**
The high-level algorithm is:
......
switch (stat_index) {
case O_SCIENCE:
compare_key_trade_bonus = rates[SCIENCE] * pcity->bonus[O_TRADE] / 100.0;
break;
break;
case O_LUXURY:
compare_key_trade_bonus = rates[LUXURY] * pcity->bonus[O_TRADE] / 100.0;
break;
break;
case O_GOLD:
compare_key_trade_bonus = rates[TAX] * pcity->bonus[O_TRADE] / 100.0;
break;
break;
default:
compare_key_trade_bonus = 0.0;
break;
break;
}
qsort(state->lattice_by_prod[stat_index].p, state->lattice_by_prod[stat_index].size,
sizeof(*state->lattice_by_prod[stat_index].p),
......
init_partial_solution(&state->current, numtypes, city_size_get(pcity),
negative_ok);
state->choice.stack = fc_malloc(city_size_get(pcity)
* sizeof(*state->choice.stack));
* sizeof(*state->choice.stack));
state->choice.size = 0;
/* Initialize workers map */
......
solving anything.
****************************************************************************/
static void begin_search(struct cm_state *state,
const struct cm_parameter *parameter,
const struct cm_parameter *parameter,
bool negative_ok)
{
#ifdef GATHER_TIME_STATS
timer_start(performance.current->wall_timer);
performance.current->query_count++;
#endif
#endif /* GATHER_TIME_STATS */
/* copy the parameter and sort the main lattice by it */
cm_copy_parameter(&state->parameter, parameter);
......
state->best_value = worst_fitness();
destroy_partial_solution(&state->current);
init_partial_solution(&state->current, num_types(state),
city_size_get(state->pcity),
city_size_get(state->pcity),
negative_ok);
state->choice.size = 0;
}
/************************************************************************//**
Clean up after a search.
Currently, does nothing except stop the timer and output.
......
#ifdef PRINT_TIME_STATS_EVERY_QUERY
print_performance(performance.current);
#endif
#endif /* PRINT_TIME_STATS_EVERY_QUERY */
performance.current = NULL;
#endif /* GATHER_TIME_STATS */
......
FC_FREE(state);
}
/************************************************************************//**
Run B&B until we find the best solution.
****************************************************************************/
......
Returns true if the two cm_parameters are equal.
****************************************************************************/
bool cm_are_parameter_equal(const struct cm_parameter *const p1,
const struct cm_parameter *const p2)
const struct cm_parameter *const p2)
{
output_type_iterate(i) {
if (p1->minimal_surplus[i] != p2->minimal_surplus[i]) {
......
Copy the parameter from the source to the destination field.
****************************************************************************/
void cm_copy_parameter(struct cm_parameter *dest,
const struct cm_parameter *const src)
const struct cm_parameter *const src)
{
memcpy(dest, src, sizeof(struct cm_parameter));
}
......
} tile_type_vector_iterate_end;
}
/************************************************************************//**
Print debugging data about a partial CM solution.
****************************************************************************/
......
if (NULL != pwork && pwork == pcity) {
int cx, cy;
city_tile_index_to_xy(&cx, &cy, cindex,
city_map_radius_sq_get(pcity));
log_test(" {%2d,%2d} (%4d,%4d)", cx, cy, TILE_XY(ptile));
common/aicore/cm.h
* the actual city setting.
*/
void cm_query_result(struct city *pcity,
const struct cm_parameter *const parameter,
struct cm_result *result, bool negative_ok);
const struct cm_parameter *const parameter,
struct cm_result *result, bool negative_ok);
/*
* Call this function if the city has changed. To be safe call it
......
/***************** utility methods *************************************/
bool cm_are_parameter_equal(const struct cm_parameter *const p1,
const struct cm_parameter *const p2);
const struct cm_parameter *const p2);
void cm_copy_parameter(struct cm_parameter *dest,
const struct cm_parameter *const src);
const struct cm_parameter *const src);
void cm_init_parameter(struct cm_parameter *dest);
void cm_init_emergency_parameter(struct cm_parameter *dest);
    (1-1/1)