bool can_generate(const gamemap& map, const std::vector<team>& teams, const unit_map& units, const unit& u, const map_location& loc)
{
	if (!map.on_board(loc)) {
		return false;
	}
	if (u.movement_cost(map[loc]) == unit_movement_type::UNREACHABLE) {
		return false;
	}
	unit_map::const_iterator it = units.find(loc, false);
	if (it.valid() && !it->can_stand(u)) {
		return false;
	}

	map_location locs[6];
	get_adjacent_tiles(loc, locs);
	for (int i = 0; i != 6; ++i) {
		if (!map.on_board(locs[i])) {
			continue;
		}
		if (u.movement_cost(map[locs[i]]) != unit_movement_type::UNREACHABLE) {
			return true;
		}
	}
	return false;
}

// Complexity: O(nr lg(nr) + nr^2), where n = locs.size(), r = radius.
// The nr^2 term is bounded by the size of the board.
void get_tiles_radius(const gamemap& map, const std::vector<map_location>& locs,
                      size_t radius, std::set<map_location>& result,
                      bool with_border)
{
	// Make sure the provided locations are included.
	// This would be needed in case some of the provided locations are off-map.
	// It also allows simpler processing if the radius is zero.
	// For efficiency, do this first since locs is potentially unsorted.
	result.insert(locs.begin(), locs.end());

	if ( radius != 0  &&  !locs.empty() )
	{
		const int border = with_border ? map.border_size() : 0;
		column_ranges collected_tiles;

		// Collect the hexes within the desired disks into collected_tiles.
		// This maps each x-value to a set of ranges of y-values that
		// are covered by the disks around each element of locs.
		// (So the data size at this point is proportional to the number
		// of x-values involved, which is O(nr). The lg(nr) factor comes
		// from the data being sorted.)
		get_column_ranges(collected_tiles, locs, radius, -border, map.w() + border);

		// Now that all the tiles have been collected, add them to result.
		// (There are O(nr^2) hexes to add.) By collecting before adding, each
		// hex will be processed only once, even when disks overlap. This is
		// how we can get good performance if there is significant overlap, and
		// how the work required can be bound by the size of the board.
		ranges_to_tiles(result, collected_tiles, -border, map.h() + border);
	}
}

boost::optional<std::string> game_board::replace_map(const gamemap & newmap) {
	boost::optional<std::string> ret = boost::optional<std::string> ();

	/* Remember the locations where a village is owned by a side. */
	std::map<map_location, int> villages;
	for(const auto& village : map_->villages()) {
		const int owner = village_owner(village);
		if(owner != -1) {
			villages[village] = owner;
		}
	}

	for (unit_map::iterator itor = units_.begin(); itor != units_.end(); ) {
		if (!newmap.on_board(itor->get_location())) {
			if (!try_add_unit_to_recall_list(itor->get_location(), itor.get_shared_ptr())) {
				*ret = std::string("replace_map: Cannot add a unit that would become off-map to the recall list\n");
			}
			units_.erase(itor++);
		} else {
			++itor;
		}
	}

	/* Disown villages that are no longer villages. */
	for(const auto& village : villages) {
		if(!newmap.is_village(village.first)) {
			teams_[village.second].lose_village(village.first);
		}
	}

	*map_ = newmap;
	return ret;
}

bool move_result::test_route(const unit &un, const team &my_team, const unit_map &units, const std::vector<team> &teams, const gamemap &map, bool)
{
	if (from_== to_) {
		if (!remove_movement_ || (un.movement_left() == 0) ) {
			set_error(E_EMPTY_MOVE);
			return false;
		}
		return true;
	}

	if (un.movement_left() == 0 ) {
		set_error(E_EMPTY_MOVE);
		return false;
	}

	if (!to_.valid()) {
		set_error(E_NO_ROUTE);
		return false;
	}
	const pathfind::shortest_path_calculator calc(un, my_team, units, teams,map);

	//allowed teleports
	std::set<map_location> allowed_teleports = pathfind::get_teleport_locations(un, units, my_team, true);//@todo 1.9: see_all -> false

	//do an A*-search
	route_ = pathfind::a_star_search(un.get_location(), to_, 10000.0, &calc, map.w(), map.h(), &allowed_teleports);
	if (route_.steps.empty()) {
		set_error(E_NO_ROUTE);
		return false;
	}
	return true;
}

