/**
  @file /ai/Strategizer/strategygraph.cpp
  @brief Zdrojovy kod grafu strategicke disponibility.
  
  Zdrojovy kod grafu strategicke disponibility.
  
  @author PZ
  @version 0.1
*/

#include "ai/Strategizer/strategygraph.h"
#include "gui/common/KTime.h"

namespace ai_ns
{
namespace strategizer_ns
{

using namespace World;

bool type_threat::operator<(const struct type_threat& t2)
{
  if (threat_disponibility==t2.threat_disponibility)
  {
    return (threat_weight<t2.threat_weight);
  }
  else
    return (threat_disponibility<t2.threat_disponibility);
}

bool type_help_needed::operator<(const struct type_help_needed& thn)
{
  return (importance<thn.importance);
}

/* CStrVertex implementace */
CStrVertex::CStrVertex()
{
}

CStrVertex::CStrVertex(TDipOwnership dip)
{
  setDipOwnership(dip);
}

CStrVertex::~CStrVertex()
{
}

CStrEdge* CStrVertex::createEdge(CStrVertex* vref)
{ 
  return 0;
}

#ifdef _K_EDITOR_
const char* CStrVertex::getClassName()
{ 
  return typeid(*this).name();
}
#endif

/* CStaticEntity implementace */
CStaticEntity::CStaticEntity()
{
  guarded=false;
}

CStaticEntity::CStaticEntity(TDipOwnership dip)
:CStrVertex(dip)
{
}

bool CStaticEntity::operator<(const CStaticEntity* & ose)
{
  return (this->getPrice()<ose->getPrice());
}

/* CCity implementace */
CCity::CCity()
{
  int cpc;
  for(cpc=0;cpc<MAX_CITY_SIZE;cpc++)
  {
    position[cpc]=-1;
  }
}

CCity::CCity(TDipOwnership dip)
:CStaticEntity(dip)
{
  int cpc;
  for(cpc=0;cpc<MAX_CITY_SIZE;cpc++)
  {
    position[cpc]=-1;
  }
}

/* CBuilding implementace */
CBuilding::CBuilding()
{
}

CBuilding::CBuilding(TDipOwnership dip)
:CStaticEntity(dip)
{
}

/* CDynamicEntity implementace */
CDynamicEntity::CDynamicEntity()
{
}

CDynamicEntity::CDynamicEntity(TDipOwnership dip)
:CStrVertex(dip)
{
}

CStrEdge* CDynamicEntity::createEdge(CStrVertex* vref)
{
  if ((this->getDipOwnership()!=My) && (vref->getDipOwnership()!=My))
  {
    // hrany mezi cizimi entitami me nezajimaji
    return 0;
  }

  if (dynamic_cast<CStaticEntity*>(vref)) // jednotka --> staticka entita
  {
    CStrEdge* rv=new CStrEdge();
    rv->vertex_from=this->getID();
    rv->vertex_to=vref->getID();
    return rv;
  }
  else
  if (dynamic_cast<CDynamicEntity*>(vref)) // jednotka --> jednotka
  {
      if ((this->getDipOwnership()==My) && (vref->getDipOwnership()==My))
      {
        // hrany mezi vlastnimi jednotkami me nezajimaji
        return 0;
      }
      CAttackEdge* rv=new CAttackEdge();
      rv->vertex_from=this->getID();
      rv->vertex_to=vref->getID();
      return rv;
  }
  return 0;
}

/* CUnit implementace */
CUnit::CUnit()
{
}

CUnit::CUnit(TDipOwnership dip)
:CDynamicEntity(dip)
{
}

/* CStrEdge implementace */

#ifdef _K_EDITOR_
const char* CStrEdge::getClassName()
{ 
  return typeid(*this).name();
}
#endif

/* CAttackEdge implementace */

/* CStrGraph implementace */
CStrGraph::CStrGraph(TPacket_AI_LetsGo* initPackage,int player_id,PLAYER_TYPE ai_level)
{
  this->rememberFloodFilledMap=0;
  this->rememberedFloodFillForUnit=0;
  SIP=initPackage;
  GLOBALLOGID(PRIORITY_AI_ALLOC, "PrivAllocatedMarkMap ln 174 strategygraph");
  this->PrivAllocatedMarkMap=(bool*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(bool));
  this->PrivAllocatedFloodMask=(int*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(int));
  this->player_id=player_id;
  switch (ai_level)
  {
    case PT_AI_1:// umela inteligence - zacatecnik
      ai_level_difficulty_constant=2;
      break;
    case PT_AI_2:// umela inteligence - pokrocily
      ai_level_difficulty_constant=1;
      break;
    case PT_AI_3:// umela inteligence - expert
      ai_level_difficulty_constant=0;
      break;
    default:ai_level_difficulty_constant=0;
  }

  vertices.clear();
  edges.clear();

  int tcounter;
  for(tcounter=0;tcounter<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcounter++) threats[tcounter].clear();
  needs.clear();
  sources.clear();

  needed_helps.clear();
  non_defending_targets.clear();
  not_used_sources.clear();
}

CStrGraph::~CStrGraph()
{
  KMemFree(this->PrivAllocatedFloodMask);
  KMemFree(this->PrivAllocatedMarkMap);
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;

  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++) delete (*vertIt);
  vertices.clear();
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++) delete (*edgeIt);
  edges.clear();

  int tcounter;
  for(tcounter=0;tcounter<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcounter++) threats[tcounter].clear();
  needs.clear();
  sources.clear();

  needed_helps.clear();
  non_defending_targets.clear();
  not_used_sources.clear();
}

int CStrGraph::enlistVertex(CStrVertex* v)
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  
  if (vertices.empty())
  {
    vertices.push_back(v);
    vertIt=vertices.begin();
    (*vertIt)->setID(1);
    return 1;
  }

  int tempID=(*(vertices.begin()))->getID();
  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
    if (((*vertIt)->getID()-1)>tempID)
    {
      vertIt=vertices.insert(vertIt,v);
      (*vertIt)->setID(tempID+1);
      return tempID+1;
    }
    else
    {
      tempID=(*vertIt)->getID();
    }
  }
  // sem se dostane, pokud jsou vrcholy setrizene dle IDcek bez mezer
  vertices.push_back(v);
  vertIt=vertices.end()-1;
  (*vertIt)->setID(tempID+1);
  return tempID+1;
}

void CStrGraph::enlistVertexWithID(CStrVertex* v,int id) throw(E_8K_AI_Strategy_NotUniqueVertexID)
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  
  if (!checkUniqueVerticeID(id))
  {
    THROW(E_8K_AI_Strategy_NotUniqueVertexID,"ID pridavaneho vrcholu neni unikatni.")
  }

  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
    if ((*vertIt)->getID()>id)
    {
      vertIt=vertices.insert(vertIt,v);
      (*vertIt)->setID(id);
      return;
    }
  }
  vertices.push_back(v);
  vertIt=vertices.end()-1;
  (*vertIt)->setID(id);
}

void CStrGraph::removeVertex(int vertexID) throw(E_8K_AI_Strategy_VertexIDNotFound)
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  
  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
    if ((*vertIt)->getID()==vertexID)
    {
      delete (*vertIt);
      vertices.erase(vertIt);
      return;
    }
  }
  THROW(E_8K_AI_Strategy_VertexIDNotFound,"Vrchol s danym ID nenalezen.")
}

int CStrGraph::enlistEdge(CStrEdge* e)
{
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  
  if (edges.empty())
  {
    edges.push_back(e);
    edgeIt=edges.begin();
    (*edgeIt)->setID(1);
    return 1;
  }

  int tempID=(*(edges.begin()))->getID();
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    if (((*edgeIt)->getID()-1)>tempID)
    {
      edgeIt=edges.insert(edgeIt,e);
      (*edgeIt)->setID(tempID+1);
      return tempID+1;
    }
    else
    {
      tempID=(*edgeIt)->getID();
    }
  }
  // sem se dostane, pokud jsou hrany setrizene dle IDcek bez mezer
  edges.push_back(e);
  edgeIt=edges.end()-1;
  (*edgeIt)->setID(tempID+1);
  return tempID+1;
}

void CStrGraph::enlistEdgeWithID(CStrEdge* e,int id) throw(E_8K_AI_Strategy_NotUniqueEdgeID)
{
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  
  if (!checkUniqueEdgeID(id))
  {
    THROW(E_8K_AI_Strategy_NotUniqueEdgeID,"ID pridavane hrany neni unikatni.")
  }

  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    if ((*edgeIt)->getID()>id)
    {
      edgeIt=edges.insert(edgeIt,e);
      (*edgeIt)->setID(id);
      return;
    }
  }
  edges.push_back(e);
  edgeIt=edges.end()-1;
  (*edgeIt)->setID(id);
}

void CStrGraph::removeEdge(int edgeID) throw(E_8K_AI_Strategy_EdgeIDNotFound)
{
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    if ((*edgeIt)->getID()==edgeID)
    {
      delete (*edgeIt);
      edges.erase(edgeIt);
      return;
    }
  }
  THROW(E_8K_AI_Strategy_EdgeIDNotFound,"Hrana s danym ID nenalezena.")
}

void CStrGraph::createEdges(int verticeID,bool both_directions) throw(E_8K_AI_Strategy_VertexIDNotFound)
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt2;
  CStrEdge* tempedge;

  for (vertIt=vertices.begin();((vertIt!=vertices.end()) && ((*vertIt)->getID()!=verticeID));vertIt++);
  if (vertIt==vertices.end())
  {
    THROW(E_8K_AI_Strategy_VertexIDNotFound,"Vrchol s danym ID nenalezen.");
  }

  for (vertIt2=vertices.begin();vertIt2!=vertices.end();vertIt2++)
  {
    if ((*vertIt2)->getID()!=(*vertIt)->getID())
    {
      if (tempedge=(*vertIt)->createEdge(*vertIt2))
      {
        enlistEdge(tempedge);
      }
      if (both_directions)
      {
        if (tempedge=(*vertIt2)->createEdge(*vertIt))
        {
          enlistEdge(tempedge);
        }
      }
    }
  }

}

