"""Craftax code policy for fixture and procedural (48x48) worlds."""

from __future__ import annotations

from collections import deque
from typing import Any


_DIRS = (("right", 1, 0), ("down", 0, 1), ("left", -1, 0), ("up", 0, -1))
_EXPLORE_DIRS = ("right", "down", "left", "up")
_PASSABLE = {".", ">", "<", "P", ",", "!"}
_WOOD_TILES = {"tree", "fire_tree", "ice_shrub"}
_PLACEABLE = {"grass", "sand", "path", "floor", "dirt"}
_LEVEL_CLEAR_KILLS = 8
_HOSTILE_KINDS = {
    "zombie",
    "skeleton",
    "gnome_warrior",
    "gnome_archer",
    "orc_solider",
    "orc_mage",
    "lizard",
    "kobold",
    "knight",
    "archer",
    "troll",
    "deep_thing",
    "pigman",
    "fire_elemental",
    "frost_troll",
    "ice_elemental",
}


def choose_actions(
    *,
    observation_text: str,
    session: dict[str, Any],
    valid_actions: list[str],
    engine: Any = None,
    readout: dict[str, Any],
    seed: int,
    ply: int,
) -> dict[str, Any]:
    obs = readout["observation"]
    inv = obs["inventory"]
    achievements = set(obs.get("achievements", []))
    local_map = obs["local_map"]
    valid = set(valid_actions)
    front = obs["player"]["front_tile"]
    front_char = _front_char(obs, local_map)
    front_entity = _entity_kind_at_front(obs)
    table_near = _nearby(local_map, "A")
    furnace_near = _nearby(local_map, "F")
    table_known = table_near or "place_table" in achievements
    pickaxe = int(inv.get("pickaxe", 0))
    sword = int(inv.get("sword", 0))
    wood = int(inv.get("wood", 0))
    stone = int(inv.get("stone", 0))
    phase = _phase(achievements, pickaxe, sword, ply, obs)
    pos_tuple = tuple(_player_pos(obs))
    current_level = int(obs["player"]["level"])
    if session.get("tracked_level") != current_level:
        session["tracked_level"] = current_level
        session["visited"] = {pos_tuple}
    if session.get("last_pos") == pos_tuple:
        session["stuck"] = int(session.get("stuck", 0)) + 1
    else:
        session["stuck"] = 0
    session["last_pos"] = list(pos_tuple)
    visited = session.setdefault("visited", set())
    visited.add(pos_tuple)

    if table_near:
        session["table_pos"] = _player_pos(obs)
    if furnace_near:
        session["furnace_pos"] = _player_pos(obs)

    if front_entity in _HOSTILE_KINDS and sword >= 1 and phase in {"defeat_zombie", "descend", "dungeon", "iron_pick"}:
        return _decision("do", f"attack {front_entity}")

    if _should_harvest(phase, front, front_entity, pickaxe, achievements):
        return _decision("do", f"harvest {front}")

    if front == "chest":
        return _decision("do", "open chest")
    if front in {"water", "fountain"} and "collect_drink" not in achievements:
        return _decision("do", "collect drink")
    if front == "ripe_plant" and "eat_plant" not in achievements:
        return _decision("do", "eat ripe plant")

    if _passive_food_pending(achievements) and phase == "side_crafts" and "place_furnace" in achievements:
        for passive_kind, achievement in (("bat", "eat_bat"), ("snail", "eat_snail")):
            if achievement not in achievements:
                routed = _go_mob_global(readout, valid, session, kind=passive_kind, reason=f"opportunist {passive_kind}")
                if routed:
                    return routed
        if "eat_plant" not in achievements and _has_tile_char(readout, "P"):
            routed = _seek_tile(readout, valid, session, "P", "seek ripe plant", stand_on=True)
            if routed:
                return routed

    if front_entity in {"cow", "bat", "snail"} and (
        phase in {"eat_cow", "side_crafts", "iron_pick", "descend", "dungeon"}
        or _passive_food_pending(achievements, front_entity)
    ):
        return _decision("do", f"interact with {front_entity}")

    if int(inv.get("torches", 0)) >= 1 and "place_torch" not in achievements and "place_torch" in valid:
        if _can_take(engine, "place_torch"):
            return _decision("place_torch", "place torch")
        setup = _setup_for_action(engine, valid, "place_torch")
        if setup:
            return _decision(setup, "setup torch placement")

    if phase == "wood_pickaxe":
        if table_near and wood >= 1 and "make_wood_pickaxe" in valid:
            return _decision("make_wood_pickaxe", "craft wood pickaxe")
        if table_known and not table_near and wood >= 1:
            routed = _return_to_table(readout, valid, session)
            if routed:
                return routed
        if not table_known and wood >= 3 and "place_table" in valid and _can_take(engine, "place_table"):
            return _decision("place_table", "place crafting table")
        if not table_known and wood >= 3 and "place_table" in valid:
            setup = _setup_for_action(engine, valid, "place_table")
            if setup:
                return _decision(setup, "setup table placement")
        if wood < (1 if table_known else 3):
            routed = _seek_tile(readout, valid, session, "T", "seek wood")
            if routed:
                return routed
        if not table_known:
            routed = _seek_placement_adjacent(readout, valid, session)
            if routed:
                return routed
        routed = _return_to_table(readout, valid, session)
        if routed:
            return routed
        return _explore(readout, valid, session, "wood pickaxe explore")

    if phase == "wood_sword":
        if table_near and wood >= 1 and "make_wood_sword" in valid:
            return _decision("make_wood_sword", "craft wood sword")
        if wood < 1:
            routed = _seek_tile(readout, valid, session, "T", "seek wood for sword")
            if routed:
                return routed
        routed = _return_to_table(readout, valid, session)
        if routed:
            return routed
        return _explore(readout, valid, session, "wood sword explore")

    if phase == "stone_pickaxe":
        if table_near and wood >= 1 and stone >= 1 and "make_stone_pickaxe" in valid:
            return _decision("make_stone_pickaxe", "craft stone pickaxe")
        if stone < 1:
            routed = _seek_tile(readout, valid, session, "S^", "seek stone", tile_only=True)
            if routed:
                return routed
        if wood < 1:
            routed = _seek_tile(readout, valid, session, "T", "seek wood")
            if routed:
                return routed
        routed = _return_to_table(readout, valid, session)
        if routed:
            return routed
        return _explore(readout, valid, session, "stone pickaxe explore")

    if phase == "eat_cow":
        routed = _go_mob_global(readout, valid, session, kind="cow", reason="seek cow")
        if routed:
            return routed
        routed = _go_entity(readout, valid, session, "cow", "seek cow")
        if routed:
            return routed
        return _frontier_explore(readout, valid, session, "find cow") or _explore(
            readout, valid, session, "find cow"
        )

    if phase == "defeat_zombie":
        routed = _go_mob_global(readout, valid, session, kind="zombie", reason="seek zombie")
        if routed:
            return routed
        routed = _go_entity(readout, valid, session, "zombie", "seek zombie", avoid_hostiles=False)
        if routed:
            return routed
        routed = _seek_tile(readout, valid, session, "Z", "seek zombie on map", avoid_hostiles=False)
        if routed:
            return routed
        return _frontier_explore(readout, valid, session, "find zombie") or _explore(
            readout, valid, session, "find zombie"
        )

    if phase == "side_crafts":
        if "place_furnace" not in achievements:
            if stone >= 1 and "place_furnace" in valid and _can_take(engine, "place_furnace"):
                return _decision("place_furnace", "place furnace")
            if stone >= 1 and "place_furnace" in valid:
                setup = _setup_for_action(engine, valid, "place_furnace")
                if setup:
                    return _decision(setup, "setup furnace placement")
            if stone >= 1:
                routed = _seek_placement_adjacent(readout, valid, session)
                if routed:
                    return routed
            if stone < 1 and pickaxe >= 1:
                routed = _seek_tile(readout, valid, session, "S^", "seek stone for furnace", tile_only=True)
                if routed:
                    return routed
        elif "collect_coal" not in achievements and pickaxe >= 1:
            routed = _seek_tile(readout, valid, session, "C", "seek coal", tile_only=True)
            if routed:
                return routed
        elif "collect_iron" not in achievements and pickaxe >= 2:
            routed = _seek_tile(readout, valid, session, "I", "seek iron", tile_only=True)
            if routed:
                return routed
        if _side_crafts_core_done(achievements):
            wants_torch = "make_torch" not in achievements and int(inv.get("coal", 0)) >= 1
            wants_arrow = "make_arrow" not in achievements
            if (wants_torch or wants_arrow) and (wood >= 1 or _trees_visible(readout)):
                if wood < 1:
                    routed = _seek_tile(readout, valid, session, "T", "seek wood for crafts")
                    if routed:
                        return routed
                if wants_arrow and stone < 1 and pickaxe >= 1:
                    routed = _seek_tile(readout, valid, session, "S^", "seek stone for arrow", tile_only=True)
                    if routed:
                        return routed
                if not table_near:
                    routed = _return_to_table(readout, valid, session)
                    if routed:
                        return routed
                if table_near and wants_torch and "make_torch" in valid:
                    return _decision("make_torch", "craft torch")
                if table_near and wants_arrow and "make_arrow" in valid:
                    return _decision("make_arrow", "craft arrows")
            if table_near and furnace_near and pickaxe < 3 and int(inv.get("iron", 0)) >= 1 and int(inv.get("coal", 0)) >= 1 and wood >= 1 and stone >= 1 and "make_iron_pickaxe" in valid:
                return _decision("make_iron_pickaxe", "craft iron pickaxe")
            if table_near and wood >= 1 and stone >= 1 and sword < 2 and "make_stone_sword" in valid and "make_stone_sword" not in achievements:
                return _decision("make_stone_sword", "craft stone sword")
        if not _side_crafts_core_done(achievements):
            if pickaxe >= 2 and int(inv.get("coal", 0)) < 1 and "place_furnace" in achievements:
                routed = _seek_tile(readout, valid, session, "C", "seek coal early", tile_only=True)
                if routed:
                    return routed
            if pickaxe >= 2 and int(inv.get("iron", 0)) < 1 and "place_furnace" in achievements:
                routed = _seek_tile(readout, valid, session, "I", "seek iron early", tile_only=True)
                if routed:
                    return routed
            routed = _frontier_explore(readout, valid, session, "seek side craft resources")
            if routed:
                return routed
            routed = _explore(readout, valid, session, "side craft explore")
            if routed:
                return routed

    if phase == "iron_pick":
        routed = _pursue_iron_pickaxe(readout, valid, session, inv, achievements, pickaxe, table_near, furnace_near)
        if routed:
            return routed
        return _frontier_explore(readout, valid, session, "iron pick prep") or _explore(
            readout, valid, session, "iron pick prep"
        )

    if phase == "descend":
        routed = _attempt_descend(readout, valid, session, engine, obs)
        if routed:
            return routed

    if phase == "dungeon":
        routed = _pursue_dungeon_floor(readout, valid, session, engine, obs, inv, achievements, pickaxe, sword, table_near, furnace_near)
        if routed:
            return routed

    if int(inv.get("sapling", 0)) >= 1 and "place_plant" not in achievements and front == "grass" and "place_plant" in valid:
        return _decision("place_plant", "plant sapling")
    if pickaxe >= 2 and front == "grass" and "collect_sapling" not in achievements:
        return _decision("do", "roll grass for sapling")

    progress = _best_sim_action(engine, valid)
    if progress:
        return _decision(progress, "sim progress")
    routed = _seek_tile(readout, valid, session, "TASCIHDrs>HF", "explore resources", tile_only=True)
    if routed:
        return routed
    return _explore(readout, valid, session, "explore")


