#include "BananaBrain.h"

void BuildingPlacementManager::init()
{
	init_power_grid();
	if (Broodwar->self()->getRace() == Races::Protoss) init_photon_cannon_positions();
	if (Broodwar->self()->getRace() == Races::Terran) init_missile_turret_positions();
	if (Broodwar->self()->getRace() == Races::Zerg) init_creep_colony_positions();
}

void BuildingPlacementManager::init_power_grid()
{
	init_power_grid(power_grid_2x2_, -4, -6, 5);
	init_power_grid(power_grid_2x2_, -3, -7, 6);
	init_power_grid(power_grid_2x2_, -2, -7, 7);
	init_power_grid(power_grid_2x2_, -1, -7, 7);
	init_power_grid(power_grid_2x2_, 0, -7, 7);
	init_power_grid(power_grid_2x2_, 1, -7, 7);
	init_power_grid(power_grid_2x2_, 2, -7, 6);
	init_power_grid(power_grid_2x2_, 3, -6, 5);
	init_power_grid(power_grid_2x2_, 4, -3, 2);
	
	init_power_grid(power_grid_3x2_, -4, -6, 5);
	init_power_grid(power_grid_3x2_, -3, -7, 6);
	init_power_grid(power_grid_3x2_, -2, -8, 7);
	init_power_grid(power_grid_3x2_, -1, -8, 7);
	init_power_grid(power_grid_3x2_, 0, -8, 7);
	init_power_grid(power_grid_3x2_, 1, -8, 7);
	init_power_grid(power_grid_3x2_, 2, -7, 6);
	init_power_grid(power_grid_3x2_, 3, -6, 5);
	init_power_grid(power_grid_3x2_, 4, -3, 2);
	
	init_power_grid(power_grid_4x3_, -5, -4, 1);
	init_power_grid(power_grid_4x3_, -4, -7, 4);
	init_power_grid(power_grid_4x3_, -3, -8, 5);
	init_power_grid(power_grid_4x3_, -2, -8, 6);
	init_power_grid(power_grid_4x3_, -1, -8, 6);
	init_power_grid(power_grid_4x3_, 0, -8, 6);
	init_power_grid(power_grid_4x3_, 1, -8, 6);
	init_power_grid(power_grid_4x3_, 2, -8, 5);
	init_power_grid(power_grid_4x3_, 3, -7, 4);
	init_power_grid(power_grid_4x3_, 4, -4, 1);
}

void BuildingPlacementManager::init_power_grid(std::set<TilePosition>& grid,int y,int xmin,int xmax)
{
	for (int x = xmin; x <= xmax; x++) grid.insert(TilePosition(x, y));
}

void BuildingPlacementManager::init_photon_cannon_positions()
{
	for (auto& base : base_state.bases()) {
		Position defense_center = calculate_defense_center(base);
		if (defense_center.isValid()) {
			Position base_center = base->Center();
			TilePosition base_position = base->Location();
			std::vector<TilePosition>& positions = photon_cannon_positions_[base];
			
			if (base_center.y > defense_center.y) {
				if (base_center.x > defense_center.x) {
					positions.push_back(base_position + TilePosition(4, 0));
					positions.push_back(base_position + TilePosition(0, 3));
					positions.push_back(base_position + TilePosition(4, 3));
					pylon_positions_[base] = base_position + TilePosition(2, 3);
				} else {
					positions.push_back(base_position + TilePosition(-2, 3));
					positions.push_back(base_position + TilePosition(-2, 0));
					positions.push_back(base_position + TilePosition(2, 3));
					pylon_positions_[base] = base_position + TilePosition(0, 3);
				}
			} else {
				if (base_center.x > defense_center.x) {
					positions.push_back(base_position + TilePosition(4, -2));
					positions.push_back(base_position + TilePosition(0, -2));
					positions.push_back(base_position + TilePosition(4, 1));
					pylon_positions_[base] = base_position + TilePosition(2, -2);
				} else {
					positions.push_back(base_position + TilePosition(-2, -2));
					positions.push_back(base_position + TilePosition(2, -2));
					positions.push_back(base_position + TilePosition(-2, 1));
					pylon_positions_[base] = base_position + TilePosition(0, -2);
				}
			}
		}
	}
}

void BuildingPlacementManager::init_missile_turret_positions()
{
	for (auto& base : base_state.bases()) {
		Position defense_center = calculate_defense_center(base);
		if (defense_center.isValid()) {
			Position base_center = base->Center();
			TilePosition base_position = base->Location();
			std::vector<TilePosition>& positions = missile_turret_positions_[base];
			
			if (base_center.y > defense_center.y) {
				if (base_center.x > defense_center.x) {
					positions.push_back(base_position + TilePosition(4, -1));
					positions.push_back(base_position + TilePosition(0, 3));
					positions.push_back(base_position + TilePosition(4, 3));
				} else {
					positions.push_back(base_position + TilePosition(-2, 3));
					positions.push_back(base_position + TilePosition(-2, 0));
					positions.push_back(base_position + TilePosition(2, 3));
				}
			} else {
				if (base_center.x > defense_center.x) {
					positions.push_back(base_position + TilePosition(4, -2));
					positions.push_back(base_position + TilePosition(0, -2));
					positions.push_back(base_position + TilePosition(4, 3));
				} else {
					positions.push_back(base_position + TilePosition(-2, -2));
					positions.push_back(base_position + TilePosition(2, -2));
					positions.push_back(base_position + TilePosition(-2, 1));
				}
			}
		}
	}
}

void BuildingPlacementManager::init_creep_colony_positions()
{
	for (auto& base : base_state.bases()) {
		std::set<const BWEM::Area*> areas;
		areas.insert(base->GetArea());
		
		TileGrid<bool> blocked;
		insert_unbuildable_nonarea_locations(blocked, areas);
		insert_building_locations(blocked);
		insert_base_locations(blocked);
		
		FastTilePosition base_tile_position = base->Location();
		for (int dx = 0; dx < UnitTypes::Zerg_Hatchery.tileWidth(); dx++) {
			blocked.set(base_tile_position + FastTilePosition(dx, UnitTypes::Zerg_Hatchery.tileHeight()), true);
		}
		for (int dy = 0; dy < UnitTypes::Zerg_Hatchery.tileHeight() + 1; dy++) {
			blocked.set(base_tile_position + FastTilePosition(-1, dy), true);
			blocked.set(base_tile_position + FastTilePosition(UnitTypes::Zerg_Hatchery.tileWidth(), dy), true);
		}
		
		FastPosition base_position = base->Center();
		FastPosition sum(0, 0);
		int count = 0;
		
		for (auto& mineral : base->Minerals()) {
			sum += mineral->Pos();
			sum += base_position;
			count += 2;
		}
		FastPosition center_position;
		if (count == 0) {
			center_position = base_position;
		} else {
			center_position = sum / count;
		}
		
		FastTilePosition best_tile_position = TilePositions::None;
		int best_distance = INT_MAX;
		for (int y = 0; y < Broodwar->mapHeight(); y++) {
			for (int x = 0; x < Broodwar->mapWidth(); x++) {
				FastTilePosition candidate_tile_position(x, y);
				if (rectangle_buildable_for_building_with_clearance(candidate_tile_position, UnitTypes::Zerg_Creep_Colony, blocked, 0)) {
					FastPosition candidate_position = center_position_for(UnitTypes::Zerg_Creep_Colony, candidate_tile_position);
					int distance = center_position.getApproxDistance(candidate_position);
					if (distance < best_distance) {
						best_tile_position = candidate_tile_position;
						best_distance = distance;
					}
				}
			}
		}
		
		if (best_tile_position.isValid()) {
			creep_colony_positions_[base] = best_tile_position;
		}
	}
}

Position BuildingPlacementManager::calculate_defense_center(const BWEM::Base* base)
{
	Position mineral_center;
	int mineral_center_count = 0;
	for (auto& mineral : base->Minerals()) {
		mineral_center += mineral->Pos();
		mineral_center_count++;
	}
	
	Position defense_center;
	int defense_center_count = 0;
	if (mineral_center_count > 0) {
		defense_center = mineral_center / mineral_center_count;
		defense_center_count++;
	}
	for (auto& geyser : base->Geysers()) {
		defense_center += geyser->Pos();
		defense_center_count++;
	}
	
	return (defense_center_count > 0) ? (defense_center / defense_center_count) : Positions::None;
}

