/*
* Tyr is an AI for StarCraft: Broodwar, 
* 
* Please visit https://github.com/SimonPrins/Tyr for further information.
* 
* Copyright 2015 Simon Prins
*
* This file is part of Tyr.
* Tyr 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 of the License, or
* (at your option) any later version.
* Tyr 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.
* You should have received a copy of the GNU General Public License
* along with Tyr.  If not, see http://www.gnu.org/licenses/.
*/


package com.tyr.buildingplacement;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

import com.tyr.BWTAProxy;
import com.tyr.DebugMessages;
import com.tyr.EnemyManager;
import com.tyr.EnemyPosition;
import com.tyr.PositionUtil;
import com.tyr.Settings;
import com.tyr.Tyr;
import com.tyr.UnitTracker;
import com.tyr.agents.Agent;
import com.tyr.agents.BuildDefensive;
import com.tyr.unitgroups.MineralWorkers;

import bwapi.Color;
import bwapi.Game;
import bwapi.Player;
import bwapi.Position;
import bwapi.Race;
import bwapi.TilePosition;
import bwapi.Unit;
import bwapi.UnitType;
import bwta.BaseLocation;
import bwta.Chokepoint;
import bwta.Region;


/**
 * This class manages the space on the map.
 * It keeps track of where buildings have been placed and which space has been occupied.
 * It can be used to determine new placements for buildings etc..
 * @author Simon
 *
 */
public class SpaceManager
{
	/**
	 * The map that determines for each tile position whether it is occupied or not.
	 * A value of 1 means the position is clear, a value of 2 means that it is occupied by one of our buildings.
	 * A value of 3 means that it is occupied by a neutral building.
	 */
	public int[][] map;
	
	/**
	 * The width of the map.
	 */
	public int width;
	
	/**
	 * The height of the map.
	 */
	public int height;
	
	/**
	 * The main exit for our base.
	 */
	private static Position mainExit = null;
	
	/**
	 * Debug mode for this class.
	 */
	static final boolean debug = false;
	
	/**
	 * List of standard buildSiteLocators, which will be used to find a placement for a new building.
	 */
	public ArrayList<BuildSiteLocator> buildSiteLocators = new ArrayList<BuildSiteLocator>();
	
	public DepotBuildSite depotBuildSite = null;
	

	/**
	 * As Protoss, do we have too little powered space left to build any buildings? 
	 */
	public static boolean noPower = false;
	
	/**
	 * List of pylons currently under construction.
	 */
	private static List<Unit> buildingPylons = new ArrayList<>();
	
	/**
	 * The maximum distance at which we build cannons to defend the natural.
	 */
	private static int cannonExpandDist = 360;
	
	/**
	 * List of all buildings.
	 */
	private List<Unit> buildings = new ArrayList<>();

	/**
	 * Location of neutral eggs used by the naturalExpandPos() method.
	 */
	private static List<Position> eggs;
	
	public SpaceManager()
	{
		this.width = Tyr.game.mapWidth();
		this.height = Tyr.game.mapHeight();
		
		// Initialize the map.
		map = new int[width][height];
		for(int x=0; x<width; x++)
			for(int y=0; y<height; y++)
				if(Tyr.game.isBuildable(x, y))
					map[x][y] = 1;
		
		if (Tyr.self.getRace() == Race.Terran)
		{
			depotBuildSite = new DepotBuildSite();
			buildSiteLocators.add(depotBuildSite);
		}
		else if (Tyr.self.getRace() == Race.Protoss)
			buildSiteLocators.add(new PylonBuildSite());
		
		buildSiteLocators.add(new DefaultBuildSite());
		
		if (Tyr.game.mapFileName().contains("Destination") || Tyr.game.mapFileName().contains("Alchemist"))
			cannonExpandDist = 300;
	}

	public void onFrame(Game game, Player self, Tyr bot)
	{
		for(int x=0; x<width; x++)
			for(int y=0; y<height; y++)
				if(map[x][y] != 0 && map[x][y] != 3)
					map[x][y] = 1;
		
		// Reserve space on the map for all currently visible neutral units.
		for(Unit neutralUnit : game.getNeutralUnits())
			reserveSpace(neutralUnit);

		// When a pylon completes or a building gets destroyed we may have space to build buildings again.
		if (self.getRace() == Race.Protoss)
		{
			if (noPower)
				DebugMessages.addMessage("No pylon power detected!");
			
			for (Unit unit : buildingPylons)
				if (unit.isCompleted())
					noPower = false;
			
			for (Unit unit : buildings)
				if (unit.getHitPoints() < 0 || unit.getRemoveTimer() > 0 || !unit.exists())
					noPower = false;
		}
		
		buildingPylons = new ArrayList<>();
		buildings = new ArrayList<>();
		
		// Reserve space on the map for all the players own buildings.
		for(Unit myUnit : self.getUnits())
		{
			if(!myUnit.getType().isBuilding())
				continue;
			
			if(myUnit.isLifted())
				continue;
			
			if (myUnit.getType() == UnitType.Protoss_Pylon && !myUnit.isCompleted())
				buildingPylons.add(myUnit);
			
			buildings.add(myUnit);
			
			reserveSpace(myUnit);
		}
		
		for (MineralWorkers base : bot.workForce.mineralWorkers)
		{
			if (base.turretSite != null)
			{
				for (TilePosition pos : base.turretSite.turretPositions)
				{
					if (pos != null)
					{
						reserveSpace(pos, UnitType.Terran_Missile_Turret);
						game.drawBoxMap(pos.getX()*32, pos.getY()*32, (pos.getX() + 2)*32, (pos.getY() + 2)*32, Color.Orange);
					}
				}
			}
		}
		
		// Reserve space for all the buildings we intend to build.
		for(BuildCommand com : bot.buildCommands)
			reserveSpace(com);
		
		// Reserve space for the walloff, if it exists or if we intend to build it.
		if(bot.wallOff != null && bot.wallOff.placementFound)
		{
			for(BuildCommand com : bot.wallOff.buildPlan)
				reserveSpace(com);
			
			for(BuildCommand com : bot.wallOff.underConstruction)
				reserveSpace(com);
		}
		
		// Draw some debug information.
		if (debug)
		{
			for(int x=0; x<width; x++)
				for(int y=0; y<height; y++)
				{
					if(map[x][y] == 0)
						game.drawBoxMap(x*32, y*32, x*32 + 32, y*32 + 32, Color.Red);
					else if (map[x][y] == 2)
						game.drawBoxMap(x*32, y*32, x*32 + 32, y*32 + 32, Color.Blue);
					else if (map[x][y] == 3)
						game.drawBoxMap(x*32, y*32, x*32 + 32, y*32 + 32, Color.Grey);
				}
		}
		
		// Find all potential supply depot placements.
		if (depotBuildSite != null && Tyr.game.getFrameCount() >= 200)
		{
			if (Tyr.game.getFrameCount() == 200)
				DebugMessages.log("Performing DepotBuildSite.onFrame() for the first time.");
			depotBuildSite.onFrame();
			if (Tyr.game.getFrameCount() == 200)
				DebugMessages.log("DepotBuildSite.onFrame() completed successfuly for the first time.");
		}
	}
	