time_of_day tod_manager::time_of_day_at(const unit_map& units,const map_location& loc, const gamemap& map) const
{
	int lighten = std::max<int>(map.get_terrain_info(map.get_terrain(loc)).light_modification() , 0);
	int darken = std::min<int>(map.get_terrain_info(map.get_terrain(loc)).light_modification() , 0);

	time_of_day tod = get_time_of_day(lighten + darken,loc);

	if(loc.valid()) {
		map_location locs[7];
		locs[0] = loc;
		get_adjacent_tiles(loc,locs+1);

		for(int i = 0; i != 7; ++i) {
			const unit_map::const_iterator itor = units.find(locs[i]);
			if(itor != units.end() &&
			    itor->second.get_ability_bool("illuminates") &&
			    !itor->second.incapacitated())
			{
				unit_ability_list illum = itor->second.get_abilities("illuminates");
				unit_abilities::effect illum_effect(illum,lighten,false);
				int mod = illum_effect.get_composite_value();
				if(mod + tod.lawful_bonus > illum.highest("max_value").first) {
					mod = illum.highest("max_value").first - tod.lawful_bonus;
				}
				lighten = std::max<int>(mod, lighten);
				darken = std::min<int>(mod, darken);
			}
		}
	}
	tod = get_time_of_day(lighten + darken,loc);

	return tod;
}

void team::build(const config& cfg, const gamemap& map, int gold)
{
	gold_ = gold;
	info_.read(cfg);

	fog_.set_enabled(cfg["fog"].to_bool());
	fog_.read(cfg["fog_data"]);
	shroud_.set_enabled(cfg["shroud"].to_bool());
	shroud_.read(cfg["shroud_data"]);
	auto_shroud_updates_ = cfg["auto_shroud"].to_bool(auto_shroud_updates_);

	LOG_NG << "team::team(...): team_name: " << info_.team_name << ", shroud: " << uses_shroud()
		   << ", fog: " << uses_fog() << ".\n";

	// Load the WML-cleared fog.
	const config& fog_override = cfg.child("fog_override");
	if(fog_override) {
		const std::vector<map_location> fog_vector
				= map.parse_location_range(fog_override["x"], fog_override["y"], true);
		fog_clearer_.insert(fog_vector.begin(), fog_vector.end());
	}

	// To ensure some minimum starting gold,
	// gold is the maximum of 'gold' and what is given in the config file
	gold_ = std::max(gold, info_.gold);
	if(gold_ != info_.gold) {
		info_.start_gold = gold;
	}

	// Old code was doing:
	// info_.start_gold = std::to_string(gold) + " (" + info_.start_gold + ")";
	// Was it correct?

	// Load in the villages the side controls at the start
	for(const config& v : cfg.child_range("village")) {
		map_location loc(v);
		if(map.is_village(loc)) {
			villages_.insert(loc);
		} else {
			WRN_NG << "[side] " << current_player() << " [village] points to a non-village location " << loc
				   << std::endl;
		}
	}

	countdown_time_ = cfg["countdown_time"];
	action_bonus_count_ = cfg["action_bonus_count"];

	planned_actions_.reset(new wb::side_actions());
	planned_actions_->set_team_index(info_.side - 1);
}

