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 given tech is ever reachable by the players sharing
 294   the research by checking tech tree limitations.
 295
 296   Helper for research_update().
 297 ****************************************************************************/
 298 static bool research_get_reachable(const struct research *presearch,
 299                                    Tech_type_id tech)
 300 {
 301   if (valid_advance_by_number(tech) == NULL) {
 302     return FALSE;
 303   } else if (advance_required(tech, AR_ROOT) != A_NONE) {
 304     /* 'tech' has at least one root requirement. We need to check them
 305      * all. */
 306     bv_techs done;
 307     Tech_type_id techs[game.control.num_tech_types];
 308     enum tech_req req;
 309     int techs_num;
 310     int i;
 311
 312     techs[0] = tech;
 313     BV_CLR_ALL(done);
 314     BV_SET(done, A_NONE);
 315     BV_SET(done, tech);
 316     techs_num = 1;
 317
 318     for (i = 0; i < techs_num; i++) {
 319       if (advance_required(techs[i], AR_ROOT) == techs[i]) {
 320         /* This tech requires itself; it can only be reached by special
 321          * means (init_techs, lua script, ...).
 322          * If you already know it, you can "reach" it; if not, not. (This
 323          * case is needed for descendants of this tech.) */
 324         if (presearch->inventions[techs[i]].state != TECH_KNOWN) {
 325           return FALSE;
 326         }
 327       } else {
 328         /* Check if requirements are reachable. */
 329         Tech_type_id req_tech;
 330
 331         for (req = 0; req < AR_SIZE; req++) {
 332           req_tech = advance_required(techs[i], req);
 333           if (valid_advance_by_number(req_tech) == NULL) {
 334             return FALSE;
 335           } else if (!BV_ISSET(done, req_tech)) {
 336             if (advance_required(req_tech, AR_ROOT) != A_NONE) {
 337               fc_assert(techs_num < ARRAY_SIZE(techs));
 338               techs[techs_num] = req_tech;
 339               techs_num++;
 340             }
 341             BV_SET(done, req_tech);
 342           }
 343         }
 344       }
 345     }
 346   }
 347
 348   return TRUE;
 349 }
 350
 351 /****************************************************************************
 352   Returns TRUE iff the players sharing 'presearch' already have got the
 353   knowledge of all root requirement technologies.
 354
 355   Helper for research_update().
 356 ****************************************************************************/
 357 static bool research_get_root_reqs_known(const struct research *presearch,
 358                                          Tech_type_id tech)
 359 {
 360   if (advance_required(tech, AR_ROOT) != A_NONE) {
 361     /* 'padvance' has got at least one root requirement. We need to check
 362      * if all of them are known. */
 363     bv_techs done;
 364     Tech_type_id techs[game.control.num_tech_types];
 365     Tech_type_id root;
 366     int techs_num;
 367     int i;
 368
 369     techs[0] = tech;
 370     BV_CLR_ALL(done);
 371     BV_SET(done, A_NONE);
 372     BV_SET(done, tech);
 373     techs_num = 1;
 374
 375     for (i = 0; i < techs_num; i++) {
 376       root = advance_required(techs[i], AR_ROOT);
 377       if (presearch->inventions[root].state != TECH_KNOWN) {
 378         return FALSE;
 379       } else {
 380         /* Check if requirement roots are also known. */
 381         enum tech_req req;
 382         Tech_type_id req_tech;
 383
 384         for (req = 0; req <= AR_TWO; req++) {
 385           req_tech = advance_required(techs[i], req);
 386           if (!BV_ISSET(done, req_tech)) {
 387             if (advance_required(req_tech, AR_ROOT) != A_NONE) {
 388               fc_assert(techs_num < ARRAY_SIZE(techs));
 389               techs[techs_num] = req_tech;
 390               techs_num++;
 391             }
 392             BV_SET(done, req_tech);
 393           }
 394         }
 395       }
 396     }
 397   }
 398
 399   return TRUE;
 400 }
 401
 402 /****************************************************************************
 403   Mark as TECH_PREREQS_KNOWN each tech which is available, not known and
 404   which has all requirements fullfiled.
 405
 406   Recalculate presearch->num_known_tech_with_flag
 407   Should always be called after research_invention_set().
 408 ****************************************************************************/
 409 void research_update(struct research *presearch)
 410 {
 411   enum tech_flag_id flag;
 412   int techs_researched;
 413
 414   advance_index_iterate(A_FIRST, i) {
 415     enum tech_state state = presearch->inventions[i].state;
 416     bool root_reqs_known = TRUE;
 417     bool reachable = research_get_reachable(presearch, i);
 418
 419     if (reachable) {
 420       root_reqs_known = research_get_root_reqs_known(presearch, i);
 421       if (state != TECH_KNOWN) {
 422         /* Update state. */
 423         state = (root_reqs_known
 424                  && (presearch->inventions[advance_required(i, AR_ONE)].state
 425                      == TECH_KNOWN)
 426                  && (presearch->inventions[advance_required(i, AR_TWO)].state
 427                      == TECH_KNOWN)
 428                  ? TECH_PREREQS_KNOWN : TECH_UNKNOWN);
 429       }
 430     } else {
 431       fc_assert(state == TECH_UNKNOWN);
 432       root_reqs_known = FALSE;
 433     }
 434     presearch->inventions[i].state = state;
 435     presearch->inventions[i].reachable = reachable;
 436     presearch->inventions[i].root_reqs_known = root_reqs_known;
 437
 438     /* Updates required_techs, num_required_techs and bulbs_required. */
 439     BV_CLR_ALL(presearch->inventions[i].required_techs);
 440     presearch->inventions[i].num_required_techs = 0;
 441     presearch->inventions[i].bulbs_required = 0;
 442
 443     if (!reachable || state == TECH_KNOWN) {
 444       continue;
 445     }
 446
 447     techs_researched = presearch->techs_researched;
 448     advance_req_iterate(valid_advance_by_number(i), preq) {
 449       Tech_type_id j = advance_number(preq);
 450
 451       if (TECH_KNOWN == research_invention_state(presearch, j)) {
 452         continue;
 453       }
 454
 455       BV_SET(presearch->inventions[i].required_techs, j);
 456       presearch->inventions[i].num_required_techs++;
 457       presearch->inventions[i].bulbs_required +=
 458           research_total_bulbs_required(presearch, j, FALSE);
 459       /* This is needed to get a correct result for the
 460        * research_total_bulbs_required() call when
 461        * game.info.game.info.tech_cost_style is TECH_COST_CIV1CIV2. */
 462       presearch->techs_researched++;
 463     } advance_req_iterate_end;
 464     presearch->techs_researched = techs_researched;
 465   } advance_index_iterate_end;
 466
 467 #ifdef FREECIV_DEBUG
 468   advance_index_iterate(A_FIRST, i) {
 469     char buf[advance_count() + 1];
 470
 471     advance_index_iterate(A_NONE, j) {
 472       if (BV_ISSET(presearch->inventions[i].required_techs, j)) {
 473         buf[j] = '1';
 474       } else {
 475         buf[j] = '0';
 476       }
 477     } advance_index_iterate_end;
 478     buf[advance_count()] = '\0';
 479
 480     log_debug("%s: [%3d] %-25s => %s%s%s",
 481               research_rule_name(presearch),
 482               i,
 483               advance_rule_name(advance_by_number(i)),
 484               tech_state_name(research_invention_state(presearch, i)),
 485               presearch->inventions[i].reachable ? "" : " [unrechable]",
 486               presearch->inventions[i].root_reqs_known
 487               ? "" : " [root reqs aren't known]");
 488     log_debug("%s: [%3d] %s", research_rule_name(presearch), i, buf);
 489   } advance_index_iterate_end;
 490 #endif /* FREECIV_DEBUG */
 491
 492   for (flag = 0; flag <= tech_flag_id_max(); flag++) {
 493     /* Iterate over all possible tech flags (0..max). */
 494     presearch->num_known_tech_with_flag[flag] = 0;
 495
 496     advance_index_iterate(A_NONE, i) {
 497       if (TECH_KNOWN == research_invention_state(presearch, i)
 498           && advance_has_flag(i, flag)) {
 499         presearch->num_known_tech_with_flag[flag]++;
 500       }
 501     } advance_index_iterate_end;
 502   }
 503 }
 504
 505 /****************************************************************************
 506   Returns state of the tech for current research.
 507   This can be: TECH_KNOWN, TECH_UNKNOWN, or TECH_PREREQS_KNOWN
 508   Should be called with existing techs.
 509
 510   If 'presearch' is NULL this checks whether any player knows the tech
 511   (used by the client).
 512 ****************************************************************************/
 513 enum tech_state research_invention_state(const struct research *presearch,
 514                                          Tech_type_id tech)
 515 {
 516   fc_assert_ret_val(NULL != valid_advance_by_number(tech), -1);
 517
 518   if (NULL != presearch) {
 519     return presearch->inventions[tech].state;
 520   } else if (game.info.global_advances[tech]) {
 521     return TECH_KNOWN;
 522   } else {
 523     return TECH_UNKNOWN;
 524   }
 525 }
 526
 527 /****************************************************************************
 528   Set research knowledge about tech to given state.
 529 ****************************************************************************/
 530 enum tech_state research_invention_set(struct research *presearch,
 531                                        Tech_type_id tech,
 532                                        enum tech_state value)
 533 {
 534   enum tech_state old;
 535
 536   fc_assert_ret_val(NULL != valid_advance_by_number(tech), -1);
 537
 538   old = presearch->inventions[tech].state;
 539   if (old == value) {
 540     return old;
 541   }
 542   presearch->inventions[tech].state = value;
 543
 544   if (value == TECH_KNOWN) {
 545     game.info.global_advances[tech] = TRUE;
 546   }
 547   return old;
 548 }
 549
 550 /****************************************************************************
 551   Returns TRUE iff the given tech is ever reachable by the players sharing
 552   the research by checking tech tree limitations.
 553
 554   'presearch' may be NULL in which case a simplified result is returned
 555   (used by the client).
 556 ****************************************************************************/
 557 bool research_invention_reachable(const struct research *presearch,
 558                                   const Tech_type_id tech)
 559 {
 560   if (valid_advance_by_number(tech) == NULL) {
 561     return FALSE;
 562   } else if (presearch != NULL) {
 563     return presearch->inventions[tech].reachable;
 564   } else {
 565     researches_iterate(research_iter) {
 566       if (research_iter->inventions[tech].reachable) {
 567         return TRUE;
 568       }
 569     } researches_iterate_end;
 570
 571     return FALSE;
 572   }
 573 }
 574
 575 /****************************************************************************
 576   Returns TRUE iff the given tech can be given to the players sharing the
 577   research immediately.
 578
 579   If allow_holes is TRUE, any reachable tech is ok. If it's FALSE,
 580   getting the tech must not leave holes to the known techs tree.
 581 ****************************************************************************/
 582 bool research_invention_gettable(const struct research *presearch,
 583                                  const Tech_type_id tech,
 584                                  bool allow_holes)
 585 {
 586   if (valid_advance_by_number(tech) == NULL) {
 587     return FALSE;
 588   } else if (presearch != NULL) {
 589     return (allow_holes
 590             ? presearch->inventions[tech].root_reqs_known
 591             : presearch->inventions[tech].state == TECH_PREREQS_KNOWN);
 592   } else {
 593     researches_iterate(research_iter) {
 594       if (allow_holes
 595           ? research_iter->inventions[tech].root_reqs_known
 596           : research_iter->inventions[tech].state == TECH_PREREQS_KNOWN) {
 597         return TRUE;
 598       }
 599     } researches_iterate_end;
 600
 601     return FALSE;
 602   }
 603 }
 604
 605 /****************************************************************************
 606   Return the next tech we should research to advance towards our goal.
 607   Returns A_UNSET if nothing is available or the goal is already known.
 608 ****************************************************************************/
 609 Tech_type_id research_goal_step(const struct research *presearch,
 610                                 Tech_type_id goal)
 611 {
 612   const struct advance *pgoal = valid_advance_by_number(goal);
 613
 614   if (NULL == pgoal
 615       || !research_invention_reachable(presearch, goal)) {
 616     return A_UNSET;
 617   }
 618
 619   advance_req_iterate(pgoal, preq) {
 620     switch (research_invention_state(presearch, advance_number(preq))) {
 621     case TECH_PREREQS_KNOWN:
 622       return advance_number(preq);
 623     case TECH_KNOWN:
 624     case TECH_UNKNOWN:
 625        break;
 626     };
 627   } advance_req_iterate_end;
 628   return A_UNSET;
 629 }
 630
 631 /****************************************************************************
 632   Returns the number of technologies the player need to research to get
 633   the goal technology. This includes the goal technology. Technologies
 634   are only counted once.
 635
 636   'presearch' may be NULL in which case it will returns the total number
 637   of technologies needed for reaching the goal.
 638 ****************************************************************************/
 639 int research_goal_unknown_techs(const struct research *presearch,
 640                                 Tech_type_id goal)
 641 {
 642   const struct advance *pgoal = valid_advance_by_number(goal);
 643
 644   if (NULL == pgoal) {
 645     return 0;
 646   } else if (NULL != presearch) {
 647     return presearch->inventions[goal].num_required_techs;
 648   } else {
 649     return pgoal->num_reqs;
 650   }
 651 }
 652
 653 /****************************************************************************
 654   Function to determine cost (in bulbs) of reaching goal technology.
 655   These costs _include_ the cost for researching the goal technology
 656   itself.
 657
 658   'presearch' may be NULL in which case it will returns the total number
 659   of bulbs needed for reaching the goal.
 660 ****************************************************************************/
 661 int research_goal_bulbs_required(const struct research *presearch,
 662                                  Tech_type_id goal)
 663 {
 664   const struct advance *pgoal = valid_advance_by_number(goal);
 665
 666   if (NULL == pgoal) {
 667     return 0;
 668   } else if (NULL != presearch) {
 669     return presearch->inventions[goal].bulbs_required;
 670   } else if (game.info.tech_cost_style == TECH_COST_CIV1CIV2) {
 671      return game.info.base_tech_cost * pgoal->num_reqs
 672             * (pgoal->num_reqs + 1) / 2;
 673   } else {
 674     int bulbs_required = 0;
 675
 676     advance_req_iterate(pgoal, preq) {
 677       bulbs_required += preq->cost;
 678     } advance_req_iterate_end;
 679     return bulbs_required;
 680   }
 681 }
 682
 683 /****************************************************************************
 684   Returns if the given tech has to be researched to reach the goal. The
 685   goal itself isn't a requirement of itself.
 686
 687   'presearch' may be NULL.
 688 ****************************************************************************/
 689 bool research_goal_tech_req(const struct research *presearch,
 690                             Tech_type_id goal, Tech_type_id tech)
 691 {
 692   const struct advance *pgoal, *ptech;
 693
 694   if (tech == goal
 695       || NULL == (pgoal = valid_advance_by_number(goal))
 696       || NULL == (ptech = valid_advance_by_number(tech))) {
 697     return FALSE;
 698   } else if (NULL != presearch) {
 699     return BV_ISSET(presearch->inventions[goal].required_techs, tech);
 700   } else {
 701     advance_req_iterate(pgoal, preq) {
 702       if (preq == ptech) {
 703         return TRUE;
 704       }
 705     } advance_req_iterate_end;
 706     return FALSE;
 707   }
 708 }
 709
 710 /****************************************************************************
 711   Function to determine cost for technology.  The equation is determined
 712   from game.info.tech_cost_style and game.info.tech_leakage.
 713
 714   tech_cost_style:
 715   TECH_COST_CIV1CIV2: Civ (I|II) style. Every new tech add base_tech_cost to
 716                       cost of next tech.
 717   TECH_COST_CLASSIC: Cost of technology is:
 718                        base_tech_cost * (1 + reqs) * sqrt(1 + reqs) / 2
 719                      where reqs == number of requirement for tech, counted
 720                      recursively.
 721   TECH_COST_CLASSIC_PRESET: Cost are read from tech.ruleset. Missing costs
 722                             are generated by style "Classic".
 723   TECH_COST_EXPERIMENTAL: Cost of technology is:
 724                             base_tech_cost * (reqs^2
 725                                               / (1 + sqrt(sqrt(reqs + 1)))
 726                                               - 0.5)
 727                           where reqs == number of requirement for tech,
 728                           counted recursively.
 729   TECH_COST_EXPERIMENTAL_PRESET: Cost are read from tech.ruleset. Missing
 730                                  costs are generated by style "Experimental".
 731
 732   tech_leakage:
 733   TECH_LEAKAGE_NONE: No reduction of the technology cost.
 734   TECH_LEAKAGE_EMBASSIES: Technology cost is reduced depending on the number
 735                           of players which already know the tech and you have
 736                           an embassy with.
 737   TECH_LEAKAGE_PLAYERS: Technology cost is reduced depending on the number of
 738                         all players (human, AI and barbarians) which already
 739                         know the tech.
 740   TECH_LEAKAGE_NO_BARBS: Technology cost is reduced depending on the number
 741                          of normal players (human and AI) which already know
 742                          the tech.
 743
 744   At the end we multiply by the sciencebox value, as a percentage.  The
 745   cost can never be less than 1.
 746
 747   'presearch' may be NULL in which case a simplified result is returned
 748   (used by client and manual code).
 749 ****************************************************************************/
 750 int research_total_bulbs_required(const struct research *presearch,
 751                                   Tech_type_id tech, bool loss_value)
 752 {
 753   enum tech_cost_style tech_cost_style = game.info.tech_cost_style;
 754   int members;
 755   double base_cost, total_cost;
 756
 757   if (!loss_value
 758       && NULL != presearch
 759       && !is_future_tech(tech)
 760       && research_invention_state(presearch, tech) == TECH_KNOWN) {
 761     /* A non-future tech which is already known costs nothing. */
 762     return 0;
 763   }
 764
 765   if (is_future_tech(tech)) {
 766     /* Future techs use style TECH_COST_CIV1CIV2. */
 767     tech_cost_style = TECH_COST_CIV1CIV2;
 768   }
 769
 770   fc_assert_msg(tech_cost_style_is_valid(tech_cost_style),
 771                 "Invalid tech_cost_style %d", tech_cost_style);
 772   base_cost = 0.0;
 773   switch (tech_cost_style) {
 774   case TECH_COST_CIV1CIV2:
 775     if (NULL != presearch) {
 776       base_cost = game.info.base_tech_cost * presearch->techs_researched;
 777       break;
 778     }
 779
 780   case TECH_COST_CLASSIC:
 781   case TECH_COST_CLASSIC_PRESET:
 782   case TECH_COST_EXPERIMENTAL:
 783   case TECH_COST_EXPERIMENTAL_PRESET:
 784     {
 785       const struct advance *padvance = valid_advance_by_number(tech);
 786
 787       if (NULL != padvance) {
 788         base_cost = padvance->cost;
 789       } else {
 790         fc_assert(NULL != padvance); /* Always fails. */
 791       }
 792     }
 793     break;
 794   }
 795
 796   total_cost = 0.0;
 797   members = 0;
 798   research_players_iterate(presearch, pplayer) {
 799     members++;
 800     total_cost += (base_cost
 801                    * get_player_bonus(pplayer, EFT_TECH_COST_FACTOR));
 802   } research_players_iterate_end;
 803   if (0 == members) {
 804     /* There is no more alive players for this research, no need to apply
 805      * complicated modifiers. */
 806     return base_cost * (double) game.info.sciencebox / 100.0;
 807   }
 808   base_cost = total_cost / members;
 809
 810   fc_assert_msg(tech_leakage_style_is_valid(game.info.tech_leakage),
 811                 "Invalid tech_leakage %d", game.info.tech_leakage);
 812   switch (game.info.tech_leakage) {
 813   case TECH_LEAKAGE_NONE:
 814     /* no change */
 815     break;
 816
 817   case TECH_LEAKAGE_EMBASSIES:
 818     {
 819       int players = 0, players_with_tech_and_embassy = 0;
 820
 821       players_iterate_alive(aplayer) {
 822         const struct research *aresearch = research_get(aplayer);
 823
 824         players++;
 825         if (aresearch == presearch
 826             || (A_FUTURE == tech
 827                 ? aresearch->future_tech <= presearch->future_tech
 828                 : TECH_KNOWN != research_invention_state(aresearch, tech))) {
 829           continue;
 830         }
 831
 832         research_players_iterate(presearch, pplayer) {
 833           if (player_has_embassy(pplayer, aplayer)) {
 834             players_with_tech_and_embassy++;
 835             break;
 836           }
 837         } research_players_iterate_end;
 838       } players_iterate_alive_end;
 839
 840       fc_assert_ret_val(0 < players, base_cost);
 841       fc_assert(players >= players_with_tech_and_embassy);
 842       base_cost *= (double) (players - players_with_tech_and_embassy);
 843       base_cost /= (double) players;
 844     }
 845     break;
 846
 847   case TECH_LEAKAGE_PLAYERS:
 848     {
 849       int players = 0, players_with_tech = 0;
 850
 851       players_iterate_alive(aplayer) {
 852         players++;
 853         if (A_FUTURE == tech
 854             ? research_get(aplayer)->future_tech > presearch->future_tech
 855             : TECH_KNOWN == research_invention_state(research_get(aplayer),
 856                                                      tech)) {
 857           players_with_tech++;
 858         }
 859       } players_iterate_alive_end;
 860
 861       fc_assert_ret_val(0 < players, base_cost);
 862       fc_assert(players >= players_with_tech);
 863       base_cost *= (double) (players - players_with_tech);
 864       base_cost /= (double) players;
 865     }
 866     break;
 867
 868   case TECH_LEAKAGE_NO_BARBS:
 869     {
 870       int players = 0, players_with_tech = 0;
 871
 872       players_iterate_alive(aplayer) {
 873         if (is_barbarian(aplayer)) {
 874           continue;
 875         }
 876         players++;
 877         if (A_FUTURE == tech
 878             ? research_get(aplayer)->future_tech > presearch->future_tech
 879             : TECH_KNOWN == research_invention_state(research_get(aplayer),
 880                                                      tech)) {
 881           players_with_tech++;
 882         }
 883       } players_iterate_alive_end;
 884
 885       fc_assert_ret_val(0 < players, base_cost);
 886       fc_assert(players >= players_with_tech);
 887       base_cost *= (double) (players - players_with_tech);
 888       base_cost /= (double) players;
 889     }
 890     break;
 891   }
 892
 893   /* Assign a science penalty to the AI at easier skill levels. This code
 894    * can also be adopted to create an extra-hard AI skill level where the AI
 895    * gets science benefits. */
 896
 897   total_cost = 0.0;
 898   research_players_iterate(presearch, pplayer) {
 899     if (pplayer->ai_controlled) {
 900       fc_assert(0 < pplayer->ai_common.science_cost);
 901       total_cost += base_cost * pplayer->ai_common.science_cost / 100.0;
 902     } else {
 903       total_cost += base_cost;
 904     }
 905   } research_players_iterate_end;
 906   base_cost = total_cost / members;
 907
 908   base_cost *= (double) game.info.sciencebox / 100.0;
 909
 910   return MAX(base_cost, 1);
 911 }
 912
 913
 914 /****************************************************************************
 915   Calculate the bulb upkeep needed for all techs of a player. See also
 916   research_total_bulbs_required().
 917 ****************************************************************************/
 918 int player_tech_upkeep(const struct player *pplayer)
 919 {
 920   const struct research *presearch = research_get(pplayer);
 921   int f = presearch->future_tech, t = presearch->techs_researched;
 922   double tech_upkeep = 0.0;
 923   double total_research_factor;
 924   int members;
 925
 926   if (TECH_UPKEEP_NONE == game.info.tech_upkeep_style) {
 927     return 0;
 928   }
 929
 930   total_research_factor = 0.0;
 931   members = 0;
 932   research_players_iterate(presearch, contributor) {
 933     total_research_factor += (get_player_bonus(contributor, EFT_TECH_COST_FACTOR)
 934                               + (contributor->ai_controlled
 935                                  ? contributor->ai_common.science_cost / 100.0
 936                                  : 1));
 937     members++;
 938   } research_players_iterate_end;
 939   if (0 == members) {
 940     /* No player still alive. */
 941     return 0;
 942   }
 943
 944   /* Upkeep cost for 'normal' techs (t). */
 945   fc_assert_msg(tech_cost_style_is_valid(game.info.tech_cost_style),
 946                 "Invalid tech_cost_style %d", game.info.tech_cost_style);
 947   switch (game.info.tech_cost_style) {
 948   case TECH_COST_CIV1CIV2:
 949     /* sum_1^t x = t * (t + 1) / 2 */
 950     tech_upkeep += game.info.base_tech_cost * t * (t + 1) / 2;
 951     break;
 952   case TECH_COST_CLASSIC:
 953   case TECH_COST_CLASSIC_PRESET:
 954   case TECH_COST_EXPERIMENTAL:
 955   case TECH_COST_EXPERIMENTAL_PRESET:
 956     advance_iterate(A_FIRST, padvance) {
 957       if (TECH_KNOWN == research_invention_state(presearch,
 958                                                  advance_number(padvance))) {
 959         tech_upkeep += padvance->cost;
 960       }
 961     } advance_iterate_end;
 962     if (0 < f) {
 963       /* Upkeep cost for future techs (f) are calculated using style 0:
 964        * sum_t^(t+f) x = (f * (2 * t + f + 1) + 2 * t) / 2 */
 965       tech_upkeep += (double) (game.info.base_tech_cost
 966                                * (f * (2 * t + f + 1) + 2 * t) / 2);
 967     }
 968     break;
 969   }
 970
 971   tech_upkeep *= total_research_factor / members;
 972   tech_upkeep *= (double) game.info.sciencebox / 100.0;
 973   /* We only want to calculate the upkeep part of one player, not the
 974    * whole team! */
 975   tech_upkeep /= members;
 976   tech_upkeep /= game.info.tech_upkeep_divider;
 977
 978   switch (game.info.tech_upkeep_style) {
 979   case TECH_UPKEEP_BASIC:
 980     tech_upkeep -= get_player_bonus(pplayer, EFT_TECH_UPKEEP_FREE);
 981     break;
 982   case TECH_UPKEEP_PER_CITY:
 983     tech_upkeep -= get_player_bonus(pplayer, EFT_TECH_UPKEEP_FREE);
 984     tech_upkeep *= city_list_size(pplayer->cities);
 985     break;
 986   case TECH_UPKEEP_NONE:
 987     fc_assert(game.info.tech_upkeep_style != TECH_UPKEEP_NONE);
 988     tech_upkeep = 0.0;
 989   }
 990
 991   if (0.0 > tech_upkeep) {
 992     tech_upkeep = 0.0;
 993   }
 994
 995   log_debug("[%s (%d)] tech upkeep: %d", player_name(pplayer),
 996             player_number(pplayer), (int) tech_upkeep);
 997   return (int) tech_upkeep;
 998 }
 999