TilePosition BuildingPlacementManager::place_building(UnitType unit_type)
{
	TileGrid<bool> blocked;
	insert_building_locations(blocked);
	insert_threatened_ground_locations(blocked);
	
	TileGrid<bool> resource_blocked;
	insert_resource_locations(resource_blocked);
	
	if (specific_positions_.count(unit_type) > 0) {
		TileGrid<bool> power_grid = determine_power_grid(unit_type);
		for (auto& tile_position : specific_positions_[unit_type]) {
			if (test_power_requirement(power_grid, unit_type, tile_position) &&
				test_building_location(blocked, resource_blocked, unit_type, tile_position, false)) {
				return tile_position;
			}
		}
	}
	
	insert_specific_building_locations(blocked);
	
	if (unit_type == UnitTypes::Terran_Missile_Turret) {
		struct PotentialLocationForBase {
			int count = 0;
			TilePosition tile_position = TilePositions::None;
		};
		
		std::map<const BWEM::Base*,PotentialLocationForBase> potential_locations;
		for (auto& entry : missile_turret_positions_) {
			const BWEM::Base* base = entry.first;
			for (auto& tile_position : entry.second) {
				if (test_building_location(blocked, resource_blocked, UnitTypes::Terran_Missile_Turret, tile_position, false)) {
					PotentialLocationForBase& potential = potential_locations[base];
					potential.count++;
					if (potential.count == 1) potential.tile_position = tile_position;
				}
			}
		}
		
		if (!potential_locations.empty()) {
			auto it = std::min_element(potential_locations.begin(), potential_locations.end(), [](auto& entry1,auto& entry2){
				return entry1.second.count < entry2.second.count;
			});
			return (*it).second.tile_position;
		}
	}
	
	if (unit_type == UnitTypes::Protoss_Photon_Cannon) {
		TileGrid<bool> power_grid = determine_power_grid(UnitTypes::Protoss_Photon_Cannon);
		
		struct PotentialLocationForBase {
			int count = 0;
			TilePosition tile_position = TilePositions::None;
		};
		
		std::map<const BWEM::Base*,PotentialLocationForBase> potential_locations;
		for (auto& entry : photon_cannon_positions_) {
			const BWEM::Base* base = entry.first;
			for (auto& tile_position : entry.second) {
				if (test_power_requirement(power_grid, UnitTypes::Protoss_Photon_Cannon, tile_position) &&
					test_building_location(blocked, resource_blocked, UnitTypes::Protoss_Photon_Cannon, tile_position, false)) {
					PotentialLocationForBase& potential = potential_locations[base];
					potential.count++;
					if (potential.count == 1) potential.tile_position = tile_position;
				}
			}
		}
		
		if (!potential_locations.empty()) {
			auto it = std::min_element(potential_locations.begin(), potential_locations.end(), [](auto& entry1,auto& entry2){
				return entry1.second.count < entry2.second.count;
			});
			return (*it).second.tile_position;
		}
	}
	
	insert_base_locations(blocked);
	insert_padded_resource_locations(resource_blocked, unit_type.isResourceDepot());
	insert_base_defense_photon_cannon_locations(blocked);
	insert_base_defense_missile_turret_locations(blocked);
	insert_base_defense_creep_colony_locations(blocked);
	
	if (unit_type == UnitTypes::Protoss_Pylon) {
		std::set<const BWEM::Base*> bases(base_state.controlled_and_planned_bases());
		
		TilePosition result = TilePositions::None;
		
		const BWEM::Base* start_base = base_state.start_base();
		if (bases.count(start_base) > 0) {
			result = place_pylon(blocked, resource_blocked, pylon_placement_start_location(start_base));
			bases.erase(start_base);
		}
		
		for (auto& base : bases) {
			if (result.isValid()) break;
			result = place_pylon(blocked, resource_blocked, pylon_placement_start_location(base));
		}
		
		return result;
	} else if (unit_type.requiresPsi()) {
		std::vector<TilePosition> pylon_positions = determine_completed_pylon_positions();
		TilePosition start_position = Broodwar->self()->getStartLocation();
		std::sort(pylon_positions.begin(), pylon_positions.end(), [start_position](TilePosition a,TilePosition b){
			return start_position.getApproxDistance(a) < start_position.getApproxDistance(b);
		});
		for (TilePosition pylon_position : pylon_positions) {
			const BWEM::Area* pylon_area = bwem_map.GetArea(pylon_position);
			for (int dy = -5; dy <= 4; dy++) {
				for (int dx = -8; dx <= 8; dx++) {
					TilePosition candidate = pylon_position + TilePosition(dx, dy);
					if (!candidate.isValid()) continue;
					if (!tile_in_controlled_area(candidate, pylon_area)) continue;
					if (check_power(pylon_position, unit_type, candidate) &&
						test_building_location(blocked, resource_blocked, unit_type, candidate)) return candidate;
				}
			}
		}
		return TilePositions::None;
	} else {
		std::set<const BWEM::Base*> bases(base_state.controlled_and_planned_bases());
		
		TilePosition result = TilePositions::None;
		
		const BWEM::Base* start_base = base_state.start_base();
		if (bases.count(start_base) > 0) {
			result = place_other_building(blocked, resource_blocked, start_base->Location(), unit_type);
			bases.erase(start_base);
		}
		
		for (auto& base : bases) {
			if (result.isValid()) break;
			result = place_other_building(blocked, resource_blocked, base->Location(), unit_type);
		}
		
		return result;
	}
}

TilePosition BuildingPlacementManager::place_base_defense_pylon(const BWEM::Base* base)
{
	TileGrid<bool> blocked;
	insert_building_locations(blocked);
	insert_base_locations(blocked);
	insert_specific_building_locations(blocked);
	insert_base_defense_photon_cannon_locations(blocked);
	insert_threatened_ground_locations(blocked);
	
	TileGrid<bool> resource_blocked;
	insert_resource_locations(resource_blocked);
	
	TilePosition tile_position = place_pylon(blocked, resource_blocked, pylon_placement_start_location(base));
	if (tile_position.isValid()) {
		for (auto& cannon_position : photon_cannon_positions_[base]) {
			if (check_power(tile_position, UnitTypes::Protoss_Photon_Cannon, cannon_position)) {
				return tile_position;
			}
		}
	}
	return TilePositions::None;
}

TilePosition BuildingPlacementManager::place_base_defense_photon_cannon(const BWEM::Base* base)
{
	TileGrid<bool> blocked;
	insert_building_locations(blocked);
	insert_base_locations(blocked);
	insert_specific_building_locations(blocked);
	insert_threatened_ground_locations(blocked);
	
	TileGrid<bool> resource_blocked;
	insert_resource_locations(resource_blocked);
	
	TileGrid<bool> power_grid = determine_power_grid(UnitTypes::Protoss_Photon_Cannon);
	
	for (auto& tile_position : photon_cannon_positions_[base]) {
		if (test_power_requirement(power_grid, UnitTypes::Protoss_Photon_Cannon, tile_position) &&
			test_building_location(blocked, resource_blocked, UnitTypes::Protoss_Photon_Cannon, tile_position, false)) {
			return tile_position;
		}
	}
	return TilePositions::None;
}

TilePosition BuildingPlacementManager::place_base_defense_missile_turret(const BWEM::Base* base)
{
	TileGrid<bool> blocked;
	insert_building_locations(blocked);
	insert_base_locations(blocked);
	insert_specific_building_locations(blocked);
	insert_threatened_ground_locations(blocked);
	
	TileGrid<bool> resource_blocked;
	insert_resource_locations(resource_blocked);
	
	for (auto& tile_position : missile_turret_positions_[base]) {
		if (test_building_location(blocked, resource_blocked, UnitTypes::Terran_Missile_Turret, tile_position, false)) {
			return tile_position;
		}
	}
	return TilePositions::None;
}

