benjivers/val Public Public: anyone can read this; the crew can change it.

/**

 * A tile grid and the questions everything else asks of it: which tiles are

 * solid, where a circle slides to, whether a wall stands between two points,

 * where a ray stops, and how far a walk is.

 *

 * The grid is rows of letters. `#` is a wall; every other letter is floor,

 * and what a letter means beyond that is the game's business — this module

 * hands back the cells of a letter and never asks what they are for.

 *

 * `makeGrid` binds the maths to one set of rows and one tile size. The

 * collision itself is `glide.ts`, which the browser runs too; the walk

 * distances are cached per goal for the round and cleared by the caller.

 */

import { circleBlocked, slideCircle } from "./glide.ts";

export type Point = { x: number; y: number };

export type Grid = {

  lines: string[];

  cols: number;

  rows: number;

  tile: number;

  width: number;

  height: number;

  /** The letter at a tile; anything off the grid is a wall. */

  at: (col: number, row: number) => string;

  solidTile: (col: number, row: number) => boolean;

  tileOf: (x: number, y: number) => { col: number; row: number };

  centreOf: (col: number, row: number) => Point;

  solidAt: (x: number, y: number) => boolean;

  /** The letter under a point. */

  cellAt: (x: number, y: number) => string;

  /** The centres of every tile carrying this letter, row by row. */

  cellsOf: (mark: string) => Point[];

  /** Slide a circle through this grid. */

  moveCircle: (x: number, y: number, dx: number, dy: number, r: number) => Point;

  /** True when a circle at (x,y) overlaps any solid tile. */

  blockedCircle: (x: number, y: number, r: number) => boolean;

  wallBetween: (a: Point, b: Point) => boolean;

  rayHitWall: (from: Point, angle: number, range: number) => Point;

  walkDistance: (from: Point, to: Point) => number;

  pathStep: (from: Point, to: Point) => Point;

  clearPaths: () => void;

};

/** Closest approach of a segment to a point, as distance and travel along it. */

export function segmentPoint(a: Point, b: Point, p: Point): { dist: number; travel: number } {

  const dx = b.x - a.x;

  const dy = b.y - a.y;

  const len2 = dx * dx + dy * dy;

  const t = len2 === 0 ? 0 : Math.max(0, Math.min(1, ((p.x - a.x) * dx + (p.y - a.y) * dy) / len2));

  const cx = a.x + dx * t;

  const cy = a.y + dy * t;

  return { dist: Math.hypot(p.x - cx, p.y - cy), travel: t * Math.sqrt(len2) };

}

export const segmentHitsCircle = (a: Point, b: Point, c: Point, r: number): boolean =>

  segmentPoint(a, b, c).dist <= r;

const STEPS = [

  [1, 0],

  [-1, 0],

  [0, 1],

  [0, -1],

] as const;

