Skynet/Skynet/BuildingPlacer.cpp

Go to the documentation of this file.

#include "BuildingPlacer.h"

#include <boost/bind.hpp>

#include "BaseTracker.h"
#include "UnitHelper.h"
#include "MapHelper.h"
#include "UnitTracker.h"
#include "TerrainAnaysis.h"
#include "DrawBuffer.h"
#include "WallTracker.h"
#include "BorderTracker.h"
#include "ScoutManager.h"
#include "PylonPowerTracker.h"

BuildingPlacerClass::BuildingPlacerClass()
{
}

void BuildingPlacerClass::calculateReservations()
{
        const BWAPI::UnitType &centerType = BWAPI::Broodwar->self()->getRace().getCenter();
        const BWAPI::UnitType &refineryType = BWAPI::Broodwar->self()->getRace().getRefinery();

        // first reserve all wall positions
        mPermanentReserved = WallTracker::Instance().getWallTiles();

        // for each base that has resources
        for each(Base base in BaseTracker::Instance().getResourceBases())
        {
                // reserve the base location
                for(int x = base->getCenterBuildLocation().x(); x < base->getCenterBuildLocation().x()+centerType.tileWidth(); ++x)
                        for(int y = base->getCenterBuildLocation().y(); y < base->getCenterBuildLocation().y()+centerType.tileHeight(); ++y)
                                mPermanentReserved[TilePosition(x, y)] = centerType;

                // if its zerg, also reserve the area the larva hang out
                if(BWAPI::Broodwar->self()->getRace() == BWAPI::Races::Zerg)
                {
                        for(int x = base->getCenterBuildLocation().x() - 1; x < base->getCenterBuildLocation().x()+centerType.tileWidth()+1; ++x)
                                for(int y = base->getCenterBuildLocation().y() - 1; y < base->getCenterBuildLocation().y()+centerType.tileHeight()+1; ++y)
                                        mPermanentReserved[TilePosition(x, y)] = centerType;
                }

                // and reserve the geyser space just so it doesn't get included in the resource reserved space
                for each(Unit geyser in base->getGeysers())
                {
                        for(int x = geyser->getTilePosition().x(); x < geyser->getTilePosition().x()+geyser->getType().tileWidth(); ++x)
                                for(int y = geyser->getTilePosition().y(); y < geyser->getTilePosition().y()+geyser->getType().tileHeight(); ++y)
                                        mPermanentReserved[TilePosition(x, y)] = refineryType;
                }

                reserveResourceSpace(base->getMinerals(), base);
                reserveResourceSpace(base->getGeysers(), base);
        }
}

void BuildingPlacerClass::finaliseReservations()
{
        // Reserve the tiles around the choke for general use
        // TODO: perhaps only in a path between the two sides
        for each(Chokepoint choke in TerrainAnaysis::Instance().getChokepoints())
        {
                int minX = std::min(choke->getBuildTiles().first.x(), choke->getBuildTiles().second.x());
                int maxX = std::max(choke->getBuildTiles().first.x(), choke->getBuildTiles().second.x());

                int minY = std::min(choke->getBuildTiles().first.y(), choke->getBuildTiles().second.y());
                int maxY = std::max(choke->getBuildTiles().first.y(), choke->getBuildTiles().second.y());

                for(int x = minX; x <= maxX; ++x)
                        for(int y = minY; y <= maxY; ++y)
                                if(mPermanentReserved.count(TilePosition(x, y)) == 0)
                                        mPermanentReserved[TilePosition(x, y)] = BWAPI::UnitTypes::None;
        }
}

