cig/spring2022/spring2022.py

import sys
import time
import heapq
import math

debug = True

t0 = time.time()


# todo: attacking strategy: place one guy nearer to opponent hq
# todo: considerate shielding monsters threatening opponent hq
# todo: review the order heroes are playing in each strategy


def log(*msg):
    if debug:
        print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr, flush=True)


def time_to(total, step):
    """ number of steps to reach total """
    return total // step + (1 if total % step > 0 else 0)


class BaseClass:
    def __repr__(self):
        return f"<{self.__class__.__name__}: {self.__dict__}>"


class Queue(BaseClass):
    def __init__(self):
        self.items = []

    def __bool__(self):
        return bool(self.items)

    def __repr__(self):
        return str(self.items)

    def values(self):
        return (v for _, v in self.items)

    def put(self, priority, item):
        while priority in [p for p, _ in self.items]:
            priority += 1
        heapq.heappush(self.items, (priority, item))

    def get(self):
        return heapq.heappop(self.items)[1]

    def get_items(self):
        return heapq.heappop(self.items)


class GridItem(BaseClass):
    def __init__(self, pos=(-1, -1)):
        self._previous_pos = None
        self._pos = pos

    @property
    def x(self):
        return self.pos[0]

    @property
    def y(self):
        return self.pos[1]

    @property
    def pos(self):
        return self._pos

    @pos.setter
    def pos(self, pos):
        self._previous_pos = self.pos
        self._pos = pos

    @property
    def previous_pos(self):
        return self._previous_pos


class HeadQuarter(GridItem):
    SIGHT = 6000

    def __init__(self, pos):
        super().__init__(pos)
        self.health = 3
        self.mana = 10


class Role:
    NAME = "None"
    POSITION = (1500, 1500)
    ALT_POSITIONS = []

    def __repr__(self):
        return self.__class__.__name__


class Defender(Role):
    NAME = "Defender"
    POSITION = (1250, 1250)


class DefenderRight(Defender):
    NAME = "Defender (right)"
    POSITION = (500, 3000)


class DefenderLeft(Defender):
    NAME = "Defender (left)"
    POSITION = (3000, 500)


class GateKeeper(Role):
    NAME = "Gatekeeper"
    POSITION = (4500, 3000)


class GateKeeperRight(GateKeeper):
    NAME = "Gatekeeper (right)"
    POSITION = (1500, 5000)


class GateKeeperLeft(GateKeeper):
    NAME = "Gatekeeper (left)"
    POSITION = (5500, 1000)


class Hunter(Role):
    NAME = "Hunter"
    POSITION = (6000, 4000)
    ALT_POSITIONS = [(3500, 6500), (8000, 1500)]


class HunterRight(Hunter):
    NAME = "Hunter (right)"
    POSITION = (3500, 6500)
    ALT_POSITIONS = [(1500, 7500), (6000, 4000)]


class HunterLeft(Hunter):
    NAME = "Hunter (left)"
    POSITION = (8000, 1500)
    ALT_POSITIONS = [(9000, 500), (6000, 4000)]


class Attacker(Role):
    NAME = "Attacker"
    POSITION = (7500, 4000)
    ALT_POSITIONS = [(5000, 6500), (8000, 2000)]


class AttackerRight(Attacker):
    NAME = "Attacker (right)"
    POSITION = (5000, 6500)
    ALT_POSITIONS = [(1500, 7500), (6000, 4000)]


class AttackerLeft(Attacker):
    NAME = "Attacker (left)"
    POSITION = (8000, 2000)
    ALT_POSITIONS = [(9000, 500), (6000, 4000)]


class Saboteur(Role):
    NAME = "Saboteur"
    POSITION = (15000, 6000)
    ALT_POSITIONS = [(12000, 3500), (10000, 6000)]


class Strategy(BaseClass):
    def __init__(self, roles, default=Defender):
        self.roles = roles
        self.pos = 0
        self.default = default

    def pick(self):
        """ Get the next role in line for the hero, or defender by default """
        try:
            role = self.roles[self.pos]
            self.pos += 1
            return role
        except IndexError:
            return self.default


