server/gamehand.c

   1 /***********************************************************************
   2  Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2, or (at your option)
   6    any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12 ***********************************************************************/
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <fc_config.h>
  16 #endif
  17
  18 #include <stdio.h> /* for remove() */
  19
  20 /* utility */
  21 #include "capability.h"
  22 #include "fcintl.h"
  23 #include "log.h"
  24 #include "mem.h"
  25 #include "rand.h"
  26 #include "registry.h"
  27 #include "shared.h"
  28 #include "string_vector.h"
  29 #include "support.h"
  30
  31 /* common */
  32 #include "ai.h"
  33 #include "calendar.h"
  34 #include "events.h"
  35 #include "game.h"
  36 #include "improvement.h"
  37 #include "movement.h"
  38 #include "packets.h"
  39
  40 /* server */
  41 #include "citytools.h"
  42 #include "connecthand.h"
  43 #include "maphand.h"
  44 #include "notify.h"
  45 #include "plrhand.h"
  46 #include "srv_main.h"
  47 #include "unittools.h"
  48
  49 /* server/advisors */
  50 #include "advdata.h"
  51
  52 #include "gamehand.h"
  53
  54 #define CHALLENGE_ROOT "challenge"
  55
  56 #define SPECLIST_TAG startpos
  57 #define SPECLIST_TYPE struct startpos
  58 #include "speclist.h"
  59 #define startpos_list_iterate(list, plink, psp)                             \
  60   TYPED_LIST_BOTH_ITERATE(struct startpos_list_link, struct startpos,       \
  61                           list, plink, psp)
  62 #define startpos_list_iterate_end LIST_BOTH_ITERATE_END
  63
  64 struct team_placement_config {
  65   struct tile **startpos;
  66   int flexible_startpos_num;
  67   int usable_startpos_num;
  68   int total_startpos_num;
  69 };
  70
  71 struct team_placement_state {
  72   int *startpos;
  73   long score;
  74 };
  75
  76 #define SPECPQ_TAG team_placement
  77 #define SPECPQ_DATA_TYPE struct team_placement_state *
  78 #define SPECPQ_PRIORITY_TYPE long
  79 #include "specpq.h"
  80
  81 static struct strvec *ruleset_choices = NULL;
  82
  83 /****************************************************************************
  84   Get role_id for given role character
  85 ****************************************************************************/
  86 enum unit_role_id crole_to_role_id(char crole)
  87 {
  88   switch (crole) {
  89   case 'c':
  90     return L_START_CITIES;
  91   case 'w':
  92     return L_START_WORKER;
  93   case 'x':
  94     return L_START_EXPLORER;
  95   case 'k':
  96     return L_START_KING;
  97   case 's':
  98     return L_START_DIPLOMAT;
  99   case 'f':
 100     return L_START_FERRY;
 101   case 'd':
 102     return L_START_DEFEND_OK;
 103   case 'D':
 104     return L_START_DEFEND_GOOD;
 105   case 'a':
 106     return L_START_ATTACK_FAST;
 107   case 'A':
 108     return L_START_ATTACK_STRONG;
 109   default:
 110     return 0;
 111   }
 112 }
 113
 114 /****************************************************************************
 115   Get unit_type for given role character
 116 ****************************************************************************/
 117 struct unit_type *crole_to_unit_type(char crole, struct player *pplayer)
 118 {
 119   struct unit_type *utype = NULL;
 120   enum unit_role_id role = crole_to_role_id(crole);
 121
 122   if (role == 0) {
 123     fc_assert_ret_val(FALSE, NULL);
 124     return NULL;
 125   }
 126
 127   /* Create the unit of an appropriate type, if it exists */
 128   if (num_role_units(role) > 0) {
 129     if (pplayer != NULL) {
 130       utype = first_role_unit_for_player(pplayer, role);
 131     }
 132     if (utype == NULL) {
 133       utype = get_role_unit(role, 0);
 134     }
 135   }
 136
 137   return utype;
 138 }
 139
 140 /****************************************************************************
 141   Place a starting unit for the player. Returns tile where unit was really
 142   placed.
 143 ****************************************************************************/
 144 static struct tile *place_starting_unit(struct tile *starttile,
 145                                         struct player *pplayer,
 146                                         char crole)
 147 {
 148   struct tile *ptile = NULL;
 149   struct unit_type *utype = crole_to_unit_type(crole, pplayer);
 150   bool hut_present = FALSE;
 151
 152   if (utype != NULL) {
 153     iterate_outward(&(wld.map), starttile,
 154                     wld.map.xsize + wld.map.ysize, itertile) {
 155       if (!is_non_allied_unit_tile(itertile, pplayer)
 156           && is_native_tile(utype, itertile)) {
 157         ptile = itertile;
 158         break;
 159       }
 160     } iterate_outward_end;
 161   }
 162
 163   if (ptile == NULL) {
 164     /* No place where unit may exist. */
 165     return NULL;
 166   }
 167
 168   fc_assert_ret_val(!is_non_allied_unit_tile(ptile, pplayer), NULL);
 169
 170   /* For scenarios or dispersion, huts may coincide with player starts (in
 171    * other cases, huts are avoided as start positions).  Remove any such hut,
 172    * and make sure to tell the client, since we may have already sent this
 173    * tile (with the hut) earlier: */
 174   extra_type_by_cause_iterate(EC_HUT, pextra) {
 175     if (tile_has_extra(ptile, pextra)) {
 176       tile_extra_rm_apply(ptile, pextra);
 177       hut_present = TRUE;
 178     }
 179   } extra_type_by_cause_iterate_end;
 180
 181   if (hut_present) {
 182     update_tile_knowledge(ptile);
 183     log_verbose("Removed hut on start position for %s",
 184                 player_name(pplayer));
 185   }
 186
 187   /* Expose visible area. */
 188   map_show_circle(pplayer, ptile, game.server.init_vis_radius_sq);
 189
 190   if (utype != NULL) {
 191     (void) create_unit(pplayer, ptile, utype, FALSE, 0, 0);
 192     return ptile;
 193   }
 194
 195   return NULL;
 196 }
 197
 198 /****************************************************************************
 199   Find a valid position not far from our starting position.
 200 ****************************************************************************/
 201 static struct tile *find_dispersed_position(struct player *pplayer,
 202                                             struct tile *pcenter)
 203 {
 204   struct tile *ptile;
 205   int x, y;
 206
 207   do {
 208     index_to_map_pos(&x, &y, tile_index(pcenter));
 209     x += fc_rand(2 * game.server.dispersion + 1) - game.server.dispersion;
 210     y += fc_rand(2 * game.server.dispersion + 1) - game.server.dispersion;
 211   } while (!((ptile = map_pos_to_tile(&(wld.map), x, y))
 212              && tile_continent(pcenter) == tile_continent(ptile)
 213              && !is_ocean_tile(ptile)
 214              && !is_non_allied_unit_tile(ptile, pplayer)));
 215
 216   return ptile;
 217 }
 218
 219 /* Calculate the distance between tiles, according to the 'teamplacement'
 220  * setting set to 'CLOSEST'. */
 221 #define team_placement_closest sq_map_distance
 222
 223 /****************************************************************************
 224   Calculate the distance between tiles, according to the 'teamplacement'
 225   setting set to 'CONTINENT'.
 226 ****************************************************************************/
 227 static int team_placement_continent(const struct tile *ptile1,
 228                                     const struct tile *ptile2)
 229 {
 230   return (ptile1->continent == ptile2->continent
 231           ? sq_map_distance(ptile1, ptile2)
 232           : sq_map_distance(ptile1, ptile2) + MAP_INDEX_SIZE);
 233 }
 234
 235 /****************************************************************************
 236   Calculate the distance between tiles, according to the 'teamplacement'
 237   setting set to 'HORIZONTAL'.
 238 ****************************************************************************/
 239 static int team_placement_horizontal(const struct tile *ptile1,
 240                                      const struct tile *ptile2)
 241 {
 242   int dx, dy;
 243
 244   map_distance_vector(&dx, &dy, ptile1, ptile2);
 245   /* Map vector to natural vector (Y axis). */
 246   return abs(MAP_IS_ISOMETRIC ? dx + dy : dy);
 247 }
 248
 249 /****************************************************************************
 250   Calculate the distance between tiles, according to the 'teamplacement'
 251   setting set to 'VERTICAL'.
 252 ****************************************************************************/
 253 static int team_placement_vertical(const struct tile *ptile1,
 254                                    const struct tile *ptile2)
 255 {
 256   int dx, dy;
 257
 258   map_distance_vector(&dx, &dy, ptile1, ptile2);
 259   /* Map vector to natural vector (X axis). */
 260   return abs(MAP_IS_ISOMETRIC ? dx - dy : dy);
 261 }
 262
 263 /****************************************************************************
 264   Destroys a team_placement_state structure.
 265 ****************************************************************************/
 266 static void team_placement_state_destroy(struct team_placement_state *pstate)
 267 {
 268   free(pstate->startpos);
 269   free(pstate);
 270 }
 271
 272 /****************************************************************************
 273   Find the best team placement, according to the 'team_placement' setting.
 274 ****************************************************************************/
 275 static void do_team_placement(const struct team_placement_config *pconfig,
 276                               struct team_placement_state *pbest_state,
 277                               int iter_max)
 278 {
 279   const size_t state_array_size = (sizeof(*pbest_state->startpos)
 280                                    * pconfig->total_startpos_num);
 281   struct team_placement_pq *pqueue =
 282       team_placement_pq_new(pconfig->total_startpos_num * 4);
 283   int (*distance)(const struct tile *, const struct tile *) = NULL;
 284   struct team_placement_state *pstate, *pnew;
 285   const struct tile *ptile1, *ptile2;
 286   long base_delta, delta;
 287   bool base_delta_calculated;
 288   int iter = 0;
 289   bool repeat;
 290   int i, j, k, t1, t2;
 291
 292   switch (wld.map.server.team_placement) {
 293   case TEAM_PLACEMENT_CLOSEST:
 294     distance = team_placement_closest;
 295     break;
 296   case TEAM_PLACEMENT_CONTINENT:
 297     distance = team_placement_continent;
 298     break;
 299   case TEAM_PLACEMENT_HORIZONTAL:
 300     distance = team_placement_horizontal;
 301     break;
 302   case TEAM_PLACEMENT_VERTICAL:
 303     distance = team_placement_vertical;
 304     break;
 305   case TEAM_PLACEMENT_DISABLED:
 306     break;
 307   }
 308   fc_assert_ret_msg(distance != NULL, "Wrong team_placement variant (%d)",
 309                     wld.map.server.team_placement);
 310
 311   /* Initialize starting state. */
 312   pstate = fc_malloc(sizeof(*pstate));
 313   pstate->startpos = fc_malloc(state_array_size);
 314   memcpy(pstate->startpos, pbest_state->startpos, state_array_size);
 315   pstate->score = pbest_state->score;
 316
 317   do {
 318     repeat = FALSE;
 319     for (i = 0; i < pconfig->usable_startpos_num; i++) {
 320       t1 = pstate->startpos[i];
 321       if (t1 == -1) {
 322         continue; /* Not used. */
 323       }
 324       ptile1 = pconfig->startpos[i];
 325       base_delta_calculated = FALSE;
 326       for (j = i + 1; j < (i >= pconfig->flexible_startpos_num
 327                            ? pconfig->usable_startpos_num
 328                            : pconfig->flexible_startpos_num); j++) {
 329         t2 = pstate->startpos[j];
 330         if (t2 == -1) {
 331           /* Not assigned yet. */
 332           ptile2 = pconfig->startpos[j];
 333           if (base_delta_calculated) {
 334             delta = base_delta;
 335             for (k = 0; k < pconfig->total_startpos_num; k++) {
 336               if (k != i && t1 == pstate->startpos[k]) {
 337                 delta += distance(ptile2, pconfig->startpos[k]);
 338               }
 339             }
 340           } else {
 341             delta = 0;
 342             base_delta = 0;
 343             for (k = 0; k < pconfig->total_startpos_num; k++) {
 344               if (k != i && t1 == pstate->startpos[k]) {
 345                 base_delta -= distance(ptile1, pconfig->startpos[k]);
 346                 delta += distance(ptile2, pconfig->startpos[k]);
 347               }
 348             }
 349             delta += base_delta;
 350             base_delta_calculated = TRUE;
 351           }
 352         } else if (t1 < t2) {
 353           ptile2 = pconfig->startpos[j];
 354           if (base_delta_calculated) {
 355             delta = base_delta;
 356             for (k = 0; k < pconfig->total_startpos_num; k++) {
 357               if (k != i && t1 == pstate->startpos[k]) {
 358                 delta += distance(ptile2, pconfig->startpos[k]);
 359               } else if (k != j && t2 == pstate->startpos[k]) {
 360                 delta -= distance(ptile2, pconfig->startpos[k]);
 361                 delta += distance(ptile1, pconfig->startpos[k]);
 362               }
 363             }
 364           } else {
 365             delta = 0;
 366             base_delta = 0;
 367             for (k = 0; k < pconfig->total_startpos_num; k++) {
 368               if (k != i && t1 == pstate->startpos[k]) {
 369                 base_delta -= distance(ptile1, pconfig->startpos[k]);
 370                 delta += distance(ptile2, pconfig->startpos[k]);
 371               } else if (k != j && t2 == pstate->startpos[k]) {
 372                 delta -= distance(ptile2, pconfig->startpos[k]);
 373                 delta += distance(ptile1, pconfig->startpos[k]);
 374               }
 375             }
 376             delta += base_delta;
 377             base_delta_calculated = TRUE;
 378           }
 379         } else {
 380           continue;
 381         }
 382
 383         if (delta <= 0) {
 384           repeat = TRUE;
 385           pnew = fc_malloc(sizeof(*pnew));
 386           pnew->startpos = fc_malloc(state_array_size);
 387           memcpy(pnew->startpos, pstate->startpos, state_array_size);
 388           pnew->startpos[i] = t2;
 389           pnew->startpos[j] = t1;
 390           pnew->score = pstate->score + delta;
 391           team_placement_pq_insert(pqueue, pnew, -pnew->score);
 392
 393           if (pnew->score < pbest_state->score) {
 394             memcpy(pbest_state->startpos, pnew->startpos, state_array_size);
 395             pbest_state->score = pnew->score;
 396           }
 397         }
 398       }
 399     }
 400
 401     team_placement_state_destroy(pstate);
 402     if (iter++ >= iter_max) {
 403       log_normal(_("Didn't find optimal solution for team placement "
 404                    "in %d iterations."), iter);
 405       break;
 406     }
 407
 408   } while (repeat && team_placement_pq_remove(pqueue, &pstate));
 409
 410   team_placement_pq_destroy_full(pqueue, team_placement_state_destroy);
 411 }
 412
 413 /****************************************************************************
 414   Initialize a new game: place the players' units onto the map, etc.
 415 ****************************************************************************/
 416 void init_new_game(void)
 417 {
 418   struct startpos_list *impossible_list, *targeted_list, *flexible_list;
 419   struct tile *player_startpos[player_slot_count()];
 420   int placed_units[player_slot_count()];
 421   int players_to_place = player_count();
 422   int sulen;
 423
 424   randomize_base64url_string(server.game_identifier,
 425                              sizeof(server.game_identifier));
 426
 427   /* Assign players to starting positions on the map.
 428    * (In scenarios with restrictions on which nations can use which predefined
 429    * start positions, this process tries to satisfy those restrictions, but
 430    * does not guarantee to. Even if there is a solution to the matching
 431    * problem, this algorithm may not find it.) */
 432
 433   fc_assert(player_count() <= map_startpos_count());
 434
 435   /* Convert the startposition hash table in a linked lists, as we mostly
 436    * need now to iterate it now. And then, we will be able to remove the
 437    * assigned start postions one by one. */
 438   impossible_list = startpos_list_new();
 439   targeted_list = startpos_list_new();
 440   flexible_list = startpos_list_new();
 441
 442   map_startpos_iterate(psp) {
 443     if (startpos_allows_all(psp)) {
 444       startpos_list_append(flexible_list, psp);
 445     } else {
 446       startpos_list_append(targeted_list, psp);
 447     }
 448   } map_startpos_iterate_end;
 449
 450   fc_assert(startpos_list_size(targeted_list)
 451             + startpos_list_size(flexible_list) == map_startpos_count());
 452
 453   memset(player_startpos, 0, sizeof(player_startpos));
 454   log_verbose("Placing players at start positions.");
 455
 456   /* First assign start positions which have restrictions on which nations
 457    * can use them. */
 458   if (0 < startpos_list_size(targeted_list)) {
 459     log_verbose("Assigning matching nations.");
 460
 461     startpos_list_shuffle(targeted_list); /* Randomize. */
 462     do {
 463       struct nation_type *pnation;
 464       struct startpos_list_link *choice;
 465       bool removed = FALSE;
 466
 467       /* Assign first players which can pick only one start position. */
 468       players_iterate(pplayer) {
 469         if (NULL != player_startpos[player_index(pplayer)]) {
 470           /* Already assigned. */
 471           continue;
 472         }
 473
 474         pnation = nation_of_player(pplayer);
 475         choice = NULL;
 476         startpos_list_iterate(targeted_list, plink, psp) {
 477           if (startpos_nation_allowed(psp, pnation)) {
 478             if (NULL != choice) {
 479               choice = NULL;
 480               break; /* Many choices. */
 481             } else {
 482               choice = plink;
 483             }
 484           }
 485         } startpos_list_iterate_end;
 486
 487         if (NULL != choice) {
 488           /* Assign this start position to this player and remove
 489            * both from consideration. */
 490           struct tile *ptile =
 491               startpos_tile(startpos_list_link_data(choice));
 492
 493           player_startpos[player_index(pplayer)] = ptile;
 494           startpos_list_erase(targeted_list, choice);
 495           players_to_place--;
 496           removed = TRUE;
 497           log_verbose("Start position (%d, %d) exactly matches player %s (%s).",
 498                       TILE_XY(ptile), player_name(pplayer),
 499                       nation_rule_name(pnation));
 500         }
 501       } players_iterate_end;
 502
 503       if (!removed) {
 504         /* Didn't find any 1:1 matches. For the next restricted start
 505          * position, assign a random matching player. (This may create
 506          * restrictions such that more 1:1 matches are possible.) */
 507         struct startpos *psp = startpos_list_back(targeted_list);
 508         struct tile *ptile = startpos_tile(psp);
 509         struct player *rand_plr = NULL;
 510         int i = 0;
 511
 512         startpos_list_pop_back(targeted_list); /* Detach 'psp'. */
 513         players_iterate(pplayer) {
 514           if (NULL != player_startpos[player_index(pplayer)]) {
 515             /* Already assigned. */
 516             continue;
 517           }
 518
 519           pnation = nation_of_player(pplayer);
 520           if (startpos_nation_allowed(psp, pnation) && 0 == fc_rand(++i)) {
 521             rand_plr = pplayer;
 522           }
 523         } players_iterate_end;
 524
 525         if (NULL != rand_plr) {
 526           player_startpos[player_index(rand_plr)] = ptile;
 527           players_to_place--;
 528           log_verbose("Start position (%d, %d) matches player %s (%s).",
 529                       TILE_XY(ptile), player_name(rand_plr),
 530                       nation_rule_name(nation_of_player(rand_plr)));
 531         } else {
 532           /* This start position cannot be assigned, given the assignments
 533            * made so far. We may have to fall back to mismatched
 534            * assignments. */
 535           log_verbose("Start position (%d, %d) cannot be assigned for "
 536                       "any player, keeping for the moment...",
 537                       TILE_XY(ptile));
 538           /* Keep it for later, we may need it. */
 539           startpos_list_append(impossible_list, psp);
 540         }
 541       }
 542     } while (0 < players_to_place && 0 < startpos_list_size(targeted_list));
 543   }
 544
 545   /* Now try to assign with regard to the 'teamplacement' setting. */
 546   if (players_to_place > 0
 547       && wld.map.server.team_placement != TEAM_PLACEMENT_DISABLED
 548       && player_count() > team_count()) {
 549     const struct player_list *members;
 550     int team_placement_players_to_place = 0;
 551     int real_team_count = 0;
 552
 553     teams_iterate(pteam) {
 554       members = team_members(pteam);
 555       fc_assert(0 < player_list_size(members));
 556       real_team_count++;
 557       if (player_list_size(members) == 1) {
 558         /* Single player teams, doesn't count for team placement. */
 559         continue;
 560       }
 561       player_list_iterate(members, pplayer) {
 562         if (player_startpos[player_index(pplayer)] == NULL) {
 563           team_placement_players_to_place++;
 564         }
 565       } player_list_iterate_end;
 566     } teams_iterate_end;
 567
 568     if (real_team_count > 1 && team_placement_players_to_place > 0) {
 569       /* We really can do something to improve team placement. */
 570       struct team_placement_config config;
 571       struct team_placement_state state;
 572       int i, j, t;
 573
 574       log_verbose("Do team placement for %d players, using %s variant.",
 575                   team_placement_players_to_place,
 576                   team_placement_name(wld.map.server.team_placement));
 577
 578       /* Initialize configuration. */
 579       config.flexible_startpos_num = startpos_list_size(flexible_list);
 580       config.usable_startpos_num = config.flexible_startpos_num;
 581       if (config.flexible_startpos_num < team_placement_players_to_place) {
 582         config.usable_startpos_num += startpos_list_size(impossible_list);
 583       }
 584       config.total_startpos_num = (config.usable_startpos_num
 585                                    + player_count() - players_to_place);
 586       config.startpos = fc_malloc(sizeof(*config.startpos)
 587                                   * config.total_startpos_num);
 588       i = 0;
 589       startpos_list_iterate(flexible_list, plink, psp) {
 590         config.startpos[i++] = startpos_tile(psp);
 591       } startpos_list_iterate_end;
 592       fc_assert(i == config.flexible_startpos_num);
 593       if (i < config.usable_startpos_num) {
 594         startpos_list_iterate(impossible_list, plink, psp) {
 595           config.startpos[i++] = startpos_tile(psp);
 596         } startpos_list_iterate_end;
 597       }
 598       fc_assert(i == config.usable_startpos_num);
 599       while (i < config.total_startpos_num) {
 600         config.startpos[i++] = NULL;
 601       }
 602       fc_assert(i == config.total_startpos_num);
 603
 604       /* Initialize state. */
 605       state.startpos = fc_malloc(sizeof(*state.startpos)
 606                                  * config.total_startpos_num);
 607       state.score = 0;
 608       i = 0;
 609       j = config.usable_startpos_num;
 610       teams_iterate(pteam) {
 611         members = team_members(pteam);
 612         if (player_list_size(members) <= 1) {
 613           /* Single player teams, doesn't count for team placement. */
 614           continue;
 615         }
 616         t = team_number(pteam);
 617         player_list_iterate(members, pplayer) {
 618           struct tile *ptile = player_startpos[player_index(pplayer)];
 619
 620           if (ptile == NULL) {
 621             state.startpos[i++] = t;
 622           } else {
 623             state.startpos[j] = t;
 624             config.startpos[j] = ptile;
 625             j++;
 626           }
 627         } player_list_iterate_end;
 628       } teams_iterate_end;
 629       while (i < config.usable_startpos_num) {
 630         state.startpos[i++] = -1;
 631       }
 632       fc_assert(i == config.usable_startpos_num);
 633       while (j < config.total_startpos_num) {
 634         state.startpos[j++] = -1;
 635       }
 636       fc_assert(j == config.total_startpos_num);
 637
 638       /* Look for best team placement. */
 639       do_team_placement(&config, &state, team_placement_players_to_place);
 640
 641       /* Apply result. */
 642       for (i = 0; i < config.usable_startpos_num; i++) {
 643         t = state.startpos[i];
 644         if (t != -1) {
 645           const struct team *pteam = team_by_number(t);
 646           int candidate_index = -1;
 647           int candidate_num = 0;
 648
 649           log_verbose("Start position (%d, %d) assigned to team %d (%s)",
 650                       TILE_XY(config.startpos[i]),
 651                       t, team_rule_name(pteam));
 652
 653           player_list_iterate(team_members(pteam), member) {
 654             if (player_startpos[player_index(member)] == NULL
 655                 && fc_rand(++candidate_num) == 0) {
 656               candidate_index = player_index(member);
 657             }
 658           } player_list_iterate_end;
 659           fc_assert(candidate_index >= 0);
 660           player_startpos[candidate_index] = config.startpos[i];
 661           team_placement_players_to_place--;
 662           players_to_place--;
 663         }
 664       }
 665       fc_assert(team_placement_players_to_place == 0);
 666
 667       /* Free data. */
 668       if (players_to_place > 0) {
 669         /* We need to remove used startpos from the lists. */
 670         i = 0;
 671         startpos_list_iterate(flexible_list, plink, psp) {
 672           fc_assert(config.startpos[i] == startpos_tile(psp));
 673           if (state.startpos[i] != -1) {
 674             startpos_list_erase(flexible_list, plink);
 675           }
 676           i++;
 677         } startpos_list_iterate_end;
 678         fc_assert(i == config.flexible_startpos_num);
 679         if (i < config.usable_startpos_num) {
 680           startpos_list_iterate(impossible_list, plink, psp) {
 681             fc_assert(config.startpos[i] == startpos_tile(psp));
 682             if (state.startpos[i] != -1) {
 683               startpos_list_erase(impossible_list, plink);
 684             }
 685             i++;
 686           } startpos_list_iterate_end;
 687         }
 688         fc_assert(i == config.usable_startpos_num);
 689       }
 690
 691       free(config.startpos);
 692     }
 693   }
 694
 695   /* Now assign unrestricted start positions to any remaining players. */
 696   if (0 < players_to_place && 0 < startpos_list_size(flexible_list)) {
 697     struct tile *ptile;
 698
 699     log_verbose("Assigning unrestricted start positions.");
 700
 701     startpos_list_shuffle(flexible_list); /* Randomize. */
 702     players_iterate(pplayer) {
 703       if (NULL != player_startpos[player_index(pplayer)]) {
 704         /* Already assigned. */
 705         continue;
 706       }
 707
 708       ptile = startpos_tile(startpos_list_front(flexible_list));
 709       player_startpos[player_index(pplayer)] = ptile;
 710       players_to_place--;
 711       startpos_list_pop_front(flexible_list);
 712       log_verbose("Start position (%d, %d) assigned randomly "
 713                   "to player %s (%s).", TILE_XY(ptile), player_name(pplayer),
 714                   nation_rule_name(nation_of_player(pplayer)));
 715       if (0 == startpos_list_size(flexible_list)) {
 716         break;
 717       }
 718     } players_iterate_end;
 719   }
 720
 721   if (0 < players_to_place && 0 < startpos_list_size(impossible_list)) {
 722     /* We still have players to place, and we have some restricted start
 723      * positions whose nation requirements can't be satisfied given existing
 724      * assignments. Fall back to making assignments ignoring the positions'
 725      * nation requirements. */
 726
 727     struct tile *ptile;
 728
 729     log_verbose("Ignoring nation restrictions on remaining start positions.");
 730
 731     startpos_list_shuffle(impossible_list); /* Randomize. */
 732     players_iterate(pplayer) {
 733       if (NULL != player_startpos[player_index(pplayer)]) {
 734         /* Already assigned. */
 735         continue;
 736       }
 737
 738       ptile = startpos_tile(startpos_list_front(impossible_list));
 739       player_startpos[player_index(pplayer)] = ptile;
 740       players_to_place--;
 741       startpos_list_pop_front(impossible_list);
 742       log_verbose("Start position (%d, %d) assigned to mismatched "
 743                   "player %s (%s).", TILE_XY(ptile), player_name(pplayer),
 744                   nation_rule_name(nation_of_player(pplayer)));
 745       if (0 == startpos_list_size(impossible_list)) {
 746         break;
 747       }
 748     } players_iterate_end;
 749   }
 750
 751   fc_assert(0 == players_to_place);
 752
 753   startpos_list_destroy(impossible_list);
 754   startpos_list_destroy(targeted_list);
 755   startpos_list_destroy(flexible_list);
 756
 757   sulen = strlen(game.server.start_units);
 758
 759   /* Loop over all players, creating their initial units... */
 760   players_iterate(pplayer) {
 761     struct tile *ptile;
 762
 763     /* We have to initialise the advisor and ai here as we could make contact
 764      * to other nations at this point. */
 765     adv_data_phase_init(pplayer, FALSE);
 766     CALL_PLR_AI_FUNC(phase_begin, pplayer, pplayer, FALSE);
 767
 768     ptile = player_startpos[player_index(pplayer)];
 769
 770     fc_assert_action(NULL != ptile, continue);
 771
 772     /* Place first city */
 773     if (game.server.start_city) {
 774       create_city(pplayer, ptile, city_name_suggestion(pplayer, ptile),
 775                   NULL);
 776     }
 777
 778     if (sulen > 0) {
 779       /* Place the first unit. */
 780       if (place_starting_unit(ptile, pplayer,
 781                               game.server.start_units[0]) != NULL) {
 782         placed_units[player_index(pplayer)] = 1;
 783       } else {
 784         placed_units[player_index(pplayer)] = 0;
 785       }
 786     } else {
 787       placed_units[player_index(pplayer)] = 0;
 788     }
 789   } players_iterate_end;
 790
 791   /* Place all other units. */
 792   players_iterate(pplayer) {
 793     int i;
 794     struct tile *const ptile = player_startpos[player_index(pplayer)];
 795     struct nation_type *nation = nation_of_player(pplayer);
 796
 797     fc_assert_action(NULL != ptile, continue);
 798
 799     /* Place global start units */
 800     for (i = 1; i < sulen; i++) {
 801       struct tile *rand_tile = find_dispersed_position(pplayer, ptile);
 802
 803       /* Create the unit of an appropriate type. */
 804       if (place_starting_unit(rand_tile, pplayer,
 805                               game.server.start_units[i]) != NULL) {
 806         placed_units[player_index(pplayer)]++;
 807       }
 808     }
 809
 810     /* Place nation specific start units (not role based!) */
 811     i = 0;
 812     while (NULL != nation->init_units[i] && MAX_NUM_UNIT_LIST > i) {
 813       struct tile *rand_tile = find_dispersed_position(pplayer, ptile);
 814
 815       create_unit(pplayer, rand_tile, nation->init_units[i], FALSE, 0, 0);
 816       placed_units[player_index(pplayer)]++;
 817       i++;
 818     }
 819   } players_iterate_end;
 820
 821   players_iterate(pplayer) {
 822     /* Close the active phase for advisor and ai for all players; it was
 823      * opened in the first loop above. */
 824     adv_data_phase_done(pplayer);
 825     CALL_PLR_AI_FUNC(phase_finished, pplayer, pplayer);
 826
 827     fc_assert_msg(game.server.start_city || 0 < placed_units[player_index(pplayer)],
 828                   _("No units placed for %s!"), player_name(pplayer));
 829   } players_iterate_end;
 830
 831   shuffle_players();
 832 }
 833
 834 /**************************************************************************
 835   Tell clients the year, and also update turn_done and nturns_idle fields
 836   for all players.
 837 **************************************************************************/
 838 void send_year_to_clients(void)
 839 {
 840   struct packet_new_year apacket;
 841
 842   players_iterate(pplayer) {
 843     pplayer->nturns_idle++;
 844   } players_iterate_end;
 845
 846   apacket.year = game.info.year;
 847   apacket.fragments = game.info.fragment_count;
 848   apacket.turn = game.info.turn;
 849   lsend_packet_new_year(game.est_connections, &apacket);
 850
 851   /* Hmm, clients could add this themselves based on above packet? */
 852   notify_conn(game.est_connections, NULL, E_NEXT_YEAR, ftc_any,
 853               _("Year: %s"), calendar_text());
 854 }
 855
 856 /**************************************************************************
 857   Send game_info packet; some server options and various stuff...
 858   dest == NULL means game.est_connections
 859
 860   It may be sent at any time. It MUST be sent before any player info,
 861   as it contains the number of players.  To avoid inconsistency, it
 862   SHOULD be sent after rulesets and any other server settings.
 863 **************************************************************************/
 864 void send_game_info(struct conn_list *dest)
 865 {
 866   struct packet_timeout_info tinfo;
 867
 868   if (!dest) {
 869     dest = game.est_connections;
 870   }
 871
 872   tinfo = game.tinfo;
 873
 874   /* the following values are computed every
 875      time a packet_game_info packet is created */
 876
 877   /* Sometimes this function is called before the phase_timer is
 878    * initialized.  In that case we want to send the dummy value. */
 879   if (current_turn_timeout() > 0 && game.server.phase_timer) {
 880     /* Whenever the client sees this packet, it starts a new timer at 0;
 881      * but the server's timer is only ever reset at the start of a phase
 882      * (and game.tinfo.seconds_to_phasedone is relative to this).
 883      * Account for the difference. */
 884     tinfo.seconds_to_phasedone = game.tinfo.seconds_to_phasedone
 885         - timer_read_seconds(game.server.phase_timer);
 886   } else {
 887     /* unused but at least initialized */
 888     tinfo.seconds_to_phasedone = -1.0;
 889   }
 890
 891   conn_list_iterate(dest, pconn) {
 892     /* Timeout info is separate from other packets since it has to
 893      * be sent always (it's not 'is-info') while the others are 'is-info'
 894      * Calendar info has been split from Game info packet to make packet
 895      * size more tolerable when json protocol is in use. */
 896     send_packet_game_info(pconn, &(game.info));
 897     send_packet_calendar_info(pconn, &(game.calendar));
 898     send_packet_timeout_info(pconn, &tinfo);
 899   }
 900   conn_list_iterate_end;
 901 }
 902
 903 /**************************************************************************
 904   Send current scenario info. dest NULL causes send to everyone
 905 **************************************************************************/
 906 void send_scenario_info(struct conn_list *dest)
 907 {
 908   if (!dest) {
 909     dest = game.est_connections;
 910   }
 911
 912   conn_list_iterate(dest, pconn) {
 913     send_packet_scenario_info(pconn, &(game.scenario));
 914   } conn_list_iterate_end;
 915 }
 916
 917 /**************************************************************************
 918   Send description of the current scenario. dest NULL causes send to everyone
 919 **************************************************************************/
 920 void send_scenario_description(struct conn_list *dest)
 921 {
 922   if (!dest) {
 923     dest = game.est_connections;
 924   }
 925
 926   conn_list_iterate(dest, pconn) {
 927     send_packet_scenario_description(pconn, &(game.scenario_desc));
 928   } conn_list_iterate_end;
 929 }
 930
 931 /**************************************************************************
 932   adjusts game.info.timeout based on various server options
 933
 934   timeoutint: adjust game.info.timeout every timeoutint turns
 935   timeoutinc: adjust game.info.timeout by adding timeoutinc to it.
 936   timeoutintinc: every time we adjust game.info.timeout, we add timeoutintinc
 937                  to timeoutint.
 938   timeoutincmult: every time we adjust game.info.timeout, we multiply timeoutinc
 939                   by timeoutincmult
 940 **************************************************************************/
 941 int update_timeout(void)
 942 {
 943   /* if there's no timer or we're doing autogame, do nothing */
 944   if (game.info.timeout < 1 || game.server.timeoutint == 0) {
 945     return game.info.timeout;
 946   }
 947
 948   if (game.server.timeoutcounter >= game.server.timeoutint) {
 949     game.info.timeout += game.server.timeoutinc;
 950     game.server.timeoutinc *= game.server.timeoutincmult;
 951
 952     game.server.timeoutcounter = 1;
 953     game.server.timeoutint += game.server.timeoutintinc;
 954
 955     if (game.info.timeout > GAME_MAX_TIMEOUT) {
 956       notify_conn(game.est_connections, NULL, E_SETTING, ftc_server,
 957                   _("The turn timeout has exceeded its maximum value, "
 958                     "fixing at its maximum."));
 959       log_debug("game.info.timeout exceeded maximum value");
 960       game.info.timeout = GAME_MAX_TIMEOUT;
 961       game.server.timeoutint = 0;
 962       game.server.timeoutinc = 0;
 963     } else if (game.info.timeout < 0) {
 964       notify_conn(game.est_connections, NULL, E_SETTING, ftc_server,
 965                   _("The turn timeout is smaller than zero, "
 966                     "fixing at zero."));
 967       log_debug("game.info.timeout less than zero");
 968       game.info.timeout = 0;
 969     }
 970   } else {
 971     game.server.timeoutcounter++;
 972   }
 973
 974   log_debug("timeout=%d, inc=%d incmult=%d\n   "
 975             "int=%d, intinc=%d, turns till next=%d",
 976             game.info.timeout, game.server.timeoutinc,
 977             game.server.timeoutincmult, game.server.timeoutint,
 978             game.server.timeoutintinc,
 979             game.server.timeoutint - game.server.timeoutcounter);
 980
 981   return game.info.timeout;
 982 }
 983
 984 /**************************************************************************
 985   adjusts game.seconds_to_turn_done when enemy moves a unit, we see it and
 986   the remaining timeout is smaller than the timeoutaddenemymove option.
 987
 988   It's possible to use a similar function to do that per-player.  In
 989   theory there should be a separate timeout for each player and the
 990   added time should only go onto the victim's timer.
 991 **************************************************************************/
 992 void increase_timeout_because_unit_moved(void)
 993 {
 994   if (current_turn_timeout() > 0 && game.server.timeoutaddenemymove > 0) {
 995     double maxsec = (timer_read_seconds(game.server.phase_timer)
 996                      + (double) game.server.timeoutaddenemymove);
 997
 998     if (maxsec > game.tinfo.seconds_to_phasedone) {
 999       game.tinfo.seconds_to_phasedone = maxsec;
1000       send_game_info(NULL);
1001     }
1002   }
1003 }
1004
1005 /**************************************************************************
1006   generate challenge filename for this connection, cannot fail.
1007 **************************************************************************/
1008 static void gen_challenge_filename(struct connection *pc)
1009 {
1010 }
1011
1012 /**************************************************************************
1013   get challenge filename for this connection.
1014 **************************************************************************/
1015 static const char *get_challenge_filename(struct connection *pc)
1016 {
1017   static char filename[MAX_LEN_PATH];
1018
1019   fc_snprintf(filename, sizeof(filename), "%s_%d_%d",
1020       CHALLENGE_ROOT, srvarg.port, pc->id);
1021
1022   return filename;
1023 }
1024
1025 /**************************************************************************
1026   get challenge full filename for this connection.
1027 **************************************************************************/
1028 static const char *get_challenge_fullname(struct connection *pc)
1029 {
1030   static char fullname[MAX_LEN_PATH];
1031   const char *sdir = freeciv_storage_dir();
1032   const char *cname;
1033
1034   if (sdir == NULL) {
1035     return NULL;
1036   }
1037
1038   cname = get_challenge_filename(pc);
1039
1040   if (cname == NULL) {
1041     return NULL;
1042   }
1043
1044   fc_snprintf(fullname, sizeof(fullname), "%s" DIR_SEPARATOR "%s", sdir, cname);
1045
1046   return fullname;
1047 }
1048
1049 /**************************************************************************
1050   find a file that we can write too, and return it's name.
1051 **************************************************************************/
1052 const char *new_challenge_filename(struct connection *pc)
1053 {
1054   gen_challenge_filename(pc);
1055   return get_challenge_filename(pc);
1056 }
1057
1058
1059 /**************************************************************************
1060   Call this on a connection with HACK access to send it a set of ruleset
1061   choices.  Probably this should be called immediately when granting
1062   HACK access to a connection.
1063 **************************************************************************/
1064 static void send_ruleset_choices(struct connection *pc)
1065 {
1066   struct packet_ruleset_choices packet;
1067   size_t i;
1068
1069   if (ruleset_choices == NULL) {
1070     /* This is only read once per server invocation.  Add a new ruleset
1071      * and you have to restart the server. */
1072     ruleset_choices = fileinfolist(get_data_dirs(), RULESET_SUFFIX);
1073   }
1074
1075   packet.ruleset_count = MIN(MAX_NUM_RULESETS, strvec_size(ruleset_choices));
1076   for (i = 0; i < packet.ruleset_count; i++) {
1077     sz_strlcpy(packet.rulesets[i], strvec_get(ruleset_choices, i));
1078   }
1079
1080   send_packet_ruleset_choices(pc, &packet);
1081 }
1082
1083 /**************************************************************************
1084   Free list of ruleset choices.
1085 **************************************************************************/
1086 void ruleset_choices_free(void)
1087 {
1088   if (ruleset_choices != NULL) {
1089     strvec_destroy(ruleset_choices);
1090     ruleset_choices = NULL;
1091   }
1092 }
1093
1094 /****************************************************************************
1095   Opens a file specified by the packet and compares the packet values with
1096   the file values. Sends an answer to the client once it's done.
1097 ****************************************************************************/
1098 void handle_single_want_hack_req(struct connection *pc,
1099                                  const struct packet_single_want_hack_req *
1100                                  packet)
1101 {
1102   struct section_file *secfile;
1103   const char *token = NULL;
1104   bool you_have_hack = FALSE;
1105
1106   if ((secfile = secfile_load(get_challenge_fullname(pc), FALSE))) {
1107     token = secfile_lookup_str(secfile, "challenge.token");
1108     you_have_hack = (token && strcmp(token, packet->token) == 0);
1109     secfile_destroy(secfile);
1110   } else {
1111     log_debug("Error reading '%s':\n%s", get_challenge_fullname(pc),
1112               secfile_error());
1113   }
1114
1115   if (!token) {
1116     log_debug("Failed to read authentication token");
1117   }
1118
1119   if (you_have_hack) {
1120     conn_set_access(pc, ALLOW_HACK, TRUE);
1121   }
1122
1123   dsend_packet_single_want_hack_reply(pc, you_have_hack);
1124
1125   send_ruleset_choices(pc);
1126   send_conn_info(pc->self, NULL);
1127 }