TilePosition BuildingPlacementManager::place_base_defense_creep_colony(const BWEM::Base* base)
{
	TileGrid<bool> blocked;
	insert_building_locations(blocked);
	insert_base_locations(blocked);
	insert_specific_building_locations(blocked);
	insert_threatened_ground_locations(blocked);
	
	TileGrid<bool> resource_blocked;
	insert_resource_locations(resource_blocked);
	
	auto it = creep_colony_positions_.find(base);
	if (it != creep_colony_positions_.end()) {
		TilePosition tile_position = it->second;
		if (test_building_location(blocked, resource_blocked, UnitTypes::Zerg_Creep_Colony, tile_position, false)) {
			return tile_position;
		}
	}
	return TilePositions::None;
}

TilePosition BuildingPlacementManager::pylon_placement_start_location(const BWEM::Base* base)
{
	TilePosition tile_position = pylon_positions_[base];
	for (int dy = 0; dy < UnitTypes::Protoss_Pylon.tileHeight(); dy++) {
		for (int dx = 0; dx < UnitTypes::Protoss_Pylon.tileWidth(); dx++) {
			if (!Broodwar->isBuildable(tile_position + TilePosition(dx, dy))) return base->Location();
		}
	}
	return tile_position;
}

TilePosition BuildingPlacementManager::place_pylon(const TileGrid<bool>& blocked,const TileGrid<bool>& resource_blocked,TilePosition start_location)
{
	const BWEM::Area* start_area = bwem_map.GetArea(start_location);
	std::vector<TilePosition> pylon_positions = determine_pylon_positions();
	
	std::queue<TilePosition> queue;
	queue.push(start_location);
	std::set<TilePosition> seen;
	seen.insert(start_location);
	
	while (!queue.empty()) {
		TilePosition candidate = queue.front();
		queue.pop();
		seen.insert(candidate);
		
		if (!candidate.isValid()) continue;
		if (!tile_in_controlled_area(candidate, start_area)) continue;
		
		if (test_building_location(blocked, resource_blocked, UnitTypes::Protoss_Pylon, candidate) &&
			test_distance_from_existing_pylons(pylon_positions, candidate)) return candidate;
		
		for (TilePosition delta : { TilePosition(-1, 0), TilePosition(1, 0), TilePosition(0, -1), TilePosition(0, 1) }) {
			TilePosition next = candidate + delta;
			if (seen.count(next) == 0) {
				queue.push(next);
				seen.insert(next);
			}
		}
	}
	
	return TilePositions::None;
}

TilePosition BuildingPlacementManager::place_other_building(const TileGrid<bool>& blocked,const TileGrid<bool>& resource_blocked,TilePosition start_location,UnitType type)
{
	const BWEM::Area* start_area = bwem_map.GetArea(start_location);
	
	std::queue<TilePosition> queue;
	queue.push(start_location);
	std::set<TilePosition> seen;
	seen.insert(start_location);
	
	while (!queue.empty()) {
		TilePosition candidate = queue.front();
		queue.pop();
		seen.insert(candidate);
		
		if (!candidate.isValid()) continue;
		if (!tile_in_controlled_area(candidate, start_area)) continue;
		
		if (test_building_location(blocked, resource_blocked, type, candidate)) return candidate;
		
		for (TilePosition delta : { TilePosition(-1, 0), TilePosition(1, 0), TilePosition(0, -1), TilePosition(0, 1) }) {
			TilePosition next = candidate + delta;
			if (seen.count(next) == 0) {
				queue.push(next);
				seen.insert(next);
			}
		}
	}
	
	return TilePositions::None;
}

std::vector<TilePosition> BuildingPlacementManager::determine_pylon_positions()
{
	std::vector<TilePosition> result;
	
	for (auto& unit : Broodwar->self()->getUnits()) {
		if (unit->getType() == UnitTypes::Protoss_Pylon) result.push_back(unit->getTilePosition());
	}
	
	for (auto& entry : worker_manager.worker_map()) {
		const Worker& worker = entry.second;
		if (worker.order()->building_type() == UnitTypes::Protoss_Pylon) {
			result.push_back(worker.order()->building_position());
		}
	}
	
	return result;
}

std::vector<TilePosition> BuildingPlacementManager::determine_completed_pylon_positions()
{
	std::vector<TilePosition> result;
	
	for (auto& unit : Broodwar->self()->getUnits()) {
		if (unit->getType() == UnitTypes::Protoss_Pylon && unit->isCompleted()) result.push_back(unit->getTilePosition());
	}
	
	return result;
}

bool BuildingPlacementManager::test_distance_from_existing_pylons(const std::vector<TilePosition>& pylon_positions,TilePosition tile_position)
{
	for (auto& pylon_position : pylon_positions) {
		int dx = tile_position.x - pylon_position.x;
		int dy = tile_position.y - pylon_position.y;
		if (abs(dx) < 6 && abs(dy) < 5) return false;
	}
	return true;
}

bool BuildingPlacementManager::tile_in_controlled_area(TilePosition tile_position,const BWEM::Area* start_area)
{
	const std::set<const BWEM::Area*>& areas = base_state.controlled_areas();
	
	const BWEM::Area* area = bwem_map.GetArea(tile_position);
	if (area != nullptr) {
		return area == start_area || areas.count(area) > 0;
	} else {
		WalkPosition walk_position(tile_position);
		for (int dy = 0; dy < 4; dy++) {
			for (int dx = 0; dx < 4; dx++) {
				area = bwem_map.GetArea(walk_position + WalkPosition(dx, dy));
				if (area != nullptr && (area == start_area || areas.count(area) > 0)) return true;
			}
		}
		return false;
	}
}

void BuildingPlacementManager::insert_building_location(TileGrid<bool>& blocked,UnitType unit_type,TilePosition base_position)
{
	for (int dy = 0; dy < unit_type.tileHeight(); dy++) {
		for (int dx = 0; dx < unit_type.tileWidth(); dx++) {
			blocked.set(base_position + TilePosition(dx, dy), true);
		}
	}
	if (unit_type.canBuildAddon()) {
		for (int dy = 0; dy < 2; dy++) {
			for (int dx = 0; dx < 2; dx++) {
				blocked.set(base_position + TilePosition(unit_type.tileWidth() + dx, unit_type.tileHeight() - 2 + dy), true);
			}
		}
	}
}

void BuildingPlacementManager::remove_building_location(TileGrid<bool>& blocked,UnitType unit_type,TilePosition base_position)
{
	for (int dy = 0; dy < unit_type.tileHeight(); dy++) {
		for (int dx = 0; dx < unit_type.tileWidth(); dx++) {
			blocked.set(base_position + TilePosition(dx, dy), false);
		}
	}
}

void BuildingPlacementManager::insert_building_location_with_padding(TileGrid<bool>& blocked,UnitType unit_type,TilePosition base_position,int padding)
{
	for (int dy = -padding; dy < unit_type.tileHeight() + padding; dy++) {
		for (int dx = -padding; dx < unit_type.tileWidth() + padding; dx++) {
			blocked.set(base_position + TilePosition(dx, dy), true);
		}
	}
}

bool BuildingPlacementManager::test_power_requirement(const TileGrid<bool>& power_grid,UnitType unit_type,TilePosition base_position)
{
	return !unit_type.requiresPsi() || power_grid.get(base_position);
}

