/********************************************************************** 
 Freeciv - Copyright (C) 2003 - The Freeciv Team
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
***********************************************************************/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>  
#include <string.h>  
#include <assert.h>

#include "city.h"
#include "game.h"
#include "government.h"
#include "map.h"
#include "mem.h"
#include "log.h"
#include "packets.h"
#include "path_finding.h"
#include "pf_tools.h"
#include "player.h"
#include "support.h" 
#include "timing.h"

#include "citytools.h"
#include "gotohand.h"
#include "maphand.h"
#include "settlers.h"
#include "unittools.h"

#include "aicity.h"
#include "aidata.h"
#include "ailog.h"
#include "aitools.h"
#include "aiunit.h"
#include "citymap.h"

#include "aisettler.h"

/* COMMENTS */
/* 
   This code tries hard to do the right thing, including looking
   into the future (wrt to government), and also doing this in a
   modpack friendly manner. However, there are some pieces missing.
    * A tighter integration into the city management code would 
   give more optimal city placements, since existing cities could
   move their workers around to give a new city better placement.
   Occasionally you will see cities being placed sub-optimally
   because the best city center tile is taken when another tile
   could have been worked instead by the city that took it.
*/

static struct {
  int sum;
  char food;
  char trade;
  char shield;
} cachemap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];

/**************************************************************************
  Fill cityresult struct with useful info about the city spot. It must 
  contain valid x, y coordinates and total should be zero.

  We assume whatever best government we are aiming for.

  We always return valid other_x and other_y if total > 0.
**************************************************************************/
static void cityresult_fill(struct player *pplayer,
                            struct ai_data *ai,
                            struct cityresult *result)
{
  struct city *pcity = map_get_city(result->x, result->y);
  struct tile *ptile = NULL;
  int sum = 0;
  bool virtual_city = FALSE;
  int curr_govt = pplayer->government;

  pplayer->government = ai->goal.govt.idx;

  result->best_other = 0;
  result->other_x = -1;
  result->other_y = -1;
  result->o_x = -1; /* as other_x but city-relative */
  result->o_y = -1;
  result->remaining = 0;

  if (!pcity) {
    pcity = create_city_virtual(pplayer, result->x, result->y, "Virtuaville");
    virtual_city = TRUE;
  }

  city_map_checked_iterate(result->x, result->y, i, j, map_x, map_y) {
    int reserved = citymap_read(map_x, map_y);
    bool city_center = is_city_center(i, j);

    ptile = map_get_tile(map_x, map_y);

    if (reserved < 0
        || (ai_handicap(pplayer, H_MAP)
            && !map_is_known(map_x, map_y, pplayer))) {
      /* Tile is reserved or we can't see it */
      sum = 0;
    } else if (cachemap[map_x][map_y].sum <= 0 || city_center) {
      /* We cannot read city center from cache */

      /* Food */
      result->tile[i][j].food = base_city_get_food_tile(i, j, pcity, FALSE);

      /* Shields */
      result->tile[i][j].shield =base_city_get_shields_tile(i, j, pcity, FALSE);

      /* Trade */
      result->tile[i][j].trade = base_city_get_trade_tile(i, j, pcity, FALSE);

      sum = result->tile[i][j].food * ai->food_priority
            + result->tile[i][j].trade * ai->science_priority
            + result->tile[i][j].shield * ai->shield_priority;
      if (!city_center) {
        /* Avoid crowdedness, except for city center. */
        sum -= reserved * ai->growth_priority;
      }
      /* Balance perfection */
      sum *= ai->perfection / 2;
      if (result->tile[i][j].food >= 2) {
        sum *= 2; /* we need this to grow */
      }

      if (!city_center) {
        cachemap[map_x][map_y].sum = sum;
        cachemap[map_x][map_y].trade = result->tile[i][j].trade;
        cachemap[map_x][map_y].shield = result->tile[i][j].shield;
        cachemap[map_x][map_y].food = result->tile[i][j].food;
      }
    } else {
      sum = cachemap[map_x][map_y].sum;
      result->tile[i][j].shield = cachemap[map_x][map_y].shield;
      result->tile[i][j].trade = cachemap[map_x][map_y].trade;
      result->tile[i][j].food = cachemap[map_x][map_y].food;
    }

    /* Calculate city center and best other than city center */
    if (city_center) {
      result->city_center = sum;
    } else if (sum > result->best_other) {
      /* First add other other to remaining */
      result->remaining += result->best_other
                           / ai->growth_potential_deemphasis;
      /* Then make new best other */
      result->best_other = sum;
      result->other_x = map_x;
      result->other_y = map_y;
      result->o_x = i;
      result->o_y = j;
    } else {
      /* Save total remaining calculation, divided by crowdedness
       * of the area and the emphasis placed on space for growth. */
      result->remaining += sum / ai->growth_potential_deemphasis;
    }
  } city_map_checked_iterate_end;

