Freeciv-3.3: /fast/freeciv/nightly/main/common/aicore/cm.c File Reference

Freeciv-3.3

Loading...
Searching...
No Matches
Data Structures | Macros | Functions | Variables
cm.c File Reference
`#include <stdlib.h>`
`#include <string.h>`
`#include "fcintl.h"`
`#include "log.h"`
`#include "mem.h"`
`#include "shared.h"`
`#include "support.h"`
`#include "timing.h"`
`#include "city.h"`
`#include "game.h"`
`#include "government.h"`
`#include "map.h"`
`#include "specialist.h"`
`#include "cm.h"`
`#include "specvec.h"`

Go to the source code of this file.

## Data Structures

struct | cm_fitness
struct | cm_tile
struct | cm_tile_type
struct | partial_solution
struct | cm_state

## Macros

#define | CM_MAX_LOOP 27500
#define | CPUHOG_CM_MAX_LOOP (CM_MAX_LOOP * 4)
#define | PRINT_TIME_STATS_EVERY_QUERY
#define | LOG_TIME_STATS LOG_DEBUG
#define | LOG_CM_STATE LOG_DEBUG
#define | LOG_LATTICE LOG_DEBUG
#define | LOG_REACHED_LEAF LOG_DEBUG
#define | LOG_BETTER_LEAF LOG_DEBUG
#define | LOG_PRUNE_BRANCH LOG_DEBUG
#define | SPECVEC_TAG tile
#define | SPECVEC_TYPE struct cm_tile
#define | SPECVEC_TAG tile_type
#define | SPECVEC_TYPE struct cm_tile_type *
#define | tile_type_vector_iterate(vector, var)
#define | tile_type_vector_iterate_end }} VECTOR_ITERATE_END; }
#define | print_tile_type(loglevel, ptype, prefix)
#define | print_lattice(loglevel, lattice)
#define | print_partial_solution(loglevel, soln, state)

## Functions