def _monsters_killed_on_level(obs: dict[str, Any]) -> int:
    floor_state = obs.get("floor_state") or {}
    killed = floor_state.get("monsters_killed") or []
    level = int(obs["player"]["level"])
    if level < len(killed):
        return int(killed[level])
    return 0


def _level_is_cleared(obs: dict[str, Any]) -> bool:
    return _monsters_killed_on_level(obs) >= _LEVEL_CLEAR_KILLS


def _mobs_on_level(
    readout: dict[str, Any],
    *,
    kind: str | None = None,
    mob_class: str | None = None,
) -> list[tuple[int, int]]:
    obs = readout["observation"]
    level = int(obs["player"]["level"])
    positions: list[tuple[int, int]] = []
    mob_state = obs.get("mob_state") or {}
    for group in mob_state.values():
        if not isinstance(group, list):
            continue
        for entity in group:
            if not entity.get("mask", True):
                continue
            if int(entity.get("level", 0)) != level:
                continue
            if kind is not None and str(entity.get("kind")) != kind:
                continue
            if mob_class is not None and str(entity.get("class")) != mob_class:
                continue
            pos = entity.get("pos")
            if isinstance(pos, list) and len(pos) == 2:
                positions.append((int(pos[0]), int(pos[1])))
    return positions