	/**
	 * Reserves space on the map for a building.
	 * @param unit The building for which we reserve spcace.
	 */
	public void reserveSpace(Unit unit)
	{
		reserveSpace(unit.getTilePosition(), unit.getType());
	}

	/**
	 * Reserves space on the map for a building we intend to build.
	 * @param com The buildcommand for which we want to reserve the space.
	 */
	public void reserveSpace(BuildCommand com)
	{
		reserveSpace(com.position, com.building);
	}
	
	/**
	 * Reserve space on the map for a building.
	 * @param pos The position where the building has been built (or where we intend to build it).
	 * @param building The type of building.
	 */
	public void reserveSpace(TilePosition pos, UnitType building)
	{
		// If the building could build and add-on, we reserve space for that.
		if(building.canBuildAddon())
			for(int dx=0; dx<2; dx++)
				for(int dy=0; dy<2; dy++)
					map[pos.getX() + building.tileWidth() + dx][pos.getY() + building.tileHeight() - 2 + dy] = 2;
		
		// Reserve space for the building itself.
		for(int dx = 0; dx < building.tileWidth(); dx++)
			for(int dy = 0; dy < building.tileHeight(); dy++)
				map[pos.getX() + dx][pos.getY() + dy] = building.isNeutral()?3:2;
	}
	
	/**
	 * Determines whether a building can be built at a certain position.
	 * @param builder The worker that will build the building.
	 * @param pos The position where the building is to be built.
	 * @param building The type of building we intend to build.
	 * @param keepExpandsFree Do disalow buildings to be built at an expand.
	 * @return Returns true if the building can be built here, returns false otherwise.
	 */
	public boolean canBuildHere(Unit builder, TilePosition pos,
			UnitType building, boolean keepExpandsFree)
	{
		// Check that the building placement is inside the actual map.
		if(pos.getX() < 0 || pos.getY()<0 
				|| pos.getX() + building.tileWidth () >= width 
				|| pos.getY() + building.tileHeight() >= height)
			return false;
		
		// Check that that the space is clear of obstructions.
		for(int dx = 0; dx < building.tileWidth(); dx++)
			for(int dy = 0; dy < building.tileHeight(); dy++)
				if(map[pos.getX()+dx][pos.getY()+dy] != 1)
					return false;
		
		// If we build and add-on we need to check the space for that too.
		if(building.canBuildAddon())
		{
			// Check that the add-on falls inside the map.
			if (pos.getX() + building.tileWidth() + 2 >= width)
				return false;
			
			// Check that the space where we want to build the building is clear.
			for(int dx=0; dx<2; dx++)
				for(int dy=0; dy<2; dy++)
					if (map[pos.getX() + building.tileWidth() + dx][pos.getY() + building.tileHeight() - 2 + dy] != 1)
						return false;
		}

		// Only bases may be built at an expand location.
		if (keepExpandsFree && BWTAProxy.initialized && !building.isResourceDepot())
		{
			for(BaseLocation loc : Tyr.bot.expands)
			{
				TilePosition locpos = loc.getTilePosition();
				if (pos.getX() + building.tileWidth() <= locpos.getX() - 1)
					continue;
				if (pos.getX() > locpos.getX() + UnitType.Terran_Command_Center.tileWidth() + 3)
					continue;
				if (pos.getY() + building.tileHeight() <= locpos.getY() - 1)
					continue;
				if (pos.getY() > locpos.getY() + UnitType.Terran_Command_Center.tileHeight() + 1)
					continue;
				
				return false;
			}
		}
		
		
		// Finally let the game check whether or not it thinks the building can be built.
		if (BWTAProxy.initialized)
			return Tyr.game.canBuildHere(pos, building, builder, false);
		else return false;
	}

	/**
	 * Determines whether a certain tile is free.
	 * @param pos The tile of which we want to know whether or not it is free.
	 * @return True if the tile is free, false if it is occupied.
	 */
	public boolean isFree(TilePosition pos) 
	{
		// Is the tile outside the map?
		if(pos.getX() < 0 || pos.getY()<0 
				|| pos.getX() + 1 >= width 
				|| pos.getY() + 1 >= height)
			return false;
		
		// Check whether the space on the map is actually clear.
		return map[pos.getX()][pos.getY()] == 1;
	}
	