bool BuildingPlacementManager::test_building_location(const TileGrid<bool>& blocked,const TileGrid<bool>& resource_blocked,UnitType unit_type,TilePosition base_position,bool group_check)
{
	for (int dy = 0; dy < unit_type.tileHeight(); dy++) {
		for (int dx = 0; dx < unit_type.tileWidth(); dx++) {
			TilePosition tile_position = base_position + TilePosition(dx, dy);
			if (!Broodwar->isBuildable(tile_position) ||
				(Broodwar->hasCreep(tile_position) != unit_type.requiresCreep() && !unit_type.isResourceDepot())) return false;
			if (blocked.get(tile_position) || resource_blocked.get(tile_position)) return false;
		}
	}
	if (unit_type.canBuildAddon()) {
		for (int dy = 0; dy < 2; dy++) {
			for (int dx = 0; dx < 2; dx++) {
				TilePosition tile_position = base_position + TilePosition(unit_type.tileWidth() + dx, unit_type.tileHeight() - 2 + dy);
				if (!Broodwar->isBuildable(tile_position) ||
					(Broodwar->hasCreep(tile_position) != unit_type.requiresCreep() && !unit_type.isResourceDepot())) return false;
				if (blocked.get(tile_position) || resource_blocked.get(tile_position)) return false;
			}
		}
	}
	
	if (group_check) {
		std::set<TilePosition> group = determine_connected_tiles(blocked, unit_type, base_position);
		if (unit_type != UnitTypes::Protoss_Photon_Cannon && group.size() >= 8 * 6) return false;
		std::set<TilePosition> border = determine_border(group);
		if (!is_connected(border)) return false;
		for (auto location : border) if (!walkability_grid.is_terrain_walkable(location)) return false;
	}
	
	return true;
}

std::set<TilePosition> BuildingPlacementManager::determine_border(const std::set<TilePosition>& positions)
{
	std::set<TilePosition> result;
	
	for (TilePosition position : positions) {
		for (TilePosition delta : { TilePosition(-1, -1), TilePosition(0, -1), TilePosition(1, -1),
			TilePosition(-1, 0), TilePosition(1, 0),
			TilePosition(-1, 1), TilePosition(0, 1), TilePosition(1, 1) }) {
				TilePosition tile_position = position + delta;
				if (positions.count(tile_position) == 0) result.insert(tile_position);
			}
	}
	
	return result;
}

std::set<TilePosition> BuildingPlacementManager::determine_connected_tiles(const TileGrid<bool>& blocked,UnitType unit_type,TilePosition base_position)
{
	std::set<TilePosition> done;
	std::queue<TilePosition> queue;
	for (int dy = 0; dy < unit_type.tileHeight(); dy++) {
		for (int dx = 0; dx < unit_type.tileWidth(); dx++) {
			TilePosition tile_position = base_position + TilePosition(dx, dy);
			queue.push(tile_position);
			done.insert(tile_position);
		}
	}
	if (unit_type.canBuildAddon()) {
		for (int dy = 0; dy < 2; dy++) {
			for (int dx = 0; dx < 2; dx++) {
				TilePosition tile_position = base_position + TilePosition(unit_type.tileWidth() + dx, unit_type.tileHeight() - 2 + dy);
				queue.push(tile_position);
				done.insert(tile_position);
			}
		}
	}
	
	while (!queue.empty()) {
		TilePosition current = queue.front();
		queue.pop();
		
		for (TilePosition delta : { TilePosition(-1, -1), TilePosition(0, -1), TilePosition(1, -1),
			TilePosition(-1, 0), TilePosition(1, 0),
			TilePosition(-1, 1), TilePosition(0, 1), TilePosition(1, 1) }) {
				TilePosition tile_position = current + delta;
				if (blocked.get(tile_position) && done.count(tile_position) == 0) {
					queue.push(tile_position);
					done.insert(tile_position);
				}
			}
	}
	
	return done;
}

bool BuildingPlacementManager::is_connected(const std::set<TilePosition>& positions)
{
	if (positions.empty()) return true;
	std::set<TilePosition> done;
	std::queue<TilePosition> queue;
	TilePosition first = *(positions.begin());
	done.insert(first);
	queue.push(first);
	
	while (!queue.empty()) {
		TilePosition current = queue.front();
		queue.pop();
		
		for (TilePosition delta : { TilePosition(-1, -1), TilePosition(0, -1), TilePosition(1, -1),
			TilePosition(-1, 0), TilePosition(1, 0),
			TilePosition(-1, 1), TilePosition(0, 1), TilePosition(1, 1) }) {
				TilePosition tile_position = current + delta;
				if (positions.count(tile_position) > 0 && done.count(tile_position) == 0) {
					queue.push(tile_position);
					done.insert(tile_position);
				}
			}
	}
	
	return done.size() == positions.size();
}

void BuildingPlacementManager::draw()
{
	for (auto& entry : pylon_positions_) {
		Rect rect(UnitTypes::Protoss_Pylon, entry.second, true);
		rect.draw(Colors::Orange);
	}
	for (auto& entry : photon_cannon_positions_) {
		for (auto& tile_position : entry.second) {
			Rect rect(UnitTypes::Protoss_Photon_Cannon, tile_position, true);
			rect.draw(Colors::Orange);
		}
	}
	for (auto& entry : missile_turret_positions_) {
		for (auto& tile_position : entry.second) {
			Rect rect(UnitTypes::Terran_Missile_Turret, tile_position, true);
			rect.draw(Colors::Orange);
		}
	}
	for (auto& entry : creep_colony_positions_) {
		Rect rect(UnitTypes::Zerg_Creep_Colony, entry.second, true);
		rect.draw(Colors::Orange);
	}
	for (auto& entry : specific_positions_) {
		UnitType type = entry.first;
		for (auto& tile_position : entry.second) {
			Rect rect(type, tile_position, true);
			rect.draw(Colors::Orange);
		}
	}
}

void BuildingPlacementManager::insert_building_locations(TileGrid<bool>& blocked)
{
	for (Unit unit : Broodwar->self()->getUnits()) {
		UnitType unit_type = unit->getType();
		if (unit_type.isBuilding()) insert_building_location(blocked, unit_type, unit->getTilePosition());
		if (unit_type.isResourceDepot() && unit_type.getRace() == Races::Zerg) {
			for (int dx = 0; dx < unit_type.tileWidth(); dx++) {
				blocked.set(unit->getTilePosition() + TilePosition(dx, unit_type.tileHeight()), true);
			}
			for (int dy = 0; dy < unit_type.tileHeight() + 1; dy++) {
				blocked.set(unit->getTilePosition() + TilePosition(-1, dy), true);
				blocked.set(unit->getTilePosition() + TilePosition(unit_type.tileWidth(), dy), true);
			}
		}
	}
	
	for (auto& neutral_unit : information_manager.neutral_units()) {
		if (!neutral_unit->flying && !neutral_unit->type.isMineralField() && neutral_unit->type != UnitTypes::Resource_Vespene_Geyser) {
			insert_building_location(blocked, neutral_unit->type, neutral_unit->tile_position());
		}
	}
	
	for (auto& entry : worker_manager.worker_map()) {
		const Worker& worker = entry.second;
		UnitType unit_type = worker.order()->building_type();
		if (unit_type != UnitTypes::None) {
			insert_building_location(blocked, unit_type, worker.order()->building_position());
		}
	}
}

void BuildingPlacementManager::insert_base_locations(TileGrid<bool>& blocked)
{
	for (auto& base : base_state.bases()) {
		insert_building_location(blocked, UnitTypes::Protoss_Nexus, base->Location());
	}
}

void BuildingPlacementManager::insert_padded_resource_locations(TileGrid<bool>& blocked,bool resource_depot)
{
	int padding = resource_depot ? 3 : 2;
	
	for (Unit unit : Broodwar->self()->getUnits()) {
		UnitType unit_type = unit->getType();
		if (unit_type.isRefinery()) {
			insert_building_location_with_padding(blocked, unit_type, unit->getTilePosition(), padding);
		}
	}
	
	for (auto& neutral_unit : information_manager.neutral_units()) {
		if (neutral_unit->type.isMineralField() || neutral_unit->type == UnitTypes::Resource_Vespene_Geyser) {
			insert_building_location_with_padding(blocked, neutral_unit->type, neutral_unit->tile_position(), padding);
		}
	}
}

void BuildingPlacementManager::insert_resource_locations(TileGrid<bool>& blocked)
{
	for (Unit unit : Broodwar->self()->getUnits()) {
		UnitType unit_type = unit->getType();
		if (unit_type.isRefinery()) {
			insert_building_location(blocked, unit_type, unit->getTilePosition());
		}
	}
	
	for (auto& neutral_unit : information_manager.neutral_units()) {
		if (neutral_unit->type.isMineralField() || neutral_unit->type == UnitTypes::Resource_Vespene_Geyser) {
			insert_building_location(blocked, neutral_unit->type, neutral_unit->tile_position());
		}
	}
}

