/********************************************************************** 
 Freeciv - Copyright (C) 2002 - 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 "log.h"
#include "map.h"
#include "mem.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 "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 citycache struct with useful info about the city spot. cache must 
  contain valid x, y coordinates.

  We assume whatever best government we are aiming for.

  We always return valid other_x and other_y if total > 0.
**************************************************************************/
static void citycache_fill(struct player *pplayer, struct citycache *cache)
{
  struct city *pcity = map_get_city(cache->x, cache->y);
  struct tile *ptile = NULL;
  int sum = 0;
  bool virtual_city = FALSE;
  struct ai_data *ai = ai_data_get(pplayer);
  int curr_govt = pplayer->government;
  int o_x = -1, o_y = -1; /* other_x and other_y but city relative */

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

  cache->best_other = -1;
  cache->other_x = -1;
  cache->other_y = -1;
  cache->remaining = 0;

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

  city_map_checked_iterate(cache->x, cache->y, i, j, map_x, map_y) {
    int reserved = citymap_read(map_x, map_y);
    ptile = map_get_tile(map_x, map_y);

    if (reserved < 0) {
      /* Tile is reserved */
      sum = 0;
    } else if (cachemap[map_x][map_y].sum == -1 || !is_city_center(i, j)) {
      /* We cannot read city center from cache */

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

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

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

      sum = (cache->tile[i][j].food * ai->food_priority
             + cache->tile[i][j].trade * ai->science_priority
             + cache->tile[i][j].shield * ai->shield_priority);
      if (cache->tile[i][j].food >= 2) {
        sum *= 2; /* we need this to grow */
      }
      /* If this tile is in proximity of a city, we don't want it this much. 
       * The more cities it overlaps with, the less we want it. */
      sum /= (reserved + 1);

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

    /* Calculate city center and best other than city center */
    if (is_city_center(i, j)) {
      cache->city_center = sum;
    } else if (sum > cache->best_other) {
      cache->best_other = sum;
      cache->other_x = map_x;
      cache->other_y = map_y;
    } else {
      /* Save total remaining calculation */
      cache->remaining += sum;
    }
  }
  city_map_checked_iterate_end;

  /* Baseline is a size one city */
  cache->total = cache->city_center + cache->best_other;

  /* 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
   * cities. */
  if (game.fulltradesize == 1) {
    cache->total -= ai->science_priority
                    * city_corruption(pcity, 
                                      cache->tile[o_x][o_y].trade
                                      + cache->tile[2][2].trade);
  }
  cache->total -= ai->shield_priority
                  * city_waste(pcity,
                               cache->tile[o_x][o_y].shield
                               + cache->tile[2][2].shield);
  cache->total = MAX(0, cache->total);

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

  if (cache->best_other == 0) {
    /* Everything taken! */
    cache->total = 0;
    return;
  }

  assert(cache->best_other != -1 && cache->other_x != -1 
         && cache->other_y != -1);
  assert(cache->city_center >= 0);
  assert(cache->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 cache->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 citycache *cache)
{  
  struct tile *ptile = map_get_tile(x, y);
  bool ocean_adjacent = is_terrain_near_tile(x, y, T_OCEAN);
  struct city *pcity = map_get_city(x, y);
  int defense_bonus;

  assert(punit);
  assert(pplayer);
  assert(cache);

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

  if (ptile->terrain == T_OCEAN) {
    return;
  }

  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 */
  }

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

  /* If (x, y) is an existing city, consider immigration */
  if (pcity) {
/*    cache->total = cache->best_other; <<-- buggy */
    cache->total = 0;
    return;
  }

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

  /* Avoid starvation: We must have enough food at city center */
  if (cache->tile[2][2].food < 2) {
    cache->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;
  }
  cache->total += (cache->total * defense_bonus) / ai->defense_emphasis;

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

  /* Add remaining points, which is our potential */
  cache->total += (cache->remaining / ai->growth_potential_emphasis);

  assert(cache->total >= 0);

  return;
}

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

/**************************************************************************
  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 citycache *best)
{
  struct player *pplayer = unit_owner(punit);
  struct ai_data *ai = ai_data_get(pplayer);
  struct citycache cache;

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

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

  /* Uh, we're on board a ship... */
  if (map_get_tile(punit->x, punit->y)->terrain == T_OCEAN) {
    UNIT_LOG(LOG_ERROR, punit, "We're trying to find a city while on board "
             "a ship...");
    return;
  }

  simple_unit_path_iterator(punit, pos) {
    int turns;

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

    /* This ugly algorithm punishes long treks exponentially. */
    turns = pos.total_MC / unit_type(punit)->move_rate;
    if (turns > 1) {
      int i, d = ai->perfection;

      for (i = 0; i < turns; i++) {
        cache.total -= d;
        d += ai->perfection / 2;
      }
    }

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

    /* Find best spot */
    if (cache.total > best->total) {
      *best = cache;
    }
  } simple_unit_path_iterator_end;
}