def _go_mob_global(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    *,
    kind: str | None = None,
    mob_class: str | None = None,
    reason: str,
) -> dict[str, Any] | None:
    obs = readout["observation"]
    start = tuple(_player_pos(obs))
    lines = _ascii_lines(readout)
    best_route: list[str] = []
    best_dist = 10**9
    for target in _mobs_on_level(readout, kind=kind, mob_class=mob_class):
        routed = _route_to_adjacent_pos(lines, start, target, set())
        if not routed:
            continue
        dist = _manhattan(start, target)
        if dist < best_dist:
            best_dist = dist
            best_route = routed
    action = _first_valid(best_route, valid)
    if not action:
        return None
    route = _valid_prefix(best_route, valid)
    session["last_action"] = route[0]
    return _decision_actions(route, reason)


def _hunt_level_mobs(readout: dict[str, Any], valid: set[str], session: dict[str, Any]) -> dict[str, Any] | None:
    obs = readout["observation"]
    level = int(obs["player"]["level"])
    kinds = (
        "skeleton",
        "zombie",
        "gnome_warrior",
        "gnome_archer",
        "orc_solider",
        "orc_mage",
        "kobold",
        "archer",
        "lizard",
        "knight",
        "troll",
        "pigman",
        "fire_elemental",
        "frost_troll",
        "ice_elemental",
        "deep_thing",
    )
    if level >= 6:
        kinds = (
            "frost_troll",
            "ice_elemental",
            "deep_thing",
            "troll",
            "knight",
            "skeleton",
            "zombie",
            "gnome_warrior",
            "gnome_archer",
            "orc_solider",
            "orc_mage",
            "kobold",
            "archer",
            "lizard",
            "pigman",
            "fire_elemental",
        )
    for kind in kinds:
        routed = _go_mob_global(readout, valid, session, kind=kind, reason=f"hunt {kind}")
        if routed:
            return routed
    return _go_mob_global(readout, valid, session, mob_class="melee", reason="hunt melee mob")


def _passive_mob_pending(achievements: set[str]) -> bool:
    return "eat_bat" not in achievements or "eat_snail" not in achievements


def _passive_food_pending(achievements: set[str], front_entity: str | None = None) -> bool:
    pending = {
        "bat": "eat_bat" not in achievements,
        "snail": "eat_snail" not in achievements,
        "cow": "eat_cow" not in achievements,
    }
    if front_entity is not None:
        return pending.get(front_entity, False)
    return pending["bat"] or pending["snail"] or "eat_plant" not in achievements


def _pursue_passive_food(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    achievements: set[str],
) -> dict[str, Any] | None:
    for passive_kind, achievement in (("bat", "eat_bat"), ("snail", "eat_snail")):
        if achievement not in achievements:
            routed = _go_mob_global(readout, valid, session, kind=passive_kind, reason=f"seek {passive_kind}")
            if routed:
                return routed
            routed = _go_entity(readout, valid, session, passive_kind, f"seek {passive_kind}")
            if routed:
                return routed
    if "eat_plant" not in achievements and _has_tile_char(readout, "P"):
        routed = _seek_tile(readout, valid, session, "P", "seek ripe plant", stand_on=True)
        if routed:
            return routed
    return _frontier_explore(readout, valid, session, "seek passive food") or _explore(
        readout, valid, session, "seek passive food"
    )


def _ensure_dungeon_stations(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    engine: Any,
    inv: dict[str, Any],
    achievements: set[str],
    table_near: bool,
    furnace_near: bool,
) -> dict[str, Any] | None:
    table_known = table_near or "place_table" in achievements
    furnace_known = furnace_near or "place_furnace" in achievements
    if not table_known and int(inv.get("wood", 0)) >= 3 and "place_table" in valid and _can_take(engine, "place_table"):
        return _decision("place_table", "place dungeon table")
    if not table_known and int(inv.get("wood", 0)) >= 3 and "place_table" in valid:
        setup = _setup_for_action(engine, valid, "place_table")
        if setup:
            return _decision(setup, "setup dungeon table")
    if table_known and not furnace_known and int(inv.get("stone", 0)) >= 1 and "place_furnace" in valid and _can_take(engine, "place_furnace"):
        return _decision("place_furnace", "place dungeon furnace")
    if table_known and not furnace_known and int(inv.get("stone", 0)) >= 1 and "place_furnace" in valid:
        setup = _setup_for_action(engine, valid, "place_furnace")
        if setup:
            return _decision(setup, "setup dungeon furnace")
    if not table_known and int(inv.get("wood", 0)) >= 3:
        routed = _seek_placement_adjacent(readout, valid, session)
        if routed:
            return routed
    return None


def _iron_pick_ready(achievements: set[str], pickaxe: int) -> bool:
    return pickaxe >= 3 or "make_iron_pickaxe" in achievements


def _iron_pick_resources_ready(inv: dict[str, Any]) -> bool:
    return (
        int(inv.get("iron", 0)) >= 1
        and int(inv.get("coal", 0)) >= 1
        and int(inv.get("wood", 0)) >= 1
        and int(inv.get("stone", 0)) >= 1
    )


def _return_to_crafting_station(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
) -> dict[str, Any] | None:
    furnace_pos = session.get("furnace_pos")
    if isinstance(furnace_pos, list) and len(furnace_pos) == 2:
        routed = _go_pos(readout, valid, session, (int(furnace_pos[0]), int(furnace_pos[1])), "return to furnace")
        if routed:
            return routed
    if _has_tile_char(readout, "F"):
        routed = _go(readout, valid, session, "F", "return to furnace")
        if routed:
            return routed
    return _return_to_table(readout, valid, session)


def _pursue_iron_pickaxe(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    inv: dict[str, Any],
    achievements: set[str],
    pickaxe: int,
    table_near: bool,
    furnace_near: bool,
) -> dict[str, Any] | None:
    if _iron_pick_ready(achievements, pickaxe):
        return None
    if table_near and furnace_near and _iron_pick_resources_ready(inv) and "make_iron_pickaxe" in valid:
        return _decision("make_iron_pickaxe", "craft iron pickaxe")
    if _iron_pick_resources_ready(inv):
        routed = _return_to_crafting_station(readout, valid, session)
        if routed:
            return routed
    if int(inv.get("coal", 0)) < 1 and pickaxe >= 1:
        routed = _seek_tile(readout, valid, session, "C", "seek coal for iron pick", tile_only=True)
        if routed:
            return routed
    if int(inv.get("iron", 0)) < 1 and pickaxe >= 2:
        routed = _seek_tile(readout, valid, session, "I", "seek iron for iron pick", tile_only=True)
        if routed:
            return routed
    if "collect_coal" not in achievements and pickaxe >= 1:
        routed = _seek_tile(readout, valid, session, "C", "seek coal for iron pick", tile_only=True)
        if routed:
            return routed
    if "collect_iron" not in achievements and pickaxe >= 2:
        routed = _seek_tile(readout, valid, session, "I", "seek iron for iron pick", tile_only=True)
        if routed:
            return routed
    if int(inv.get("wood", 0)) < 1:
        routed = _seek_tile(readout, valid, session, "T", "seek wood for iron pick")
        if routed:
            return routed
    if int(inv.get("stone", 0)) < 1 and pickaxe >= 1:
        routed = _seek_tile(readout, valid, session, "S^", "seek stone for iron pick", tile_only=True)
        if routed:
            return routed
    return None


