cig/cultist_war/main.py

import heapq
import sys
import time

debug = True

t0 = time.time()


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 Node(BaseClass):
    def __init__(self, pos, path=None):
        self.pos = pos
        self.path = path or []


class PathNode(tuple):
    def __new__(cls, x, y, parent=None):
        n = tuple.__new__(cls, (x, y))
        n.parent = parent
        n.cost = 0
        return n

    def __repr__(self):
        return f"<{self[0]}, {self[1]}, c:{self.cost}>"


class DiscoveryNode(tuple):
    def __new__(cls, x, y, cost=0, ancestors=None, matches=None):
        n = tuple.__new__(cls, (x, y))
        n.cost = cost
        n.ancestors = ancestors if ancestors is not None else []
        n.matches = matches if matches is not None else []
        return n

    def __repr__(self):
        return f"<{self[0]}, {self[1]}>"


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 ConversionStep:
    def __init__(self):
        self.pos = None
        self.candidates = []

    def __repr__(self):
        return f"<{self.pos}, c:{self.candidates}>"


class ConversionPath:
    def __init__(self):
        self.steps = []

    def __repr__(self):
        return f"<{self.steps}>"

    @classmethod
    def make_from_discovery_node(cls, node):
        nodes = node.ancestors + [node]
        path = cls()
        found = []

        for node in nodes:
            step = ConversionStep()
            step.pos = tuple(node)
            for m in node.matches:
                if m in found:
                    continue
                step.candidates.append(m)
                found.append(m)
            path.steps.append(step)
        return path

    def next_candidate(self):
        path = []
        for step in self.steps:
            path.append(step)
            if step.candidates:
                return path
        return None


class Player(BaseClass):
    def __init__(self, id_):
        self.id = id_


ME = Player(int(input()))  # Input gives the player id: 0 plays first
OPPONENT = Player(1 - ME.id)

PLAYERS_INDEX = {p.id: p for p in [ME, OPPONENT]}
PLAYERS_ORDER = sorted([ME, OPPONENT], key=lambda p: p.id)


class Threat(BaseClass):
    def __init__(self, unit, damages, pos, line):
        self.unit = unit
        self.damages = damages
        self.pos = pos
        self.line = line if line else []

        self.target = None
        self.fatal = False
        self.neutral = False

    def __repr__(self):
        return f"<Threat (unit: {self.unit.id}, damages={self.damages}, pos={self.pos}, target={self.target.id if self.target else None}, fatal={self.fatal}, line={self.line})>"

    def fatal_for(self, unit):
        return self.damages >= unit.hp


class Unit(BaseClass):
    TYPE_CULTIST = 0
    TYPE_CULT_LEADER = 1

    OWNER_0 = 0
    OWNER_1 = 1
    NO_OWNER = 2

    MAX_HP = 10
    SHOOTING_RANGE = 6
    SHOOTING_MAX_DAMAGE = 7

    def __init__(self, id_):
        self.id = id_
        self.hp = Unit.MAX_HP
        self.x = None
        self.y = None
        self.owner = None

        self.targets = []
        self.threaten_by = []
        self.has_been_shooted = False

    @property
    def pos(self):
        return self.x, self.y

    @property
    def owned(self):
        return self.owner == ME.id

    @property
    def opponent(self):
        return self.owner == OPPONENT.id

    @property
    def neutral(self):
        return self.owner == self.NO_OWNER


class CultLeader(Unit):
    pass


class Action(BaseClass):
    pass


class ActionWait(Action):
    def __repr__(self):
        return f"<ActionWait>"

    def exec(self):
        print("WAIT")


class ActionMove(Action):
    def __init__(self, unit, pos, message=''):
        self.unit = unit
        self.pos = pos
        self.message = message

    def __repr__(self):
        return f"<ActionMove: {self.unit.id} to {self.pos} ({self.message})>"

    def exec(self):
        print(f"{self.unit.id} MOVE {self.pos[0]} {self.pos[1]}")


