#include "stdafx.h"
#include "L2BuildingPlacer.h"

static const int PYLON_POWER_RADIUS = 10;
static const int PYLON_BUILD_RADIUS = 15;

L2BuildingPlacer::L2BuildingPlacer()
  : m_reservedEmplacements(new bool*[BWAPI::Broodwar->mapWidth()])
  , m_needAdditionalPylons(false)
{
  for (int x = 0; x < BWAPI::Broodwar->mapWidth(); x++)
  {
    m_reservedEmplacements[x]= new bool[BWAPI::Broodwar->mapHeight()];
    for (int y = 0; y < BWAPI::Broodwar->mapHeight(); y++)
    {
      m_reservedEmplacements[x][y] = false;
    }
  }
}

L2BuildingPlacer::~L2BuildingPlacer()
{
  for (int x = 0; x < BWAPI::Broodwar->mapWidth(); x++)
  {
    delete[] m_reservedEmplacements[x];
  }
  delete[] m_reservedEmplacements;
}

bool L2BuildingPlacer::needsAdditionalPylons() const
{
  return m_needAdditionalPylons;
}

BWAPI::TilePosition L2BuildingPlacer::getBuildingLocation(BWAPI::Unit* builder, BWAPI::UnitType toBuild, AutoPopulatedLocation* location, int minBuildDistance)
{
  int maxBuildDistance = PYLON_POWER_RADIUS;

  //Find a place for a pylon
  if(toBuild==BWAPI::UnitTypes::Protoss_Pylon)
  {
    maxBuildDistance = PYLON_BUILD_RADIUS;

    while(m_nexusesWithoutPylon.begin() != m_nexusesWithoutPylon.end())
    {
      if( (*m_nexusesWithoutPylon.begin()) != NULL && (*m_nexusesWithoutPylon.begin())->exists())
      {
        BWAPI::TilePosition tempTP = getBuildLocationNear(builder, (*m_nexusesWithoutPylon.begin())->getTilePosition(),toBuild,minBuildDistance,maxBuildDistance);
        if(tempTP!=BWAPI::TilePositions::None)
        {
          return tempTP;
        }
      }
      // TODO: should be set in onBuildingCompleted() instead; this method should be const
      m_nexusesWithoutPylon.erase(m_nexusesWithoutPylon.begin());
    }

    //We need to place the first pylon
    while(minBuildDistance>=1)
    {
      std::pair<AutoPopulatedLocation::building_const_iterator, AutoPopulatedLocation::building_const_iterator> building = location->getOwnBuildings();

      if(building.first == building.second)
      {
        //the base is empty how do we know where to build our pylon location
        BWAPI::TilePosition tempTP = getBuildLocationNear(builder, BWAPI::TilePosition(location->getCurrentCenter()),toBuild,minBuildDistance,maxBuildDistance);
      }

      //The base has no pylon but has building. Build Pylon close
      for( ; building.first != building.second ; ++building.first )
      {
        BWAPI::Unit* unit = (*building.first)->getUnit();
        assert(unit->getPlayer() == BWAPI::Broodwar->self());
        assert(unit->getType() != BWAPI::UnitTypes::Protoss_Probe);
        assert(unit->getType() != BWAPI::UnitTypes::Resource_Mineral_Field);
        assert(unit->getType() != BWAPI::UnitTypes::Resource_Vespene_Geyser);
        BWAPI::TilePosition tempTP = getBuildLocationNear(builder, unit->getTilePosition(),toBuild,minBuildDistance,maxBuildDistance);
        if(tempTP != BWAPI::TilePositions::None)
        {
          return tempTP;
        }
      }
      minBuildDistance--;
    }
  }
  
  //Find a place for a nexus
  else if(toBuild==BWAPI::UnitTypes::Protoss_Nexus)
  {
    BaseLocation* bl = dynamic_cast<BaseLocation*> (location);
    if(bl != NULL)
    {
      const BWTA::BaseLocation* base = bl->getBWTABaseLocation();
      const BWAPI::TilePosition tile = base->getTilePosition();
      if (canBuildHere(NULL, tile, toBuild, false))
      {
        return base->getTilePosition();
      }
      else
      {
        return BWAPI::TilePositions::None;
      }
    }else
    {
      //Why a nexus here
      return BWAPI::TilePositions::None;
    }
  }
  
  //Find a place for an assimilator
  else if(toBuild==BWAPI::UnitTypes::Protoss_Assimilator)
  {    
    if(dynamic_cast<BaseLocation*>(location))
    {
      BaseLocation* bl = dynamic_cast<BaseLocation*> (location);
      const BWTA::BaseLocation* base = bl->getBWTABaseLocation();
      const std::set<BWAPI::TilePosition>& geysers = base->getGeysersPosition();
      for(std::set<BWAPI::TilePosition>::const_iterator it = geysers.begin(); it != geysers.end() ; ++it)
      {
        BWAPI::TilePosition geyser = (*it);
        const std::set<BWAPI::Unit*>& units = BWAPI::Broodwar->getUnitsOnTile(geyser.x(),geyser.y());
        bool canBuild = true;
        for(std::set<BWAPI::Unit*>::const_iterator i = units.begin(); (i!=units.end() && canBuild) ; ++i)
        {
          if((*i)->getType() != BWAPI::UnitTypes::Resource_Vespene_Geyser)
          {
            canBuild = false;
          }
        }
        if(canBuild)
        {
          return geyser;
        }
      }
      //If here there is no empty geyser
      //Send ERROR
    }else
    {
      //Why an assimilator here
      return BWAPI::TilePositions::None;
    }
    //Must get a list of all empty gas in location
    return BWAPI::TilePositions::None;
  }
  
  //This is neither a pylon nor a nexus nor an assimilator. We need power.
  else
  {
    while(minBuildDistance>=0)
    {
      std::pair<AutoPopulatedLocation::unit_type_const_iterator, AutoPopulatedLocation::unit_type_const_iterator> building = location->getOwnUnits(BWAPI::UnitTypes::Protoss_Pylon);

      if(building.first == building.second)
      {
        m_needAdditionalPylons = true;
        return BWAPI::TilePositions::None;
      }

      for( ; building.first != building.second ; building.first = ++(building.first) )
      {
        BWAPI::Unit* unit = (*building.first)->getUnit();
        if(unit->isCompleted())
        {
          BWAPI::TilePosition tempTP = getBuildLocationNear(builder, unit->getTilePosition(),toBuild,minBuildDistance,maxBuildDistance);
          if(tempTP != BWAPI::TilePositions::None)
          {
            //Maybe should reserve the tile here
            return tempTP;
          }
        }
      }
      m_needAdditionalPylons = true;
      minBuildDistance--;
    }
  }
  m_needAdditionalPylons = true;
  return BWAPI::TilePositions::None;
}