  if (virtual_city) {
    /* Baseline is a size one city (city center + best extra tile). */
    result->total = result->city_center + result->best_other;
  } else if (result->best_other != -1) {
    /* Baseline is best extra tile only. This is why making new cities 
     * is so darn good. */
    result->total = result->best_other;
  } else {
    /* There is no available tile in this city. All is worked. */
    result->total = 0;
    return;
  }

  if (virtual_city) {
    /* Corruption and waste of a size one city deducted. Notice that we
     * don't do this if 'fulltradesize' is changed, since then we'd
     * never make cities. */
    if (game.fulltradesize == 1) {
      result->total -= ai->science_priority
                       * city_corruption(pcity, 
                                   result->tile[result->o_x][result->o_y].trade
                                   + result->tile[2][2].trade);
    }
    result->total -= ai->shield_priority
                     * city_waste(pcity,
                                  result->tile[result->o_x][result->o_y].shield
                                  + result->tile[2][2].shield);
  } else {
    /* Deduct difference in corruption and waste for real cities. Note that it
     * is possible (with notradesize) that we _gain_ value here. */
    pcity->size++;
    result->total -= ai->science_priority
                     * (city_corruption(pcity,
                                 result->tile[result->o_x][result->o_y].trade)
                        - pcity->corruption);
    result->total -= ai->shield_priority
                     * (city_waste(pcity,
                                   result->tile[result->o_x][result->o_y].shield)
                        - pcity->shield_waste);
    pcity->size--;
  }
  result->total = MAX(0, result->total);

  pplayer->government = curr_govt;
  if (virtual_city) {
    remove_city_virtual(pcity);
  }

  assert(result->total == 0 || result->best_other != -1);
  assert(result->total == 0 || result->other_x != -1);
  assert(result->total == 0 || result->other_y != -1);
  assert(result->city_center >= 0);
  assert(result->remaining >= 0);
}

/**************************************************************************
  Calculates the desire for founding a new city at (x, y). The citymap 
  ensures that we do not build cities too close to each other. If we 
  return result->total == 0, then no place was found.
**************************************************************************/
static void city_desirability(struct player *pplayer, struct ai_data *ai,
                              struct unit *punit, int x, int y,
                              struct cityresult *result)
{  
  bool ocean_adjacent = is_terrain_near_tile(x, y, T_OCEAN);
  struct city *pcity = map_get_city(x, y);
  int defense_bonus;

  assert(punit && ai && pplayer && result);

  result->x = x;
  result->y = y;
  result->total = 0;

  if (!city_can_be_built_here(x, y, punit)
      || (ai_handicap(pplayer, H_MAP)
          && !map_is_known(x, y, pplayer))) {
    return;
  }

  /* Check if another settler has taken a spot within mindist */
  square_iterate(x, y, game.rgame.min_dist_bw_cities-1, x1, y1) {
    if (citymap_is_reserved(x1, y1)) {
      return;
    }
  } square_iterate_end;

  if (enemies_at(punit, x, y)) {
    return;
  }

  if (pcity && pcity->size >= game.add_to_size_limit) {
    return;
  }

