Freeciv-3.2
Loading...
Searching...
No Matches
cm.c
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 2002 - The Freeciv Project
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12***********************************************************************/
13
14#ifdef HAVE_CONFIG_H
15#include <fc_config.h>
16#endif
17
18#include <stdlib.h>
19#include <string.h>
20
21/* utility */
22#include "fcintl.h"
23#include "log.h"
24#include "mem.h"
25#include "shared.h"
26#include "support.h"
27#include "timing.h"
28
29/* common */
30#include "city.h"
31#include "game.h"
32#include "government.h"
33#include "map.h"
34#include "specialist.h"
35
36#include "cm.h"
37
38/*
39 * Terms used
40 * ==========
41 *
42 * Stats: food, shields, trade, luxury, science, and gold.
43 * Production: amount of stats you get directly from farming tiles or
44 * having specialists.
45 * Surplus: amount of stats you get, taking buildings, taxes, disorder, and
46 * any other effects into account.
47 *
48 * Happy State: disorder (unhappy), content (!unhappy && !happy) and
49 * happy (happy)
50 *
51 * Tile type: usually, many tiles produce the same f/s/t. So we bin the
52 * tiles into tile types. Specialists are also a 'tile type.'
53 *
54 * Unlike the original CM code, which used a dynamic programming approach,
55 * this code uses a branch-and-bound approach. The DP approach allowed
56 * caching, but it was hard to guarantee the correctness of the cache, so
57 * it was usually tossed and recomputed.
58 *
59 * The B&B approach also allows a very simple greedy search, whereas the DP
60 * approach required a lot of pre-computing. And, it appears to be very
61 * slightly faster. It evaluates about half as many solutions, but each
62 * candidate solution is more expensive due to the lack of caching.
63 *
64 * We use highly specific knowledge about how the city computes its stats
65 * in two places:
66 * - setting the min_production array. Ideally the city should tell us.
67 * - computing the weighting for tiles. Ditto.
68 */
69
70
71/*****************************************************************************
72 Defines, structs, globals, forward declarations
73*****************************************************************************/
74
75/* If this is uncommented, research loop runs without limit on iterations. */
76/* #define CM_LOOP_NO_LIMIT */
77
78/* Maximal iterations before the search loop is stopped, or until warning is
79 * printed if CM_LOOP_NO_LIMIT is defined. */
80#define CM_MAX_LOOP 27500
81
82#define CPUHOG_CM_MAX_LOOP (CM_MAX_LOOP * 4)
83
84#ifdef DEBUG_TIMERS
85#define GATHER_TIME_STATS
86#endif
87#ifdef FREECIV_DEBUG
88#define CM_DEBUG
89#endif
90
91/* Whether to print every query, or just at cm_free ; matters only
92 if GATHER_TIME_STATS is on */
93#define PRINT_TIME_STATS_EVERY_QUERY
94
95#define LOG_TIME_STATS LOG_DEBUG
96#define LOG_CM_STATE LOG_DEBUG
97#define LOG_LATTICE LOG_DEBUG
98#define LOG_REACHED_LEAF LOG_DEBUG
99#define LOG_BETTER_LEAF LOG_DEBUG
100#define LOG_PRUNE_BRANCH LOG_DEBUG
101
102#ifdef GATHER_TIME_STATS
103static struct {
104 struct one_perf {
105 struct timer *wall_timer;
106 int query_count;
107 int apply_count;
108 const char *name;
109 } greedy, opt;
110
111 struct one_perf *current;
113
114static void print_performance(struct one_perf *counts);
115#endif /* GATHER_TIME_STATS */
116
117/* Fitness of a solution. */
119 int weighted; /* weighted sum */
120 bool sufficient; /* false => doesn't meet constraints */
121};
122
123
124/*
125 * We have a cyclic structure here, so we need to forward-declare the
126 * structs
127 */
128struct cm_tile_type;
129struct cm_tile;
130
131/*
132 * A tile. Has a pointer to the type, and the x/y coords.
133 * Used mostly just for converting to cm_result.
134 */
135struct cm_tile {
136 const struct cm_tile_type *type;
137 int index; /* city map index; only valid if !is_specialist */
138};
139
140/* define the tile_vector as array<cm_tile> */
141#define SPECVEC_TAG tile
142#define SPECVEC_TYPE struct cm_tile
143#include "specvec.h"
144
145/* define the tile_type_vector as array <cm_tile_type*> */
146#define SPECVEC_TAG tile_type
147#define SPECVEC_TYPE struct cm_tile_type *
148#include "specvec.h"
149#define tile_type_vector_iterate(vector, var) { \
150 struct cm_tile_type *var; \
151 TYPED_VECTOR_ITERATE(struct cm_tile_type*, vector, var##p) { \
152 var = *var##p; \
153 {
154#define tile_type_vector_iterate_end }} VECTOR_ITERATE_END; }
155
156/*
157 * A tile type.
158 * Holds the production (a hill produces 1/0/0);
159 * Holds a list of which tiles match this (all the hills and tundra);
160 * Holds a list of other types that are strictly better
161 * (grassland 2/0/0, plains 1/1/0, but not gold mine 0/1/6).
162 * Holds a list of other types that are strictly worse
163 * (the grassland and plains hold a pointer to the hill).
164 *
165 * Specialists are special types; is_specialist is set, and the tile
166 * vector is empty. We can never run out of specialists.
167 */
170 double estimated_fitness; /* weighted sum of production */
172 Specialist_type_id spec; /* valid only if is_specialist */
173 struct tile_vector tiles; /* valid only if !is_specialist */
176 int lattice_index; /* index in state->lattice */
177 int lattice_depth; /* depth = sum(#tiles) over all better types */
178};
179
180
181/*
182 * A partial solution.
183 * Has the count of workers assigned to each lattice position, and
184 * a count of idle workers yet unassigned.
185 */
187 /* indices for these two match the lattice indices */
188 int *worker_counts; /* number of workers on each type */
189 int *prereqs_filled; /* number of better types filled up */
190
191 int production[O_LAST]; /* raw production, cached for the heuristic */
192 int idle; /* number of idle workers */
193};
194
195/*
196 * State of the search.
197 * This holds all the information needed to do the search, all in one
198 * struct, in order to clean up the function calls.
199 */
200struct cm_state {
201 /* input from the caller */
203 /*mutable*/ struct city *pcity;
204
205 /* the tile lattice */
208
209 /* the best known solution, and its fitness */
212
213 /* hard constraints on production: any solution with less production than
214 * this fails to satisfy the constraints, so we can stop investigating
215 * this branch. A solution with more production than this may still
216 * fail (for being unhappy, for instance). */
218
219 /* needed luxury to be content, this includes effects by specialists */
221
222 /* the current solution we're examining. */
224
225 /*
226 * Where we are in the search. When we add a worker to the current
227 * partial solution, we also push the tile type index on the stack.
228 */
229 struct {
230 int *stack;
231 int size;
233
234 bool *workers_map; /* placement of the workers within the city map */
235};
236
237
238/* return #fields + specialist types */
239static int num_types(const struct cm_state *state);
240
241
242/* debugging functions */
243#ifdef CM_DEBUG
244static void real_print_tile_type(enum log_level level, const char *file,
245 const char *function, int line,
246 const struct cm_tile_type *ptype,
247 const char *prefix);
248#define print_tile_type(loglevel, ptype, prefix) \
249 if (log_do_output_for_level(loglevel)) { \
250 real_print_tile_type(loglevel, __FILE__, __FUNCTION__, __FC_LINE__, \
251 ptype, prefix); \
252 }
253
254static void real_print_lattice(enum log_level level, const char *file,
255 const char *function, int line,
256 const struct tile_type_vector *lattice);
257#define print_lattice(loglevel, lattice) \
258 if (log_do_output_for_level(loglevel)) { \
259 real_print_lattice(loglevel, __FILE__, __FUNCTION__, __FC_LINE__, \
260 lattice); \
261 }
262
264 const char *file,
265 const char *function, int line,
266 const struct partial_solution *soln,
267 const struct cm_state *state);
268#define print_partial_solution(loglevel, soln, state) \
269 if (log_do_output_for_level(loglevel)) { \
270 real_print_partial_solution(loglevel, __FILE__, __FUNCTION__, \
271 __FC_LINE__, soln, state); \
272 }
273
274#else
275#define print_tile_type(loglevel, ptype, prefix)
276#define print_lattice(loglevel, lattice)
277#define print_partial_solution(loglevel, soln, state)
278#endif /* CM_DEBUG */
279
280static void cm_result_copy(struct cm_result *result,
281 const struct city *pcity, bool *workers_map);
282
283static double estimate_fitness(const struct cm_state *state,
284 const int production[]);
285static bool choice_is_promising(struct cm_state *state, int newchoice,
286 bool negative_ok);
287
288/************************************************************************/
293void cm_init(void)
294{
295 /* In the B&B algorithm there's not really anything to initialize. */
296#ifdef GATHER_TIME_STATS
297 memset(&performance, 0, sizeof(performance));
298
299 performance.greedy.wall_timer = timer_new(TIMER_USER, TIMER_ACTIVE,
300 "cm.greedy");
301 performance.greedy.name = "greedy";
302
304 "cm.opt");
305 performance.opt.name = "opt";
306#endif /* GATHER_TIME_STATS */
307}
308
309/************************************************************************/
315{
316 /* In the B&B algorithm there's not really anything to initialize. */
317}
318
319/************************************************************************/
322void cm_clear_cache(struct city *pcity)
323{
324 /* The B&B algorithm doesn't have city caches so there's nothing to do. */
325}
326
327/************************************************************************/
330void cm_free(void)
331{
332#ifdef GATHER_TIME_STATS
335
336 timer_destroy(performance.greedy.wall_timer);
337 timer_destroy(performance.opt.wall_timer);
338 memset(&performance, 0, sizeof(performance));
339#endif /* GATHER_TIME_STATS */
340}
341
342/************************************************************************/
345struct cm_result *cm_result_new(struct city *pcity)
346{
347 struct cm_result *result;
348
349 /* initialise all values */
350 result = fc_calloc(1, sizeof(*result));
351 result->city_radius_sq = pcity ? city_map_radius_sq_get(pcity)
353 result->worker_positions
355 sizeof(*result->worker_positions));
356
357 /* test if the city pointer is valid; the cm_result struct can be
358 * returned as it uses the maximal possible value for the size of
359 * 'worker_positions' (= city_map_tiles(CITY_MAP_MAX_RADIUS_SQ))*/
360 fc_assert_ret_val(pcity != NULL, result);
361
362 return result;
363}
364
365/************************************************************************/
368void cm_result_destroy(struct cm_result *result)
369{
370 if (result != NULL) {
371 if (result->worker_positions != NULL) {
372 FC_FREE(result->worker_positions);
373 }
374 FC_FREE(result);
375 }
376}
377
378/****************************************************************************
379 Functions of tile-types.
380****************************************************************************/
381
382/************************************************************************/
385static void tile_type_init(struct cm_tile_type *type)
386{
387 memset(type, 0, sizeof(*type));
388 tile_vector_init(&type->tiles);
389 tile_type_vector_init(&type->better_types);
390 tile_type_vector_init(&type->worse_types);
391}
392
393/************************************************************************/
397static struct cm_tile_type *tile_type_dup(const struct cm_tile_type *oldtype)
398{
399 struct cm_tile_type *newtype = fc_malloc(sizeof(*newtype));
400
401 memcpy(newtype, oldtype, sizeof(*oldtype));
402 tile_vector_init(&newtype->tiles);
403 tile_type_vector_init(&newtype->better_types);
404 tile_type_vector_init(&newtype->worse_types);
405
406 return newtype;
407}
408
409/************************************************************************/
413{
414 /* The call to vector_free() will magically free all the tiles in the
415 * vector. */
416 tile_vector_free(&type->tiles);
417 tile_type_vector_free(&type->better_types);
418 tile_type_vector_free(&type->worse_types);
419}
420
421/************************************************************************/
426{
428 /* Destroy all data in the type, and free the type itself. */
430 free(type);
432
434}
435
436/************************************************************************/
441static bool tile_type_equal(const struct cm_tile_type *a,
442 const struct cm_tile_type *b)
443{
446 return FALSE;
447 }
449
450 if (a->is_specialist != b->is_specialist) {
451 return FALSE;
452 }
453
454 return TRUE;
455}
456
457/************************************************************************/
465static int tile_type_better(const struct cm_tile_type *a,
466 const struct cm_tile_type *b)
467{
468 int ret = 0;
469
472 if (ret > 0) {
473 return 0;
474 }
475 ret = -1;
476 } else if (b->production[stat_index] < a->production[stat_index]) {
477 if (ret < 0) {
478 return 0;
479 }
480 ret = 1;
481 }
483
484 if (a->is_specialist && !b->is_specialist) {
485 /* If A is a specialist and B isn't, and all of A's production is at
486 * least as good as B's, then A is better because it doesn't tie up
487 * the map tile. */
488 if (ret < 0) {
489 return 0;
490 }
491 return 1;
492 } else if (!a->is_specialist && b->is_specialist) {
493 /* Vice versa. */
494 if (ret > 0) {
495 return 0;
496 }
497 return -1;
498 }
499
500 return ret;
501}
502
503/************************************************************************/
510 const struct tile_type_vector *vec,
511 const struct cm_tile_type *ptype)
512{
513 int i;
514
515 for (i = 0; i < vec->size; i++) {
516 if (tile_type_equal(vec->p[i], ptype)) {
517 return i;
518 }
519 }
520
521 return -1;
522}
523
524/************************************************************************/
529static int tile_type_num_tiles(const struct cm_tile_type *type)
530{
531 if (type->is_specialist) {
532 return FC_INFINITY;
533 } else {
534 return tile_vector_size(&type->tiles);
535 }
536}
537
538/************************************************************************/
544static int tile_type_num_prereqs(const struct cm_tile_type *ptype)
545{
546 return ptype->better_types.size;
547}
548
549/************************************************************************/
554static const struct cm_tile_type *tile_type_get(const struct cm_state *state,
555 int type)
556{
557 /* Sanity check the index. */
559 fc_assert_ret_val(state->lattice.size > type, NULL);
560
561 return state->lattice.p[type];
562}
563
564/************************************************************************/
570static const struct cm_tile *tile_get(const struct cm_tile_type *ptype, int j)
571{
572 fc_assert_ret_val(!ptype->is_specialist, NULL);
573 fc_assert_ret_val(0 <= j, NULL);
575
576 return &ptype->tiles.p[j];
577}
578
579
580/****************************************************************************
581 Functions on the cm_fitness struct.
582****************************************************************************/
583
584/************************************************************************/
587static bool fitness_better(struct cm_fitness a, struct cm_fitness b)
588{
589 if (a.sufficient != b.sufficient) {
590 return a.sufficient;
591 }
592 return a.weighted > b.weighted;
593}
594
595/************************************************************************/
600{
601 struct cm_fitness f;
602
604 f.weighted = -FC_INFINITY;
605 return f;
606}
607
608/************************************************************************/
612static struct cm_fitness compute_fitness(const int surplus[],
613 bool disorder, bool happy,
614 const struct cm_parameter *parameter)
615{
616 struct cm_fitness fitness;
617
619 fitness.weighted = 0;
620
622 fitness.weighted += surplus[stat_index] * parameter->factor[stat_index];
623 if (surplus[stat_index] < parameter->minimal_surplus[stat_index]) {
624 fitness.sufficient = FALSE;
625 }
627
628 if (happy) {
629 fitness.weighted += parameter->happy_factor;
630 } else if (parameter->require_happy) {
631 fitness.sufficient = FALSE;
632 }
633
634 if (disorder && !parameter->allow_disorder) {
635 fitness.sufficient = FALSE;
636 }
637
638 return fitness;
639}
640
641/****************************************************************************
642 Handle struct partial_solution.
643 - perform a deep copy
644 - convert to city
645 - convert to cm_result
646****************************************************************************/
647
648/************************************************************************/
652 int ntypes, int idle, bool negative_ok)
653{
654 into->worker_counts = fc_calloc(ntypes, sizeof(*into->worker_counts));
655 into->prereqs_filled = fc_calloc(ntypes, sizeof(*into->prereqs_filled));
656 if (negative_ok) {
658 into->production[otype] = -FC_INFINITY;
660 } else {
661 memset(into->production, 0, sizeof(into->production));
662 }
663 into->idle = idle;
664}
665
666/************************************************************************/
671{
672 free(into->worker_counts);
673 free(into->prereqs_filled);
674}
675
676/************************************************************************/
681 const struct partial_solution *src,
682 const struct cm_state *state)
683{
685 sizeof(*dst->worker_counts) * num_types(state));
687 sizeof(*dst->prereqs_filled) * num_types(state));
688 memcpy(dst->production, src->production, sizeof(dst->production));
689 dst->idle = src->idle;
690}
691
692
693/****************************************************************************
694 Evaluating a completed solution.
695****************************************************************************/
696
697/************************************************************************/
700static void apply_solution(struct cm_state *state,
701 const struct partial_solution *soln)
702{
703 struct city *pcity = state->pcity;
705 const struct civ_map *nmap = &(wld.map);
706#ifndef FREECIV_NDEBUG
707 int citizen_count = 0;
708#endif
709
710#ifdef GATHER_TIME_STATS
711 performance.current->apply_count++;
712#endif
713
714 fc_assert_ret(0 == soln->idle);
715
716 /* Clear all specialists, and remove all workers from fields (except
717 * the city center). */
718 memset(&pcity->specialists, 0, sizeof(pcity->specialists));
719
720 city_map_iterate(city_radius_sq, cindex, x, y) {
721 if (is_free_worked_index(cindex)) {
722 state->workers_map[cindex] = TRUE;
723 } else {
724 state->workers_map[cindex] = FALSE;
725 }
727
728 /* Now for each tile type, find the right number of such tiles and set them
729 * as worked. For specialists we just increase the number of specialists
730 * of that type. */
731 for (i = 0 ; i < num_types(state); i++) {
732 int nworkers = soln->worker_counts[i];
733 const struct cm_tile_type *type;
734
735 if (nworkers == 0) {
736 /* No citizens of this type. */
737 continue;
738 }
739#ifndef FREECIV_NDEBUG
741#endif
742
743 type = tile_type_get(state, i);
744
745 if (type->is_specialist) {
746 /* Just increase the number of specialists. */
747 pcity->specialists[type->spec] += nworkers;
748 } else {
749 int j;
750
751 /* Place citizen workers onto the citymap tiles. */
752 for (j = 0; j < nworkers; j++) {
753 const struct cm_tile *cmtile = tile_get(type, j);
754
755 state->workers_map[cmtile->index] = TRUE;
756 }
757 }
758 }
759
760 /* Finally we must refresh the city to reset all the precomputed fields. */
762
764}
765
766/************************************************************************/
771static void get_city_surplus(const struct city *pcity,
772 int surplus[],
773 bool *disorder, bool *happy)
774{
776 surplus[o] = pcity->surplus[o];
778
779 *disorder = city_unhappy(pcity);
780 *happy = city_happy(pcity);
781}
782
783/************************************************************************/
787 const struct partial_solution *soln)
788{
789 struct city *pcity = state->pcity;
790 int surplus[O_LAST];
791 bool disorder, happy;
792
793 /* apply and evaluate the solution, backup is done in find_best_solution */
794 apply_solution(state, soln);
795 get_city_surplus(pcity, surplus, &disorder, &happy);
796
797 /* if this solution is not content, we have an estimate on min. luxuries */
798 if (disorder) {
799 /* We have to consider the influence of each specialist in this
800 solution possibly 'hiding' a potential unhappy citizen who
801 could require luxuries.
802 Since we know the city is in disorder, we can discount most
803 effects that make citizens content, since they clearly weren't
804 sufficient.
805 This may not be sufficient luxury to make the city content (due
806 to military unhappiness etc), but certainly no less will do.
807 (Specialists may also be making angry citizens content, requiring
808 additional luxuries, but we don't try to consider that here; this
809 just means we might explore some solutions unnecessarily.) */
812
813 state->min_luxury = surplus[O_LUXURY]
815 + 1;
816 }
817
818 return compute_fitness(surplus, disorder, happy, &state->parameter);
819}
820
821/************************************************************************/
825static void convert_solution_to_result(struct cm_state *state,
826 const struct partial_solution *soln,
827 struct cm_result *result)
828{
829 struct cm_fitness fitness;
830
831 if (soln->idle != 0) {
832 /* If there are unplaced citizens it's not a real solution, so the
833 * result is invalid. */
834 result->found_a_valid = FALSE;
835 return;
836 }
837
838 /* apply and evaluate the solution, backup is done in find_best_solution */
839 apply_solution(state, soln);
840 cm_result_copy(result, state->pcity, state->workers_map);
841
842 /* result->found_a_valid should be only true if it matches the
843 * parameter; figure out if it does */
844 fitness = compute_fitness(result->surplus, result->disorder,
845 result->happy, &state->parameter);
846 result->found_a_valid = fitness.sufficient;
847}
848
849/****************************************************************************
850 Compare functions to allow sorting lattice vectors.
851****************************************************************************/
852
853/************************************************************************/
861 const struct cm_tile_type *b)
862{
863 if (a == b) {
864 return 0;
865 }
866
867 /* Least depth first */
868 if (a->lattice_depth != b->lattice_depth) {
869 return a->lattice_depth - b->lattice_depth;
870 }
871
872 /* With equal depth, break ties arbitrarily, more production first. */
876 }
878
879 /* If we get here, then we have two copies of identical types, an error */
881 return 0;
882}
883
884/************************************************************************/
890static int compare_tile_type_by_fitness(const void *va, const void *vb)
891{
892 struct cm_tile_type * const *a = va;
893 struct cm_tile_type * const *b = vb;
894 double diff;
895
896 if (*a == *b) {
897 return 0;
898 }
899
900 /* To avoid double->int roundoff problems, we call a result non-zero only
901 * if it's larger than 0.5. */
902 diff = (*b)->estimated_fitness - (*a)->estimated_fitness;
903 if (diff > 0.5) {
904 return 1; /* return value is int; don't round down! */
905 }
906 if (diff < -0.5) {
907 return -1;
908 }
909
911}
912
915
916/************************************************************************/
922static int compare_tile_type_by_stat(const void *va, const void *vb)
923{
924 struct cm_tile_type * const *a = va;
925 struct cm_tile_type * const *b = vb;
926
927 if (*a == *b) {
928 return 0;
929 }
930
931 /* Consider the influence of trade on science, luxury, gold
932 for compute_max_stats_heuristics, which uses these sorted arrays,
933 it is essential, that the sorting is correct, else promising
934 branches get pruned */
935 double valuea = (*a)->production[compare_key] +
936 compare_key_trade_bonus * (*a)->production[O_TRADE];
937 double valueb = (*b)->production[compare_key] +
938 compare_key_trade_bonus * (*b)->production[O_TRADE];
939
940 /* Most production of what we care about goes first */
941 /* Double compare is ok, both values are calculated in the same way
942 and should only be considered equal, if equal in compare_key
943 and O_TRADE */
944 if (valuea != valueb) {
945 /* b-a so we sort big numbers first */
946 return valueb - valuea;
947 }
948
950}
951
952/****************************************************************************
953 Compute the tile-type lattice.
954****************************************************************************/
955
956/************************************************************************/
960static void compute_tile_production(const struct city *pcity,
961 const struct tile *ptile,
962 struct cm_tile_type *out)
963{
965
967 out->production[o] = city_tile_output(pcity, ptile, is_celebrating, o);
969}
970
971/************************************************************************/
978static void tile_type_lattice_add(struct tile_type_vector *lattice,
979 const struct cm_tile_type *newtype,
980 int tindex)
981{
982 struct cm_tile_type *type;
983 int i;
984
986 if (i >= 0) {
987 /* We already have this type of tile; use it. */
988 type = lattice->p[i];
989 } else {
990 /* This is a new tile type; add it to the lattice. */
992
993 /* Link up to the types we dominate, and those that dominate us */
996
997 if (cmp > 0) {
998 tile_type_vector_append(&type->better_types, other);
999 tile_type_vector_append(&other->worse_types, type);
1000 } else if (cmp < 0) {
1001 tile_type_vector_append(&other->better_types, type);
1002 tile_type_vector_append(&type->worse_types, other);
1003 }
1005
1006 /* Insert into the list */
1007 type->lattice_index = lattice->size;
1008 tile_type_vector_append(lattice, type);
1009 }
1010
1011 /* Finally, add the tile to the tile type. */
1012 if (!type->is_specialist) {
1013 struct cm_tile tile;
1014
1015 tile.type = type;
1016 tile.index = tindex;
1017
1018 tile_vector_append(&type->tiles, tile);
1019 }
1020}
1021
1022/*
1023 * Add the specialist types to the lattice.
1024 */
1025
1026/************************************************************************/
1031 const struct city *pcity)
1032{
1033 struct cm_tile_type type;
1034
1036 type.is_specialist = TRUE;
1037
1038 /* for each specialist type, create a tile_type that has as production
1039 * the bonus for the specialist (if the city is allowed to use it) */
1041 if (city_can_use_specialist(pcity, i)) {
1042 type.spec = i;
1043 output_type_iterate(output) {
1044 type.production[output] = get_specialist_output(pcity, i, output);
1046
1047 tile_type_lattice_add(lattice, &type, 0);
1048 }
1050}
1051
1052/************************************************************************/
1059static void top_sort_lattice(struct tile_type_vector *lattice)
1060{
1061 if (lattice->size > 0) {
1062 int i;
1063 bool marked[lattice->size];
1064 bool will_mark[lattice->size];
1065 struct tile_type_vector vectors[2];
1066 struct tile_type_vector *current, *next;
1067
1068 memset(marked, 0, sizeof(marked));
1069 memset(will_mark, 0, sizeof(will_mark));
1070
1073 current = &vectors[0];
1074 next = &vectors[1];
1075
1076 /* Fill up 'next' */
1078 if (tile_type_num_prereqs(ptype) == 0) {
1080 }
1082
1083 /* While we have nodes to process: mark the nodes whose prereqs have
1084 * all been visited. Then, store all the new nodes on the frontier. */
1085 while (next->size != 0) {
1086 /* What was the next frontier is now the current frontier */
1087 struct tile_type_vector *vtmp = current;
1088
1089 current = next;
1090 next = vtmp;
1091 next->size = 0; /* Clear out the contents */
1092
1093 /* Look over the current frontier and process everyone */
1095 /* See if all prereqs were marked. If so, decide to mark this guy,
1096 and put all the descendents on 'next'. */
1097 bool can_mark = TRUE;
1098 int sumdepth = 0;
1099
1100 if (will_mark[ptype->lattice_index]) {
1101 continue; /* We've already been processed */
1102 }
1103 tile_type_vector_iterate(&ptype->better_types, better) {
1104 if (!marked[better->lattice_index]) {
1105 can_mark = FALSE;
1106 break;
1107 } else {
1108 sumdepth += tile_type_num_tiles(better);
1109 if (sumdepth >= FC_INFINITY) {
1110 /* If this is the case, then something better could
1111 always be used, and the same holds for our children */
1113 can_mark = TRUE;
1114 break;
1115 }
1116 }
1118 if (can_mark) {
1119 /* Mark and put successors on the next frontier */
1120 will_mark[ptype->lattice_index] = TRUE;
1121 tile_type_vector_iterate(&ptype->worse_types, worse) {
1124
1125 /* This is what we spent all this time computing. */
1126 ptype->lattice_depth = sumdepth;
1127 }
1129
1130 /* Now, actually mark everyone and get set for next loop */
1131 for (i = 0; i < lattice->size; i++) {
1132 marked[i] = marked[i] || will_mark[i];
1133 will_mark[i] = FALSE;
1134 }
1135 }
1136
1139 }
1140}
1141
1142/************************************************************************/
1158static void clean_lattice(struct tile_type_vector *lattice,
1159 const struct city *pcity)
1160{
1161 int i, j; /* i is the index we read, j is the index we write */
1162 struct tile_type_vector tofree;
1163 bool forced_loop = FALSE;
1164
1165 /* We collect the types we want to remove and free them in one fell
1166 swoop at the end, in order to avoid memory errors. */
1168
1169 /* forced_loop is workaround for what seems like gcc optimization
1170 * bug.
1171 * This applies to -O2 optimization on some distributions. */
1172 if (lattice->size > 0) {
1173 forced_loop = TRUE;
1174 }
1175 for (i = 0, j = 0; i < lattice->size || forced_loop; i++) {
1176 struct cm_tile_type *ptype = lattice->p[i];
1177 citizens csize = city_size_get(pcity);
1178
1180
1181 if (ptype->lattice_depth >= csize) {
1183 } else {
1184 /* Remove links to children that are being removed. */
1185
1186 int ci, cj; /* 'c' for 'child'; read from ci, write to cj */
1187
1188 lattice->p[j] = ptype;
1189 lattice->p[j]->lattice_index = j;
1190 j++;
1191
1192 for (ci = 0, cj = 0; ci < ptype->worse_types.size; ci++) {
1193 const struct cm_tile_type *ptype2 = ptype->worse_types.p[ci];
1194
1195 if (ptype2->lattice_depth < csize) {
1196 ptype->worse_types.p[cj] = ptype->worse_types.p[ci];
1197 cj++;
1198 }
1199 }
1200 ptype->worse_types.size = cj;
1201 }
1202 }
1203 lattice->size = j;
1204
1206}
1207
1208/************************************************************************/
1213static void sort_lattice_by_fitness(const struct cm_state *state,
1214 struct tile_type_vector *lattice)
1215{
1216 int i;
1217
1218 /* compute fitness */
1220 ptype->estimated_fitness = estimate_fitness(state, ptype->production);
1222
1223 /* sort by it */
1224 qsort(lattice->p, lattice->size, sizeof(*lattice->p),
1226
1227 /* fix the lattice indices */
1228 for (i = 0; i < lattice->size; i++) {
1229 lattice->p[i]->lattice_index = i;
1230 }
1231
1232 log_base(LOG_LATTICE, "sorted lattice:");
1233 print_lattice(LOG_LATTICE, lattice);
1234}
1235
1236/************************************************************************/
1239static void init_tile_lattice(struct city *pcity,
1240 struct tile_type_vector *lattice)
1241{
1242 struct cm_tile_type type;
1243 struct tile *pcenter = city_tile(pcity);
1244 const struct civ_map *nmap = &(wld.map);
1245
1246 /* Add all the fields into the lattice */
1247 tile_type_init(&type); /* Init just once */
1248
1250 ctindex) {
1251 if (is_free_worked(pcity, ptile)) {
1252 continue;
1253 } else if (city_can_work_tile(pcity, ptile)) {
1254 compute_tile_production(pcity, ptile, &type); /* Clobbers type */
1255 tile_type_lattice_add(lattice, &type, ctindex); /* Copy type if needed */
1256 }
1258
1259 /* Add all the specialists into the lattice. */
1260 init_specialist_lattice_nodes(lattice, pcity);
1261
1262 /* Set the lattice_depth fields, and clean up unreachable nodes. */
1263 top_sort_lattice(lattice);
1264 clean_lattice(lattice, pcity);
1265
1266 /* All done now. */
1267 print_lattice(LOG_LATTICE, lattice);
1268}
1269
1270
1271/****************************************************************************
1272
1273 Handling the choice stack for the bb algorithm.
1274
1275****************************************************************************/
1276
1277
1278/************************************************************************/
1281static bool choice_stack_empty(struct cm_state *state)
1282{
1283 return state->choice.size == 0;
1284}
1285
1286/************************************************************************/
1289static int last_choice(struct cm_state *state)
1290{
1292
1293 return state->choice.stack[state->choice.size - 1];
1294}
1295
1296/************************************************************************/
1301static int num_types(const struct cm_state *state)
1302{
1303 return tile_type_vector_size(&state->lattice);
1304}
1305
1306/************************************************************************/
1313 int itype, int number,
1314 const struct cm_state *state)
1315{
1316 const struct cm_tile_type *ptype = tile_type_get(state, itype);
1317 int newcount;
1318 int old_worker_count = soln->worker_counts[itype];
1319
1320 if (number == 0) {
1321 return;
1322 }
1323
1324 /* update the number of idle workers */
1325 newcount = soln->idle - number;
1326 fc_assert_ret(newcount >= 0);
1328 soln->idle = newcount;
1329
1330 /* update the worker counts */
1331 newcount = soln->worker_counts[itype] + number;
1332 fc_assert_ret(newcount >= 0);
1334 soln->worker_counts[itype] = newcount;
1335
1336 /* update prereqs array: if we are no longer full but we were,
1337 * we need to decrement the count, and vice-versa. */
1339 fc_assert_ret(number < 0);
1340 tile_type_vector_iterate(&ptype->worse_types, other) {
1341 soln->prereqs_filled[other->lattice_index]--;
1342 fc_assert_ret(soln->prereqs_filled[other->lattice_index] >= 0);
1344 } else if (soln->worker_counts[itype] == tile_type_num_tiles(ptype)) {
1345 fc_assert_ret(number > 0);
1346 tile_type_vector_iterate(&ptype->worse_types, other) {
1347 soln->prereqs_filled[other->lattice_index]++;
1348 fc_assert_ret(soln->prereqs_filled[other->lattice_index]
1351 }
1352
1353 /* update production */
1355 newcount = soln->production[stat_index] + number * ptype->production[stat_index];
1356 soln->production[stat_index] = newcount;
1358}
1359
1360/************************************************************************/
1364 int itype, const struct cm_state *state)
1365{
1366 add_workers(soln, itype, 1, state);
1367}
1368
1369/************************************************************************/
1373 int itype, const struct cm_state *state)
1374{
1375 add_workers(soln, itype, -1, state);
1376}
1377
1378/************************************************************************/
1382static void pop_choice(struct cm_state *state)
1383{
1385 remove_worker(&state->current, last_choice(state), state);
1386 state->choice.size--;
1387}
1388
1389/************************************************************************/
1392static bool prereqs_filled(const struct partial_solution *soln, int type,
1393 const struct cm_state *state)
1394{
1395 const struct cm_tile_type *ptype = tile_type_get(state, type);
1397
1398 return soln->prereqs_filled[type] == prereqs;
1399}
1400
1401/************************************************************************/
1410static int next_choice(struct cm_state *state, int oldchoice, bool negative_ok)
1411{
1412 int newchoice;
1413
1414 for (newchoice = oldchoice + 1;
1415 newchoice < num_types(state); newchoice++) {
1416 const struct cm_tile_type *ptype = tile_type_get(state, newchoice);
1417
1418 if (!ptype->is_specialist && (state->current.worker_counts[newchoice]
1419 == tile_vector_size(&ptype->tiles))) {
1420 /* we've already used all these tiles */
1421 continue;
1422 }
1423 if (!prereqs_filled(&state->current, newchoice, state)) {
1424 /* we could use a strictly better tile instead */
1425 continue;
1426 }
1428 /* heuristic says we can't beat the best going this way */
1429 log_base(LOG_PRUNE_BRANCH, "--- pruning branch ---");
1432 " + worker on ");
1433 log_base(LOG_PRUNE_BRANCH, "--- branch pruned ---");
1434 continue;
1435 }
1436 break;
1437 }
1438
1439 /* returns num_types if no next choice was available. */
1440 return newchoice;
1441}
1442
1443
1444/************************************************************************/
1448static bool take_sibling_choice(struct cm_state *state, bool negative_ok)
1449{
1450 int oldchoice = last_choice(state);
1451 int newchoice;
1452
1453 /* need to remove first, to run the heuristic */
1454 remove_worker(&state->current, oldchoice, state);
1456
1457 if (newchoice == num_types(state)) {
1458 /* add back in so the caller can then remove it again. */
1459 add_worker(&state->current, oldchoice, state);
1460 return FALSE;
1461 } else {
1462 add_worker(&state->current, newchoice, state);
1463 state->choice.stack[state->choice.size-1] = newchoice;
1464 /* choice.size is unchanged */
1465 return TRUE;
1466 }
1467}
1468
1469/************************************************************************/
1476static bool take_child_choice(struct cm_state *state, bool negative_ok)
1477{
1478 int oldchoice, newchoice;
1479
1480 if (state->current.idle == 0) {
1481 return FALSE;
1482 }
1483
1484 if (state->choice.size == 0) {
1485 oldchoice = 0;
1486 } else {
1487 oldchoice = last_choice(state);
1488 }
1489
1490 /* oldchoice-1 because we can use oldchoice again */
1492
1493 /* did we fail? */
1494 if (newchoice == num_types(state)) {
1495 return FALSE;
1496 }
1497
1498 /* now push the new choice on the choice stack */
1499 add_worker(&state->current, newchoice, state);
1500 state->choice.stack[state->choice.size] = newchoice;
1501 state->choice.size++;
1502
1503 return TRUE;
1504}
1505
1506/************************************************************************/
1511 const struct cm_state *state,
1512 const struct tile_type_vector *lattice)
1513{
1514 int last_worker_choice = -1;
1515 int i;
1516
1517 if (soln->idle == 0) {
1518 return;
1519 }
1520
1521 /* find the last worker type added (-1 if none) */
1522 for (i = 0; i < num_types(state); i++) {
1523 if (soln->worker_counts[i] != 0) {
1525 }
1526 }
1527
1528 /* While there are idle workers, pick up the next-best kind of tile,
1529 * and assign the workers to the tiles.
1530 * Respect lexicographic order and prerequisites. */
1532 int used = soln->worker_counts[ptype->lattice_index];
1533 int total = tile_type_num_tiles(ptype);
1534 int touse;
1535
1536 if (ptype->lattice_index < last_worker_choice) {
1537 /* lex-order: we can't use ptype (some other branch
1538 will check this combination, or already did) */
1539 continue;
1540 }
1541 if (!prereqs_filled(soln, ptype->lattice_index, state)) {
1542 /* don't bother using this tile before all better tiles are used */
1543 continue;
1544 }
1545
1546 touse = total - used;
1547 if (touse > soln->idle) {
1548 touse = soln->idle;
1549 }
1550 add_workers(soln, ptype->lattice_index, touse, state);
1551
1552 if (soln->idle == 0) {
1553 /* nothing left to do here */
1554 return;
1555 }
1557}
1558
1559/************************************************************************/
1562static int specialists_in_solution(const struct cm_state *state,
1563 const struct partial_solution *soln)
1564{
1565 int count = 0;
1566 int i;
1567
1568 for (i = 0 ; i < num_types(state); i++) {
1569 if (soln->worker_counts[i] > 0 && tile_type_get(state, i)->is_specialist) {
1570 count += soln->worker_counts[i];
1571 }
1572 }
1573
1574 return count;
1575}
1576
1577/************************************************************************/
1587static void compute_max_stats_heuristic(const struct cm_state *state,
1588 const struct partial_solution *soln,
1589 int production[],
1590 int check_choice, bool negative_ok)
1591{
1592 struct partial_solution solnplus; /* Will be soln, plus some tiles */
1593 const struct civ_map *nmap = &(wld.map);
1594
1595 /* Production is whatever the solution produces, plus the
1596 most possible of each kind of production the idle workers could
1597 produce */
1598
1599 if (soln->idle == 1) {
1600 /* Then the total solution is soln + this new worker. So we know the
1601 production exactly, and can shortcut the later code. */
1602 const struct cm_tile_type *ptype = tile_type_get(state, check_choice);
1603
1604 memcpy(production, soln->production, sizeof(soln->production));
1606 production[stat_index] += ptype->production[stat_index];
1608
1609 } else {
1610
1611 /* Initialize solnplus here, after the shortcut check */
1613 city_size_get(state->pcity),
1614 negative_ok);
1615
1617 /* compute the solution that has soln, then the check_choice,
1618 then complete it with the best available tiles for the stat. */
1622
1625
1627
1628 }
1629
1630 /* We found the basic production, however, bonus, taxes,
1631 * free production, tithes, trade routes are missing.
1632 * We add free production, and have the city.c code do the rest */
1633
1634 struct city *pcity = state->pcity;
1635 struct tile *pcenter = city_tile(pcity);
1637
1639 int base = production[stat_index];
1640
1642 if (is_free_worked(pcity, ptile)) {
1644 }
1646 pcity->citizen_base[stat_index] = base;
1648
1649 set_city_production(pcity);
1650 memcpy(production, pcity->prod, sizeof(pcity->prod));
1651}
1652
1653/************************************************************************/
1659static bool choice_is_promising(struct cm_state *state, int newchoice,
1660 bool negative_ok)
1661{
1662 int production[O_LAST];
1663 bool beats_best = FALSE;
1664
1665 /* this computes an upper bound (componentwise) for the current branch,
1666 if it is worse in every component than the best, or still insufficient,
1667 then we can prune the whole branch */
1668 compute_max_stats_heuristic(state, &state->current, production, newchoice,
1669 negative_ok);
1670
1672 if (production[stat_index] < state->min_production[stat_index]) {
1673 log_base(LOG_PRUNE_BRANCH, "--- pruning: insufficient %s (%d < %d)",
1675 state->min_production[stat_index]);
1676 return FALSE;
1677 }
1678 if (production[stat_index] > state->best.production[stat_index]
1679 && state->parameter.factor[stat_index] > 0 ) {
1680 beats_best = TRUE;
1681 /* may still fail to meet min at another production type, so
1682 * don't short-circuit */
1683 }
1685
1686 /* If we don't get the city content, we assume using every idle worker
1687 as specialist and the maximum producible luxury already computed.
1688 If this is less than the amount of luxury we calculated in
1689 evaluate_solution() (where min_luxury is set), when we observed the
1690 city in disorder, then this is clearly not worth pursuing.
1691 (Since we're comparing to evaluate_solution()'s calculation, we
1692 don't need to take effects, angry citizens etc into account here
1693 either.)
1694 FIXME: this heuristic will break in rulesets where specialists can
1695 influence happiness other than by direct production of luxury. */
1696 {
1701 int max_luxury = production[O_LUXURY]
1703
1704 if (max_luxury < state->min_luxury ) {
1705 log_base(LOG_PRUNE_BRANCH, "--- pruning: disorder (%d + %d*%d < %d)",
1706 production[O_LUXURY],
1709 state->min_luxury);
1710 return FALSE;
1711 }
1712 }
1713 if (!beats_best) {
1714 log_base(LOG_PRUNE_BRANCH, "--- pruning: best is better in all important ways");
1715 }
1716
1717 return beats_best;
1718}
1719
1720/************************************************************************/
1723static void init_min_production(struct cm_state *state)
1724{
1725 struct city *pcity = state->pcity;
1726
1728 state->min_production[o] = pcity->usage[o] + state->parameter.minimal_surplus[o];
1730
1731 /* We could get a minimum on luxury if we knew how many luxuries were
1732 * needed to make us content. */
1733}
1734
1735/************************************************************************/
1738static void get_tax_rates(const struct player *pplayer, int rates[])
1739{
1740 const int SCIENCE = 0, TAX = 1, LUXURY = 2;
1741
1742 if (game.info.changable_tax) {
1743 rates[SCIENCE] = pplayer->economic.science;
1744 rates[LUXURY] = pplayer->economic.luxury;
1745 rates[TAX] = 100 - rates[SCIENCE] - rates[LUXURY];
1746 } else {
1750 }
1751
1752 /* ANARCHY */
1754 rates[SCIENCE] = 0;
1755 rates[LUXURY] = 100;
1756 rates[TAX] = 0;
1757 }
1758}
1759
1760/************************************************************************/
1768static double estimate_fitness(const struct cm_state *state,
1769 const int production[])
1770{
1771 const int SCIENCE = 0, TAX = 1, LUXURY = 2;
1772 const struct city *pcity = state->pcity;
1773 const struct player *pplayer = city_owner(pcity);
1774 int rates[3];
1775 double estimates[O_LAST];
1776 double sum = 0;
1777 int trade;
1778
1780 estimates[stat_index] = production[stat_index];
1782
1783 /* bonus to trade is applied before calculating taxes, see city.c */
1784 trade = estimates[O_TRADE] * pcity->bonus[O_TRADE] / 100.0;
1785
1786 get_tax_rates(pplayer, rates);
1787
1788 /* sci/lux/gold get benefit from the tax rates (in percentage) */
1790 += rates[SCIENCE] * trade / 100.0;
1792 += rates[LUXURY] * trade / 100.0;
1794 += rates[TAX] * trade / 100.0;
1795
1796 /* now add in the bonuses from building effects (in percentage) */
1798 estimates[stat_index] *= pcity->bonus[stat_index] / 100.0;
1800
1801 /* finally, sum it all up, weighted by the parameter, but give additional
1802 * weight to luxuries to take account of disorder/happy constraints */
1806 sum += estimates[O_LUXURY];
1807
1808 return sum;
1809}
1810
1811/************************************************************************/
1823static bool bb_next(struct cm_state *state, bool negative_ok)
1824{
1825 /* if no idle workers, then look at our solution. */
1826 if (state->current.idle == 0) {
1827 struct cm_fitness value = evaluate_solution(state, &state->current);
1828
1830 if (fitness_better(value, state->best_value)) {
1831 log_base(LOG_BETTER_LEAF, "-> replaces previous best");
1832 copy_partial_solution(&state->best, &state->current, state);
1833 state->best_value = value;
1834 }
1835 }
1836
1837 /* try to move to a child branch, if we can. If not (including if we're
1838 at a leaf), then move to a sibling. */
1839 if (!take_child_choice(state, negative_ok)) {
1840 /* keep trying to move to a sibling branch, or popping out a level if
1841 we're stuck (fully examined the current branch) */
1842 while ((!choice_stack_empty(state))
1843 && !take_sibling_choice(state, negative_ok)) {
1844 pop_choice(state);
1845 }
1846
1847 /* if we popped out all the way, we're done */
1848 if (choice_stack_empty(state)) {
1849 return TRUE;
1850 }
1851 }
1852
1853 /* if we didn't detect that we were done, we aren't */
1854 return FALSE;
1855}
1856
1857/************************************************************************/
1860static struct cm_state *cm_state_init(struct city *pcity, bool negative_ok)
1861{
1862 const int SCIENCE = 0, TAX = 1, LUXURY = 2;
1863 const struct player *pplayer = city_owner(pcity);
1864 int numtypes;
1865 struct cm_state *state = fc_malloc(sizeof(*state));
1866 int rates[3];
1868
1869 log_base(LOG_CM_STATE, "creating cm_state for %s (size %d)",
1871
1872 /* copy the arguments */
1873 state->pcity = pcity;
1874
1875 /* create the lattice */
1879
1880 get_tax_rates(pplayer, rates);
1881
1882 /* For the heuristic, make sorted copies of the lattice */
1884 int lsize = tile_type_vector_size(&state->lattice);
1885
1886 if (lsize > 0) {
1890 /* Calculate effect of 1 trade production on interesting production */
1891 switch (stat_index) {
1892 case O_SCIENCE:
1894 break;
1895 case O_LUXURY:
1897 break;
1898 case O_GOLD:
1900 break;
1901 default:
1903 break;
1904 }
1906 sizeof(*state->lattice_by_prod[stat_index].p),
1908 }
1910
1911 state->min_luxury = - FC_INFINITY;
1912
1913 /* We have no best solution yet, so its value is the worst possible. */
1915 state->best_value = worst_fitness();
1916
1917 /* Initialize the current solution and choice stack to empty */
1919 state->choice.stack = fc_malloc(csize * sizeof(*state->choice.stack));
1920 state->choice.size = 0;
1921
1922 /* Initialize workers map */
1924 sizeof(state->workers_map));
1925
1926 return state;
1927}
1928
1929/************************************************************************/
1933{
1934 struct city *pcity = state->pcity;
1936 citizens city_size = city_size_get(pcity);
1937 int max_surplus = -game.info.food_cost * city_size;
1939 citizens workers = city_size;
1940 int food_needed = city_granary_size(city_size) - pcity->food_stock;
1941 int min_turns;
1942 const struct civ_map *nmap = &(wld.map);
1943
1944 city_map_iterate(city_radius_sq, cindex, x, y) {
1945 struct tile *ptile = city_map_to_tile(nmap, pcity->tile, city_radius_sq, x, y);
1946 if (!ptile) {
1947 continue;
1948 }
1949 if (is_free_worked_index(cindex)) {
1951 }
1953
1954 if (max_surplus <= 0) {
1955 return max_surplus;
1956 }
1957
1958 if (food_needed <= 0) {
1959 return 0;
1960 }
1961
1963 int num = tile_vector_size(&ptype->tiles);
1964
1965 if (ptype->is_specialist || workers < num) {
1966 max_surplus += workers * ptype->production[O_FOOD];
1967 break;
1968 }
1969 max_surplus += num * ptype->production[O_FOOD];
1970 workers -= num;
1972
1973 /* min_turns will always be positive because if food_needed or
1974 * max_surplus are non-positive, this function returns earlier. */
1976
1977 return (food_needed + min_turns - 1) / min_turns;
1978}
1979
1980/************************************************************************/
1984static void begin_search(struct cm_state *state,
1985 const struct cm_parameter *parameter,
1986 bool negative_ok)
1987{
1988#ifdef GATHER_TIME_STATS
1989 timer_start(performance.current->wall_timer);
1990 performance.current->query_count++;
1991#endif /* GATHER_TIME_STATS */
1992
1993 /* copy the parameter and sort the main lattice by it */
1994 cm_copy_parameter(&state->parameter, parameter);
1995 sort_lattice_by_fitness(state, &state->lattice);
1996
1997 if (parameter->max_growth) {
2000 }
2001
2002 init_min_production(state);
2003
2004 /* Clear out the old solution */
2005 state->best_value = worst_fitness();
2007 init_partial_solution(&state->current, num_types(state),
2008 city_size_get(state->pcity),
2009 negative_ok);
2010 state->choice.size = 0;
2011}
2012
2013/************************************************************************/
2017static void end_search(struct cm_state *state)
2018{
2019#ifdef GATHER_TIME_STATS
2020 timer_stop(performance.current->wall_timer);
2021
2022#ifdef PRINT_TIME_STATS_EVERY_QUERY
2024#endif /* PRINT_TIME_STATS_EVERY_QUERY */
2025
2026 performance.current = NULL;
2027#endif /* GATHER_TIME_STATS */
2028}
2029
2030/************************************************************************/
2033static void cm_state_free(struct cm_state *state)
2034{
2041
2042 FC_FREE(state->choice.stack);
2043 FC_FREE(state->workers_map);
2044 FC_FREE(state);
2045}
2046
2047/************************************************************************/
2050static void cm_find_best_solution(struct cm_state *state,
2051 const struct cm_parameter *const parameter,
2052 struct cm_result *result, bool negative_ok)
2053{
2054 int loop_count = 0;
2055 int max_count;
2056 struct city backup;
2057
2058#ifdef GATHER_TIME_STATS
2059 performance.current = &performance.opt;
2060#endif
2061
2062 begin_search(state, parameter, negative_ok);
2063
2064 /* Make a backup of the city to restore at the very end */
2065 memcpy(&backup, state->pcity, sizeof(backup));
2066
2067 if (player_is_cpuhog(city_owner(state->pcity))) {
2069 } else {
2071 }
2072
2073 result->aborted = FALSE;
2074
2075 /* search until we find a feasible solution */
2076 while (!bb_next(state, negative_ok)) {
2077 /* Limit the number of loops. */
2078 loop_count++;
2079
2080 if (loop_count == max_count + 1) {
2081#ifdef FREECIV_TESTMATIC
2082 /* This happens at a rate inversely proportional to the number of needed iterations
2083 * https://osdn.net/projects/freeciv/ticket/44438
2084 * we mostly find solutions in less than 100 iteration
2085 * 33% in less than 24 iterations
2086 * 66% in less than 100
2087 * 99% in less than 1800
2088 * extremely rarely 10 000+
2089 * it is not a bug it is normal, so just silent this warning
2090 */
2091 log_base(
2092 LOG_DEBUG,
2093 "Did not find a cm solution in %d iterations for %s.",
2094 max_count, city_name_get(state->pcity));
2095#endif /* FREECIV_TESTMATIC */
2096
2097#ifndef CM_LOOP_NO_LIMIT
2098 result->aborted = TRUE;
2099 break;
2100#endif /* CM_LOOP_NO_LIMIT */
2101 }
2102 }
2103
2104#ifdef CM_LOOP_NO_LIMIT
2105 if (loop_count > max_count) {
2106 log_warn("It took %d iterations to finish.", loop_count);
2107 }
2108#endif /* CM_LOOP_NO_LIMIT */
2109
2110 /* convert to the caller's format */
2111 convert_solution_to_result(state, &state->best, result);
2112
2113 memcpy(state->pcity, &backup, sizeof(backup));
2114
2115 end_search(state);
2116}
2117
2118/************************************************************************/
2122void cm_query_result(struct city *pcity,
2123 const struct cm_parameter *param,
2124 struct cm_result *result, bool negative_ok)
2125{
2126 struct cm_state *state = cm_state_init(pcity, negative_ok);
2127 const struct civ_map *nmap = &(wld.map);
2128
2129 /* Refresh the city. Otherwise the CM can give wrong results or just be
2130 * slower than necessary. Note that cities are often passed in in an
2131 * unrefreshed state (which should probably be fixed). */
2133
2134 cm_find_best_solution(state, param, result, negative_ok);
2135 cm_state_free(state);
2136}
2137
2138/************************************************************************/
2141bool cm_are_parameter_equal(const struct cm_parameter *const p1,
2142 const struct cm_parameter *const p2)
2143{
2145 if (p1->minimal_surplus[i] != p2->minimal_surplus[i]) {
2146 return FALSE;
2147 }
2148 if (p1->factor[i] != p2->factor[i]) {
2149 return FALSE;
2150 }
2152 if (p1->require_happy != p2->require_happy) {
2153 return FALSE;
2154 }
2155 if (p1->allow_disorder != p2->allow_disorder) {
2156 return FALSE;
2157 }
2158 if (p1->allow_specialists != p2->allow_specialists) {
2159 return FALSE;
2160 }
2161 if (p1->happy_factor != p2->happy_factor) {
2162 return FALSE;
2163 }
2164 if (p1->max_growth != p2->max_growth) {
2165 return FALSE;
2166 }
2167
2168 return TRUE;
2169}
2170
2171/************************************************************************/
2175 const struct cm_parameter *const src)
2176{
2177 memcpy(dest, src, sizeof(struct cm_parameter));
2178}
2179
2180/************************************************************************/
2184{
2186 dest->minimal_surplus[stat_index] = 0;
2187 dest->factor[stat_index] = 1;
2189
2190 dest->happy_factor = 1;
2191 dest->require_happy = FALSE;
2192 dest->allow_disorder = FALSE;
2193 dest->allow_specialists = TRUE;
2194 dest->max_growth = FALSE;
2195}
2196
2197/************************************************************************/
2202{
2205 dest->factor[stat_index] = 1;
2207
2208 dest->happy_factor = 1;
2209 dest->require_happy = FALSE;
2210 dest->allow_disorder = TRUE;
2211 dest->allow_specialists = TRUE;
2212 dest->max_growth = FALSE;
2213}
2214
2215/************************************************************************/
2218int cm_result_workers(const struct cm_result *result)
2219{
2220 int count = 0;
2221
2222 city_map_iterate(result->city_radius_sq, cindex, x, y) {
2223 if (is_free_worked_index(cindex)) {
2224 continue;
2225 }
2226
2227 if (result->worker_positions[cindex]) {
2228 count++;
2229 }
2231
2232 return count;
2233}
2234
2235/************************************************************************/
2238int cm_result_specialists(const struct cm_result *result)
2239{
2240 int count = 0;
2241
2243 count += result->specialists[spec];
2245
2246 return count;
2247}
2248
2249/************************************************************************/
2252int cm_result_citizens(const struct cm_result *result)
2253{
2254 return cm_result_workers(result) + cm_result_specialists(result);
2255}
2256
2257/************************************************************************/
2262 const struct city *pcity)
2263{
2264 cm_result_copy(result, pcity, NULL);
2265}
2266
2267/************************************************************************/
2272static void cm_result_copy(struct cm_result *result,
2273 const struct city *pcity, bool *workers_map)
2274{
2275 struct tile *pcenter = city_tile(pcity);
2276 const struct civ_map *nmap = &(wld.map);
2277
2278 /* Clear worker positions */
2279 memset(result->worker_positions, 0,
2280 sizeof(*result->worker_positions)
2281 * city_map_tiles(result->city_radius_sq));
2282
2284 if (workers_map == NULL) {
2285 /* Use the main map */
2286 struct city *pwork = tile_worked(ptile);
2287
2288 result->worker_positions[ctindex] = (NULL != pwork && pwork == pcity);
2289 } else {
2290 result->worker_positions[ctindex] = workers_map[ctindex];
2291 }
2293
2294 /* Copy the specialist counts */
2296 result->specialists[spec] = pcity->specialists[spec];
2298
2299 /* Find the surplus production numbers */
2300 get_city_surplus(pcity, result->surplus,
2301 &result->disorder, &result->happy);
2302
2303 /* This is a valid result, in a sense */
2304 result->found_a_valid = TRUE;
2305}
2306
2307/************************************************************************/
2310#ifdef CM_DEBUG
2311static void snprint_production(char *buffer, size_t bufsz,
2312 const int production[])
2313{
2314 fc_snprintf(buffer, bufsz, "[%d %d %d %d %d %d]",
2318}
2319
2320/************************************************************************/
2323static void real_print_tile_type(enum log_level level, const char *file,
2324 const char *function, int line,
2325 const struct cm_tile_type *ptype,
2326 const char *prefix)
2327{
2328 char prodstr[256];
2329
2330 snprint_production(prodstr, sizeof(prodstr), ptype->production);
2331 do_log(file, function, line, FALSE, level,
2332 "%s%s fitness %g depth %d, idx %d; %d tiles", prefix,
2333 prodstr, ptype->estimated_fitness, ptype->lattice_depth,
2334 ptype->lattice_index, tile_type_num_tiles(ptype));
2335}
2336
2337/************************************************************************/
2340static void real_print_lattice(enum log_level level, const char *file,
2341 const char *function, int line,
2342 const struct tile_type_vector *lattice)
2343{
2344 do_log(file, function, line, FALSE, level,
2345 "lattice has %u terrain types", (unsigned) lattice->size);
2349}
2350
2351/************************************************************************/
2355 const char *file,
2356 const char *function, int line,
2357 const struct partial_solution *soln,
2358 const struct cm_state *state)
2359{
2360 int i;
2361 int last_type = 0;
2362 char buf[256];
2363
2364 if (soln->idle != 0) {
2365 do_log(file, function, line, FALSE, level,
2366 "** partial solution has %d idle workers", soln->idle);
2367 } else {
2368 do_log(file, function, line, FALSE, level, "** completed solution:");
2369 }
2370
2371 snprint_production(buf, sizeof(buf), soln->production);
2372 do_log(file, function, line, FALSE, level, "production: %s", buf);
2373
2374 do_log(file, function, line, FALSE, level, "tiles used:");
2375 for (i = 0; i < num_types(state); i++) {
2376 if (soln->worker_counts[i] != 0) {
2377 fc_snprintf(buf, sizeof(buf), " %d tiles of type ",
2378 soln->worker_counts[i]);
2380 tile_type_get(state, i), buf);
2381 }
2382 }
2383
2384 for (i = 0; i < num_types(state); i++) {
2385 if (soln->worker_counts[i] != 0) {
2386 last_type = i;
2387 }
2388 }
2389
2390 do_log(file, function, line, FALSE, level, "tiles available:");
2391 for (i = last_type; i < num_types(state); i++) {
2392 const struct cm_tile_type *ptype = tile_type_get(state, i);
2393
2394 if (soln->prereqs_filled[i] == tile_type_num_prereqs(ptype)
2395 && soln->worker_counts[i] < tile_type_num_tiles(ptype)) {
2397 tile_type_get(state, i), " ");
2398 }
2399 }
2400}
2401
2402#endif /* CM_DEBUG */
2403
2404#ifdef GATHER_TIME_STATS
2405/************************************************************************/
2408static void print_performance(struct one_perf *counts)
2409{
2410 double s, ms;
2411 double q;
2412 int queries, applies;
2413
2414 s = timer_read_seconds(counts->wall_timer);
2415 ms = 1000.0 * s;
2416
2417 queries = counts->query_count;
2418 q = queries;
2419
2420 applies = counts->apply_count;
2421
2423 "CM-%s: overall=%fs queries=%d %fms / query, %d applies",
2424 counts->name, s, queries, ms / q, applies);
2425}
2426#endif /* GATHER_TIME_STATS */
2427
2428/************************************************************************/
2431void cm_print_city(const struct city *pcity)
2432{
2433 struct tile *pcenter = city_tile(pcity);
2434 const struct civ_map *nmap = &(wld.map);
2435
2436 log_test("cm_print_city(city %d=\"%s\")", pcity->id, city_name_get(pcity));
2437 log_test(" size=%d, specialists=%s",
2439
2440 log_test(" workers at:");
2442 cindex) {
2443 struct city *pwork = tile_worked(ptile);
2444
2445 if (NULL != pwork && pwork == pcity) {
2446 int cx, cy;
2447
2448 city_tile_index_to_xy(&cx, &cy, cindex,
2449 city_map_radius_sq_get(pcity));
2450 log_test(" {%2d,%2d} (%4d,%4d)", cx, cy, TILE_XY(ptile));
2451 }
2453
2454 log_test(" food = %3d (%+3d)",
2455 pcity->prod[O_FOOD], pcity->surplus[O_FOOD]);
2456 log_test(" shield = %3d (%+3d)",
2457 pcity->prod[O_SHIELD], pcity->surplus[O_SHIELD]);
2458 log_test(" trade = %3d", pcity->surplus[O_TRADE]);
2459
2460 log_test(" gold = %3d (%+3d)",
2461 pcity->prod[O_GOLD], pcity->surplus[O_GOLD]);
2462 log_test(" luxury = %3d", pcity->prod[O_LUXURY]);
2463 log_test(" science = %3d", pcity->prod[O_SCIENCE]);
2464}
2465
2466/************************************************************************/
2469void cm_print_result(const struct cm_result *result)
2470{
2472 sizeof(*city_map_data));
2473
2474 log_test("cm_print_result(result=%p)", (void *) result);
2475 log_test(" found_a_valid=%d disorder=%d happy=%d",
2476 result->found_a_valid, result->disorder, result->happy);
2477
2478 city_map_iterate(result->city_radius_sq, cindex, x, y) {
2479 if (is_free_worked_index(cindex)) {
2480 city_map_data[cindex] = 2;
2481 } else if (result->worker_positions[cindex]) {
2482 city_map_data[cindex] = 1;
2483 } else {
2484 city_map_data[cindex] = 0;
2485 }
2487 log_test("workers map (2: free worked; 1: worker; 0: not used):");
2490
2491 log_test(" (workers/specialists) %d/%s", cm_result_workers(result),
2493
2495 log_test(" %10s surplus=%d", get_output_name(i), result->surplus[i]);
2497}
bool base_city_celebrating(const struct city *pcity)
Definition city.c:1637
bool is_free_worked(const struct city *pcity, const struct tile *ptile)
Definition city.c:3601
int city_granary_size(int city_size)
Definition city.c:2132
struct tile * city_map_to_tile(const struct civ_map *nmap, const struct tile *city_center, int city_radius_sq, int city_map_x, int city_map_y)
Definition city.c:305
const char * city_name_get(const struct city *pcity)
Definition city.c:1137
bool city_can_use_specialist(const struct city *pcity, Specialist_type_id type)
Definition city.c:1065
bool city_tile_index_to_xy(int *city_map_x, int *city_map_y, int city_tile_index, int city_radius_sq)
Definition city.c:101
citizens player_content_citizens(const struct player *pplayer)
Definition city.c:2186
void citylog_map_data(enum log_level level, int radius_sq, int *map_data)
Definition city.c:411
bool city_unhappy(const struct city *pcity)
Definition city.c:1626
void set_city_production(struct city *pcity)
Definition city.c:2953
const char * get_output_name(Output_type_id output)
Definition city.c:629
void city_refresh_from_main_map(const struct civ_map *nmap, struct city *pcity, bool *workers_map)
Definition city.c:3176
bool city_happy(const struct city *pcity)
Definition city.c:1614
int city_map_radius_sq_get(const struct city *pcity)
Definition city.c:137
citizens city_specialists(const struct city *pcity)
Definition city.c:3317
static int cmp(int v1, int v2)
Definition city.c:325
int city_tile_output(const struct city *pcity, const struct tile *ptile, bool is_celebrating, Output_type_id otype)
Definition city.c:1283
int city_map_tiles(int city_radius_sq)
Definition city.c:171
bool city_can_work_tile(const struct city *pcity, const struct tile *ptile)
Definition city.c:1456
#define city_tile(_pcity_)
Definition city.h:564
#define city_tile_iterate_index(_nmap, _radius_sq, _city_tile, _tile, _index)
Definition city.h:201
#define CITY_MAP_MAX_RADIUS_SQ
Definition city.h:86
static citizens city_size_get(const struct city *pcity)
Definition city.h:569
#define city_tile_iterate_index_end
Definition city.h:209
#define output_type_iterate(output)
Definition city.h:845
#define city_owner(_pcity_)
Definition city.h:563
#define city_tile_iterate(_nmap, _radius_sq, _city_tile, _tile)
Definition city.h:230
#define city_map_iterate_end
Definition city.h:177
#define city_map_iterate(_radius_sq, _index, _x, _y)
Definition city.h:173
#define city_tile_iterate_end
Definition city.h:238
#define is_free_worked_index(city_tile_index)
Definition city.h:880
#define city_map_tiles_from_city(_pcity)
Definition city.h:127
#define output_type_iterate_end
Definition city.h:851
void cm_init_citymap(void)
Definition cm.c:314
static void convert_solution_to_result(struct cm_state *state, const struct partial_solution *soln, struct cm_result *result)
Definition cm.c:825
static void sort_lattice_by_fitness(const struct cm_state *state, struct tile_type_vector *lattice)
Definition cm.c:1213
static double estimate_fitness(const struct cm_state *state, const int production[])
Definition cm.c:1768
static void get_tax_rates(const struct player *pplayer, int rates[])
Definition cm.c:1738
static int specialists_in_solution(const struct cm_state *state, const struct partial_solution *soln)
Definition cm.c:1562
static void begin_search(struct cm_state *state, const struct cm_parameter *parameter, bool negative_ok)
Definition cm.c:1984
static int min_food_surplus_for_fastest_growth(struct cm_state *state)
Definition cm.c:1932
static int next_choice(struct cm_state *state, int oldchoice, bool negative_ok)
Definition cm.c:1410
static void tile_type_destroy(struct cm_tile_type *type)
Definition cm.c:412
#define LOG_TIME_STATS
Definition cm.c:95
static struct cm_fitness compute_fitness(const int surplus[], bool disorder, bool happy, const struct cm_parameter *parameter)
Definition cm.c:612
static void init_partial_solution(struct partial_solution *into, int ntypes, int idle, bool negative_ok)
Definition cm.c:651
static void complete_solution(struct partial_solution *soln, const struct cm_state *state, const struct tile_type_vector *lattice)
Definition cm.c:1510
static const struct cm_tile * tile_get(const struct cm_tile_type *ptype, int j)
Definition cm.c:570
static struct cm_fitness worst_fitness(void)
Definition cm.c:599
static bool take_child_choice(struct cm_state *state, bool negative_ok)
Definition cm.c:1476
static void compute_tile_production(const struct city *pcity, const struct tile *ptile, struct cm_tile_type *out)
Definition cm.c:960
void cm_clear_cache(struct city *pcity)
Definition cm.c:322
static const struct cm_tile_type * tile_type_get(const struct cm_state *state, int type)
Definition cm.c:554
#define LOG_LATTICE
Definition cm.c:97
static Output_type_id compare_key
Definition cm.c:913
static struct cm_fitness evaluate_solution(struct cm_state *state, const struct partial_solution *soln)
Definition cm.c:786
static int tile_type_vector_find_equivalent(const struct tile_type_vector *vec, const struct cm_tile_type *ptype)
Definition cm.c:509
void cm_copy_parameter(struct cm_parameter *dest, const struct cm_parameter *const src)
Definition cm.c:2174
static bool choice_stack_empty(struct cm_state *state)
Definition cm.c:1281
static void tile_type_vector_free_all(struct tile_type_vector *vec)
Definition cm.c:425
static struct cm_state * cm_state_init(struct city *pcity, bool negative_ok)
Definition cm.c:1860
static struct cm_tile_type * tile_type_dup(const struct cm_tile_type *oldtype)
Definition cm.c:397
static bool prereqs_filled(const struct partial_solution *soln, int type, const struct cm_state *state)
Definition cm.c:1392
static void clean_lattice(struct tile_type_vector *lattice, const struct city *pcity)
Definition cm.c:1158
void cm_init_parameter(struct cm_parameter *dest)
Definition cm.c:2183
static int tile_type_num_prereqs(const struct cm_tile_type *ptype)
Definition cm.c:544
static void copy_partial_solution(struct partial_solution *dst, const struct partial_solution *src, const struct cm_state *state)
Definition cm.c:680
static void cm_state_free(struct cm_state *state)
Definition cm.c:2033
static int compare_tile_type_by_fitness(const void *va, const void *vb)
Definition cm.c:890
struct cm_result * cm_result_new(struct city *pcity)
Definition cm.c:345
static void destroy_partial_solution(struct partial_solution *into)
Definition cm.c:670
int cm_result_specialists(const struct cm_result *result)
Definition cm.c:2238
#define print_partial_solution(loglevel, soln, state)
Definition cm.c:277
void cm_result_from_main_map(struct cm_result *result, const struct city *pcity)
Definition cm.c:2261
#define print_lattice(loglevel, lattice)
Definition cm.c:276
static bool tile_type_equal(const struct cm_tile_type *a, const struct cm_tile_type *b)
Definition cm.c:441
static void tile_type_init(struct cm_tile_type *type)
Definition cm.c:385
static void cm_result_copy(struct cm_result *result, const struct city *pcity, bool *workers_map)
Definition cm.c:2272
#define tile_type_vector_iterate(vector, var)
Definition cm.c:149
#define LOG_REACHED_LEAF
Definition cm.c:98
static void add_worker(struct partial_solution *soln, int itype, const struct cm_state *state)
Definition cm.c:1363
static bool choice_is_promising(struct cm_state *state, int newchoice, bool negative_ok)
Definition cm.c:1659
bool cm_are_parameter_equal(const struct cm_parameter *const p1, const struct cm_parameter *const p2)
Definition cm.c:2141
static double compare_key_trade_bonus
Definition cm.c:914
static void init_tile_lattice(struct city *pcity, struct tile_type_vector *lattice)
Definition cm.c:1239
static bool take_sibling_choice(struct cm_state *state, bool negative_ok)
Definition cm.c:1448
static void cm_find_best_solution(struct cm_state *state, const struct cm_parameter *const parameter, struct cm_result *result, bool negative_ok)
Definition cm.c:2050
static void apply_solution(struct cm_state *state, const struct partial_solution *soln)
Definition cm.c:700
static void init_min_production(struct cm_state *state)
Definition cm.c:1723
void cm_result_destroy(struct cm_result *result)
Definition cm.c:368
void cm_print_result(const struct cm_result *result)
Definition cm.c:2469
static void end_search(struct cm_state *state)
Definition cm.c:2017
static int compare_tile_type_by_stat(const void *va, const void *vb)
Definition cm.c:922
static int tile_type_num_tiles(const struct cm_tile_type *type)
Definition cm.c:529
static bool fitness_better(struct cm_fitness a, struct cm_fitness b)
Definition cm.c:587
void cm_query_result(struct city *pcity, const struct cm_parameter *param, struct cm_result *result, bool negative_ok)
Definition cm.c:2122
static bool bb_next(struct cm_state *state, bool negative_ok)
Definition cm.c:1823
static void top_sort_lattice(struct tile_type_vector *lattice)
Definition cm.c:1059
static void get_city_surplus(const struct city *pcity, int surplus[], bool *disorder, bool *happy)
Definition cm.c:771
#define LOG_BETTER_LEAF
Definition cm.c:99
static void compute_max_stats_heuristic(const struct cm_state *state, const struct partial_solution *soln, int production[], int check_choice, bool negative_ok)
Definition cm.c:1587
static int last_choice(struct cm_state *state)
Definition cm.c:1289
#define print_tile_type(loglevel, ptype, prefix)
Definition cm.c:275
static int compare_tile_type_by_lattice_order(const struct cm_tile_type *a, const struct cm_tile_type *b)
Definition cm.c:860
static void remove_worker(struct partial_solution *soln, int itype, const struct cm_state *state)
Definition cm.c:1372
#define CPUHOG_CM_MAX_LOOP
Definition cm.c:82
void cm_init(void)
Definition cm.c:293
static int tile_type_better(const struct cm_tile_type *a, const struct cm_tile_type *b)
Definition cm.c:465
static void init_specialist_lattice_nodes(struct tile_type_vector *lattice, const struct city *pcity)
Definition cm.c:1030
static void add_workers(struct partial_solution *soln, int itype, int number, const struct cm_state *state)
Definition cm.c:1312
int cm_result_citizens(const struct cm_result *result)
Definition cm.c:2252
static void tile_type_lattice_add(struct tile_type_vector *lattice, const struct cm_tile_type *newtype, int tindex)
Definition cm.c:978
void cm_init_emergency_parameter(struct cm_parameter *dest)
Definition cm.c:2201
static void pop_choice(struct cm_state *state)
Definition cm.c:1382
#define LOG_PRUNE_BRANCH
Definition cm.c:100
static int num_types(const struct cm_state *state)
Definition cm.c:1301
#define tile_type_vector_iterate_end
Definition cm.c:154
#define LOG_CM_STATE
Definition cm.c:96
#define CM_MAX_LOOP
Definition cm.c:80
void cm_print_city(const struct city *pcity)
Definition cm.c:2431
int cm_result_workers(const struct cm_result *result)
Definition cm.c:2218
void cm_free(void)
Definition cm.c:330
struct timer * wall_timer
Definition cma_core.c:92
char * incite_cost
Definition comments.c:75
static void base(QVariant data1, QVariant data2)
Definition dialogs.cpp:2931
unsigned char citizens
Definition fc_types.h:388
int Specialist_type_id
Definition fc_types.h:375
@ O_SHIELD
Definition fc_types.h:101
@ O_FOOD
Definition fc_types.h:101
@ O_TRADE
Definition fc_types.h:101
@ O_SCIENCE
Definition fc_types.h:101
@ O_LUXURY
Definition fc_types.h:101
@ O_GOLD
Definition fc_types.h:101
@ O_LAST
Definition fc_types.h:101
enum output_type_id Output_type_id
Definition fc_types.h:378
struct civ_game game
Definition game.c:62
struct world wld
Definition game.c:63
struct government * government_of_player(const struct player *pplayer)
Definition government.c:114
GType type
Definition repodlgs.c:1313
static const int bufsz
Definition helpdlg.c:70
const char * name
Definition inputfile.c:127
void do_log(const char *file, const char *function, int line, bool print_from_where, enum log_level level, const char *message,...)
Definition log.c:514
#define fc_assert_ret(condition)
Definition log.h:191
#define log_warn(message,...)
Definition log.h:105
#define log_test
Definition log.h:136
#define fc_assert(condition)
Definition log.h:176
#define LOG_TEST
Definition log.h:139
#define fc_assert_ret_val(condition, val)
Definition log.h:194
#define log_base(level, message,...)
Definition log.h:94
log_level
Definition log.h:28
@ LOG_DEBUG
Definition log.h:34
#define fc_calloc(n, esz)
Definition mem.h:38
#define FC_FREE(ptr)
Definition mem.h:41
#define fc_malloc(sz)
Definition mem.h:34
static bool player_is_cpuhog(const struct player *pplayer)
Definition player.h:575
struct setting_list * level[OLEVELS_NUM]
Definition settings.c:190
#define FC_INFINITY
Definition shared.h:36
#define MAX(x, y)
Definition shared.h:54
const char * specialists_string(const citizens *specialist_list)
Definition specialist.c:199
int get_specialist_output(const struct city *pcity, Specialist_type_id sp, Output_type_id otype)
Definition specialist.c:217
#define specialist_type_iterate_end
Definition specialist.h:79
#define specialist_type_iterate(sp)
Definition specialist.h:73
struct sprite int int y
Definition sprite_g.h:31
struct sprite int x
Definition sprite_g.h:31
Definition city.h:320
int surplus[O_LAST]
Definition city.h:355
int food_stock
Definition city.h:367
int id
Definition city.h:326
int city_radius_sq
Definition city.h:375
int citizen_base[O_LAST]
Definition city.h:359
int usage[O_LAST]
Definition city.h:360
struct universal production
Definition city.h:396
bool happy
Definition city.h:462
int bonus[O_LAST]
Definition city.h:363
citizens specialists[SP_MAX]
Definition city.h:336
struct tile * tile
Definition city.h:322
int prod[O_LAST]
Definition city.h:358
struct packet_game_info info
Definition game.h:89
struct government * government_during_revolution
Definition game.h:94
int weighted
Definition cm.c:119
bool sufficient
Definition cm.c:120
bool allow_disorder
Definition cm.h:44
int factor[O_LAST]
Definition cm.h:47
bool max_growth
Definition cm.h:42
bool allow_specialists
Definition cm.h:45
bool require_happy
Definition cm.h:43
int minimal_surplus[O_LAST]
Definition cm.h:41
int happy_factor
Definition cm.h:48
Definition cm.h:52
bool found_a_valid
Definition cm.h:54
bool disorder
Definition cm.h:54
bool aborted
Definition cm.h:53
int surplus[O_LAST]
Definition cm.h:56
bool happy
Definition cm.h:54
bool * worker_positions
Definition cm.h:59
int city_radius_sq
Definition cm.h:58
citizens specialists[SP_MAX]
Definition cm.h:60
Definition cm.c:200
int size
Definition cm.c:231
struct partial_solution best
Definition cm.c:210
struct cm_parameter parameter
Definition cm.c:202
int min_production[O_LAST]
Definition cm.c:217
struct tile_type_vector lattice
Definition cm.c:206
struct partial_solution current
Definition cm.c:223
struct tile_type_vector lattice_by_prod[O_LAST]
Definition cm.c:207
struct cm_fitness best_value
Definition cm.c:211
bool * workers_map
Definition cm.c:234
int min_luxury
Definition cm.c:220
struct city * pcity
Definition cm.c:203
int * stack
Definition cm.c:230
struct cm_state::@15 choice
int production[O_LAST]
Definition cm.c:169
Specialist_type_id spec
Definition cm.c:172
struct tile_type_vector better_types
Definition cm.c:174
struct tile_vector tiles
Definition cm.c:173
bool is_specialist
Definition cm.c:171
int lattice_depth
Definition cm.c:177
int lattice_index
Definition cm.c:176
struct tile_type_vector worse_types
Definition cm.c:175
double estimated_fitness
Definition cm.c:170
Definition cm.c:135
const struct cm_tile_type * type
Definition cm.c:136
int index
Definition cm.c:137
int production[O_LAST]
Definition cm.c:191
int * worker_counts
Definition cm.c:188
int * prereqs_filled
Definition cm.c:189
struct player_economic economic
Definition player.h:282
Definition tile.h:50
int index
Definition tile.h:51
Definition timing.c:81
struct civ_map map
int fc_snprintf(char *str, size_t n, const char *format,...)
Definition support.c:974
#define TRUE
Definition support.h:46
#define FALSE
Definition support.h:47
#define bool
Definition support.h:71
#define tile_worked(_tile)
Definition tile.h:114
#define TILE_XY(ptile)
Definition tile.h:43
void timer_destroy(struct timer *t)
Definition timing.c:208
void timer_start(struct timer *t)
Definition timing.c:264
void timer_stop(struct timer *t)
Definition timing.c:308
struct timer * timer_new(enum timer_timetype type, enum timer_use use, const char *name)
Definition timing.c:160
double timer_read_seconds(struct timer *t)
Definition timing.c:384
@ TIMER_ACTIVE
Definition timing.h:46
@ TIMER_USER
Definition timing.h:42