domain/converters/learning.grid.converter.ts

domain/converters/learning.grid.converter.ts is a file in Bane's Lab Site. 120 lines of code and 36 definitions.

import { CROSSING_COST, GRID_STEP } from "#configuration/constants/learning.constants";
import type { LearningGrid, LearningModel, LearningPoint } from "#types/learning.types";

const NEIGHBORS: readonly (readonly [number, number])[] = [
    [0, 1],
    [1, 0],
    [-1, 0],
    [0, -1],
];

const MARGIN = 2;

interface Visit {
    readonly cell: number;
    readonly spent: number;
}

export const gridFor = function gridFor(model: LearningModel): LearningGrid {
    const wide = Math.ceil(model.width / GRID_STEP) + MARGIN;
    const tall = Math.ceil(model.height / GRID_STEP) + MARGIN;
    const blocked = new Uint8Array(wide * tall);
    for (const block of model.blocks) {
        const x0 = Math.max(0, Math.floor((block.x - MARGIN) / GRID_STEP));
        const x1 = Math.min(wide - 1, Math.ceil((block.x + block.width + MARGIN) / GRID_STEP));
        const y0 = Math.max(0, Math.floor((block.y - MARGIN) / GRID_STEP));
        const y1 = Math.min(tall - 1, Math.ceil((block.y + block.height + MARGIN) / GRID_STEP));
        for (let cy = y0; cy <= y1; cy += 1) {
            for (let cx = x0; cx <= x1; cx += 1) {
                blocked[cy * wide + cx] = 1;
            }
        }
    }
    return { blocked, taken: new Uint8Array(wide * tall), tall, wide };
};

export const cellAt = function cellAt(grid: LearningGrid, point: LearningPoint): number {
    return Math.round(point.y / GRID_STEP) * grid.wide + Math.round(point.x / GRID_STEP);
};

export const isSolid = function isSolid(grid: LearningGrid, point: LearningPoint): boolean {
    const cx = Math.round(point.x / GRID_STEP);
    const cy = Math.round(point.y / GRID_STEP);
    if (cx < 0 || cy < 0 || cx >= grid.wide || cy >= grid.tall) {
        return true;
    }
    return grid.blocked[cy * grid.wide + cx] === 1;
};

const cheapestOf = function cheapestOf(heap: readonly Visit[]): number {
    let pick = 0;
    for (let scan = 1; scan < heap.length; scan += 1) {
        if ((heap[scan]?.spent ?? Infinity) < (heap[pick]?.spent ?? Infinity)) {
            pick = scan;
        }
    }
    return pick;
};

const stepCost = function stepCost(grid: LearningGrid, cell: number, spent: number): number {
    return spent + (grid.taken[cell] === 1 ? CROSSING_COST : 1);
};

const neighbors = function neighbors(grid: LearningGrid, cell: number, goal: number): number[] {
    const cx = cell % grid.wide;
    const cy = Math.floor(cell / grid.wide);
    const found: number[] = [];
    for (const [dx, dy] of NEIGHBORS) {
        const nx = cx + dx;
        const ny = cy + dy;
        const inside = nx >= 0 && ny >= 0 && nx < grid.wide && ny < grid.tall;
        const step = ny * grid.wide + nx;
        if (inside && (grid.blocked[step] !== 1 || step === goal)) {
            found.push(step);
        }
    }
    return found;
};

interface Reached {
    readonly came: Int32Array;
    readonly cost: Float64Array;
}

const improvements = function improvements(
    grid: LearningGrid,
    reached: Reached,
    here: Visit,
    goal: number,
): readonly Visit[] {
    const better: Visit[] = [];
    for (const step of neighbors(grid, here.cell, goal)) {
        const spent = stepCost(grid, step, here.spent);
        if (spent < (reached.cost[step] ?? Infinity)) {
            reached.cost[step] = spent;
            reached.came[step] = here.cell;
            better.push({ cell: step, spent });
        }
    }
    return better;
};

export const searchGrid = function searchGrid(grid: LearningGrid, start: number, goal: number): Int32Array {
    const reached: Reached = {
        came: new Int32Array(grid.wide * grid.tall).fill(-1),
        cost: new Float64Array(grid.wide * grid.tall).fill(Infinity),
    };
    const heap: Visit[] = [{ cell: start, spent: 0 }];
    reached.came[start] = start;
    reached.cost[start] = 0;
    while (heap.length > 0) {
        const here = heap.splice(cheapestOf(heap), 1)[0] ?? { cell: start, spent: 0 };
        if (here.cell === goal) {
            break;
        }
        if (here.spent <= (reached.cost[here.cell] ?? Infinity)) {
            heap.push(...improvements(grid, reached, here, goal));
        }
    }
    return reached.came;
};

export const walkBack = function walkBack(grid: LearningGrid, came: Int32Array, start: number, goal: number): number[] {
    const back: number[] = [];
    let cursor = goal;
    while (cursor !== start) {
        back.push(cursor);
        grid.taken[cursor] = 1;
        cursor = came[cursor] ?? start;
    }
    back.push(start);
    grid.taken[start] = 1;
    return back.toReversed();
};