/*

    ~//#  La fabuleuse aventure de \o/ #\\~
    
    \o/ était un jeune et audacieux programmeur,
    dont le Fabuleux Destin (d'Améile Poulain) le mena à diriger
    des travaux légendaires et mener des combats héroïque.
    
    Son incroyable quête, la plus grande de toutes celles qu'il a pu
    entreprendre, fut d'avoir un impitoyable pouvoir de Sciences &
    Technologies en Mana-gement et Gestion de Magie & Mes Sorciers (M&M'S).
    
    Il établit un plan au départ.
    Après avoir perdu celui-ci, retrouvé, signé, contresigné, reperdu à nouveau,
    déchiqueté par un Pitbull qui errait par ici, avant de finalement finir
    enterré six pieds sous terre ; il décida d'entamer son impitoyable
    quête « au feeling wesh vazy » de par son talent immense et son
    imagination infinie.
    
    
    « Au feeling. »
    Ne cherchez pas plus loin, la plupart de ce code est fait à l'instinct.
    
    J'abhorre les noms de l'API, tandis que je couche avec le Préprocesseur.
    Que dire ? Mélangeons les deux ! La plupart des fonctionnalités de l'API
    sont obfusquées derrière d'insalubres macros.
    
    La partie Construction aura pris le plus de temps, c'est un comble.
    Créer aléatoirement (avec tirage de tourelle à non équiprobabilité,
    pour faire genre) une tourelle, à une position pas trop loin d'un
    coin intéressant ; exemple concret : une fontaine.
    S'il y en a trop, des fois, on en vire une comme ça, pour le plaisir.
    
    La partie Déplacement a le plus grand caractère algorithmique (\u0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF en Unicode)
    En effet, elle contient un incroyable et excitant BFS. Ouais, je sais, c'est la classe.
    On cherche des coins pas trop mal pour chaque groupe de sorcier, et on les déplace
    dans c'te dite direction.
    
    Si on approche de la fin, on focalise tout sur l'artefact et les bases, histoire
    de gruger quelques points supplémentaires.
    
    Les deux dernières parties n'ont aucun intérêt.
    Je vous laisse deviner ce qu'elles sont censées faire chez n'importe qui
    (sauf chez les prêcheurs de PHP peut-être).
    
    
    Et c'est ainsi, que \o/ réussit à vaincre tous ses adversaires,
    avant de se rendre compte qu'il était en train de se mutiler lui-même.
    
    
    \_o< \_o< \_o<  ##   LES COINGS SONT BONS   ##  >o_/ >o_/ >o_/ 
    ... PAN !
    
 */
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include "api.hh"
#include "alea.hh"
#include "misc.hh"

using namespace std;


vector<Position> reperes;

void Debut()
{
    srand(time(0) ^ 0x42);
    
    // Déterminer les repères de la carte
    for (int x = 0; x < TAILLE_TERRAIN; x++)
    {
        for (int y = 0; y < TAILLE_TERRAIN; y++)
        {
            if (Case(x, y) != CASE_SIMPLE)
                reperes.push_back((Position) {x, y});
        }
    }
    sort(reperes.begin(), reperes.end());
}


void Construction()
{
    vector<Tourelle> tourelles = Liste_Tourelles(ID);
    bool adjacent[TAILLE_TERRAIN][TAILLE_TERRAIN] = {false};

    // Déterminer les cases adjacentes à une tourelle
    for (size_t index = 0; index < tourelles.size(); index++)
    {
        vector<Position> voisins = Bloc(tourelles[index].pos);
        
        adjacent[tourelles[index].pos.x][tourelles[index].pos.y] = true;
        for (size_t voisin = 0; voisin < voisins.size(); voisin++)
            adjacent[voisins[voisin].x][voisins[voisin].y] = true;
    }

    if (tourelles.empty())
    {
        vector<Position> alentours = Alentours(Base(ID), PORTEE_CONSTRUCTION);
        vector<Position> eligible;
        
        // Déterminer la liste des cases libres aux alentours de la base
        for (size_t index = 0; index < alentours.size(); index++)
            if (Constructible(alentours[index]))
                eligible.push_back(alentours[index]);
        if (eligible.empty())
            Creer_Sorciers(MAGIE / COUT_SORCIER);
        else
            Creer_Tourelle(eligible[Aleatoire(0, eligible.size() - 1)], PORTEE_TOURELLE);
    }
    else if (tourelles.size() >= TOURELLES_MAX)
    {
        if (Bernouilli(1. / 3, 2. / 3))
            Creer_Sorciers(MAGIE / COUT_SORCIER);
        else
        {
            vector<Evenement> candidats;
            double total = 0;


            // Calculer la probabilité de choisir une tourelle à détruire
            for (size_t index = 0; index < tourelles.size(); index++)
            {
                candidats.push_back(Evenement(index, (double)
                     Distance(tourelles[index].pos, Base(ID))
                     / Distance(tourelles[index].pos,
                       Plus_Proche(reperes, tourelles[index].pos))
                     / (tourelles[index].vie * tourelles[index].vie)
                    // Votre formule de calcul ici
                ));
                total += candidats.back().probabilite;
            }
            for (size_t index = 0; index < tourelles.size(); index++)
                candidats[index].probabilite /= total;
            Detruire_Tourelle(tourelles[Choisir(candidats)].pos);
        }
    }
    else
    {
        if (Bernouilli(3. / 7, 4. / 7))
            Creer_Sorciers(MAGIE / COUT_SORCIER);
        else
        {
            vector<Evenement> candidats;
            double total = 0;


            // Calculer la probabilité de choisir une tourelle
            for (size_t index = 0; index < tourelles.size(); index++)
            {
                if (Bernouilli(1. / 2, 1. / 2))
                    candidats.push_back(Evenement(index, (double)
                        999. / Distance(tourelles[index].pos,
                               Plus_Proche(reperes, tourelles[index].pos))
                        // Votre formule de calcul ici
                    ));
                else
                    candidats.push_back(Evenement(index, (double)
                        100. / Distance_Carre(tourelles[index].pos, Base(ID))
                        // Votre formule de calcul ici aussi
                    ));
                total += candidats.back().probabilite;
            }
            for (size_t index = 0; index < tourelles.size(); index++)
                candidats[index].probabilite /= total;

            int choix = Choisir(candidats);
            vector<Position> alentours = Alentours(tourelles[choix].pos,
                                                   PORTEE_CONSTRUCTION);
            vector<Position> eligible;

            // Déterminer la liste des cases libres aux alentours de la tourelle
            for (size_t index = 0; index < alentours.size(); index++)
                if (!adjacent[alentours[index].x][alentours[index].y]
                &&  Constructible(alentours[index]))
                    eligible.push_back(alentours[index]);

            if (eligible.empty())
                Creer_Sorciers(MAGIE / COUT_SORCIER);
            else
            {
                Position element = eligible[Aleatoire(0, eligible.size() - 1)];
                int portee;
                
                // Choisir une case pas trop proche de la base
                for (size_t index = 0; index < eligible.size(); index++)
                    if (Distance_Carre(eligible[index], Base(ID))
                     >  Distance_Carre(element, Base(ID))
                    &&  Bernouilli(1. / 3, 2. / 3))
                        element = eligible[index];
                
                for (portee = PORTEE_MAX; COUT_AMELIORATION(portee) > MAGIE
                              && portee > PORTEE_TOURELLE; portee--);
                Creer_Tourelle(element, portee);
            }
            Creer_Sorciers(MAGIE / COUT_SORCIER);
        }
    }
}