void BuildingPlacerClass::reserveResourceSpace(const UnitGroup &resources, Base base)
{
        for each(Unit resource in resources)
        {
                int distanceBetween = (resource->getPosition().getApproxDistance(base->getCenterLocation()) / 32) + 1;
                for(int x = resource->getTilePosition().x() - int(distanceBetween); x < resource->getTilePosition().x() + int(distanceBetween) + 4; ++x)
                {
                        for(int y = resource->getTilePosition().y() - int(distanceBetween); y < resource->getTilePosition().y() + int(distanceBetween) + 3; ++y)
                        {
                                int distanceToResource = Position(x*32+16, y*32+16).getApproxDistance(resource->getPosition()) / 32;
                                int distanceToBase = Position(x*32+16, y*32+16).getApproxDistance(base->getCenterLocation()) / 32;

                                if(distanceToResource + distanceToBase < distanceBetween && mPermanentReserved.count(TilePosition(x, y)) == 0)
                                {
                                        if(resource->getType().isMineralField())
                                                mResources[resource].insert(TilePosition(x, y));

                                        ++mResourceReserved[TilePosition(x, y)];
                                }
                        }
                }
        }
}

void BuildingPlacerClass::update()
{
        for(std::set<ReservedLocation>::iterator it = mReservedLocations.begin(); it != mReservedLocations.end();)
        {
                if((*it)->update())
                        mReservedLocations.erase(it++);
                else
                        ++it;
        }

//      for(std::map<TilePosition, BWAPI::UnitType>::iterator it = mPermanentReserved.begin(); it != mPermanentReserved.end(); ++it)
//      {
//              BWAPI::Broodwar->drawBox(BWAPI::CoordinateType::Map, it->first.x() * 32, it->first.y() * 32, it->first.x() * 32 + 32, it->first.y() * 32 + 32, BWAPI::Colors::Red);
//      }
//      for(std::map<TilePosition, int>::iterator it = mResourceReserved.begin(); it != mResourceReserved.end(); ++it)
//      {
//              BWAPI::Broodwar->drawCircle(BWAPI::CoordinateType::Map, it->first.x()*32+16, it->first.y()*32+16, 16, BWAPI::Colors::Blue);
//      }
//      for(std::map<TilePosition, ReservedLocation>::iterator it = mReservedTiles.begin(); it != mReservedTiles.end(); ++it)
//      {
//              BWAPI::Broodwar->drawBox(BWAPI::CoordinateType::Map, it->first.x() * 32, it->first.y() * 32, it->first.x() * 32 + 32, it->first.y() * 32 + 32, BWAPI::Colors::Red);
//      }
}

void BuildingPlacerClass::onDestroy(Unit unit)
{
        if(mResources.count(unit) != 0)
        {
                for each(TilePosition tile in mResources[unit])
                {
                        --mResourceReserved[tile];
                        if(mResourceReserved[tile] == 0)
                                mResourceReserved.erase(tile);
                }

                mResources.erase(unit);
        }
}

void BuildingPlacerClass::reserve(ReservedLocation location)
{
        int startx = location->getTilePosition().x();
        int starty = location->getTilePosition().y();

        int endx = startx + location->getUnitType().tileWidth();
        int endy = starty + location->getUnitType().tileHeight();

        if(UnitHelper::hasAddon(location->getUnitType()))
                endx += 2;

        for(int x = startx; x < endx; ++x)
                for(int y = starty; y < endy; ++y)
                        mReservedTiles[TilePosition(x, y)] = location;
}

void BuildingPlacerClass::free(ReservedLocation location)
{
        int startx = location->getTilePosition().x();
        int starty = location->getTilePosition().y();

        int endx = startx + location->getUnitType().tileWidth();
        int endy = starty + location->getUnitType().tileHeight();

        if(UnitHelper::hasAddon(location->getUnitType()))
                endx += 2;

        for(int x = startx; x < endx; ++x)
                for(int y = starty; y < endy; ++y)
                        mReservedTiles.erase(TilePosition(x, y));
}

ReservedLocation BuildingPlacerClass::getLandingReservation(Unit unit)
{
        ReservedLocation location(new ReservedLocationClass(unit));
        mReservedLocations.insert(location);
        return location;
}

ReservedLocation BuildingPlacerClass::getBuildingReservation(BuildingLocation position, BWAPI::UnitType type)
{
        ReservedLocation location(new ReservedLocationClass(type, position));
        mReservedLocations.insert(location);
        return location;
}

bool BuildingPlacerClass::isReserved(TilePosition position) const
{
        return mReservedTiles.find(position) != mReservedTiles.end();
}