map_location pathfind::find_vacant_tile(const gamemap& map,
				const unit_map& units,
				const map_location& loc,
				pathfind::VACANT_TILE_TYPE vacancy,
				const unit* pass_check)
{
	if (!map.on_board(loc)) return map_location();
	std::set<map_location> pending_tiles_to_check, tiles_checked;
	pending_tiles_to_check.insert(loc);
	// Iterate out 50 hexes from loc
	for (int distance = 0; distance < 50; ++distance) {
		if (pending_tiles_to_check.empty())
			return map_location();
		//Copy over the hexes to check and clear the old set
		std::set<map_location> tiles_checking;
		tiles_checking.swap(pending_tiles_to_check);
		//Iterate over all the hexes we need to check
		foreach (const map_location &loc, tiles_checking)
		{
			//If this area is not a castle but should, skip it.
			if (vacancy == pathfind::VACANT_CASTLE && !map.is_castle(loc)) continue;
			const bool pass_check_and_unreachable = pass_check
				&& pass_check->movement_cost(map[loc]) == unit_movement_type::UNREACHABLE;
			//If the unit can't reach the tile and we have searched
			//an area of at least radius 10 (arbitrary), skip the tile.
			//Neccessary for cases such as an unreachable
			//starting hex surrounded by 6 other unreachable hexes, in which case
			//the algorithm would not even search distance==1
			//even if there's a reachable hex for distance==2.
			if (pass_check_and_unreachable && distance > 10) continue;
			//If the hex is empty and we do either no pass check or the hex is reachable, return it.
			if (units.find(loc) == units.end() && !pass_check_and_unreachable) return loc;
			map_location adjs[6];
			get_adjacent_tiles(loc,adjs);
			foreach (const map_location &loc, adjs)
			{
				if (!map.on_board(loc)) continue;
				// Add the tile to be checked if it hasn't already been and
				// isn't being checked.
				if (tiles_checked.find(loc) == tiles_checked.end() &&
				    tiles_checking.find(loc) == tiles_checking.end())
				{
					pending_tiles_to_check.insert(loc);
				}
			}
		}
		tiles_checked.swap(tiles_checking);
	}
	return map_location();
}

void get_tiles_radius(gamemap const &map, std::vector<map_location> const &locs,
                      size_t radius, std::set<map_location> &res, xy_pred *pred)
{
	typedef std::set<map_location> location_set;
	location_set not_visited(locs.begin(), locs.end()), must_visit, filtered_out;
	++radius;

	for(;;) {
		location_set::const_iterator it = not_visited.begin(), it_end = not_visited.end();
		std::copy(it,it_end,std::inserter(res,res.end()));
		for(; it != it_end; ++it) {
			map_location adj[6];
			get_adjacent_tiles(*it, adj);
			for(size_t i = 0; i != 6; ++i) {
				map_location const &loc = adj[i];
				if(map.on_board(loc) && !res.count(loc) && !filtered_out.count(loc)) {
					if(!pred || (*pred)(loc)) {
						must_visit.insert(loc);
					} else {
						filtered_out.insert(loc);
					}
				}
			}
		}

		if(--radius == 0 || must_visit.empty()) {
			break;
		}

		not_visited.swap(must_visit);
		must_visit.clear();
	}
}

gamemap editor_map::mask_to(const gamemap& target) const
{
	if (target.w() != w() || target.h() != h()) {
		throw editor_action_exception(_("The size of the target map is different from the current map"));
	}
	gamemap mask(target);
	map_location iter;
	for (iter.x = -border_size(); iter.x < w() + border_size(); ++iter.x) {
		for (iter.y = -border_size(); iter.y < h() + border_size(); ++iter.y) {
			if (target.get_terrain(iter) == get_terrain(iter)) {
				mask.set_terrain(iter, t_translation::FOGGED);
			}
		}
	}
	return mask;
}

void add_river(river_ptr river, const height_map& heights, gamemap& m, const corner_location& c1, const corner_location& c2)
{
	location adj1[3];
	location adj2[3];
	
	std::vector<location> locs;
	get_adjacent_hexes_to_corner(c1, adj1);
	get_adjacent_hexes_to_corner(c2, adj2);
	for(int i = 0; i != 3; ++i) {
		for(int j = 0; j != 3; ++j) {
			if(adj1[i] == adj2[j]) {
				locs.push_back(adj1[i]);
			}
		}
	}

	assert(locs.size() == 2);

	DIRECTION dir1 = get_adjacent_direction(locs[0], locs[1]);
	DIRECTION dir2 = get_adjacent_direction(locs[1], locs[0]);
	assert(dir1 != NULL_DIRECTION);
	assert(dir2 != NULL_DIRECTION);

	tile_ptr t1 = m.get_tile(locs[0]);
	tile_ptr t2 = m.get_tile(locs[1]);

	t1->add_river(dir1, river);
	t2->add_river(dir2, river);
}