void CStrGraph::createEdgesForAllVertices()
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt2;
  CStrEdge* tempedge;

  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
//    for (vertIt2=vertIt;vertIt2!=vertices.end();vertIt2++) <- why was this here ??? I guess it was a bug
    for (vertIt2=vertices.begin();vertIt2!=vertices.end();vertIt2++)
    {
      if (vertIt!=vertIt2) // this is going to be sorted by unit_id
      {
        if (tempedge=(*vertIt)->createEdge(*vertIt2))
        {          
          enlistEdge(tempedge);
        }
      }
    }
  }

  // this is useless if I made the modification above

/*  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
//    for (vertIt2=vertIt;vertIt2!=vertices.end();vertIt2++)
    for (vertIt2=vertices.begin();vertIt2!=vertices.end();vertIt2++)
    {
      if (vertIt!=vertIt2)
      {
//        if (tempedge=(*vertIt)->createEdge(*vertIt2))
//        {          
  //    x       CStrVertex* vf=tempedge->vertex_from;
  //    x        COORDS sh;
  //    x        sh.x=vf->getPosX();
  //    x        sh.y=vf->getPosY();
  //    x        pfr.unit_id=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit;
  //
//          enlistEdge(tempedge);
//        }
        if (tempedge=(*vertIt2)->createEdge(*vertIt))
        {
          enlistEdge(tempedge);
        }
      }
    }
  }
*/

}

CStrEdge* CStrGraph::findEdge(int vertex_from_id,int vertex_to_id)
{
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    if (((*edgeIt)->vertex_from==vertex_from_id) && ((*edgeIt)->vertex_to==vertex_to_id))
    {
      return (*edgeIt);
    }
  }
  return 0;
}

bool CStrGraph::checkUniqueVerticeID(int id)
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  
  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
    if ((*vertIt)->getID()==id)
    {
      return false;
    }
  }
  return true;
}

bool CStrGraph::checkUniqueEdgeID(int id)
{
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    if ((*edgeIt)->getID()==id)
    {
      return false;
    }
  }
  return true;
}

CStrVertex* CStrGraph::getVertexPointer(int vertexID) throw(E_8K_AI_Strategy_VertexIDNotFound)
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  
  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
    if ((*vertIt)->getID()==vertexID)
    {
      return (*vertIt);
    }
  }
  THROW(E_8K_AI_Strategy_VertexIDNotFound,"Vrchol s danym ID nenalezen.")
}

CStrEdge* CStrGraph::getEdgePointer(int edgeID) throw(E_8K_AI_Strategy_EdgeIDNotFound)
{
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    if ((*edgeIt)->getID()==edgeID)
    {
      return (*edgeIt);
    }
  }
  THROW(E_8K_AI_Strategy_EdgeIDNotFound,"Vrchol s danym ID nenalezen.")
}

std::VERTEX_CONTAINER<CStrVertex*>* CStrGraph::getVertices()
{
  return (&vertices);
}

std::EDGE_CONTAINER<CStrEdge*>* CStrGraph::getEdges()
{
  return (&edges);
}

// This takes a bit long 
void CStrGraph::computeGraphEdgesValues(int playerID)
{

  GLOBALLOGID(PRIORITY_AI_FLOODFILL, "Compute edges");


  // I moved some repeated cyclus here
  fillMarkMap(playerID);

  // compute graph disponibility, action points
  std::EDGE_CONTAINER<CStrEdge*>* edc=getEdges();
  std::EDGE_CONTAINER<CStrEdge*>::iterator edIt;
/*

  // I moved it here ... it was repeated in the cyclus in city case
  // I hope this change doesnt make something wrong :)
  GLOBALLOGID(PRIORITY_AI_ALLOC, "AllocatedMarkMap ln 515 strategygraph");
        ai_ns::pathfind_ns::PF_MARKMAP AllocatedMarkMap=(bool*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(bool));
        int i;
  GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 521 strategygraph");
        for(i=0;i<(SIP->map->width()*SIP->map->height());i++)
        {
          if (VISIBILITY_FOR_PLAYER_ON_HEXID(SIP->visibility_maps,playerID,i)==VI_NEVER_SEEN)
          {
            AllocatedMarkMap[i]=true;
          }
          else
          {
            AllocatedMarkMap[i]=false;
          }
        }
        ai_ns::pathfind_ns::FLOOD_MASK AllocatedFloodMask=(int*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(int));
*/

  this->rememberFloodFilledMap=1; // I can use what I have counted before !!!

  int last_computed_dispPath_id=-1; // id jednotky

  for(edIt=(*edc).begin();edIt!=(*edc).end();edIt++)
  {
    CStrVertex* vf=getVertexPointer((*edIt)->vertex_from);
    CStrVertex* vt=getVertexPointer((*edIt)->vertex_to);

    GLOBALLOGID(PRIORITY_AI_ALLOC, "\nVertex start at %i",gui::KTime());

    if (dynamic_cast<CAttackEdge*>(*edIt)) // jednotka --> jednotka
    {
      CAttackEdge* ae=dynamic_cast<CAttackEdge*>(*edIt);
      COORDS sh;
      COORDS th;
      sh.x=vf->getPosX();
      sh.y=vf->getPosY();
      th.x=vt->getPosX();
      th.y=vt->getPosY();
      COORDS nfh=getActionPoint(playerID,sh,th);
      ae->setActionPointX(nfh.x);
      ae->setActionPointY(nfh.y);
      if (INVALID_COORDS(nfh))
      {
        ae->setTimeDisponibility(NOT_ACCESIBLE_DISPONIBILITY);
      }
      else
      {
        PACKET_PATHFIND_REQUEST pfr;
        pfr.unit_id=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit;
        pfr.from=sh;
        TDipOwnership odo;
        if (vf->getDipOwnership()==My) // od me jednotky vede hrana k cizi
        {
          odo=vt->getDipOwnership();
        }
        else
        if (vt->getDipOwnership()==My) // od cizi jednotky vede hrana k me
        {
          odo=vf->getDipOwnership();
        }
        else
        {
          THROW(E_8K_AI_Strategy_InvalidAttackEdge,"Invalidni utocna hrana");
        }
        switch (odo)
        {
          case Ally:pfr.to=th;
                    pfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_IgnoreMyUnitsAndTargetUnit;
                    break;
          case Truce:
          case Enemy:
          case War:pfr.to=nfh;
                   pfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
                   break;
          default:GLOBALLOGID(PRIORITY_FATAL, "AI FATAL ERROR: Neexistujici diplomaticky vztah.");
                  //break;
        }

        pfr.points_of_movement=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW START 596 unit->unit x=%i y=%i uid=%i TO x=%i y=%i uid=%i",sh.x,sh.y,pfr.unit_id,th.x,th.y,((SIP->map->getHexAt(th.x,th.y))->data()).unit);
        TPATH* dispPath=(TPATH*) KSendGlobalMessage(MSG_PATHFIND_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pfr);
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW END 596");
        if (!dispPath)
        {
          ae->setTimeDisponibility(NOT_ACCESIBLE_DISPONIBILITY);
        }
        else
        {
          TPATH_ITERATOR dispPathIt=dispPath->begin();
          int turn_count=0;
          int akt_pom=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
          while (dispPathIt!=dispPath->end())
          {
            if (akt_pom<dispPathIt->step_cost)
            {
              akt_pom=UNIT_TYPE_ON_HEX(SIP->map,SIP->rules,SIP->living_units,sh.x,sh.y).max_points_of_movement;
              turn_count++;
            }
            else
            {
              akt_pom-=dispPathIt->step_cost;
            }
            dispPathIt++;
          }
          if ((pfr.pathfind_transparency!=ai_ns::pathfind_ns::PFT_IgnoreMyUnits) && (pfr.pathfind_transparency!=ai_ns::pathfind_ns::PFT_IgnoreMyUnitsAndTargetUnit) && (akt_pom==0)) turn_count++; // protoze zautocit muze az v dalsim kole
          ae->setTimeDisponibility(turn_count);
          delete dispPath;
        }
      }
    }
    else // jednotka --> staticka entita
    {
      if (dynamic_cast<CCity*>(vt)) // jednotka --> mesto
      {
        COORDS sh;
        sh.x=vf->getPosX();
        sh.y=vf->getPosY();

        if (  this->rememberedFloodFillForUnit!=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit   )
        {
          PACKET_FLOODFILL_REQUEST pfr;
          pfr.unit_id=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit;
          this->rememberedFloodFillForUnit=pfr.unit_id;  // remember which unit has the filled map
          pfr.start_hex=sh;
          pfr.mark_map=  this->PrivAllocatedMarkMap;
          pfr.flood_mask=this->PrivAllocatedFloodMask;
          pfr.flooding_transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
          GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW START 641 unit->city x=%i y=%i uid=%i",sh.x,sh.y,pfr.unit_id);
          KSendGlobalMessage(MSG_FLOODFILL_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pfr);
          GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW END 641");
        }

//        GLOBALLOGID(PRIORITY_AI_ALLOC, "Destroyed -> In front of");
        
//        KMemFree(AllocatedMarkMap); - not now, its in the end

        int bv=-1;
        int ncs=-1;
        int cpcs=((CCity*) vt)->getCitySize();
        int cpit;
        for(cpit=0;cpit<cpcs;cpit++)
        {
          if (this->PrivAllocatedFloodMask[(((CCity*) vt)->position)[cpit]]!=FLOOD_MASK_VALUE_NOT_ACCESSIBLE)
          {
            if ((bv<0) || (bv>this->PrivAllocatedFloodMask[(((CCity*) vt)->position)[cpit]]))
            {
              ncs=(((CCity*) vt)->position)[cpit];
              bv=this->PrivAllocatedFloodMask[(((CCity*) vt)->position)[cpit]];
            }
          }
        }
//        KMemFree(AllocatedFloodMask); - not now, its in the end

        COORDS th;
        th.x=ncs%SIP->map->width();
        th.y=ncs/SIP->map->width();
        PACKET_PATHFIND_REQUEST pathfr;
        pathfr.unit_id=UNIT_ID_ON_HEX(SIP->map,sh.x,sh.y);
        pathfr.from=sh;
        pathfr.to=th;
        pathfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_IgnoreMyUnitsAndTargetUnit;
        pathfr.points_of_movement=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW START 675 unit->city x=%i y=%i uid=%i TO x=%i y=%i",sh.x,sh.y,((SIP->map->getHexAt(sh.x,sh.y))->data()).unit,th.x,th.y);
        TPATH* dispPath=(TPATH*) KSendGlobalMessage(MSG_PATHFIND_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pathfr);
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW END 675");
        if (!dispPath)
        {
          (*edIt)->setTimeDisponibility(NOT_ACCESIBLE_DISPONIBILITY);
        }
        else
        {
          TPATH_ITERATOR dispPathIt=dispPath->begin();
          int turn_count=0;
          int akt_pom=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
          while (dispPathIt!=dispPath->end())
          {
            if (akt_pom<dispPathIt->step_cost)
            {
              akt_pom=UNIT_TYPE_ON_HEX(SIP->map,SIP->rules,SIP->living_units,sh.x,sh.y).max_points_of_movement;
              turn_count++;
            }
            else
            {
              akt_pom-=dispPathIt->step_cost;
            }
            dispPathIt++;
          }
          (*edIt)->setTimeDisponibility(turn_count);
          delete dispPath;
        }

      }
      else // jednotka --> budova
      {
        COORDS sh;
        COORDS th;
        sh.x=vf->getPosX();
        sh.y=vf->getPosY();
        th.x=vt->getPosX();
        th.y=vt->getPosY();
        PACKET_PATHFIND_REQUEST pfr;
        pfr.unit_id=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit;
        pfr.from=sh;
        int bpid=BUILDING_ON_HEX(SIP->map,SIP->living_buildings,th.x,th.y).player;
        if (bpid==playerID)
        {
          pfr.to=th;
          pfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_IgnoreMyUnitsAndTargetUnit;
        }
        else
        {
          if (!(IS_UNIT_ON_HEX(SIP->map,th.x,th.y))) // je budova prazdna?
          {
            pfr.to=th;
            pfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_IgnoreTargetUnit;
          }
          else
          {
            pfr.to=th;
            pfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_IgnoreMyUnitsAndTargetUnit;
          }
        }
        pfr.points_of_movement=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW START 736 unit->building x=%i y=%i uid=%i TO x=%i y=%i bid=%i",sh.x,sh.y,pfr.unit_id,th.x,th.y,SIP->map->getHexAt(th.x,th.y)->data().building);
        TPATH* dispPath=(TPATH*) KSendGlobalMessage(MSG_PATHFIND_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pfr);
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF computeGraphEdgesValues NOW END 736");
        if (!dispPath)
        {
          (*edIt)->setTimeDisponibility(NOT_ACCESIBLE_DISPONIBILITY);
        }
        else
        {
          TPATH_ITERATOR dispPathIt=dispPath->begin();
          int turn_count=0;
          int akt_pom=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
          while (dispPathIt!=dispPath->end())
          {
            if (akt_pom<dispPathIt->step_cost)
            {
              akt_pom=UNIT_TYPE_ON_HEX(SIP->map,SIP->rules,SIP->living_units,sh.x,sh.y).max_points_of_movement;
              turn_count++;
            }
            else
            {
              akt_pom-=dispPathIt->step_cost;
            }
            dispPathIt++;
          }
          (*edIt)->setTimeDisponibility(turn_count);
          delete dispPath;
        }
      }
    }

  }

  GLOBALLOGID(PRIORITY_AI_FLOODFILL, "Compute edges end");

  this->rememberFloodFilledMap=0; // set it back

  
//  KMemFree(AllocatedMarkMap);
//  KMemFree(AllocatedFloodMask);
}