class StrategyFullDefense(Strategy):
    NAME = "Full Defense"

    def __init__(self):
        super().__init__([Defender, DefenderLeft, DefenderRight])


class StrategyDefensive(Strategy):
    NAME = "Defensive"

    def __init__(self):
        super().__init__([Attacker, GateKeeper, Defender])


class StrategyBalanced(Strategy):
    NAME = "Balanced"

    def __init__(self):
        super().__init__([Attacker, Hunter, Defender])


class StrategyPrudentFarm(Strategy):
    NAME = "Farm (prudent)"

    def __init__(self):
        super().__init__([HunterLeft, HunterRight, GateKeeper])


class StrategyFarm(Strategy):
    NAME = "Farm"

    def __init__(self):
        super().__init__([Attacker, HunterLeft, HunterRight])


class StrategyAggressive(Strategy):
    NAME = "Aggressive"

    def __init__(self):
        super().__init__([Saboteur, Attacker, GateKeeper])


class Action(BaseClass):
    def __init__(self, priority=1000):
        self.priority = priority
        self.feasibility = 0
        self.done = False
        self._pos = None

    @property
    def pos(self):
        return self._pos

    def do(self):
        self.done = True

    def __repr__(self):
        return f"{self.__class__.__name__} [{self.priority}/{self.feasibility}]"


class Move(Action):
    def __init__(self, pos, priority=1000):
        super().__init__(priority)
        self._pos = pos

    def do(self):
        super().do()
        print(f"MOVE {self.pos[0]} {self.pos[1]}")

    def __repr__(self):
        return f"{self.__class__.__name__} {self.pos} [{self.priority}/{self.feasibility}]"


class Explore(Move):
    pass


class MoveAt(Action):
    def __init__(self, target, priority=1000):
        super().__init__(priority)
        self.target = target

    @property
    def pos(self):
        return self.target.pos

    def do(self):
        super().do()
        print(f"MOVE {self.pos[0]} {self.pos[1]}")

    def __repr__(self):
        return f"{self.__class__.__name__} {self.target.id} [{self.priority}/{self.feasibility}]"


class Defend(MoveAt):
    pass


class Hunt(MoveAt):
    pass


class Reposition(Move):
    pass


class Cast(Action):
    SPELL = ""
    MANA_COST = 10

    def __init__(self, priority=1000):
        super().__init__(priority)
        self.params = []

    def do(self):
        super().do()
        print(f"SPELL {self.SPELL} {' '.join(map(str, self.params))}")

    def __repr__(self):
        return f"{self.__class__.__name__} {' '.join(map(str, self.params))} [{self.priority}/{self.feasibility}]"


class CastWind(Cast):
    SPELL = "WIND"
    RADIUS = 1280
    DEPTH = 2200

    def __init__(self, pos, priority=1000):
        super().__init__(priority)
        self.params = pos


class CastControl(Cast):
    SPELL = "CONTROL"
    RANGE = 2200

    def __init__(self, target_id, pos, priority=1000):
        super().__init__(priority)
        x, y = pos
        self.params = [target_id, x, y]


class CastShield(Cast):
    SPELL = "SHIELD"
    RANGE = 2200
    DURATION = 12

    def __init__(self, target_id, priority=1000):
        super().__init__(priority)
        self.params = [target_id]


class Wait(Action):
    def do(self):
        print(f"WAIT")