1000
1001 /****************************************************************************
1002   Returns the real size of the player research iterator.
1003 ****************************************************************************/
1004 size_t research_iter_sizeof(void)
1005 {
1006   return sizeof(struct research_iter);
1007 }
1008
1009 /****************************************************************************
1010   Returns the research structure pointed by the iterator.
1011 ****************************************************************************/
1012 static void *research_iter_get(const struct iterator *it)
1013 {
1014   return &research_array[RESEARCH_ITER(it)->index];
1015 }
1016
1017 /****************************************************************************
1018   Jump to next team research structure.
1019 ****************************************************************************/
1020 static void research_iter_team_next(struct iterator *it)
1021 {
1022   struct research_iter *rit = RESEARCH_ITER(it);
1023
1024   if (team_slots_initialised()) {
1025     do {
1026       rit->index++;
1027     } while (rit->index < ARRAY_SIZE(research_array) && !it->valid(it));
1028   }
1029 }
1030
1031 /****************************************************************************
1032   Returns FALSE if there is no valid team at current index.
1033 ****************************************************************************/
1034 static bool research_iter_team_valid(const struct iterator *it)
1035 {
1036   struct research_iter *rit = RESEARCH_ITER(it);
1037
1038   return (0 <= rit->index
1039           && ARRAY_SIZE(research_array) > rit->index
1040           && NULL != team_by_number(rit->index));
1041 }
1042
1043 /****************************************************************************
1044   Jump to next player research structure.
1045 ****************************************************************************/
1046 static void research_iter_player_next(struct iterator *it)
1047 {
1048   struct research_iter *rit = RESEARCH_ITER(it);
1049
1050   if (player_slots_initialised()) {
1051     do {
1052       rit->index++;
1053     } while (rit->index < ARRAY_SIZE(research_array) && !it->valid(it));
1054   }
1055 }
1056
1057 /****************************************************************************
1058   Returns FALSE if there is no valid player at current index.
1059 ****************************************************************************/
1060 static bool research_iter_player_valid(const struct iterator *it)
1061 {
1062   struct research_iter *rit = RESEARCH_ITER(it);
1063
1064   return (0 <= rit->index
1065           && ARRAY_SIZE(research_array) > rit->index
1066           && NULL != player_by_number(rit->index));
1067 }
1068
1069 /****************************************************************************
1070   Initializes a player research iterator.
1071 ****************************************************************************/
1072 struct iterator *research_iter_init(struct research_iter *it)
1073 {
1074   struct iterator *base = ITERATOR(it);
1075
1076   base->get = research_iter_get;
1077   it->index = -1;
1078
1079   if (game.info.team_pooled_research) {
1080     base->next = research_iter_team_next;
1081     base->valid = research_iter_team_valid;
1082   } else {
1083     base->next = research_iter_player_next;
1084     base->valid = research_iter_player_valid;
1085   }
1086
1087   base->next(base);
1088   return base;
1089 }
1090
1091 /****************************************************************************
1092   Returns the real size of the research player iterator.
1093 ****************************************************************************/
1094 size_t research_player_iter_sizeof(void)
1095 {
1096   return sizeof(struct research_player_iter);
1097 }
1098
1099 /****************************************************************************
1100   Returns whether the iterator is currently at a valid state.
1101 ****************************************************************************/
1102 static inline bool research_player_iter_valid_state(struct iterator *it)
1103 {
1104   const struct player *pplayer = iterator_get(it);
1105
1106   return (NULL == pplayer || pplayer->is_alive);
1107 }
1108
1109 /****************************************************************************
1110   Returns player of the iterator.
1111 ****************************************************************************/
1112 static void *research_player_iter_pooled_get(const struct iterator *it)
1113 {
1114   return player_list_link_data(RESEARCH_PLAYER_ITER(it)->plink);
1115 }
1116
1117 /****************************************************************************
1118   Returns the next player sharing the research.
1119 ****************************************************************************/
1120 static void research_player_iter_pooled_next(struct iterator *it)
1121 {
1122   struct research_player_iter *rpit = RESEARCH_PLAYER_ITER(it);
1123
1124   do {
1125     rpit->plink = player_list_link_next(rpit->plink);
1126   } while (!research_player_iter_valid_state(it));
1127 }
1128
1129 /****************************************************************************
1130   Returns whether the iterate is valid.
1131 ****************************************************************************/
1132 static bool research_player_iter_pooled_valid(const struct iterator *it)
1133 {
1134   return NULL != RESEARCH_PLAYER_ITER(it)->plink;
1135 }
1136
1137 /****************************************************************************
1138   Returns player of the iterator.
1139 ****************************************************************************/
1140 static void *research_player_iter_not_pooled_get(const struct iterator *it)
1141 {
1142   return RESEARCH_PLAYER_ITER(it)->pplayer;
1143 }
1144
1145 /****************************************************************************
1146   Invalidate the iterator.
1147 ****************************************************************************/
1148 static void research_player_iter_not_pooled_next(struct iterator *it)
1149 {
1150   RESEARCH_PLAYER_ITER(it)->pplayer = NULL;
1151 }
1152
1153 /****************************************************************************
1154   Returns whether the iterate is valid.
1155 ****************************************************************************/
1156 static bool research_player_iter_not_pooled_valid(const struct iterator *it)
1157 {
1158   return NULL != RESEARCH_PLAYER_ITER(it)->pplayer;
1159 }
1160
1161 /****************************************************************************
1162   Initializes a research player iterator.
1163 ****************************************************************************/
1164 struct iterator *research_player_iter_init(struct research_player_iter *it,
1165                                            const struct research *presearch)
1166 {
1167   struct iterator *base = ITERATOR(it);
1168
1169   if (game.info.team_pooled_research && NULL != presearch) {
1170     base->get = research_player_iter_pooled_get;
1171     base->next = research_player_iter_pooled_next;
1172     base->valid = research_player_iter_pooled_valid;
1173     it->plink = player_list_head(team_members(team_by_number(research_number
1174                                                              (presearch))));
1175   } else {
1176     base->get = research_player_iter_not_pooled_get;
1177     base->next = research_player_iter_not_pooled_next;
1178     base->valid = research_player_iter_not_pooled_valid;
1179     it->pplayer = (NULL != presearch
1180                    ? player_by_number(research_number(presearch)) : NULL);
1181   }
1182
1183   /* Ensure we have consistent data. */
1184   if (!research_player_iter_valid_state(base)) {
1185     iterator_next(base);
1186   }
1187
1188   return base;
1189 }