map_location find_vacant_tile(const gamemap& map,
				const unit_map& units,
				const map_location& loc,
				VACANT_TILE_TYPE vacancy,
				const unit* pass_check)
{
	std::set<map_location> pending_tiles_to_check;
	std::set<map_location> tiles_checked;
	pending_tiles_to_check.insert( loc );
	// Iterate out 50 hexes from loc
	for (int distance = 0; distance < 50; ++distance) {
		if (pending_tiles_to_check.empty())
			return map_location();
		//Copy over the hexes to check and clear the old set
		std::set<map_location> tiles_checking = pending_tiles_to_check;
		std::set<map_location>::const_iterator tc_itor = tiles_checking.begin();
		pending_tiles_to_check.clear();
		//Iterate over all the hexes we need to check
		for ( ; tc_itor != tiles_checking.end(); ++tc_itor )
		{
			//If the unit cannot reach this area or it's not a castle but should, skip it.
			if ((vacancy == VACANT_CASTLE && !map.is_castle(*tc_itor))
			|| (pass_check && pass_check->movement_cost(map[*tc_itor])
					== unit_movement_type::UNREACHABLE))
				continue;
			//If the hex is empty, return it.
			if (map.on_board(*tc_itor) && units.find(*tc_itor) == units.end())
				return (*tc_itor);
			map_location adjs[6];
			get_adjacent_tiles(*tc_itor,adjs);
			for (int i = 0; i != 6; ++i)
			{
				//Add the tile to be checked if it hasn't already been and isn't already
				//pending to be checked
				if (pending_tiles_to_check.find(adjs[i]) == pending_tiles_to_check.end() &&
					tiles_checked.find(adjs[i]) == tiles_checked.end() &&
					tiles_checking.find(adjs[i]) == tiles_checking.end())
				{
					pending_tiles_to_check.insert(adjs[i]);
				}
			}
		}
		tiles_checked = tiles_checking;
	}
	return map_location();
}

bool recruit_result::test_leader_on_keep(const gamemap &map, const unit &my_leader, bool)
{
	if (!map.is_keep(my_leader.get_location())) {
		set_error(E_LEADER_NOT_ON_KEEP);
		return false;
	}
	return true;
}

map_location pathfind::find_vacant_tile(const gamemap& map,
				const unit_map& units,
				const map_location& loc,
				pathfind::VACANT_TILE_TYPE vacancy,
				const unit* pass_check)
{
	if (!map.on_board(loc)) return map_location();
	std::set<map_location> pending_tiles_to_check, tiles_checked;
	pending_tiles_to_check.insert(loc);
	// Iterate out 50 hexes from loc
	for (int distance = 0; distance < 50; ++distance) {
		if (pending_tiles_to_check.empty())
			return map_location();
		//Copy over the hexes to check and clear the old set
		std::set<map_location> tiles_checking;
		tiles_checking.swap(pending_tiles_to_check);
		//Iterate over all the hexes we need to check
		foreach (const map_location &loc, tiles_checking)
		{
			//If the unit cannot reach this area or it's not a castle but should, skip it.
			if ((vacancy == pathfind::VACANT_CASTLE && !map.is_castle(loc))
			|| (pass_check && pass_check->movement_cost(map[loc])
					== unit_movement_type::UNREACHABLE))
				continue;
			//If the hex is empty, return it.
			if (units.find(loc) == units.end())
				return loc;
			map_location adjs[6];
			get_adjacent_tiles(loc,adjs);
			foreach (const map_location &loc, adjs)
			{
				if (!map.on_board(loc)) continue;
				// Add the tile to be checked if it hasn't already been and
				// isn't being checked.
				if (tiles_checked.find(loc) == tiles_checked.end() &&
				    tiles_checking.find(loc) == tiles_checking.end())
				{
					pending_tiles_to_check.insert(loc);
				}
			}
		}
		tiles_checked.swap(tiles_checking);
	}
	return map_location();
}