  if (!pcity && citymap_is_reserved(x, y)) {
    return; /* reserved, go away */
  }

  cityresult_fill(pplayer, ai, result); /* Burn CPU, burn! */
  if (result->total == 0) {
    /* Failed to find a good spot */
    return;
  }

  /* If (x, y) is an existing city, consider immigration */
  if (pcity && pcity->owner == pplayer->player_no) {
    return;
  }

  /*** Alright: Now consider building a new city ***/

  /* Avoid starvation: We must have enough food to grow. */
  if (result->tile[2][2].food 
      + result->tile[result->o_x][result->o_y].food < 3) {
    result->total = 0;
    return;
  }

  /* Avoid resource starvation. */
  if (result->tile[2][2].shield
      + result->tile[result->o_x][result->o_y].shield == 0) {
    result->total = 0;
    return;
  }

  /* Defense modification (as tie breaker mostly) */
  defense_bonus = get_tile_type(map_get_terrain(x, y))->defense_bonus;
  if (map_has_special(x, y, S_RIVER)) {
    defense_bonus +=
        (defense_bonus * terrain_control.river_defense_bonus) / 100;
  }
  result->total += (result->total * defense_bonus) / ai->defense_emphasis;

  /* Adjust for ocean adjacency, which is nice */
  if (ocean_adjacent) {
    result->total += (result->total * ai->naval_emphasis) / 100;
  }

  /* Add remaining points, which is our potential */
  result->total += result->remaining;

  assert(result->total >= 0);

  return;
}

/**************************************************************************
  Prime settler engine.
**************************************************************************/
void ai_settler_init(struct player *pplayer)
{
  memset(&cachemap, -1, sizeof(cachemap));
}

/****************************************************************************
 Combined cost function for a land unit on a ferry, taking into account
  possibilities of attacking on land.  For movements sea-to-sea the cost is
  collected via the extra cost call-back.
****************************************************************************/
static int combined_land_move(int x, int y, enum direction8 dir,
                                     int x1, int y1,
                                     struct pf_parameter *param)
{
  struct tile *src_tile = map_get_tile(x, y);
  struct tile *tgt_tile = map_get_tile(x1, y1);
  int move_cost;

  if (is_ocean(tgt_tile->terrain)) {
    /* Any-to-Sea */
    if (is_ocean(src_tile->terrain)
        || same_pos(x, y, param->start_x, param->start_y)) {
      move_cost = 0;
    } else {
      move_cost = PF_IMPOSSIBLE_MC;
    }
  } else if (src_tile->terrain == T_OCEAN) {
    /* Sea-to-Land. */
    if (!is_non_allied_unit_tile(tgt_tile, param->owner)
        && !is_non_allied_city_tile(tgt_tile, param->owner)) {
      move_cost
        = get_tile_type(tgt_tile->terrain)->movement_cost * SINGLE_MOVE;
    } else {
      move_cost = PF_IMPOSSIBLE_MC;
    }
  } else {
    /* Land-to-Land */
    if (!is_non_allied_unit_tile(tgt_tile, param->owner)) {
      move_cost = src_tile->move_cost[dir];
    } else {
      /* We don't attack */
      move_cost = PF_IMPOSSIBLE_MC;
    }
  }
  return move_cost;
}

/****************************************************************************
  EC callback to account for the cost of sea moves by a unit carried by a
  ferry.  To use we need to put the ferry move_rate into the data field of
  param.
****************************************************************************/
static int sea_move(int x, int y, enum known_type known,
                    struct pf_parameter *param)
{
  int moverate = *(int *)(param->data);

  if (is_ocean(map_get_tile(x, y)->terrain)) {
    return SINGLE_MOVE * PF_TURN_FACTOR / moverate;
  } else {
    return 0;
  }
}