export function makeGrid(lines: string[], tile: number): Grid {

  const cols = lines[0]!.length;

  const rows = lines.length;

  const at = (col: number, row: number): string =>

    row < 0 || row >= rows || col < 0 || col >= cols ? "#" : lines[row]![col]!;

  const solidTile = (col: number, row: number): boolean => at(col, row) === "#";

  const tileOf = (x: number, y: number): { col: number; row: number } => ({

    col: Math.floor(x / tile),

    row: Math.floor(y / tile),

  });

  const centreOf = (col: number, row: number): Point => ({

    x: col * tile + tile / 2,

    y: row * tile + tile / 2,

  });

  const solidAt = (x: number, y: number): boolean => {

    const t = tileOf(x, y);

    return solidTile(t.col, t.row);

  };

  const cellAt = (x: number, y: number): string => {

    const t = tileOf(x, y);

    return at(t.col, t.row);

  };

  const cellsOf = (mark: string): Point[] => {

    const out: Point[] = [];

    for (let row = 0; row < rows; row++)

      for (let col = 0; col < cols; col++) if (at(col, row) === mark) out.push(centreOf(col, row));

    return out;

  };

  const moveCircle = (x: number, y: number, dx: number, dy: number, r: number): Point =>

    slideCircle(x, y, dx, dy, r, solidTile, tile);

  const blockedCircle = (x: number, y: number, r: number): boolean => circleBlocked(x, y, r, solidTile, tile);

  /**

   * Does a wall stand between two points? Sampled every third of a tile: a

   * wall is a whole tile thick, so nothing is ever stepped over.

   */

  function wallBetween(a: Point, b: Point): boolean {

    const dx = b.x - a.x;

    const dy = b.y - a.y;

    const dist = Math.hypot(dx, dy);

    const steps = Math.ceil(dist / (tile / 3));

    for (let i = 1; i < steps; i++) {

      const t = i / steps;

      if (solidAt(a.x + dx * t, a.y + dy * t)) return true;

    }

    return false;

  }

  /** Where a shot stops: the first wall along the ray, or its full range. */

  function rayHitWall(from: Point, angle: number, range: number): Point {

    const dx = Math.cos(angle);

    const dy = Math.sin(angle);

    const step = tile / 4;

    for (let d = step; d <= range; d += step) {

      const x = from.x + dx * d;

      const y = from.y + dy * d;

      if (solidAt(x, y)) return { x: from.x + dx * (d - step), y: from.y + dy * (d - step) };

    }

    return { x: from.x + dx * range, y: from.y + dy * range };

  }

  // Walk distance from a goal tile, breadth-first over floor. Bots ask for it

  // every few ticks; the field for a goal is built once and kept for the round.

  const fields = new Map<number, Int32Array>();

  const clearPaths = (): void => void fields.clear();

  function field(goalCol: number, goalRow: number): Int32Array {

    const key = goalRow * cols + goalCol;

    const cached = fields.get(key);

    if (cached) return cached;

    const dist = new Int32Array(cols * rows).fill(-1);

    if (!solidTile(goalCol, goalRow)) {

      dist[key] = 0;

      const queue: number[] = [key];

      for (let head = 0; head < queue.length; head++) {

        const here = queue[head]!;

        const col = here % cols;

        const row = (here - col) / cols;

        const d = dist[here]!;

        for (const [dc, dr] of STEPS) {

          const nc = col + dc;

          const nr = row + dr;

          if (nc < 0 || nc >= cols || nr < 0 || nr >= rows) continue;

          const nk = nr * cols + nc;

          if (dist[nk] !== -1 || solidTile(nc, nr)) continue;

          dist[nk] = d + 1;

          queue.push(nk);

        }

      }

    }

    if (fields.size > 64) fields.clear();

    fields.set(key, dist);

    return dist;

  }

  /** Walk distance in tiles between two points, or -1 when unreachable. */

  function walkDistance(from: Point, to: Point): number {

    const f = tileOf(from.x, from.y);

    const g = tileOf(to.x, to.y);

    return field(g.col, g.row)[f.row * cols + f.col] ?? -1;

  }

  /**

   * The next point to walk toward on the way to a goal: the centre of the

   * neighbouring tile that is one step closer, so a walker rounds corners

   * instead of grinding into them.

   */

  function pathStep(from: Point, to: Point): Point {

    const f = tileOf(from.x, from.y);

    const g = tileOf(to.x, to.y);

    if (f.col === g.col && f.row === g.row) return to;

    const dist = field(g.col, g.row);

    const here = dist[f.row * cols + f.col] ?? -1;

    if (here <= 0) return to;

    let best: Point | null = null;

    let bestD = here;

    for (const [dc, dr] of STEPS) {

      const nc = f.col + dc;

      const nr = f.row + dr;

      if (nc < 0 || nc >= cols || nr < 0 || nr >= rows) continue;

      const d = dist[nr * cols + nc] ?? -1;

      if (d !== -1 && d < bestD) {

        bestD = d;

        best = centreOf(nc, nr);

      }

    }

    // Straight to the goal when nothing stands in the way — smoother than

    // walking tile centre to tile centre down an open corridor.

    if (best && !wallBetween(from, to) && (walkDistance(from, to) ?? 99) < 6) return to;

    return best ?? to;

  }

  return {

    lines,

    cols,

    rows,

    tile,

    width: cols * tile,

    height: rows * tile,

    at,

    solidTile,

    tileOf,

    centreOf,

    solidAt,

    cellAt,

    cellsOf,

    moveCircle,

    blockedCircle,

    wallBetween,

    rayHitWall,

    walkDistance,

    pathStep,

    clearPaths,

  };

}