def _can_descend_further(obs: dict[str, Any]) -> bool:
    level = int(obs["player"]["level"])
    floor_state = obs.get("floor_state") or {}
    ladders = floor_state.get("down_ladders") or []
    return level + 1 < len(ladders) and _down_ladder_pos(obs) is not None


def _attempt_descend(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    engine: Any,
    obs: dict[str, Any],
) -> dict[str, Any] | None:
    if not _can_descend_further(obs):
        return None
    if not _level_is_cleared(obs):
        routed = _hunt_level_mobs(readout, valid, session)
        if routed:
            return routed
    ladder_pos = _down_ladder_pos(obs)
    on_ladder = _player_on_tile(readout, ">") or (
        ladder_pos is not None and _player_pos(obs) == ladder_pos
    )
    if on_ladder and "descend" in valid and _can_take(engine, "descend"):
        return _decision("descend", "descend to next floor")
    if on_ladder and "descend" in valid:
        routed = _hunt_level_mobs(readout, valid, session)
        if routed:
            return routed
    goal = ladder_pos or session.get("ladder_pos")
    if not isinstance(goal, list):
        nearest = _nearest_char_pos(readout, ">")
        if nearest is not None:
            goal = list(nearest)
            session["ladder_pos"] = goal
    if isinstance(goal, list):
        routed = _go_pos(
            readout,
            valid,
            session,
            (int(goal[0]), int(goal[1])),
            "walk to ladder",
            avoid_hostiles=False,
        )
        if routed:
            return routed
    routed = _seek_tile(readout, valid, session, ">", "seek ladder", stand_on=True, avoid_hostiles=False)
    if routed:
        return routed
    return _frontier_explore(readout, valid, session, "find ladder") or _explore(
        readout, valid, session, "find ladder"
    )


def _pursue_dungeon_floor(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    engine: Any,
    obs: dict[str, Any],
    inv: dict[str, Any],
    achievements: set[str],
    pickaxe: int,
    sword: int,
    table_near: bool,
    furnace_near: bool,
) -> dict[str, Any] | None:
    level = int(obs["player"]["level"])
    if not _iron_pick_ready(achievements, pickaxe) and level <= 1:
        station = _ensure_dungeon_stations(
            readout, valid, session, engine, inv, achievements, table_near, furnace_near
        )
        if station:
            return station
        routed = _pursue_iron_pickaxe(
            readout, valid, session, inv, achievements, pickaxe, table_near, furnace_near
        )
        if routed:
            return routed
    if _level_is_cleared(obs) and _can_descend_further(obs) and level >= 4:
        routed = _attempt_descend(readout, valid, session, engine, obs)
        if routed:
            return routed
    if sword >= 1 and not _level_is_cleared(obs):
        routed = _hunt_level_mobs(readout, valid, session)
        if routed:
            return routed
    if pickaxe >= 3:
        if "collect_diamond" not in achievements:
            routed = _seek_tile(readout, valid, session, "D", "seek diamond", tile_only=True)
            if routed:
                return routed
        if "collect_ruby" not in achievements:
            routed = _seek_tile(readout, valid, session, "r", "seek ruby", tile_only=True)
            if routed:
                return routed
        if "collect_sapphire" not in achievements:
            routed = _seek_tile(readout, valid, session, "s", "seek sapphire", tile_only=True)
            if routed:
                return routed
    if "open_chest" not in achievements:
        routed = _seek_tile(readout, valid, session, "H", "seek chest", stand_on=False)
        if routed:
            return routed
    if (
        table_near
        and furnace_near
        and _iron_pick_resources_ready(inv)
        and "make_iron_sword" not in achievements
        and "make_iron_sword" in valid
    ):
        return _decision("make_iron_sword", "craft iron sword")
    if (
        table_near
        and furnace_near
        and pickaxe < 3
        and _iron_pick_resources_ready(inv)
        and "make_iron_pickaxe" in valid
    ):
        return _decision("make_iron_pickaxe", "craft iron pickaxe")
    if table_near and int(inv.get("wood", 0)) >= 1 and int(inv.get("stone", 0)) >= 1 and sword < 2 and "make_stone_sword" in valid:
        return _decision("make_stone_sword", "craft stone sword")
    if int(inv.get("bow", 0)) >= 1 and int(inv.get("arrows", 0)) >= 1 and "fire_bow" not in achievements:
        progress = _best_sim_action(engine, valid, ("fire_bow",))
        if progress:
            return _decision(progress, "fire bow")
    if _level_is_cleared(obs) and _can_descend_further(obs):
        routed = _attempt_descend(readout, valid, session, engine, obs)
        if routed:
            return routed
    routed = _frontier_explore(readout, valid, session, "explore floor")
    if routed:
        return routed
    return _explore(readout, valid, session, "explore floor")


def _best_sim_action(
    engine: Any,
    valid: set[str],
    preferred: tuple[str, ...] | None = None,
) -> str | None:
    if engine is None:
        return None
    candidates: list[str] = []
    if preferred:
        candidates.extend(action for action in preferred if action in valid)
    candidates.extend(action for action in valid if action not in candidates and action != "noop")
    best: tuple[float, str] | None = None
    for action in candidates:
        sim = engine.clone_for_sim()
        before_invalid = sim.private.invalid_action_count
        before_achievements = set(sim.symbolic_readout()["observation"].get("achievements", []))
        sim.step(action)
        if sim.private.invalid_action_count > before_invalid:
            continue
        reward = float(sim.private.reward_last)
        after_achievements = set(sim.symbolic_readout()["observation"].get("achievements", []))
        score = reward + (10.0 if after_achievements - before_achievements else 0.0)
        if score > 0 and (best is None or score > best[0]):
            best = (score, action)
    return best[1] if best else None


def _side_crafts_core_done(achievements: set[str]) -> bool:
    return (
        "collect_coal" in achievements
        and "collect_iron" in achievements
        and "place_furnace" in achievements
    )


def _seek_placement_adjacent(readout: dict[str, Any], valid: set[str], session: dict[str, Any]) -> dict[str, Any] | None:
    return _go(
        readout,
        valid,
        session,
        ".,",
        "find placement spot",
        tile_only=True,
        stand_on=False,
    )


