common/research.c

   1 /****************************************************************************
   2  Freeciv - Copyright (C) 2004 - The Freeciv Team
   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 #ifdef HAVE_CONFIG_H
  14 #include <fc_config.h>
  15 #endif
  16
  17 /* utility */
  18 #include "iterator.h"
  19 #include "log.h"
  20 #include "shared.h"
  21 #include "string_vector.h"
  22 #include "support.h"
  23
  24 /* common */
  25 #include "fc_types.h"
  26 #include "game.h"
  27 #include "player.h"
  28 #include "name_translation.h"
  29 #include "team.h"
  30 #include "tech.h"
  31
  32 #include "research.h"
  33
  34
  35 struct research_iter {
  36   struct iterator vtable;
  37   int index;
  38 };
  39 #define RESEARCH_ITER(p) ((struct research_iter *) p)
  40
  41 struct research_player_iter {
  42   struct iterator vtable;
  43   union {
  44     struct player *pplayer;
  45     struct player_list_link *plink;
  46   };
  47 };
  48 #define RESEARCH_PLAYER_ITER(p) ((struct research_player_iter *) p)
  49
  50 static struct research research_array[MAX_NUM_PLAYER_SLOTS];
  51
  52 static struct name_translation advance_unset_name = NAME_INIT;
  53 static struct name_translation advance_future_name = NAME_INIT;
  54 static struct name_translation advance_unknown_name = NAME_INIT;
  55
  56 static struct strvec *future_rule_name;
  57 static struct strvec *future_name_translation;
  58
  59 /****************************************************************************
  60   Initializes all player research structure.
  61 ****************************************************************************/
  62 void researches_init(void)
  63 {
  64   int i;
  65
  66   /* Ensure we have enough space for players or teams. */
  67   fc_assert(ARRAY_SIZE(research_array) >= team_slot_count());
  68   fc_assert(ARRAY_SIZE(research_array) >= player_slot_count());
  69
  70   memset(research_array, 0, sizeof(research_array));
  71   for (i = 0; i < ARRAY_SIZE(research_array); i++) {
  72     research_array[i].tech_goal = A_UNSET;
  73     research_array[i].researching = A_UNSET;
  74     research_array[i].researching_saved = A_UNKNOWN;
  75     research_array[i].future_tech = 0;
  76     research_array[i].inventions[A_NONE].state = TECH_KNOWN;
  77   }
  78
  79   game.info.global_advances[A_NONE] = TRUE;
  80
  81   /* Set technology names. */
  82   /* TRANS: "None" tech */
  83   name_set(&advance_unset_name, NULL, N_("?tech:None"));
  84   name_set(&advance_future_name, NULL, N_("Future Tech."));
  85   /* TRANS: "Unknown" advance/technology */
  86   name_set(&advance_unknown_name, NULL, N_("(Unknown)"));
  87
  88   future_rule_name = strvec_new();
  89   future_name_translation = strvec_new();
  90 }
  91
  92 /****************************************************************************
  93   Free all resources allocated for the research system
  94 ****************************************************************************/
  95 void researches_free(void)
  96 {
  97   strvec_destroy(future_rule_name);
  98   strvec_destroy(future_name_translation);
  99 }
 100
 101 /****************************************************************************
 102   Returns the index of the research in the array.
 103 ****************************************************************************/
 104 int research_number(const struct research *presearch)
 105 {
 106   fc_assert_ret_val(NULL != presearch, -1);
 107   return presearch - research_array;
 108 }
 109
 110 /****************************************************************************
 111   Returns the research for the given index.
 112 ****************************************************************************/
 113 struct research *research_by_number(int number)
 114 {
 115   fc_assert_ret_val(0 <= number, NULL);
 116   fc_assert_ret_val(ARRAY_SIZE(research_array) > number, NULL);
 117   return &research_array[number];
 118 }
 119
 120 /****************************************************************************
 121   Returns the research structure associated with the player.
 122 ****************************************************************************/
 123 struct research *research_get(const struct player *pplayer)
 124 {
 125   if (NULL == pplayer) {
 126     /* Special case used at client side. */
 127     return NULL;
 128   } else if (game.info.team_pooled_research) {
 129     return &research_array[team_number(pplayer->team)];
 130   } else {
 131     return &research_array[player_number(pplayer)];
 132   }
 133 }
 134
 135 /****************************************************************************
 136   Returns the name of the research owner: a player name or a team name.
 137 ****************************************************************************/
 138 const char *research_rule_name(const struct research *presearch)
 139 {
 140   if (game.info.team_pooled_research) {
 141     return team_rule_name(team_by_number(research_number(presearch)));
 142   } else {
 143     return player_name(player_by_number(research_number(presearch)));
 144   }
 145 }
 146
 147 /****************************************************************************
 148   Returns the name of the research owner: a player name or a team name.
 149 ****************************************************************************/
 150 const char *research_name_translation(const struct research *presearch)
 151 {
 152   if (game.info.team_pooled_research) {
 153     return team_name_translation(team_by_number(research_number(presearch)));
 154   } else {
 155     return player_name(player_by_number(research_number(presearch)));
 156   }
 157 }
 158
 159 /****************************************************************************
 160   Set in 'buf' the name of the research owner. It may be either a nation
 161   plural name, or something like "members of team Red".
 162 ****************************************************************************/
 163 int research_pretty_name(const struct research *presearch, char *buf,
 164                          size_t buf_len)
 165 {
 166   const struct player *pplayer;
 167
 168   if (game.info.team_pooled_research) {
 169     const struct team *pteam = team_by_number(research_number(presearch));
 170
 171     if (1 != player_list_size(team_members(pteam))) {
 172       char buf2[buf_len];
 173
 174       team_pretty_name(pteam, buf2, sizeof(buf2));
 175       /* TRANS: e.g. "members of team 1", or even "members of team Red". */
 176       return fc_snprintf(buf, buf_len, _("members of %s"), buf2);
 177     } else {
 178       pplayer = player_list_front(team_members(pteam));
 179     }
 180   } else {
 181     pplayer = player_by_number(research_number(presearch));
 182   }
 183
 184   return fc_strlcpy(buf, nation_plural_for_player(pplayer), buf_len);
 185 }
 186
 187 /****************************************************************************
 188   Return the name translation for 'tech'. Utility for
 189   research_advance_rule_name() and research_advance_translated_name().
 190 ****************************************************************************/
 191 static inline const struct name_translation *
 192 research_advance_name(Tech_type_id tech)
 193 {
 194   if (A_UNSET == tech) {
 195     return &advance_unset_name;
 196   } else if (A_FUTURE == tech) {
 197     return &advance_future_name;
 198   } else if (A_UNKNOWN == tech) {
 199     return &advance_unknown_name;
 200   } else {
 201     const struct advance *padvance = advance_by_number(tech);
 202
 203     fc_assert_ret_val(NULL != padvance, NULL);
 204     return &padvance->name;
 205   }
 206 }
 207
 208 /****************************************************************************
 209   Set a new future tech name in the string vector, and return the string
 210   duplicate stored inside the vector.
 211 ****************************************************************************/
 212 static const char *research_future_set_name(struct strvec *psv, int no,
 213                                             const char *new_name)
 214 {
 215   if (strvec_size(psv) <= no) {
 216     /* Increase the size of the vector if needed. */
 217     strvec_reserve(psv, no + 1);
 218   }
 219
 220   /* Set in vector. */
 221   strvec_set(psv, no, new_name);
 222
 223   /* Return duplicate of 'new_name'. */
 224   return strvec_get(psv, no);
 225 }
 226
 227 /****************************************************************************
 228   Store the rule name of the given tech (including A_FUTURE) in 'buf'.
 229   'presearch' may be NULL.
 230   We don't return a static buffer because that would break anything that
 231   needed to work with more than one name at a time.
 232 ****************************************************************************/
 233 const char *research_advance_rule_name(const struct research *presearch,
 234                                        Tech_type_id tech)
 235 {
 236   if (A_FUTURE == tech && NULL != presearch) {
 237     const int no = presearch->future_tech;
 238     char buffer[256];
 239     const char *name;
 240
 241     name = strvec_get(future_rule_name, no);
 242     if (name != NULL) {
 243       /* Already stored in string vector. */
 244       return name;
 245     }
 246
 247     /* NB: 'presearch->future_tech == 0' means "Future Tech. 1". */
 248     fc_snprintf(buffer, sizeof(buffer), "%s %d",
 249                 rule_name_get(&advance_future_name),
 250                 no + 1);
 251     name = research_future_set_name(future_rule_name, no, buffer);
 252     fc_assert(name != NULL);
 253     fc_assert(name != buffer);
 254     return name;
 255   }
 256
 257   return rule_name_get(research_advance_name(tech));
 258 }
 259
 260 /****************************************************************************
 261   Store the translated name of the given tech (including A_FUTURE) in 'buf'.
 262   'presearch' may be NULL.
 263   We don't return a static buffer because that would break anything that
 264   needed to work with more than one name at a time.
 265 ****************************************************************************/
 266 const char *
 267 research_advance_name_translation(const struct research *presearch,
 268                                   Tech_type_id tech)
 269 {
 270   if (A_FUTURE == tech && NULL != presearch) {
 271     const int no = presearch->future_tech;
 272     char buffer[256];
 273     const char *name;
 274
 275     name = strvec_get(future_name_translation, no);
 276     if (name != NULL) {
 277       /* Already stored in string vector. */
 278       return name;
 279     }
 280
 281     /* NB: 'presearch->future_tech == 0' means "Future Tech. 1". */
 282     fc_snprintf(buffer, sizeof(buffer), _("Future Tech. %d"), no + 1);
 283     name = research_future_set_name(future_name_translation, no, buffer);
 284     fc_assert(name != NULL);
 285     fc_assert(name != buffer);
 286     return name;
 287   }
 288
 289   return name_translation_get(research_advance_name(tech));
 290 }
 291
 292 /**************************************************************************
 293   Returns TRUE iff the requirement vector may become active against the
 294   given target.
 295
 296   If may become active if all unchangeable requirements are active.
 297 **************************************************************************/
 298 static bool reqs_may_activate(const struct player *target_player,
 299                               const struct player *other_player,
 300                               const struct city *target_city,
 301                               const struct impr_type *target_building,
 302                               const struct tile *target_tile,
 303                               const struct unit *target_unit,
 304                               const struct unit_type *target_unittype,
 305                               const struct output_type *target_output,
 306                               const struct specialist *target_specialist,
 307                               const struct action *target_action,
 308                               const struct requirement_vector *reqs,
 309                               const enum   req_problem_type prob_type)
 310 {
 311   requirement_vector_iterate(reqs, preq) {
 312     if (is_req_unchanging(preq)
 313         && !is_req_active(target_player, other_player, target_city,
 314                           target_building, target_tile,
 315                           target_unit, target_unittype,
 316                           target_output, target_specialist, target_action,
 317                           preq, prob_type)) {
 318       return FALSE;
 319     }
 320   } requirement_vector_iterate_end;
 321   return TRUE;
 322 }
 323
 324 /**************************************************************************
 325   Evaluates the legality of starting to research this tech according to
 326   reqs_eval() and the tech's research_reqs. Returns TRUE iff legal.
 327
 328   The reqs_eval() argument evaluates the requirements. One variant may
 329   check the current situation while another may check potential future
 330   situations.
 331
 332   Helper for research_update().
 333 **************************************************************************/
 334 static bool
 335 research_allowed(const struct research *presearch,
 336                  Tech_type_id tech,
 337                  bool (*reqs_eval)(const struct player *tplr,
 338                                    const struct player *oplr,
 339                                    const struct city *tcity,
 340                                    const struct impr_type *tbld,
 341                                    const struct tile *ttile,
 342                                    const struct unit *tunit,
 343                                    const struct unit_type *tutype,
 344                                    const struct output_type *top,
 345                                    const struct specialist *tspe,
 346                                    const struct action *tact,
 347                                    const struct requirement_vector *reqs,
 348                                    const enum   req_problem_type ptype))
 349 {
 350   struct advance *adv;
 351
 352   adv = valid_advance_by_number(tech);
 353
 354   if (adv == NULL) {
 355     /* Not a valid advance. */
 356     return FALSE;
 357   }
 358
 359   research_players_iterate(presearch, pplayer) {
 360     if (reqs_eval(pplayer, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
 361                   NULL, NULL, &(adv->research_reqs), RPT_CERTAIN)) {
 362       /* It is enough that one player that shares research is allowed to
 363        * research it.
 364        * Reasoning: Imagine a tech with that requires a nation in the
 365        * player range. If the requirement applies to all players sharing
 366        * research it will be illegal in research sharing games. To require
 367        * that the player that fulfills the requirement must order it to be
 368        * researched creates unnecessary bureaucracy. */
 369       return TRUE;
 370     }
 371   } research_players_iterate_end;
 372
 373   return FALSE;
 374 }
 375
 376 /**************************************************************************
 377   Returns TRUE iff researching the given tech is allowed according to its
 378   research_reqs.
 379
 380   Helper for research_update().
 381 **************************************************************************/
 382 #define research_is_allowed(presearch, tech)                              \
 383   research_allowed(presearch, tech, are_reqs_active)
 384
 385 /**************************************************************************
 386   Returns TRUE iff researching the given tech may become allowed according
 387   to its research_reqs.
 388
 389   Helper for research_get_reachable_rreqs().
 390 **************************************************************************/
 391 #define research_may_become_allowed(presearch, tech)                      \
 392   research_allowed(presearch, tech, reqs_may_activate)
 393
 394 /****************************************************************************
 395   Returns TRUE iff the given tech is ever reachable by the players sharing
 396   the research as far as research_reqs are concerned.
 397
 398   Helper for research_get_reachable().
 399 ****************************************************************************/
 400 static bool research_get_reachable_rreqs(const struct research *presearch,
 401                                          Tech_type_id tech)
 402 {
 403   bv_techs done;
 404   Tech_type_id techs[game.control.num_tech_types];
 405   enum tech_req req;
 406   int techs_num;
 407   int i;
 408
 409   techs[0] = tech;
 410   BV_CLR_ALL(done);
 411   BV_SET(done, A_NONE);
 412   BV_SET(done, tech);
 413   techs_num = 1;
 414
 415   /* Check that all recursive requirements have their research_reqs
 416    * in order. */
 417   for (i = 0; i < techs_num; i++) {
 418     if (presearch->inventions[techs[i]].state == TECH_KNOWN) {
 419       /* This tech is already reached. What is required to research it and
 420        * the techs it depends on is therefore irrelevant. */
 421       continue;
 422     }
 423
 424     if (!research_may_become_allowed(presearch, techs[i])) {
 425       /* It will always be illegal to start researching this tech because
 426        * of unchanging requirements. Since it isn't already known and can't
 427        * be researched it must be unreachable. */
 428       return FALSE;
 429     }
 430
 431     /* Check if required techs are research_reqs reachable. */
 432     for (req = 0; req < AR_SIZE; req++) {
 433       Tech_type_id req_tech = advance_required(techs[i], req);
 434
 435       if (valid_advance_by_number(req_tech) == NULL) {
 436         return FALSE;
 437       } else if (!BV_ISSET(done, req_tech)) {
 438         fc_assert(techs_num < ARRAY_SIZE(techs));
 439         techs[techs_num] = req_tech;
 440         techs_num++;
 441
 442         BV_SET(done, req_tech);
 443       }
 444     }
 445   }
 446
 447   return TRUE;
 448 }
 449
 450 /****************************************************************************
 451   Returns TRUE iff the given tech is ever reachable by the players sharing
 452   the research by checking tech tree limitations.
 453
 454   Helper for research_update().
 455 ****************************************************************************/
 456 static bool research_get_reachable(const struct research *presearch,
 457                                    Tech_type_id tech)
 458 {
 459   if (valid_advance_by_number(tech) == NULL) {
 460     return FALSE;
 461   } else if (advance_required(tech, AR_ROOT) != A_NONE) {
 462     /* 'tech' has at least one root requirement. We need to check them
 463      * all. */
 464     bv_techs done;
 465     Tech_type_id techs[game.control.num_tech_types];
 466     enum tech_req req;
 467     int techs_num;
 468     int i;
 469
 470     techs[0] = tech;
 471     BV_CLR_ALL(done);
 472     BV_SET(done, A_NONE);
 473     BV_SET(done, tech);
 474     techs_num = 1;
 475
 476     for (i = 0; i < techs_num; i++) {
 477       if (advance_required(techs[i], AR_ROOT) == techs[i]) {
 478         /* This tech requires itself; it can only be reached by special
 479          * means (init_techs, lua script, ...).
 480          * If you already know it, you can "reach" it; if not, not. (This
 481          * case is needed for descendants of this tech.) */
 482         if (presearch->inventions[techs[i]].state != TECH_KNOWN) {
 483           return FALSE;
 484         }
 485       } else {
 486         /* Check if requirements are reachable. */
 487         Tech_type_id req_tech;
 488
 489         for (req = 0; req < AR_SIZE; req++) {
 490           req_tech = advance_required(techs[i], req);
 491           if (valid_advance_by_number(req_tech) == NULL) {
 492             return FALSE;
 493           } else if (!BV_ISSET(done, req_tech)) {
 494             if (advance_required(req_tech, AR_ROOT) != A_NONE) {
 495               fc_assert(techs_num < ARRAY_SIZE(techs));
 496               techs[techs_num] = req_tech;
 497               techs_num++;
 498             }
 499
 500             BV_SET(done, req_tech);
 501           }
 502         }
 503       }
 504     }
 505   }
 506
 507   /* Check reseach reqs reachability. */
 508   if (!research_get_reachable_rreqs(presearch, tech)) {
 509     return FALSE;
 510   }
 511
 512   return TRUE;
 513 }
 514
 515 /****************************************************************************
 516   Returns TRUE iff the players sharing 'presearch' already have got the
 517   knowledge of all root requirement technologies.
 518
 519   Helper for research_update().
 520 ****************************************************************************/
 521 static bool research_get_root_reqs_known(const struct research *presearch,
 522                                          Tech_type_id tech)
 523 {
 524   if (advance_required(tech, AR_ROOT) != A_NONE) {
 525     /* 'padvance' has got at least one root requirement. We need to check
 526      * if all of them are known. */
 527     bv_techs done;
 528     Tech_type_id techs[game.control.num_tech_types];
 529     Tech_type_id root;
 530     int techs_num;
 531     int i;
 532
 533     techs[0] = tech;
 534     BV_CLR_ALL(done);
 535     BV_SET(done, A_NONE);
 536     BV_SET(done, tech);
 537     techs_num = 1;
 538
 539     for (i = 0; i < techs_num; i++) {
 540       root = advance_required(techs[i], AR_ROOT);
 541       if (presearch->inventions[root].state != TECH_KNOWN) {
 542         return FALSE;
 543       } else {
 544         /* Check if requirement roots are also known. */
 545         enum tech_req req;
 546         Tech_type_id req_tech;
 547
 548         for (req = 0; req <= AR_TWO; req++) {
 549           req_tech = advance_required(techs[i], req);
 550           if (!BV_ISSET(done, req_tech)) {
 551             if (advance_required(req_tech, AR_ROOT) != A_NONE) {
 552               fc_assert(techs_num < ARRAY_SIZE(techs));
 553               techs[techs_num] = req_tech;
 554               techs_num++;
 555             }
 556             BV_SET(done, req_tech);
 557           }
 558         }
 559       }
 560     }
 561   }
 562
 563   return TRUE;
 564 }
 565
 566 /****************************************************************************
 567   Mark as TECH_PREREQS_KNOWN each tech which is available, not known and
 568   which has all requirements fullfiled.
 569
 570   Recalculate presearch->num_known_tech_with_flag
 571   Should always be called after research_invention_set().
 572 ****************************************************************************/
 573 void research_update(struct research *presearch)
 574 {
 575   enum tech_flag_id flag;
 576   int techs_researched;
 577
 578   advance_index_iterate(A_FIRST, i) {
 579     enum tech_state state = presearch->inventions[i].state;
 580     bool root_reqs_known = TRUE;
 581     bool reachable = research_get_reachable(presearch, i);
 582
 583     /* Finding if the root reqs of an unreachable tech isn't redundant.
 584      * A tech can be unreachable via research but have known root reqs
 585      * because of unfilfilled research_reqs. Unfulfilled research_reqs
 586      * doesn't prevent the player from aquiring the tech by other means. */
 587     root_reqs_known = research_get_root_reqs_known(presearch, i);
 588
 589     if (reachable) {
 590       if (state != TECH_KNOWN) {
 591         /* Update state. */
 592         state = (root_reqs_known
 593                  && (presearch->inventions[advance_required(i, AR_ONE)].state
 594                      == TECH_KNOWN)
 595                  && (presearch->inventions[advance_required(i, AR_TWO)].state
 596                      == TECH_KNOWN)
 597                  && research_is_allowed(presearch, i)
 598                  ? TECH_PREREQS_KNOWN : TECH_UNKNOWN);
 599       }
 600     } else {
 601       fc_assert(state == TECH_UNKNOWN);
 602     }
 603     presearch->inventions[i].state = state;
 604     presearch->inventions[i].reachable = reachable;
 605     presearch->inventions[i].root_reqs_known = root_reqs_known;
 606
 607     /* Updates required_techs, num_required_techs and bulbs_required. */
 608     BV_CLR_ALL(presearch->inventions[i].required_techs);
 609     presearch->inventions[i].num_required_techs = 0;
 610     presearch->inventions[i].bulbs_required = 0;
 611
 612     if (!reachable || state == TECH_KNOWN) {
 613       continue;
 614     }
 615
 616     techs_researched = presearch->techs_researched;
 617     advance_req_iterate(valid_advance_by_number(i), preq) {
 618       Tech_type_id j = advance_number(preq);
 619
 620       if (TECH_KNOWN == research_invention_state(presearch, j)) {
 621         continue;
 622       }
 623
 624       BV_SET(presearch->inventions[i].required_techs, j);
 625       presearch->inventions[i].num_required_techs++;
 626       presearch->inventions[i].bulbs_required +=
 627           research_total_bulbs_required(presearch, j, FALSE);
 628       /* This is needed to get a correct result for the
 629        * research_total_bulbs_required() call when
 630        * game.info.game.info.tech_cost_style is TECH_COST_CIV1CIV2. */
 631       presearch->techs_researched++;
 632     } advance_req_iterate_end;
 633     presearch->techs_researched = techs_researched;
 634   } advance_index_iterate_end;
 635
 636 #ifdef FREECIV_DEBUG
 637   advance_index_iterate(A_FIRST, i) {
 638     char buf[advance_count() + 1];
 639
 640     advance_index_iterate(A_NONE, j) {
 641       if (BV_ISSET(presearch->inventions[i].required_techs, j)) {
 642         buf[j] = '1';
 643       } else {
 644         buf[j] = '0';
 645       }
 646     } advance_index_iterate_end;
 647     buf[advance_count()] = '\0';
 648
 649     log_debug("%s: [%3d] %-25s => %s%s%s",
 650               research_rule_name(presearch),
 651               i,
 652               advance_rule_name(advance_by_number(i)),
 653               tech_state_name(research_invention_state(presearch, i)),
 654               presearch->inventions[i].reachable ? "" : " [unrechable]",
 655               presearch->inventions[i].root_reqs_known
 656               ? "" : " [root reqs aren't known]");
 657     log_debug("%s: [%3d] %s", research_rule_name(presearch), i, buf);
 658   } advance_index_iterate_end;
 659 #endif /* FREECIV_DEBUG */
 660
 661   for (flag = 0; flag <= tech_flag_id_max(); flag++) {
 662     /* Iterate over all possible tech flags (0..max). */
 663     presearch->num_known_tech_with_flag[flag] = 0;
 664
 665     advance_index_iterate(A_NONE, i) {
 666       if (TECH_KNOWN == research_invention_state(presearch, i)
 667           && advance_has_flag(i, flag)) {
 668         presearch->num_known_tech_with_flag[flag]++;
 669       }
 670     } advance_index_iterate_end;
 671   }
 672 }
 673
 674 /****************************************************************************
 675   Returns state of the tech for current research.
 676   This can be: TECH_KNOWN, TECH_UNKNOWN, or TECH_PREREQS_KNOWN
 677   Should be called with existing techs.
 678
 679   If 'presearch' is NULL this checks whether any player knows the tech
 680   (used by the client).
 681 ****************************************************************************/
 682 enum tech_state research_invention_state(const struct research *presearch,
 683                                          Tech_type_id tech)
 684 {
 685   fc_assert_ret_val(NULL != valid_advance_by_number(tech), -1);
 686
 687   if (NULL != presearch) {
 688     return presearch->inventions[tech].state;
 689   } else if (game.info.global_advances[tech]) {
 690     return TECH_KNOWN;
 691   } else {
 692     return TECH_UNKNOWN;
 693   }
 694 }
 695
 696 /****************************************************************************
 697   Set research knowledge about tech to given state.
 698 ****************************************************************************/
 699 enum tech_state research_invention_set(struct research *presearch,
 700                                        Tech_type_id tech,
 701                                        enum tech_state value)
 702 {
 703   enum tech_state old;
 704
 705   fc_assert_ret_val(NULL != valid_advance_by_number(tech), -1);
 706
 707   old = presearch->inventions[tech].state;
 708   if (old == value) {
 709     return old;
 710   }
 711   presearch->inventions[tech].state = value;
 712
 713   if (value == TECH_KNOWN) {
 714     if (!game.info.global_advances[tech]) {
 715       game.info.global_advances[tech] = TRUE;
 716       game.info.global_advance_count++;
 717     }
 718   }
 719
 720   return old;
 721 }
 722
 723 /****************************************************************************
 724   Returns TRUE iff the given tech is ever reachable via research by the
 725   players sharing the research by checking tech tree limitations.
 726
 727   'presearch' may be NULL in which case a simplified result is returned
 728   (used by the client).
 729 ****************************************************************************/
 730 bool research_invention_reachable(const struct research *presearch,
 731                                   const Tech_type_id tech)
 732 {
 733   if (valid_advance_by_number(tech) == NULL) {
 734     return FALSE;
 735   } else if (presearch != NULL) {
 736     return presearch->inventions[tech].reachable;
 737   } else {
 738     researches_iterate(research_iter) {
 739       if (research_iter->inventions[tech].reachable) {
 740         return TRUE;
 741       }
 742     } researches_iterate_end;
 743
 744     return FALSE;
 745   }
 746 }
 747
 748 /****************************************************************************
 749   Returns TRUE iff the given tech can be given to the players sharing the
 750   research immediately.
 751
 752   If allow_holes is TRUE, any tech with known root reqs is ok. If it's
 753   FALSE, getting the tech must not leave holes to the known techs tree.
 754 ****************************************************************************/
 755 bool research_invention_gettable(const struct research *presearch,
 756                                  const Tech_type_id tech,
 757                                  bool allow_holes)
 758 {
 759   if (valid_advance_by_number(tech) == NULL) {
 760     return FALSE;
 761   } else if (presearch != NULL) {
 762     return (allow_holes
 763             ? presearch->inventions[tech].root_reqs_known
 764             : presearch->inventions[tech].state == TECH_PREREQS_KNOWN);
 765   } else {
 766     researches_iterate(research_iter) {
 767       if (allow_holes
 768           ? research_iter->inventions[tech].root_reqs_known
 769           : research_iter->inventions[tech].state == TECH_PREREQS_KNOWN) {
 770         return TRUE;
 771       }
 772     } researches_iterate_end;
 773
 774     return FALSE;
 775   }
 776 }
 777
 778 /****************************************************************************
 779   Return the next tech we should research to advance towards our goal.
 780   Returns A_UNSET if nothing is available or the goal is already known.
 781 ****************************************************************************/
 782 Tech_type_id research_goal_step(const struct research *presearch,
 783                                 Tech_type_id goal)
 784 {
 785   const struct advance *pgoal = valid_advance_by_number(goal);
 786
 787   if (NULL == pgoal
 788       || !research_invention_reachable(presearch, goal)) {
 789     return A_UNSET;
 790   }
 791
 792   advance_req_iterate(pgoal, preq) {
 793     switch (research_invention_state(presearch, advance_number(preq))) {
 794     case TECH_PREREQS_KNOWN:
 795       return advance_number(preq);
 796     case TECH_KNOWN:
 797     case TECH_UNKNOWN:
 798        break;
 799     };
 800   } advance_req_iterate_end;
 801   return A_UNSET;
 802 }
 803
 804 /****************************************************************************
 805   Returns the number of technologies the player need to research to get
 806   the goal technology. This includes the goal technology. Technologies
 807   are only counted once.
 808
 809   'presearch' may be NULL in which case it will returns the total number
 810   of technologies needed for reaching the goal.
 811 ****************************************************************************/
 812 int research_goal_unknown_techs(const struct research *presearch,
 813                                 Tech_type_id goal)
 814 {
 815   const struct advance *pgoal = valid_advance_by_number(goal);
 816
 817   if (NULL == pgoal) {
 818     return 0;
 819   } else if (NULL != presearch) {
 820     return presearch->inventions[goal].num_required_techs;
 821   } else {
 822     return pgoal->num_reqs;
 823   }
 824 }
 825
 826 /****************************************************************************
 827   Function to determine cost (in bulbs) of reaching goal technology.
 828   These costs _include_ the cost for researching the goal technology
 829   itself.
 830
 831   'presearch' may be NULL in which case it will returns the total number
 832   of bulbs needed for reaching the goal.
 833 ****************************************************************************/
 834 int research_goal_bulbs_required(const struct research *presearch,
 835                                  Tech_type_id goal)
 836 {
 837   const struct advance *pgoal = valid_advance_by_number(goal);
 838
 839   if (NULL == pgoal) {
 840     return 0;
 841   } else if (NULL != presearch) {
 842     return presearch->inventions[goal].bulbs_required;
 843   } else if (game.info.tech_cost_style == TECH_COST_CIV1CIV2) {
 844      return game.info.base_tech_cost * pgoal->num_reqs
 845             * (pgoal->num_reqs + 1) / 2;
 846   } else {
 847     int bulbs_required = 0;
 848
 849     advance_req_iterate(pgoal, preq) {
 850       bulbs_required += preq->cost;
 851     } advance_req_iterate_end;
 852     return bulbs_required;
 853   }
 854 }
 855
 856 /****************************************************************************
 857   Returns if the given tech has to be researched to reach the goal. The
 858   goal itself isn't a requirement of itself.
 859
 860   'presearch' may be NULL.
 861 ****************************************************************************/
 862 bool research_goal_tech_req(const struct research *presearch,
 863                             Tech_type_id goal, Tech_type_id tech)
 864 {
 865   const struct advance *pgoal, *ptech;
 866
 867   if (tech == goal
 868       || NULL == (pgoal = valid_advance_by_number(goal))
 869       || NULL == (ptech = valid_advance_by_number(tech))) {
 870     return FALSE;
 871   } else if (NULL != presearch) {
 872     return BV_ISSET(presearch->inventions[goal].required_techs, tech);
 873   } else {
 874     advance_req_iterate(pgoal, preq) {
 875       if (preq == ptech) {
 876         return TRUE;
 877       }
 878     } advance_req_iterate_end;
 879     return FALSE;
 880   }
 881 }
 882
 883 /****************************************************************************
 884   Function to determine cost for technology.  The equation is determined
 885   from game.info.tech_cost_style and game.info.tech_leakage.
 886
 887   tech_cost_style:
 888   TECH_COST_CIV1CIV2: Civ (I|II) style. Every new tech add base_tech_cost to
 889                       cost of next tech.
 890   TECH_COST_CLASSIC: Cost of technology is:
 891                        base_tech_cost * (1 + reqs) * sqrt(1 + reqs) / 2
 892                      where reqs == number of requirement for tech, counted
 893                      recursively.
 894   TECH_COST_CLASSIC_PRESET: Cost are read from tech.ruleset. Missing costs
 895                             are generated by style "Classic".
 896   TECH_COST_EXPERIMENTAL: Cost of technology is:
 897                             base_tech_cost * (reqs^2
 898                                               / (1 + sqrt(sqrt(reqs + 1)))
 899                                               - 0.5)
 900                           where reqs == number of requirement for tech,
 901                           counted recursively.
 902   TECH_COST_EXPERIMENTAL_PRESET: Cost are read from tech.ruleset. Missing
 903                                  costs are generated by style "Experimental".
 904
 905   tech_leakage:
 906   TECH_LEAKAGE_NONE: No reduction of the technology cost.
 907   TECH_LEAKAGE_EMBASSIES: Technology cost is reduced depending on the number
 908                           of players which already know the tech and you have
 909                           an embassy with.
 910   TECH_LEAKAGE_PLAYERS: Technology cost is reduced depending on the number of
 911                         all players (human, AI and barbarians) which already
 912                         know the tech.
 913   TECH_LEAKAGE_NO_BARBS: Technology cost is reduced depending on the number
 914                          of normal players (human and AI) which already know
 915                          the tech.
 916
 917   At the end we multiply by the sciencebox value, as a percentage.  The
 918   cost can never be less than 1.
 919
 920   'presearch' may be NULL in which case a simplified result is returned
 921   (used by client and manual code).
 922 ****************************************************************************/
 923 int research_total_bulbs_required(const struct research *presearch,
 924                                   Tech_type_id tech, bool loss_value)
 925 {
 926   enum tech_cost_style tech_cost_style = game.info.tech_cost_style;
 927   int members;
 928   double base_cost, total_cost;
 929
 930   if (!loss_value
 931       && NULL != presearch
 932       && !is_future_tech(tech)
 933       && research_invention_state(presearch, tech) == TECH_KNOWN) {
 934     /* A non-future tech which is already known costs nothing. */
 935     return 0;
 936   }
 937
 938   if (is_future_tech(tech)) {
 939     /* Future techs use style TECH_COST_CIV1CIV2. */
 940     tech_cost_style = TECH_COST_CIV1CIV2;
 941   }
 942
 943   fc_assert_msg(tech_cost_style_is_valid(tech_cost_style),
 944                 "Invalid tech_cost_style %d", tech_cost_style);
 945   base_cost = 0.0;
 946   switch (tech_cost_style) {
 947   case TECH_COST_CIV1CIV2:
 948     if (NULL != presearch) {
 949       base_cost = game.info.base_tech_cost * presearch->techs_researched;
 950       break;
 951     }
 952
 953   case TECH_COST_CLASSIC:
 954   case TECH_COST_CLASSIC_PRESET:
 955   case TECH_COST_EXPERIMENTAL:
 956   case TECH_COST_EXPERIMENTAL_PRESET:
 957     {
 958       const struct advance *padvance = valid_advance_by_number(tech);
 959
 960       if (NULL != padvance) {
 961         base_cost = padvance->cost;
 962       } else {
 963         fc_assert(NULL != padvance); /* Always fails. */
 964       }
 965     }
 966     break;
 967   }
 968
 969   total_cost = 0.0;
 970   members = 0;
 971   research_players_iterate(presearch, pplayer) {
 972     members++;
 973     total_cost += (base_cost
 974                    * get_player_bonus(pplayer, EFT_TECH_COST_FACTOR));
 975   } research_players_iterate_end;
 976   if (0 == members) {
 977     /* There is no more alive players for this research, no need to apply
 978      * complicated modifiers. */
 979     return base_cost * (double) game.info.sciencebox / 100.0;
 980   }
 981   base_cost = total_cost / members;
 982
 983   fc_assert_msg(tech_leakage_style_is_valid(game.info.tech_leakage),
 984                 "Invalid tech_leakage %d", game.info.tech_leakage);
 985   switch (game.info.tech_leakage) {
 986   case TECH_LEAKAGE_NONE:
 987     /* no change */
 988     break;
 989
 990   case TECH_LEAKAGE_EMBASSIES:
 991     {
 992       int players = 0, players_with_tech_and_embassy = 0;
 993
 994       players_iterate_alive(aplayer) {
 995         const struct research *aresearch = research_get(aplayer);
 996
 997         players++;
 998         if (aresearch == presearch
 999             || (A_FUTURE == tech
1000                 ? aresearch->future_tech <= presearch->future_tech
1001                 : TECH_KNOWN != research_invention_state(aresearch, tech))) {
1002           continue;
1003         }
1004
1005         research_players_iterate(presearch, pplayer) {
1006           if (player_has_embassy(pplayer, aplayer)) {
1007             players_with_tech_and_embassy++;
1008             break;
1009           }
1010         } research_players_iterate_end;
1011       } players_iterate_alive_end;
1012
1013       fc_assert_ret_val(0 < players, base_cost);
1014       fc_assert(players >= players_with_tech_and_embassy);
1015       base_cost *= (double) (players - players_with_tech_and_embassy);
1016       base_cost /= (double) players;
1017     }
1018     break;
1019
1020   case TECH_LEAKAGE_PLAYERS:
1021     {
1022       int players = 0, players_with_tech = 0;
1023
1024       players_iterate_alive(aplayer) {
1025         players++;
1026         if (A_FUTURE == tech
1027             ? research_get(aplayer)->future_tech > presearch->future_tech
1028             : TECH_KNOWN == research_invention_state(research_get(aplayer),
1029                                                      tech)) {
1030           players_with_tech++;
1031         }
1032       } players_iterate_alive_end;
1033
1034       fc_assert_ret_val(0 < players, base_cost);
1035       fc_assert(players >= players_with_tech);
1036       base_cost *= (double) (players - players_with_tech);
1037       base_cost /= (double) players;
1038     }
1039     break;
1040
1041   case TECH_LEAKAGE_NO_BARBS:
1042     {
1043       int players = 0, players_with_tech = 0;
1044
1045       players_iterate_alive(aplayer) {
1046         if (is_barbarian(aplayer)) {
1047           continue;
1048         }
1049         players++;
1050         if (A_FUTURE == tech
1051             ? research_get(aplayer)->future_tech > presearch->future_tech
1052             : TECH_KNOWN == research_invention_state(research_get(aplayer),
1053                                                      tech)) {
1054           players_with_tech++;
1055         }
1056       } players_iterate_alive_end;
1057
1058       fc_assert_ret_val(0 < players, base_cost);
1059       fc_assert(players >= players_with_tech);
1060       base_cost *= (double) (players - players_with_tech);
1061       base_cost /= (double) players;
1062     }
1063     break;
1064   }
1065
1066   /* Assign a science penalty to the AI at easier skill levels. This code
1067    * can also be adopted to create an extra-hard AI skill level where the AI
1068    * gets science benefits. */
1069
1070   total_cost = 0.0;
1071   research_players_iterate(presearch, pplayer) {
1072     if (is_ai(pplayer)) {
1073       fc_assert(0 < pplayer->ai_common.science_cost);
1074       total_cost += base_cost * pplayer->ai_common.science_cost / 100.0;
1075     } else {
1076       total_cost += base_cost;
1077     }
1078   } research_players_iterate_end;
1079   base_cost = total_cost / members;
1080
1081   base_cost *= (double) game.info.sciencebox / 100.0;
1082
1083   return MAX(base_cost, 1);
1084 }
1085
1086
1087 /****************************************************************************
1088   Calculate the bulb upkeep needed for all techs of a player. See also
1089   research_total_bulbs_required().
1090 ****************************************************************************/
1091 int player_tech_upkeep(const struct player *pplayer)
1092 {
1093   const struct research *presearch = research_get(pplayer);
1094   int f = presearch->future_tech, t = presearch->techs_researched;
1095   double tech_upkeep = 0.0;
1096   double total_research_factor;
1097   int members;
1098
1099   if (TECH_UPKEEP_NONE == game.info.tech_upkeep_style) {
1100     return 0;
1101   }
1102
1103   total_research_factor = 0.0;
1104   members = 0;
1105   research_players_iterate(presearch, contributor) {
1106     total_research_factor += (get_player_bonus(contributor, EFT_TECH_COST_FACTOR)
1107                               + (is_ai(contributor)
1108                                  ? contributor->ai_common.science_cost / 100.0
1109                                  : 1));
1110     members++;
1111   } research_players_iterate_end;
1112   if (0 == members) {
1113     /* No player still alive. */
1114     return 0;
1115   }
1116
1117   /* Upkeep cost for 'normal' techs (t). */
1118   fc_assert_msg(tech_cost_style_is_valid(game.info.tech_cost_style),
1119                 "Invalid tech_cost_style %d", game.info.tech_cost_style);
1120   switch (game.info.tech_cost_style) {
1121   case TECH_COST_CIV1CIV2:
1122     /* sum_1^t x = t * (t + 1) / 2 */
1123     tech_upkeep += game.info.base_tech_cost * t * (t + 1) / 2;
1124     break;
1125   case TECH_COST_CLASSIC:
1126   case TECH_COST_CLASSIC_PRESET:
1127   case TECH_COST_EXPERIMENTAL:
1128   case TECH_COST_EXPERIMENTAL_PRESET:
1129     advance_iterate(A_FIRST, padvance) {
1130       if (TECH_KNOWN == research_invention_state(presearch,
1131                                                  advance_number(padvance))) {
1132         tech_upkeep += padvance->cost;
1133       }
1134     } advance_iterate_end;
1135     if (0 < f) {
1136       /* Upkeep cost for future techs (f) are calculated using style 0:
1137        * sum_t^(t+f) x = (f * (2 * t + f + 1) + 2 * t) / 2 */
1138       tech_upkeep += (double) (game.info.base_tech_cost
1139                                * (f * (2 * t + f + 1) + 2 * t) / 2);
1140     }
1141     break;
1142   }
1143
1144   tech_upkeep *= total_research_factor / members;
1145   tech_upkeep *= (double) game.info.sciencebox / 100.0;
1146   /* We only want to calculate the upkeep part of one player, not the
1147    * whole team! */
1148   tech_upkeep /= members;
1149   tech_upkeep /= game.info.tech_upkeep_divider;
1150
1151   switch (game.info.tech_upkeep_style) {
1152   case TECH_UPKEEP_BASIC:
1153     tech_upkeep -= get_player_bonus(pplayer, EFT_TECH_UPKEEP_FREE);
1154     break;
1155   case TECH_UPKEEP_PER_CITY:
1156     tech_upkeep -= get_player_bonus(pplayer, EFT_TECH_UPKEEP_FREE);
1157     tech_upkeep *= city_list_size(pplayer->cities);
1158     break;
1159   case TECH_UPKEEP_NONE:
1160     fc_assert(game.info.tech_upkeep_style != TECH_UPKEEP_NONE);
1161     tech_upkeep = 0.0;
1162   }
1163
1164   if (0.0 > tech_upkeep) {
1165     tech_upkeep = 0.0;
1166   }
1167
1168   log_debug("[%s (%d)] tech upkeep: %d", player_name(pplayer),
1169             player_number(pplayer), (int) tech_upkeep);
1170   return (int) tech_upkeep;
1171 }
1172
1173
1174 /****************************************************************************
1175   Returns the real size of the player research iterator.
1176 ****************************************************************************/
1177 size_t research_iter_sizeof(void)
1178 {
1179   return sizeof(struct research_iter);
1180 }
1181
1182 /****************************************************************************
1183   Returns the research structure pointed by the iterator.
1184 ****************************************************************************/
1185 static void *research_iter_get(const struct iterator *it)
1186 {
1187   return &research_array[RESEARCH_ITER(it)->index];
1188 }
1189
1190 /****************************************************************************
1191   Jump to next team research structure.
1192 ****************************************************************************/
1193 static void research_iter_team_next(struct iterator *it)
1194 {
1195   struct research_iter *rit = RESEARCH_ITER(it);
1196
1197   if (team_slots_initialised()) {
1198     do {
1199       rit->index++;
1200     } while (rit->index < ARRAY_SIZE(research_array) && !it->valid(it));
1201   }
1202 }
1203
1204 /****************************************************************************
1205   Returns FALSE if there is no valid team at current index.
1206 ****************************************************************************/
1207 static bool research_iter_team_valid(const struct iterator *it)
1208 {
1209   struct research_iter *rit = RESEARCH_ITER(it);
1210
1211   return (0 <= rit->index
1212           && ARRAY_SIZE(research_array) > rit->index
1213           && NULL != team_by_number(rit->index));
1214 }
1215
1216 /****************************************************************************
1217   Jump to next player research structure.
1218 ****************************************************************************/
1219 static void research_iter_player_next(struct iterator *it)
1220 {
1221   struct research_iter *rit = RESEARCH_ITER(it);
1222
1223   if (player_slots_initialised()) {
1224     do {
1225       rit->index++;
1226     } while (rit->index < ARRAY_SIZE(research_array) && !it->valid(it));
1227   }
1228 }
1229
1230 /****************************************************************************
1231   Returns FALSE if there is no valid player at current index.
1232 ****************************************************************************/
1233 static bool research_iter_player_valid(const struct iterator *it)
1234 {
1235   struct research_iter *rit = RESEARCH_ITER(it);
1236
1237   return (0 <= rit->index
1238           && ARRAY_SIZE(research_array) > rit->index
1239           && NULL != player_by_number(rit->index));
1240 }
1241
1242 /****************************************************************************
1243   Initializes a player research iterator.
1244 ****************************************************************************/
1245 struct iterator *research_iter_init(struct research_iter *it)
1246 {
1247   struct iterator *base = ITERATOR(it);
1248
1249   base->get = research_iter_get;
1250   it->index = -1;
1251
1252   if (game.info.team_pooled_research) {
1253     base->next = research_iter_team_next;
1254     base->valid = research_iter_team_valid;
1255   } else {
1256     base->next = research_iter_player_next;
1257     base->valid = research_iter_player_valid;
1258   }
1259
1260   base->next(base);
1261   return base;
1262 }
1263
1264 /****************************************************************************
1265   Returns the real size of the research player iterator.
1266 ****************************************************************************/
1267 size_t research_player_iter_sizeof(void)
1268 {
1269   return sizeof(struct research_player_iter);
1270 }
1271
1272 /****************************************************************************
1273   Returns whether the iterator is currently at a valid state.
1274 ****************************************************************************/
1275 static inline bool research_player_iter_valid_state(struct iterator *it)
1276 {
1277   const struct player *pplayer = iterator_get(it);
1278
1279   return (NULL == pplayer || pplayer->is_alive);
1280 }
1281
1282 /****************************************************************************
1283   Returns player of the iterator.
1284 ****************************************************************************/
1285 static void *research_player_iter_pooled_get(const struct iterator *it)
1286 {
1287   return player_list_link_data(RESEARCH_PLAYER_ITER(it)->plink);
1288 }
1289
1290 /****************************************************************************
1291   Returns the next player sharing the research.
1292 ****************************************************************************/
1293 static void research_player_iter_pooled_next(struct iterator *it)
1294 {
1295   struct research_player_iter *rpit = RESEARCH_PLAYER_ITER(it);
1296
1297   do {
1298     rpit->plink = player_list_link_next(rpit->plink);
1299   } while (!research_player_iter_valid_state(it));
1300 }
1301
1302 /****************************************************************************
1303   Returns whether the iterate is valid.
1304 ****************************************************************************/
1305 static bool research_player_iter_pooled_valid(const struct iterator *it)
1306 {
1307   return NULL != RESEARCH_PLAYER_ITER(it)->plink;
1308 }
1309
1310 /****************************************************************************
1311   Returns player of the iterator.
1312 ****************************************************************************/
1313 static void *research_player_iter_not_pooled_get(const struct iterator *it)
1314 {
1315   return RESEARCH_PLAYER_ITER(it)->pplayer;
1316 }
1317
1318 /****************************************************************************
1319   Invalidate the iterator.
1320 ****************************************************************************/
1321 static void research_player_iter_not_pooled_next(struct iterator *it)
1322 {
1323   RESEARCH_PLAYER_ITER(it)->pplayer = NULL;
1324 }
1325
1326 /****************************************************************************
1327   Returns whether the iterate is valid.
1328 ****************************************************************************/
1329 static bool research_player_iter_not_pooled_valid(const struct iterator *it)
1330 {
1331   return NULL != RESEARCH_PLAYER_ITER(it)->pplayer;
1332 }
1333
1334 /****************************************************************************
1335   Initializes a research player iterator.
1336 ****************************************************************************/
1337 struct iterator *research_player_iter_init(struct research_player_iter *it,
1338                                            const struct research *presearch)
1339 {
1340   struct iterator *base = ITERATOR(it);
1341
1342   if (game.info.team_pooled_research && NULL != presearch) {
1343     base->get = research_player_iter_pooled_get;
1344     base->next = research_player_iter_pooled_next;
1345     base->valid = research_player_iter_pooled_valid;
1346     it->plink = player_list_head(team_members(team_by_number(research_number
1347                                                              (presearch))));
1348   } else {
1349     base->get = research_player_iter_not_pooled_get;
1350     base->next = research_player_iter_not_pooled_next;
1351     base->valid = research_player_iter_not_pooled_valid;
1352     it->pplayer = (NULL != presearch
1353                    ? player_by_number(research_number(presearch)) : NULL);
1354   }
1355
1356   /* Ensure we have consistent data. */
1357   if (!research_player_iter_valid_state(base)) {
1358     iterator_next(base);
1359   }
1360
1361   return base;
1362 }