void L2BuildingPlacer::reservePosition(BWAPI::TilePosition tile, BWAPI::UnitType toBuild)
{
  //Add it to the reserve list
  for(int x = tile.x() ; x < (tile.x() + toBuild.tileWidth() - 1) ; x++)
  {
    for(int y = tile.y() ; y < (tile.y() + toBuild.tileHeight() - 1) ; y++)
    {
      assert(!m_reservedEmplacements[x][y]);
      m_reservedEmplacements[x][y] = true;
    }
  }
}

void L2BuildingPlacer::unreservePosition(BWAPI::TilePosition tile, BWAPI::UnitType toBuild)
{
  for(int x = tile.x() ; x < (tile.x() + toBuild.tileWidth() - 1) ; x++)
  {
    for(int y = tile.y() ; y < (tile.y() + toBuild.tileHeight() - 1) ; y++)
    {
      assert(m_reservedEmplacements[x][y]);
      m_reservedEmplacements[x][y] = false;
    }
  }
}

bool L2BuildingPlacer::overReservedPosition(BWAPI::TilePosition tile, BWAPI::UnitType toBuild)
{
  if(!tile.isValid())
    return true;
  for(int x = tile.x() ; x < (tile.x() + toBuild.tileWidth() - 1) ; x++)
  {
    for(int y = tile.y() ; y < (tile.y() + toBuild.tileHeight() - 1) ; y++)
    {
      if(x<0 || x>=BWAPI::Broodwar->mapWidth() || y<0 || y>=BWAPI::Broodwar->mapHeight())
        return true;
      if(m_reservedEmplacements[x][y])
        return true;
    }
  }
  return false;
}