void Deplacer(Position source, Position cible, int sorciers)
{
    vector<Position> trajet = Trajet(source, cible);
    Position actuel = trajet.back();
    
    for (int portee = 0; portee < PORTEE_SORCIER && actuel != cible; portee++)
    {
        actuel = trajet.back();
        trajet.pop_back();
    }
    Migrer(source, actuel, sorciers);
}

void Deplacement()
{
    vector<Position> potentiel;
    vector<int> ennemis = Adversaires();

    // Déterminer les objectifs potentiels sur la carte
    for (int x = 0; x < TAILLE_TERRAIN; x++)
    {
        for (int y = 0; y < TAILLE_TERRAIN; y++)
        {
            Position element = {x, y};
            if (TOUR >= (MAX_TOUR - ECHEANCE_FIN))
            {
                if (Case(x, y) == CASE_ARTEFACT
                || (Case(x, y) == CASE_BASE && element != Base(ID)))
                    potentiel.push_back(element);
            }
            else
            {
                if (Case(x, y) == CASE_FONTAINE)
                        potentiel.push_back(element);
            }
        }
    }
    for (size_t id = 0; id < ennemis.size(); id++)
        potentiel.push_back(Base(ennemis[id]));
    
    // Filtrer les objectifs potentiels
    for (size_t index = 0; index < potentiel.size(); index++)
        if (Sorciers_Places(potentiel[index], ID) > 20)
            potentiel.erase(potentiel.begin() + index);
    sort(potentiel.begin(), potentiel.end());
    
    if (potentiel.empty())
        return;
    // Affecter un objectif à chaque groupe de sorcier
    for (int x = 0; x < TAILLE_TERRAIN; x++)
    {
        for (int y = 0; y < TAILLE_TERRAIN; y++)
        {
            Position element = {x, y};
            int sorciers = Sorciers_Places(element, ID);
            
            if (sorciers > 0)
            {
                if (element == Base(ID) && sorciers > (10 + TOUR))
                    Deplacer(element, Plus_Proche(potentiel, element), sorciers);
                else if (( Case(x, y) == CASE_FONTAINE
                        || Case(x, y) == CASE_BASE) && sorciers > 40 && element != Base(ID))
                {
                    sorciers -= 21;
                    Deplacer(element, Plus_Proche(potentiel, element), sorciers);
                }
                else if (Case(x, y) == CASE_SIMPLE)
                    Deplacer(element, Plus_Proche(potentiel, element), sorciers);
            }
        }
    }
}

void Tirs()
{
    vector<Tourelle> tourelles = Liste_Tourelles(ID);
    
    for (size_t index = 0; index < tourelles.size(); index++)
        Exterminer(tourelles[index]);
}

void Siege()
{
    for (int x = 0; x < TAILLE_TERRAIN; x++)
    {
        for (int y = 0; y < TAILLE_TERRAIN; y++)
        {
            Position element = {x, y};
            int sorciers = Sorciers_Places(element, ID);
            
            if (sorciers > 0)
            {
                vector<Position> voisins = Voisins(element);
                
                for (size_t voisin = 0; voisin < voisins.size(); voisin++)
                    Attaquer(element, voisins[voisin], sorciers);
            }
        }
    }
}

void Fin()
{
}