COORDS_ARRAY CStrGraph::getAttackPossibleHexes(int playerID,COORDS sh,COORDS th) throw(E_8K_AI_Strategy_NoUnitPresent)
{
  if (!IS_UNIT_ON_HEX(SIP->map,sh.x,sh.y))
  {
	  THROW(E_8K_AI_Strategy_NoUnitPresent,"Na zdrojovem hexu neni zadna jednotka.")
  }
  // na cilovem hexu ani nemusi byt jednotka
  /*
  if (!IS_UNIT_ON_HEX(SIP->map,th.x,th.y))
  {
	  THROW(E_8K_AI_Strategy_NoUnitPresent,"Na cilovem hexu neni zadna jednotka.")
  }
  */

  PACKET_GET_INVERSE_ATTACK_RANGE pgiar;
  pgiar.type=MSG_GET_INVERSE_ATTACK_RANGE;
  pgiar.player_id=playerID;
  pgiar.attacker=UNIT_ID_ON_HEX(SIP->map,sh.x,sh.y);
  pgiar.target=(th.y*SIP->map->width())+th.x;
  TPacket_RET_INVERSE_ATTACK_RANGE* aph_result=(TPacket_RET_INVERSE_ATTACK_RANGE*) KSendGlobalMessage(MSG_WORLD_AI,MOD_STRATEGY, MOD_WORLD_SERVER, &pgiar);

  COORDS_ARRAY nhs;
  nhs.clear();
  std::vector<HEX_ID>::iterator iIt;
  for (iIt=aph_result->attack_range.begin();iIt!=aph_result->attack_range.end();iIt++)
  {
    COORDS tmpcoords;
    tmpcoords.x=(*iIt)%SIP->map->width();
    tmpcoords.y=(*iIt)/SIP->map->width();
    nhs.push_back(tmpcoords);
  }
  delete aph_result;
  return nhs;
}


void CStrGraph::fillMarkMap(int playerID)
{
  int i;
  GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 812 strategygraph");
  for(i=0;i<(SIP->map->width()*SIP->map->height());i++)
  {

    if   ((SIP->map->insideBorders(i)) && (VISIBILITY_FOR_PLAYER_ON_HEXID(SIP->visibility_maps,playerID,i)==VI_NEVER_SEEN))
//    if                                  (VISIBILITY_FOR_PLAYER_ON_HEXID(SIP->visibility_maps,playerID,i)==VI_NEVER_SEEN)
    {
      this->PrivAllocatedMarkMap[i]=true;
    }
    else
    {
      this->PrivAllocatedMarkMap[i]=false;
    }
  }
}

// TOTO TRVA DLOUHO
COORDS CStrGraph::getActionPoint(int playerID,COORDS sh,COORDS th) throw(E_8K_AI_Strategy_PlayerCantSeeTarget)
{
  if (VISIBILITY_FOR_PLAYER_ON_HEX(SIP->visibility_maps,playerID,th.x,th.y)==VI_NEVER_SEEN) THROW(E_8K_AI_Strategy_PlayerCantSeeTarget,"Hrac nevidi na sveho nepritele.")

  COORDS rv;
  rv.x=-1;
  rv.y=-1;
  COORDS_ARRAY nhs=getAttackPossibleHexes(playerID,sh,th);
  if (nhs.empty())
  {
    return rv;
  }

//  ai_ns::pathfind_ns::PF_MARKMAP AllocatedMarkMap=(bool*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(bool));
// moved to function above - fillMarkMap
  // TOTO PRESUNOUT
//  ai_ns::pathfind_ns::FLOOD_MASK AllocatedFloodMask=(int*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(int));

//  GLOBALLOGID(PRIORITY_AI_ALLOC, "Destroyed -> Privat");

  if (this->rememberFloodFilledMap==1) 
  {
    if (  this->rememberedFloodFillForUnit!=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit   )
    {
      PACKET_FLOODFILL_REQUEST pfr;
      pfr.unit_id=((SIP->map->getHexAt(sh.x,sh.y))->data()).unit;
      this->rememberedFloodFillForUnit=pfr.unit_id;  // remember which unit has the filled map
      GLOBALLOGID(PRIORITY_AI_ALLOC, "I remember FloodFill for unit %i",this->rememberedFloodFillForUnit);
      pfr.start_hex=sh;
      pfr.mark_map=this->PrivAllocatedMarkMap;
      pfr.flood_mask=this->PrivAllocatedFloodMask;
      pfr.flooding_transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
      KSendGlobalMessage(MSG_FLOODFILL_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pfr);
    }
  }
  
//  KMemFree(AllocatedMarkMap);

  int bv=-1;
  COORDS_ARRAY::iterator nhsIt;
  for(nhsIt=nhs.begin();nhsIt!=nhs.end();nhsIt++)
  {
    if (this->PrivAllocatedFloodMask[(nhsIt->y*SIP->map->width())+nhsIt->x]!=FLOOD_MASK_VALUE_NOT_ACCESSIBLE)
    {
      if ((bv<0) || (bv>this->PrivAllocatedFloodMask[(nhsIt->y*SIP->map->width())+nhsIt->x]))
      {
        rv=(*nhsIt);
        bv=this->PrivAllocatedFloodMask[(nhsIt->y*SIP->map->width())+nhsIt->x];
      }
    }
  }
 // KMemFree(AllocatedFloodMask);
  
  return rv;
}