/**************************************************************************
  Find nearest and best city placement. Transparently checks if we should
  add ourselves to an existing city (TODO).
**************************************************************************/
static struct city *settler_map_iterate(struct pf_parameter *parameter,
                                        struct unit *punit,
                                        struct cityresult *best,
                                        struct player *pplayer)
{
  const int enough = 250; /* WAG */
  struct cityresult result;
  int best_turn = 0; /* Which turn we found the best fit */
  struct city *port = NULL;
  struct ai_data *ai = ai_data_get(pplayer);
  struct pf_map *map;

  map = pf_create_map(parameter);
  pf_iterator(map, pos) {
    int turns;
    struct tile *ptile = map_get_tile(pos.x, pos.y);

    if (is_ocean(ptile->terrain)) {
      continue; /* This can happen if there is a ferry near shore. */
    }
    if (parameter->get_MC != combined_land_move
        && ptile->continent != map_get_tile(punit->x, punit->y)->continent) {
      /* We have an accidential land bridge. Ignore it. It will in all
       * likelihood go away next turn, or even in a few nanoseconds. */
      continue;
    }

    /* Find ports for phase 2 here */
    if (port != NULL && is_at_coast(pos.x, pos.y)) {
      port = map_get_city(pos.x, pos.y);
    }

    /* Calculate worth */
    city_desirability(pplayer, ai, punit, pos.x, pos.y, &result);

    /* Check if actually found something */
    if (result.total == 0) {
      continue;
    }

    /* This algorithm punishes long treks */
    turns = pos.total_MC / unit_type(punit)->move_rate;
    result.total = amortize(result.total, ai->perfection * turns);

    /* Reduce want by settler cost. Easier than amortize, but still
     * weeds out very small wants. ie we create a threshold here. */
    result.total -= unit_type(punit)->build_cost;

    /* Find best spot */
    if (result.total > best->total) {
      *best = result;
      best_turn = turns;
    }

    /* Can we terminate early? We have a 'good enough' spot, and
     * we don't block the establishment of a better city just one
     * further step away. */
    if (best->total > enough
        && turns > unit_type(punit)->move_rate /* sic */
        && best_turn < turns /*+ game.rgame.min_dist_bw_cities*/) {
      break;
    }
  } pf_iterator_end;


  pf_destroy_map(map);

  return port;
}

/**************************************************************************
  Find nearest and best city placement. Transparently checks if we should
  add ourselves to an existing city (TODO).
**************************************************************************/
void find_best_city_placement(struct unit *punit, struct cityresult *best)
{
  struct player *pplayer = unit_owner(punit);
  struct pf_parameter parameter;
  struct city *port = NULL; /* The nearest port to us */
  /* TODO: Consider building a new boat */
  bool do_overseas = ai_player_has_enough_boats(pplayer, 1);

  assert(pplayer && pplayer->ai.control);

  best->x = -1;
  best->y = -1;
  best->total = 0;

  if (do_overseas && is_at_coast(punit->x, punit->y)) {
    port = map_get_city(punit->x, punit->y);
  }

  /* Phase 1: Consider building cities on our continent */

  pft_fill_unit_parameter(&parameter, punit);
  if (port == NULL) {
    port = settler_map_iterate(&parameter, punit, best, pplayer);
  } else {
    (void) settler_map_iterate(&parameter, punit, best, pplayer);
  }

  /* Phase 2: Consider travelling to another continent */

  if (do_overseas && port) {
    Unit_Type_id boattype
      = best_role_unit_for_player(pplayer, L_FERRYBOAT);
    static int ferry_rate;  /* FIXME: do we need static? */

    if (boattype == U_LAST) {
      /* Sea travel not possible yet */
      return;
    }

    pft_fill_unit_parameter(&parameter, punit);
    parameter.turn_mode = TM_WORST_TIME;
    parameter.start_x = port->x;
    parameter.start_y = port->y;
    parameter.get_TB = no_fights_or_unknown;
    parameter.get_EC = sea_move;
    parameter.get_MC = combined_land_move;
    ferry_rate = get_unit_type(boattype)->move_rate;
    parameter.data = &ferry_rate;

    (void) settler_map_iterate(&parameter, punit, best, pplayer);
  }
}