	/**
	 * Determines whether or not we can build a building at a certain location.
	 * @param builder The builder who will build the building.
	 * @param i The x location of the tileposition where we want to build the building.
	 * @param j The y location of the tileposition where we want to build the building.
	 * @param building The type of building we want to build.
	 * @return  True if we are able to build the building, false otherwise.
	 */
	public static boolean canBuildHere(Unit builder, int i, int j, UnitType building)
	{
		return canBuildHere(builder, i, j, building, true, true, true);
	}
	
	/**
	 * Determines whether the area needed to build a building at the given location has the required creep.
	 * @param p The tile position of the building.
	 * @param building The type of building that we want to build there.
	 * @return True iff the area has the needed creep.
	 */
	public static boolean hasCreep(TilePosition p, UnitType building)
	{
		if (!building.requiresCreep())
			return true;
		
		for (int i=p.getX(); i<=p.getX()+building.tileWidth(); i++)
			for (int j=p.getY(); j<=p.getY()+building.tileHeight(); j++)
				if (!Tyr.game.hasCreep(i, j))
					return false;
		
		return true;
	}
	
	/**
	 * Determines if the area where we want to build the building is free of units.
	 * @param p The position where we want to build the building.
	 * @param building The type of building we want to build.
	 * @param builder The unit who will build the building.
	 * @return Returns true iff there are no units in the way for building the building.
	 */
	public static boolean freeOfUnits(TilePosition p, UnitType building, Unit builder)
	{
		for (Unit u : Tyr.game.getAllUnits()) 
		{
			if (u.getID() == builder.getID()) continue;
			
			
			// Defensive structures are allowed to be built close together.
			if ((building == UnitType.Terran_Bunker || building == UnitType.Terran_Missile_Turret) 
					&& (u.getType() == UnitType.Terran_Bunker || u.getType() == UnitType.Terran_Missile_Turret
						|| u.getType().isRefinery() || u.getType() == UnitType.Resource_Vespene_Geyser || u.getType() == UnitType.Protoss_Photon_Cannon || u.getType() == UnitType.Protoss_Forge))
					continue;
			
			// Supply depots, armories and academies are allowed to be built close together.
			if (building == UnitType.Terran_Supply_Depot
					&& (u.getType() == UnitType.Terran_Supply_Depot 
					|| u.getType() == UnitType.Terran_Armory || u.getType() == UnitType.Terran_Academy))
					continue;
			
			if (building == UnitType.Terran_Missile_Turret || building == UnitType.Protoss_Photon_Cannon)
			{
				if (Math.abs(u.getTilePosition().getX() - p.getX()) < 2 && Math.abs(u.getTilePosition().getY() - p.getY()) < 2)
					return false;
				/*
				if ((u.getTilePosition().getX()-i < building.tileWidth() && i - u.getTilePosition().getX() < u.getType().tileWidth())
						&& (u.getTilePosition().getY()-j < building.tileHeight() && j - u.getTilePosition().getY() < u.getType().tileHeight()))
				{
					Tyr.drawCircle(u.getPosition(), Color.Green);
					return false;
				}*/
			}
			else
			{
				// Check that there is space around buildings, so that units will be able to move around the base. 
				if ((u.getTilePosition().getX()-p.getX() < building.tileWidth()+1 && p.getX() - u.getTilePosition().getX() < u.getType().tileWidth()+1)
						&& (u.getTilePosition().getY()-p.getY() < building.tileHeight()+1 && p.getY() - u.getTilePosition().getY() < u.getType().tileHeight() + 1))
					return false;
			}
		}
		return true;
	}
	
	/**
	 * Determines whether or not we can build a building at a certain location.
	 * @param builder The builder who will build the building.
	 * @param i The x location of the tileposition where we want to build the building.
	 * @param j The y location of the tileposition where we want to build the building.
	 * @param building The type of building we want to build.
	 * @param checkMap Do we check the map for illegal building placements?
	 * @param keepExpandsFree Do we prevent the building from being built near an expand location.
	 * @param checkUnits Do we check for units in the way of our building?
	 * @return  True if we are able to build the building, false otherwise.
	 */
	public static boolean canBuildHere(Unit builder, int i, int j, UnitType building, boolean checkMap, boolean keepExpandsFree, boolean checkUnits)
	{
		// We cannot build a building that requires psi if we do not have psi.
		if (building.requiresPsi() && Tyr.self.completedUnitCount(UnitType.Protoss_Pylon) == 0)
			return false;
		
		if(checkMap)
		{
			// See if we know of any other buildings that are in the way.
			if (!Tyr.bot.spaceManager.canBuildHere(builder, new TilePosition(i,j), building, keepExpandsFree)
					|| !(!building.canBuildAddon() || Tyr.bot.spaceManager.canBuildHere(builder, new TilePosition(i+2,j), building, keepExpandsFree)))
				return false;
		}
		else
		{
			if (BWTAProxy.initialized)
				return Tyr.game.canBuildHere(new TilePosition(i,j), building, builder, false);
			else return false;
		}
		
		if(!hasCreep(new TilePosition(i, j), building))
			return false;
		
		// See if the building will not block the exit of our base.
		if (BWTAProxy.initialized && getMainExit().getDistance(Tyr.tileToPosition(new TilePosition(i,j))) <= 64)
			return false;
		
		return freeOfUnits(new TilePosition(i, j), building, builder);
	}
	
	/**
	 * Builds a building.
	 * @param building The type of building to be built.
	 * @return Returns true if we succeeded in building the building, returns false otherwise.
	 */
	public boolean build(UnitType building)
	{
		return build(building, null);
	}
	