class Entity(GridItem):
    TYPE_MONSTER = 0
    TYPE_HERO = 1
    TYPE_OPPONENT_HERO = 2

    def __init__(self, id_, pos=(-1, -1)):
        super().__init__(pos)
        self.id = id_  # Unique identifier
        self.shield_life = -1  # Count down until shield spell fades
        self.health = -1  # Remaining health of this monster
        self.is_controlled = False

        # Computed properties
        self.visible = False
        self.distance_to_hq = None
        self.moving_time_to_hq = None
        self.distance_to_opponent_hq = None
        self.moving_time_to_opponent_hq = None
        self.distance_from_entity = {}
        self.moving_time_from_entity = {}
        self.go_toward_hq = False
        self.go_toward_opponent_hq = False
        self.is_on_my_side = False
        self.is_on_opponent_side = False
        self.camper = False

    def init_round(self):
        self.visible = False
        self.distance_to_hq = None
        self.moving_time_to_hq = None
        self.distance_to_opponent_hq = None
        self.moving_time_to_opponent_hq = None
        self.distance_from_entity = {}
        self.moving_time_from_entity = {}
        self.go_toward_hq = False
        self.go_toward_opponent_hq = False
        self.is_on_my_side = False
        self.is_on_opponent_side = False
        self.camper = False


class Hero(Entity):
    ATTACK = 2
    ATTACK_RANGE = 800
    SPEED = 800
    SIGHT = 2200

    def __init__(self, id_):
        super().__init__(id_)
        self.role = Role
        self.current_role_pos = None


class OpponentHero(Hero):
    def __init__(self, id_):
        super().__init__(id_)


class Monster(Entity):
    THREAT_FOR_ME = 1
    THREAT_FOR_OPPONENT = 2
    NO_THREAT = 0
    SPEED = 400
    THREAT_RANGE = 5000
    ATTACK_RANGE = 300

    def __init__(self, id_):
        super().__init__(id_)
        self.near_base = False
        self.threat_for = self.NO_THREAT
        self.vx = 0  # Trajectory of this monster
        self.vy = 0

    @property
    def next_pos(self):
        return self.x + self.vx, self.y + self.vy

    @property
    def threats_hq(self):
        return self.threat_for == self.THREAT_FOR_ME

    @property
    def threats_opponent_hq(self):
        return self.threat_for == self.THREAT_FOR_OPPONENT

    @property
    def alive(self):
        return self.health > 0