void BuildingPlacementManager::insert_specific_building_locations(TileGrid<bool>& blocked)
{
	for (auto& entry : specific_positions_) {
		UnitType unit_type = entry.first;
		for (auto& tile_position : entry.second) {
			insert_building_location(blocked, unit_type, tile_position);
		}
	}
}

void BuildingPlacementManager::insert_base_defense_photon_cannon_locations(TileGrid<bool>& blocked)
{
	for (auto& entry : photon_cannon_positions_) {
		for (auto& tile_position : entry.second) {
			insert_building_location(blocked, UnitTypes::Protoss_Photon_Cannon, tile_position);
		}
	}
}

void BuildingPlacementManager::insert_base_defense_missile_turret_locations(TileGrid<bool>& blocked)
{
	for (auto& entry : missile_turret_positions_) {
		for (auto& tile_position : entry.second) {
			insert_building_location(blocked, UnitTypes::Terran_Missile_Turret, tile_position);
		}
	}
}

void BuildingPlacementManager::insert_base_defense_creep_colony_locations(TileGrid<bool>& blocked)
{
	for (auto& entry : creep_colony_positions_) {
		insert_building_location(blocked, UnitTypes::Zerg_Creep_Colony, entry.second);
	}
}

void BuildingPlacementManager::insert_threatened_ground_locations(TileGrid<bool>& blocked)
{
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			TilePosition tile_position(x, y);
			if (threat_grid.ground_threat(tile_position)) blocked.set(tile_position, true);
		}
	}
}

void BuildingPlacementManager::insert_neutral_creep(TileGrid<bool>& blocked)
{
	for (auto& neutral_unit : information_manager.neutral_units()) {
		std::unordered_set<FastTilePosition> creep_tiles = creep_spread(neutral_unit->type, neutral_unit->position);
		for (FastTilePosition tile_position : creep_tiles) {
			blocked.set(tile_position, true);
		}
	}
}

TileGrid<bool> BuildingPlacementManager::determine_power_grid(UnitType unit_type)
{
	TileGrid<bool> result;
	
	if (unit_type.requiresPsi()) {
		const std::set<TilePosition>* grid = nullptr;
		if (unit_type.tileWidth() == 2 && unit_type.tileHeight() == 2) {
			grid = &power_grid_2x2_;
		} else if (unit_type.tileWidth() == 3 && unit_type.tileHeight() == 2) {
			grid = &power_grid_3x2_;
		} else if (unit_type.tileWidth() == 4 && unit_type.tileHeight() == 3) {
			grid = &power_grid_4x3_;
		}
		
		if (grid != nullptr) {
			for (Unit unit : Broodwar->self()->getUnits()) {
				if (unit->getType() == UnitTypes::Protoss_Pylon && unit->isCompleted()) {
					for (TilePosition tile_position : *grid) {
						result.set(tile_position + unit->getTilePosition(), true);
					}
				}
			}
		}
	}
	
	return result;
}

bool BuildingPlacementManager::check_power(TilePosition pylon_position,UnitType building_type,TilePosition building_position)
{
	if (!building_type.requiresPsi()) return true;
	const std::set<TilePosition>* grid = nullptr;
	if (building_type.tileWidth() == 2 && building_type.tileHeight() == 2) {
		grid = &power_grid_2x2_;
	} else if (building_type.tileWidth() == 3 && building_type.tileHeight() == 2) {
		grid = &power_grid_3x2_;
	} else if (building_type.tileWidth() == 4 && building_type.tileHeight() == 3) {
		grid = &power_grid_4x3_;
	}
	if (grid == nullptr) return false;
	return grid->count(building_position - pylon_position) > 0;
}

TilePosition BuildingPlacementManager::calculate_proxy_barracks_position()
{
	const int barracks_width = UnitTypes::Terran_Barracks.tileWidth();
	const int barracks_height = UnitTypes::Terran_Barracks.tileHeight();
	
	struct ProxyPosition
	{
		TilePosition barracks_position;
		int distance = 0;
	};
	
	std::set<const BWEM::Area*> non_start_areas;
	for (auto& base : base_state.bases()) if (!base->Starting()) non_start_areas.insert(base->GetArea());
	
	TileGrid<bool> blocked;
	insert_unbuildable_nonarea_locations(blocked, non_start_areas);
	insert_building_locations(blocked);
	insert_resource_locations(blocked);
	insert_neutral_creep(blocked);
	
	std::vector<ProxyPosition> candidate_proxy_positions;
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			TilePosition tile_position(x, y);
			if (rectangle_buildable_for_building_with_clearance(tile_position, UnitTypes::Terran_Barracks, blocked)) {
				Position position = center_position_for(UnitTypes::Terran_Barracks, tile_position);
				int distance = maximum_distance_from_possible_opponent_starting_bases(position);
				if (distance > 0) {
					ProxyPosition candidate { tile_position, distance };
					candidate_proxy_positions.push_back(candidate);
				}
			}
		}
	}
	
	ProxyPosition proxy_position = smallest_priority(candidate_proxy_positions, [](const ProxyPosition& proxy_position){
		return proxy_position.distance;
	});
	
	if (proxy_position.distance > 0) {
		specific_positions_[UnitTypes::Terran_Barracks].push_back(proxy_position.barracks_position);
		proxy_barracks_position_ = proxy_position.barracks_position;
		return proxy_position.barracks_position;
	} else {
		return TilePositions::None;
	}
}

TilePosition BuildingPlacementManager::calculate_proxy_gateway_position()
{
	const int gateway_width = UnitTypes::Protoss_Gateway.tileWidth();
	const int gateway_height = UnitTypes::Protoss_Gateway.tileHeight();
	const int pylon_width = UnitTypes::Protoss_Pylon.tileWidth();
	const int pylon_height = UnitTypes::Protoss_Pylon.tileHeight();
	
	struct ProxyPosition
	{
		TilePosition pylon_position;
		TilePosition first_gateway_position;
		TilePosition second_gateway_position;
		int distance = 0;
	};
	
	std::set<const BWEM::Area*> non_start_areas;
	for (auto& base : base_state.bases()) if (!base->Starting()) non_start_areas.insert(base->GetArea());
	
	TileGrid<bool> blocked;
	insert_unbuildable_nonarea_locations(blocked, non_start_areas);
	insert_building_locations(blocked);
	insert_resource_locations(blocked);
	insert_neutral_creep(blocked);
	
	std::vector<ProxyPosition> deltas{
		{ TilePosition(gateway_width, 0), TilePosition(0, 0), TilePosition(gateway_width + pylon_width, 0) },
		{ TilePosition(0, gateway_height), TilePosition(0, 0), TilePosition(0, gateway_height + pylon_height) },
		{ TilePosition(gateway_width - pylon_width, gateway_height - pylon_height), TilePosition(0, gateway_height), TilePosition(gateway_width, 0) },
		{ TilePosition(gateway_width, gateway_height), TilePosition(0, gateway_height), TilePosition(gateway_width, 0) },
		{ TilePosition(gateway_width, gateway_height), TilePosition(0, 0), TilePosition(gateway_width + pylon_width, gateway_height + pylon_height) },
		{ TilePosition(gateway_width, gateway_height), TilePosition(gateway_width + pylon_width, 0), TilePosition(0, gateway_height + pylon_height) }
	};
	
	std::vector<ProxyPosition> candidate_proxy_positions;
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			TilePosition tile_position(x, y);
			for (auto& delta : deltas) {
				ProxyPosition candidate{
					tile_position + delta.pylon_position,
					tile_position + delta.first_gateway_position,
					tile_position + delta.second_gateway_position
				};
				if (rectangle_buildable_for_building_with_clearance(candidate.pylon_position, UnitTypes::Protoss_Pylon, blocked) &&
					rectangle_buildable_for_building_with_clearance(candidate.first_gateway_position, UnitTypes::Protoss_Gateway, blocked) &&
					rectangle_buildable_for_building_with_clearance(candidate.second_gateway_position, UnitTypes::Protoss_Gateway, blocked)) {
					Position position = center_position_for(UnitTypes::Protoss_Pylon, candidate.pylon_position);
					int distance = maximum_distance_from_possible_opponent_starting_bases(position);
					if (distance > 0) {
						candidate.distance = distance;
						candidate_proxy_positions.push_back(candidate);
					}
				}
			}
		}
	}
	
	ProxyPosition proxy_position = smallest_priority(candidate_proxy_positions, [](const ProxyPosition& proxy_position){
		return proxy_position.distance;
	});
	if (proxy_position.distance > 0) {
		specific_positions_[UnitTypes::Protoss_Pylon].push_back(proxy_position.pylon_position);
		specific_positions_[UnitTypes::Protoss_Gateway].push_back(proxy_position.first_gateway_position);
		specific_positions_[UnitTypes::Protoss_Gateway].push_back(proxy_position.second_gateway_position);
		proxy_pylon_position_ = proxy_position.pylon_position;
		return proxy_position.pylon_position;
	} else {
		return TilePositions::None;
	}
}