bool BuildingPlacerClass::isReserved(int x, int y) const
{
        return isReserved(TilePosition(x, y));
}

bool BuildingPlacerClass::isResourceReserved(TilePosition position) const
{
        return mResourceReserved.find(position) != mResourceReserved.end();
}

bool BuildingPlacerClass::isResourceReserved(int x, int y) const
{
        return isResourceReserved(TilePosition(x, y));
}

std::pair<TilePosition, Base> BuildingPlacerClass::buildingLocationToTile(BuildingLocation position, BWAPI::UnitType type) const
{
        if(type.isRefinery())
                return getRefineryLocation();

        if(type.requiresPsi())
        {
                bool atleastone = false;
                for each(Unit pylon in UnitTracker::Instance().selectAllUnits(BWAPI::UnitTypes::Protoss_Pylon))
                {
                        if(pylon->isCompleted())
                                atleastone = true;
                }
                if(!atleastone)
                        return std::make_pair(BWAPI::TilePositions::None, Base());
        }

        switch(position.underlying())
        {
        case BuildingLocation::BaseChoke:
                {
                        TilePosition pos = WallTracker::Instance().getWallPosition(type);
                        if(pos != BWAPI::TilePositions::None)
                                return std::make_pair(pos, BaseTracker::Instance().getBase(pos));
                }
        case BuildingLocation::BaseParimeter:
        case BuildingLocation::Base:
                {
                        for each(Base base in baseToBuildAtOrder(type))
                        {
                                TilePosition pos = getBuildLocation(base, type); // TODO : flags of some sort so certain units can be build in minerals etc

                                if(pos != BWAPI::TilePositions::None)
                                        return std::make_pair(pos, base);
                        }
                        break;
                }
        case BuildingLocation::Expansion:
                        return getExpandLocation();
        case BuildingLocation::ExpansionGas:
                        return getExpandLocation(true);
        case BuildingLocation::Proxy:
                        //TODO: find a location that isn't on the path between any base to any other base start locations closest to potential enemy locations
        case BuildingLocation::Manner:
                        //TODO: build in a location that harms the enemy, engineering bay in expand location, pylon in mineral line, gas steal etc
                break;
        }

        return std::make_pair(BWAPI::TilePositions::None, Base());
}

std::pair<TilePosition, Base> BuildingPlacerClass::getlandingLocation(Unit unit) const
{
        // TODO : NYI
        return std::make_pair(BWAPI::TilePositions::None, Base());
        //return BuildingPlacer::Instance().getBuildLocation(unit->getTilePosition() + TilePosition(0, 1));
}

class BuildLocationCompare
{
public:
        BuildLocationCompare(Base base, BWAPI::UnitType type) : mBase(base), mType(type) {}

        bool operator()(TilePosition location) const
        {
                if(BaseTracker::Instance().getBase(location) != mBase)
                        return false;

                return BuildingPlacer::Instance().isLocationNonBlocking(location, mType);
        }

private:
        Base mBase;
        BWAPI::UnitType mType;
};

TilePosition BuildingPlacerClass::getBuildLocation(Base base, BWAPI::UnitType type) const
{
        return MapHelper::spiralSearch(base->getCenterBuildLocation(), BuildLocationCompare(base, type));
}

class RegionChokeCompare
{
public:
        RegionChokeCompare(bool ignoreReservations, Region region)
                : mIgnoreReservations(ignoreReservations)
                , mRegion(region)
        {}

        bool operator()(TilePosition &location)
        {
                return BuildingPlacer::Instance().isTileWalkable(location, mIgnoreReservations) && TerrainAnaysis::Instance().getRegion(location) == mRegion;
        }

private:
        bool mIgnoreReservations;
        Region mRegion;
};