def _frontier_explore(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    reason: str,
) -> dict[str, Any] | None:
    lines = _ascii_lines(readout)
    if not lines:
        return None
    start = tuple(_player_pos(readout["observation"]))
    visited = session.setdefault("visited", set())
    if len(visited) > 400:
        visited.clear()
        visited.add(start)
    queue: deque[tuple[int, int]] = deque([start])
    seen = {start}
    while queue:
        x, y = queue.popleft()
        for action, dx, dy in _DIRS:
            nxt = (x + dx, y + dy)
            if nxt in seen or not _is_passable(lines, nxt):
                continue
            seen.add(nxt)
            if nxt not in visited:
                routed = _route_to_tile(lines, start, nxt, set())
                action_name = _first_valid(routed or [], valid)
                if action_name:
                    route = _valid_prefix(routed or [], valid)
                    session["last_action"] = route[0]
                    return _decision_actions(route, reason)
            queue.append(nxt)
    return None


def _can_take(engine: Any, action: str) -> bool:
    return engine is None or not _is_immediate_violation(engine, action)


def _is_immediate_violation(engine: Any, action: str) -> bool:
    sim = engine.clone_for_sim()
    before_invalid = sim.private.invalid_action_count
    sim.step(action)
    return sim.private.invalid_action_count > before_invalid


def _setup_for_action(engine: Any, valid: set[str], target_action: str) -> str | None:
    if engine is None:
        return None
    for action in ("right", "down", "left", "up"):
        if action not in valid:
            continue
        sim = engine.clone_for_sim()
        before_invalid = sim.private.invalid_action_count
        sim.step(action)
        if sim.private.invalid_action_count > before_invalid:
            continue
        probe = sim.clone_for_sim()
        before_probe_invalid = probe.private.invalid_action_count
        probe.step(target_action)
        if probe.private.invalid_action_count == before_probe_invalid and float(probe.private.reward_last) > 0:
            return action
    return None


def _down_ladder_pos(obs: dict[str, Any]) -> list[int] | None:
    level = int(obs["player"]["level"])
    floor_state = obs.get("floor_state") or {}
    ladders = floor_state.get("down_ladders") or []
    if level >= len(ladders):
        return None
    pos = ladders[level]
    if not isinstance(pos, list) or len(pos) != 2:
        return None
    x, y = int(pos[0]), int(pos[1])
    if x < 0 or y < 0:
        return None
    return [x, y]


def _seek_tile(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    targets: str,
    reason: str,
    *,
    tile_only: bool = False,
    stand_on: bool = False,
    avoid_hostiles: bool = True,
) -> dict[str, Any] | None:
    if not _has_tile_char(readout, targets):
        return None
    return _go(
        readout,
        valid,
        session,
        targets,
        reason,
        tile_only=tile_only,
        stand_on=stand_on,
        avoid_hostiles=avoid_hostiles,
    )


def _seek_place_spot(readout: dict[str, Any], valid: set[str], session: dict[str, Any]) -> dict[str, Any] | None:
    return _seek_placement_adjacent(readout, valid, session)


def _return_to_table(readout: dict[str, Any], valid: set[str], session: dict[str, Any]) -> dict[str, Any] | None:
    table_pos = session.get("table_pos")
    if isinstance(table_pos, list) and len(table_pos) == 2:
        routed = _go_pos(readout, valid, session, (int(table_pos[0]), int(table_pos[1])), "return to table")
        if routed:
            return routed
    if _has_tile_char(readout, "A"):
        return _go(readout, valid, session, "A", "return to table")
    return None


def _go_pos(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    goal: tuple[int, int],
    reason: str,
    *,
    avoid_hostiles: bool = True,
) -> dict[str, Any] | None:
    lines = _ascii_lines(readout)
    start = tuple(_player_pos(readout["observation"]))
    blocked = _hostile_positions(readout) if avoid_hostiles else set()
    routed = _route_to_tile(lines, start, goal, blocked) or []
    action = _first_valid(routed, valid)
    if not action:
        return None
    route = _valid_prefix(routed, valid)
    session["last_action"] = route[0]
    return _decision_actions(route, reason)


def _explore(readout: dict[str, Any], valid: set[str], session: dict[str, Any], reason: str) -> dict[str, Any]:
    heading = int(session.get("explore_heading", 0)) % 4
    if int(session.get("stuck", 0)) >= 2:
        heading = (heading + 1) % 4
        session["explore_heading"] = heading
        session["stuck"] = 0
    local_map = readout["observation"]["local_map"]
    for offset in range(4):
        direction = _EXPLORE_DIRS[(heading + offset) % 4]
        if direction not in valid:
            continue
        if _local_move_blocked(local_map, direction):
            continue
        session["explore_heading"] = (heading + offset) % 4
        session["last_action"] = direction
        return _decision(direction, reason)
    action = _safe_move(valid)
    session["last_action"] = action
    return _decision(action, reason)


def _local_move_blocked(local_map: list[str], direction: str) -> bool:
    center_y = len(local_map) // 2
    center_x = len(local_map[0]) // 2 if local_map else 0
    dx, dy = {"right": (1, 0), "down": (0, 1), "left": (-1, 0), "up": (0, -1)}[direction]
    x = center_x + dx
    y = center_y + dy
    if y < 0 or y >= len(local_map) or x < 0 or x >= len(local_map[y]):
        return True
    char = local_map[y][x]
    return char in {"#", "%", "~", " ", "?"}


def _has_tile_char(readout: dict[str, Any], targets: str) -> bool:
    return any(char in targets for row in _ascii_lines(readout) for char in row)


def _best_reward_action(engine: Any, valid: set[str]) -> str | None:
    if engine is None:
        return None
    best: tuple[float, str] | None = None
    for action in valid:
        if action == "noop":
            continue
        sim = engine.clone_for_sim()
        before_invalid = sim.private.invalid_action_count
        sim.step(action)
        if sim.private.invalid_action_count > before_invalid:
            continue
        reward = float(sim.private.reward_last)
        if reward > 0 and (best is None or reward > best[0]):
            best = (reward, action)
    return best[1] if best else None


def _phase(achievements: set[str], pickaxe: int, sword: int, ply: int = 0, obs: dict[str, Any] | None = None) -> str:
    if pickaxe < 1:
        return "wood_pickaxe"
    if sword < 1:
        return "wood_sword"
    if "make_stone_pickaxe" not in achievements:
        return "stone_pickaxe"
    if "eat_cow" not in achievements:
        return "eat_cow"
    if "defeat_zombie" not in achievements:
        return "defeat_zombie"
    if "place_furnace" not in achievements:
        return "side_crafts"
    if obs is not None and int(obs["player"]["level"]) >= 1:
        return "dungeon"
    missing_side = "collect_coal" not in achievements or "collect_iron" not in achievements
    if not _iron_pick_ready(achievements, pickaxe) and ply < 300:
        return "iron_pick"
    if missing_side and ply < 120:
        return "side_crafts"
    if pickaxe >= 2 and sword >= 1:
        return "descend"
    if missing_side:
        return "side_crafts"
    return "descend"