void BuildingPlacementManager::calculate_two_gateways_near_choke_position()
{
	const int gateway_width = UnitTypes::Protoss_Gateway.tileWidth();
	const int gateway_height = UnitTypes::Protoss_Gateway.tileHeight();
	const int pylon_width = UnitTypes::Protoss_Pylon.tileWidth();
	const int pylon_height = UnitTypes::Protoss_Pylon.tileHeight();
	
	struct TwoGatePosition
	{
		TilePosition pylon_position;
		TilePosition first_gateway_position;
		TilePosition second_gateway_position;
		int distance = 0;
	};
	
	std::set<const BWEM::Area*> component_areas = base_state.connected_areas(base_state.main_base()->GetArea(), base_state.controlled_and_planned_areas());
	Border border(component_areas);
	if (border.chokepoints().size() == 1) {
		const BWEM::ChokePoint* chokepoint = chokepoint = *(border.chokepoints().begin());
		Position choke_center = chokepoint_center(chokepoint);
		
		TileGrid<bool> blocked;
		insert_unbuildable_nonarea_locations(blocked, base_state.controlled_and_planned_areas());
		insert_building_locations(blocked);
		insert_resource_locations(blocked);
		insert_neutral_creep(blocked);
		
		std::vector<TwoGatePosition> deltas{
			{ TilePosition(gateway_width, 0), TilePosition(0, 0), TilePosition(gateway_width + pylon_width, 0) },
			{ TilePosition(0, gateway_height), TilePosition(0, 0), TilePosition(0, gateway_height + pylon_height) },
			{ TilePosition(gateway_width - pylon_width, gateway_height - pylon_height), TilePosition(0, gateway_height), TilePosition(gateway_width, 0) },
			{ TilePosition(gateway_width, gateway_height), TilePosition(0, gateway_height), TilePosition(gateway_width, 0) },
			{ TilePosition(gateway_width, gateway_height), TilePosition(0, 0), TilePosition(gateway_width + pylon_width, gateway_height + pylon_height) },
			{ TilePosition(gateway_width, gateway_height), TilePosition(gateway_width + pylon_width, 0), TilePosition(0, gateway_height + pylon_height) }
		};
		
		std::vector<TwoGatePosition> candidate_positions;
		for (int y = 0; y < Broodwar->mapHeight(); y++) {
			for (int x = 0; x < Broodwar->mapWidth(); x++) {
				TilePosition tile_position(x, y);
				for (auto& delta : deltas) {
					TwoGatePosition candidate{
						tile_position + delta.pylon_position,
						tile_position + delta.first_gateway_position,
						tile_position + delta.second_gateway_position
					};
					if (rectangle_buildable_for_building_with_clearance(candidate.pylon_position, UnitTypes::Protoss_Pylon, blocked, 2) &&
						rectangle_buildable_for_building_with_clearance(candidate.first_gateway_position, UnitTypes::Protoss_Gateway, blocked, 2) &&
						rectangle_buildable_for_building_with_clearance(candidate.second_gateway_position, UnitTypes::Protoss_Gateway, blocked, 2)) {
						int first_gateway_distance = calculate_distance(UnitTypes::Protoss_Gateway, center_position_for(UnitTypes::Protoss_Gateway, candidate.first_gateway_position), choke_center);
						int second_gateway_distance = calculate_distance(UnitTypes::Protoss_Gateway, center_position_for(UnitTypes::Protoss_Gateway, candidate.second_gateway_position), choke_center);
						candidate.distance = first_gateway_distance + second_gateway_distance;
						candidate_positions.push_back(candidate);
					}
				}
			}
		}
		
		TwoGatePosition two_gate_position = smallest_priority(candidate_positions, [](const TwoGatePosition& two_gate_position){
			return two_gate_position.distance;
		});
		if (two_gate_position.distance > 0) {
			specific_positions_[UnitTypes::Protoss_Pylon].push_back(two_gate_position.pylon_position);
			specific_positions_[UnitTypes::Protoss_Gateway].push_back(two_gate_position.first_gateway_position);
			specific_positions_[UnitTypes::Protoss_Gateway].push_back(two_gate_position.second_gateway_position);
		}
	}
}

TilePosition BuildingPlacementManager::calculate_gateway_first_expand_position()
{
	if (base_state.natural_base() == nullptr) return TilePositions::None;
	
	Position base_position = Positions::None;
	Position center_position = Positions::None;
	std::set<const BWEM::Area*> areas = determine_gateway_first_areas_and_positions(base_position, center_position);
	
	TileGrid<bool> blocked;
	insert_unbuildable_nonarea_locations(blocked, areas);
	insert_building_locations(blocked);
	insert_padded_resource_locations(blocked);
	insert_base_locations(blocked);
	insert_base_defense_photon_cannon_locations(blocked);
	insert_neutral_creep(blocked);
	
	struct ProxyPosition
	{
		TilePosition pylon_position;
		TilePosition gateway_position;
		int distance = 0;
	};
	
	std::vector<ProxyPosition> candidate_proxy_positions;
	
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			TilePosition gateway_position(x, y);
			if (rectangle_buildable_for_building_with_clearance(gateway_position, UnitTypes::Protoss_Gateway, blocked)) {
				insert_building_location(blocked, UnitTypes::Protoss_Gateway, gateway_position);
				std::vector<TilePosition> pylon_positions;
				for (int yp = y - 8; yp <= y + 8; yp++) {
					for (int xp = x - 8; xp <= x + 8; xp++) {
						TilePosition pylon_position{xp, yp};
						if (check_power(pylon_position, UnitTypes::Protoss_Gateway, gateway_position) &&
							rectangle_buildable_for_building_with_clearance(pylon_position, UnitTypes::Protoss_Pylon, blocked)) {
							pylon_positions.push_back(pylon_position);
						}
					}
				}
				TilePosition pylon_position = smallest_priority(pylon_positions, [base_position](auto tile_position){
					Position position = center_position_for(UnitTypes::Protoss_Pylon, tile_position);
					return ground_distance(position, base_position);
				}, TilePositions::None);
				if (pylon_position.isValid()) {
					Position position = center_position_for(UnitTypes::Protoss_Pylon, pylon_position);
					candidate_proxy_positions.push_back({
						pylon_position,
						gateway_position,
						ground_distance(center_position, center_position_for(UnitTypes::Protoss_Gateway, gateway_position))
					});
				}
				remove_building_location(blocked, UnitTypes::Protoss_Gateway, gateway_position);
			}
		}
	}
	
	ProxyPosition proxy_position = smallest_priority(candidate_proxy_positions, [](const ProxyPosition& proxy_position){
		return proxy_position.distance;
	});
	if (proxy_position.distance > 0) {
		specific_positions_[UnitTypes::Protoss_Pylon].push_back(proxy_position.pylon_position);
		specific_positions_[UnitTypes::Protoss_Gateway].push_back(proxy_position.gateway_position);
		return proxy_position.pylon_position;
	} else {
		return TilePositions::None;
	}
}

