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; \
      {

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 1363 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 1312 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 1823 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 1984 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 1659 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 1281 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 1158 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 2141 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 2174 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 2050 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 2201 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 2183 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 2431 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 2469 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 2122 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 2252 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 2272 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 2261 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 2238 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 2218 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 2033 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 1860 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 890 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 860 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 922 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 1510 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 1587 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 960 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 825 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 2017 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 1768 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 786 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 771 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 1738 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 1723 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 1030 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 1239 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 1289 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 1932 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 1410 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 1301 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 1382 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 1392 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 1372 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 1213 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 1562 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 1476 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 1448 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 978 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 1059 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 913 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 914 of file cm.c.

Referenced by cm_state_init(), and compare_tile_type_by_stat().