bool L2BuildingPlacer::canBuildHere(BWAPI::Unit* builder, BWAPI::TilePosition tile, BWAPI::UnitType type, bool checkExplored)
{
  bool isFree = (!overReservedPosition(tile,type));
  if (!isFree)
  {
    return false;
  }
  bool canBuild = (BWAPI::Broodwar->canBuildHere(builder,tile,type,checkExplored));
  if (!canBuild)
  {
    return false;
  }
  if (type != BWAPI::UnitTypes::Protoss_Nexus)
  {
    const BWTA::BaseLocation* closest = BWTA::getNearestBaseLocation(tile);
    if (closest != NULL)
    {
      const BWAPI::TilePosition nexusTile = closest->getTilePosition();
      // Check if [tile, type] intersects with [nexusTile, Nexus]

      const int x         = tile.x();
      const int xMax      = tile.x() + type.tileWidth();
      const int y         = tile.y();
      const int yMax      = tile.y() + type.tileHeight();

      is_between<int, true> xNexus(nexusTile.x(), nexusTile.x() + BWAPI::UnitTypes::Protoss_Nexus.tileWidth() - 1);
      is_between<int, true> yNexus(nexusTile.y(), nexusTile.y() + BWAPI::UnitTypes::Protoss_Nexus.tileHeight() - 1);

      if ((xNexus(x) || xNexus(xMax)) && (yNexus(y) || yNexus(yMax)))
        return false;
    }
  }

  return true;
}

bool L2BuildingPlacer::canBuildHereWithSpace(BWAPI::Unit* builder, BWAPI::TilePosition tile, BWAPI::UnitType type, int minBuildDistance, bool checkExplored)
{
  if(!canBuildHere(builder,tile,type,checkExplored))
    return false;
  if(minBuildDistance<1)
    return true;
  else if(!canWalkAround(tile,type))
    return false;

  //test if space around building is OK
  int width = type.tileWidth();
  int height = type.tileHeight();
  int buildingTopX = tile.x();
  int buildingTopY = tile.y();

  //Test the top part
  int topX = buildingTopX + width - 1 + minBuildDistance;
  int topY = buildingTopY - 1;
  int botX = buildingTopX - minBuildDistance;
  int botY = buildingTopY - minBuildDistance;

  for(int i = botX ; i <= topX ; i++)
  {
    for(int j = botY ; j <= topY ; j++)
    {
      BWAPI::TilePosition tile = BWAPI::TilePosition(i,j);
      if(tileHasBuilding(tile))
        return false;
    }
  }

  //Test the bottom part
  topX = buildingTopX + width - 1 + minBuildDistance;
  topY = buildingTopY + height - 1 + minBuildDistance;
  botX = buildingTopX - minBuildDistance;
  botY = buildingTopY + height;

  for(int i = botX ; i <= topX ; i++)
  {
    for(int j = botY ; j <= topY ; j++)
    {
      BWAPI::TilePosition tile = BWAPI::TilePosition(i,j);
      if(tileHasBuilding(tile))
        return false;
    }
  }

  //Test the left part
  topX = buildingTopX - 1;
  topY = buildingTopY + height - 1;
  botX = buildingTopX - minBuildDistance;
  botY = buildingTopY;

  for(int i = botX ; i <= topX ; i++)
  {
    for(int j = botY ; j <= topY ; j++)
    {
      BWAPI::TilePosition tile = BWAPI::TilePosition(i,j);
      if(tileHasBuilding(tile))
        return false;
    }
  }

  //Test the right part
  topX = buildingTopX + width - 1 + minBuildDistance;
  topY = buildingTopY + height - 1 ;
  botX = buildingTopX + width;
  botY = buildingTopY;

  for(int i = botX ; i <= topX ; i++)
  {
    for(int j = botY ; j <= topY ; j++)
    {
      BWAPI::TilePosition tile = BWAPI::TilePosition(i,j);
      if(tileHasBuilding(tile))
        return false;
    }
  }

  return true;
}

bool L2BuildingPlacer::canWalkAround(BWAPI::TilePosition tile, BWAPI::UnitType type)
{
  int x = tile.x()-1;
  int xmax = tile.x() + type.tileWidth() + 1;
  int y = tile.y()-1;
  int ymax = tile.y() + type.tileHeight() + 1;
  for(int i = x ; i<=xmax ; i++)
  {
    for(int j = y ; j<=ymax ; j++)
    {
      if(!isTileWalkable(BWAPI::TilePosition(i,j)))
      {
        return false;
      }
      else//Check for gas or mineral
      {
        std::set<BWAPI::Unit*> units = BWAPI::Broodwar->getUnitsOnTile(i,j);
        for(std::set<BWAPI::Unit*>::iterator i = units.begin() ; i!=units.end() ; ++i)
        {
          if((*i)->getType() == BWAPI::UnitTypes::Protoss_Assimilator ||
            (*i)->getType() == BWAPI::UnitTypes::Resource_Mineral_Field ||
            (*i)->getType() == BWAPI::UnitTypes::Resource_Mineral_Field_Type_2 ||
            (*i)->getType() == BWAPI::UnitTypes::Resource_Mineral_Field_Type_3 ||
            (*i)->getType() == BWAPI::UnitTypes::Resource_Vespene_Geyser)
          {
            return false;
          }
        }
      }
    }
  }
  return true;
}