bool BuildingPlacerClass::isLocationNonBlocking(TilePosition position, BWAPI::UnitType type, bool ignoreReservations) const
{
        if(!isLocationBuildable(position, type, ignoreReservations))
                return false;

        std::set<TilePosition> targets = getSurroundingTiles(position, type, ignoreReservations);

        /* If there are no surrounding tiles, it's probably impossible to reach the build site */
        if(targets.empty())
                return false;

        /* Don't build on choke tiles, they are vital for the calculation */
        Region region = TerrainAnaysis::Instance().getRegion(position);
        const std::set<TilePosition> &chokeTiles = region->getChokepointTiles();
        for each(TilePosition tile in chokeTiles)
        {
                if(tile.x() >= position.x() && tile.x() < position.x() + type.tileWidth() && tile.y() >= position.y() && tile.y() < position.y() + type.tileHeight())
                        return false;

                targets.insert(tile);
        }

        /* Start from one of the chokes */
        TilePosition startTile = *chokeTiles.begin();

        /* Ignore the tiles we are building on as we cant path though this building */
        std::set<TilePosition> ignoreTiles;
        for(int x = position.x(); x < position.x() + type.tileWidth(); ++x)
                for(int y = position.y(); y < position.y() + type.tileHeight(); ++y)
                        ignoreTiles.insert(TilePosition(x, y));

        /* Don't block other buildings */
        for each(Unit unit in UnitTracker::Instance().getAllUnits())
        {
                if(unit->exists() && !unit->getType().canProduce())
                        continue;

                /* Refineries are ok as they will be protected by resource reservation */
                if(unit->getType().isRefinery())
                        continue;

                if(UnitHelper::unitProducesGround(unit->getType()))
                {
                        /* 2 is no location found yet */
                        int isBlocked = 2;
                        for each(TilePosition tile in getSurroundingTiles(unit->getTilePosition(), unit->getType(), ignoreReservations))
                        {
                                if(TerrainAnaysis::Instance().getRegion(tile) == region)
                                {
                                        /* If this location is touching this building, ensure we don't block all exits */
                                        if(ignoreTiles.find(tile) != ignoreTiles.end())
                                                isBlocked = (isBlocked==0?0:1);
                                        else
                                        {
                                                /* This tile is not blocked, we can touch this building here */
                                                targets.insert(tile);
                                                isBlocked = 0;
                                        }
                                }
                        }

                        /* Building here will stop units being able to exit this building */
                        if(isBlocked == 1)
                                return false;
                }
        }

        /* Check which tiles can be reached */
        targets = MapHelper::floodFill(startTile, RegionChokeCompare(ignoreReservations, region), targets, ignoreTiles);

        /* If there are no remaining targets, there are all reachable */
        if(targets.empty())
                return true;

        /* Check if we could reach these positions before */
        std::set<TilePosition> newTargets = MapHelper::floodFill(startTile, RegionChokeCompare(ignoreReservations, region), targets);

        /* If they are the same, they were never reachable */
        if(targets == newTargets)
        {
                //if(m_bShowDebugInfo)
//              {
//                      DrawBuffer::Instance().clearBuffer(BufferedCategory::BuildingPlacer);
//                      for each(TilePosition tile in targets)
//                              DrawBuffer::Instance().drawBufferedCircle(BWAPI::CoordinateType::Map, tile.x()*32+16, tile.y()*32+16, 16, 240, BWAPI::Colors::Red, false, BufferedCategory::BuildingPlacer);
// 
//                      for(int x = position.x(); x < position.x() + type.tileWidth(); ++x)
//                              for(int y = position.y(); y < position.y() + type.tileHeight(); ++y)
//                                      DrawBuffer::Instance().drawBufferedCircle(BWAPI::CoordinateType::Map, x*32+16, y*32+16, 16, 240, BWAPI::Colors::White, false, BufferedCategory::BuildingPlacer);
//              }

                return true;
        }

        //if(m_bShowDebugInfo)
//      {
//              DrawBuffer::Instance().clearBuffer(BufferedCategory::BuildingPlacer);
//              for each(TilePosition tile in targets)
//                      DrawBuffer::Instance().drawBufferedCircle(BWAPI::CoordinateType::Map, tile.x()*32+16, tile.y()*32+16, 16, 240, BWAPI::Colors::Red, false, BufferedCategory::BuildingPlacer);
// 
//              for each(TilePosition tile in newTargets)
//                      DrawBuffer::Instance().drawBufferedCircle(BWAPI::CoordinateType::Map, tile.x()*32+16, tile.y()*32+16, 16, 240, BWAPI::Colors::Yellow, false, BufferedCategory::BuildingPlacer);
// 
//              for(int x = position.x(); x < position.x() + type.tileWidth(); ++x)
//                      for(int y = position.y(); y < position.y() + type.tileHeight(); ++y)
//                              DrawBuffer::Instance().drawBufferedCircle(BWAPI::CoordinateType::Map, x*32+16, y*32+16, 16, 240, BWAPI::Colors::White, false, BufferedCategory::BuildingPlacer);
// 
//              DrawBuffer::Instance().drawBufferedCircle(BWAPI::CoordinateType::Map, startTile.x()*32+16, startTile.y()*32+16, 16, 240, BWAPI::Colors::Green, false, BufferedCategory::BuildingPlacer);
//      }

        return false;
}