TilePosition BuildingPlacementManager::calculate_photons_cannons_near_choke_position(unsigned int cannon_count)
{
	std::set<const BWEM::Area*> component_areas = base_state.connected_areas(base_state.main_base()->GetArea(), base_state.controlled_and_planned_areas());
	Border border(component_areas);
	if (border.chokepoints().size() == 1) {
		const BWEM::ChokePoint* chokepoint = chokepoint = *(border.chokepoints().begin());
		Position choke_position = chokepoint_center(chokepoint);
	
			TileGrid<bool> blocked;
			insert_unbuildable_nonarea_locations(blocked, base_state.controlled_areas());
			insert_building_locations(blocked);
			insert_padded_resource_locations(blocked);
			insert_base_locations(blocked);
			insert_base_defense_photon_cannon_locations(blocked);
			
			struct ProxyPosition
			{
				TilePosition pylon_position;
				int distance;
			};
			
			std::vector<ProxyPosition> candidate_proxy_positions;
			
			for (int y = 0; y < Broodwar->mapHeight(); y++) {
				for (int x = 0; x < Broodwar->mapWidth(); x++) {
					TilePosition pylon_position{x, y};
					if (rectangle_buildable_for_building_with_clearance(pylon_position, UnitTypes::Protoss_Pylon, blocked)) {
						int distance = center_position_for(UnitTypes::Protoss_Pylon, pylon_position).getApproxDistance(choke_position);
						candidate_proxy_positions.push_back(ProxyPosition{pylon_position, distance});
					}
				}
			}
			
			struct ProxyPositionOrder
			{
				bool operator()(const ProxyPosition& a,const ProxyPosition& b) const {
					return std::make_tuple(a.distance, a.pylon_position) < std::make_tuple(b.distance, b.pylon_position);
				};
			};
			std::sort(candidate_proxy_positions.begin(), candidate_proxy_positions.end(), ProxyPositionOrder());
			
			for (auto& candidate : candidate_proxy_positions) {
				TileGrid<bool> blocked_inner(blocked);
				TilePosition pylon_position = candidate.pylon_position;
				insert_building_location(blocked_inner, UnitTypes::Protoss_Pylon, pylon_position);
				std::vector<TilePosition> cannon_positions;
				std::vector<TilePosition> candidate_cannon_positions;
				for (unsigned int i = 0; i < cannon_count; i++) {
					for (int yc = pylon_position.y - 8; yc <= pylon_position.y + 8; yc++) {
						for (int xc = pylon_position.x - 8; xc <= pylon_position.x + 8; xc++) {
							TilePosition cannon_position{xc, yc};
							if (check_power(pylon_position, UnitTypes::Protoss_Photon_Cannon, cannon_position) &&
								rectangle_buildable_for_building_with_clearance(cannon_position, UnitTypes::Protoss_Photon_Cannon, blocked_inner)) {
								candidate_cannon_positions.push_back(cannon_position);
							}
						}
					}
					TilePosition cannon_position = smallest_priority(candidate_cannon_positions, [choke_position](auto& cannon_position){
						return calculate_distance(UnitTypes::Protoss_Photon_Cannon, center_position_for(UnitTypes::Protoss_Photon_Cannon, cannon_position), choke_position);
					});
					if (cannon_position.isValid()) {
						cannon_positions.push_back(cannon_position);
						insert_building_location(blocked_inner, UnitTypes::Protoss_Photon_Cannon, cannon_position);
					} else {
						break;
					}
					candidate_cannon_positions.clear();
				}
				if (cannon_positions.size() == cannon_count) {
					specific_positions_[UnitTypes::Protoss_Pylon].push_back(candidate.pylon_position);
					for (auto& cannon_position : cannon_positions) specific_positions_[UnitTypes::Protoss_Photon_Cannon].push_back(cannon_position);
					return candidate.pylon_position;
				}
			}
	}
	
	return TilePositions::None;
}

bool BuildingPlacementManager::calculate_forge_fast_expand_position()
{
	WallPlacement::FFEPlacer placer;
	return placer.place_ffe();
}

int BuildingPlacementManager::calculate_defense_creep_colony_positions(const BWEM::Base* base,int count_requested)
{
	std::set<const BWEM::Area*> component_areas = base_state.connected_areas(base->GetArea(), base_state.controlled_and_planned_areas());
	Border border(component_areas);
	const BWEM::ChokePoint* chokepoint = border.largest_chokepoint_with_area(base->GetArea());
	
	FastPosition choke_center = (chokepoint != nullptr) ? chokepoint_center(chokepoint) : Positions::None;
	FastPosition base_center = base->Center();
	int choke_base_distance = (chokepoint != nullptr) ? choke_center.getApproxDistance(base_center) : 0;
	
	std::set<const BWEM::Area*> base_area_set;
	base_area_set.insert(base->GetArea());
	
	TileGrid<bool> blocked;
	insert_unbuildable_nonarea_locations(blocked, base_area_set);
	insert_building_locations(blocked);
	insert_padded_resource_locations(blocked);
	insert_base_locations(blocked);
	
	struct ColonyPosition
	{
		FastTilePosition tile_position;
		int distance;
		
		bool operator<(const ColonyPosition& o) const
		{
			return std::make_tuple(distance, tile_position) < std::make_tuple(o.distance, o.tile_position);
		}
	};
	
	std::vector<ColonyPosition> candidate_positions;
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			FastTilePosition tile_position(x, y);
			if (rectangle_buildable_for_building_with_clearance(tile_position, UnitTypes::Zerg_Creep_Colony, blocked, 0)) {
				FastPosition position = center_position_for(UnitTypes::Zerg_Creep_Colony, tile_position);
				int base_distance = position.getApproxDistance(base_center);
				if (base_distance >= 128 &&
					(!choke_center.isValid() || position.getApproxDistance(choke_center) < choke_base_distance)) {
					candidate_positions.push_back(ColonyPosition{ tile_position, base_distance });
				}
			}
		}
	}
	
	std::sort(candidate_positions.begin(), candidate_positions.end());
	
	TileGrid<bool> building_blocked;
	insert_building_locations(building_blocked);
	insert_base_locations(building_blocked);
	
	int count_placed = 0;
	for (auto& candidate_position : candidate_positions) {
		if (count_placed >= count_requested) break;
		if (test_building_location(building_blocked, blocked, UnitTypes::Zerg_Creep_Colony, candidate_position.tile_position)) {
			specific_positions_[UnitTypes::Zerg_Creep_Colony].push_back(candidate_position.tile_position);
			insert_building_location(blocked, UnitTypes::Zerg_Creep_Colony, candidate_position.tile_position);
			insert_building_location(building_blocked, UnitTypes::Zerg_Creep_Colony, candidate_position.tile_position);
			count_placed++;
		}
	}
	return count_placed;
}

bool BuildingPlacementManager::calculate_macro_hatch_position(const BWEM::Base* base)
{
	std::set<const BWEM::Area*> component_areas = base_state.connected_areas(base->GetArea(), base_state.controlled_and_planned_areas());
	Border border(component_areas);
	const BWEM::ChokePoint* chokepoint = border.largest_chokepoint_with_area(base->GetArea());
	FastPosition near_position;
	if (chokepoint != nullptr) {
		near_position = chokepoint_center(chokepoint);
	} else {
		near_position = base->Center();
	}
	
	std::set<const BWEM::Area*> base_area_set;
	base_area_set.insert(base->GetArea());
	
	TileGrid<bool> blocked;
	insert_unbuildable_nonarea_locations(blocked, base_area_set);
	insert_building_locations(blocked);
	insert_padded_resource_locations(blocked, true);
	insert_base_locations(blocked);
	
	struct HatcheryPosition
	{
		FastTilePosition tile_position;
		int distance = 0;
	};
	
	std::vector<HatcheryPosition> candidate_positions;
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			FastTilePosition tile_position(x, y);
			if (rectangle_buildable_for_building_with_clearance(tile_position, UnitTypes::Zerg_Hatchery, blocked)) {
				FastPosition position = center_position_for(UnitTypes::Zerg_Hatchery, tile_position);
				int distance = position.getApproxDistance(near_position);
				if (chokepoint == nullptr || distance >= 128) {
					candidate_positions.push_back(HatcheryPosition{ tile_position, distance });
				}
			}
		}
	}
	
	HatcheryPosition hatchery_position = smallest_priority(candidate_positions, [](auto& hatchery_position){
		return hatchery_position.distance;
	});
	
	bool result = false;
	if (hatchery_position.distance > 0) {
		specific_positions_[UnitTypes::Zerg_Hatchery].push_back(hatchery_position.tile_position);
	}
	return result;
}