bool L2BuildingPlacer::isTileWalkable(BWAPI::TilePosition tile)
{
  // Make sure units can walk around the building

  // Check all walk tiles instead of the corners?

  int x1=(tile.x()*4);
  int x2=((tile.x()*4)+3);
  int y1=(tile.y()*4);
  int y2=((tile.y()*4)+3);

  return BWAPI::Broodwar->isWalkable(x1, y1) &&
         BWAPI::Broodwar->isWalkable(x2, y1) &&
         BWAPI::Broodwar->isWalkable(x2, y2) && 
         BWAPI::Broodwar->isWalkable(x1, y2);
}

bool L2BuildingPlacer::tileHasBuilding(BWAPI::TilePosition tile)
{
  if(!tile.isValid())
    //One of the tile around the building is not valid, The build minBuildDistance is not respected.
    return false;
  const std::set<BWAPI::Unit*>& unitOnTile = BWAPI::Broodwar->getUnitsOnTile(tile.x(),tile.y());
  if(!unitOnTile.empty())
  {
    for(std::set<BWAPI::Unit*>::const_iterator it = unitOnTile.begin() ; it != unitOnTile.end() ; ++it)
    {
      //There is a unit on the tile that is not the builder
      if(!(*it)->getType().canMove() && (*it)->getPlayer()==BWAPI::Broodwar->self() )
      {
        //the unit cant move. Must be a building, so the minBuildDistance between two building is not respected.
        return true;
      }
    }
  }
  if(m_reservedEmplacements[tile.x()][tile.y()])
  {
    //The tile is reserved for another building
    return true;
  }
  return false;
}

BWAPI::TilePosition L2BuildingPlacer::getBuildLocationNear(BWAPI::Unit* builder, BWAPI::TilePosition tile, BWAPI::UnitType type, int minBuildDistance, int maxBuildDistance)
{
  int x      = tile.x();
  int xMax   = x + maxBuildDistance;
  int y      = tile.y();
  int yMax   = y + maxBuildDistance;
  int length = 1;
  int j      = 0;
  bool first = true;
  int dx     = 0;
  int dy     = 1;

  while ( x<=xMax || y<=yMax ) //We'll ride the spiral to the end
  {
    //if we can build here, return this tile tile
    if (x >= 0 && x < BWAPI::Broodwar->mapWidth() && y >= 0 && y < BWAPI::Broodwar->mapHeight())
      if (this->canBuildHereWithSpace(builder, BWAPI::TilePosition(x, y), type, minBuildDistance, false))
        return BWAPI::TilePosition(x, y);

    //otherwise, move to another tile
    x = x + dx;
    y = y + dy;
    //count how many steps we take in this direction
    j++;
    if (j == length) //if we've reached the end, its time to turn
    {
      //reset step counter
      j = 0;

      //Spiral out. Keep going.
      if (!first)
        length++; //increment step counter if needed

      //first=true for every other turn so we spiral out at the right rate
      first = !first;

      //turn counter clockwise 90 degrees:
      if (dx == 0)
      {
        dx = dy;
        dy = 0;
      }
      else
      {
        dy = -dx;
        dx = 0;
      }
    }
    //Spiral out. Keep going.
  }

  return BWAPI::TilePositions::None;
}

void L2BuildingPlacer::onBuildingCompleted(BWAPI::Unit* building)
{
  if(building->getType() == BWAPI::UnitTypes::Protoss_Pylon)
  {
    m_needAdditionalPylons = false;
  }
  else if(building->getType() == BWAPI::UnitTypes::Protoss_Nexus)
  {
    m_nexusesWithoutPylon.insert(m_nexusesWithoutPylon.end(),building);
  }
}

void L2BuildingPlacer::onFrameDebug()
{
  for (int x = 0; x < BWAPI::Broodwar->mapWidth(); x++)
  {
    for (int y = 0; y < BWAPI::Broodwar->mapHeight(); y++)
    {
      if (m_reservedEmplacements[x][y])
      {
        BWAPI::Broodwar->drawBoxMap(x * TILE_SIZE, y * TILE_SIZE, (x + 1) * TILE_SIZE - 1, (y + 1) * TILE_SIZE - 1, BWAPI::Colors::Yellow, false);
      }
    }
  }
}