class Grid(BaseClass):
    MAX_X = 17630
    MAX_Y = 9000

    def __init__(self):
        self.threat_level = 0
        self.round = 0
        self._index = {}
        self.hq = None
        self.opponent_hq = None
        self.strategy = None

    @property
    def index(self):
        return self._index

    def get(self, _id):
        return self._index[_id]

    @property
    def entities(self):
        return [e for e in self._index.values() if e.visible]

    @property
    def heroes(self):
        return sorted([v for v in self.entities if type(v) is Hero], key=lambda x: x.id)

    @property
    def monsters(self):
        return [v for v in self.entities if type(v) is Monster]

    @property
    def opponent_heroes(self):
        return [v for v in self.entities if type(v) is OpponentHero]

    def init_game(self):
        self.hq = HeadQuarter([int(i) for i in input().split()])
        self.opponent_hq = HeadQuarter((Grid.MAX_X, Grid.MAX_Y) if self.hq.x == 0 else (0, 0))
        _ = int(input())  # Heroes per player, always 3

    def update_entity(self, entity):
        entity.distance_to_hq = self.distance(self.hq.pos, entity.pos)
        entity.moving_time_to_hq = self.moving_time_to(entity, self.hq.pos)
        entity.distance_to_opponent_hq = self.distance(self.opponent_hq.pos, entity.pos)
        entity.moving_time_to_opponent_hq = self.moving_time_to(entity, self.opponent_hq.pos)
        entity.distance_from_entity = {e.id: self.distance(e.pos, entity.pos) for e in self.entities if
                                       e.id != entity.id}
        entity.moving_time_from_entity = {e.id: self.moving_time_to(entity, e.pos) for e in self.entities if
                                          e.id != entity.id}
        if type(entity) is Monster:
            entity.go_toward_hq = (entity.vx <= 0 and entity.vy <= 0 and self.hq.x == 0 or
                                   entity.vx >= 0 and entity.vy >= 0 and self.hq.x != 0)
            entity.go_toward_opponent_hq = (entity.vx >= 0 and entity.vy >= 0 and self.opponent_hq.x != 0 or
                                            entity.vx <= 0 and entity.vy <= 0 and self.opponent_hq.x == 0)

        entity.is_on_my_side = entity.distance_to_hq < entity.distance_to_opponent_hq
        entity.is_on_opponent_side = not entity.is_on_my_side

        if type(entity) is OpponentHero:
            if entity.previous_pos and entity.pos == entity.previous_pos and entity.is_on_my_side:
                entity.camper = True

    def init_round(self):
        """ get inputs and  reinit the state of entities """
        self.round += 1
        log(f"Round {self.round}")

        # *** Update HQ status
        self.hq.health, self.hq.mana = [int(j) for j in input().split()]
        self.opponent_hq.health, self.opponent_hq.mana = [int(j) for j in input().split()]

        # *** Reinit the entities state
        for entity in self.entities:
            entity.init_round()

        # *** Update entities
        entity_count = int(input())  # Amount of heroes and monsters you can see
        for i in range(entity_count):

            _id, _type, _x, _y, shield_life, is_controlled, health, vx, vy, near_base, threat_for = [int(j) for j in
                                                                                                     input().split()]
            # Entity is not indexed already
            if _id not in self.index:
                if _type == Entity.TYPE_MONSTER:
                    entity = Monster(_id)

                elif _type == Entity.TYPE_HERO:
                    entity = Hero(_id)

                elif _type == Entity.TYPE_OPPONENT_HERO:
                    entity = OpponentHero(_id)

                else:
                    log("Error: unknown type ({_type})")
                    break
                self.index[_id] = entity

            # Update entity
            entity = self.get(_id)
            entity.pos = (_x, _y)
            entity.shield_life = shield_life
            entity.is_controlled = is_controlled
            entity.health = health
            entity.visible = True

            if type(entity) is Monster:
                entity.near_base = bool(near_base)
                entity.threat_for = threat_for
                entity.vx = vx
                entity.vy = vy

        # purge index
        self.purge()

        # update entities
        for entity in self.entities:
            self.update_entity(entity)

        # *** define strategy and roles
        self.threat_level = self.compute_threat_level()

        self.strategy = self.define_strategy()
        for hero in self.heroes:
            role = self.strategy.pick()
            if hero.role != role:
                hero.current_role_pos = None
            elif hero.pos in self.get_role_positions(hero.role):
                # remember as the last occupied role position
                hero.current_role_pos = hero.pos
            hero.role = role

        log(f'## Threat: {self.threat_level} - Strategy: {self.strategy.NAME} ##')
        log("Heroes: {}".format(','.join(
            [f"<{h.id},P:{h.pos},M:{h.moving_time_to_hq},O:{int(h.is_on_opponent_side)}>" for h in self.heroes])))
        log("Monsters: {}".format(','.join(
            [f"<{m.id},P:{m.pos},T:{int(m.threats_hq)},V:{int(m.visible)},M:{m.moving_time_to_hq},"
             f"N:{int(m.go_toward_hq)},O:{int(m.go_toward_opponent_hq)},S:{int(m.shield_life > 0)}>" for m
             in self.monsters])))
        log("Opponents: {}".format(','.join(
            [f"<{o.id},P:{o.pos},S:{o.shield_life},M:{o.moving_time_to_hq},C:{int(o.camper)}>" for o in self.opponent_heroes])))

    def purge(self):
        """ remove dead entities from the index """
        self._index = {k: e for k, e in self._index.items() if type}

        index = {}
        for entity in self.entities:
            if isinstance(entity, Monster):
                if self.visible(entity.next_pos) and not entity.visible:
                    # entity should be visible, but has not been seen, presumed dead
                    continue

            index[entity.id] = entity

        self._index = index

    def compute_threat_level(self):
        level = 0
        for monster in self.monsters:
            if monster.threats_hq:
                level += (monster.health + monster.shield_life) * max(24 - monster.moving_time_to_hq, 0)
        for enemy in self.opponent_heroes:
            if enemy.is_on_my_side:
                level += 50

        return level

    def define_strategy(self):
        # *** Define strategy

        if self.threat_level > 1400:
            return StrategyFullDefense()
        if self.threat_level > 1000:
            return StrategyDefensive()
        elif self.threat_level > 800:
            return StrategyBalanced()

        if self.round < 40:
            if self.threat_level:
                return StrategyPrudentFarm()
            else:
                return StrategyFarm()
        elif self.round < 100:
            return StrategyBalanced()
        else:
            return StrategyAggressive()

    def get_action_for(self, hero):
        actions = []

        k0_defend = 10
        k0_reposition = 250
        k0_hunt = 200
        k0_cast_wind = 150
        k0_cast_offensive_wind = 220
        k0_cast_control = 100
        k0_cast_control_monster = 100
        k0_cast_offensive_control = 200
        k0_cast_shield = 150
        k0_cast_shield_on_monster = 80

        k_attack_time = 5
        k_hero_nearer = 30
        k_defend_against_shielded = -20
        k_defender_priority_bonus = -50
        k_go_toward_hq = -30
        k_hunt_distance = 5
        k_hunt_pv = 2
        k_position_distance_from_pos = -8
        k_cast_wind_threats = -1
        k_cast_wind_enemy = -20
        k_cast_wind_enemy_on_my_side = -10
        k_cast_wind_enemy_near_hq = -5
        k_cast_wind_proximity = 5
        k_cast_wind_bad_target = 10
        k_cast_wind_last_defense = -30
        k_cast_wind_last_defense_limit = 10
        k_control_health = -2
        k_control_time = 5
        k_control_going_toward = -20
        k_shield_enemy_near = -20
        k_shield_monster = -1
        k_shield_monster_distance = 3
        k_cast_shield_distance = 10
        k_camper_bonus = -50
        k_cast_control_on_opponent_defender = 10
        k_cast_control_on_opponent_defender_threat = -1

        defend_threshold = 18
        min_control_hp = 15
        min_shield_distance = max(CastWind.RADIUS, CastControl.RANGE)
        min_shield_threat = 60
        offensive_buff = -1
        offensive_buff_control = -2

        k_feasibility_moving_time = 10
        k_feasibility_casting_cost = 5
        k_feasibility_far_from_pos = 5
        k_feasibility_defender_far_from_pos = 10

        min_mana_priority = 240

        # *** Defend
        for monster in self.monsters:
            if monster.threats_hq and monster.moving_time_to_hq < defend_threshold:
                priority = k0_defend

                # Réduire la priorité en fonction de la distance
                priority += (k_attack_time * monster.moving_time_to_hq)
                # TODO: réduire priority pour chaque monstre suppl que l'attaque pourrait toucher

                priority += k_defend_against_shielded * int(monster.shield_life > 0)

                # Réduire la priorité pour chaque héros plus proche du qg
                for other_hero in [h for h in self.heroes if h is not hero]:
                    if other_hero.moving_time_to_hq < monster.moving_time_to_hq:
                        priority += k_hero_nearer

                if isinstance(hero, (Defender, GateKeeper)):
                    priority += k_defender_priority_bonus

                action = Defend(monster, priority)
                actions.append(action)

        # *** Position
        role_pos = self.get_role_position(hero)
        if hero.pos != role_pos:
            priority = k0_reposition
            priority += k_position_distance_from_pos * self.moving_time_to(hero, role_pos)
            action = Reposition(role_pos, priority)
            actions.append(action)

        # *** Hunt
        if hero.is_on_my_side and \
                not issubclass(hero.role, (Defender, GateKeeper)) and \
                not (issubclass(hero.role, Saboteur) and hero.is_on_my_side):
            for monster in self.monsters:
                if monster.threats_opponent_hq:
                    # it's defense domain or not worth it
                    continue
                priority = k0_hunt
                priority += k_hunt_distance * hero.moving_time_from_entity[monster.id]
                priority += k_go_toward_hq * monster.go_toward_hq
                priority += k_hunt_pv * monster.health
                action = Hunt(monster, priority)
                actions.append(action)

        # *** Cast WIND on threats
        if self.hq.mana >= CastWind.MANA_COST:
            affected = [e for e in self.in_wind_area(hero) if not e.shield_life]
            if affected:
                priority = k0_cast_wind

                # Affected entities
                priority += k_cast_wind_threats * sum([m.health for m in affected if type(m) is Monster and m.threats_hq])
                priority += k_cast_wind_enemy * len([m for m in affected if type(m) is OpponentHero])
                priority += k_cast_wind_enemy_on_my_side * len([m for m in affected if type(m) is OpponentHero and m.is_on_my_side])
                priority += k_cast_wind_enemy_near_hq * sum([m.moving_time_to_hq for m in affected if type(m) is OpponentHero if m.distance_to_hq < HeadQuarter.SIGHT])
                priority += k_camper_bonus * len([m for m in affected if type(m) is OpponentHero and m.is_on_my_side and m.camper])

                # Hq average proximity
                priority += k_cast_wind_proximity * hero.moving_time_to_hq

                # last defence
                priority += sum([k_cast_wind_last_defense * (k_cast_wind_last_defense_limit - m.moving_time_to_hq) for m in affected if type(m) is Monster and m.moving_time_to_hq < k_cast_wind_last_defense_limit])

                action = CastWind(self.opponent_hq.pos, priority)
                actions.append(action)

        # *** Cast CONTROL on approaching monsters
        if self.hq.mana >= (CastWind.MANA_COST + CastControl.MANA_COST):
            possible_targets = [m for m in self.monsters if
                                m.distance_from_entity[hero.id] < CastControl.RANGE and not m.shield_life]
            for monster in possible_targets:
                if monster.health < min_control_hp:
                    # too weak
                    continue

                if monster.go_toward_opponent_hq:
                    # already targeting enemy
                    continue

                if monster.distance_to_hq <= (monster.THREAT_RANGE + monster.SPEED):
                    # too late...
                    continue

                if monster.is_controlled:
                    # already controlled
                    continue

                priority = k0_cast_control
                priority += k_control_health * monster.health
                priority += k_control_time * min(monster.moving_time_to_opponent_hq, monster.moving_time_to_hq)
                priority += k_control_going_toward * monster.go_toward_hq
                action = CastControl(monster.id, self.opponent_hq.pos, priority)
                actions.append(action)

        # *** Cast CONTROL on campers
        if self.hq.mana >= (CastWind.MANA_COST + CastControl.MANA_COST):
            possible_targets = [e for e in self.opponent_heroes if
                                e.distance_from_entity[hero.id] < CastControl.RANGE
                                and not e.shield_life and e.camper]
            for enemy in possible_targets:
                if enemy.is_controlled:
                    # already controlled
                    continue
                priority = k0_cast_control
                action = CastControl(enemy.id, self.opponent_hq.pos, priority)
                actions.append(action)

        # *** Cast SHIELD on self
        opponents_within_casting_range = [o.id for o in self.opponent_heroes if
                                          o.distance_from_entity[hero.id] < min_shield_distance]
        if hero.shield_life == 0 and \
                self.hq.mana >= (CastWind.MANA_COST + CastShield.MANA_COST) and \
                opponents_within_casting_range\
                and self.threat_level > min_shield_threat\
                and hero.is_on_my_side:
            # log(f"{hero.id}: shield against {[(o.id, o.pos, o.distance_from_entity[hero.id]) for o in self.opponent_heroes]}")
            priority = k0_cast_shield
            priority += k_shield_enemy_near * len(opponents_within_casting_range)
            priority += k_cast_shield_distance * min(hero.moving_time_to_hq, hero.moving_time_to_opponent_hq)
            action = CastShield(hero.id, priority)
            actions.append(action)

        if hero.is_on_opponent_side and not isinstance(self.strategy, (StrategyDefensive, StrategyFullDefense)):

            threat_on_opponent_hq = sum(m.health + m.shield_life for m in self.monsters if m.threats_opponent_hq)
            threat_on_opponent_hq -= 10 * len([o for o in self.opponent_heroes if o.distance_to_opponent_hq < Monster.THREAT_RANGE])
            log(f"Offensive buff: {threat_on_opponent_hq}")

            for monster in self.monsters:
                # cast control on monsters near opponent hq
                if self.hq.mana >= (CastWind.MANA_COST + CastControl.MANA_COST) and monster.distance_from_entity[hero.id] < CastControl.RANGE:
                    if monster.health < min_control_hp:
                        # too weak
                        continue

                    if monster.go_toward_opponent_hq:
                        # already targeting enemy
                        continue

                    if monster.shield_life > 0:
                        continue

                    priority = k0_cast_control_monster
                    action = CastControl(monster.id, self.opponent_hq.pos, priority)
                    actions.append(action)

            if threat_on_opponent_hq > 50:
                for monster in self.monsters:
                    # cast shield on monsters threatening opponent hq
                    if self.hq.mana >= (CastWind.MANA_COST + CastShield.MANA_COST) and monster.distance_from_entity[hero.id] < CastShield.RANGE:
                        if not monster.threats_opponent_hq or not monster.go_toward_opponent_hq:
                            # not targeting enemy
                            continue
                        if monster.shield_life > 0:
                            continue
                        priority = k0_cast_shield_on_monster
                        priority += k_shield_monster_distance * monster.moving_time_to_opponent_hq
                        priority += k_shield_monster * monster.health
                        action = CastShield(monster.id, priority)
                        actions.append(action)

            # cast wind on monsters threatening opponent hq
            affected = [e for e in self.in_wind_area(hero) if not e.shield_life]
            if self.hq.mana >= (CastWind.MANA_COST + CastShield.MANA_COST) and affected:
                priority = k0_cast_offensive_wind
                priority += k_cast_wind_threats * sum([m.health for m in affected if type(m) is Monster and m.threats_opponent_hq and not m.shield_life])
                priority += k_cast_wind_bad_target * len([e for e in affected if type(e) is OpponentHero and not e.shield_life])
                priority += k_cast_wind_proximity * hero.moving_time_to_opponent_hq
                priority += offensive_buff * threat_on_opponent_hq
                action = CastWind(self.opponent_hq.pos, priority)
                actions.append(action)

            # cast wind on enemies defending opponent hq
            affected = [e for e in self.in_wind_area(hero) if not e.shield_life]
            if self.hq.mana >= (CastWind.MANA_COST + CastShield.MANA_COST) and affected:
                priority = k0_cast_offensive_wind
                priority += k_cast_wind_enemy * len([e for e in affected if type(e) is OpponentHero and not e.shield_life])
                priority += k_cast_wind_bad_target * len([e for e in affected if type(e) is Monster and not e.shield_life])
                priority += k_cast_wind_proximity * hero.moving_time_to_opponent_hq
                priority += offensive_buff * threat_on_opponent_hq
                action = CastWind(self.hq.pos, priority)
                actions.append(action)

            for enemy in self.opponent_heroes:
                if self.hq.mana >= (CastWind.MANA_COST + CastControl.MANA_COST) and enemy.distance_from_entity[hero.id] < CastControl.RANGE:
                    if enemy.is_controlled:
                        # already controlled
                        continue
                    if enemy.shield_life:
                        continue

                    priority = k0_cast_offensive_control
                    priority += k_cast_control_on_opponent_defender * enemy.moving_time_to_opponent_hq
                    priority += k_cast_control_on_opponent_defender_threat * threat_on_opponent_hq
                    priority += offensive_buff_control * threat_on_opponent_hq
                    action = CastControl(enemy.id, self.hq.pos, priority)
                    actions.append(action)

        # Estimate feasibility
        for action in actions:
            action.feasibility = -1

            # ignore impossibles actions
            if isinstance(action, Defend):
                if action.target.moving_time_to_hq < hero.moving_time_to_hq:
                    # too late...
                    continue

            action.feasibility = 0

            if action.pos and not isinstance(action, Reposition):
                action.feasibility += k_feasibility_moving_time * self.moving_time_to(hero, action.pos)

            if isinstance(action, Cast):
                action.feasibility += k_feasibility_casting_cost * action.MANA_COST

            action.feasibility += k_feasibility_far_from_pos * self.moving_time_to(hero, hero.current_role_pos or hero.role.POSITION)

        actions = sorted([a for a in actions if a.feasibility >= 0], key=lambda a: a.priority + a.feasibility)

        try:
            log(actions)
            return actions[0]
        except IndexError:
            return Wait()

    def update_after_action(self, hero, action):
        if isinstance(action, (Move, MoveAt)):
            hero.pos = self.position_after_moving(hero, action.pos, hero.SPEED)
            # log(f"{hero.id}: move to {action.pos}, new pos: {hero.pos}")
            for monster in self.in_attack_area(hero):
                monster.health -= hero.ATTACK
                if monster.health <= 0:
                    del self._index[monster.id]

        if isinstance(action, Cast):
            self.hq.mana -= action.MANA_COST

        if isinstance(action, CastWind):
            affected = self.in_wind_area(hero)
            for entity in affected:
                entity.pos = self.position_after_moving(entity, action.params, action.DEPTH)
                self.update_entity(entity)

        if isinstance(action, CastShield):
            self.index[action.params[0]].shield_life = CastShield.DURATION

        if isinstance(action, CastControl):
            target_id, x, y = action.params
            target = self.index[target_id]
            target.pos = self.position_after_moving(target, (x, y), target.SPEED)
            self.update_entity(target)
            target.is_controlled = True
            if type(target) is Monster:
                target.go_toward_opponent_hq = True

        if not isinstance(action, Reposition):
            # reinit alternative positions if hero has acted elsewhere
            hero.current_role_pos = None

    def play(self, hero):
        action = self.get_action_for(hero)
        log(f"> {action}")
        action.do()
        self.update_after_action(hero, action)

    @staticmethod
    def manhattan(from_, to_):
        xa, ya = from_
        xb, yb = to_
        return abs(xa - xb) + abs(ya - yb)

    @staticmethod
    def distance(from_, to_):
        xa, ya = from_
        xb, yb = to_
        return int(math.sqrt((xa - xb) ** 2 + abs(ya - yb) ** 2))

    @staticmethod
    def moving_time_to(entity, target):
        distance = Grid.distance(entity.pos, target)
        return time_to(distance, entity.SPEED)

    @staticmethod
    def position_after_moving(entity, pos, speed):
        """ get the entity position after it moved toward `pos` from `speed` """
        x0, y0 = entity.pos
        x1, y1 = pos
        dx, dy = (x1 - x0) / (x1 or 1), (y1 - y0) / (y1 or 1)

        return x0 + int(dx * speed), y0 + int(dy * speed)

    def visible(self, pos):
        return self.distance(self.hq.pos, pos) < self.hq.SIGHT or \
               any(self.distance(h.pos, pos) < h.SIGHT for h in self.heroes)

    def get_role_positions(self, role):
        positions = [role.POSITION] + role.ALT_POSITIONS
        if self.hq.x != 0:
            return [(self.MAX_X - x, self.MAX_Y - y) for x, y in positions]
        else:
            return positions

    def get_role_position(self, hero):
        """ get the position for the given role """
        role_positions = self.get_role_positions(hero.role)

        pos = role_positions[0]
        # log(f"{hero.pos} - {hero.current_role_pos} - {role_positions}")
        if hero.current_role_pos:
            try:
                i = role_positions.index(hero.current_role_pos)
                pos = role_positions[i + 1]
            except (ValueError, IndexError):
                pass
        return pos

    def in_attack_area(self, hero):
        return [e for e in self.monsters if e.distance_from_entity[hero.id] <= Hero.ATTACK_RANGE]

    def in_wind_area(self, hero):
        return [e for e in self.entities if type(e) is not Hero and e.distance_from_entity[hero.id] <= CastWind.RADIUS]


def main():
    # *** init game
    grid = Grid()
    grid.init_game()

    while True:
        # *** get inputs and init round
        grid.init_round()

        # *** Compute priorities
        for hero in grid.heroes:
            grid.play(hero)


main()