std::vector<TilePosition> BuildingPlacementManager::determine_second_gateway_positions(const TileGrid<bool>& blocked,TilePosition first_gateway_position)
{
	std::vector<TilePosition> all_positions;
	
	int x1 = first_gateway_position.x - UnitTypes::Protoss_Gateway.tileWidth();
	int y1 = first_gateway_position.y - UnitTypes::Protoss_Gateway.tileHeight();
	int x2 = first_gateway_position.x + UnitTypes::Protoss_Gateway.tileWidth();
	int y2 = first_gateway_position.y + UnitTypes::Protoss_Gateway.tileHeight();
	
	for (int x = x1 + 1; x <= x2 - 1; x++) {
		all_positions.push_back(TilePosition(x, y1));
		all_positions.push_back(TilePosition(x, y2));
	}
	for (int y = y1 + 1; y <= y2 - 1; y++) {
		all_positions.push_back(TilePosition(x1, y));
		all_positions.push_back(TilePosition(x2, y));
	}
	
	std::vector<TilePosition> result;
	for (TilePosition tile_position : all_positions) {
		if (rectangle_buildable_for_building_with_clearance(tile_position, UnitTypes::Protoss_Gateway, blocked)) {
			result.push_back(tile_position);
		}
	}
	
	return result;
}

std::set<const BWEM::Area*> BuildingPlacementManager::determine_gateway_first_areas_and_positions(Position& base_position_out,Position& center_position_out)
{
	if (base_state.natural_base() == nullptr) return std::set<const BWEM::Area*>();
	
	std::set<const BWEM::Area*> enclosed_areas = base_state.enclosed_areas({base_state.start_base()->GetArea(), base_state.natural_base()->GetArea()});
	Border border(enclosed_areas);
	
	std::set<const BWEM::Area*> areas = border.inside_areas();
	areas.insert(border.outside_areas().begin(), border.outside_areas().end());
	
	const BWEM::ChokePoint* chokepoint = (border.chokepoints().size() == 1) ? *(border.chokepoints().begin()) : nullptr;
	
	if (border.inside_areas().count(base_state.natural_base()->GetArea()) > 0) {
		base_position_out = base_state.natural_base()->Center();
	} else {
		base_position_out = base_state.main_base()->Center();
	}
	center_position_out = (chokepoint == nullptr) ? base_position_out : chokepoint_center(chokepoint);
	return areas;
}

void BuildingPlacementManager::insert_unbuildable_nonarea_locations(TileGrid<bool>& blocked,const std::set<const BWEM::Area*> areas)
{
	for (int y = 0; y < Broodwar->mapHeight(); y++) {
		for (int x = 0; x < Broodwar->mapWidth(); x++) {
			TilePosition tile_position(x, y);
			if (!Broodwar->isBuildable(tile_position) || !tile_inside_areas(tile_position, areas)) blocked.set(tile_position, true);
		}
	}
}

bool BuildingPlacementManager::rectangle_buildable_for_building_with_clearance(TilePosition tile_position,UnitType unit_type,const TileGrid<bool>& blocked,int clearance)
{
	int x = tile_position.x;
	int y = tile_position.y;
	int w = unit_type.tileWidth();
	int h = unit_type.tileHeight();
	
	for (int dy = 0; dy < h; dy++) {
		for (int dx = 0; dx < w; dx++) {
			TilePosition tile_position(x + dx, y + dy);
			if (blocked.get(tile_position)) return false;
		}
	}
	
	for (int nx = x - clearance; nx < x + w + clearance; nx++) {
        for (int i = 0; i < clearance; i++) {
            TilePosition top_tile_position(nx, y - clearance + i);
            if (!walkability_grid.is_walkable(top_tile_position)) return false;
            TilePosition bottom_tile_position(nx, y + h + i);
            if (!walkability_grid.is_walkable(bottom_tile_position)) return false;
        }
	}
	
	for (int ny = y; ny < y + h; ny++) {
        for (int i = 0; i < clearance; i++) {
            TilePosition left_tile_position(x - clearance + i, ny);
            if (!walkability_grid.is_walkable(left_tile_position)) return false;
            TilePosition right_tile_position(x + w + i, ny);
            if (!walkability_grid.is_walkable(right_tile_position)) return false;
        }
	}
	
	return true;
}

bool BuildingPlacementManager::tile_inside_areas(TilePosition tile_position,const std::set<const BWEM::Area*>& areas)
{
	const BWEM::Area* area = bwem_map.GetArea(tile_position);
	if (area != nullptr) {
		return areas.count(area) > 0;
	} else {
		WalkPosition walk_position(tile_position);
		bool at_least_one_match = false;
		for (int dy = 0; dy < 4; dy++) {
			for (int dx = 0; dx < 4; dx++) {
				area = bwem_map.GetArea(walk_position + WalkPosition(dx, dy));
				if (area != nullptr) {
					bool match = (areas.count(area) > 0);
					if (!match) return false;
					at_least_one_match = true;
				}
			}
		}
		return at_least_one_match;
	}
}

int BuildingPlacementManager::maximum_distance_from_possible_opponent_starting_bases(Position position)
{
	int maximum = -1;
	for (auto& base : tactics_manager.possible_enemy_start_bases()) {
		Position base_position = center_position_for(UnitTypes::Protoss_Nexus, base->Location());
		int distance = ground_distance(position, base_position);
		maximum = std::max(maximum, distance);
	}
	return maximum;
}

void BuildingPlacementManager::onUnitDestroy(Unit unit)
{
	if (proxy_pylon_position_.isValid() &&
		unit->getType() == UnitTypes::Protoss_Pylon &&
		unit->getTilePosition() == proxy_pylon_position_) {
		proxy_pylon_position_ = TilePositions::None;
	}
	if (proxy_barracks_position_.isValid() &&
		unit->getType() == UnitTypes::Terran_Barracks &&
		unit->getTilePosition() == proxy_barracks_position_) {
		proxy_barracks_position_ = TilePositions::None;
	}
}

void BuildingPlacementManager::apply_specific_positions(const WallPlacement::FFEPosition& ffe)
{
	specific_positions_[UnitTypes::Protoss_Gateway].push_back(ffe.gateway_position);
	specific_positions_[UnitTypes::Protoss_Forge].push_back(ffe.forge_position);
	specific_positions_[UnitTypes::Protoss_Pylon].push_back(ffe.pylon_position);
	ffe_saved_natural_base_defense_cannon_positions_ = photon_cannon_positions_[base_state.natural_base()];
	ffe_saved_natural_base_defense_pylon_position_ = pylon_positions_[base_state.natural_base()];
	photon_cannon_positions_[base_state.natural_base()].clear();
	for (TilePosition cannon_position : ffe.cannon_positions) {
		photon_cannon_positions_[base_state.natural_base()].push_back(cannon_position);
	}
	pylon_positions_[base_state.natural_base()] = ffe.pylon_position;
	ffe_position_ = ffe;
}

void BuildingPlacementManager::restore_saved_ffe_natural_base_defense_positions()
{
	if (!ffe_saved_natural_base_defense_cannon_positions_.empty() && ffe_saved_natural_base_defense_pylon_position_.isValid()) {
		photon_cannon_positions_[base_state.natural_base()] = ffe_saved_natural_base_defense_cannon_positions_;
		pylon_positions_[base_state.natural_base()] = ffe_saved_natural_base_defense_pylon_position_;
		ffe_saved_natural_base_defense_cannon_positions_.clear();
		ffe_saved_natural_base_defense_pylon_position_ = TilePositions::None;
	}
}