bool BuildingPlacerClass::isLocationBuildable(TilePosition position, BWAPI::UnitType type, bool ignoreReservations) const
{
        if(type.isRefinery())
        {
                for each(Unit geyser in UnitTracker::Instance().getGeysers())
                {
                        if(geyser->getTilePosition() == position)
                        {
                                if(!ignoreReservations)
                                {
                                        for(int x = position.x(); x < position.x() + type.tileWidth(); ++x)
                                        {
                                                for(int y = position.y(); y < position.y() + type.tileHeight(); ++y)
                                                {
                                                        if(isReserved(x, y))
                                                                return false;
                                                }
                                        }
                                }

                                return true;
                        }
                }

                return false;
        }

        for(int x = position.x(); x < position.x() + type.tileWidth(); ++x)
        {
                for(int y = position.y(); y < position.y() + type.tileHeight(); ++y)
                {
                        if(!isTileBuildable(TilePosition(x, y), type, ignoreReservations))
                                return false;
                }
        }

        if(type.isResourceDepot())
        {
                for each(Unit mineral in UnitTracker::Instance().getMinerals())
                {
                        if(mineral->accessibility() != AccessType::Dead)
                        {
                                if (mineral->getTilePosition().x() > position.x() - 5 &&
                                        mineral->getTilePosition().y() > position.y() - 4 &&
                                        mineral->getTilePosition().x() < position.x() + 7 &&
                                        mineral->getTilePosition().y() < position.y() + 6)
                                {
                                        return false;
                                }
                        }
                }
                for each(Unit geyser in UnitTracker::Instance().getGeysers())
                {
                        if(geyser->accessibility() != AccessType::Dead)
                        {
                                if (geyser->getTilePosition().x() > position.x() - 7 &&
                                        geyser->getTilePosition().y() > position.y() - 5 &&
                                        geyser->getTilePosition().x() < position.x() + 7 &&
                                        geyser->getTilePosition().y() < position.y() + 6)
                                {
                                        return false;
                                }
                        }
                }
        }

        if(type.requiresPsi())
        {
                if(!PylonPowerTracker::Instance().hasPower(position, type))
                        return false;
        }

        /* If this has an addon, make sure there is space to build it */
        if(UnitHelper::hasAddon(type) && !isAddonBuildable(position))
                return false;

        /* Put some extra space between the first 6 pylons*/
        /*if(type == BWAPI::UnitTypes::Protoss_Pylon)
        {
                UnitGroup ug = SelectAll(BWAPI::UnitTypes::Protoss_Pylon);
                if(ug.size() < 6)
                {
                        ug = ug.inRadius(8 * 32, position);

                        if(ug.size() != 0)
                                return false;
                }
        }*/

        return true;
}