	/**
	 * Build a building.
	 * @param building The type of building to be built.
	 * @param desiredPosition The TilePosition at which we want to build the building.
	 * @return Returns true if we succeeded in building the building, returns false otherwise.
	 */
	public boolean build(UnitType building, Position desiredPosition)
	{
		// We have no power to power our new building, need to build a pylon first!
		if (Tyr.self.getRace() == Race.Protoss && noPower)
			if (building != UnitType.Protoss_Nexus && building != UnitType.Protoss_Assimilator && building != UnitType.Protoss_Pylon)
				return false;
		
		// Get a worker to build the building.
		Agent worker = Tyr.bot.workForce.pop(desiredPosition == null?
				Tyr.tileToPosition(Tyr.self.getStartLocation())
				:desiredPosition);
		
		if (worker == null)
			return false;
		
		// Find an appropriate placement from one of our build site locators.
		TilePosition buildTile = null;
		for (BuildSiteLocator locator : buildSiteLocators)
		{
			buildTile = locator.findPlacement(building, desiredPosition==null?null:Tyr.positionToTile(desiredPosition), worker);
			if (buildTile != null)
				break;
		}
		
		if (buildTile == null)
		{
			// Couldn't find placement for protoss building, probably need more power.
			if (Tyr.self.getRace() == Race.Protoss)
				if (building != UnitType.Protoss_Nexus && building != UnitType.Protoss_Assimilator && building != UnitType.Protoss_Pylon)
					noPower = true;
			
  			Tyr.bot.workForce.add(worker);
  			return false;
		}
		
		// If we are building a new base, we try to find a mineral patch to mineralwalk to.
		boolean closeMineralFound = false;
		if (building.isResourceDepot())
		{
			List<Unit> inRange = Tyr.game.getUnitsInRadius(Tyr.tileToPosition(buildTile), 270);
			for(Unit mineral : inRange)
			{
				if (mineral.getType().isMineralField())
				{
					worker.unit.gather(mineral);
					closeMineralFound = true;
					break;
				}
			}
		}
		
		Tyr.bot.builders.add(worker);
		BuildCommand com = null;
		com = placeBuilding(worker, building, buildTile);
		if (!closeMineralFound)
			worker.unit.move(com.getCenter());
		return true;
	}

	/**
	 * Build a building.
	 * @param building The type of building to be built.
	 * @param desiredPosition The TilePosition at which we want to build the building.
	 * @param worker The worker who will build the building.
	 * @return Returns true if we succeeded in building the building, returns false otherwise.
	 */
	public BuildCommand build(UnitType building, Position desiredPosition, Agent worker)
	{
		BuildCommand com = null;
		if (worker == null)
			return null;
		
		// Find an appropriate placement from one of our build site locators.
		TilePosition buildTile = null;
		for (BuildSiteLocator locator : buildSiteLocators)
		{
			buildTile = locator.findPlacement(building, desiredPosition==null?null:Tyr.positionToTile(desiredPosition), worker);
			if (buildTile != null)
				break;
		}
		
		if (buildTile == null)
  			return null;

		com = new BuildCommand(worker, building, buildTile);
		reserveSpace(com);
		Tyr.bot.reservedMinerals += building.mineralPrice();
		Tyr.bot.reservedGas += building.gasPrice();
		
		worker.unit.move(com.getCenter());
		return com;
	}

	/**
	 * Build a building.
	 * @param building The type of building to be built.
	 * @param desiredPosition The TilePosition at which we want to build the building.v
	 * @param locator The BuildSiteLocator which will be used to find an appropriate placement for the building.
	 * @param worker The worker who will build the building.
	 * @return Returns true if we succeeded in building the building, returns false otherwise.
	 */
	public BuildCommand build(UnitType building, Position desiredPosition, BuildSiteLocator locator, Agent worker)
	{
		BuildCommand com = null;
		if (worker == null)
			return null;
		
		// Find an appropriate placement from one of our build site locators.
		TilePosition buildTile = null;
		buildTile = locator.findPlacement(building, desiredPosition==null?null:Tyr.positionToTile(desiredPosition), worker);
		
		if (buildTile == null)
  			return null;

		com = new BuildCommand(worker, building, buildTile);
		reserveSpace(com);
		Tyr.bot.reservedMinerals += building.mineralPrice();
		Tyr.bot.reservedGas += building.gasPrice();
		
		worker.unit.move(com.getCenter());
		return com;
	}
	
	/**
	 * Build a building.
	 * @param building The type of building to be built.
	 * @param desiredPosition The TilePosition at which we want to build the building.v
	 * @param locator The BuildSiteLocator which will be used to find an appropriate placement for the building.
	 * @return Returns true if we succeeded in building the building, returns false otherwise.
	 */
	public boolean build(UnitType building, Position desiredPosition, BuildSiteLocator locator)
	{
		// Get a worker to build the building.
		Agent worker = Tyr.bot.workForce.pop(desiredPosition == null?
				Tyr.tileToPosition(Tyr.self.getStartLocation())
				:desiredPosition);
		
		if (worker == null)
			return false;
		
		// Find an appropriate placement from the provided build site locator.
		TilePosition buildTile = locator.findPlacement(building, desiredPosition==null?null:Tyr.positionToTile(desiredPosition), worker);
		
		// No placement was found, we will not build the building.
		if (buildTile == null)
		{
  			Tyr.bot.workForce.add(worker);
  			return false;
		}
		
		// If we are building a new base, we try to find a mineral patch to mineralwalk to.
		boolean closeMineralFound = false;
		if (building.isResourceDepot())
		{
			List<Unit> inRange = Tyr.game.getUnitsInRadius(Tyr.tileToPosition(buildTile), 270);
			for(Unit mineral : inRange)
			{
				if (mineral.getType().isMineralField())
				{
					worker.unit.gather(mineral);
					closeMineralFound = true;
					break;
				}
			}
		}

		Tyr.bot.builders.add(worker);
		BuildCommand com = null;
		com = placeBuilding(worker, building, buildTile);
		if (!closeMineralFound)
			worker.unit.move(com.getCenter());
		return true;
	}
	