def _trees_visible(readout: dict[str, Any]) -> bool:
    return "T" in str(readout.get("ascii", ""))


def _nearest_char_pos(readout: dict[str, Any], targets: str) -> tuple[int, int] | None:
    lines = _ascii_lines(readout)
    if not lines:
        return None
    pos = _player_pos(readout["observation"])
    start = (int(pos[0]), int(pos[1]))
    best: tuple[int, int] | None = None
    best_dist = 10**9
    for y, row in enumerate(lines):
        for x, ch in enumerate(row):
            if ch not in targets:
                continue
            dist = _manhattan(start, (x, y))
            if dist < best_dist:
                best_dist = dist
                best = (x, y)
    return best


def _should_harvest(
    phase: str,
    front: str,
    front_entity: str | None,
    pickaxe: int,
    achievements: set[str],
) -> bool:
    if front_entity is not None:
        return False
    if front in _WOOD_TILES and phase in {"wood_pickaxe", "wood_sword", "stone_pickaxe", "stone_sword", "side_crafts", "iron_pick", "passive_food"}:
        return True
    if front in {"stone", "stalagmite"} and pickaxe >= 1 and phase in {"stone_pickaxe", "stone_sword", "side_crafts", "iron_pick", "descend"}:
        return True
    if front == "coal" and pickaxe >= 1 and phase in {"side_crafts", "iron_pick", "descend", "dungeon"}:
        return True
    if front == "iron" and pickaxe >= 2 and phase in {"side_crafts", "iron_pick", "descend", "dungeon"}:
        return True
    if front == "diamond" and pickaxe >= 3 and phase == "dungeon" and "collect_diamond" not in achievements:
        return True
    if front == "ruby" and pickaxe >= 3 and phase == "dungeon" and "collect_ruby" not in achievements:
        return True
    if front == "sapphire" and pickaxe >= 3 and phase == "dungeon" and "collect_sapphire" not in achievements:
        return True
    return False


def _go(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    targets: str,
    reason: str,
    *,
    tile_only: bool = False,
    stand_on: bool = False,
    avoid_hostiles: bool = True,
) -> dict[str, Any]:
    if int(session.get("stuck", 0)) >= 2:
        probe_count = int(session.get("_stuck_route_probe_count", 0)) + 1
        session["_stuck_route_probe_count"] = probe_count
        if probe_count % 8 != 0:
            unstick = _unstick_decision(valid, session)
            if unstick:
                return unstick
    route = _route(
        readout,
        targets,
        session,
        tile_only=tile_only,
        stand_on=stand_on,
        avoid_hostiles=avoid_hostiles,
    )
    action = _first_valid(route, valid)
    if action:
        route = _valid_prefix(route, valid)
        session["last_action"] = route[0]
        return _decision_actions(route, reason)
    if int(session.get("stuck", 0)) >= 2:
        unstick = _unstick_decision(valid, session)
        if unstick:
            return unstick
    action = _safe_move(valid)
    session["last_action"] = action
    return _decision(action, reason)


def _unstick_decision(valid: set[str], session: dict[str, Any]) -> dict[str, Any] | None:
    for candidate in ("left", "up", "down", "right", "noop"):
        if candidate in valid and candidate != session.get("last_action"):
            session["last_action"] = candidate
            return _decision(candidate, "unstick")
    return None


def _go_entity(
    readout: dict[str, Any],
    valid: set[str],
    session: dict[str, Any],
    kind: str,
    reason: str,
    *,
    avoid_hostiles: bool = True,
) -> dict[str, Any] | None:
    action = _first_valid(_route_to_entity(readout, kind), valid)
    if action:
        session["last_action"] = action
        return _decision(action, reason)
    return None


def _decision(action: str, reason: str) -> dict[str, Any]:
    return {"actions": [action], "policy_reason": reason}


def _decision_actions(actions: list[str], reason: str) -> dict[str, Any]:
    return {"actions": actions, "policy_reason": reason}


def _first_valid(actions: list[str], valid: set[str]) -> str | None:
    for action in actions:
        if action in valid:
            return action
    return None


def _valid_prefix(actions: list[str], valid: set[str]) -> list[str]:
    prefix: list[str] = []
    for action in actions:
        if action not in valid:
            break
        prefix.append(action)
    return prefix


def _player_pos(obs: dict[str, Any]) -> list[int]:
    pos = obs["player"]["pos"]
    return [int(pos[0]), int(pos[1])]


def _entity_positions(readout: dict[str, Any]) -> set[tuple[int, int]]:
    positions: set[tuple[int, int]] = set()
    obs = readout["observation"]
    for entity in obs.get("nearby_entities", []):
        if not entity.get("mask", True):
            continue
        pos = entity.get("pos")
        if isinstance(pos, list) and len(pos) == 2:
            positions.add((int(pos[0]), int(pos[1])))
    return positions


def _entity_positions_for_kind(readout: dict[str, Any], kind: str) -> list[tuple[int, int]]:
    obs = readout["observation"]
    positions: list[tuple[int, int]] = []
    for entity in obs.get("nearby_entities", []):
        if str(entity.get("kind")) != kind or not entity.get("mask", True):
            continue
        pos = entity.get("pos")
        if isinstance(pos, list) and len(pos) == 2:
            positions.append((int(pos[0]), int(pos[1])))
    return positions


def _route_to_entity(readout: dict[str, Any], kind: str) -> list[str]:
    obs = readout["observation"]
    pos = obs["player"]["pos"]
    if not isinstance(pos, list) or len(pos) != 2:
        return []
    start = (int(pos[0]), int(pos[1]))
    lines = _ascii_lines(readout)
    best: list[str] = []
    best_dist = 10**9
    for target in _entity_positions_for_kind(readout, kind):
        routed = _route_to_adjacent_pos(lines, start, target, set())
        if not routed:
            continue
        dist = _manhattan(start, target)
        if dist < best_dist:
            best_dist = dist
            best = routed
    return best


