// Shared code for the sample opponent bots (random, brawler, kiter): their policies (policy.ts)
// use these helpers, and run.ts connects a policy to the ladder.
// Bot authors should start from bots/ts-starter, which is self-contained.
//
// Two rules these helpers follow, and your bot should too:
// - For this tick, choose from what the observation offers: `moves` and `dashes` hold only what the
//   engine would accept now, and `danger` says which tiles get hit when. The map is for planning
//   further ahead (paths, room to manoeuvre), where the observation can't help.
// - Read every number from `hello.rules`; the ladder retunes them between releases.

export type Dir = "N" | "NE" | "E" | "SE" | "S" | "SW" | "W" | "NW";
export type Pos = [number, number];
export const DIRS: Dir[] = ["N", "NE", "E", "SE", "S", "SW", "W", "NW"];
export const VEC: Record<Dir, Pos> = { N: [0, -1], NE: [1, -1], E: [1, 0], SE: [1, 1], S: [0, 1], SW: [-1, 1], W: [-1, 0], NW: [-1, -1] };

/** The parts of `hello.rules` these bots read. Every field: /docs/rules. */
export interface Rules {
  stats: { max_hp: number; move_cooldown: number };
  attacks: {
    ranged: { speed: number };
    frostburst: { range: number; slow?: number };
    repulsor: { push: number };
  };
  knockback: { wall_slam_stun: number };
  pickups?: { health?: { amount: number } };
}

/** The parts of `hello` these bots read. */
export interface Hello {
  match_id: string;
  bot_id: number;
  seed_public: number;
  /** rows of `.` (floor) and `#` (wall) */
  map: string[];
  rules: Rules;
}

export interface Enemy {
  id: number;
  pos: Pos;
  hp: number;
  /** ticks until it can dash again; 0 = ready */
  dash_cooldown: number;
  state: string;
  state_ticks_left: number;
  slow_ticks_left: number;
}

/** The parts of an observation these bots read. Every field: /docs/schema/observation.json. */
export interface Observation {
  tick: number;
  self: { id: number; pos: Pos; hp: number; max_hp: number; state: string; cooldowns: Record<string, number> };
  /** visible opponents only */
  enemies: Enemy[];
  /** steps the engine would accept now, with the tile each reaches */
  moves: { dir: Dir; tile: Pos }[];
  /** dashes the engine would accept now, with the landing tile */
  dashes: { dir: Dir; tile: Pos; distance: number }[];
  /** every tile each visible opponent shot or area will hit, and on which tick */
  danger: { tile: Pos; tick: number }[];
  pickups: { pos: Pos; kind: string; ready_in: number }[];
  areas: { owner: number; ticks_left: number; tiles: Pos[] }[];
  zone: { center: Pos; radius: number; next_radius: number | null; shrinks_in: number | null };
  events: { kind: string; [field: string]: unknown }[];
}

/** The attack half of a turn. The repulsor has no aim, so it needs no target. */
export interface Attack {
  name: string;
  target?: Pos;
}

/** What a bot does in one tick: a movement (a step or a dash, or neither), then an optional attack. */
export interface Turn {
  move?: Dir;
  dash?: Dir;
  attack?: Attack;
  /** said to everyone, at most hello.rules.shout.max_length characters */
  shout?: string;
}

export interface Ctx {
  hello: Hello;
  map: string[];
  /** what a policy notes across the ticks of one match: the enemy's last sighting and step, a temperament */
  memory: Record<string, any>;
  /** seeded per match (from hello.seed_public and this bot's id), so games vary but stay reproducible */
  rand: () => number;
}