int* CStrGraph::getLandForDefence(int playerID)
{
  GLOBALLOGID(PRIORITY_AI_ALLOC, "ActionAreaForDefence ln 851 strategygraph");
  int* ActionAreaForDefence=(int*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(int));

  // nastavi "hracovo" uzemi jako vsechny hexy co vidi
  int i;
  GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 866 strategygraph");
  for(i=0;i<SIP->map->width()*SIP->map->height();i++)
	{
    if (VISIBILITY_FOR_PLAYER_ON_HEXID(SIP->visibility_maps,playerID,i)!=World::VI_NEVER_SEEN)
    {
      ActionAreaForDefence[i]=playerID;
    }
	}
  
  return ActionAreaForDefence;

  /*
  // nastavi "hracovo" uzemi Voronoi-like zaplavou dle jeho budov
  int* ActionAreaForDefence=(int*) KMemAlloc((map->width()*map->height())*sizeof(int));
	
  std::vector<THexOwnership> bactemp;
  bactemp.clear();
  THexOwnership bactempitem;
  THexOwnership* bac;
  
  int i;
  for(i=0;i<map->width()*map->height();i++)
	{
    if (VISIBILITY_FOR_PLAYER_ON_HEXID(visibility_maps,playerID,i)!=World::VI_NEVER_SEEN)
    {
      if (IS_BUILDING_ON_HEXID(map,i))
      {
        bactempitem.entityNumber=BUILDING_ON_HEXID(map,living_buildings,i).player;
        bactempitem.x=i%map->width();
        bactempitem.y=i/map->width();
        bactemp.push_back(bactempitem);
      }
    }
	}

  int bacnum=(int) (bactemp.size());
  bac=(THexOwnership*) KMemAlloc(bacnum*sizeof(THexOwnership));
  int tcnt=0;
  for(std::vector<THexOwnership>::iterator btIt=bactemp.begin();btIt!=bactemp.end();btIt++)
  {
    bac[tcnt]=*btIt;
    tcnt++;
  }
  bactemp.clear();

  try
  {
    computeBorders(ActionAreaForDefence,map->height(),map->width(),bacnum,bac,true);
  }
  catch (E_8K_Editor_InvalidCenters e)
  {
    GLOBALLOGID(PRIORITY_FATAL, "AI FATAL ERROR: Invalidni centra entit.");
  }
  
  KMemFree(bac);

  return ActionAreaForDefence;
  */
}

int CStrGraph::getBestStaticDefensePlaceForUnitOnHexID(int hexid,CStaticEntity* stEntity) throw(E_8K_AI_Strategy_NoUnitPresent)
{
  if (!(IS_UNIT_ON_HEXID(SIP->map,hexid))) THROW(E_8K_AI_Strategy_NoUnitPresent,"Hex, na kterem mela byt jednotka je prazdny.");

  if (dynamic_cast<CBuilding*>(stEntity))
  {
/*     GLOBALLOGID(PRIORITY_AI_ALLOC, "AllocatedMarkMap ln 920 strategygraph");
   ai_ns::pathfind_ns::PF_MARKMAP AllocatedMarkMap=(bool*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(bool));
    int i;
    GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 935 strategygraph");
    for(i=0;(i<(SIP->map->width()*SIP->map->height()));i++)
    {
      if ((SIP->map->insideBorders(i)) && (VISIBILITY_FOR_PLAYER_ON_HEXID(SIP->visibility_maps,player_id,i)==VI_NEVER_SEEN))
      {
        AllocatedMarkMap[i]=true;
      }
      else
      {
        AllocatedMarkMap[i]=false;
      }
    }

    ai_ns::pathfind_ns::FLOOD_MASK AllocatedFloodMask=(int*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(int));
*/
    COORDS sh;
    sh.x=stEntity->getPosX();
    sh.y=stEntity->getPosY();
    PACKET_FLOODFILL_REQUEST pfr;
    pfr.unit_id=UNIT_ID_ON_HEXID(SIP->map,hexid);
    pfr.start_hex=sh;
    pfr.mark_map=this->PrivAllocatedMarkMap;
    pfr.flood_mask=this->PrivAllocatedFloodMask;
    pfr.flooding_transparency=ai_ns::pathfind_ns::PFT_IgnoreAllUnits;
    KSendGlobalMessage(MSG_FLOODFILL_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pfr);
//    KMemFree(AllocatedMarkMap);
    
    bool badp=false;
    int bp;
    while (!badp)
    {
        bp=-1;
        int i;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 967 strategygraph");
        for(i=0;(i<(SIP->map->width()*SIP->map->height()));i++)
        {
          if ((SIP->map->insideBorders(i)) && (!((this->PrivAllocatedFloodMask[i]==FLOOD_MASK_VALUE_CANT_SEE) || (this->PrivAllocatedFloodMask[i]==FLOOD_MASK_VALUE_NOT_ACCESSIBLE))))
          {
            if (bp<0)
            {
              bp=i;
            }
            else
            {
              if (this->PrivAllocatedFloodMask[i]<this->PrivAllocatedFloodMask[bp]) bp=i;
            }
          }
        }
        if (bp==-1) return (-1);

        PACKET_PATHFIND_REQUEST pathfr;
        pathfr.unit_id=UNIT_ID_ON_HEXID(SIP->map,hexid);
        COORDS sh,th;
        sh.x=hexid%SIP->map->width();
        sh.y=hexid/SIP->map->width();
        th.x=bp%SIP->map->width();
        th.y=bp/SIP->map->width();
        pathfr.from=sh;
        pathfr.to=th;
        pathfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
        pathfr.points_of_movement=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF getBestStaticDefensePlaceForUnitOnHexID NOW START 1012");
        TPATH* dispPath=(TPATH*) KSendGlobalMessage(MSG_PATHFIND_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pathfr);
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF getBestStaticDefensePlaceForUnitOnHexID NOW END 1012");
        if (dispPath)
        {
          badp=true;
          delete dispPath;
        }
        else
        {
          this->PrivAllocatedFloodMask[bp]=FLOOD_MASK_VALUE_NOT_ACCESSIBLE;
        }
    }
//    KMemFree(AllocatedFloodMask);
    return bp;
  }
  else
  if (dynamic_cast<CCity*>(stEntity))
  {
    CCity* cp=dynamic_cast<CCity*>(stEntity);
    bool fdpf=false;
    int chi=0;
    while ((!fdpf) && (chi<cp->getCitySize()))
    {
      if (!IS_UNIT_ON_HEXID(SIP->map,cp->position[chi]))
      {
        PACKET_PATHFIND_REQUEST pathfr;
        pathfr.unit_id=UNIT_ID_ON_HEXID(SIP->map,hexid);
        COORDS sh,th;
        sh.x=hexid%SIP->map->width();
        sh.y=hexid/SIP->map->width();
        th.x=(cp->position[chi])%(SIP->map->width());
        th.y=(cp->position[chi])/(SIP->map->width());
        pathfr.from=sh;
        pathfr.to=th;
        pathfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
        pathfr.points_of_movement=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF getBestStaticDefensePlaceForUnitOnHexID NOW START 1049");
        TPATH* dispPath=(TPATH*) KSendGlobalMessage(MSG_PATHFIND_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pathfr);
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF getBestStaticDefensePlaceForUnitOnHexID NOW END 1049");
        if (dispPath)
        {
          fdpf=true;
          delete dispPath;
        }
      }
      chi++;
    }
    if (chi<cp->getCitySize())
    {
      return (cp->position[chi-1]);
    }
    else // mesto je zcela obsazene nebo nedostupne, musim hledat pozice venku
    {
/*
      ai_ns::pathfind_ns::PF_MARKMAP AllocatedMarkMap=(bool*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(bool));
      GLOBALLOGID(PRIORITY_AI_ALLOC, "AllocatedMarkMap ln 1031 strategygraph");
      int i;
  GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 1048 strategygraph");
      for(i=0;(i<(SIP->map->width()*SIP->map->height()));i++)
      {
        if ((SIP->map->insideBorders(i)) && (VISIBILITY_FOR_PLAYER_ON_HEXID(SIP->visibility_maps,player_id,i)==VI_NEVER_SEEN))
        {
          AllocatedMarkMap[i]=true;
        }
        else
        {
          AllocatedMarkMap[i]=false;
        }
      }
      ai_ns::pathfind_ns::FLOOD_MASK AllocatedFloodMask=(int*) KMemAlloc((SIP->map->width()*SIP->map->height())*sizeof(int));
*/
      COORDS sh;
      sh.x=((cp->position)[0])%SIP->map->width();
      sh.y=((cp->position)[0])/SIP->map->width();
      PACKET_FLOODFILL_REQUEST pfr;
      pfr.unit_id=UNIT_ID_ON_HEXID(SIP->map,hexid);
      pfr.start_hex=sh;
      pfr.mark_map=this->PrivAllocatedMarkMap;
      pfr.flood_mask=this->PrivAllocatedFloodMask;
      pfr.flooding_transparency=ai_ns::pathfind_ns::PFT_IgnoreAllUnits;
      KSendGlobalMessage(MSG_FLOODFILL_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pfr);
//      KMemFree(AllocatedMarkMap);
    
      bool badp=false;
      int bp;
      while (!badp)
      {
          bp=-1;
          int i;
  GLOBALLOGID(PRIORITY_AI_ALLOC, "for ln 1080 strategygraph");
          for(i=0;(i<(SIP->map->width()*SIP->map->height()));i++)
          {
            if ((SIP->map->insideBorders(i)) && (!((this->PrivAllocatedFloodMask[i]==FLOOD_MASK_VALUE_CANT_SEE) || (this->PrivAllocatedFloodMask[i]==FLOOD_MASK_VALUE_NOT_ACCESSIBLE))))
            {
              if (bp<0)
              {
                bp=i;
              }
              else
              {
                if (this->PrivAllocatedFloodMask[i]<this->PrivAllocatedFloodMask[bp]) bp=i;
              }
            }
          }
          if (bp==-1) return (-1);

          PACKET_PATHFIND_REQUEST pathfr;
          pathfr.unit_id=UNIT_ID_ON_HEXID(SIP->map,hexid);
          COORDS sh,th;
          sh.x=hexid%SIP->map->width();
          sh.y=hexid/SIP->map->width();
          th.x=bp%SIP->map->width();
          th.y=bp/SIP->map->width();
          pathfr.from=sh;
          pathfr.to=th;
          pathfr.pathfind_transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
          pathfr.points_of_movement=UNIT_ON_HEX(SIP->map,SIP->living_units,sh.x,sh.y).points_of_movement;
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF getBestStaticDefensePlaceForUnitOnHexID NOW START 1129");
          TPATH* dispPath=(TPATH*) KSendGlobalMessage(MSG_PATHFIND_REQUEST,MOD_STRATEGY,MOD_PATHFIND,&pathfr);
        GLOBALLOGID(PRIORITY_AI_ALLOC, "PF getBestStaticDefensePlaceForUnitOnHexID NOW END 1129");
          if (dispPath)
          {
            badp=true;
            delete dispPath;
          }
          else
          {
            this->PrivAllocatedFloodMask[bp]=FLOOD_MASK_VALUE_NOT_ACCESSIBLE;
          }
      }
//      KMemFree(AllocatedFloodMask);
      return bp;
    }
  }
  else
  {
    return (-1);
  }
}