def _route(
    readout: dict[str, Any],
    targets: str,
    session: dict[str, Any],
    *,
    tile_only: bool = False,
    stand_on: bool = False,
    avoid_hostiles: bool = True,
) -> list[str]:
    obs = readout["observation"]
    pos = obs["player"]["pos"]
    lines = _ascii_lines(readout)
    if not lines or not isinstance(pos, list) or len(pos) != 2:
        return _toward_chars(obs["local_map"], targets)
    start = (int(pos[0]), int(pos[1]))
    entity_positions = _entity_positions(readout) if tile_only else set()
    blocked = _hostile_positions(readout) if avoid_hostiles else set()
    cache_key = (
        start,
        targets,
        bool(tile_only),
        bool(stand_on),
        bool(avoid_hostiles),
        tuple(sorted(entity_positions)),
    )
    current_ply = int(session.get("ply", 0))
    miss_cache = session.setdefault("_route_miss_cache", {})
    cached_at = miss_cache.get(cache_key)
    if isinstance(cached_at, int) and current_ply - cached_at < 16:
        return _toward_chars(obs["local_map"], targets)
    if stand_on:
        best: list[str] = []
        best_dist = 10**9
        for y, row in enumerate(lines):
            for x, ch in enumerate(row):
                if ch not in targets:
                    continue
                if tile_only and (x, y) in entity_positions:
                    continue
                if (x, y) in blocked:
                    continue
                dist = _manhattan(start, (x, y))
                if dist < best_dist:
                    routed = _route_to_tile(lines, start, (x, y), blocked)
                    if routed is not None:
                        best_dist = dist
                        best = routed
        if not best:
            if len(miss_cache) > 2048:
                miss_cache.clear()
            miss_cache[cache_key] = current_ply
        return best
    routed = _route_to_nearest_tile(lines, start, targets, entity_positions if tile_only else set(), blocked)
    if routed:
        return routed
    if len(miss_cache) > 2048:
        miss_cache.clear()
    miss_cache[cache_key] = current_ply
    return _toward_chars(obs["local_map"], targets)


def _hostile_positions(readout: dict[str, Any]) -> set[tuple[int, int]]:
    obs = readout["observation"]
    blocked: set[tuple[int, int]] = set()
    for entity in obs.get("nearby_entities", []):
        if not entity.get("mask", True):
            continue
        if str(entity.get("class")) in {"melee", "ranged"} or str(entity.get("kind")) in {"zombie", "skeleton"}:
            pos = entity.get("pos")
            if isinstance(pos, list) and len(pos) == 2:
                blocked.add((int(pos[0]), int(pos[1])))
    return blocked


def _route_to_nearest_tile(
    lines: list[str],
    start: tuple[int, int],
    targets: str,
    skip: set[tuple[int, int]],
    blocked: set[tuple[int, int]],
) -> list[str]:
    first_action, distance, visit_order, parent = _reachable_first_actions(lines, start, blocked)
    best: list[str] = []
    best_dist = 10**9
    for y, row in enumerate(lines):
        for x, ch in enumerate(row):
            if ch not in targets:
                continue
            if (x, y) in skip:
                continue
            if (x, y) in blocked:
                continue
            dist = _manhattan(start, (x, y))
            if dist >= best_dist:
                continue
            if dist == 1:
                facing = _direction_toward(start, (x, y))
                if facing:
                    return [facing]
            adjacent_route = _route_to_adjacent_target(
                (x, y),
                first_action,
                distance,
                visit_order,
                parent,
                blocked,
            )
            if adjacent_route:
                best_dist = dist
                best = adjacent_route
    return best


def _reachable_first_actions(
    lines: list[str],
    start: tuple[int, int],
    blocked: set[tuple[int, int]],
) -> tuple[
    dict[tuple[int, int], str | None],
    dict[tuple[int, int], int],
    dict[tuple[int, int], int],
    dict[tuple[int, int], tuple[int, int] | None],
]:
    queue: deque[tuple[int, int]] = deque([start])
    first_action: dict[tuple[int, int], str | None] = {start: None}
    distance: dict[tuple[int, int], int] = {start: 0}
    visit_order: dict[tuple[int, int], int] = {start: 0}
    parent: dict[tuple[int, int], tuple[int, int] | None] = {start: None}
    next_order = 1
    while queue:
        x, y = queue.popleft()
        for action, dx, dy in _DIRS:
            nxt = (x + dx, y + dy)
            if nxt in first_action or nxt in blocked or not _is_passable(lines, nxt):
                continue
            first_action[nxt] = action if (x, y) == start else first_action[(x, y)]
            distance[nxt] = distance[(x, y)] + 1
            visit_order[nxt] = next_order
            parent[nxt] = (x, y)
            next_order += 1
            queue.append(nxt)
    return first_action, distance, visit_order, parent


def _route_to_adjacent_target(
    target: tuple[int, int],
    first_action: dict[tuple[int, int], str | None],
    distance: dict[tuple[int, int], int],
    visit_order: dict[tuple[int, int], int],
    parent: dict[tuple[int, int], tuple[int, int] | None],
    blocked: set[tuple[int, int]],
) -> list[str]:
    best: tuple[int, int, tuple[int, int]] | None = None
    x, y = target
    for _, dx, dy in _DIRS:
        nxt = (x + dx, y + dy)
        if nxt in blocked:
            continue
        first = first_action.get(nxt)
        if first is None:
            continue
        candidate = (distance[nxt], visit_order[nxt], nxt)
        if best is None or candidate[0] < best[0]:
            best = candidate
        elif best is not None and candidate[0] == best[0] and candidate[1] < best[1]:
            best = candidate
    return [] if best is None else _path_to(parent, best[2])


def _has_standable_neighbor(lines: list[str], target: tuple[int, int], blocked: set[tuple[int, int]]) -> bool:
    x, y = target
    for action, dx, dy in _DIRS:
        nxt = (x + dx, y + dy)
        if nxt in blocked:
            continue
        if _is_passable(lines, nxt):
            return True
    return False


def _route_to_adjacent_pos(
    lines: list[str],
    start: tuple[int, int],
    target: tuple[int, int],
    blocked: set[tuple[int, int]] | None = None,
) -> list[str]:
    blocked = blocked or set()
    if _manhattan(start, target) == 1:
        facing = _direction_toward(start, target)
        return [facing] if facing else []
    queue: deque[tuple[int, int]] = deque([start])
    first_action: dict[tuple[int, int], str | None] = {start: None}
    parent: dict[tuple[int, int], tuple[int, int] | None] = {start: None}
    while queue:
        x, y = queue.popleft()
        for action, dx, dy in _DIRS:
            nxt = (x + dx, y + dy)
            if nxt in first_action or nxt in blocked or not _is_passable(lines, nxt):
                continue
            first_action[nxt] = action if (x, y) == start else first_action[(x, y)]
            parent[nxt] = (x, y)
            if _manhattan(nxt, target) == 1:
                return _path_to(parent, nxt)
            queue.append(nxt)
    return []