/** mulberry32: tiny seeded PRNG returning floats in [0, 1). */
export function seededRandom(seed: number): () => number {
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

export const cheb = (a: Pos, b: Pos) => Math.max(Math.abs(a[0] - b[0]), Math.abs(a[1] - b[1]));
export const add = (a: Pos, d: Dir, k = 1): Pos => [a[0] + VEC[d][0] * k, a[1] + VEC[d][1] * k];
const same = (a: Pos, b: Pos) => a[0] === b[0] && a[1] === b[1];

/** The octant the vector from a to b falls in (same rule the engine uses). */
export function dirTo(a: Pos, b: Pos): Dir | null {
  const dx = b[0] - a[0];
  const dy = b[1] - a[1];
  if (!dx && !dy) return null;
  const t = 0.41421356;
  if (Math.abs(dy) < Math.abs(dx) * t) return dx > 0 ? "E" : "W";
  if (Math.abs(dx) < Math.abs(dy) * t) return dy > 0 ? "S" : "N";
  if (dx > 0) return dy > 0 ? "SE" : "NE";
  return dy > 0 ? "SW" : "NW";
}

export const tile = (map: string[], p: Pos) => (p[1] < 0 || p[1] >= map.length || p[0] < 0 || p[0] >= map[0]!.length ? "#" : map[p[1]]![p[0]]!);

/**
 * For planning paths: could a fighter at `from` step in `d`, walls alone considered? Not into a
 * wall, and not diagonally past a wall corner. For this tick's step, use `observation.moves`.
 */
export function canStep(map: string[], from: Pos, d: Dir): boolean {
  if (tile(map, add(from, d)) === "#") return false;
  const [dx, dy] = VEC[d];
  if (dx && dy && (tile(map, [from[0] + dx, from[1]]) === "#" || tile(map, [from[0], from[1] + dy]) === "#")) return false;
  return true;
}

// The searches below run several times a tick, so they work on tile numbers (y * width + x) with
// typed arrays rather than positions and strings, and look up steps in a table made once per map.

const stepTables = new WeakMap<string[], Uint8Array>();

/** `canStep` for every tile and direction of a map (by its rows), worked out on first use: index tile * 8 + direction. */
function stepTable(map: string[]): Uint8Array {
  let table = stepTables.get(map);
  if (!table) {
    const w = map[0]!.length;
    table = new Uint8Array(map.length * w * 8);
    for (let y = 0; y < map.length; y++)
      for (let x = 0; x < w; x++) for (let k = 0; k < 8; k++) table[(y * w + x) * 8 + k] = canStep(map, [x, y], DIRS[k]!) ? 1 : 0;
    stepTables.set(map, table);
  }
  return table;
}

/** The tiles in `blocked` that are on the map, as tile numbers. */
function blockedSet(map: string[], blocked: Pos[]): Set<number> {
  const w = map[0]!.length;
  return new Set(blocked.filter((p) => p[0] >= 0 && p[1] >= 0 && p[0] < w && p[1] < map.length).map((p) => p[1] * w + p[0]));
}

/** First step of a BFS path from `from` to any tile within `range` of `goal`, avoiding walls and `blocked`. */
export function stepToward(map: string[], from: Pos, goal: Pos, range = 0, blocked: Pos[] = []): Dir | null {
  const w = map[0]!.length;
  const steps = stepTable(map);
  const block = blockedSet(map, blocked);
  // the direction of the first step on the way to each tile reached: -1 not reached, 8 the start
  const first = new Int8Array(map.length * w).fill(-1);
  const queue = new Int32Array(map.length * w); // each tile is queued at most once
  let tail = 0;
  queue[tail++] = from[1] * w + from[0];
  first[queue[0]!] = 8;
  const dist = new Int32Array(8);
  const order = [0, 1, 2, 3, 4, 5, 6, 7];
  for (let head = 0; head < tail; head++) {
    const i = queue[head]!;
    const x = i % w;
    const y = (i - x) / w;
    const via = first[i]!;
    if (Math.max(Math.abs(x - goal[0]), Math.abs(y - goal[1])) <= range) return via === 8 ? null : DIRS[via]!;
    // Prefer straight-line directions first so paths look natural: nearest the goal first, ties in DIRS order.
    for (let k = 0; k < 8; k++) {
      const [dx, dy] = VEC[DIRS[k]!];
      dist[k] = Math.max(Math.abs(x + dx - goal[0]), Math.abs(y + dy - goal[1]));
      order[k] = k;
    }
    order.sort((a, b) => dist[a]! - dist[b]! || a - b);
    for (const k of order) {
      if (!steps[i * 8 + k]) continue;
      const [dx, dy] = VEC[DIRS[k]!];
      const n = i + dy * w + dx;
      if (first[n] !== -1 || block.has(n)) continue;
      first[n] = via === 8 ? k : via;
      queue[tail++] = n;
    }
  }
  return null;
}

/** BFS steps from `from` to `goal` (walls avoided), or Infinity if unreachable. */
export function pathLength(map: string[], from: Pos, goal: Pos, blocked: Pos[] = []): number {
  const w = map[0]!.length;
  const steps = stepTable(map);
  const block = blockedSet(map, blocked);
  const count = new Int16Array(map.length * w).fill(-1);
  const queue = new Int32Array(map.length * w);
  let tail = 0;
  queue[tail++] = from[1] * w + from[0];
  count[queue[0]!] = 0;
  const target = goal[1] * w + goal[0];
  const onMap = goal[0] >= 0 && goal[1] >= 0 && goal[0] < w && goal[1] < map.length;
  for (let head = 0; head < tail; head++) {
    const i = queue[head]!;
    if (onMap && i === target) return count[i]!;
    for (let k = 0; k < 8; k++) {
      if (!steps[i * 8 + k]) continue;
      const [dx, dy] = VEC[DIRS[k]!];
      const n = i + dy * w + dx;
      if (count[n] !== -1 || block.has(n)) continue;
      count[n] = count[i]! + 1;
      queue[tail++] = n;
    }
  }
  return Infinity;
}

/** Is `p` inside the zone, `margin` tiles in? Once a shrink is announced, inside the next zone. */
export function inSafeZone(obs: Observation, p: Pos, margin = 0): boolean {
  const radius = obs.zone.shrinks_in === null ? obs.zone.radius : obs.zone.next_radius!;
  return cheb(p, obs.zone.center) <= radius - margin;
}

/** Is tile `p` hit by an opponent's shot or area between `first` and `last` ticks from now (0 = the tick we reply to)? */
export function hitIn(obs: Observation, p: Pos, first: number, last: number): boolean {
  return obs.danger.some((d) => same(d.tile, p) && d.tick - obs.tick >= first && d.tick - obs.tick <= last);
}

/**
 * Leave a tile that a shot or area will hit within 2 ticks: a step to a tile that stays safe, or
 * a dash (invulnerable on its own tick) to a landing that is safe after it. Shots fired this tick
 * from 2 tiles or closer land at once and never show in `danger`: up close, keep moving.
 */
export function evadeDanger(obs: Observation): Turn | null {
  if (obs.self.state !== "idle" || !hitIn(obs, obs.self.pos, 0, 2)) return null;
  for (const m of obs.moves) if (!hitIn(obs, m.tile, 0, 2) && inSafeZone(obs, m.tile)) return { move: m.dir };
  for (const d of obs.dashes) if (!hitIn(obs, d.tile, 1, 2) && inSafeZone(obs, d.tile)) return { dash: d.dir };
  return null;
}

/**
 * First step toward the best stocked pickup within `maxSteps`, or null. Skips pickups the enemy
 * is closer to, ones outside the (shrinking) zone, and health that would mostly be wasted.
 */
export function pickupStep(obs: Observation, ctx: Ctx, maxSteps: number): Dir | null {
  const me = obs.self;
  const enemy = obs.enemies[0];
  const heal = ctx.hello.rules.pickups?.health?.amount ?? 0;
  let best: { p: Observation["pickups"][number]; steps: number } | null = null;
  for (const p of obs.pickups) {
    if (p.ready_in > 0 || !inSafeZone(obs, p.pos)) continue;
    if (p.kind === "health" && me.hp > me.max_hp - heal * 0.6) continue;
    const steps = pathLength(ctx.map, me.pos, p.pos, enemy ? [enemy.pos] : []);
    if (steps > maxSteps || (enemy && cheb(enemy.pos, p.pos) < steps)) continue;
    if (!best || steps < best.steps) best = { p, steps };
  }
  return best ? stepToward(ctx.map, me.pos, best.p.pos, 0, enemy ? [enemy.pos] : []) : null;
}

/** How much room there is around a tile: open tiles within 2 (0–24). */
export function openness(map: string[], p: Pos): number {
  let n = 0;
  for (let dx = -2; dx <= 2; dx++)
    for (let dy = -2; dy <= 2; dy++) {
      if (!dx && !dy) continue;
      if (tile(map, [p[0] + dx, p[1] + dy]) === ".") n++;
    }
  return n;
}

/** How good a tile is to back off to: far from the threat, roomy, and not far from the zone's centre. */
function retreatScore(obs: Observation, ctx: Ctx, to: Pos, threat: Pos): number {
  const centre = cheb(to, obs.zone.center) * (inSafeZone(obs, to, 2) ? 0.3 : 1);
  return 3 * cheb(to, threat) + 0.6 * openness(ctx.map, to) - 0.8 * centre + ctx.rand() * 0.5;
}

/**
 * Best step away from `threat`, from `observation.moves`: far from it, toward open space and the
 * zone centre, so a retreating bot circles around instead of backing into a corner.
 */
export function retreatStep(obs: Observation, ctx: Ctx, threat: Pos): Dir | null {
  let best: { dir: Dir; score: number } | null = null;
  for (const m of obs.moves) {
    if (hitIn(obs, m.tile, 0, 2)) continue;
    const score = retreatScore(obs, ctx, m.tile, threat);
    if (!best || score > best.score) best = { dir: m.dir, score };
  }
  return best?.dir ?? null;
}

/** The best escape dash from `observation.dashes`: one that really gets away, lands safe and stays in the zone. */
export function escapeDash(obs: Observation, ctx: Ctx, threat: Pos): Dir | null {
  let best: { dir: Dir; score: number } | null = null;
  for (const d of obs.dashes) {
    if (d.distance < 2 || cheb(d.tile, threat) < 2 || !inSafeZone(obs, d.tile) || hitIn(obs, d.tile, 1, 2)) continue;
    const score = retreatScore(obs, ctx, d.tile, threat);
    if (!best || score > best.score) best = { dir: d.dir, score };
  }
  return best?.dir ?? null;
}

/** Ticks one patrol leg lasts. */
const PATROL_TICKS = 30;

/**
 * Where to go while the enemy is out of sight: where it was last seen, then around the zone,
 * one corner of a square half its radius out every PATROL_TICKS. Never park and wait: two bots
 * that do can spend a whole match on opposite sides of a pillar.
 */
export function searchGoal(obs: Observation, ctx: Ctx): Pos {
  const last: Pos | undefined = ctx.memory.lastSeen;
  if (last && cheb(obs.self.pos, last) > 1) return last;
  ctx.memory.lastSeen = undefined;
  const r = Math.max(1, Math.floor(obs.zone.radius / 2));
  const [cx, cy] = obs.zone.center;
  const corners: Pos[] = [[cx - r, cy - r], [cx + r, cy - r], [cx + r, cy + r], [cx - r, cy + r]];
  return corners[Math.floor(obs.tick / PATROL_TICKS) % corners.length]!;
}

/** A bot's decisions: its version label and its turn for each observation. */
export interface Policy {
  version: string;
  decide: (obs: Observation, ctx: Ctx) => Turn;
}

/** The per-match context a policy keeps, from the match's `hello` (the parsed message, as it arrived). */
export function newCtx(message: unknown): Ctx {
  const hello = message as Hello;
  return { hello, map: hello.map, memory: {}, rand: seededRandom(hello.seed_public * 7919 + hello.bot_id) };
}

/**
 * The frame that answers an observation (the parsed message, as it arrived). A crash in `decide`
 * is logged and the tick is idle, so one bug never costs the match.
 */
export function reply(policy: Policy, message: unknown, ctx: Ctx): string {
  const obs = message as Observation;
  let turn: Turn;
  try {
    turn = policy.decide(obs, ctx);
  } catch (e) {
    console.error(e);
    turn = {};
  }
  return JSON.stringify({ tick: obs.tick, ...turn });
}

/** Where the fighter ends its movement this tick under `turn` (its own tile if it neither steps nor dashes). */
export function endTile(obs: Observation, turn: Turn): Pos {
  const found = turn.move ? obs.moves.find((m) => m.dir === turn.move) : turn.dash ? obs.dashes.find((d) => d.dir === turn.dash) : null;
  return found ? found.tile : obs.self.pos;
}

/**
 * Note where the enemy is and when it last stepped, for `searchGoal`, `enemyStepIn` and leading
 * shots. Call once per observation, first thing. A step from inside a frostburst area costs the
 * area's slow on top of the move cooldown.
 */
export function watchEnemy(obs: Observation, ctx: Ctx): void {
  const enemy = obs.enemies[0];
  const prev = ctx.memory.enemyPrev;
  if (enemy && prev && prev.tick === obs.tick - 1 && cheb(prev.pos, enemy.pos) === 1) {
    const slow = prev.slowed ? (ctx.hello.rules.attacks.frostburst.slow ?? 0) : 0;
    ctx.memory.enemyMoveReady = obs.tick - 1 + ctx.hello.rules.stats.move_cooldown + slow;
    ctx.memory.enemyStep = [enemy.pos[0] - prev.pos[0], enemy.pos[1] - prev.pos[1]];
  } else if (enemy && prev && prev.tick === obs.tick - 1) ctx.memory.enemyStep = null;
  ctx.memory.enemyPrev = enemy ? { tick: obs.tick, pos: enemy.pos, slowed: enemy.slow_ticks_left > 0 } : null;
  if (enemy) ctx.memory.lastSeen = enemy.pos;
}

/** Ticks from now until the enemy can step again (0 = it can step this tick), as far as we saw it step. */
export function enemyStepIn(obs: Observation, ctx: Ctx): number {
  return Math.max(0, (ctx.memory.enemyMoveReady ?? 0) - obs.tick);
}

/**
 * How many ticks, starting with this one, the enemy can't leave its tile: it is stunned or
 * recovering from a dash, or it just stepped and its dash is on cooldown too.
 */
export function pinnedFor(obs: Observation, ctx: Ctx, enemy: Enemy): number {
  if (enemy.state === "stunned" || enemy.state === "recovering") return enemy.state_ticks_left;
  return Math.min(enemyStepIn(obs, ctx), enemy.dash_cooldown);
}

/** Ticks after firing that a standard shot from `from` reaches `to` (0 = this tick). */
export function shotArrival(rules: Rules, from: Pos, to: Pos): number {
  return Math.max(0, Math.ceil(cheb(from, to) / rules.attacks.ranged.speed) - 1);
}

/** Where a repulsor shove from `from` leaves a target at `target`, and whether a wall stops it (a slam). */
export function shove(map: string[], from: Pos, target: Pos, push: number): { tile: Pos; slam: boolean } {
  const dir = dirTo(from, target)!;
  let p = target;
  for (let k = 0; k < push; k++) {
    if (!canStep(map, p, dir)) return { tile: p, slam: true };
    p = add(p, dir);
  }
  return { tile: p, slam: false };
}

/**
 * The attack phase, fired from `from` (where the movement ends). Combos first: a shot the pinned
 * enemy can't dodge, then a shove into a wall (a slam stuns, which sets up that shot) or into one of
 * our areas that explodes before they can leave. Otherwise a mix of shots, frostburst and shoves.
 * Returns null when nothing is ready or no enemy is in sight. `aim` overrides where the standard
 * shot is aimed (to lead a moving target); `shoveChance` is the chance of a shove that is neither
 * a slam nor a trap (a kiter shoves to make room).
 */
export function chooseAttack(obs: Observation, ctx: Ctx, from: Pos, aim?: Pos, shoveChance = 0.4): Attack | null {
  const enemy = obs.enemies[0];
  if (!enemy) return null;
  const rules = ctx.hello.rules;
  // Each weapon has its own cooldown.
  const ready = (name: string) => obs.self.cooldowns[name] === 0;
  const d = cheb(from, enemy.pos);
  if (d === 0) return null;
  // A sure hit: the shot lands before the enemy can step or dash off its tile.
  if (ready("ranged") && shotArrival(rules, from, enemy.pos) < pinnedFor(obs, ctx, enemy)) return { name: "ranged", target: enemy.pos };
  if (d === 1 && ready("repulsor")) {
    const landing = shove(ctx.map, from, enemy.pos, rules.attacks.repulsor.push);
    // A slammed target stays put for the stun; otherwise only an area exploding this tick is sure.
    const holds = landing.slam ? rules.knockback.wall_slam_stun + 1 : 1;
    const trap = obs.areas.some((a) => a.owner === obs.self.id && a.ticks_left <= holds && a.tiles.some((t) => same(t, landing.tile)));
    if (landing.slam || trap || ctx.rand() < shoveChance) return { name: "repulsor" };
  }
  // Frostburst is cast on the target's tile and needs it in sight from where the movement ends. We
  // only know sight from where we stand, so cast it standing still. Best on a target that can't dash out.
  const stuck = enemy.state === "recovering" || enemy.dash_cooldown > 0;
  const castable = same(from, obs.self.pos) && d > 1 && d <= rules.attacks.frostburst.range;
  if (castable && ready("frostburst") && !enemy.slow_ticks_left && ctx.rand() < (stuck ? 0.6 : 0.25)) return { name: "frostburst", target: enemy.pos };
  return ready("ranged") ? { name: "ranged", target: aim ?? enemy.pos } : null;
}