bool BuildingPlacerClass::isTileBlocked(TilePosition tile, BWAPI::UnitType type, bool ignoreReservations) const
{
        if(!ignoreReservations)
        {
                if(isReserved(tile) || (!UnitHelper::isStaticDefense(type) && isResourceReserved(tile)))
                        return true;

                std::map<TilePosition, BWAPI::UnitType>::const_iterator it = mPermanentReserved.find(tile);
                if(it != mPermanentReserved.end())
                        if(it->second != type)
                                return true;
        }

        for each(Unit unit in UnitTracker::Instance().getUnitsOnTile(tile.x(), tile.y()))
        {
                if(!unit->exists())
                        continue;

                if(unit->getType().isBuilding() && !unit->isLifted())
                        return true;

                if(!type.isRefinery() && unit->getType() == BWAPI::UnitTypes::Resource_Vespene_Geyser)
                        return true;

                if(!unit->getType().canMove())
                        return true;
        }

        if(BWAPI::Broodwar->self()->getRace() == BWAPI::Races::Terran && !type.isAddon())
        {
                if(tile.x()-1 >= 0)
                        if(isAddonBuilder(tile.x()-1, tile.y()))
                                return true;
                if(tile.x()-2 >= 0)
                        if(isAddonBuilder(tile.x()-2, tile.y()))
                                return true;
        }

        return false;
}

bool BuildingPlacerClass::isTileBuildable(TilePosition tile, BWAPI::UnitType type, bool ignoreReservations) const
{
        if(!BWAPI::Broodwar->isBuildable(tile))
                return false;

        if(type.getRace() == BWAPI::Races::Zerg)
        {
                if(!type.isResourceDepot() && !BWAPI::Broodwar->hasCreep(tile))
                        return false;
        }
        else if(BWAPI::Broodwar->hasCreep(tile))
                return false;

        return !isTileBlocked(tile, type, ignoreReservations);
}

bool BuildingPlacerClass::isTileWalkable(TilePosition tile, bool ignoreReservations) const
{
        if(!MapHelper::isTileWalkable(tile))
                return false;

        return !isTileBlocked(tile, BWAPI::UnitTypes::None, ignoreReservations);
}

std::pair<TilePosition, Base> BuildingPlacerClass::getRefineryLocation() const
{
        for each(Base base in baseToBuildAtOrder())
        {
                for each(Unit geyser in base->getGeysers())
                {
                        if(!isReserved(geyser->getTilePosition()))
                                return std::make_pair(geyser->getTilePosition(), base);
                }
        }

        return std::make_pair(BWAPI::TilePositions::None, Base());
}

bool baseCompare(const Base &i, const Base &j)
{
        if(BWAPI::Broodwar->getFrameCount() < 12000)
        {
                if(i->isStartLocation())
                {
                        if(!j->isStartLocation())
                                return true;
                }
                else if(j->isStartLocation())
                        return false;
        }

        return (i->getNumberOfTechBuildings() > j->getNumberOfTechBuildings());
}

bool baseComparePylon(const Base &i, const Base &j)
{
        // Prioritise a base without a depot the lowest
        if(i->getResourceDepot())
        {
                if(!j->getResourceDepot())
                        return true;
        }
        else if(!j->getResourceDepot())
                return false;

        // Next prioritise the base that doesn't have a pylon
        int iCount = 0;
        for each(Unit building in i->getBuildings())
        {
                if(building->getType() == BWAPI::UnitTypes::Protoss_Pylon && building->getPlayer() == BWAPI::Broodwar->self())
                        ++iCount;
        }

        int jCount = 0;
        for each(Unit building in j->getBuildings())
        {
                if(building->getType() == BWAPI::UnitTypes::Protoss_Pylon && building->getPlayer() == BWAPI::Broodwar->self())
                        ++jCount;
        }

        if(iCount == 0)
        {
                if(jCount != 0)
                        return true;
        }
        else if(jCount == 0)
                return false;

        // Finally prioritise using the default sort
        return baseCompare(i, j);
}

bool baseCompareDefense(const Base &i, const Base &j, BWAPI::UnitType type)
{
        int iCount = 0;
        for each(Unit building in i->getBuildings())
        {
                if(building->getType() == type && building->getPlayer() == BWAPI::Broodwar->self())
                        ++iCount;
        }

        int jCount = 0;
        for each(Unit building in j->getBuildings())
        {
                if(building->getType() == type && building->getPlayer() == BWAPI::Broodwar->self())
                        ++jCount;
        }

        return jCount > iCount;
}

