common.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include "optional.hpp"
 
static constexpr int MAX_ROUND = 512;
 
/* Map */
 
enum class BuildingType
{
    Empty,
    Tower,
    Base
};
 
static constexpr int EDGE = 10;
 
static constexpr int MAP_SIZE = 2 * EDGE - 1;
 
enum PointType {
    Void = -1,   
    Path = 0,    
    Barrier = 1, 
    Player0Highland = 2, 
    Player1Highland = 3, 
};
 
static constexpr int MAP_PROPERTY[MAP_SIZE][MAP_SIZE] = {
    {-1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 0, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, 0, 0, 1, 0, 1, 0, 0, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, -1, -1, -1, -1},
    {-1, -1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, -1, -1},
    {0, 0, 2, 2, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 2, 2, 0, 0},
    {0, 0, 0, 2, 0, 0, 2, 2, 0, 2, 0, 2, 2, 0, 0, 2, 0, 0, 0},
    {0, 2, 2, 0, 2, 0, 0, 2, 0, 2, 0, 2, 0, 0, 2, 0, 2, 2, 0},
    {0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0},
    {0, 0, 2, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 2, 0, 0},
    {0, 1, 3, 0, 3, 1, 0, 1, 0, 1, 0, 1, 0, 1, 3, 0, 3, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0},
    {0, 3, 3, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 3, 3, 0},
    {0, 3, 0, 0, 0, 0, 3, 3, 0, 3, 0, 3, 3, 0, 0, 0, 0, 3, 0},
    {0, 0, 3, 3, 0, 0, 0, 3, 0, 3, 0, 3, 0, 0, 0, 3, 3, 0, 0},
    {-1, 0, 0, 3, 0, 1, 1, 0, 0, 3, 0, 0, 1, 1, 0, 3, 0, 0, -1},
    {-1, -1, -1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, -1, -1, -1},
    {-1, -1, -1, -1, -1, 0, 0, 1, 1, 0, 1, 1, 0, 0, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
};
 
static constexpr int OFFSET[2][6][2] = {{{0, 1}, {-1, 0}, {0, -1}, {1, -1}, {1, 0}, {1, 1}},
                                {{-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, 0}, {0, 1}}};
 
inline int distance(int x0, int y0, int x1, int y1)
{
    int dy = abs(y0 - y1);
    int dx;
    if (abs(y0 - y1) % 2)
    {
        if (x0 > x1)
            dx = std::max(0, abs(x0 - x1) - abs(y0 - y1) / 2 - (y0 % 2));
        else
            dx = std::max(0, abs(x0 - x1) - abs(y0 - y1) / 2 - (1 - (y0 % 2)));
    }
    else
        dx = std::max(0, abs(x0 - x1) - abs(y0 - y1) / 2);
 
    return dx + dy;
}
 
inline bool is_valid_pos(int x, int y)
{
    if (x < 0 || x >= MAP_SIZE || y < 0 || y >= MAP_SIZE)
        return false;
    return MAP_PROPERTY[x][y] != PointType::Void;
}
 
inline bool is_path(int x, int y)
{
    if (x < 0 || x >= MAP_SIZE || y < 0 || y >= MAP_SIZE)
        return false;
    return MAP_PROPERTY[x][y] == PointType::Path;
}
 
inline bool is_highland(int player, int x, int y)
{
    if (x < 0 || x >= MAP_SIZE || y < 0 || y >= MAP_SIZE)
        return false;
    return MAP_PROPERTY[x][y] == (player == 0 ? PointType::Player0Highland : PointType::Player1Highland);
}
 
inline int get_direction(int x0, int y0, int x1, int y1)
{
    int dx = x1 - x0;
    int dy = y1 - y0;
    for (int i = 0; i < 6; ++i)
    {
        if (OFFSET[y0 % 2][i][0] == dx && OFFSET[y0 % 2][i][1] == dy)
            return i;
    }
    return -1;
}
 
/* Coin */
 
static constexpr int COIN_INIT = 50,
                     BASIC_INCOME = 1;
static constexpr int TOWER_BUILD_PRICE_BASE = 15,
                     TOWER_BUILD_PRICE_RATIO = 2;
static constexpr int LEVEL2_TOWER_UPGRADE_PRICE = 60,
                     LEVEL3_TOWER_UPGRADE_PRICE = 200;
static constexpr double TOWER_DOWNGRADE_REFUND_RATIO = 0.8;
static constexpr int LEVEL2_BASE_UPGRADE_PRICE = 200,
                     LEVEL3_BASE_UPGRADE_PRICE = 250;
 
/* Pheromone */
 
static constexpr double PHEROMONE_INIT = 10,
                        PHEROMONE_MIN = 0,
                        PHEROMONE_ATTENUATING_RATIO = 0.97;
 
 
/* Entity */
 
enum AntState
{
    Alive   = 0, 
    Success = 1, 
    Fail    = 2, 
    TooOld  = 3, 
    Frozen  = 4  
};
 
struct Ant
{
    // Attributes
    int id, player;
    int x, y;
    int hp, level, age;
    AntState state;
    std::vector<int> path;
    int evasion; // tag for emergency evasion
    bool deflector;  // tag for deflector
    // Static info
    static constexpr int AGE_LIMIT = 32;
    static constexpr int MAX_HP_INFO[] = {10, 25, 50}; // Max HP of an ant of certain level
    static constexpr int REWARD_INFO[] = {3, 5, 7};    // Reward for killing an ant of certain level
 
    Ant(int id, int player, int x, int y, int hp, int level, int age, AntState state)
        : id(id), player(player), x(x), y(y), hp(hp), level(level), age(age), state(state), evasion(0), deflector(false) {}
    
    void move(int direction)
    {
        path.push_back(direction);
        x += OFFSET[y % 2][direction][0];
        y += OFFSET[y % 2][direction][1];
    }
 
    int max_hp() const
    {
        return MAX_HP_INFO[level];
    }
 
    int reward() const
    {
        return REWARD_INFO[level];
    }
 
    bool is_alive() const
    {
        return state == AntState::Alive || state == AntState::Frozen;
    }
 
    bool is_in_range(int x, int y, int range) const
    {
        return distance(this->x, this->y, x, y) <= range;
    }
 
    bool is_attackable_from(int player, int x, int y, int range) const
    {
        return this->player != player && is_alive() && is_in_range(x, y, range);
    }
};
 
constexpr int Ant::MAX_HP_INFO[];
constexpr int Ant::REWARD_INFO[];
 
enum TowerType
{
    // Basic
    Basic = 0,
    // Heavy class
    Heavy     = 1,
    HeavyPlus = 11,
    Ice       = 12,
    Cannon    = 13,
    // Quick class
    Quick     = 2,
    QuickPlus = 21,
    Double    = 22,
    Sniper    = 23,
    // Mortar class
    Mortar     = 3,
    MortarPlus = 31,
    Pulse      = 32,
    Missile    = 33
};
 
struct TowerInfo
{
    int attack;   
    double speed; 
    int range;    
};
 
constexpr TowerInfo TOWER_INFO[] = {
    {5, 2, 2},  // ID = 0
    {20, 2, 2}, // ID = 1
    {6, 1, 3},  // ID = 2
    {16, 4, 3}, // ID = 3
    {}, {}, {}, {}, {}, {}, {}, // Padding
    {35, 2, 3}, // ID = 11
    {15, 2, 2}, // ID = 12
    {50, 3, 3}, // ID = 13
    {}, {}, {}, {}, {}, {}, {}, // Padding
    {8, 0.5, 3}, // ID = 21
    {7, 1, 4},  // ID = 22
    {15, 2, 6},   // ID = 23
    {}, {}, {}, {}, {}, {}, {}, // Padding
    {35, 4, 4}, // ID = 31
    {30, 3, 2}, // ID = 32 
    {45, 6, 5}  // ID = 33
};
 
struct Tower
{
    int id, player;
    int x, y;
    TowerType type;
    int damage, range;
    int cd;       
    double speed; 
 
    Tower(int id, int player, int x, int y, TowerType type = TowerType::Basic, int cd = -1)
        : id(id), player(player), x(x), y(y), type(type), cd(cd)
    {
        upgrade(type); // CD is reset to the max
        if (cd != -1) // If CD is given
            this->cd = cd;
    }
    std::vector<int> attack(std::vector<Ant>& ants)
    {
        std::vector<int> attacked_idxs;
        // Count down CD
        cd = std::max(cd - 1, 0);
        if (cd <= 0) // Ready to attack
        {
            // How many times the tower will try to find targets in this turn
            int time = speed >= 1 ? 1 : (1 / speed);
            // How many targets the tower should find each time (maybe less than required number)
            int target_num = type == Double ? 2 : 1;
            // Find and action
            while (time--)
            {
                std::vector<int> target_idxs = find_targets(ants, target_num);
                std::vector<int> attackable_idxs = find_attackable(ants, target_idxs);
                for (int idx: attackable_idxs)
                    action(ants[idx]);
                attacked_idxs.insert(attacked_idxs.end(), attackable_idxs.begin(), attackable_idxs.end());
            }
            // Uniquify to prevent multiple occurances of the same ant
            std::sort(attacked_idxs.begin(), attacked_idxs.end());
            attacked_idxs.erase(std::unique(attacked_idxs.begin(), attacked_idxs.end()), attacked_idxs.end());
            // Reset CD if really attacks
            if (!attacked_idxs.empty())
                reset_cd();
        }
        return attacked_idxs;
    }
 
    std::vector<int> find_targets(const std::vector<Ant>& ants, int target_num) const
    {
        // Initialize index array for reference
        std::vector<int> idxs = get_attackable_ants(ants, x, y, range);
        // Partial sort to get first n elements
        auto bound = target_num <= idxs.size() ? (idxs.begin() + target_num) : idxs.end();
        std::partial_sort(idxs.begin(), bound, idxs.end(), [&] (int i, int j) {
            int dist1 = distance(ants[i].x, ants[i].y, x, y),
                dist2 = distance(ants[j].x, ants[j].y, x, y);
            if (dist1 != dist2)
                return dist1 < dist2;
            else
                return i < j;
        });
        // Get first n elements
        if (idxs.size() > target_num)
            idxs.resize(target_num);
        return idxs;
    }
 
    std::vector<int> find_attackable(const std::vector<Ant>& ants, const std::vector<int>& target_idxs) const
    {
        std::vector<int> attackable_idxs;
        for (int idx: target_idxs)
        {
            std::vector<int> tmp;
            switch (type)
            {
                case Mortar:
                    tmp = get_attackable_ants(ants, ants[idx].x, ants[idx].y, 1);
                    break;
                case MortarPlus:
                    tmp = get_attackable_ants(ants, ants[idx].x, ants[idx].y, 1);
                    break;
                case Pulse:
                    tmp = get_attackable_ants(ants, x, y, range);
                    break;
                case Missile:
                    tmp = get_attackable_ants(ants, ants[idx].x, ants[idx].y, 2);
                    break;
                default:
                    tmp = {idx};
            }
            attackable_idxs.insert(attackable_idxs.end(), tmp.begin(), tmp.end());
        }
        return attackable_idxs;
    }
 
    void action(Ant& ant) const
    {
        if (ant.evasion > 0)  // evasion effect
            ant.evasion--;  // count down times
        else if (ant.deflector && damage < ant.max_hp() / 2) // deflector effect
            return; // get no damage
        else // normal condition
        {
            ant.hp -= damage;
            if (type == Ice)
                ant.state = AntState::Frozen;
            if (ant.hp <= 0)
                ant.state = AntState::Fail;
        }
    }
 
    std::vector<int> get_attackable_ants(const std::vector<Ant>& ants, int x, int y, int range) const
    {
        std::vector<int> idxs;
        for (int i = 0; i < ants.size(); ++i)
            if (ants[i].is_attackable_from(player, x, y, range))
                idxs.push_back(i);
        return idxs;
    }
 
    bool is_ready() const
    {
        return cd <= 0;
    }
 
    void reset_cd()
    {
        cd = speed > 1 ? speed : 1;
    }
 
    void upgrade(TowerType new_type)
    {
        type = new_type;
        damage = TOWER_INFO[new_type].attack;
        speed = TOWER_INFO[new_type].speed;
        range = TOWER_INFO[new_type].range;
        reset_cd(); // Reset when `speed` has changed
    }
 
    bool is_upgrade_type_valid(int type) const
    {
        if (type < TowerType::Basic || type > TowerType::Missile)
            return false;
        switch (this->type)
        {
            case TowerType::Basic:
                return type == TowerType::Heavy || type == TowerType::Quick || type == TowerType::Mortar;
            case TowerType::Heavy:
                return type == TowerType::HeavyPlus || type == TowerType::Ice || type == TowerType::Cannon;
            case TowerType::Quick:
                return type == TowerType::QuickPlus || type == TowerType::Double || type == TowerType::Sniper;
            case TowerType::Mortar:
                return type == TowerType::MortarPlus || type == TowerType::Pulse || type == TowerType::Missile;
        }
        return false;
    }
 
    void downgrade()
    {
        type = static_cast<TowerType>(type / 10);
        damage = TOWER_INFO[type].attack;
        speed = TOWER_INFO[type].speed;
        range = TOWER_INFO[type].range;
        reset_cd(); // Reset when `speed` has changed
    }
 
    bool is_downgrade_valid() const
    {
        return type != TowerType::Basic;
    }
};
 
struct Base
{
    // Attributes
    const int player, x, y;
    int hp;
    int gen_speed_level; 
    int ant_level;       
    // Static info
    static constexpr int MAX_HP = 50;
    static constexpr int POSITION[2][2] = {{2, EDGE - 1},  {(MAP_SIZE - 1) - 2, EDGE - 1}};  
    static constexpr int GENERATION_CYCLE_INFO[] = {4, 2, 1}; 
    
    Base(int player)
        : player(player), x(POSITION[player][0]), y(POSITION[player][1]), hp(MAX_HP),
          gen_speed_level(0), ant_level(0) {}
 
    optional<Ant> generate_ant(int id, int round)
    {
        return round % GENERATION_CYCLE_INFO[gen_speed_level] == 0
            ? make_optional(Ant(
                id, player, x, y,
                Ant::MAX_HP_INFO[ant_level], ant_level,
                0, AntState::Alive
            ))
            : nullopt;
    }
 
    void upgrade_generation_speed()
    {
        gen_speed_level++;
    }
 
    void upgrade_generated_ant()
    {
        ant_level++;
    }
};
 
constexpr int Base::POSITION[2][2];
constexpr int Base::GENERATION_CYCLE_INFO[];
 
enum SuperWeaponType
{
    LightningStorm = 1,
    EmpBlaster = 2,
    Deflector = 3,
    EmergencyEvasion = 4,
    SuperWeaponCount
};
 
static constexpr int SUPER_WEAPON_INFO[5][4] = {
    {}, // Padding
    {20, 3, 100, 150}, // LightningStorm
    {20, 3, 100, 150}, // EmpBlaster
    {10, 3, 50, 100}, // Deflector
    {1, 3, 50, 100}   // Evasion
};
 
struct SuperWeapon
{
    SuperWeaponType type;
    int player;
    int x, y;
    int left_time;
    int range;
 
    SuperWeapon(SuperWeaponType type, int player, int x, int y) : 
        type(type), player(player), x(x), y(y), left_time(SUPER_WEAPON_INFO[type][0]), range(SUPER_WEAPON_INFO[type][1]) {}
 
    bool is_in_range(int x, int y) const
    {
        return distance(x, y, this->x, this->y) <= range;
    }
};
 
/* Operation */
 
enum OperationType
{
    // Towers
    BuildTower = 11,     
    UpgradeTower = 12,   
    DowngradeTower = 13, 
    // Super weapons
    UseLightningStorm = 21,   
    UseEmpBlaster = 22,       
    UseDeflector = 23,        
    UseEmergencyEvasion = 24, 
    // Base
    UpgradeGenerationSpeed = 31, 
    UpgradeGeneratedAnt = 32     
};
 
struct Operation
{
    OperationType type;
    int arg0, arg1;
    static constexpr int INVALID_ARG = -1; 
 
    Operation(OperationType type, int arg0 = INVALID_ARG, int arg1 = INVALID_ARG)
        : type(type), arg0(arg0), arg1(arg1) {}
 
    friend std::ostream& operator<<(std::ostream& out, const Operation& op) 
    {
        out << op.type;
        if (op.arg0 != INVALID_ARG)
            out << ' ' << op.arg0;
        if (op.arg1 != INVALID_ARG)
            out << ' ' << op.arg1;
        out << std::endl;
        return out;
    }
};
 
struct Random
{
    unsigned long long seed; 
 
    Random(unsigned long long seed): seed(seed) {}
 
    unsigned long long get()
    {
        seed = (25214903917 * seed) & ((1ll << 48) - 1);
        return seed;
    }
};