Freeciv-3.3
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#ifndef FREECIV_NDEBUG
706 int citizen_count = 0;
707#endif
708
709#ifdef GATHER_TIME_STATS
710 performance.current->apply_count++;
711#endif
712
713 fc_assert_ret(0 == soln->idle);
714
715 /* Clear all specialists, and remove all workers from fields (except
716 * the city center). */
717 memset(&pcity->specialists, 0, sizeof(pcity->specialists));
718
720 if (is_free_worked_index(cindex)) {
721 state->workers_map[cindex] = TRUE;
722 } else {
723 state->workers_map[cindex] = FALSE;
724 }
726
727 /* Now for each tile type, find the right number of such tiles and set them
728 * as worked. For specialists we just increase the number of specialists
729 * of that type. */
730 for (i = 0 ; i < num_types(state); i++) {
731 int nworkers = soln->worker_counts[i];
732 const struct cm_tile_type *type;
733
734 if (nworkers == 0) {
735 /* No citizens of this type. */
736 continue;
737 }
738#ifndef FREECIV_NDEBUG
740#endif
741
742 type = tile_type_get(state, i);
743
744 if (type->is_specialist) {
745 /* Just increase the number of specialists. */
746 pcity->specialists[type->spec] += nworkers;
747 } else {
748 int j;
749
750 /* Place citizen workers onto the citymap tiles. */
751 for (j = 0; j < nworkers; j++) {
752 const struct cm_tile *cmtile = tile_get(type, j);
753
754 state->workers_map[cmtile->index] = TRUE;
755 }
756 }
757 }
758
759 /* Finally we must refresh the city to reset all the precomputed fields. */
762}
763
764/************************************************************************/
769static void get_city_surplus(const struct city *pcity,
770 int surplus[],
771 bool *disorder, bool *happy)
772{
774 surplus[o] = pcity->surplus[o];
776
777 *disorder = city_unhappy(pcity);
778 *happy = city_happy(pcity);
779}
780
781/************************************************************************/
785 const struct partial_solution *soln)
786{
787 struct city *pcity = state->pcity;
788 int surplus[O_LAST];
789 bool disorder, happy;
790
791 /* apply and evaluate the solution, backup is done in find_best_solution */
792 apply_solution(state, soln);
793 get_city_surplus(pcity, surplus, &disorder, &happy);
794
795 /* if this solution is not content, we have an estimate on min. luxuries */
796 if (disorder) {
797 /* We have to consider the influence of each specialist in this
798 solution possibly 'hiding' a potential unhappy citizen who
799 could require luxuries.
800 Since we know the city is in disorder, we can discount most
801 effects that make citizens content, since they clearly weren't
802 sufficient.
803 This may not be sufficient luxury to make the city content (due
804 to military unhappiness etc), but certainly no less will do.
805 (Specialists may also be making angry citizens content, requiring
806 additional luxuries, but we don't try to consider that here; this
807 just means we might explore some solutions unnecessarily.) */
810
811 state->min_luxury = surplus[O_LUXURY]
813 + 1;
814 }
815
816 return compute_fitness(surplus, disorder, happy, &state->parameter);
817}
818
819/************************************************************************/
823static void convert_solution_to_result(struct cm_state *state,
824 const struct partial_solution *soln,
825 struct cm_result *result)
826{
827 struct cm_fitness fitness;
828
829 if (soln->idle != 0) {
830 /* If there are unplaced citizens it's not a real solution, so the
831 * result is invalid. */
832 result->found_a_valid = FALSE;
833 return;
834 }
835
836 /* apply and evaluate the solution, backup is done in find_best_solution */
837 apply_solution(state, soln);
838 cm_result_copy(result, state->pcity, state->workers_map);
839
840 /* result->found_a_valid should be only true if it matches the
841 * parameter; figure out if it does */
842 fitness = compute_fitness(result->surplus, result->disorder,
843 result->happy, &state->parameter);
844 result->found_a_valid = fitness.sufficient;
845}
846
847/****************************************************************************
848 Compare functions to allow sorting lattice vectors.
849****************************************************************************/
850
851/************************************************************************/
859 const struct cm_tile_type *b)
860{
861 if (a == b) {
862 return 0;
863 }
864
865 /* Least depth first */
866 if (a->lattice_depth != b->lattice_depth) {
867 return a->lattice_depth - b->lattice_depth;
868 }
869
870 /* With equal depth, break ties arbitrarily, more production first. */
874 }
876
877 /* If we get here, then we have two copies of identical types, an error */
879 return 0;
880}
881
882/************************************************************************/
888static int compare_tile_type_by_fitness(const void *va, const void *vb)
889{
890 struct cm_tile_type * const *a = va;
891 struct cm_tile_type * const *b = vb;
892 double diff;
893
894 if (*a == *b) {
895 return 0;
896 }
897
898 /* To avoid double->int roundoff problems, we call a result non-zero only
899 * if it's larger than 0.5. */
900 diff = (*b)->estimated_fitness - (*a)->estimated_fitness;
901 if (diff > 0.5) {
902 return 1; /* return value is int; don't round down! */
903 }
904 if (diff < -0.5) {
905 return -1;
906 }
907
909}
910
913
914/************************************************************************/
920static int compare_tile_type_by_stat(const void *va, const void *vb)
921{
922 struct cm_tile_type * const *a = va;
923 struct cm_tile_type * const *b = vb;
924
925 if (*a == *b) {
926 return 0;
927 }
928
929 /* Consider the influence of trade on science, luxury, gold
930 for compute_max_stats_heuristics, which uses these sorted arrays,
931 it is essential, that the sorting is correct, else promising
932 branches get pruned */
933 double valuea = (*a)->production[compare_key] +
934 compare_key_trade_bonus * (*a)->production[O_TRADE];
935 double valueb = (*b)->production[compare_key] +
936 compare_key_trade_bonus * (*b)->production[O_TRADE];
937
938 /* Most production of what we care about goes first */
939 /* Double compare is ok, both values are calculated in the same way
940 and should only be considered equal, if equal in compare_key
941 and O_TRADE */
942 if (valuea != valueb) {
943 /* b-a so we sort big numbers first */
944 return valueb - valuea;
945 }
946
948}
949
950/****************************************************************************
951 Compute the tile-type lattice.
952****************************************************************************/
953
954/************************************************************************/
958static void compute_tile_production(const struct city *pcity,
959 const struct tile *ptile,
960 struct cm_tile_type *out)
961{
963
965 out->production[o] = city_tile_output(pcity, ptile, is_celebrating, o);
967}
968
969/************************************************************************/
976static void tile_type_lattice_add(struct tile_type_vector *lattice,
977 const struct cm_tile_type *newtype,
978 int tindex)
979{
980 struct cm_tile_type *type;
981 int i;
982
984 if (i >= 0) {
985 /* We already have this type of tile; use it. */
986 type = lattice->p[i];
987 } else {
988 /* This is a new tile type; add it to the lattice. */
990
991 /* Link up to the types we dominate, and those that dominate us */
994
995 if (cmp > 0) {
996 tile_type_vector_append(&type->better_types, other);
997 tile_type_vector_append(&other->worse_types, type);
998 } else if (cmp < 0) {
999 tile_type_vector_append(&other->better_types, type);
1000 tile_type_vector_append(&type->worse_types, other);
1001 }
1003
1004 /* Insert into the list */
1005 type->lattice_index = lattice->size;
1006 tile_type_vector_append(lattice, type);
1007 }
1008
1009 /* Finally, add the tile to the tile type. */
1010 if (!type->is_specialist) {
1011 struct cm_tile tile;
1012
1013 tile.type = type;
1014 tile.index = tindex;
1015
1016 tile_vector_append(&type->tiles, tile);
1017 }
1018}
1019
1020/*
1021 * Add the specialist types to the lattice.
1022 */
1023
1024/************************************************************************/
1029 const struct city *pcity)
1030{
1031 struct cm_tile_type type;
1032
1034 type.is_specialist = TRUE;
1035
1036 /* for each specialist type, create a tile_type that has as production
1037 * the bonus for the specialist (if the city is allowed to use it) */
1039 if (city_can_use_specialist(pcity, i)) {
1040 type.spec = i;
1041 output_type_iterate(output) {
1042 type.production[output] = get_specialist_output(pcity, i, output);
1044
1045 tile_type_lattice_add(lattice, &type, 0);
1046 }
1048}
1049
1050/************************************************************************/
1057static void top_sort_lattice(struct tile_type_vector *lattice)
1058{
1059 if (lattice->size > 0) {
1060 int i;
1061 bool marked[lattice->size];
1062 bool will_mark[lattice->size];
1063 struct tile_type_vector vectors[2];
1064 struct tile_type_vector *current, *next;
1065
1066 memset(marked, 0, sizeof(marked));
1067 memset(will_mark, 0, sizeof(will_mark));
1068
1071 current = &vectors[0];
1072 next = &vectors[1];
1073
1074 /* Fill up 'next' */
1076 if (tile_type_num_prereqs(ptype) == 0) {
1078 }
1080
1081 /* While we have nodes to process: mark the nodes whose prereqs have
1082 * all been visited. Then, store all the new nodes on the frontier. */
1083 while (next->size != 0) {
1084 /* What was the next frontier is now the current frontier */
1085 struct tile_type_vector *vtmp = current;
1086
1087 current = next;
1088 next = vtmp;
1089 next->size = 0; /* Clear out the contents */
1090
1091 /* Look over the current frontier and process everyone */
1093 /* See if all prereqs were marked. If so, decide to mark this guy,
1094 and put all the descendents on 'next'. */
1095 bool can_mark = TRUE;
1096 int sumdepth = 0;
1097
1098 if (will_mark[ptype->lattice_index]) {
1099 continue; /* We've already been processed */
1100 }
1101 tile_type_vector_iterate(&ptype->better_types, better) {
1102 if (!marked[better->lattice_index]) {
1103 can_mark = FALSE;
1104 break;
1105 } else {
1106 sumdepth += tile_type_num_tiles(better);
1107 if (sumdepth >= FC_INFINITY) {
1108 /* If this is the case, then something better could
1109 always be used, and the same holds for our children */
1111 can_mark = TRUE;
1112 break;
1113 }
1114 }
1116 if (can_mark) {
1117 /* Mark and put successors on the next frontier */
1118 will_mark[ptype->lattice_index] = TRUE;
1119 tile_type_vector_iterate(&ptype->worse_types, worse) {
1122
1123 /* This is what we spent all this time computing. */
1124 ptype->lattice_depth = sumdepth;
1125 }
1127
1128 /* Now, actually mark everyone and get set for next loop */
1129 for (i = 0; i < lattice->size; i++) {
1130 marked[i] = marked[i] || will_mark[i];
1131 will_mark[i] = FALSE;
1132 }
1133 }
1134
1137 }
1138}
1139
1140/************************************************************************/
1156static void clean_lattice(struct tile_type_vector *lattice,
1157 const struct city *pcity)
1158{
1159 int i, j; /* i is the index we read, j is the index we write */
1160 struct tile_type_vector tofree;
1161 bool forced_loop = FALSE;
1162
1163 /* We collect the types we want to remove and free them in one fell
1164 swoop at the end, in order to avoid memory errors. */
1166
1167 /* forced_loop is workaround for what seems like gcc optimization
1168 * bug.
1169 * This applies to -O2 optimization on some distributions. */
1170 if (lattice->size > 0) {
1171 forced_loop = TRUE;
1172 }
1173 for (i = 0, j = 0; i < lattice->size || forced_loop; i++) {
1174 struct cm_tile_type *ptype = lattice->p[i];
1175 citizens csize = city_size_get(pcity);
1176
1178
1179 if (ptype->lattice_depth >= csize) {
1181 } else {
1182 /* Remove links to children that are being removed. */
1183
1184 int ci, cj; /* 'c' for 'child'; read from ci, write to cj */
1185
1186 lattice->p[j] = ptype;
1187 lattice->p[j]->lattice_index = j;
1188 j++;
1189
1190 for (ci = 0, cj = 0; ci < ptype->worse_types.size; ci++) {
1191 const struct cm_tile_type *ptype2 = ptype->worse_types.p[ci];
1192
1193 if (ptype2->lattice_depth < csize) {
1194 ptype->worse_types.p[cj] = ptype->worse_types.p[ci];
1195 cj++;
1196 }
1197 }
1198 ptype->worse_types.size = cj;
1199 }
1200 }
1201 lattice->size = j;
1202
1204}
1205
1206/************************************************************************/
1211static void sort_lattice_by_fitness(const struct cm_state *state,
1212 struct tile_type_vector *lattice)
1213{
1214 int i;
1215
1216 /* compute fitness */
1218 ptype->estimated_fitness = estimate_fitness(state, ptype->production);
1220
1221 /* sort by it */
1222 qsort(lattice->p, lattice->size, sizeof(*lattice->p),
1224
1225 /* fix the lattice indices */
1226 for (i = 0; i < lattice->size; i++) {
1227 lattice->p[i]->lattice_index = i;
1228 }
1229
1230 log_base(LOG_LATTICE, "sorted lattice:");
1231 print_lattice(LOG_LATTICE, lattice);
1232}
1233
1234/************************************************************************/
1237static void init_tile_lattice(struct city *pcity,
1238 struct tile_type_vector *lattice)
1239{
1240 struct cm_tile_type type;
1241 struct tile *pcenter = city_tile(pcity);
1242 const struct civ_map *nmap = &(wld.map);
1243
1244 /* Add all the fields into the lattice */
1245 tile_type_init(&type); /* Init just once */
1246
1248 ctindex) {
1249 if (is_free_worked(pcity, ptile)) {
1250 continue;
1251 } else if (city_can_work_tile(pcity, ptile)) {
1252 compute_tile_production(pcity, ptile, &type); /* Clobbers type */
1253 tile_type_lattice_add(lattice, &type, ctindex); /* Copy type if needed */
1254 }
1256
1257 /* Add all the specialists into the lattice. */
1258 init_specialist_lattice_nodes(lattice, pcity);
1259
1260 /* Set the lattice_depth fields, and clean up unreachable nodes. */
1261 top_sort_lattice(lattice);
1262 clean_lattice(lattice, pcity);
1263
1264 /* All done now. */
1265 print_lattice(LOG_LATTICE, lattice);
1266}
1267
1268
1269/****************************************************************************
1270
1271 Handling the choice stack for the bb algorithm.
1272
1273****************************************************************************/
1274
1275
1276/************************************************************************/
1279static bool choice_stack_empty(struct cm_state *state)
1280{
1281 return state->choice.size == 0;
1282}
1283
1284/************************************************************************/
1287static int last_choice(struct cm_state *state)
1288{
1290
1291 return state->choice.stack[state->choice.size - 1];
1292}
1293
1294/************************************************************************/
1299static int num_types(const struct cm_state *state)
1300{
1301 return tile_type_vector_size(&state->lattice);
1302}
1303
1304/************************************************************************/
1311 int itype, int number,
1312 const struct cm_state *state)
1313{
1314 const struct cm_tile_type *ptype = tile_type_get(state, itype);
1315 int newcount;
1316 int old_worker_count = soln->worker_counts[itype];
1317
1318 if (number == 0) {
1319 return;
1320 }
1321
1322 /* update the number of idle workers */
1323 newcount = soln->idle - number;
1324 fc_assert_ret(newcount >= 0);
1326 soln->idle = newcount;
1327
1328 /* update the worker counts */
1329 newcount = soln->worker_counts[itype] + number;
1330 fc_assert_ret(newcount >= 0);
1332 soln->worker_counts[itype] = newcount;
1333
1334 /* update prereqs array: if we are no longer full but we were,
1335 * we need to decrement the count, and vice-versa. */
1337 fc_assert_ret(number < 0);
1338 tile_type_vector_iterate(&ptype->worse_types, other) {
1339 soln->prereqs_filled[other->lattice_index]--;
1340 fc_assert_ret(soln->prereqs_filled[other->lattice_index] >= 0);
1342 } else if (soln->worker_counts[itype] == tile_type_num_tiles(ptype)) {
1343 fc_assert_ret(number > 0);
1344 tile_type_vector_iterate(&ptype->worse_types, other) {
1345 soln->prereqs_filled[other->lattice_index]++;
1346 fc_assert_ret(soln->prereqs_filled[other->lattice_index]
1349 }
1350
1351 /* update production */
1353 newcount = soln->production[stat_index] + number * ptype->production[stat_index];
1354 soln->production[stat_index] = newcount;
1356}
1357
1358/************************************************************************/
1362 int itype, const struct cm_state *state)
1363{
1364 add_workers(soln, itype, 1, state);
1365}
1366
1367/************************************************************************/
1371 int itype, const struct cm_state *state)
1372{
1373 add_workers(soln, itype, -1, state);
1374}
1375
1376/************************************************************************/
1380static void pop_choice(struct cm_state *state)
1381{
1383 remove_worker(&state->current, last_choice(state), state);
1384 state->choice.size--;
1385}
1386
1387/************************************************************************/
1390static bool prereqs_filled(const struct partial_solution *soln, int type,
1391 const struct cm_state *state)
1392{
1393 const struct cm_tile_type *ptype = tile_type_get(state, type);
1395
1396 return soln->prereqs_filled[type] == prereqs;
1397}
1398
1399/************************************************************************/
1408static int next_choice(struct cm_state *state, int oldchoice, bool negative_ok)
1409{
1410 int newchoice;
1411
1412 for (newchoice = oldchoice + 1;
1413 newchoice < num_types(state); newchoice++) {
1414 const struct cm_tile_type *ptype = tile_type_get(state, newchoice);
1415
1416 if (!ptype->is_specialist && (state->current.worker_counts[newchoice]
1417 == tile_vector_size(&ptype->tiles))) {
1418 /* we've already used all these tiles */
1419 continue;
1420 }
1421 if (!prereqs_filled(&state->current, newchoice, state)) {
1422 /* we could use a strictly better tile instead */
1423 continue;
1424 }
1426 /* heuristic says we can't beat the best going this way */
1427 log_base(LOG_PRUNE_BRANCH, "--- pruning branch ---");
1430 " + worker on ");
1431 log_base(LOG_PRUNE_BRANCH, "--- branch pruned ---");
1432 continue;
1433 }
1434 break;
1435 }
1436
1437 /* returns num_types if no next choice was available. */
1438 return newchoice;
1439}
1440
1441
1442/************************************************************************/
1446static bool take_sibling_choice(struct cm_state *state, bool negative_ok)
1447{
1448 int oldchoice = last_choice(state);
1449 int newchoice;
1450
1451 /* need to remove first, to run the heuristic */
1452 remove_worker(&state->current, oldchoice, state);
1454
1455 if (newchoice == num_types(state)) {
1456 /* add back in so the caller can then remove it again. */
1457 add_worker(&state->current, oldchoice, state);
1458 return FALSE;
1459 } else {
1460 add_worker(&state->current, newchoice, state);
1461 state->choice.stack[state->choice.size-1] = newchoice;
1462 /* choice.size is unchanged */
1463 return TRUE;
1464 }
1465}
1466
1467/************************************************************************/
1474static bool take_child_choice(struct cm_state *state, bool negative_ok)
1475{
1476 int oldchoice, newchoice;
1477
1478 if (state->current.idle == 0) {
1479 return FALSE;
1480 }
1481
1482 if (state->choice.size == 0) {
1483 oldchoice = 0;
1484 } else {
1485 oldchoice = last_choice(state);
1486 }
1487
1488 /* oldchoice-1 because we can use oldchoice again */
1490
1491 /* did we fail? */
1492 if (newchoice == num_types(state)) {
1493 return FALSE;
1494 }
1495
1496 /* now push the new choice on the choice stack */
1497 add_worker(&state->current, newchoice, state);
1498 state->choice.stack[state->choice.size] = newchoice;
1499 state->choice.size++;
1500
1501 return TRUE;
1502}
1503
1504/************************************************************************/
1509 const struct cm_state *state,
1510 const struct tile_type_vector *lattice)
1511{
1512 int last_worker_choice = -1;
1513 int i;
1514
1515 if (soln->idle == 0) {
1516 return;
1517 }
1518
1519 /* find the last worker type added (-1 if none) */
1520 for (i = 0; i < num_types(state); i++) {
1521 if (soln->worker_counts[i] != 0) {
1523 }
1524 }
1525
1526 /* While there are idle workers, pick up the next-best kind of tile,
1527 * and assign the workers to the tiles.
1528 * Respect lexicographic order and prerequisites. */
1530 int used = soln->worker_counts[ptype->lattice_index];
1531 int total = tile_type_num_tiles(ptype);
1532 int touse;
1533
1534 if (ptype->lattice_index < last_worker_choice) {
1535 /* lex-order: we can't use ptype (some other branch
1536 will check this combination, or already did) */
1537 continue;
1538 }
1539 if (!prereqs_filled(soln, ptype->lattice_index, state)) {
1540 /* don't bother using this tile before all better tiles are used */
1541 continue;
1542 }
1543
1544 touse = total - used;
1545 if (touse > soln->idle) {
1546 touse = soln->idle;
1547 }
1548 add_workers(soln, ptype->lattice_index, touse, state);
1549
1550 if (soln->idle == 0) {
1551 /* nothing left to do here */
1552 return;
1553 }
1555}
1556
1557/************************************************************************/
1560static int specialists_in_solution(const struct cm_state *state,
1561 const struct partial_solution *soln)
1562{
1563 int count = 0;
1564 int i;
1565
1566 for (i = 0 ; i < num_types(state); i++) {
1567 if (soln->worker_counts[i] > 0 && tile_type_get(state, i)->is_specialist) {
1568 count += soln->worker_counts[i];
1569 }
1570 }
1571
1572 return count;
1573}
1574
1575/************************************************************************/
1585static void compute_max_stats_heuristic(const struct cm_state *state,
1586 const struct partial_solution *soln,
1587 int production[],
1588 int check_choice, bool negative_ok)
1589{
1590 struct partial_solution solnplus; /* Will be soln, plus some tiles */
1591 const struct civ_map *nmap = &(wld.map);
1592
1593 /* Production is whatever the solution produces, plus the
1594 most possible of each kind of production the idle workers could
1595 produce */
1596
1597 if (soln->idle == 1) {
1598 /* Then the total solution is soln + this new worker. So we know the
1599 production exactly, and can shortcut the later code. */
1600 const struct cm_tile_type *ptype = tile_type_get(state, check_choice);
1601
1602 memcpy(production, soln->production, sizeof(soln->production));
1604 production[stat_index] += ptype->production[stat_index];
1606
1607 } else {
1608
1609 /* Initialize solnplus here, after the shortcut check */
1611 city_size_get(state->pcity),
1612 negative_ok);
1613
1615 /* compute the solution that has soln, then the check_choice,
1616 then complete it with the best available tiles for the stat. */
1620
1623
1625
1626 }
1627
1628 /* We found the basic production, however, bonus, taxes,
1629 * free production, tithes, trade routes are missing.
1630 * We add free production, and have the city.c code do the rest */
1631
1632 struct city *pcity = state->pcity;
1633 struct tile *pcenter = city_tile(pcity);
1635
1637 int base = production[stat_index];
1638
1640 if (is_free_worked(pcity, ptile)) {
1642 }
1644 pcity->citizen_base[stat_index] = base;
1646
1647 set_city_production(pcity);
1648 memcpy(production, pcity->prod, sizeof(pcity->prod));
1649}
1650
1651/************************************************************************/
1657static bool choice_is_promising(struct cm_state *state, int newchoice,
1658 bool negative_ok)
1659{
1660 int production[O_LAST];
1661 bool beats_best = FALSE;
1662
1663 /* this computes an upper bound (componentwise) for the current branch,
1664 if it is worse in every component than the best, or still insufficient,
1665 then we can prune the whole branch */
1666 compute_max_stats_heuristic(state, &state->current, production, newchoice,
1667 negative_ok);
1668
1670 if (production[stat_index] < state->min_production[stat_index]) {
1671 log_base(LOG_PRUNE_BRANCH, "--- pruning: insufficient %s (%d < %d)",
1673 state->min_production[stat_index]);
1674 return FALSE;
1675 }
1676 if (production[stat_index] > state->best.production[stat_index]
1677 && state->parameter.factor[stat_index] > 0 ) {
1678 beats_best = TRUE;
1679 /* may still fail to meet min at another production type, so
1680 * don't short-circuit */
1681 }
1683
1684 /* If we don't get the city content, we assume using every idle worker
1685 as specialist and the maximum producible luxury already computed.
1686 If this is less than the amount of luxury we calculated in
1687 evaluate_solution() (where min_luxury is set), when we observed the
1688 city in disorder, then this is clearly not worth pursuing.
1689 (Since we're comparing to evaluate_solution()'s calculation, we
1690 don't need to take effects, angry citizens etc into account here
1691 either.)
1692 FIXME: this heuristic will break in rulesets where specialists can
1693 influence happiness other than by direct production of luxury. */
1694 {
1699 int max_luxury = production[O_LUXURY]
1701
1702 if (max_luxury < state->min_luxury ) {
1703 log_base(LOG_PRUNE_BRANCH, "--- pruning: disorder (%d + %d*%d < %d)",
1704 production[O_LUXURY],
1707 state->min_luxury);
1708 return FALSE;
1709 }
1710 }
1711 if (!beats_best) {
1712 log_base(LOG_PRUNE_BRANCH, "--- pruning: best is better in all important ways");
1713 }
1714
1715 return beats_best;
1716}
1717
1718/************************************************************************/
1721static void init_min_production(struct cm_state *state)
1722{
1723 struct city *pcity = state->pcity;
1724
1726 state->min_production[o] = pcity->usage[o] + state->parameter.minimal_surplus[o];
1728
1729 /* We could get a minimum on luxury if we knew how many luxuries were
1730 * needed to make us content. */
1731}
1732
1733/************************************************************************/
1736static void get_tax_rates(const struct player *pplayer, int rates[])
1737{
1738 const int SCIENCE = 0, TAX = 1, LUXURY = 2;
1739
1740 if (game.info.changable_tax) {
1741 rates[SCIENCE] = pplayer->economic.science;
1742 rates[LUXURY] = pplayer->economic.luxury;
1743 rates[TAX] = 100 - rates[SCIENCE] - rates[LUXURY];
1744 } else {
1748 }
1749
1750 /* ANARCHY */
1752 rates[SCIENCE] = 0;
1753 rates[LUXURY] = 100;
1754 rates[TAX] = 0;
1755 }
1756}
1757
1758/************************************************************************/
1766static double estimate_fitness(const struct cm_state *state,
1767 const int production[])
1768{
1769 const int SCIENCE = 0, TAX = 1, LUXURY = 2;
1770 const struct city *pcity = state->pcity;
1771 const struct player *pplayer = city_owner(pcity);
1772 int rates[3];
1773 double estimates[O_LAST];
1774 double sum = 0;
1775 int trade;
1776
1778 estimates[stat_index] = production[stat_index];
1780
1781 /* bonus to trade is applied before calculating taxes, see city.c */
1782 trade = estimates[O_TRADE] * pcity->bonus[O_TRADE] / 100.0;
1783
1784 get_tax_rates(pplayer, rates);
1785
1786 /* sci/lux/gold get benefit from the tax rates (in percentage) */
1788 += rates[SCIENCE] * trade / 100.0;
1790 += rates[LUXURY] * trade / 100.0;
1792 += rates[TAX] * trade / 100.0;
1793
1794 /* now add in the bonuses from building effects (in percentage) */
1796 estimates[stat_index] *= pcity->bonus[stat_index] / 100.0;
1798
1799 /* finally, sum it all up, weighted by the parameter, but give additional
1800 * weight to luxuries to take account of disorder/happy constraints */
1804 sum += estimates[O_LUXURY];
1805
1806 return sum;
1807}
1808
1809/************************************************************************/
1821static bool bb_next(struct cm_state *state, bool negative_ok)
1822{
1823 /* if no idle workers, then look at our solution. */
1824 if (state->current.idle == 0) {
1825 struct cm_fitness value = evaluate_solution(state, &state->current);
1826
1828 if (fitness_better(value, state->best_value)) {
1829 log_base(LOG_BETTER_LEAF, "-> replaces previous best");
1830 copy_partial_solution(&state->best, &state->current, state);
1831 state->best_value = value;
1832 }
1833 }
1834
1835 /* try to move to a child branch, if we can. If not (including if we're
1836 at a leaf), then move to a sibling. */
1837 if (!take_child_choice(state, negative_ok)) {
1838 /* keep trying to move to a sibling branch, or popping out a level if
1839 we're stuck (fully examined the current branch) */
1840 while ((!choice_stack_empty(state))
1841 && !take_sibling_choice(state, negative_ok)) {
1842 pop_choice(state);
1843 }
1844
1845 /* if we popped out all the way, we're done */
1846 if (choice_stack_empty(state)) {
1847 return TRUE;
1848 }
1849 }
1850
1851 /* if we didn't detect that we were done, we aren't */
1852 return FALSE;
1853}
1854
1855/************************************************************************/
1858static struct cm_state *cm_state_init(struct city *pcity, bool negative_ok)
1859{
1860 const int SCIENCE = 0, TAX = 1, LUXURY = 2;
1861 const struct player *pplayer = city_owner(pcity);
1862 int numtypes;
1863 struct cm_state *state = fc_malloc(sizeof(*state));
1864 int rates[3];
1866
1867 log_base(LOG_CM_STATE, "creating cm_state for %s (size %d)",
1869
1870 /* copy the arguments */
1871 state->pcity = pcity;
1872
1873 /* create the lattice */
1877
1878 get_tax_rates(pplayer, rates);
1879
1880 /* For the heuristic, make sorted copies of the lattice */
1882 int lsize = tile_type_vector_size(&state->lattice);
1883
1884 if (lsize > 0) {
1888 /* Calculate effect of 1 trade production on interesting production */
1889 switch (stat_index) {
1890 case O_SCIENCE:
1892 break;
1893 case O_LUXURY:
1895 break;
1896 case O_GOLD:
1898 break;
1899 default:
1901 break;
1902 }
1904 sizeof(*state->lattice_by_prod[stat_index].p),
1906 }
1908
1909 state->min_luxury = - FC_INFINITY;
1910
1911 /* We have no best solution yet, so its value is the worst possible. */
1913 state->best_value = worst_fitness();
1914
1915 /* Initialize the current solution and choice stack to empty */
1917 state->choice.stack = fc_malloc(csize * sizeof(*state->choice.stack));
1918 state->choice.size = 0;
1919
1920 /* Initialize workers map */
1922 sizeof(state->workers_map));
1923
1924 return state;
1925}
1926
1927/************************************************************************/
1931{
1932 struct city *pcity = state->pcity;
1934 citizens city_size = city_size_get(pcity);
1935 int max_surplus = -game.info.food_cost * city_size;
1937 citizens workers = city_size;
1938 int food_needed = city_granary_size(city_size) - pcity->food_stock;
1939 int min_turns;
1940 const struct civ_map *nmap = &(wld.map);
1941
1942 city_map_iterate(city_radius_sq, cindex, x, y) {
1943 struct tile *ptile = city_map_to_tile(nmap, pcity->tile, city_radius_sq, x, y);
1944 if (!ptile) {
1945 continue;
1946 }
1947 if (is_free_worked_index(cindex)) {
1949 }
1951
1952 if (max_surplus <= 0) {
1953 return max_surplus;
1954 }
1955
1956 if (food_needed <= 0) {
1957 return 0;
1958 }
1959
1961 int num = tile_vector_size(&ptype->tiles);
1962
1963 if (ptype->is_specialist || workers < num) {
1964 max_surplus += workers * ptype->production[O_FOOD];
1965 break;
1966 }
1967 max_surplus += num * ptype->production[O_FOOD];
1968 workers -= num;
1970
1971 /* min_turns will always be positive because if food_needed or
1972 * max_surplus are non-positive, this function returns earlier. */
1974
1975 return (food_needed + min_turns - 1) / min_turns;
1976}
1977
1978/************************************************************************/
1982static void begin_search(struct cm_state *state,
1983 const struct cm_parameter *parameter,
1984 bool negative_ok)
1985{
1986#ifdef GATHER_TIME_STATS
1987 timer_start(performance.current->wall_timer);
1988 performance.current->query_count++;
1989#endif /* GATHER_TIME_STATS */
1990
1991 /* copy the parameter and sort the main lattice by it */
1992 cm_copy_parameter(&state->parameter, parameter);
1993 sort_lattice_by_fitness(state, &state->lattice);
1994
1995 if (parameter->max_growth) {
1998 }
1999
2000 init_min_production(state);
2001
2002 /* Clear out the old solution */
2003 state->best_value = worst_fitness();
2005 init_partial_solution(&state->current, num_types(state),
2006 city_size_get(state->pcity),
2007 negative_ok);
2008 state->choice.size = 0;
2009}
2010
2011/************************************************************************/
2015static void end_search(struct cm_state *state)
2016{
2017#ifdef GATHER_TIME_STATS
2018 timer_stop(performance.current->wall_timer);
2019
2020#ifdef PRINT_TIME_STATS_EVERY_QUERY
2022#endif /* PRINT_TIME_STATS_EVERY_QUERY */
2023
2024 performance.current = NULL;
2025#endif /* GATHER_TIME_STATS */
2026}
2027
2028/************************************************************************/
2031static void cm_state_free(struct cm_state *state)
2032{
2039
2040 FC_FREE(state->choice.stack);
2041 FC_FREE(state->workers_map);
2042 FC_FREE(state);
2043}
2044
2045/************************************************************************/
2048static void cm_find_best_solution(struct cm_state *state,
2049 const struct cm_parameter *const parameter,
2050 struct cm_result *result, bool negative_ok)
2051{
2052 int loop_count = 0;
2053 int max_count;
2054 struct city backup;
2055
2056#ifdef GATHER_TIME_STATS
2057 performance.current = &performance.opt;
2058#endif
2059
2060 begin_search(state, parameter, negative_ok);
2061
2062 /* Make a backup of the city to restore at the very end */
2063 memcpy(&backup, state->pcity, sizeof(backup));
2064
2065 if (player_is_cpuhog(city_owner(state->pcity))) {
2067 } else {
2069 }
2070
2071 result->aborted = FALSE;
2072
2073 /* search until we find a feasible solution */
2074 while (!bb_next(state, negative_ok)) {
2075 /* Limit the number of loops. */
2076 loop_count++;
2077
2078 if (loop_count == max_count + 1) {
2079#ifdef FREECIV_TESTMATIC
2080 /* This happens at a rate inversely proportional to the number of needed iterations
2081 * https://osdn.net/projects/freeciv/ticket/44438
2082 * we mostly find solutions in less than 100 iteration
2083 * 33% in less than 24 iterations
2084 * 66% in less than 100
2085 * 99% in less than 1800
2086 * extremely rarely 10 000+
2087 * it is not a bug it is normal, so just silent this warning
2088 */
2089 log_base(
2090 LOG_DEBUG,
2091 "Did not find a cm solution in %d iterations for %s.",
2092 max_count, city_name_get(state->pcity));
2093#endif /* FREECIV_TESTMATIC */
2094
2095#ifndef CM_LOOP_NO_LIMIT
2096 result->aborted = TRUE;
2097 break;
2098#endif /* CM_LOOP_NO_LIMIT */
2099 }
2100 }
2101
2102#ifdef CM_LOOP_NO_LIMIT
2103 if (loop_count > max_count) {
2104 log_warn("It took %d iterations to finish.", loop_count);
2105 }
2106#endif /* CM_LOOP_NO_LIMIT */
2107
2108 /* convert to the caller's format */
2109 convert_solution_to_result(state, &state->best, result);
2110
2111 memcpy(state->pcity, &backup, sizeof(backup));
2112
2113 end_search(state);
2114}
2115
2116/************************************************************************/
2120void cm_query_result(struct city *pcity,
2121 const struct cm_parameter *param,
2122 struct cm_result *result, bool negative_ok)
2123{
2124 struct cm_state *state = cm_state_init(pcity, negative_ok);
2125
2126 /* Refresh the city. Otherwise the CM can give wrong results or just be
2127 * slower than necessary. Note that cities are often passed in in an
2128 * unrefreshed state (which should probably be fixed). */
2130
2131 cm_find_best_solution(state, param, result, negative_ok);
2132 cm_state_free(state);
2133}
2134
2135/************************************************************************/
2138bool cm_are_parameter_equal(const struct cm_parameter *const p1,
2139 const struct cm_parameter *const p2)
2140{
2142 if (p1->minimal_surplus[i] != p2->minimal_surplus[i]) {
2143 return FALSE;
2144 }
2145 if (p1->factor[i] != p2->factor[i]) {
2146 return FALSE;
2147 }
2149 if (p1->require_happy != p2->require_happy) {
2150 return FALSE;
2151 }
2152 if (p1->allow_disorder != p2->allow_disorder) {
2153 return FALSE;
2154 }
2155 if (p1->allow_specialists != p2->allow_specialists) {
2156 return FALSE;
2157 }
2158 if (p1->happy_factor != p2->happy_factor) {
2159 return FALSE;
2160 }
2161 if (p1->max_growth != p2->max_growth) {
2162 return FALSE;
2163 }
2164
2165 return TRUE;
2166}
2167
2168/************************************************************************/
2172 const struct cm_parameter *const src)
2173{
2174 memcpy(dest, src, sizeof(struct cm_parameter));
2175}
2176
2177/************************************************************************/
2181{
2183 dest->minimal_surplus[stat_index] = 0;
2184 dest->factor[stat_index] = 1;
2186
2187 dest->happy_factor = 1;
2188 dest->require_happy = FALSE;
2189 dest->allow_disorder = FALSE;
2190 dest->allow_specialists = TRUE;
2191 dest->max_growth = FALSE;
2192}
2193
2194/************************************************************************/
2199{
2202 dest->factor[stat_index] = 1;
2204
2205 dest->happy_factor = 1;
2206 dest->require_happy = FALSE;
2207 dest->allow_disorder = TRUE;
2208 dest->allow_specialists = TRUE;
2209 dest->max_growth = FALSE;
2210}
2211
2212/************************************************************************/
2215int cm_result_workers(const struct cm_result *result)
2216{
2217 int count = 0;
2218
2219 city_map_iterate(result->city_radius_sq, cindex, x, y) {
2220 if (is_free_worked_index(cindex)) {
2221 continue;
2222 }
2223
2224 if (result->worker_positions[cindex]) {
2225 count++;
2226 }
2228
2229 return count;
2230}
2231
2232/************************************************************************/
2235int cm_result_specialists(const struct cm_result *result)
2236{
2237 int count = 0;
2238
2240 count += result->specialists[spec];
2242
2243 return count;
2244}
2245
2246/************************************************************************/
2249int cm_result_citizens(const struct cm_result *result)
2250{
2251 return cm_result_workers(result) + cm_result_specialists(result);
2252}
2253
2254/************************************************************************/
2259 const struct city *pcity)
2260{
2261 cm_result_copy(result, pcity, NULL);
2262}
2263
2264/************************************************************************/
2269static void cm_result_copy(struct cm_result *result,
2270 const struct city *pcity, bool *workers_map)
2271{
2272 struct tile *pcenter = city_tile(pcity);
2273 const struct civ_map *nmap = &(wld.map);
2274
2275 /* Clear worker positions */
2276 memset(result->worker_positions, 0,
2277 sizeof(*result->worker_positions)
2278 * city_map_tiles(result->city_radius_sq));
2279
2281 if (workers_map == NULL) {
2282 /* Use the main map */
2283 struct city *pwork = tile_worked(ptile);
2284
2285 result->worker_positions[ctindex] = (NULL != pwork && pwork == pcity);
2286 } else {
2287 result->worker_positions[ctindex] = workers_map[ctindex];
2288 }
2290
2291 /* Copy the specialist counts */
2293 result->specialists[spec] = pcity->specialists[spec];
2295
2296 /* Find the surplus production numbers */
2297 get_city_surplus(pcity, result->surplus,
2298 &result->disorder, &result->happy);
2299
2300 /* This is a valid result, in a sense */
2301 result->found_a_valid = TRUE;
2302}
2303
2304/************************************************************************/
2307#ifdef CM_DEBUG
2308static void snprint_production(char *buffer, size_t bufsz,
2309 const int production[])
2310{
2311 fc_snprintf(buffer, bufsz, "[%d %d %d %d %d %d]",
2315}
2316
2317/************************************************************************/
2320static void real_print_tile_type(enum log_level level, const char *file,
2321 const char *function, int line,
2322 const struct cm_tile_type *ptype,
2323 const char *prefix)
2324{
2325 char prodstr[256];
2326
2327 snprint_production(prodstr, sizeof(prodstr), ptype->production);
2328 do_log(file, function, line, FALSE, level,
2329 "%s%s fitness %g depth %d, idx %d; %d tiles", prefix,
2330 prodstr, ptype->estimated_fitness, ptype->lattice_depth,
2331 ptype->lattice_index, tile_type_num_tiles(ptype));
2332}
2333
2334/************************************************************************/
2337static void real_print_lattice(enum log_level level, const char *file,
2338 const char *function, int line,
2339 const struct tile_type_vector *lattice)
2340{
2341 do_log(file, function, line, FALSE, level,
2342 "lattice has %u terrain types", (unsigned) lattice->size);
2346}
2347
2348/************************************************************************/
2352 const char *file,
2353 const char *function, int line,
2354 const struct partial_solution *soln,
2355 const struct cm_state *state)
2356{
2357 int i;
2358 int last_type = 0;
2359 char buf[256];
2360
2361 if (soln->idle != 0) {
2362 do_log(file, function, line, FALSE, level,
2363 "** partial solution has %d idle workers", soln->idle);
2364 } else {
2365 do_log(file, function, line, FALSE, level, "** completed solution:");
2366 }
2367
2368 snprint_production(buf, sizeof(buf), soln->production);
2369 do_log(file, function, line, FALSE, level, "production: %s", buf);
2370
2371 do_log(file, function, line, FALSE, level, "tiles used:");
2372 for (i = 0; i < num_types(state); i++) {
2373 if (soln->worker_counts[i] != 0) {
2374 fc_snprintf(buf, sizeof(buf), " %d tiles of type ",
2375 soln->worker_counts[i]);
2377 tile_type_get(state, i), buf);
2378 }
2379 }
2380
2381 for (i = 0; i < num_types(state); i++) {
2382 if (soln->worker_counts[i] != 0) {
2383 last_type = i;
2384 }
2385 }
2386
2387 do_log(file, function, line, FALSE, level, "tiles available:");
2388 for (i = last_type; i < num_types(state); i++) {
2389 const struct cm_tile_type *ptype = tile_type_get(state, i);
2390
2391 if (soln->prereqs_filled[i] == tile_type_num_prereqs(ptype)
2392 && soln->worker_counts[i] < tile_type_num_tiles(ptype)) {
2394 tile_type_get(state, i), " ");
2395 }
2396 }
2397}
2398
2399#endif /* CM_DEBUG */
2400
2401#ifdef GATHER_TIME_STATS
2402/************************************************************************/
2405static void print_performance(struct one_perf *counts)
2406{
2407 double s, ms;
2408 double q;
2409 int queries, applies;
2410
2411 s = timer_read_seconds(counts->wall_timer);
2412 ms = 1000.0 * s;
2413
2414 queries = counts->query_count;
2415 q = queries;
2416
2417 applies = counts->apply_count;
2418
2420 "CM-%s: overall=%fs queries=%d %fms / query, %d applies",
2421 counts->name, s, queries, ms / q, applies);
2422}
2423#endif /* GATHER_TIME_STATS */
2424
2425/************************************************************************/
2428void cm_print_city(const struct city *pcity)
2429{
2430 struct tile *pcenter = city_tile(pcity);
2431 const struct civ_map *nmap = &(wld.map);
2432
2433 log_test("cm_print_city(city %d=\"%s\")", pcity->id, city_name_get(pcity));
2434 log_test(" size=%d, specialists=%s",
2436
2437 log_test(" workers at:");
2439 cindex) {
2440 struct city *pwork = tile_worked(ptile);
2441
2442 if (NULL != pwork && pwork == pcity) {
2443 int cx, cy;
2444
2445 city_tile_index_to_xy(&cx, &cy, cindex,
2446 city_map_radius_sq_get(pcity));
2447 log_test(" {%2d,%2d} (%4d,%4d)", cx, cy, TILE_XY(ptile));
2448 }
2450
2451 log_test(" food = %3d (%+3d)",
2452 pcity->prod[O_FOOD], pcity->surplus[O_FOOD]);
2453 log_test(" shield = %3d (%+3d)",
2454 pcity->prod[O_SHIELD], pcity->surplus[O_SHIELD]);
2455 log_test(" trade = %3d", pcity->surplus[O_TRADE]);
2456
2457 log_test(" gold = %3d (%+3d)",
2458 pcity->prod[O_GOLD], pcity->surplus[O_GOLD]);
2459 log_test(" luxury = %3d", pcity->prod[O_LUXURY]);
2460 log_test(" science = %3d", pcity->prod[O_SCIENCE]);
2461}
2462
2463/************************************************************************/
2466void cm_print_result(const struct cm_result *result)
2467{
2469 sizeof(*city_map_data));
2470
2471 log_test("cm_print_result(result=%p)", (void *) result);
2472 log_test(" found_a_valid=%d disorder=%d happy=%d",
2473 result->found_a_valid, result->disorder, result->happy);
2474
2475 city_map_iterate(result->city_radius_sq, cindex, x, y) {
2476 if (is_free_worked_index(cindex)) {
2477 city_map_data[cindex] = 2;
2478 } else if (result->worker_positions[cindex]) {
2479 city_map_data[cindex] = 1;
2480 } else {
2481 city_map_data[cindex] = 0;
2482 }
2484 log_test("workers map (2: free worked; 1: worker; 0: not used):");
2487
2488 log_test(" (workers/specialists) %d/%s", cm_result_workers(result),
2490
2492 log_test(" %10s surplus=%d", get_output_name(i), result->surplus[i]);
2494}
bool base_city_celebrating(const struct city *pcity)
Definition city.c:1633
bool is_free_worked(const struct city *pcity, const struct tile *ptile)
Definition city.c:3597
int city_granary_size(int city_size)
Definition city.c:2129
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:1133
bool city_can_use_specialist(const struct city *pcity, Specialist_type_id type)
Definition city.c:1061
void city_refresh_from_main_map(struct city *pcity, bool *workers_map)
Definition city.c:3171
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:2183
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:1622
void set_city_production(struct city *pcity)
Definition city.c:2950
const char * get_output_name(Output_type_id output)
Definition city.c:629
bool city_happy(const struct city *pcity)
Definition city.c:1610
int city_map_radius_sq_get(const struct city *pcity)
Definition city.c:137
citizens city_specialists(const struct city *pcity)
Definition city.c:3313
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:1279
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:1452
#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:836
#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:871
#define city_map_tiles_from_city(_pcity)
Definition city.h:127
#define output_type_iterate_end
Definition city.h:842
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:823
static void sort_lattice_by_fitness(const struct cm_state *state, struct tile_type_vector *lattice)
Definition cm.c:1211
static double estimate_fitness(const struct cm_state *state, const int production[])
Definition cm.c:1766
static void get_tax_rates(const struct player *pplayer, int rates[])
Definition cm.c:1736
static int specialists_in_solution(const struct cm_state *state, const struct partial_solution *soln)
Definition cm.c:1560
static void begin_search(struct cm_state *state, const struct cm_parameter *parameter, bool negative_ok)
Definition cm.c:1982
static int min_food_surplus_for_fastest_growth(struct cm_state *state)
Definition cm.c:1930
static int next_choice(struct cm_state *state, int oldchoice, bool negative_ok)
Definition cm.c:1408
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:1508
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:1474
static void compute_tile_production(const struct city *pcity, const struct tile *ptile, struct cm_tile_type *out)
Definition cm.c:958
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:911
static struct cm_fitness evaluate_solution(struct cm_state *state, const struct partial_solution *soln)
Definition cm.c:784
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:2171
static bool choice_stack_empty(struct cm_state *state)
Definition cm.c:1279
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:1858
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:1390
static void clean_lattice(struct tile_type_vector *lattice, const struct city *pcity)
Definition cm.c:1156
void cm_init_parameter(struct cm_parameter *dest)
Definition cm.c:2180
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:2031
static int compare_tile_type_by_fitness(const void *va, const void *vb)
Definition cm.c:888
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:2235
#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:2258
#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:2269
#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:1361
static bool choice_is_promising(struct cm_state *state, int newchoice, bool negative_ok)
Definition cm.c:1657
bool cm_are_parameter_equal(const struct cm_parameter *const p1, const struct cm_parameter *const p2)
Definition cm.c:2138
static double compare_key_trade_bonus
Definition cm.c:912
static void init_tile_lattice(struct city *pcity, struct tile_type_vector *lattice)
Definition cm.c:1237
static bool take_sibling_choice(struct cm_state *state, bool negative_ok)
Definition cm.c:1446
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:2048
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:1721
void cm_result_destroy(struct cm_result *result)
Definition cm.c:368
void cm_print_result(const struct cm_result *result)
Definition cm.c:2466
static void end_search(struct cm_state *state)
Definition cm.c:2015
static int compare_tile_type_by_stat(const void *va, const void *vb)
Definition cm.c:920
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:2120
static bool bb_next(struct cm_state *state, bool negative_ok)
Definition cm.c:1821
static void top_sort_lattice(struct tile_type_vector *lattice)
Definition cm.c:1057
static void get_city_surplus(const struct city *pcity, int surplus[], bool *disorder, bool *happy)
Definition cm.c:769
#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:1585
static int last_choice(struct cm_state *state)
Definition cm.c:1287
#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:858
static void remove_worker(struct partial_solution *soln, int itype, const struct cm_state *state)
Definition cm.c:1370
#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:1028
static void add_workers(struct partial_solution *soln, int itype, int number, const struct cm_state *state)
Definition cm.c:1310
int cm_result_citizens(const struct cm_result *result)
Definition cm.c:2249
static void tile_type_lattice_add(struct tile_type_vector *lattice, const struct cm_tile_type *newtype, int tindex)
Definition cm.c:976
void cm_init_emergency_parameter(struct cm_parameter *dest)
Definition cm.c:2198
static void pop_choice(struct cm_state *state)
Definition cm.c:1380
#define LOG_PRUNE_BRANCH
Definition cm.c:100
static int num_types(const struct cm_state *state)
Definition cm.c:1299
#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:2428
int cm_result_workers(const struct cm_result *result)
Definition cm.c:2215
void cm_free(void)
Definition cm.c:330
struct timer * wall_timer
Definition cma_core.c:91
char * incite_cost
Definition comments.c:74
static void base(QVariant data1, QVariant data2)
Definition dialogs.cpp:2938
unsigned char citizens
Definition fc_types.h:392
int Specialist_type_id
Definition fc_types.h:379
@ 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:382
struct civ_game game
Definition game.c:61
struct world wld
Definition game.c:62
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:577
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:284
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:960
#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:115
#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