int CStrGraph::countWholePower()
{
  int rv=0;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CUnit*>(*vIt))
      {
        rv+=(dynamic_cast<CUnit*>(*vIt))->getOverallPower();
      }
    }
  }
  return rv;
}

int CStrGraph::countWholeWealthPrice()
{
  int rv=0;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CStaticEntity*>(*vIt))
      {
        rv+=(dynamic_cast<CStaticEntity*>(*vIt))->getPrice();
      }
    }
  }
  return rv;
}

void CStrGraph::computeRatios()
{
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CStaticEntity*>(*vIt))
      {
        (dynamic_cast<CStaticEntity*>(*vIt))->setPriceRatio((((double) ((dynamic_cast<CStaticEntity*>(*vIt))->getPrice()))/PRICE_RATIO_REDUCE_FACTOR)/(this->getWholeWealthPrice()));
      }
      if (dynamic_cast<CUnit*>(*vIt))
      {
        (dynamic_cast<CUnit*>(*vIt))->setPowerRatio(((double) ((dynamic_cast<CUnit*>(*vIt))->getOverallPower()))/(this->getWholePower()));
      }
    }
  }
}

int CStrGraph::countMyCities()
{
  int rv=0;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CCity*>(*vIt))
      {
        rv++;
      }
    }
  }
  return rv;
}

int CStrGraph::countMyCitiesPayment()
{
  int rv=0;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CCity*>(*vIt))
      {
        rv+=(dynamic_cast<CCity*>(*vIt))->getCitySize()*TOWN_INCOME;
      }
    }
  }
  return rv;
}

int CStrGraph::countMyBuildingsByType(int bType)
{
  int rv=0;
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CBuilding*>(*vIt))
      {
        if ((dynamic_cast<CBuilding*>(*vIt))->getBuildingType()==bType) rv++;
      }
    }
  }
  return rv;
}