class ActionShoot(Action):
    def __init__(self, unit, target, message=''):
        self.unit = unit
        self.target = target
        self.message = message

    def __repr__(self):
        return f"<ActionShoot: {self.unit.id} to {self.target.id} ({self.message})>"

    def exec(self):
        print(f"{self.unit.id} SHOOT {self.target.id}")


class ActionConvert(Action):
    def __init__(self, unit, target):
        self.unit = unit
        self.target = target

    def __repr__(self):
        return f"<ActionConvert: {self.unit.id} to {self.target.id}>"

    def exec(self):
        print(f"{self.unit.id} CONVERT {self.target.id}")


class Grid(BaseClass):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.round = 1

        self.cells = []
        self.obstacles = []
        self._neighbors = {}

        self.index = {}
        self.units = {}
        self.threats_on = {}
        self.max_threat = {}
        self.conversion_path = ConversionPath()
        self.ideal_conversion_path = ConversionPath()

        self.cult_leader = None
        self.opponent_cult_leader = None
        self.allied_cultists = []
        self.owned_units = []
        self.opponent_units = []
        self.opponent_cultists = []
        self.neutrals = []
        self.previous_hps = {}

    def pre_compute(self):
        self.cells = [(x, y) for x in range(self.width) for y in range(self.height)]

        for x, y in self.cells:
            self._neighbors[(x, y)] = [(xn, yn) for xn, yn in [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] if
                                       0 <= xn < self.width and 0 <= yn < self.height]

    def reinit_round(self):
        self.previous_hps = {u.id: u.hp for u in self.owned_units}
        self.units = {}
        self.threats_on = {pos: [] for pos in self.cells}
        self.max_threat = {pos: 0 for pos in self.cells}
        self.conversion_path = ConversionPath()
        self.ideal_conversion_path = ConversionPath()

    def update_unit(self, id_, type_, hp, x, y, owner):

        # quand le bresenham foire, histoire de "corriger le tir", on retient le coup pour en tenir compte
        has_been_shooted = False
        if id_ in self.previous_hps:
            if hp < self.previous_hps[id_]:
                has_been_shooted = True

        self.units[id_] = Unit(id_) if type_ != Unit.TYPE_CULT_LEADER else CultLeader(id_)
        unit = self.units[id_]
        unit.hp = hp
        unit.x = x
        unit.y = y
        unit.owner = owner
        unit.targets = []
        unit.threaten_by = []
        unit.has_been_shooted = has_been_shooted


    def update_index(self):
        self.index = {}
        self.cult_leader = None
        self.opponent_cult_leader = None
        self.allied_cultists = []
        self.owned_units = []
        self.opponent_units = []
        self.opponent_cultists = []
        self.neutrals = []

        for unit in self.units.values():
            self.index[(unit.x, unit.y)] = unit

            if unit.owner == ME.id:
                self.owned_units.append(unit)
                if type(unit) is CultLeader:
                    self.cult_leader = unit
                else:
                    self.allied_cultists.append(unit)
            elif unit.owner == OPPONENT.id:
                self.opponent_units.append(unit)
                if type(unit) is CultLeader:
                    self.opponent_cult_leader = unit
                else:
                    self.opponent_cultists.append(unit)
            else:
                self.neutrals.append(unit)

    def update_threat(self):

        sources = self.allied_cultists + self.opponent_cultists

        if self.opponent_cult_leader:
            for n in self.neighbors(*self.opponent_cult_leader.pos):
                if n in self.index and self.index[n].neutral:
                    sources.append(self.index[n])

        for u in sources:
            threat_zone = self.zone(u.pos, Unit.SHOOTING_RANGE)
            for pos in threat_zone:
                if pos in self.obstacles:
                    continue

                line_of_sight = self.line_of_sight(u.pos, pos)
                if not line_of_sight:
                    continue

                dist = self.manhattan(u.pos, pos)

                damages = u.SHOOTING_MAX_DAMAGE - dist
                threat = Threat(u, damages, pos, line_of_sight)

                self.threats_on[pos].append(threat)

                if not u.owned and self.max_threat[pos] < damages:
                    self.max_threat[pos] = damages

                if pos in self.index:
                    target = self.index[pos]
                    if target.owner == u.owner:
                        continue

                    threat.target = target
                    threat.fatal = damages >= target.hp
                    threat.neutral = u.neutral

                    u.targets.append(threat)
                    target.threaten_by.append(threat)

        # fallback pour compenser le bresenham inégal
        for a in self.owned_units:
            for t in a.threaten_by:
                if not t in a.targets:
                    threat = Threat(a, t.damages, a.pos, t.line[::-1])
                    threat.target = t.unit
                    threat.neutral = False
                    a.targets.append(threat)

    def compute_conversion_path(self):
        conversion_path = ConversionPath()
        ideal_conversion_path = ConversionPath()

        if self.cult_leader and self.neutrals:
            conversion_path = self.get_conversion_path(
                self.cult_leader,
                key=(lambda pos: pos in self.index and self.index[pos].neutral),
                moving_key=lambda pos: self.can_move_on(self.cult_leader, pos),
                limit=min(4, len(self.neutrals))
            )
            log(f"conversion : {conversion_path}")

            ideal_conversion_path = self.get_conversion_path(
                self.cult_leader,
                key=(lambda pos: pos in self.index and self.index[pos].neutral),
                moving_key=lambda pos: self.can_move_on(self.cult_leader, pos) or (pos in self.index and self.index[pos].owned),
                limit=min(4, len(self.neutrals))
            )
            log(f"ideal conversion : {ideal_conversion_path}")
        self.conversion_path = conversion_path
        self.ideal_conversion_path = ideal_conversion_path

    def update(self):
        self.update_index()
        self.update_threat()
        self.compute_conversion_path()

        # log(self.obstacles + [u.pos for u in self.allied_cultists])
        # log([n.pos for n in self.neutrals])

    def build_actions(self):
        actions = Queue()

        advantage = len(self.owned_units) > len(self.opponent_units)
        sure_advantage = len(self.owned_units) > (len(self.opponent_units) + len(self.neutrals))

        for u in self.owned_units:
            if u.threaten_by:
                log(f"Threats : {u.targets}")
                log(f"Threats : {u.threaten_by}")
            elif u.has_been_shooted:
                log(f"<!!!> {u.id} has been shooted by unknown threat!")

        # Leader take cover
        k0_protect_cult_leader = 25
        k_protect_threat_level = -5
        k_protect_worth_risk = 3
        k_cover_interest = -10

        if self.cult_leader:
            threat_level = self.max_threat[self.cult_leader.pos]

            # pas de menace apparente, mais le leader a reçu un tir depuis le tour précédent (pbm de bresenham)
            if not threat_level and self.cult_leader.has_been_shooted:
                log("<!!> leader seems not threaten but has been hurted!")
                threat_level = 10

            # une unité voisine peut être convertie, on laisse ça à l'action convert
            threats = [t
                       for t in self.cult_leader.threaten_by
                       if t.unit not in self.neighbors(*self.cult_leader.pos)]

            if threats or self.cult_leader.has_been_shooted:
                covers = [n for n in self.neighbors(*self.cult_leader.pos) if self.can_move_on(self.cult_leader, n)]

                for pos in covers:
                    interest = bool(self.conversion_path and self.conversion_path.steps and pos in [s.pos for s in
                                                                                                    self.conversion_path.steps])

                    priority = k0_protect_cult_leader
                    priority += k_protect_threat_level * (threat_level - self.max_threat[pos])
                    priority += k_cover_interest * interest
                    priority += k_protect_worth_risk * (self.cult_leader.hp - (threat_level + 1))

                    action = ActionMove(self.cult_leader, pos,
                                        f'take cover (current: {threat_level}, new: {self.max_threat[pos]})')
                    actions.put(priority, action)

        # Convert
        k0_convert = 15
        k_convert_number = -10
        k_convert_danger = 20
        k_convert_threat_on = 3
        k_convert_hurted = 1
        k_convert_neighbor_threat = -15
        k_convert_neighbor_opponent = -20
        k_convert_distance = 10

        if self.cult_leader:
            immediate_targets = [
                self.index[n] for n in self.neighbors(*self.cult_leader.pos)
                if n in self.index and self.index[n] not in self.owned_units and self.index[n] is not self.opponent_cult_leader
            ]
            for target in immediate_targets:
                priority = k0_convert
                priority += k_convert_neighbor_threat * (target.neutral and target in [t.unit for t in self.cult_leader.threaten_by])
                priority += k_convert_neighbor_opponent * target.opponent
                priority += k_convert_threat_on * max([t.damages for t in self.threats_on[target.pos] if t.unit.opponent], default=0)

                action = ActionConvert(self.cult_leader, target)
                actions.put(priority, action)

            # Go Convert
            if not immediate_targets and self.conversion_path:
                path = self.conversion_path.next_candidate()
                if path:
                    targets = [self.index[c] for c in path[-1].candidates]

                    priority = k0_convert
                    priority += k_convert_number * len(targets)
                    priority += k_convert_distance * len(path)
                    priority += k_convert_danger * sum([self.max_threat[s.pos] for s in path])

                    for target in targets:
                        priority += k_convert_hurted * (Unit.MAX_HP - target.hp)
                        priority += k_convert_threat_on * max([t.damages for t in self.threats_on[target.pos] if t.unit.opponent], default=0)

                    action = ActionMove(self.cult_leader, path[1].pos,
                                        f'go convert {",".join([str(t.id) for t in targets])}')
                    actions.put(priority, action)

        # Shoot opponent units
        k0_shoot = 0
        k_shoot_opponent_cultist = 6
        k_shoot_opponent_leader = 6 if self.neutrals else 10
        k_shoot_fatal = -5
        k_shoot_kill_before_he_kills = -5
        k_shoot_sacrifice = 30
        k0_runaway = 10
        k_runaway_threat = 10

        for a in self.allied_cultists:
            if not a.targets:
                continue

            for threat in a.targets:
                priority = k0_shoot

                if threat.target.neutral:
                    continue

                # Il est probable que l'unité se fera tirer dessus par l'ennemi le plus proche: quel résultat?
                deadly_threaten_by = [t for t in a.threaten_by if t.fatal]
                if not a.threaten_by and a.has_been_shooted:
                    log(f"<!!> unit {a.id} seems not threaten but has been hurted!")
                    deadly_threaten_by.append(Threat(self.opponent_cult_leader, 10, a.pos, []))

                if not a.threaten_by and a.has_been_shooted:
                    deadly_threaten_by.append(Threat(self.opponent_cult_leader, 10, a.pos, []))

                if deadly_threaten_by and not threat.fatal:
                    # run away! (si possible)
                    covers = [n for n in self.neighbors(*a.pos) if self.can_move_on(a, n)]

                    if covers:
                        for cover in covers:
                            threats_on_cover = [t for t in self.threats_on[cover] if not t.unit.owned]
                            if not any(t.fatal_for(a) for t in threats_on_cover):
                                action = ActionMove(a, cover, f'run away!')
                                priority += k0_runaway
                                priority += k_runaway_threat * self.max_threat[cover]
                                actions.put(priority, action)
                                continue

                    log(f'<!> {a.id} seems lost')

                elif threat.fatal and deadly_threaten_by:
                    # l'unité peut tuer la cible, mais sera probablement tuée par une autre unité ennemie
                    priority += k_shoot_sacrifice

                if not threat.fatal:
                    k = k_shoot_opponent_leader if threat.target is self.opponent_cult_leader else k_shoot_opponent_cultist
                    priority += k * len(threat.line)
                else:
                    priority += k_shoot_fatal

                # peut tuer un adversaire avant qu'il ne tue un allié
                priority += k_shoot_kill_before_he_kills * any(t.fatal and t.target is not a for t in threat.target.targets)

                action = ActionShoot(a, threat.target,
                                     f'shoot from {a.pos} (damages: {threat.damages}, pos: {threat.pos}, target: {threat.target}, fatal: {threat.fatal}, line: {threat.line})')

                actions.put(priority, action)

        # Intercept
        k0_intercept = 20
        position_hp_min = 5
        k_intercept_diff = 3

        for a in self.allied_cultists:
            if a.hp < position_hp_min:
                continue

            for o in (u for u in self.owned_units if u is not a):
                neighbors = self.neighbors(*a.pos)

                for threat in o.threaten_by:
                    if threat.fatal and not threat.fatal_for(a):
                        for n in neighbors:
                            if n in threat.line:
                                action = ActionMove(a, n, f'intercept {threat}')

                                priority = k0_intercept
                                priority = k_intercept_diff * (a.hp - o.hp)

                                actions.put(priority, action)

        # Position: go to front line
        k0_position = 50
        k_position_advantage = 40
        k_position_distance = 3  # on veut privilégier les plus près, mais pas non plus décourager ceux de l'arrière...

        for a in self.allied_cultists:
            if a.hp < position_hp_min:
                continue

            if self.max_threat[a.pos]:
                # unit already under threat, let shoot action manage this
                continue

            if any(self.max_threat[n] for n in self.neighbors(*a.pos)):
                # unit already on frontline
                continue

            # l'unité semble en sécurité, go to front-line
            nearest_frontline = self.discover(a, key=lambda x: self.can_move_on(a, x) and self.max_threat[x] >= 1,
                                              limit=1)
            # log(f"{a.id} - {nearest_frontline}")
            if not nearest_frontline:
                log(f"<!> {a.id} can not join nearest frontline")
                continue

            path, target = nearest_frontline[0]
            if path:
                # log(f"{a.id} - {path} - {target}")
                priority = k0_position
                priority += k_position_distance * len(path)
                priority += k_position_advantage * advantage

                action = ActionMove(a, path[0], f'go to frontline {target} by {path}')
                actions.put(priority, action)

        # Move out
        k0_move_out = 20
        k_move_out_gain = -3
        k_move_out_still_in_path_but_later = 5
        k_move_out_default_gain = 4

        if self.cult_leader:
            actual_path = [s.pos for s in (self.conversion_path.next_candidate() or [])]
            ideal_path = [s.pos for s in (self.ideal_conversion_path.next_candidate() or [])]

            if ideal_path:
                for a in self.allied_cultists:
                    if a.pos in ideal_path:
                        gain = len(actual_path) - len(ideal_path) if actual_path else k_move_out_default_gain

                        if gain > 0:
                            for n in self.neighbors(*a.pos):
                                if not self.can_move_on(a, n):
                                    continue

                                priority = k0_move_out
                                still_in_the_way = (n in ideal_path)

                                if still_in_the_way:
                                    if ideal_path.index(n) > ideal_path.index(a.pos):
                                        priority += k_move_out_still_in_path_but_later
                                    else:
                                        continue

                                priority += k_move_out_gain * gain

                                action = ActionMove(a, n, f'move out of the way (gain: {gain}, in the way: {still_in_the_way})')
                                actions.put(priority, action)


        # Shoot neutral units:
        k_shoot_dangerous_neutral_threat = 3
        k_shoot_dangerous_neutral_distance = 8
        dangerous_neutral_distance_limit = 3

        if self.opponent_cult_leader:

            discovered_by_opponent = self.discover(self.opponent_cult_leader,
                                                   key=lambda x: x in self.index and self.index[x].neutral, limit=3)
            neutrals_threaten = {}
            for path, target_pos in discovered_by_opponent:
                if len(path) > dangerous_neutral_distance_limit:
                    continue
                if target_pos not in neutrals_threaten or neutrals_threaten[target_pos] < len(path):
                    neutrals_threaten[target_pos] = len(path)

            threaten_neutrals_from_leader = {}
            if self.cult_leader:
                discovered_by_leader = self.discover(self.cult_leader, key=lambda x: x in neutrals_threaten, limit=3)
                for path, target_pos in discovered_by_leader:
                    if target_pos not in threaten_neutrals_from_leader or threaten_neutrals_from_leader[
                        target_pos] < len(path):
                        threaten_neutrals_from_leader[target_pos] = len(path)

            # log(f"Nearest from opp. leader: {neutrals_threaten}")
            # log(f"Nearest from own  leader: {threaten_neutrals_from_leader}")

            lost_causes = {}
            for target, dist in neutrals_threaten.items():
                if target not in threaten_neutrals_from_leader or threaten_neutrals_from_leader[target] <= \
                        neutrals_threaten[target]:
                    lost_causes[target] = (dist - threaten_neutrals_from_leader.get(target,
                                                                                    0))  # la distance retenue est la différence entre la distance entre la cible
                    # et le leader ennemi, et celle entre la cible et le leader allié

            for a in self.allied_cultists:
                for pos, dist in lost_causes.items():
                    if pos not in self.index:
                        log(f"<!> {pos} is not in the index!!")
                        continue

                    u = self.index[pos]

                    line_of_sight = self.line_of_sight(a.pos, u.pos)
                    shooting_distance = len(line_of_sight)
                    if not shooting_distance:
                        continue

                    if shooting_distance <= u.SHOOTING_RANGE:
                        # la cible est à portée
                        action = ActionShoot(a, u, f"peace keeping, shoot from {a.pos} ({line_of_sight})")

                        priority = k_shoot_dangerous_neutral_distance * shooting_distance
                        priority += k_shoot_dangerous_neutral_threat * dist
                        actions.put(priority, action)

        # Last hope: take risks
        if not advantage and not actions:
            k0_last_chance = 80
            k_last_chance_danger = 5
            last_chance_hp_min = 5

            for a in self.allied_cultists:
                if a.hp < last_chance_hp_min:
                    continue

                for n in self.neighbors(*a.pos):
                    if not self.max_threat[n]:
                        continue

                    ongoing_fights = []
                    for u in self.opponent_cultists:
                        line_of_sight = self.line_of_sight(u.pos, n)
                        if not line_of_sight:
                            continue

                        dist = self.manhattan(u.pos, n)
                        if dist <= u.SHOOTING_RANGE:
                            damages = u.SHOOTING_MAX_DAMAGE - dist

                            ongoing_fights.append((u, damages))

                    if any(d >= a.hp for _, d in ongoing_fights):
                        # c'est du suicide: sortir revient à se prendre un coup fatal
                        continue

                    action = ActionMove(a, n, f"last hope, moving")

                    priority = k0_last_chance
                    priority += k_last_chance_danger * max([d for _, d in ongoing_fights], default=0)
                    actions.put(priority, action)

        # TODO: prévoir une action intercept, où une unité alliée se place sur le chemin d'une menace fatale, si l'unité a suffisamment de pv pour affronter la menace sans mourir
        # TODO: ne pas aller convertir les neutres qui sont sous le feu ennemi, ou au moins baisser leur priorité (surtout s'ils sont la seule chose entre le leader et les ennemis);
        # TODO: augmenter la prise de risque pour la conversion, parfois ça peut changer le résultat si le leader a tous ses pvs
        # TODO: cf Capture d’écran 2022-09-24 014757.png -> même si pas de ligne entre deux pos, la position peut se retrouver sur une ligne de mire avec une autre cible... snif
        # TODO: l'algo actuel va privilégier un tir sur un neutre lointain voisin du leader ennemi, plutôt que sur un ennemi en train de nous tirer dessus
        # TODO: toujours le pbm des tirs supposés possibles mais non, ça coince quand le tir est en diagonale entre deux obstables; et autres pbm avec cet algo :(
        # TODO: abandonner l'idée d'aller convertir si la menace est mortelle...

        return actions

    def in_grid(self, pos):
        return 0 <= pos[0] < self.width and 0 <= pos[1] < self.height

    def can_see_trough(self, pos):
        return self.in_grid(pos) and pos not in self.obstacles and pos not in self.index

    def can_move_on(self, unit, pos):
        return self.in_grid(pos) and pos not in self.obstacles and (pos not in self.index or self.index[pos] is unit)

    def can_discover(self, pos):
        return self.in_grid(pos) and pos not in self.obstacles

    def moving_cost(self, unit, pos):
        if not self.can_move_on(unit, pos):
            return -1
        return 1 + self.max_threat[pos]

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

    def neighbors(self, x, y):
        return self._neighbors[(x, y)]

    def zone(self, pos, radius):
        x0, y0 = pos
        zone = []
        for x in range(max(x0 - radius, 0), min(x0 + radius, self.width)):
            for y in range(max(y0 - radius, 0), min(y0 + radius, self.height)):
                dist = self.manhattan(pos, (x, y))
                if dist <= radius:
                    zone.append((x, y))
        return zone

    @classmethod
    def line(cls, start, target):
        """
        adapted from https://github.com/fragkakis/bresenham/blob/master/src/main/java/org/fragkakis/Bresenham.java
        if strict is true, None is return if an obstacle interrupted the line; else a partial line is returned (from start to obstacle)
        """
        line = []

        x0, y0 = start
        x1, y1 = target

        reversed = y0 > y1

        if reversed:
            # on fait toujours de bas en haut, du coup on inverse au besoin
            x0, y0, x1, y1 = x1, y1, x0, y0

        dx = abs(x1 - x0)
        dy = abs(y1 - y0)

        sx = 1 if x0 < x1 else -1
        sy = 1 if y0 < y1 else -1

        err = dx - dy
        x, y = x0, y0

        while 1:
            e2 = 2 * err
            if e2 > -1 * dy:
                err -= dy
                x += sx

            if e2 < dx:
                err += dx
                y += sy

            if x == x1 and y == y1:
                break

            line.append((x, y))

        if reversed:
            line = line[::-1]

        line = [start] + line + [target]

        return line

    def line_of_sight(self, from_, to_):
        line = self.line(from_, to_)[1:]
        return line if all(self.can_see_trough(c) for c in line[:-1]) else []

    def shooting_distance(self, from_, to_):
        return len(self.line_of_sight(from_, to_))

    def path(self, unit, target):
        nodes = Queue()
        its, break_on = 0, 400

        origin = PathNode(*unit.pos)
        nodes.put(0, origin)

        while nodes:
            current = nodes.get()

            if current == target:
                path = []
                previous = current
                while previous:
                    if previous != unit.pos:
                        path.insert(0, previous)
                    previous = previous.parent
                return path

            neighbors = self.neighbors(*current)

            for x, y in neighbors:
                its += 1
                if its > break_on:
                    log("<!> pathfinding broken")
                    return None

                if (x, y) == current.parent:
                    continue

                if not self.can_move_on(unit, (x, y)):
                    continue

                moving_cost = self.moving_cost(unit, (x, y))

                cost = current.cost + moving_cost
                priority = cost + 10 * Grid.manhattan((x, y), target)

                node = PathNode(x, y, current)
                node.cost = cost
                nodes.put(priority, node)

        return None

    def discover(self, unit, key, limit=5):
        paths = []

        nodes = []
        its, break_on = 0, 2000
        origin = DiscoveryNode(*unit.pos)

        nodes.append(origin)

        while nodes:
            current = nodes.pop(0)  # l'ordre est important, pour que les premiers indexés soient les premiers analysés

            neighbors = self.neighbors(*current)

            for pos in neighbors:
                its += 1
                if its > break_on:
                    log(f"<!> discovery broke, {len(paths)} results")
                    return paths

                if current != unit.pos and key(pos):
                    # TODO: actuellement, l'algo pourra retourner x chemins différents vers la même cible
                    #       il faudrait retourner les trois meilleurs chemins vers x cibles (selon 'limit')
                    path = current.ancestors[1:] + [current]
                    paths.append((path, pos))

                    if len(paths) >= limit:
                        return paths
                    continue

                if pos in current.ancestors:
                    continue

                if not self.can_move_on(unit, pos):
                    continue

                node = DiscoveryNode(*pos, 0, current.ancestors + [current])
                nodes.append(node)
        return paths

    def get_conversion_path(self, unit, key, moving_key, limit=5):
        """ essaies de trouver le meilleur chemin pour relier des cases dont au moins une voisine valide
            la condition 'key' (dans la limite de 'limit')"""
        nodes = Queue()
        winners = Queue()
        its, break_on = 0, 1000
        origin = DiscoveryNode(*unit.pos)

        abandon_at = 120  # number of paths explored

        nodes.put(0, origin)

        for n in self.neighbors(*unit.pos):
            if key(n):
                origin.matches.append(n)

        while nodes:
            its += 1
            if its > break_on:
                log(f"<!> get_conversion_path broke")
                break

            if len(nodes.items) > abandon_at:
                log("> get_conversion_path early exit")
                break

            current = nodes.get()

            for pos in self.neighbors(*current):
                if not moving_key(pos):
                    continue

                moving_cost = 1 + self.max_threat[pos]

                matches = []
                for n in self.neighbors(*pos):
                    if n not in current.matches and key(n):
                        matches.append(n)

                cost = current.cost + moving_cost
                priority = 1000 * cost - (2000 * (len(current.matches) + len(matches)))
                priority += 100 * len(
                    [a for a in current.ancestors if a == pos])  # décourage de revenir à une case visitée

                node = DiscoveryNode(
                    pos[0],
                    pos[1],
                    cost,
                    current.ancestors + [current],
                    current.matches + matches
                )

                if matches:
                    winners.put(40 * node.cost - 100 * len(node.matches), node)

                nodes.put(priority, node)

            if len(current.matches) >= limit or its > break_on:
                break

        try:
            best_node = winners.get()
        except IndexError:
            if nodes:
                best_node = nodes.get()
            else:
                best_node = origin
        return ConversionPath.make_from_discovery_node(best_node)

    def _repr_cell(self, pos):
        return f"{self.max_threat[pos]}"
        # return f"{self.control[pos]}/{self.max_threat[pos]}"
        # return self.heat_map[pos]

        if pos in self.obstacles:
            return "X"

        unit = self.index.get(pos, None)
        if type(unit) is CultLeader:
            return "C"
        elif unit is None:
            return "."
        else:
            return "U"

    def graph(self):
        return "\n".join(
            ["|".join([str(self._repr_cell((x, y))) for x in range(self.width)]) for y in range(self.height)])


# Create grid
GRID = Grid(*[int(i) for i in input().split()])
obstacles_input = [input() for y in range(GRID.height)]
GRID.obstacles = [(x, y) for y, row in enumerate(obstacles_input) for x, val in enumerate(row) if val == 'x']

GRID.pre_compute()

while 1:
    GRID.reinit_round()
    for _ in range(int(input())):
        GRID.update_unit(*[int(j) for j in input().split()])

    log(f"start round {GRID.round}")
    GRID.update()

    actions = GRID.build_actions()

    # print("\n" + GRID.graph(), file=sys.stderr)

    for action in actions.items:
        log(f"* {action}")

    try:
        action = actions.get()
    except IndexError:
        log("no action...")
        action = ActionWait()

    log(f"exec : {action}")

    action.exec()
    GRID.round += 1