	/**
	 * Builds a building in a specified position.
	 * @param building The type of building to be built.
	 * @param pos The tile position where the building is to be built.
	 * @return Returns true if the building can be placed, returns false otherwise.
	 */
	public boolean buildExact(UnitType building, TilePosition pos)
	{
		Agent worker = Tyr.bot.workForce.pop(Tyr.tileToPosition(pos));
		if (worker == null)
			return false;
		if (canBuildHere(worker.unit, pos.getX(), pos.getY(), building, false, true, true))
		{
			placeBuilding(worker, building, pos);
			return true;
		}
		Tyr.bot.workForce.add(worker);
		return false;
	}

    /**
     * Builds a defensive building.
     * @param building The type of building we want to build.
     * @param defensePos The DefensiveStructures to which we want to add the building.
     * @return Returns true if we succeeded in building the building, returns false otherwise.
     */
    public boolean buildDefensive(UnitType building, DefensiveStructures defensePos)
    {
    	Position pos = defensePos.getDefensePos();
    	if (pos == null)
    		pos = Tyr.tileToPosition(Tyr.self.getStartLocation());
		Agent worker = Tyr.bot.workForce.pop(pos);
		if (worker == null)
			return false;
		
		TilePosition target = defensePos.getDefensePos() == null?null:Tyr.positionToTile(defensePos.getDefensePos());
		// We ware unable to find a suitable defensive position.
		if (target == null)
		{
			Tyr.bot.workForce.add(worker);
			return false;
		}

		if (Settings.getCloseDefense())
		{
			final TilePosition defendedTile = Tyr.positionToTile(defensePos.defendedPosition);
			target = new TilePosition((target.getX() + defendedTile.getX())/2, (target.getY() + defendedTile.getY())/2);
		}
		
		// Add the building to the existing defenses.
		TilePosition newDefensePos = addDefensePos(worker.unit, building, defensePos);
		if(newDefensePos != null)
		{
			placeBuilding(worker, building, newDefensePos);
			worker.order(new BuildDefensive(worker, defensePos));
			return true;
		}
		
		// If we were unable to place the building next to existing defenses, we now try to find a new location.
  		TilePosition buildTile = 
  			getBuildTile(worker.unit, building, target);
  		
  		if(buildTile == null)
  		{
  			Tyr.bot.workForce.add(worker);
  			return false;
  		}
		
		BuildCommand com = placeBuilding(worker, building, buildTile);
		worker.order(new BuildDefensive(worker, defensePos));
  		
		worker.unit.move(com.getCenter());
		
		return true;
    }
    
    /**
     * Gets a suitable build poition for the building.
     * @param builder The worker who will build the building.
     * @param buildingType The type of building to be built.
     * @param aroundTile The tile around which we look for a suitable position.
     * @return The TilePosition where the building can be built.
     */
	public TilePosition getBuildTile(Unit builder, UnitType buildingType, TilePosition aroundTile) 
	{
		TilePosition ret = null;
		int maxDist = 3;
		int stopDist = 40;
		
		// Refinery, Assimilator, Extractor
		if (buildingType.isRefinery()) {
			for (Unit n : Tyr.game.neutral().getUnits()) {
				if ((n.getType() == UnitType.Resource_Vespene_Geyser)) 
					{
						// Do not build the same refinery twice.
						boolean alreadyConstructing = false;
					
						for (BuildCommand com : Tyr.bot.buildCommands)
						{
							if (com.building.isRefinery())
							{
								if (com.position.getX() == n.getTilePosition().getX() && com.position.getY() == n.getTilePosition().getY())
								{
									alreadyConstructing = true;
									break;
								}
							}
						}
						if (alreadyConstructing)
							continue;
						
						// See if we have built a base near the gas geyser, otherwise we do not need to build the gas geyser there.
	 					boolean hasBase = false;
	 					for(MineralWorkers base : Tyr.bot.workForce.mineralWorkers)
	 					{
	 						if (base.gasWorkers != null 
	 								&& Math.abs(base.gasWorkers.geyser.getX() - n.getX())  <= 10
	 								&& Math.abs(base.gasWorkers.geyser.getY() - n.getY())  <= 10
	 								&& !base.resourceDepot.isBeingConstructed())
	 						{
	 							hasBase = true;
	 							break;
	 						}
	 					}
	 					if(!hasBase)
	 						continue;
	 					
	 					return n.getTilePosition();
	 				}
	 		}
	 	}
	 	
		// Building a new base.
	 	if (buildingType.isResourceDepot())
	 	{
	 		BaseLocation loc = null;
	 		for (BaseLocation b : Tyr.bot.expands)
	 		{
	 			if (Tyr.game.canBuildHere(b.getTilePosition(), buildingType, builder, false))
	 			{
	 				// See if the enemy has already taken this base.
	 				boolean enemyBase = false;
	 				for(EnemyPosition p : EnemyManager.getManager().enemyBuildingMemory)
	 				{
	 					enemyBase = b.getPosition().getDistance(p.pos.getX(), p.pos.getY()) < 256;
	 					if(enemyBase)
	 						break;
	 				}
	 				
	 				if (enemyBase)
	 					continue;
	 				
	 				// See if there are units in the way.
	 				boolean unitsInWay = false;
					for(BuildCommand cmd : Tyr.bot.buildCommands)
					{
						if (cmd.position.getDistance(b.getTilePosition()) <= 1)
						{
							unitsInWay = true;
							break;
						}
					}
					if (unitsInWay)
						continue;
	 				
					// We want the closest base to our own.
					if (BWTAProxy.initialized)
					{
		 				if (loc == null || BWTAProxy.getGroundDistance(aroundTile, b.getTilePosition()) < BWTAProxy.getGroundDistance(aroundTile, loc.getTilePosition()))
		 					loc = b;
					}
					else
		 				if (loc == null || aroundTile.getDistance(b.getTilePosition()) < aroundTile.getDistance(loc.getTilePosition()))
		 					loc = b;
	 			}
	 		}
	
	 	 	return loc==null?null:loc.getTilePosition();
	 	}
	 	
	 	if (!Tyr.game.isVisible(aroundTile))
	 		return aroundTile;
	 	
	 	// Just like in an increasing area around the desired position until we find something.
	 	while ((maxDist < stopDist) && (ret == null))
	 	{
	 		for (int i=aroundTile.getX()-maxDist; i<=aroundTile.getX()+maxDist; i++)
	 		{
	 			if (buildingType == UnitType.Protoss_Pylon && (i <= 6 || i >= Tyr.game.mapWidth() - 6))
	 				continue;
	 			for (int j=aroundTile.getY()-maxDist; j<=aroundTile.getY()+maxDist; j++)
	 			{
	 				if (buildingType == UnitType.Protoss_Pylon && (j <= 6 || j >= Tyr.game.mapHeight() - 6))
	 					continue;
	 				if(SpaceManager.canBuildHere(builder, i, j, buildingType))
	 					return new TilePosition(i, j);
	 			}
	 		}
	 		
 			maxDist += 2;
 		}
 	
 		return ret;
 	}
	