static int | num_types (const struct cm_state *state)
static void | cm_result_copy (struct cm_result *result, const struct city *pcity, bool *workers_map)
static double | estimate_fitness (const struct cm_state *state, const int production[])
static bool | choice_is_promising (struct cm_state *state, int newchoice, bool negative_ok)
void | cm_init (void)
void | cm_init_citymap (void)
void | cm_clear_cache (struct city *pcity)
void | cm_free (void)
struct cm_result * | cm_result_new (struct city *pcity)
void | cm_result_destroy (struct cm_result *result)
static void | tile_type_init (struct cm_tile_type *type)
static struct cm_tile_type * | tile_type_dup (const struct cm_tile_type *oldtype)
static void | tile_type_destroy (struct cm_tile_type *type)
static void | tile_type_vector_free_all (struct tile_type_vector *vec)
static bool | tile_type_equal (const struct cm_tile_type *a, const struct cm_tile_type *b)
static int | tile_type_better (const struct cm_tile_type *a, const struct cm_tile_type *b)
static int | tile_type_vector_find_equivalent (const struct tile_type_vector *vec, const struct cm_tile_type *ptype)
static int | tile_type_num_tiles (const struct cm_tile_type *type)
static int | tile_type_num_prereqs (const struct cm_tile_type *ptype)
static const struct cm_tile_type * | tile_type_get (const struct cm_state *state, int type)
static const struct cm_tile * | tile_get (const struct cm_tile_type *ptype, int j)
static bool | fitness_better (struct cm_fitness a, struct cm_fitness b)
static struct cm_fitness | worst_fitness (void)
static struct cm_fitness | compute_fitness (const int surplus[], bool disorder, bool happy, const struct cm_parameter *parameter)
static void | init_partial_solution (struct partial_solution *into, int ntypes, int idle, bool negative_ok)
static void | destroy_partial_solution (struct partial_solution *into)
static void | copy_partial_solution (struct partial_solution *dst, const struct partial_solution *src, const struct cm_state *state)
static void | apply_solution (struct cm_state *state, const struct partial_solution *soln)
static void | get_city_surplus (const struct city *pcity, int surplus[], bool *disorder, bool *happy)
static struct cm_fitness | evaluate_solution (struct cm_state *state, const struct partial_solution *soln)
static void | convert_solution_to_result (struct cm_state *state, const struct partial_solution *soln, struct cm_result *result)
static int | compare_tile_type_by_lattice_order (const struct cm_tile_type *a, const struct cm_tile_type *b)
static int | compare_tile_type_by_fitness (const void *va, const void *vb)
static int | compare_tile_type_by_stat (const void *va, const void *vb)
static void | compute_tile_production (const struct city *pcity, const struct tile *ptile, struct cm_tile_type *out)
static void | tile_type_lattice_add (struct tile_type_vector *lattice, const struct cm_tile_type *newtype, int tindex)
static void | init_specialist_lattice_nodes (struct tile_type_vector *lattice, const struct city *pcity)
static void | top_sort_lattice (struct tile_type_vector *lattice)
static void | clean_lattice (struct tile_type_vector *lattice, const struct city *pcity)
static void | sort_lattice_by_fitness (const struct cm_state *state, struct tile_type_vector *lattice)
static void | init_tile_lattice (struct city *pcity, struct tile_type_vector *lattice)
static bool | choice_stack_empty (struct cm_state *state)
static int | last_choice (struct cm_state *state)
static void | add_workers (struct partial_solution *soln, int itype, int number, const struct cm_state *state)
static void | add_worker (struct partial_solution *soln, int itype, const struct cm_state *state)
static void | remove_worker (struct partial_solution *soln, int itype, const struct cm_state *state)
static void | pop_choice (struct cm_state *state)
static bool | prereqs_filled (const struct partial_solution *soln, int type, const struct cm_state *state)
static int | next_choice (struct cm_state *state, int oldchoice, bool negative_ok)
static bool | take_sibling_choice (struct cm_state *state, bool negative_ok)
static bool | take_child_choice (struct cm_state *state, bool negative_ok)
static void | complete_solution (struct partial_solution *soln, const struct cm_state *state, const struct tile_type_vector *lattice)
static int | specialists_in_solution (const struct cm_state *state, const struct partial_solution *soln)
static void | compute_max_stats_heuristic (const struct cm_state *state, const struct partial_solution *soln, int production[], int check_choice, bool negative_ok)
static void | init_min_production (struct cm_state *state)
static void | get_tax_rates (const struct player *pplayer, int rates[])
static bool | bb_next (struct cm_state *state, bool negative_ok)
static struct cm_state * | cm_state_init (struct city *pcity, bool negative_ok)
static int | min_food_surplus_for_fastest_growth (struct cm_state *state)
static void | begin_search (struct cm_state *state, const struct cm_parameter *parameter, bool negative_ok)
static void | end_search (struct cm_state *state)
static void | cm_state_free (struct cm_state *state)
static void | cm_find_best_solution (struct cm_state *state, const struct cm_parameter *const parameter, struct cm_result *result, bool negative_ok)
void | cm_query_result (struct city *pcity, const struct cm_parameter *param, struct cm_result *result, bool negative_ok)
bool | cm_are_parameter_equal (const struct cm_parameter *const p1, const struct cm_parameter *const p2)
void | cm_copy_parameter (struct cm_parameter *dest, const struct cm_parameter *const src)
void | cm_init_parameter (struct cm_parameter *dest)
void | cm_init_emergency_parameter (struct cm_parameter *dest)
int | cm_result_workers (const struct cm_result *result)
int | cm_result_specialists (const struct cm_result *result)
int | cm_result_citizens (const struct cm_result *result)
void | cm_result_from_main_map (struct cm_result *result, const struct city *pcity)
void | cm_print_city (const struct city *pcity)
void | cm_print_result (const struct cm_result *result)

## Variables

static Output_type_id | compare_key
static double | compare_key_trade_bonus

## Macro Definition Documentation

## ◆ CM_MAX_LOOP

#define CM_MAX_LOOP 27500

Definition at line 80 of file cm.c.

## ◆ CPUHOG_CM_MAX_LOOP

#define CPUHOG_CM_MAX_LOOP (CM_MAX_LOOP * 4)

Definition at line 82 of file cm.c.

## ◆ LOG_BETTER_LEAF

#define LOG_BETTER_LEAF LOG_DEBUG

Definition at line 99 of file cm.c.

## ◆ LOG_CM_STATE

#define LOG_CM_STATE LOG_DEBUG

Definition at line 96 of file cm.c.

## ◆ LOG_LATTICE

#define LOG_LATTICE LOG_DEBUG

Definition at line 97 of file cm.c.

## ◆ LOG_PRUNE_BRANCH

#define LOG_PRUNE_BRANCH LOG_DEBUG

Definition at line 100 of file cm.c.

## ◆ LOG_REACHED_LEAF

#define LOG_REACHED_LEAF LOG_DEBUG

Definition at line 98 of file cm.c.

## ◆ LOG_TIME_STATS

#define LOG_TIME_STATS LOG_DEBUG

Definition at line 95 of file cm.c.

## ◆ print_lattice

#define print_lattice | ( |  | loglevel,
|  |  | lattice
| ) |  |

Definition at line 276 of file cm.c.

## ◆ print_partial_solution