def _route_to_tile(
    lines: list[str],
    start: tuple[int, int],
    target: tuple[int, int],
    blocked: set[tuple[int, int]] | None = None,
) -> list[str] | None:
    blocked = blocked or set()
    if start == target:
        return []
    queue: deque[tuple[int, int]] = deque([start])
    first_action: dict[tuple[int, int], str | None] = {start: None}
    parent: dict[tuple[int, int], tuple[int, int] | None] = {start: None}
    while queue:
        x, y = queue.popleft()
        for action, dx, dy in _DIRS:
            nxt = (x + dx, y + dy)
            if nxt in first_action or nxt in blocked or not _is_passable(lines, nxt):
                continue
            first_action[nxt] = action if (x, y) == start else first_action[(x, y)]
            parent[nxt] = (x, y)
            if nxt == target:
                return _path_to(parent, nxt)
            queue.append(nxt)
    return None


def _route_to_adjacent(lines: list[str], start: tuple[int, int], targets: str) -> list[str]:
    facing = _adjacent_direction(lines, start, targets)
    if facing:
        return [facing]
    queue: deque[tuple[int, int]] = deque([start])
    first_action: dict[tuple[int, int], str | None] = {start: None}
    parent: dict[tuple[int, int], tuple[int, int] | None] = {start: None}
    while queue:
        x, y = queue.popleft()
        for action, dx, dy in _DIRS:
            nxt = (x + dx, y + dy)
            if nxt in first_action or not _is_passable(lines, nxt):
                continue
            first_action[nxt] = action if (x, y) == start else first_action[(x, y)]
            parent[nxt] = (x, y)
            if _adjacent_direction(lines, nxt, targets):
                return _path_to(parent, nxt)
            queue.append(nxt)
    return []


def _path_to(
    parent: dict[tuple[int, int], tuple[int, int] | None],
    target: tuple[int, int],
) -> list[str]:
    positions: list[tuple[int, int]] = []
    current: tuple[int, int] | None = target
    while current is not None:
        positions.append(current)
        current = parent[current]
    positions.reverse()
    route: list[str] = []
    for index in range(1, len(positions)):
        action = _direction_between(positions[index - 1], positions[index])
        if action is not None:
            route.append(action)
    return route


def _direction_between(start: tuple[int, int], target: tuple[int, int]) -> str | None:
    sx, sy = start
    tx, ty = target
    delta = (tx - sx, ty - sy)
    for action, dx, dy in _DIRS:
        if delta == (dx, dy):
            return action
    return None


def _adjacent_direction(lines: list[str], pos: tuple[int, int], targets: str) -> str | None:
    x, y = pos
    for action, dx, dy in _DIRS:
        if _char_at(lines, x + dx, y + dy) in targets:
            return action
    return None


def _direction_toward(start: tuple[int, int], target: tuple[int, int]) -> str | None:
    sx, sy = start
    tx, ty = target
    dx = tx - sx
    dy = ty - sy
    if abs(dx) >= abs(dy) and dx != 0:
        return "right" if dx > 0 else "left"
    if dy != 0:
        return "down" if dy > 0 else "up"
    return None


def _manhattan(a: tuple[int, int], b: tuple[int, int]) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def _nearby(local_map: list[str], chars: str) -> bool:
    center_y = len(local_map) // 2
    center_x = len(local_map[0]) // 2 if local_map else 0
    for dx, dy in ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)):
        y = center_y + dy
        x = center_x + dx
        if 0 <= y < len(local_map) and 0 <= x < len(local_map[y]) and local_map[y][x] in chars:
            return True
    return False


def _front_placeable(front_tile: str) -> bool:
    return front_tile in {"grass", "sand", "path", "floor", "dirt"}


def _front_char(obs: dict[str, Any], local_map: list[str]) -> str:
    direction = obs["player"]["direction"]
    if not isinstance(direction, list) or len(direction) != 2:
        return ""
    center_y = len(local_map) // 2
    center_x = len(local_map[0]) // 2 if local_map else 0
    fx = center_x + int(direction[0])
    fy = center_y + int(direction[1])
    if 0 <= fy < len(local_map) and 0 <= fx < len(local_map[fy]):
        return local_map[fy][fx]
    return ""


def _entity_kind_at_front(obs: dict[str, Any]) -> str | None:
    pos = obs["player"]["pos"]
    direction = obs["player"]["direction"]
    if not isinstance(pos, list) or not isinstance(direction, list):
        return None
    front = [int(pos[0]) + int(direction[0]), int(pos[1]) + int(direction[1])]
    for entity in obs.get("nearby_entities", []):
        entity_pos = entity.get("pos")
        if isinstance(entity_pos, list) and entity_pos == front and entity.get("mask", True):
            return str(entity.get("kind"))
    return None


def _player_on_tile(readout: dict[str, Any], char: str) -> bool:
    obs = readout["observation"]
    pos = obs["player"]["pos"]
    if not isinstance(pos, list) or len(pos) != 2:
        return False
    lines = _ascii_lines(readout)
    if not lines:
        return False
    return _char_at(lines, int(pos[0]), int(pos[1])) == char


def _ascii_lines(readout: dict[str, Any]) -> list[str]:
    cached = readout.get("_ascii_lines")
    if isinstance(cached, list):
        return cached
    ascii_map = readout.get("ascii", "")
    lines = ascii_map.splitlines() if isinstance(ascii_map, str) else str(ascii_map).splitlines()
    readout["_ascii_lines"] = lines
    return lines


def _is_passable(lines: list[str], pos: tuple[int, int]) -> bool:
    char = _char_at(lines, pos[0], pos[1])
    if char in {"#", "%", "?", " ", "~", "L", "P"}:
        return False
    if char.isupper():
        return False
    return char in _PASSABLE


def _char_at(lines: list[str], x: int, y: int) -> str:
    if y < 0 or y >= len(lines) or x < 0 or x >= len(lines[y]):
        return ""
    return lines[y][x]


def _toward_chars(local_map: list[str], targets: str) -> list[str]:
    center_y = len(local_map) // 2
    center_x = len(local_map[0]) // 2 if local_map else 0
    best: tuple[int, int, int] | None = None
    for y, row in enumerate(local_map):
        for x, char in enumerate(row):
            if char in targets:
                dist = abs(x - center_x) + abs(y - center_y)
                if best is None or dist < best[0]:
                    best = (dist, x - center_x, y - center_y)
    if best is None:
        return []
    _, dx, dy = best
    if abs(dx) >= abs(dy) and dx != 0:
        return ["right" if dx > 0 else "left"]
    if dy != 0:
        return ["down" if dy > 0 else "up"]
    return ["do"]


def _safe_move(valid: set[str]) -> str:
    for action in ("right", "down", "left", "up", "noop"):
        if action in valid:
            return action
    return "noop"