	/**
	 * This method creates a new BuildCommand, reserves space and resources for it and adds it to the existing list of commands.
	 * @param worker The worker to build the building.
	 * @param building The type of building to be built.
	 * @param buildTile The place where we want to build the building.
	 * @return The resulting BuildCommand object.
	 */
	private BuildCommand placeBuilding(Agent worker, UnitType building, TilePosition buildTile)
	{
		BuildCommand com = new BuildCommand(worker, building, buildTile);
		Tyr.bot.buildCommands.add(com);
		reserveSpace(com);
		Tyr.bot.reservedMinerals += building.mineralPrice();
		Tyr.bot.reservedGas += building.gasPrice();
		
		return com;
	}
	
	/**
	 * Get a tile position for building a defensive structure.
	 * @param builder The builder to build the defensive structure.
	 * @param building The type of building to build.
	 * @param defenses The defenses to which this structure is to be added.
	 * @return A tile position where the defenses may be built or null if no such position can be found.
	 */
	public TilePosition addDefensePos(Unit builder, UnitType building, DefensiveStructures defenses)
	{
		// Look for a position around an existing building.
		for(Unit structure : defenses.defences)
		{
			TilePosition pos = structure.getTilePosition();
			
			// Look for a position above or below an existing building.
			for(int dx = 1-building.tileWidth(); dx < building.tileWidth(); dx++)
			{
				int x1 = pos.getX() + dx;
				int y1 = pos.getY() - building.tileHeight();
				int y2 = pos.getY() + structure.getType().tileHeight();
				
				if(SpaceManager.canBuildHere(builder, x1, y1, building))
					return new TilePosition(x1, y1);
				if(SpaceManager.canBuildHere(builder, x1, y2, building))
					return new TilePosition(x1, y2);
			}
			
			// Look for a position to the left or the right of the existing building.
			for(int dy = 1-building.tileHeight(); dy < building.tileHeight(); dy++)
			{
				int x1 = pos.getX() - building.tileWidth();
				int x2 = pos.getX() + structure.getType().tileWidth();
				int y1 = pos.getY() +dy;
				
				if(SpaceManager.canBuildHere(builder, x1, y1, building))
					return new TilePosition(x1, y1);
				if(SpaceManager.canBuildHere(builder, x2, y1, building))
					return new TilePosition(x2, y1);
			}
		}
		
		return null;
	}
	
	/**
	 * The main exit of our base.
	 * @return The main exit of our base.
	 */
	public static Position getMainExit()
	{
		if(!BWTAProxy.initialized)
			return null;
		
		if (mainExit == null)
			mainExit = getExit(Tyr.tileToPosition(Tyr.self.getStartLocation()));
		
		return mainExit;
	}