#define print_partial_solution | ( |  | loglevel,
|  |  | soln,
|  |  | state
| ) |  |

Definition at line 277 of file cm.c.

## ◆ print_tile_type

#define print_tile_type | ( |  | loglevel,
|  |  | ptype,
|  |  | prefix
| ) |  |

Definition at line 275 of file cm.c.

## ◆ PRINT_TIME_STATS_EVERY_QUERY

#define PRINT_TIME_STATS_EVERY_QUERY

Definition at line 93 of file cm.c.

## ◆ SPECVEC_TAG [1/2]

#define SPECVEC_TAG tile

Definition at line 141 of file cm.c.

## ◆ SPECVEC_TAG [2/2]

#define SPECVEC_TAG tile_type

Definition at line 141 of file cm.c.

## ◆ SPECVEC_TYPE [1/2]

#define SPECVEC_TYPE struct cm_tile

Definition at line 142 of file cm.c.

## ◆ SPECVEC_TYPE [2/2]

#define SPECVEC_TYPE struct cm_tile_type *

Definition at line 142 of file cm.c.

## ◆ tile_type_vector_iterate

#define tile_type_vector_iterate | ( |  | vector,
|  |  | var
| ) |  |

Value:
{ \
struct cm_tile_type *var; \
TYPED_VECTOR_ITERATE(struct cm_tile_type*, vector, var##p) { \
var = *var##p; \
{
incite_cost
char * incite_cost
Definition comments.c:74
cm_tile_type
Definition cm.c:168

Definition at line 149 of file cm.c.

## ◆ tile_type_vector_iterate_end

#define tile_type_vector_iterate_end }} VECTOR_ITERATE_END; }

Definition at line 154 of file cm.c.

## Function Documentation

## ◆ add_worker()

static void add_worker | ( | struct partial_solution * | soln,
|  | int | itype,
|  | const struct cm_state * | state
| ) |  |

static

Add just one worker to the solution.

Definition at line 1361 of file cm.c.

Referenced by compute_max_stats_heuristic(), take_child_choice(), and take_sibling_choice().

## ◆ add_workers()

static void add_workers | ( | struct partial_solution * | soln,
|  | int | itype,
|  | int | number,
|  | const struct cm_state * | state
| ) |  |

static

Update the solution to assign 'number' more workers on to tiles of the given type. 'number' may be negative, in which case we're removing workers. We do lots of sanity checking, since many bugs can get caught here.

Definition at line 1310 of file cm.c.

Referenced by add_worker(), complete_solution(), and remove_worker().

## ◆ apply_solution()

static void apply_solution | ( | struct cm_state * | state,
|  | const struct partial_solution * | soln
| ) |  |

static

Apply the solution to state->workers_map.

Definition at line 700 of file cm.c.

Referenced by convert_solution_to_result(), and evaluate_solution().

## ◆ bb_next()

static bool bb_next | ( | struct cm_state * | state,
|  | bool | negative_ok
| ) |  |

static

The high-level algorithm is:

for each idle worker, non-deterministically choose a position for the idle worker to use

To implement this, we keep a stack of the choices we've made. When we want the next node in the tree, we see if there are any idle workers left. We push an idle worker, and make it take the first field in the lattice. If there are no idle workers left, then we pop out until we can make another choice.

Definition at line 1821 of file cm.c.

Referenced by cm_find_best_solution().

## ◆ begin_search()

static void begin_search | ( | struct cm_state * | state,
|  | const struct cm_parameter * | parameter,
|  | bool | negative_ok
| ) |  |

static

Set the parameter for the state. This is the first step in actually solving anything.

Definition at line 1982 of file cm.c.

Referenced by cm_find_best_solution().

## ◆ choice_is_promising()

static bool choice_is_promising | ( | struct cm_state * | state,
|  | int | newchoice,
|  | bool | negative_ok
| ) |  |

static

A choice is unpromising if isn't better than the best in at least one way. A choice is also unpromising if any of the stats is less than the absolute minimum (in practice, this matters a lot more).

Definition at line 1657 of file cm.c.

Referenced by next_choice().

## ◆ choice_stack_empty()

static bool choice_stack_empty | ( | struct cm_state * | state | ) |

static

Return TRUE iff the stack is empty.

Definition at line 1279 of file cm.c.

Referenced by bb_next(), last_choice(), and pop_choice().

## ◆ clean_lattice()

static void clean_lattice | ( | struct tile_type_vector * | lattice,
|  | const struct city * | pcity
| ) |  |

static

Remove unreachable lattice nodes to speed up processing later. This doesn't reduce the number of evaluations we do, it just reduces the number of times we loop over and reject tile types we can never use.

A node is unreachable if there are fewer available workers than are needed to fill up all predecessors. A node at depth two needs three workers to be reachable, for example (two to fill the predecessors, and one for the tile). We remove a node if its depth is equal to the city size, or larger.

We could clean up the tile arrays in each type (if we have two workers, we can use only the first tile of a depth 1 tile type), but that wouldn't save us anything later.

Definition at line 1156 of file cm.c.

Referenced by init_tile_lattice().

## ◆ cm_are_parameter_equal()

bool cm_are_parameter_equal | ( | const struct cm_parameter *const | p1,
|  | const struct cm_parameter *const | p2
| ) |  |

Returns true if the two cm_parameters are equal.

Definition at line 2138 of file cm.c.

Referenced by append_cma_to_menu_item(), cmafec_preset_get_index_of_parameter(), create_governor_menu(), select_cma_callback(), select_governor_callback(), send_packet_web_city_info_addition_100(), and send_packet_web_cma_set_100().

## ◆ cm_clear_cache()

void cm_clear_cache | ( | struct city * | pcity | ) |

Clear the cache for a city.

Definition at line 322 of file cm.c.

Referenced by apply_result_on_server(), auto_arrange_workers(), city_changed(), and dai_manage_taxes().

## ◆ cm_copy_parameter()

void cm_copy_parameter | ( | struct cm_parameter * | dest,
|  | const struct cm_parameter *const | src
| ) |  |

Copy the parameter from the source to the destination field.

Definition at line 2171 of file cm.c.

Referenced by begin_search(), cmafec_get_fe_parameter(), cmafec_preset_add(), handle_web_cma_set(), ld_cma_callback(), package_city(), popup_load_del_presets_dialog(), and city_dialog::update_sliders().

## ◆ cm_find_best_solution()

static void cm_find_best_solution | ( | struct cm_state * | state,
|  | const struct cm_parameter *const | parameter,
|  | struct cm_result * | result,
|  | bool | negative_ok
| ) |  |

static

Run B&B until we find the best solution.

Definition at line 2048 of file cm.c.

Referenced by cm_query_result().

## ◆ cm_free()

void cm_free | ( | void |  | ) |

Called at the end of a game to free any CM data.

Definition at line 330 of file cm.c.

Referenced by game_free().

## ◆ cm_init()

void cm_init | ( | void |  | ) |

Initialize the CM data at the start of each game. Note the citymap indices will not have been initialized yet (cm_init_citymap is called when they are).

Definition at line 293 of file cm.c.

Referenced by game_init().

## ◆ cm_init_citymap()

void cm_init_citymap | ( | void |  | ) |

Initialize the CM citymap data. This function is called when the city map indices are generated (basically when the topology is set, shortly after the start of the game).

Definition at line 314 of file cm.c.

Referenced by generate_city_map_indices().

## ◆ cm_init_emergency_parameter()

void cm_init_emergency_parameter | ( | struct cm_parameter * | dest | ) |

Initialize the parameter to sane default values that will always produce a result.

Definition at line 2198 of file cm.c.

Referenced by auto_arrange_workers().

## ◆ cm_init_parameter()

void cm_init_parameter | ( | struct cm_parameter * | dest | ) |

Initialize the parameter to sane default values.

Definition at line 2180 of file cm.c.

Referenced by auto_arrange_workers(), cma_get_parameter(), cmafec_get_fe_parameter(), and dai_manage_taxes().

## ◆ cm_print_city()

void cm_print_city | ( | const struct city * | pcity | ) |

Debugging routines. Print debugging information about one city.

Definition at line 2428 of file cm.c.

Referenced by apply_result_on_server(), and auto_arrange_workers().

## ◆ cm_print_result()

void cm_print_result | ( | const struct cm_result * | result | ) |

Print debugging information about a full CM result.

Definition at line 2466 of file cm.c.

Referenced by apply_result_on_server(), and auto_arrange_workers().

## ◆ cm_query_result()

void cm_query_result | ( | struct city * | pcity,
|  | const struct cm_parameter * | param,
|  | struct cm_result * | result,
|  | bool | negative_ok
| ) |  |

Wrapper that actually runs the branch & bound, and returns the best solution.

Definition at line 2120 of file cm.c.

Referenced by auto_arrange_workers(), dai_manage_taxes(), handle_city(), and run_cma_once_callback().

## ◆ cm_result_citizens()

int cm_result_citizens | ( | const struct cm_result * | result | ) |

Count the total number of citizens in the result.

Definition at line 2249 of file cm.c.

Referenced by apply_result_on_server().

## ◆ cm_result_copy()

static void cm_result_copy | ( | struct cm_result * | result,
|  | const struct city * | pcity,
|  | bool * | workers_map
| ) |  |

static

Copy the city's current setup into the cm result structure. 'workers_map' is a bool array with the size city_map_tiles_from_city(pcity). It is TRUE for tiles worked by the city.

Definition at line 2269 of file cm.c.

Referenced by cm_result_from_main_map(), and convert_solution_to_result().

## ◆ cm_result_destroy()

void cm_result_destroy | ( | struct cm_result * | result | ) |

Destroy a cm_result.

Definition at line 368 of file cm.c.

Referenced by apply_result_on_server(), auto_arrange_workers(), dai_manage_taxes(), handle_city(), refresh_cma_dialog(), run_cma_once_callback(), and update_city_cma_dialog().

## ◆ cm_result_from_main_map()

void cm_result_from_main_map | ( | struct cm_result * | result,
|  | const struct city * | pcity
| ) |  |

Copy the city's current setup into the cm result structure. Wrapper for cm_result_main().

Definition at line 2258 of file cm.c.

Referenced by apply_result_on_server(), refresh_cma_dialog(), and update_city_cma_dialog().

## ◆ cm_result_new()

struct cm_result * cm_result_new | ( | struct city * | pcity | ) |

Create a new cm_result.

Definition at line 345 of file cm.c.

Referenced by apply_result_on_server(), auto_arrange_workers(), dai_manage_taxes(), handle_city(), refresh_cma_dialog(), run_cma_once_callback(), and update_city_cma_dialog().

## ◆ cm_result_specialists()

int cm_result_specialists | ( | const struct cm_result * | result | ) |

Count the total number of specialists in the result.

Definition at line 2235 of file cm.c.

Referenced by cm_result_citizens(), and cmafec_get_result_descr().

## ◆ cm_result_workers()

int cm_result_workers | ( | const struct cm_result * | result | ) |

Count the total number of workers in the result.

Definition at line 2215 of file cm.c.

Referenced by cm_print_result(), and cm_result_citizens().

## ◆ cm_state_free()

static void cm_state_free | ( | struct cm_state * | state | ) |

static

Release all the memory allocated by the state.

Definition at line 2031 of file cm.c.

Referenced by cm_query_result().

## ◆ cm_state_init()

static struct cm_state * cm_state_init | ( | struct city * | pcity,
|  | bool | negative_ok
| ) |  |

static

Initialize the state for the branch-and-bound algorithm.

Definition at line 1858 of file cm.c.

Referenced by cm_query_result().

## ◆ compare_tile_type_by_fitness()

static int compare_tile_type_by_fitness | ( | const void * | va,
|  | const void * | vb
| ) |  |

static

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.

Definition at line 888 of file cm.c.

Referenced by sort_lattice_by_fitness().

## ◆ compare_tile_type_by_lattice_order()

static int compare_tile_type_by_lattice_order | ( | const struct cm_tile_type * | a,
|  | const struct cm_tile_type * | b
| ) |  |

static

All the sorting in this code needs to respect the partial order in the lattice: if a is a parent of b, then a must sort before b. This routine enforces that relatively cheaply (without looking through the worse_types vectors of a and b), but requires that lattice_depth has already been computed.

Definition at line 858 of file cm.c.

Referenced by compare_tile_type_by_fitness(), and compare_tile_type_by_stat().

## ◆ compare_tile_type_by_stat()

static int compare_tile_type_by_stat | ( | const void * | va,
|  | const void * | vb
| ) |  |

static

Compare by the production of type compare_key. If a produces more food than b, then a cannot be a child of b, so this respects the partial order – unless a and b produce equal food. In that case, use compare_tile_type_by_lattice_order.

Definition at line 920 of file cm.c.

Referenced by cm_state_init().

## ◆ complete_solution()

static void complete_solution | ( | struct partial_solution * | soln,
|  | const struct cm_state * | state,
|  | const struct tile_type_vector * | lattice
| ) |  |

static

Complete the solution by choosing tiles in order off the given tile lattice.

Definition at line 1508 of file cm.c.

Referenced by compute_max_stats_heuristic().

## ◆ compute_fitness()

static struct cm_fitness compute_fitness | ( | const int | surplus[],
|  | bool | disorder,
|  | bool | happy,
|  | const struct cm_parameter * | parameter
| ) |  |

static

Compute the fitness of the given surplus (and disorder/happy status) according to the weights and minimums given in the parameter.

Definition at line 612 of file cm.c.

Referenced by convert_solution_to_result(), and evaluate_solution().

## ◆ compute_max_stats_heuristic()

static void compute_max_stats_heuristic | ( | const struct cm_state * | state,
|  | const struct partial_solution * | soln,
|  | int | production[],
|  | int | check_choice,
|  | bool | negative_ok
| ) |  |

static

The heuristic: A partial solution cannot produce more food than the amount of food it currently generates plus then placing all its workers on the best food tiles. Similarly with all the other stats. If we take the max along each production, and it's not better than the best in at least one stat, the partial solution isn't worth anything.

This function computes the max-stats produced by a partial solution.

Definition at line 1585 of file cm.c.

Referenced by choice_is_promising().

## ◆ compute_tile_production()

static void compute_tile_production | ( | const struct city * | pcity,
|  | const struct tile * | ptile,
|  | struct cm_tile_type * | out
| ) |  |

static

Compute the production of tile [x,y] and stuff it into the tile type. Doesn't touch the other fields.

Definition at line 958 of file cm.c.

Referenced by init_tile_lattice().

## ◆ convert_solution_to_result()

static void convert_solution_to_result | ( | struct cm_state * | state,
|  | const struct partial_solution * | soln,
|  | struct cm_result * | result
| ) |  |

static

Convert the solution into a cm_result. This is a fairly expensive operation.

Definition at line 823 of file cm.c.

Referenced by cm_find_best_solution().

## ◆ copy_partial_solution()

static void copy_partial_solution | ( | struct partial_solution * | dst,
|  | const struct partial_solution * | src,
|  | const struct cm_state * | state
| ) |  |

static

Copy the source solution into the destination one (the destination solution must already be allocated).

Definition at line 680 of file cm.c.

Referenced by bb_next(), and compute_max_stats_heuristic().

## ◆ destroy_partial_solution()

static void destroy_partial_solution | ( | struct partial_solution * | into | ) |

static

Free all storage associated with the solution. This is basically the opposite of init_partial_solution().

Definition at line 670 of file cm.c.

Referenced by begin_search(), cm_state_free(), and compute_max_stats_heuristic().

## ◆ end_search()

static void end_search | ( | struct cm_state * | state | ) |

static

Clean up after a search. Currently, does nothing except stop the timer and output.

Definition at line 2015 of file cm.c.

Referenced by cm_find_best_solution().

## ◆ estimate_fitness()

static double estimate_fitness | ( | const struct cm_state * | state,
|  | const int | production[]
| ) |  |

static

Estimate the fitness of a tile. Tiles are put into the lattice in fitness order, so that we start off choosing better tiles. The estimate MUST be monotone in the inputs; if it isn't, then the BB algorithm will fail.

The only fields of the state used are the city and parameter.

Definition at line 1766 of file cm.c.

Referenced by sort_lattice_by_fitness().

## ◆ evaluate_solution()

static struct cm_fitness evaluate_solution | ( | struct cm_state * | state,
|  | const struct partial_solution * | soln
| ) |  |

static

Compute the fitness of the solution. This is a fairly expensive operation.

Definition at line 784 of file cm.c.

Referenced by bb_next().

## ◆ fitness_better()

static bool fitness_better | ( | struct cm_fitness | a,
|  | struct cm_fitness | b
| ) |  |

static

Return TRUE iff fitness A is strictly better than fitness B.

Definition at line 587 of file cm.c.

Referenced by bb_next().

## ◆ get_city_surplus()

static void get_city_surplus | ( | const struct city * | pcity,
|  | int | surplus[],
|  | bool * | disorder,
|  | bool * | happy
| ) |  |

static

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.

Definition at line 769 of file cm.c.

Referenced by cm_result_copy(), and evaluate_solution().

## ◆ get_tax_rates()

static void get_tax_rates | ( | const struct player * | pplayer,
|  | int | rates[]
| ) |  |

static

Get the tax rates, see city.c

Definition at line 1736 of file cm.c.

Referenced by cm_state_init(), and estimate_fitness().

## ◆ init_min_production()

static void init_min_production | ( | struct cm_state * | state | ) |

static

Initialize minimal production needed to be sufficient

Definition at line 1721 of file cm.c.

Referenced by begin_search().

## ◆ init_partial_solution()

static void init_partial_solution | ( | struct partial_solution * | into,
|  | int | ntypes,
|  | int | idle,
|  | bool | negative_ok
| ) |  |

static

Allocate and initialize an empty solution.

Definition at line 651 of file cm.c.

Referenced by begin_search(), cm_state_init(), and compute_max_stats_heuristic().

## ◆ init_specialist_lattice_nodes()

static void init_specialist_lattice_nodes | ( | struct tile_type_vector * | lattice,
|  | const struct city * | pcity
| ) |  |

static

Create lattice nodes for each type of specialist. This adds a new tile_type for each specialist type.

Definition at line 1028 of file cm.c.

Referenced by init_tile_lattice().

## ◆ init_tile_lattice()

static void init_tile_lattice | ( | struct city * | pcity,
|  | struct tile_type_vector * | lattice
| ) |  |

static

Create the lattice.

Definition at line 1237 of file cm.c.

Referenced by cm_state_init().

## ◆ last_choice()

static int last_choice | ( | struct cm_state * | state | ) |

static

Return the last choice in the stack.

Definition at line 1287 of file cm.c.

Referenced by pop_choice(), take_child_choice(), and take_sibling_choice().

## ◆ min_food_surplus_for_fastest_growth()

static int min_food_surplus_for_fastest_growth | ( | struct cm_state * | state | ) |

static

Find the minimum food surplus needed to grow in the fewest number of turns.

Definition at line 1930 of file cm.c.

Referenced by begin_search().

## ◆ next_choice()

static int next_choice | ( | struct cm_state * | state,
|  | int | oldchoice,
|  | bool | negative_ok
| ) |  |

static

Return the next choice to make after oldchoice. A choice can be made if:

- we haven't used all the tiles
- we've used up all the better tiles
- using that choice, we have a hope of doing better than the best solution so far. If oldchoice == -1 then we return the first possible choice.

Definition at line 1408 of file cm.c.

Referenced by take_child_choice(), and take_sibling_choice().

## ◆ num_types()

static int num_types | ( | const struct cm_state * | state | ) |

static

Return the number of different tile types. There is one tile type for each type specialist, plus one for each distinct (different amounts of production) citymap tile.

Definition at line 1299 of file cm.c.

Referenced by apply_solution(), begin_search(), complete_solution(), compute_max_stats_heuristic(), copy_partial_solution(), next_choice(), specialists_in_solution(), take_child_choice(), and take_sibling_choice().

## ◆ pop_choice()

static void pop_choice | ( | struct cm_state * | state | ) |

static

Remove a worker from the current solution, and pop once off the choice stack.

Definition at line 1380 of file cm.c.

Referenced by bb_next().

## ◆ prereqs_filled()

static bool prereqs_filled | ( | const struct partial_solution * | soln,
|  | int | type,
|  | const struct cm_state * | state
| ) |  |

static

True if all tiles better than this type have been used.

Definition at line 1390 of file cm.c.

Referenced by complete_solution(), and next_choice().

## ◆ remove_worker()

static void remove_worker | ( | struct partial_solution * | soln,
|  | int | itype,
|  | const struct cm_state * | state
| ) |  |

static

Remove just one worker from the solution.

Definition at line 1370 of file cm.c.

Referenced by pop_choice(), and take_sibling_choice().

## ◆ sort_lattice_by_fitness()

static void sort_lattice_by_fitness | ( | const struct cm_state * | state,
|  | struct tile_type_vector * | lattice
| ) |  |

static

Determine the estimated_fitness fields, and sort by that. estimate_fitness is later, in a section of code that isolates much of the domain-specific knowledge.

Definition at line 1211 of file cm.c.

Referenced by begin_search().

## ◆ specialists_in_solution()

static int specialists_in_solution | ( | const struct cm_state * | state,
|  | const struct partial_solution * | soln
| ) |  |

static

Return number of specialists used in partial solution

Definition at line 1560 of file cm.c.

Referenced by choice_is_promising().

## ◆ take_child_choice()

static bool take_child_choice | ( | struct cm_state * | state,
|  | bool | negative_ok
| ) |  |

static

Go down from the current branch, if we can. Thanks to the fact that the lattice is sorted by depth, we can keep the choice stack sorted – that is, we can start our next choice as last_choice - 1. This keeps us from trying out all permutations of the same combination.

Definition at line 1474 of file cm.c.

Referenced by bb_next().

## ◆ take_sibling_choice()

static bool take_sibling_choice | ( | struct cm_state * | state,
|  | bool | negative_ok
| ) |  |

static

Pick a sibling choice to the last choice. This works down the branch to see if a choice that actually looks worse may actually be better.

Definition at line 1446 of file cm.c.

Referenced by bb_next().

## ◆ tile_get()

static const struct cm_tile * tile_get | ( | const struct cm_tile_type * | ptype,
|  | int | j
| ) |  |

static

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 types. See also tile_type_num_tiles().

Definition at line 570 of file cm.c.

Referenced by apply_solution().

## ◆ tile_type_better()

static int tile_type_better | ( | const struct cm_tile_type * | a,
|  | const struct cm_tile_type * | b
| ) |  |

static

Return positive value if tile a is better or equal to tile b in all categories, negative value if tile b is better to tile a in all categories, otherwise zero.

Specialists are considered better than workers (all else being equal) since we have an unlimited number of them.

Definition at line 465 of file cm.c.

Referenced by tile_type_lattice_add().

## ◆ tile_type_destroy()

static void tile_type_destroy | ( | struct cm_tile_type * | type | ) |

static

Free all the storage in the tile type (but don't free the type itself).

Definition at line 412 of file cm.c.

Referenced by tile_type_vector_free_all().

## ◆ tile_type_dup()

static struct cm_tile_type * tile_type_dup | ( | const struct cm_tile_type * | oldtype | ) |

static

Duplicate a tile type, except for the vectors - the vectors of the new tile type will be empty.

Definition at line 397 of file cm.c.

Referenced by tile_type_lattice_add().

## ◆ tile_type_equal()

static bool tile_type_equal | ( | const struct cm_tile_type * | a,
|  | const struct cm_tile_type * | b
| ) |  |

static

Return TRUE iff all categories of the two types are equal. This means all production outputs are equal and the is_specialist fields are also equal.

Definition at line 441 of file cm.c.

Referenced by tile_type_vector_find_equivalent().

## ◆ tile_type_get()

static const struct cm_tile_type * tile_type_get | ( | const struct cm_state * | state,
|  | int | type
| ) |  |

static

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.

Definition at line 554 of file cm.c.

Referenced by add_workers(), apply_solution(), compute_max_stats_heuristic(), next_choice(), prereqs_filled(), and specialists_in_solution().

## ◆ tile_type_init()

static void tile_type_init | ( | struct cm_tile_type * | type | ) |

static

Set all production to zero and initialize the vectors for this tile type.

Definition at line 385 of file cm.c.

Referenced by init_specialist_lattice_nodes(), and init_tile_lattice().

## ◆ tile_type_lattice_add()

static void tile_type_lattice_add | ( | struct tile_type_vector * | lattice,
|  | const struct cm_tile_type * | newtype,
|  | int | tindex
| ) |  |

static

Add the tile [x,y], with production indicated by type, to the tile-type lattice. 'newtype' can be on the stack. x/y are ignored if the type is a specialist. If the type is new, it is linked in and the lattice_index set. The lattice_depth is not set.

Definition at line 976 of file cm.c.

Referenced by init_specialist_lattice_nodes(), and init_tile_lattice().

## ◆ tile_type_num_prereqs()

static int tile_type_num_prereqs | ( | const struct cm_tile_type * | ptype | ) |

static

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 may be more than one tile of each type (see tile_type_num_tiles).

Definition at line 544 of file cm.c.

Referenced by add_workers(), prereqs_filled(), and top_sort_lattice().

## ◆ tile_type_num_tiles()

static int tile_type_num_tiles | ( | const struct cm_tile_type * | type | ) |

static

Return the number of tiles of this type that can be worked. For is_specialist types this will always be infinite but for other types of tiles it is limited by what's available in the citymap.

Definition at line 529 of file cm.c.

Referenced by add_workers(), complete_solution(), and top_sort_lattice().

## ◆ tile_type_vector_find_equivalent()

static int tile_type_vector_find_equivalent | ( | const struct tile_type_vector * | vec,
|  | const struct cm_tile_type * | ptype
| ) |  |

static

If there is a tile type in the vector that is equivalent to the given type, return its index. If not, return -1.

Equivalence is defined in tile_type_equal().

Definition at line 509 of file cm.c.

Referenced by tile_type_lattice_add().

## ◆ tile_type_vector_free_all()

static void tile_type_vector_free_all | ( | struct tile_type_vector * | vec | ) |

static

Destroy and free all types in the vector, and the vector itself. This will free all memory associated with the vector.

Definition at line 425 of file cm.c.

Referenced by clean_lattice(), and cm_state_free().

## ◆ top_sort_lattice()

static void top_sort_lattice | ( | struct tile_type_vector * | lattice | ) |

static

Topologically sort the lattice. Sets the lattice_depth field. Important assumption in this code: we've computed the transitive closure of the lattice. That is, better_types includes all types that are better.

Definition at line 1057 of file cm.c.

Referenced by init_tile_lattice().

## ◆ worst_fitness()

static struct cm_fitness worst_fitness | ( | void |  | ) |

static

Return a fitness struct that is the worst possible result we can represent.

Definition at line 599 of file cm.c.

Referenced by begin_search(), and cm_state_init().

## Variable Documentation

## ◆ compare_key

Output_type_id compare_key

static

Definition at line 911 of file cm.c.

Referenced by cm_state_init(), and compare_tile_type_by_stat().

## ◆ compare_key_trade_bonus

double compare_key_trade_bonus

static

Definition at line 912 of file cm.c.

Referenced by cm_state_init(), and compare_tile_type_by_stat().