std::vector<Base> BuildingPlacerClass::baseToBuildAtOrder(BWAPI::UnitType type) const
{
        std::vector<Base> basesOrder = baseToBuildAtOrder();

        if(type == BWAPI::UnitTypes::Protoss_Pylon)
        {
                std::sort(basesOrder.begin(), basesOrder.end(), baseComparePylon);
        }
        else if(type == BWAPI::UnitTypes::Protoss_Photon_Cannon || type == BWAPI::UnitTypes::Terran_Missile_Turret)
        {
                std::vector<Base> newBasesOrder;
                for each(Base base in basesOrder)
                {
                        if(base->getMinerals().empty())
                                continue;

                        bool hasPylon = type.requiresPsi() ? false : true;

                        if(!hasPylon)
                        {
                                std::set<Unit> buildings = base->getBuildings();
                                for each(Unit building in buildings)
                                {
                                        if(building->getType() == BWAPI::UnitTypes::Protoss_Pylon && building->getPlayer() == BWAPI::Broodwar->self() && building->isCompleted())
                                                hasPylon = true;
                                }
                        }

                        if(hasPylon)
                                newBasesOrder.push_back(base);
                }

                std::sort(newBasesOrder.begin(), newBasesOrder.end(), boost::bind<bool>(&baseCompareDefense, _1, _2, type));

                return newBasesOrder;
        }

        return basesOrder;
}

std::vector<Base> BuildingPlacerClass::baseToBuildAtOrder() const
{
        std::vector<Base> returnValue;

        for each(Base base in BaseTracker::Instance().getPlayerBases())
        {
                if(!base->isUnderAttack())
                        returnValue.push_back(base);
        }

        std::sort(returnValue.begin(), returnValue.end(), baseCompare);

        return returnValue;
}
bool BuildingPlacerClass::isAddonBuilder(int x, int y) const
{
        std::map<TilePosition, BWAPI::UnitType>::const_iterator it = mPermanentReserved.find(TilePosition(x, y));
        if(it != mPermanentReserved.end())
        {
                if(UnitHelper::hasAddon(it->second))
                        return true;
        }

        for each(Unit unit in UnitTracker::Instance().getUnitsOnTile(x, y))
        {
                if(!unit->isLifted() && UnitHelper::hasAddon(unit->getType()))
                        return true;
        }

        return false;
}

bool BuildingPlacerClass::isAddonBuildable(TilePosition position) const
{
        for(int x = position.x() + 4; x < position.x() + 6; ++x)
                for(int y = position.y() + 1; y < position.y() + 3; ++y)
                        if(!isTileBuildable(TilePosition(x, y), BWAPI::UnitTypes::Terran_Machine_Shop))
                                return false;

        return true;
}

std::pair<TilePosition, Base> BuildingPlacerClass::getExpandLocation(bool gas) const
{
        std::set<Base> enemyBases = BaseTracker::Instance().getEnemyBases();

        Base basePos;
        int closestDistance = std::numeric_limits<int>::max();
        int furthestDistance = std::numeric_limits<int>::min();
        ExpandType type = ExpandType::expNone;

        std::set<BorderPosition> myRegions = BorderTracker::Instance().getBorderPositions(PositionType::BotControlRegion);
        std::set<BorderPosition> enemyRegions = BorderTracker::Instance().getBorderPositions(PositionType::EnemyControlRegion);

        for(std::set<BorderPosition>::const_iterator it = myRegions.begin(); it != myRegions.end(); ++it)
        {
                for each(Base base in it->mRegion->getBases())
                {
                        rememberBestExpandLocation(base, basePos, closestDistance, furthestDistance, type, gas, enemyBases);
                }
        }

        if(type == ExpandType::expNone)
        {
                for each(Base base in BaseTracker::Instance().getAllBases())
                {
                        if(enemyRegions.count(BorderPosition(PositionType::EnemyControlRegion, base->getRegion())) != 0)
                                continue;

                        rememberBestExpandLocation(base, basePos, closestDistance, furthestDistance, type, gas, enemyBases);
                }
        }

        if(type == ExpandType::expNone)
        {
                for each(Base base in BaseTracker::Instance().getAllBases())
                {
                        rememberBestExpandLocation(base, basePos, closestDistance, furthestDistance, type, gas, enemyBases);
                }
        }

        if(type != ExpandType::expNone)
                return std::make_pair(basePos->getCenterBuildLocation(), basePos);
        else
                return std::make_pair(BWAPI::TilePositions::None, Base());
}