	/**
	 * The main exit of the region containing the position.
	 * @param pos A position that lies inside the region for which we are looking for the exit. 
	 * @return The main exit of the region containing the position.
	 */
	public static Position getExit(Position pos)
	{
		if(!BWTAProxy.initialized)
			return null;
		final List<BaseLocation> startLocations = BWTAProxy.getStartLocations();
		final int baseCount = startLocations.size();
		
		final Region current = BWTAProxy.getRegion(pos);
		if (current == null)
			return null;
		
		Position target = null;
		double bestDistance = -1;
		final List<Chokepoint> chokepoints = current.getChokepoints();
		if (chokepoints == null)
			return null;

		// If there is only one chokepoint for the region of our main base, then that is the main exit for our base.
		if (chokepoints.size() == 1)
			return chokepoints.get(0).getCenter();
		
		if (Tyr.game.mapName().contains("Andromeda"))
		{

			for(Chokepoint choke : chokepoints)
			{
				double distance;
				
				distance = Math.min(Tyr.game.mapHeight()*32 - choke.getY(), choke.getY());

				if (target == null || distance > bestDistance)
				{
					target = choke.getCenter();
					bestDistance = distance;
				}
			}

			return target;

		}
		
		for(Chokepoint choke : chokepoints)
		{
			if (choke == null)
				continue;
			// If there are multiple exists, we take the one farthest from the edge of the map.
			double distance = getClosestNeutralDistance(choke.getCenter());
			if(distance != -1 && distance < 128 && baseCount > 2)
				continue;
			
			distance = Math.min(choke.getX(), choke.getY());
			distance = Math.min(distance, Tyr.game.mapWidth()*32 - choke.getX());
			distance = Math.min(distance, Tyr.game.mapHeight()*32 - choke.getY());
			
			// But not too far form the edge of the map.
			if (distance >= 1024)
				continue;
			
			boolean blocked = false;
			for (EnemyPosition neutrals : EnemyManager.getManager().neutralBuildingMemory)
			{
				if (neutrals.pos.getDistance(choke) <= 128)
				{
					blocked = true;
					break;
				}
			}

			if (blocked)
				continue;
			
			if (target == null || distance > bestDistance)
			{
				target = choke.getCenter();
				bestDistance = distance;
			}
		}
		
		// If none of the chokepoints passed the basic checks from the last section, we simply take the one farthest from the edge of the map.
		if (target == null)
		{
			for(Chokepoint choke : chokepoints)
			{
				boolean blocked = false;
				for (EnemyPosition neutrals : EnemyManager.getManager().neutralBuildingMemory)
				{
					if (neutrals.pos.getDistance(choke) <= 128)
					{
						blocked = true;
						break;
					}
				}
				
				if (blocked)
					continue;
				
				double distance;
				
				distance = Math.min(choke.getX(), choke.getY());
				distance = Math.min(distance, Tyr.game.mapWidth()*32 - choke.getX());
				distance = Math.min(distance, Tyr.game.mapHeight()*32 - choke.getY());
				
				if (target == null || distance > bestDistance)
				{
					target = choke.getCenter();
					bestDistance = distance;
				}
			}
		}
		
		return target;
	}

	/**
	 * Find the distance to the closest neutral structure from a certain poition.
	 * @param pos The position for which we want to know the distance to the closest neutral structure.
	 * @return The distance to the closest neutral structure or -1 when no structure is found.
	 */
	private static double getClosestNeutralDistance(Position pos)
	{
		double result = -1;
		if ( UnitTracker.getNeutralStructures() == null)
			return -1;
		for(EnemyPosition neutral : UnitTracker.getNeutralStructures())
		{
			if (neutral == null)
				continue;
			if (neutral.type == UnitType.Resource_Mineral_Field || neutral.type == UnitType.Resource_Mineral_Field_Type_2
					|| neutral.type == UnitType.Resource_Mineral_Field_Type_3 || neutral.type == UnitType.Resource_Vespene_Geyser)
				continue;
			double distance = pos.getDistance(neutral.pos);
			if(result == -1)
				result = distance;
			else result = Math.min(result, distance);
		}
		return result;
	}
	
	/**
	 * Get the natural expand of the enemy.
	 * @return Get the natural expand of the enemy.
	 */
	public static BaseLocation getEnemyNatural()
	{
		final Position exit = SpaceManager.getExit(Tyr.bot.suspectedEnemy.get(0).getPosition());
		if (exit == null)
			return null;
		int closestDist = Integer.MAX_VALUE;
		BaseLocation result = null;
		
		for (BaseLocation loc : Tyr.bot.expands)
		{
			int newDist = (int)loc.getDistance(exit);
			if (newDist < closestDist)
			{
				closestDist = newDist;
				result = loc;
			}
		}
		
		return result;
	}
	
	/**
	 * Get our own natural expand.
	 * @return Get our own natural expand.
	 */
	public static Position getNatural()
	{
		BaseLocation loc = null;
		if (Tyr.game.mapFileName().contains("Alchemist"))
		{
			if (Tyr.bot.suspectedEnemy.size() != 1)
				return null;
			
			final Position enemyMain = Tyr.bot.suspectedEnemy.get(0).getPosition();
			final Position main = Tyr.getStartLocation();
			List<Position> bases = new ArrayList<>();
			for (BaseLocation base : Tyr.bot.expands)
				if (PositionUtil.distanceSq(base.getPosition(), main) >= 100 * 100)
					bases.add(base.getPosition());
			bases.sort(new Comparator<Position>()
			{
				@Override
				public int compare(Position p1, Position p2)
				{
					return PositionUtil.distanceSq(main, p1) - PositionUtil.distanceSq(main, p2);
				}
			});
			
			final Position natural;
			if (PositionUtil.distanceSq(bases.get(0), enemyMain) <= PositionUtil.distanceSq(bases.get(1), enemyMain))
				natural = bases.get(0);
			else
				natural = bases.get(1);
			return natural;
		}
		if (Tyr.game.mapFileName().contains("Fortress"))
		{
			final Position main = Tyr.getStartLocation();
			if (!BWTAProxy.initialized)
				return null;
			final Position choke = BWTAProxy.getRegion(main).getChokepoints().get(0).getCenter();
			int closest = 1000000000;
			Position result = null;
			for (BaseLocation b : Tyr.bot.expands)
			{
		 		if (b.isMineralOnly())
		 			continue;
		 		
		 		if (b.isIsland())
		 			continue;
		 		
		 		final int dist = PositionUtil.distanceSq(b.getPosition(), choke);
		 		if (dist < closest)
		 		{
		 			closest = dist;
		 			result = b.getPosition();
		 		}
			}
			return result;
		}
	 	for (BaseLocation b : Tyr.bot.expands)
	 	{
	 		if (b.isMineralOnly())
	 			continue;
	 		
	 		if (b.isIsland())
	 			continue;
	 		
	 		if (b.getDistance(Tyr.tileToPosition(Tyr.self.getStartLocation())) <= 100)
	 			continue;
	 		
	 		// We want the closest base to our own.
			if (BWTAProxy.initialized)
			{
		 		if (loc == null || BWTAProxy.getGroundDistance(Tyr.self.getStartLocation(), b.getTilePosition()) < BWTAProxy.getGroundDistance(Tyr.self.getStartLocation(), loc.getTilePosition()))
		 			loc = b;
			}
			else if (loc == null || Tyr.self.getStartLocation().getDistance(b.getTilePosition()) < Tyr.self.getStartLocation().getDistance(loc.getTilePosition()))
		 		loc = b;
	 	}
 		return loc==null?null:loc.getPosition();
	}
	