void CStrGraph::fillThreats()
{
  int tcount;
  for (tcount=0;tcount<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcount++) threats[tcount].clear();
  std::EDGE_CONTAINER<CStrEdge*>::iterator edgeIt;
  for (edgeIt=edges.begin();edgeIt!=edges.end();edgeIt++)
  {
    CStrVertex* v_from=getVertexPointer((*edgeIt)->vertex_from);
    CStrVertex* v_to=getVertexPointer((*edgeIt)->vertex_to);
    if (dynamic_cast<CDynamicEntity*>(v_from))
    {
      if ((v_from->getDipOwnership()!=My) && (v_from->getDipOwnership()!=Ally) && (v_to->getDipOwnership()==My))
      {
        if (dynamic_cast<CStaticEntity*>(v_to)) // tedy cizi nespojenecka jednotka ohrozuje mou statickou entitu
        {
          if (dynamic_cast<CBuilding*>(v_to)) // utok na mou budovu
          {
            TThreat thr;
            thr.attacker_vertex_id=v_from->getID();
            thr.defended_entity_vertex_id=v_to->getID();
            thr.defended_entity_price=(dynamic_cast<CBuilding*>(v_to))->getPrice();
            thr.edge_id=(*edgeIt)->getID();
            thr.threat_disponibility=(*edgeIt)->getTimeDisponibility();
            if (thr.threat_disponibility>0)
            {
              thr.threat_weight=(dynamic_cast<CUnit*>(v_from))->getAttackPower()/thr.threat_disponibility;
            }
            else
            {
              thr.threat_weight=(dynamic_cast<CUnit*>(v_from))->getAttackPower();
            }
            thr.attacker_range=(dynamic_cast<CUnit*>(v_from))->getFireRange();
            if ((thr.threat_disponibility>=0) && (thr.threat_disponibility<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
              threats[thr.threat_disponibility].push_back(thr);
          }
          else
          if (dynamic_cast<CCity*>(v_to)) // utok na me mesto
          {
            TThreat thr;
            thr.attacker_vertex_id=v_from->getID();
            thr.defended_entity_vertex_id=v_to->getID();
            thr.defended_entity_price=(dynamic_cast<CCity*>(v_to))->getPrice();
            thr.edge_id=(*edgeIt)->getID();
            thr.threat_disponibility=(*edgeIt)->getTimeDisponibility();
            if (thr.threat_disponibility>0)
            {
              thr.threat_weight=(dynamic_cast<CUnit*>(v_from))->getAttackPower()/thr.threat_disponibility;
            }
            else
            {
              thr.threat_weight=(dynamic_cast<CUnit*>(v_from))->getAttackPower();
            }
            thr.attacker_range=(dynamic_cast<CUnit*>(v_from))->getFireRange();
            if ((thr.threat_disponibility>=0) && (thr.threat_disponibility<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
              threats[thr.threat_disponibility].push_back(thr);
          }
        }
      }
    }    
  }
  for (tcount=0;tcount<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcount++) threats[tcount].sort(); 
}

void CStrGraph::fillNeedsAndSources()
{
  needs.clear();
  sources.clear();

  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CStaticEntity*>(*vIt))
      {
        needs.push_back(dynamic_cast<CStaticEntity*>(*vIt));
      }
      else
      if (dynamic_cast<CUnit*>(*vIt))
      {
        sources.push_back(dynamic_cast<CUnit*>(*vIt));
      }
    }
  }
  needs.sort();
}

void CStrGraph::performDefensive(int threat_disponibility,int iteration_no,CStaticEntity* & current_need,std::THREAT_CONTAINER<TThreat>::iterator & current_threat_iterator,CPlan* given_plan)
{  
  if (current_threat_iterator->threat_weight<=0) return; // nulovymi threaty se nema cenu zabyvat
  
  std::SOURCES_CONTAINER<CUnit*>::iterator sIt;
  
  // vytvorim si seznam moznych obrancu
  std::SOURCES_CONTAINER<CUnit*> possible_defenders;
  possible_defenders.clear();
  for (sIt=sources.begin();sIt!=sources.end();sIt++)
  {
    if ((*sIt)->DefenceDesire==NoDefenceDesire)
    {
      int ed=(findEdge((*sIt)->getID(),current_threat_iterator->defended_entity_vertex_id))->getTimeDisponibility();
      if ((ed>=0) && (ed<=threat_disponibility))
      {
        possible_defenders.push_back(*sIt);
      }
    }
  }
  
  // vytvorim si seznam moznych protiutocniku
  std::SOURCES_CONTAINER<CUnit*> possible_direct_attackers;
  possible_direct_attackers.clear();
  for (sIt=sources.begin();sIt!=sources.end();sIt++)
  {
    if ((*sIt)->DefenceDesire==NoDefenceDesire)
    {
      int ed=(findEdge((*sIt)->getID(),current_threat_iterator->attacker_vertex_id))->getTimeDisponibility();
      int ed2=(findEdge((*sIt)->getID(),current_threat_iterator->defended_entity_vertex_id))->getTimeDisponibility();
      if (((ed>=0) && (ed<=threat_disponibility)) && ((ed2>=0) && (ed2<=ed)))
      {
        possible_direct_attackers.push_back(*sIt);
      }
    }
  }


  if (!iteration_no) // prvni pruchod iterace
  {
    if (!threat_disponibility) // threat_disponibility==0
    {
      if (current_threat_iterator->attacker_range==1) // utocnik bojuje nablizko
      {
        double count_ratio=0.0;
        sIt=possible_defenders.begin();
        while ((sIt!=possible_defenders.end()) && (count_ratio<current_need->getPriceRatio()) && (current_threat_iterator->threat_weight>0))
        {
          if ((*sIt)->DefenceDesire==NoDefenceDesire)
          {
            count_ratio+=(*sIt)->getPowerRatio();
            int fdp=current_need->getFreeDefendingPlaces();
            if (fdp>0)
            {
              current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
              current_need->setFreeDefendingPlaces(fdp-1);
              current_need->setGuardedIndicator(true);
              (*sIt)->DefenceDesire=DefendInside;

              CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              tc.x=(*sIt)->getPosX();
              tc.y=(*sIt)->getPosY();
              dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
              dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

            }
            else
            {
              current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
              current_need->setGuardedIndicator(true);
              (*sIt)->DefenceDesire=DefendOutside;

              CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              tc.x=(*sIt)->getPosX();
              tc.y=(*sIt)->getPosY();
              dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
              dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

            }
          }
          sIt++;
        }
        if (current_threat_iterator->threat_weight<0)
        {
          int threat_modulo=(-1)*(current_threat_iterator->threat_weight);
          current_threat_iterator->threat_weight=0;
          std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
          tIt2++;
          int ttd=threat_disponibility;
          while ((threat_modulo>0) && (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
          {
            if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
            while ((tIt2!=threats[ttd].end()) && (threat_modulo>0))
            {
              if (tIt2->defended_entity_vertex_id==current_need->getID())
              {
                if (threat_modulo>tIt2->threat_weight)
                {
                  threat_modulo-=tIt2->threat_weight;
                  tIt2->threat_weight=0;
                }
                else
                {
                  tIt2->threat_weight-=threat_modulo;
                  threat_modulo=0;
                }
              }
              tIt2++;
            }
            ttd++;
          }
        }
      }
      else // utocnik bojuje na dalku
      {      
        if (current_need->getGuardedIndicator()) // need je jiz branen -> vyrazim na ztec
        {
          sIt=possible_direct_attackers.begin();
          while ((sIt!=possible_direct_attackers.end()) && (current_threat_iterator->threat_weight>0))
          {
            if ((*sIt)->DefenceDesire==NoDefenceDesire)
            {
              current_threat_iterator->threat_weight-=(*sIt)->getAttackPower();
              (*sIt)->DefenceDesire=DefendCharging;

              CUnitPlanAction_Go* dca=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              CStrEdge* tmpstredge=findEdge((*sIt)->getID(),current_threat_iterator->attacker_vertex_id);
              CAttackEdge* tmpedge=dynamic_cast<CAttackEdge*>(tmpstredge);
              tc.x=tmpedge->getActionPointX();
              tc.y=tmpedge->getActionPointY();
              dca->path_target=(tc.y*SIP->map->width())+tc.x;
              dca->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dca,PERFORM_IMMEDIATELY);
              CUnitPlanAction_Attack* dcaa=new CUnitPlanAction_Attack((*sIt)->getWorldID());
              CStrVertex* tmpvert=getVertexPointer(current_threat_iterator->attacker_vertex_id);
              dcaa->attack_target=(tmpvert->getPosY()*SIP->map->width())+tmpvert->getPosX();
              given_plan->addActionToBack(dcaa,PERFORM_IMMEDIATELY);


              // odectu silu utoku od threatu zapricinenych stejnym utocnikem, pro vsechny needy,
              // ktere jsou guarded a kde disponibilita >= disponibilite vybihajiciho obrance k needu
              // tedy u vsech branenych needu, ktere obrance vybehnutim vykryje
              // to jsou ty, ke kterym se dostanu driv nez v utocnik
              std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
              tIt2++;
              int ttd=threat_disponibility;
              while (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant)
              {
                if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
                while (tIt2!=threats[ttd].end())
                {
                  if (tIt2->attacker_vertex_id==current_threat_iterator->attacker_vertex_id) // vyberu pouze threaty od stejneho utocnika
                  {
                    std::NEEDS_CONTAINER<CStaticEntity*>::iterator hlpnIt;
                    for (hlpnIt=needs.begin();hlpnIt!=needs.end();hlpnIt++)
                    {
                      if ((tIt2->defended_entity_vertex_id==(*hlpnIt)->getID()) && ((*hlpnIt)->getGuardedIndicator())) // jedna se o (guarded) need, ke kteremu se threat vztahuje
                      {
                        int ed=(findEdge(tIt2->attacker_vertex_id,(*hlpnIt)->getID()))->getTimeDisponibility();
                        int ed2=(findEdge((*sIt)->getID(),(*hlpnIt)->getID()))->getTimeDisponibility();
                        if ((ed>=0) && (ed2>=0) && (ed2<=ed)) // obrance vykryje utocnika pro dany need - mohu odecist z tohoto threatu
                        {
                          tIt2->threat_weight-=(*sIt)->getAttackPower();
                          if (tIt2->threat_weight<0) tIt2->threat_weight=0;
                        }
                      }
                    }
                  }
                  tIt2++;
                }
                ttd++;
              }
            }
            sIt++;
          }
        }
        else // need jeste neni branen -> obsadim ho
        {
          double count_ratio=0.0;
          sIt=possible_defenders.begin();
          while ((sIt!=possible_defenders.end()) && (count_ratio<current_need->getPriceRatio()) && (current_threat_iterator->threat_weight>0))
          {
            if ((*sIt)->DefenceDesire==NoDefenceDesire)
            {
              count_ratio+=(*sIt)->getPowerRatio();
              current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
              current_need->setFreeDefendingPlaces(current_need->getFreeDefendingPlaces()-1);
              current_need->setGuardedIndicator(true);
              (*sIt)->DefenceDesire=DefendInside;

              CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              tc.x=(*sIt)->getPosX();
              tc.y=(*sIt)->getPosY();
              dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
              dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

              if (current_threat_iterator->threat_weight<0)
              {
                int threat_modulo=(-1)*(current_threat_iterator->threat_weight);
                current_threat_iterator->threat_weight=0;
                std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
                tIt2++;
                int ttd=threat_disponibility;
                while ((threat_modulo>0) && (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
                {
                  if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
                  while ((tIt2!=threats[ttd].end()) && (threat_modulo>0))
                  {
                    if (tIt2->defended_entity_vertex_id==current_need->getID())
                    {
                      if (threat_modulo>tIt2->threat_weight)
                      {
                        threat_modulo-=tIt2->threat_weight;
                        tIt2->threat_weight=0;
                      }
                      else
                      {
                        tIt2->threat_weight-=threat_modulo;
                        threat_modulo=0;
                      }
                    }
                    tIt2++;
                  }
                  ttd++;
                }
              }

            }
            sIt++;
          }

        }
      }
    }
    else // threat_disponibility>0 => pokud neni guarded, vysilam na ztec
    {
      if (current_need->getGuardedIndicator()) // need je jiz branen -> vyrazim na ztec
      {
        sIt=possible_direct_attackers.begin();
        while ((sIt!=possible_direct_attackers.end()) && (current_threat_iterator->threat_weight>0))
        {
          if ((*sIt)->DefenceDesire==NoDefenceDesire)
          {
            current_threat_iterator->threat_weight-=(*sIt)->getAttackPower();
            (*sIt)->DefenceDesire=DefendCharging;

            CUnitPlanAction_Go* dca=new CUnitPlanAction_Go((*sIt)->getWorldID());
            COORDS tc;
            CStrEdge* tmpstredge=findEdge((*sIt)->getID(),current_threat_iterator->attacker_vertex_id);
            CAttackEdge* tmpedge=dynamic_cast<CAttackEdge*>(tmpstredge);
            tc.x=tmpedge->getActionPointX();
            tc.y=tmpedge->getActionPointY();
            dca->path_target=(tc.y*SIP->map->width())+tc.x;
            dca->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
            given_plan->addActionToBack(dca,PERFORM_IMMEDIATELY);
            CUnitPlanAction_Attack* dcaa=new CUnitPlanAction_Attack((*sIt)->getWorldID());
            CStrVertex* tmpvert=getVertexPointer(current_threat_iterator->attacker_vertex_id);
            dcaa->attack_target=(tmpvert->getPosY()*SIP->map->width())+tmpvert->getPosX();
            given_plan->addActionToBack(dcaa,PERFORM_IMMEDIATELY);

            // odectu silu utoku od threatu zapricinenych stejnym utocnikem, pro vsechny needy,
            // ktere jsou guarded a kde disponibilita >= disponibilite vybihajiciho obrance k needu
            // tedy u vsech branenych needu, ktere obrance vybehnutim vykryje
            // to jsou ty, ke kterym se dostanu driv nez v utocnik
            std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
            tIt2++;
            int ttd=threat_disponibility;
            while (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant)
            {
              if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
              while (tIt2!=threats[ttd].end())
              {
                if (tIt2->attacker_vertex_id==current_threat_iterator->attacker_vertex_id) // vyberu pouze threaty od stejneho utocnika
                {
                  std::NEEDS_CONTAINER<CStaticEntity*>::iterator hlpnIt;
                  for (hlpnIt=needs.begin();hlpnIt!=needs.end();hlpnIt++)
                  {
                    if ((tIt2->defended_entity_vertex_id==(*hlpnIt)->getID()) && ((*hlpnIt)->getGuardedIndicator())) // jedna se o (guarded) need, ke kteremu se threat vztahuje
                    {
                      int ed=(findEdge(tIt2->attacker_vertex_id,(*hlpnIt)->getID()))->getTimeDisponibility();
                      int ed2=(findEdge((*sIt)->getID(),(*hlpnIt)->getID()))->getTimeDisponibility();
                      if ((ed>=0) && (ed2>=0) && (ed2<=ed)) // obrance vykryje utocnika pro dany need - mohu odecist z tohoto threatu
                      {
                        tIt2->threat_weight-=(*sIt)->getAttackPower();
                        if (tIt2->threat_weight<0) tIt2->threat_weight=0;
                      }
                    }
                  }
                }
                tIt2++;
              }
              ttd++;
            }
          }
          sIt++;
        }
      }
      else // need jeste neni branen -> obsadim ho
      {
        double count_ratio=0.0;
        sIt=possible_defenders.begin();
        while ((sIt!=possible_defenders.end()) && (count_ratio<current_need->getPriceRatio()) && (current_threat_iterator->threat_weight>0))
        {
          if ((*sIt)->DefenceDesire==NoDefenceDesire)
          {
            count_ratio+=(*sIt)->getPowerRatio();
            current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
            current_need->setFreeDefendingPlaces(current_need->getFreeDefendingPlaces()-1);
            current_need->setGuardedIndicator(true);
            (*sIt)->DefenceDesire=DefendInside;

            CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
            COORDS tc;
            tc.x=(*sIt)->getPosX();
            tc.y=(*sIt)->getPosY();
            dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
            dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
            given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

            if (current_threat_iterator->threat_weight<0)
            {
              int threat_modulo=(-1)*(current_threat_iterator->threat_weight);
              current_threat_iterator->threat_weight=0;
              std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
              tIt2++;
              int ttd=threat_disponibility;
              while ((threat_modulo>0) && (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
              {
                if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
                while ((tIt2!=threats[ttd].end()) && (threat_modulo>0))
                {
                  if (tIt2->defended_entity_vertex_id==current_need->getID())
                  {
                    if (threat_modulo>tIt2->threat_weight)
                    {
                      threat_modulo-=tIt2->threat_weight;
                      tIt2->threat_weight=0;
                    }
                    else
                    {
                      tIt2->threat_weight-=threat_modulo;
                      threat_modulo=0;
                    }
                  }
                  tIt2++;
                }
                ttd++;
              }
            }
          }
          sIt++;
        }
      }
    }
  }
  else  // druhy pruchod iterace
  {
    if (!threat_disponibility) // threat_disponibility==0
    {
      if (current_threat_iterator->attacker_range==1) // utocnik bojuje nablizko
      {
        sIt=possible_defenders.begin();
        while ((sIt!=possible_defenders.end()) && (current_threat_iterator->threat_weight>0))
        {
          if ((*sIt)->DefenceDesire==NoDefenceDesire)
          {
            int fdp=current_need->getFreeDefendingPlaces();
            if (fdp>0)
            {
              current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
              current_need->setFreeDefendingPlaces(fdp-1);
              current_need->setGuardedIndicator(true);
              (*sIt)->DefenceDesire=DefendInside;

              CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              tc.x=(*sIt)->getPosX();
              tc.y=(*sIt)->getPosY();
              dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
              dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

            }
            else
            {
              current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
              current_need->setGuardedIndicator(true);
              (*sIt)->DefenceDesire=DefendOutside;

              CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              tc.x=(*sIt)->getPosX();
              tc.y=(*sIt)->getPosY();
              dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
              dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

            }
          }
          sIt++;
        }
        if (current_threat_iterator->threat_weight<0)
        {
          int threat_modulo=(-1)*(current_threat_iterator->threat_weight);
          current_threat_iterator->threat_weight=0;
          std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
          tIt2++;
          int ttd=threat_disponibility;
          while ((threat_modulo>0) && (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
          {
            if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
            while ((tIt2!=threats[ttd].end()) && (threat_modulo>0))
            {
              if (tIt2->defended_entity_vertex_id==current_need->getID())
              {
                if (threat_modulo>tIt2->threat_weight)
                {
                  threat_modulo-=tIt2->threat_weight;
                  tIt2->threat_weight=0;
                }
                else
                {
                  tIt2->threat_weight-=threat_modulo;
                  threat_modulo=0;
                }
              }
              tIt2++;
            }
            ttd++;
          }
        }
      }
      else // utocnik bojuje na dalku
      {      
        if (current_need->getGuardedIndicator()) // need je jiz branen -> vyrazim na ztec
        {
          sIt=possible_direct_attackers.begin();
          while ((sIt!=possible_direct_attackers.end()) && (current_threat_iterator->threat_weight>0))
          {
            if ((*sIt)->DefenceDesire==NoDefenceDesire)
            {
              current_threat_iterator->threat_weight-=(*sIt)->getAttackPower();
              (*sIt)->DefenceDesire=DefendCharging;

              CUnitPlanAction_Go* dca=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              CStrEdge* tmpstredge=findEdge((*sIt)->getID(),current_threat_iterator->attacker_vertex_id);
              CAttackEdge* tmpedge=dynamic_cast<CAttackEdge*>(tmpstredge);
              tc.x=tmpedge->getActionPointX();
              tc.y=tmpedge->getActionPointY();
              dca->path_target=(tc.y*SIP->map->width())+tc.x;
              dca->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dca,PERFORM_IMMEDIATELY);
              CUnitPlanAction_Attack* dcaa=new CUnitPlanAction_Attack((*sIt)->getWorldID());
              CStrVertex* tmpvert=getVertexPointer(current_threat_iterator->attacker_vertex_id);
              dcaa->attack_target=(tmpvert->getPosY()*SIP->map->width())+tmpvert->getPosX();
              given_plan->addActionToBack(dcaa,PERFORM_IMMEDIATELY);


              // odectu silu utoku od threatu zapricinenych stejnym utocnikem, pro vsechny needy,
              // ktere jsou guarded a kde disponibilita >= disponibilite vybihajiciho obrance k needu
              // tedy u vsech branenych needu, ktere obrance vybehnutim vykryje
              // to jsou ty, ke kterym se dostanu driv nez v utocnik
              std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
              tIt2++;
              int ttd=threat_disponibility;
              while (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant)
              {
                if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
                while (tIt2!=threats[ttd].end())
                {
                  if (tIt2->attacker_vertex_id==current_threat_iterator->attacker_vertex_id) // vyberu pouze threaty od stejneho utocnika
                  {
                    std::NEEDS_CONTAINER<CStaticEntity*>::iterator hlpnIt;
                    for (hlpnIt=needs.begin();hlpnIt!=needs.end();hlpnIt++)
                    {
                      if ((tIt2->defended_entity_vertex_id==(*hlpnIt)->getID()) && ((*hlpnIt)->getGuardedIndicator())) // jedna se o (guarded) need, ke kteremu se threat vztahuje
                      {
                        int ed=(findEdge(tIt2->attacker_vertex_id,(*hlpnIt)->getID()))->getTimeDisponibility();
                        int ed2=(findEdge((*sIt)->getID(),(*hlpnIt)->getID()))->getTimeDisponibility();
                        if ((ed>=0) && (ed2>=0) && (ed2<=ed)) // obrance vykryje utocnika pro dany need - mohu odecist z tohoto threatu
                        {
                          tIt2->threat_weight-=(*sIt)->getAttackPower();
                          if (tIt2->threat_weight<0) tIt2->threat_weight=0;
                        }
                      }
                    }
                  }
                  tIt2++;
                }
                ttd++;
              }
            }
            sIt++;
          }
        }
        else // need jeste neni branen -> obsadim ho
        {
          sIt=possible_defenders.begin();
          while ((sIt!=possible_defenders.end()) && (current_threat_iterator->threat_weight>0))
          {
            if ((*sIt)->DefenceDesire==NoDefenceDesire)
            {
              current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
              current_need->setFreeDefendingPlaces(current_need->getFreeDefendingPlaces()-1);
              current_need->setGuardedIndicator(true);
              (*sIt)->DefenceDesire=DefendInside;

              CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
              COORDS tc;
              tc.x=(*sIt)->getPosX();
              tc.y=(*sIt)->getPosY();
              dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
              dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
              given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

              if (current_threat_iterator->threat_weight<0)
              {
                int threat_modulo=(-1)*(current_threat_iterator->threat_weight);
                current_threat_iterator->threat_weight=0;
                std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
                tIt2++;
                int ttd=threat_disponibility;
                while ((threat_modulo>0) && (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
                {
                  if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
                  while ((tIt2!=threats[ttd].end()) && (threat_modulo>0))
                  {
                    if (tIt2->defended_entity_vertex_id==current_need->getID())
                    {
                      if (threat_modulo>tIt2->threat_weight)
                      {
                        threat_modulo-=tIt2->threat_weight;
                        tIt2->threat_weight=0;
                      }
                      else
                      {
                        tIt2->threat_weight-=threat_modulo;
                        threat_modulo=0;
                      }
                    }
                    tIt2++;
                  }
                  ttd++;
                }
              }

            }
            sIt++;
          }

        }
      }
    }
    else // threat_disponibility>0 => pokud neni guarded, vysilam na ztec
    {
      if (current_need->getGuardedIndicator()) // need je jiz branen -> vyrazim na ztec
      {
        sIt=possible_direct_attackers.begin();
        while ((sIt!=possible_direct_attackers.end()) && (current_threat_iterator->threat_weight>0))
        {
          if ((*sIt)->DefenceDesire==NoDefenceDesire)
          {
            current_threat_iterator->threat_weight-=(*sIt)->getAttackPower();
            (*sIt)->DefenceDesire=DefendCharging;

            CUnitPlanAction_Go* dca=new CUnitPlanAction_Go((*sIt)->getWorldID());
            COORDS tc;
            CStrEdge* tmpstredge=findEdge((*sIt)->getID(),current_threat_iterator->attacker_vertex_id);
            CAttackEdge* tmpedge=dynamic_cast<CAttackEdge*>(tmpstredge);
            tc.x=tmpedge->getActionPointX();
            tc.y=tmpedge->getActionPointY();
            dca->path_target=(tc.y*SIP->map->width())+tc.x;
            dca->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
            given_plan->addActionToBack(dca,PERFORM_IMMEDIATELY);
            CUnitPlanAction_Attack* dcaa=new CUnitPlanAction_Attack((*sIt)->getWorldID());
            CStrVertex* tmpvert=getVertexPointer(current_threat_iterator->attacker_vertex_id);
            dcaa->attack_target=(tmpvert->getPosY()*SIP->map->width())+tmpvert->getPosX();
            given_plan->addActionToBack(dcaa,PERFORM_IMMEDIATELY);

            // odectu silu utoku od threatu zapricinenych stejnym utocnikem, pro vsechny needy,
            // ktere jsou guarded a kde disponibilita >= disponibilite vybihajiciho obrance k needu
            // tedy u vsech branenych needu, ktere obrance vybehnutim vykryje
            // to jsou ty, ke kterym se dostanu driv nez v utocnik
            std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
            tIt2++;
            int ttd=threat_disponibility;
            while (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant)
            {
              if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
              while (tIt2!=threats[ttd].end())
              {
                if (tIt2->attacker_vertex_id==current_threat_iterator->attacker_vertex_id) // vyberu pouze threaty od stejneho utocnika
                {
                  std::NEEDS_CONTAINER<CStaticEntity*>::iterator hlpnIt;
                  for (hlpnIt=needs.begin();hlpnIt!=needs.end();hlpnIt++)
                  {
                    if ((tIt2->defended_entity_vertex_id==(*hlpnIt)->getID()) && ((*hlpnIt)->getGuardedIndicator())) // jedna se o (guarded) need, ke kteremu se threat vztahuje
                    {
                      int ed=(findEdge(tIt2->attacker_vertex_id,(*hlpnIt)->getID()))->getTimeDisponibility();
                      int ed2=(findEdge((*sIt)->getID(),(*hlpnIt)->getID()))->getTimeDisponibility();
                      if ((ed>=0) && (ed2>=0) && (ed2<=ed)) // obrance vykryje utocnika pro dany need - mohu odecist z tohoto threatu
                      {
                        tIt2->threat_weight-=(*sIt)->getAttackPower();
                        if (tIt2->threat_weight<0) tIt2->threat_weight=0;
                      }
                    }
                  }
                }
                tIt2++;
              }
              ttd++;
            }
          }
          sIt++;
        }
      }
      else // need jeste neni branen -> obsadim ho
      {
        sIt=possible_defenders.begin();
        while ((sIt!=possible_defenders.end()) && (current_threat_iterator->threat_weight>0))
        {
          if ((*sIt)->DefenceDesire==NoDefenceDesire)
          {
            current_threat_iterator->threat_weight-=(*sIt)->getDefendPower();
            current_need->setFreeDefendingPlaces(current_need->getFreeDefendingPlaces()-1);
            current_need->setGuardedIndicator(true);
            (*sIt)->DefenceDesire=DefendInside;

            CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*sIt)->getWorldID());
            COORDS tc;
            tc.x=(*sIt)->getPosX();
            tc.y=(*sIt)->getPosY();
            dia->path_target=getBestStaticDefensePlaceForUnitOnHexID((tc.y*SIP->map->width())+tc.x,current_need);
            dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
            given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);

            if (current_threat_iterator->threat_weight<0)
            {
              int threat_modulo=(-1)*(current_threat_iterator->threat_weight);
              current_threat_iterator->threat_weight=0;
              std::THREAT_CONTAINER<TThreat>::iterator tIt2=current_threat_iterator;
              tIt2++;
              int ttd=threat_disponibility;
              while ((threat_modulo>0) && (ttd<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant))
              {
                if (ttd>threat_disponibility) tIt2=threats[ttd].begin();
                while ((tIt2!=threats[ttd].end()) && (threat_modulo>0))
                {
                  if (tIt2->defended_entity_vertex_id==current_need->getID())
                  {
                    if (threat_modulo>tIt2->threat_weight)
                    {
                      threat_modulo-=tIt2->threat_weight;
                      tIt2->threat_weight=0;
                    }
                    else
                    {
                      tIt2->threat_weight-=threat_modulo;
                      threat_modulo=0;
                    }
                  }
                  tIt2++;
                }
                ttd++;
              }
            }
          }
          sIt++;
        }
      }
    }
  }

  possible_defenders.clear();
  possible_direct_attackers.clear();
}



void CStrGraph::performRestDefensive(CPlan* given_plan)
{
  // TODO:
  // obsazeni uplne nebranenych needu ???

  // obsazovani needed helps
  std::HELPS_CONTAINER<THelpNeeded>::iterator nhIt;
  for(nhIt=needed_helps.begin();((nhIt!=needed_helps.end()) && (!(not_used_sources.empty())));nhIt++)
  {
    int best_td=(findEdge((*(not_used_sources.begin()))->getID(),nhIt->defended_entity_id))->getTimeDisponibility();
    std::SOURCES_CONTAINER<CUnit*>::iterator best_nusIt=not_used_sources.begin();
    std::SOURCES_CONTAINER<CUnit*>::iterator nusIt;
    for(nusIt=not_used_sources.begin();nusIt!=not_used_sources.end();nusIt++)
    {
      CStrEdge* fe=findEdge((*nusIt)->getID(),nhIt->defended_entity_id);
      if (fe->getTimeDisponibility()<best_td)
      {
        best_td=fe->getTimeDisponibility();
        best_nusIt=nusIt;
      }
    }
    CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*best_nusIt)->getWorldID());
    dia->path_target=getBestStaticDefensePlaceForUnitOnHexID(((*best_nusIt)->getPosY()*SIP->map->width())+(*best_nusIt)->getPosX(),dynamic_cast<CStaticEntity*>(getVertexPointer(nhIt->defended_entity_id)));
    dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
    given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);
    not_used_sources.erase(best_nusIt);
  }
  
  // utoky na non defending
  std::NON_DEFENDING_TARGETS_CONTAINER<CUnit*>::iterator ndIt;
  for (ndIt=non_defending_targets.begin();((ndIt!=non_defending_targets.end()) && (!(not_used_sources.empty())));ndIt++)
  {
    int best_td=(findEdge((*(non_defending_targets.begin()))->getID(),(*ndIt)->getID()))->getTimeDisponibility();
    std::SOURCES_CONTAINER<CUnit*>::iterator best_nusIt=not_used_sources.begin();
    std::SOURCES_CONTAINER<CUnit*>::iterator nusIt;
    CAttackEdge* be=0;
    for(nusIt=not_used_sources.begin();nusIt!=not_used_sources.end();nusIt++)
    {
      CStrEdge* fe=findEdge((*nusIt)->getID(),(*ndIt)->getID());
      if (fe->getTimeDisponibility()<best_td)
      {
        be=dynamic_cast<CAttackEdge*>(fe);
        best_td=fe->getTimeDisponibility();
        best_nusIt=nusIt;
      }
    }
    CUnitPlanAction_Go* dia=new CUnitPlanAction_Go((*best_nusIt)->getWorldID());
    dia->path_target=(be->getActionPointY()*SIP->map->width())+be->getActionPointX();
    dia->transparency=ai_ns::pathfind_ns::PFT_UnitsNotTransparent;
    given_plan->addActionToBack(dia,PERFORM_IMMEDIATELY);
    CUnitPlanAction_Attack* diaa=new CUnitPlanAction_Attack((*best_nusIt)->getWorldID());
    diaa->attack_target=((*ndIt)->getPosY()*SIP->map->width())+(*ndIt)->getPosX();
    given_plan->addActionToBack(diaa,PERFORM_IMMEDIATELY);
    not_used_sources.erase(best_nusIt);
  }

}

CPlan* CStrGraph::generateDefencePlan(int player_ID)
{
  CPlan* given_plan=new CPlan(player_ID);

  fillThreats();
  fillNeedsAndSources();

  int tcount;
  for (tcount=0;tcount<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcount++)
  {
    int prno;
    for (prno=0;prno<2;prno++)
    {
      std::NEEDS_CONTAINER<CStaticEntity*>::iterator nIt;
      for (nIt=needs.begin();nIt!=needs.end();nIt++)
      {
        std::THREAT_CONTAINER<TThreat>::iterator tIt;
        for (tIt=threats[tcount].begin();tIt!=threats[tcount].end();tIt++)
        {
          if (tIt->defended_entity_vertex_id==(*nIt)->getID()) // nasel jsem ohrozeni dane disponibility pro danou potrebu
          {
            performDefensive(tcount,prno,(*nIt),tIt,given_plan);
          }
        }
      }
    }
  }

  // vygeneruju nepokryte potreby braneni
  needed_helps.clear();
  for (tcount=0;tcount<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcount++)
  {
    std::THREAT_CONTAINER<TThreat>::iterator tIt;
    for (tIt=threats[tcount].begin();tIt!=threats[tcount].end();tIt++)
    {
      if (tIt->threat_weight>0)
      {
        THelpNeeded hn;
        hn.time=tIt->threat_disponibility;
        hn.help_power=tIt->threat_weight;
        hn.importance=tIt->defended_entity_price;
        hn.defended_entity_id=tIt->defended_entity_vertex_id;
        needed_helps.push_back(hn);
      }
    }
  }
  needed_helps.sort();

  // vygeneruju cizi nespojenecke cile, ktere neutoci
  non_defending_targets.clear();
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vertIt;
  for (vertIt=vertices.begin();vertIt!=vertices.end();vertIt++)
  {
    if (dynamic_cast<CUnit*>(*vertIt))
    {
      CUnit* unit=dynamic_cast<CUnit*>(*vertIt);
      if ((unit->getFireRange()==0) && ((unit->getDipOwnership()!=My) && (unit->getDipOwnership()!=Ally)))
      {
        non_defending_targets.push_back(unit);
      }
    }
  }

  // vygeneruju nevyuzite sources
  not_used_sources.clear();
  std::VERTEX_CONTAINER<CStrVertex*>::iterator vIt;
  for (vIt=vertices.begin();vIt!=vertices.end();vIt++)
  {
    if ((*vIt)->getDipOwnership()==My)
    {
      if (dynamic_cast<CUnit*>(*vIt))
      {
        CUnit* dcu=dynamic_cast<CUnit*>(*vIt);
        if ((dcu->DefenceDesire=NoDefenceDesire) && (dcu->getAttackPower()>0))
        {
          not_used_sources.push_back(dcu);
        }
      }
    }
  }


  performRestDefensive(given_plan);
  needed_helps.clear();
  non_defending_targets.clear();
  not_used_sources.clear(); // nemelo by byt potreba

  for (tcount=0;tcount<MAX_THREAT_DISPONIBILITY-ai_level_difficulty_constant;tcount++) threats[tcount].clear();
  needs.clear();
  sources.clear();
  return given_plan;
}

}
}