std::set<TilePosition> BuildingPlacerClass::getSurroundingTiles(TilePosition position, BWAPI::UnitType type, bool ignoreReservations) const
{
        std::set<TilePosition> tiles;
        int y1 = position.y() + type.tileHeight();
        int x1 = position.x() - 1;
        int y2 = position.y() + type.tileHeight() - 1;
        int x2 = position.x() - 1;

        while(true)
        {
                TilePosition t1(x1, y1);
                if(isTileWalkable(t1, ignoreReservations))
                        tiles.insert(t1);

                TilePosition t2(x2, y2);
                if(isTileWalkable(t2, ignoreReservations))
                        tiles.insert(t2);

                if(x1 < position.x() + type.tileWidth())
                        x1++;
                else
                        y1--;

                if(y1 == y2 && x1 == x2)
                        break;

                if(y2 > position.y() - 1)
                        y2--;
                else
                        x2++;
        }

        return tiles;
}

void BuildingPlacerClass::rememberBestExpandLocation(Base base, Base& bestBase, int& closestDistance, int& furthestDistance, ExpandType& type, bool gas, std::set<Base> enemyBases) const
{
        if(base->getPlayer() == NULL || (!base->isActive() && base->getPlayer() == BWAPI::Broodwar->self()))
        {
                if(base->getCenterBuildLocation() == BWAPI::TilePositions::None)
                        return;

                if(gas && base->getGeysers().empty() && base->getRefineries().empty())
                        return;

                if(base->isMinedOut())
                        return;

                if(base->isMyBase() && base->isUnderAttack())
                        return;

                ScoutType lastScoutType = ScoutManager::Instance().getLastScoutType(base);
                int lastScoutTime = ScoutManager::Instance().getLastScoutTime(base);
                if(BWAPI::Broodwar->getFrameCount() > 6200 && (lastScoutType == ScoutType::FailedWithGroundLow || lastScoutType == ScoutType::FailedWithGroundHigh || lastScoutType == ScoutType::FailedWithAir))
                        return;

                //TODO: when we have transport code, remove this if we have a transport
                bool isConnected = false;
                for each(Unit unit in UnitTracker::Instance().selectAllUnits(BWAPI::Broodwar->self()->getRace().getWorker()))
                {
                        if(unit->hasPath(Position(base->getCenterBuildLocation())))
                        {
                                isConnected = true;
                                break;
                        }
                }

                if(!isConnected)
                        return;

                if(isLocationBuildable(base->getCenterBuildLocation(), BWAPI::Broodwar->self()->getRace().getCenter()))
                {
                        for each(Base myBase in BaseTracker::Instance().getPlayerBases())
                        {
                                if(myBase->getCenterBuildLocation() == BWAPI::TilePositions::None)
                                        continue;

                                int tDistance = MapHelper::getGroundDistance(base->getCenterLocation(), myBase->getCenterLocation());
                                if(tDistance >= 1450 && type != ExpandType::expCloseToMe && !enemyBases.empty())
                                {
                                        for each(Base enemyBase in enemyBases)
                                        {
                                                int enemyDistance = MapHelper::getGroundDistance(base->getCenterLocation(), enemyBase->getCenterLocation());
                                                if(enemyDistance > furthestDistance)
                                                {
                                                        furthestDistance = enemyDistance;
                                                        bestBase = base;
                                                        type = ExpandType::expFurthestFromEnemy;
                                                }
                                        }
                                }
                                else if(tDistance < closestDistance)
                                {
                                        closestDistance = tDistance;
                                        bestBase = base;
                                        type = ExpandType::expCloseToMe;
                                }
                        }
                }
        }
}