	public static Position getDefensePos(Position basePosition)
	{
		ArrayList<Position> minerals = new ArrayList<Position>();
		
		for (EnemyPosition mineral : EnemyManager.getManager().neutralBuildingMemory)
			if (mineral.type.isMineralField() && mineral.pos.getDistance(basePosition) <= 270)
                minerals.add(mineral.pos);
		
		return getDefensePosPositions(basePosition, minerals);
	}
	
	public static Position getDefensePos(Position basePosition, ArrayList<Unit> minerals)
	{
		ArrayList<Position> positions = new ArrayList<Position>();
		for (Unit mineral: minerals)
			positions.add(mineral.getPosition());
		return getDefensePosPositions(basePosition, positions);
	}
	
	public static Position getDefensePosPositions(Position basePosition, ArrayList<Position> minerals)
	{
		Position defensePos;
		
		// Determine the position for defensive structures and units.
		int totalX = 0;
		int totalY = 0;
		
		for(Position mineral : minerals)
		{
			totalX += mineral.getX();
			totalY += mineral.getY();
		}
		// We first determine the average position of all the minerals.
		if (minerals.size() != 0)
			defensePos = new Position(totalX / minerals.size(), totalY / minerals.size());
		else
			defensePos = new Position(basePosition.getX(), basePosition.getY());
		
		// We set the defensepos to the opposite location of the average mineral position from the base.
		defensePos = new Position(2*basePosition.getX() - defensePos.getX(),
				2*basePosition.getY() - defensePos.getY());
		
		return defensePos;
	}
	
	/**
	 * Is there a pylon being built that is not yet providing power?
	 * @return Is there a pylon being built that is not yet providing power?
	 */
	public static boolean isPylonBuilding()
	{
		return buildingPylons.size() > 0;
	}

	public static Position getNaturalDefensePos()
	{
		final Position natural = getNatural();
		
		final Position main = Tyr.getStartLocation();
		final Region naturalRegion = BWTAProxy.getRegion(natural);
		Position result = null; 
		int dist = -1;
		if (Tyr.game.mapFileName().contains("ChupungRyeong") 
				|| Tyr.game.mapFileName().contains("GreatBarrierReef")
				|| Tyr.game.mapFileName().contains("HeartbreakRidge"))
		{
			dist = Integer.MAX_VALUE;
			for (Chokepoint choke : naturalRegion.getChokepoints())
			{
				int newDist = PositionUtil.distanceSq(choke.getCenter(), new Position(Tyr.game.mapWidth()*16, Tyr.game.mapHeight()*16));
				boolean blocked = false;
				for (EnemyPosition pos : EnemyManager.getManager().neutralBuildingMemory)
				{
					if (pos.distanceSq(choke.getCenter()) <= 100 * 100)
					{
						blocked = true;
						break;
					}
				}
				if (blocked)
					continue;
				
				if (newDist < dist)
				{
					dist = newDist;
					result = choke.getCenter();
				}
			}
		}
		else if (Tyr.game.mapFileName().contains("Pathfinder")
					|| Tyr.game.mapFileName().contains("Fortress"))
		{
			eggs = new ArrayList<>();
			for (EnemyPosition neutral : EnemyManager.getManager().neutralBuildingMemory)
				if (neutral.type == UnitType.Zerg_Egg)
					eggs.add(neutral.pos);
			eggs.sort(new Comparator<Position>() {

				@Override
				public int compare(Position p1, Position p2)
				{
					return PositionUtil.distanceSq(p1, natural) - PositionUtil.distanceSq(p2, natural);
				}
				
			});
			
			result = PositionUtil.getWeighted(eggs.get(0), eggs.get(1), 0.5);
		}
		else
		{
			for (Chokepoint choke : naturalRegion.getChokepoints())
			{
				int newDist = PositionUtil.distanceSq(choke.getCenter(), main);
				boolean blocked = false;
				for (EnemyPosition pos : EnemyManager.getManager().neutralBuildingMemory)
				{
					if (pos.distanceSq(choke.getCenter()) <= 100 * 100)
					{	
						blocked = true;
						break;
					}
				}
				if (blocked)
					continue;
				
				if (newDist > dist)
				{
					dist = newDist;
					result = choke.getCenter();
				}
			}
		}
		
		if (result == null || natural == null)
			return result;
		
		final int cannonDist = PositionUtil.distanceSq(natural, result); 
		
		if (cannonDist >= cannonExpandDist * cannonExpandDist)
		{
			Settings.setSmallInvasionDist((int)Math.min(cannonExpandDist + 360, Settings.getSmallInvasionDist()));
			final int dx = result.getX() - natural.getX();
			final int dy = result.getY() - natural.getY();
			final double length = Math.sqrt(dx*dx + dy*dy);
			return new Position(natural.getX() + (int)(dx * cannonExpandDist / length), natural.getY() + (int)(dy * cannonExpandDist / length));
		}
		
		Settings.setSmallInvasionDist((int)Math.min(Math.sqrt(cannonDist) + 360, Settings.getSmallInvasionDist()));
		
		return result;
	}
}