map_location pathfind::find_vacant_tile(const gamemap& map,
				const std::vector<team>& teams,
				const unit_map& units,
				const map_location& loc,
				const unit* pass_check)
{
	if (!map.on_board(loc)) return map_location();
	std::set<map_location> pending_tiles_to_check, tiles_checked;
	pending_tiles_to_check.insert(loc);
	// Iterate out 50 hexes from loc
	for (int distance = 0; distance < 50; ++distance) {
		//Copy over the hexes to check and clear the old set
		std::set<map_location> tiles_checking;
		tiles_checking.swap(pending_tiles_to_check);
		//Iterate over all the hexes we need to check
		BOOST_FOREACH (const map_location &loc, tiles_checking)
		{
			tiles_checked.insert(loc);

			// If the unit cannot reach this area or it's not a castle but should, skip it.
			if (!pass_check || can_generate(map, teams, units, *pass_check, loc)) {
				// If the hex is empty, return it.
				if (units.find(loc) == units.end()) {
					return loc;
				}
			}
			map_location adjs[6];
			get_adjacent_tiles(loc, adjs);
			BOOST_FOREACH (const map_location &loc, adjs)
			{
				if (!map.on_board(loc)) continue;
				// Add the tile to be checked if it hasn't already been and
				// isn't being checked.
				if (tiles_checked.find(loc) == tiles_checked.end()) {
					pending_tiles_to_check.insert(loc);
				}
			}			
		}
	}

void tod_manager::add_time_area(const gamemap & map, const config& cfg)
{
	areas_.push_back(area_time_of_day());
	area_time_of_day &area = areas_.back();
	area.id = cfg["id"].str();
	area.xsrc = cfg["x"].str();
	area.ysrc = cfg["y"].str();
	area.currentTime = cfg["current_time"].to_int(0);
	std::vector<map_location> const& locs (map.parse_location_range(area.xsrc, area.ysrc, true));
	area.hexes.insert(locs.begin(), locs.end());
	time_of_day::parse_times(cfg, area.times);
	has_tod_bonus_changed_ = true;
}

bool recruit_result::test_suitable_recruit_location(const gamemap &map, const unit_map &units, const unit &my_leader, bool)
{
	recruit_location_ = where_;

	//if we have not-on-board location, such as null_location, then the caller wants us to recruit on 'any' possible tile.
	if (!map.on_board(recruit_location_)) {
		recruit_location_ = pathfind::find_vacant_tile(map, units, my_leader.get_location(), pathfind::VACANT_CASTLE);
	}

	if (!can_recruit_on(map, my_leader.get_location(), recruit_location_)) {
		set_error(E_BAD_RECRUIT_LOCATION);
		return false;
	}
	return true;
}

static int placing_score(const config& side, const gamemap& map, const map_location& pos)
{
	int positions = 0, liked = 0;
	const t_translation::t_list terrain = t_translation::read_list(side["terrain_liked"]);

	for(int i = pos.x-8; i != pos.x+8; ++i) {
		for(int j = pos.y-8; j != pos.y+8; ++j) {
			const map_location pos(i,j);
			if(map.on_board(pos)) {
				++positions;
				if(std::count(terrain.begin(),terrain.end(),map[pos])) {
					++liked;
				}
			}
		}
	}

	return (100*liked)/positions;
}

marked_route mark_route(const plain_route &rt,
	const std::vector<map_location>& waypoints, const unit &u,
	const team &viewing_team, const unit_map &units,
	const std::vector<team> &teams, const gamemap &map)
{
	marked_route res;

	if (rt.steps.empty()) return res;
	res.steps = rt.steps;

	int turns = 0;
	int movement = u.movement_left();
	const team& unit_team = teams[u.side()-1];
	bool zoc = false;

	std::vector<map_location>::const_iterator i = rt.steps.begin(),
			w = waypoints.begin();

	// TODO fix the name confusion with waypoints and route.waypoints
	for (; i !=rt.steps.end(); i++) {
		bool last_step = (i+1 == rt.steps.end());

		// move_cost of the next step is irrelevant for the last step
		assert(last_step || map.on_board(*(i+1)));
		const int move_cost = last_step ? 0 : u.movement_cost(map[*(i+1)]);
		bool capture = false;
		bool pass_here = false;
		if (w != waypoints.end() && *i == *w) {
			w++;
			pass_here = true;
		}

		if (last_step || zoc || move_cost > movement) {
			// check if we stop an a village and so maybe capture it
			// if it's an enemy unit and a fogged village, we assume a capture
			// (if he already owns it, we can't know that)
			// if it's not an enemy, we can always know if he owns the village
			bool capture = map.is_village(*i) && ( !unit_team.owns_village(*i)
				 || (viewing_team.is_enemy(u.side()) && viewing_team.fogged(*i)) );

			++turns;

			bool invisible = u.invisible(*i,units,teams,false);

			res.waypoints[*i] = marked_route::waypoint(turns, pass_here, zoc, capture, invisible);

			if (last_step) break; // finished and we used dummy move_cost

			movement = u.total_movement();
			if(move_cost > movement) {
				return res; //we can't reach destination
			}
		} else if (pass_here) {
			bool invisible = u.invisible(*i,units,teams,false);
			res.waypoints[*i] = marked_route::waypoint(0, pass_here, zoc, false, invisible);
		}

		zoc = enemy_zoc(units, teams, *(i + 1), viewing_team,u.side())
					&& !u.get_ability_bool("skirmisher", *(i+1));

		if (zoc || capture) {
			movement = 0;
		} else {
			movement -= move_cost;
		}
	}

	return res;
}

void map_fragment::paste_into(gamemap& map, const map_location& loc) const
{
	for (const tile_info& i : items_) {
		map.set_terrain(i.offset.vector_sum(loc), i.terrain);
	}
}

const time_of_day tod_manager::get_illuminated_time_of_day(const unit_map & units, const gamemap & map, const map_location& loc, int for_turn) const
{
	// get ToD ignoring illumination
	time_of_day tod = get_time_of_day(loc, for_turn);

	if ( map.on_board_with_border(loc) )
	{
		// Now add terrain illumination.
		const int terrain_light = map.get_terrain_info(loc).light_bonus(tod.lawful_bonus);

		std::vector<int> mod_list;
		std::vector<int> max_list;
		std::vector<int> min_list;
		int most_add = 0;
		int most_sub = 0;

		// Find the "illuminates" effects from units that can affect loc.
		map_location locs[7];
		locs[0] = loc;
		get_adjacent_tiles(loc,locs+1);
		for ( size_t i = 0; i != 7; ++i ) {
			const unit_map::const_iterator itor = units.find(locs[i]);
			if (itor != units.end() &&
			    itor->get_ability_bool("illuminates") &&
			    !itor->incapacitated())
			{
				unit_ability_list illum = itor->get_abilities("illuminates");
				unit_abilities::effect illum_effect(illum, terrain_light, false);
				const int unit_mod = illum_effect.get_composite_value();

				// Record this value.
				mod_list.push_back(unit_mod);
				max_list.push_back(illum.highest("max_value").first);
				min_list.push_back(illum.lowest("min_value").first);
				if ( unit_mod > most_add )
					most_add = unit_mod;
				else if ( unit_mod < most_sub )
					most_sub = unit_mod;
			}
		}
		const bool net_darker = most_add < -most_sub;

		// Apply each unit's effect, tracking the best result.
		int best_result = terrain_light;
		const int base_light = terrain_light + (net_darker ? most_add : most_sub);
		for ( size_t i = 0; i != mod_list.size(); ++i ) {
			int result =
				bounded_add(base_light, mod_list[i], max_list[i], min_list[i]);

			if ( net_darker  &&  result < best_result )
				best_result = result;
			else if ( !net_darker  &&  result > best_result )
				best_result = result;
		}

		// Update the object we will return.
		tod.bonus_modified = best_result - tod.lawful_bonus;
		tod.lawful_bonus = best_result;
	}

	return tod;
}