thalassa_navigationGrid.js

import { MaterialInteraction } from "../sim/materialRegistry.js";

/**
 * Priority queue (min-heap) for A* pathfinding.
 */
class MinHeap {
    constructor() {
        this._heap = [];
    }

    /**
     * @returns {number} Number of items in heap.
     */
    get size() {
        return this._heap.length;
    }

    /**
     * @returns {boolean} True if empty.
     */
    isEmpty() {
        return this._heap.length === 0;
    }

    /**
     * Push an item into the priority queue.
     * @param {Object} item - Heap item with f, h, and order properties.
     */
    push(item) {
        this._heap.push(item);
        this._bubbleUp(this._heap.length - 1);
    }

    /**
     * Remove and return the lowest-cost item.
     * @returns {Object|null} Lowest cost item, or null if empty.
     */
    pop() {
        if (this._heap.length === 0) return null;
        const top = this._heap[0];
        const last = this._heap.pop();
        if (this._heap.length > 0 && last !== undefined) {
            this._heap[0] = last;
            this._sinkDown(0);
        }
        return top;
    }

    /**
     * @private
     */
    _compare(a, b) {
        if (a.f !== b.f) return a.f - b.f;
        if (a.h !== b.h) return a.h - b.h;
        return a.order - b.order;
    }

    /**
     * @private
     */
    _bubbleUp(index) {
        const item = this._heap[index];
        while (index > 0) {
            const parentIndex = (index - 1) >> 1;
            const parent = this._heap[parentIndex];
            if (this._compare(item, parent) >= 0) break;
            this._heap[index] = parent;
            index = parentIndex;
        }
        this._heap[index] = item;
    }

    /**
     * @private
     */
    _sinkDown(index) {
        const item = this._heap[index];
        const length = this._heap.length;
        const halfLength = length >> 1;

        while (index < halfLength) {
            const leftChild = (index << 1) + 1;
            const rightChild = leftChild + 1;
            let bestChild = leftChild;

            if (rightChild < length && this._compare(this._heap[rightChild], this._heap[leftChild]) < 0) {
                bestChild = rightChild;
            }

            if (this._compare(item, this._heap[bestChild]) <= 0) break;

            this._heap[index] = this._heap[bestChild];
            index = bestChild;
        }
        this._heap[index] = item;
    }
}

/**
 * Result returned by NavigationGrid pathfinding.
 * Extends Array so it can be iterated directly, indexed by number, or inspected via properties.
 * @class NavigationPath
 * @extends Array
 */
export class NavigationPath extends Array {
    /**
     * Ensure built-in Array methods like map/filter/slice return standard Arrays.
     * @returns {Function}
     */
    static get [Symbol.species]() {
        return Array;
    }

    /**
     * @param {Object|Array|number} [options] - Result options, steps array, or length
     * @param {string} [options.status] - "success", "unreachable", "out_of_bounds", or "same_start_goal"
     * @param {boolean} [options.success] - Whether a valid path was found
     * @param {Array} [options.path] - List of { x, y } steps
     * @param {number} [options.cost] - Total traversal cost
     * @param {number} [options.visitedNodes] - Nodes expanded during search
     */
    constructor(options = {}) {
        let steps = [];
        let opts = {};

        if (Array.isArray(options)) {
            steps = options;
            opts = { success: true, status: "success" };
        } else if (typeof options === "number") {
            super(options);
            this.status = "unreachable";
            this.success = false;
            this.cost = Infinity;
            this.visitedNodes = 0;
            this.path = this;
            return;
        } else if (typeof options === "object" && options !== null) {
            steps = options.path || [];
            opts = options;
        }

        super(...steps);
        this.status = opts.status || (opts.success ? "success" : "unreachable");
        this.success = Boolean(opts.success);
        this.cost = Number.isFinite(opts.cost) ? opts.cost : (this.success ? 0 : Infinity);
        this.visitedNodes = opts.visitedNodes || 0;
        this.path = this;
    }

    /**
     * Whether pathfinding succeeded.
     * @returns {boolean}
     */
    isSuccess() {
        return this.success;
    }

    /**
     * Whether goal was unreachable.
     * @returns {boolean}
     */
    isUnreachable() {
        return this.status === "unreachable";
    }

    /**
     * Whether start or goal was out of bounds.
     * @returns {boolean}
     */
    isOutOfBounds() {
        return this.status === "out_of_bounds";
    }

    /**
     * Whether start and goal are the same point.
     * @returns {boolean}
     */
    isSameStartGoal() {
        return this.status === "same_start_goal";
    }
}

/**
 * 2D navigation grid supporting weighted traversal costs, walkability flags,
 * elevation rules, dynamic obstacles, chunk boundary links, and A* pathfinding.
 * @class NavigationGrid
 */
export class NavigationGrid {
    /**
     * @param {number|Object} [widthOrOptions=10] - Width in tiles, or options object
     * @param {number} [height=10] - Height in tiles
     * @param {Object} [options={}] - Grid configuration options
     * @param {number} [options.defaultCost=1.0] - Default movement cost per cell
     * @param {boolean} [options.defaultWalkable=true] - Default walkability flag
     * @param {number} [options.defaultElevation=0] - Default elevation level
     * @param {number} [options.maxClimbHeight=1] - Maximum traversable height difference between adjacent cells
     * @param {boolean} [options.allowDiagonal=true] - Allow 8-way diagonal movement
     * @param {number} [options.diagonalCostMultiplier] - Multiplier for diagonal steps (default Math.SQRT2)
     */
    constructor(widthOrOptions = 10, height = 10, options = {}) {
        let width = 10;
        let h = 10;
        let opts = {};

        if (typeof widthOrOptions === "object" && widthOrOptions !== null) {
            opts = widthOrOptions;
            width = opts.width ?? 10;
            h = opts.height ?? 10;
        } else {
            width = widthOrOptions;
            h = height ?? 10;
            opts = options || {};
        }

        if (!Number.isInteger(width) || width <= 0 || !Number.isInteger(h) || h <= 0) {
            throw new TypeError("NavigationGrid width and height must be positive integers");
        }

        this.width = width;
        this.height = h;
        this.defaultCost = Number.isFinite(opts.defaultCost) && opts.defaultCost >= 1 ? opts.defaultCost : 1.0;
        this.defaultWalkable = opts.defaultWalkable !== false;
        this.defaultElevation = Number.isFinite(opts.defaultElevation) ? opts.defaultElevation : 0;
        this.maxClimbHeight = Number.isFinite(opts.maxClimbHeight) && opts.maxClimbHeight >= 0 ? opts.maxClimbHeight : 1;
        this.allowDiagonal = opts.allowDiagonal !== false;
        this.diagonalCostMultiplier = Number.isFinite(opts.diagonalCostMultiplier) && opts.diagonalCostMultiplier > 0
            ? opts.diagonalCostMultiplier
            : Math.SQRT2;

        const size = width * h;
        this._walkable = new Uint8Array(size).fill(this.defaultWalkable ? 1 : 0);
        this._cost = new Float32Array(size).fill(this.defaultCost);
        this._elevation = new Float32Array(size).fill(this.defaultElevation);

        // Dynamic obstacles
        this._obstacles = new Map();
        this._obstacleCells = new Map();
        this._nextObstacleId = 0;

        // Chunk links / portals
        this._chunkLinks = new Map();
        this._chunkLinksById = new Map();
        this._nextLinkId = 0;

        // Route monitoring & invalidation
        this.routeVersion = 0;
        this._registeredRoutes = new Map();
        this._invalidationListeners = new Set();
    }

    /**
     * Map (x, y) to a flat array index.
     * @private
     * @param {number} x
     * @param {number} y
     * @returns {number} Array index, or -1 if out of bounds.
     */
    _index(x, y) {
        if (!Number.isInteger(x) || !Number.isInteger(y) || x < 0 || x >= this.width || y < 0 || y >= this.height) {
            return -1;
        }
        return y * this.width + x;
    }

    /**
     * Check whether (x, y) is inside the grid bounds.
     * @param {number} x
     * @param {number} y
     * @returns {boolean}
     */
    inBounds(x, y) {
        return Number.isInteger(x) && Number.isInteger(y) && x >= 0 && x < this.width && y >= 0 && y < this.height;
    }

    /**
     * Get cell properties at (x, y).
     * @param {number} x
     * @param {number} y
     * @returns {Object|null} Cell state or null if out of bounds.
     */
    getCell(x, y) {
        const idx = this._index(x, y);
        if (idx === -1) return null;
        return {
            x,
            y,
            walkable: this._walkable[idx] === 1,
            cost: this._cost[idx],
            elevation: this._elevation[idx],
            isBlockedByObstacle: this.isCellBlockedByObstacle(x, y),
            effectiveWalkable: this.isWalkable(x, y)
        };
    }

    /**
     * Set multiple cell properties at once.
     * @param {number} x
     * @param {number} y
     * @param {Object} [props={}]
     * @param {boolean} [props.walkable]
     * @param {number} [props.cost]
     * @param {number} [props.elevation]
     * @returns {boolean} True if in bounds.
     */
    setCell(x, y, props = {}) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        if (props.walkable !== undefined) {
            this._walkable[idx] = props.walkable ? 1 : 0;
        }
        if (Number.isFinite(props.cost) && props.cost >= 1) {
            this._cost[idx] = props.cost;
        }
        if (Number.isFinite(props.elevation)) {
            this._elevation[idx] = props.elevation;
        }
        this.routeVersion++;
        return true;
    }

    /**
     * Check if a cell is walkable and not blocked by dynamic obstacles.
     * @param {number} x
     * @param {number} y
     * @param {boolean} [checkObstacles=true] - Whether dynamic obstacles block walkability
     * @returns {boolean}
     */
    isWalkable(x, y, checkObstacles = true) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        if (this._walkable[idx] === 0) return false;
        if (checkObstacles && this._obstacleCells.has(idx) && this._obstacleCells.get(idx).size > 0) {
            return false;
        }
        return true;
    }

    /**
     * Set walkability flag for a cell.
     * @param {number} x
     * @param {number} y
     * @param {boolean} walkable
     * @returns {boolean} True if updated.
     */
    setWalkable(x, y, walkable) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        this._walkable[idx] = walkable ? 1 : 0;
        this.routeVersion++;
        return true;
    }

    /**
     * Get traversal cost for a cell.
     * @param {number} x
     * @param {number} y
     * @returns {number} Cost value (>= 1.0) or Infinity if out of bounds / unwalkable.
     */
    getCost(x, y) {
        const idx = this._index(x, y);
        if (idx === -1 || !this.isWalkable(x, y)) return Infinity;
        return this._cost[idx];
    }

    /**
     * Set traversal cost for a cell.
     * @param {number} x
     * @param {number} y
     * @param {number} cost - Movement cost (must be >= 1.0)
     * @returns {boolean} True if updated.
     */
    setCost(x, y, cost) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        const num = Number(cost);
        if (!Number.isFinite(num) || num < 1) {
            throw new RangeError(`Traversal cost must be a finite number >= 1.0, got ${cost}`);
        }
        this._cost[idx] = num;
        this.routeVersion++;
        return true;
    }

    /**
     * Get elevation level for a cell.
     * @param {number} x
     * @param {number} y
     * @returns {number|null} Elevation level or null if out of bounds.
     */
    getElevation(x, y) {
        const idx = this._index(x, y);
        if (idx === -1) return null;
        return this._elevation[idx];
    }

    /**
     * Set elevation level for a cell.
     * @param {number} x
     * @param {number} y
     * @param {number} elevation
     * @returns {boolean} True if updated.
     */
    setElevation(x, y, elevation) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        const num = Number(elevation);
        if (!Number.isFinite(num)) {
            throw new TypeError(`Elevation must be a finite number, got ${elevation}`);
        }
        this._elevation[idx] = num;
        this.routeVersion++;
        return true;
    }

    /**
     * Set cell properties based on material definitions from SIM-01.
     * @param {number} x
     * @param {number} y
     * @param {string} materialId - Material ID (e.g., 'water', 'grass', 'wood')
     * @param {string} [state='dry'] - Material state (e.g., 'dry', 'wet', 'frozen')
     * @param {Object} [registry] - Optional MaterialRegistry instance
     * @returns {boolean} True if set.
     */
    setCellMaterial(x, y, materialId, state = "dry", registry = null) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        let cost = 1.0;
        try {
            cost = MaterialInteraction.getEffectiveTraversalCost({ materialId, state, registry });
        } catch (_) {
            try {
                cost = MaterialInteraction.getEffectiveTraversalCost(materialId, state);
            } catch (_) {
                cost = 1.0;
            }
        }
        this._cost[idx] = Math.max(1.0, cost);
        this.routeVersion++;
        return true;
    }

    /**
     * Set maximum climb height difference between adjacent cells.
     * @param {number} height
     */
    setMaxClimbHeight(height) {
        const num = Number(height);
        if (!Number.isFinite(num) || num < 0) {
            throw new RangeError(`maxClimbHeight must be a finite number >= 0, got ${height}`);
        }
        this.maxClimbHeight = num;
        this.routeVersion++;
    }

    /**
     * Get maximum climb height difference.
     * @returns {number}
     */
    getMaxClimbHeight() {
        return this.maxClimbHeight;
    }

    // =========================================================================
    // Dynamic Obstacles
    // =========================================================================

    /**
     * Add a dynamic obstacle blocking one or more cells.
     * Supports both addObstacle(id, x, y, width, height) and addObstacle({ id, x, y, width, height, cells }).
     * @param {string|Object} idOrConfig
     * @param {number} [x=0]
     * @param {number} [y=0]
     * @param {number} [width=1]
     * @param {number} [height=1]
     * @returns {Object} The registered obstacle record.
     */
    addObstacle(idOrConfig, x = 0, y = 0, width = 1, height = 1) {
        let id;
        let obstacle;

        if (typeof idOrConfig === "object" && idOrConfig !== null) {
            obstacle = { ...idOrConfig };
            id = obstacle.id ? String(obstacle.id) : `obstacle_${++this._nextObstacleId}`;
        } else {
            id = String(idOrConfig || `obstacle_${++this._nextObstacleId}`);
            obstacle = { id, x, y, width, height };
        }

        if (this._obstacles.has(id)) {
            this.removeObstacle(id);
        }

        const blockedIndices = new Set();
        if (Array.isArray(obstacle.cells)) {
            for (const cell of obstacle.cells) {
                const cx = Array.isArray(cell) ? cell[0] : cell.x;
                const cy = Array.isArray(cell) ? cell[1] : cell.y;
                const idx = this._index(cx, cy);
                if (idx !== -1) blockedIndices.add(idx);
            }
        } else {
            const ox = obstacle.x ?? 0;
            const oy = obstacle.y ?? 0;
            const ow = obstacle.width ?? 1;
            const oh = obstacle.height ?? 1;
            for (let row = 0; row < oh; row++) {
                for (let col = 0; col < ow; col++) {
                    const idx = this._index(ox + col, oy + row);
                    if (idx !== -1) blockedIndices.add(idx);
                }
            }
        }

        for (const idx of blockedIndices) {
            if (!this._obstacleCells.has(idx)) {
                this._obstacleCells.set(idx, new Set());
            }
            this._obstacleCells.get(idx).add(id);
        }

        const record = {
            id,
            ...obstacle,
            blockedIndices: Array.from(blockedIndices)
        };
        this._obstacles.set(id, record);

        this.routeVersion++;
        this._notifyInvalidation({ type: "obstacle_added", obstacle: record });
        return record;
    }

    /**
     * Remove a dynamic obstacle by ID.
     * @param {string} id
     * @returns {boolean} True if removed.
     */
    removeObstacle(id) {
        const key = String(id);
        const record = this._obstacles.get(key);
        if (!record) return false;

        for (const idx of record.blockedIndices) {
            const set = this._obstacleCells.get(idx);
            if (set) {
                set.delete(key);
                if (set.size === 0) {
                    this._obstacleCells.delete(idx);
                }
            }
        }

        this._obstacles.delete(key);
        this.routeVersion++;
        this._notifyInvalidation({ type: "obstacle_removed", obstacle: record });
        return true;
    }

    /**
     * Check if obstacle exists by ID.
     * @param {string} id
     * @returns {boolean}
     */
    hasObstacle(id) {
        return this._obstacles.has(String(id));
    }

    /**
     * Get obstacle by ID.
     * @param {string} id
     * @returns {Object|null}
     */
    getObstacle(id) {
        return this._obstacles.get(String(id)) || null;
    }

    /**
     * Get all active obstacles.
     * @returns {Object[]}
     */
    getObstacles() {
        return Array.from(this._obstacles.values());
    }

    /**
     * Remove all dynamic obstacles.
     */
    clearObstacles() {
        this._obstacles.clear();
        this._obstacleCells.clear();
        this.routeVersion++;
        this._notifyInvalidation({ type: "obstacles_cleared" });
    }

    /**
     * Check if a specific cell is blocked by dynamic obstacles.
     * @param {number} x
     * @param {number} y
     * @returns {boolean}
     */
    isCellBlockedByObstacle(x, y) {
        const idx = this._index(x, y);
        if (idx === -1) return false;
        return this._obstacleCells.has(idx) && this._obstacleCells.get(idx).size > 0;
    }

    // =========================================================================
    // Chunk Links / Portals
    // =========================================================================

    /**
     * Add a chunk link or portal connecting two coordinates.
     * Supports both addChunkLink(fromX, fromY, toX, toY, options) and addChunkLink({ from, to, cost, bidirectional, id }).
     * @param {number|Object} linkOrFromX
     * @param {number} [fromY]
     * @param {number} [toX]
     * @param {number} [toY]
     * @param {Object} [options={}]
     * @returns {Object} The created chunk link.
     */
    addChunkLink(linkOrFromX, fromY, toX, toY, options = {}) {
        let link;
        if (typeof linkOrFromX === "object" && linkOrFromX !== null) {
            link = { ...linkOrFromX };
        } else {
            link = {
                from: { x: linkOrFromX, y: fromY },
                to: { x: toX, y: toY },
                ...options
            };
        }

        if (!link.id) {
            link.id = `link_${++this._nextLinkId}`;
        }
        link.cost = Number.isFinite(link.cost) && link.cost >= 0 ? link.cost : 1.0;
        link.bidirectional = link.bidirectional !== false;
        link.enabled = link.enabled !== false;

        link.from = { x: Math.floor(link.from.x), y: Math.floor(link.from.y) };
        link.to = { x: Math.floor(link.to.x), y: Math.floor(link.to.y) };

        const fromIdx = this._index(link.from.x, link.from.y);
        if (fromIdx !== -1) {
            if (!this._chunkLinks.has(fromIdx)) {
                this._chunkLinks.set(fromIdx, []);
            }
            this._chunkLinks.get(fromIdx).push(link);
        }

        if (link.bidirectional) {
            const toIdx = this._index(link.to.x, link.to.y);
            if (toIdx !== -1) {
                const reverseLink = {
                    id: `${link.id}_reverse`,
                    from: { x: link.to.x, y: link.to.y },
                    to: { x: link.from.x, y: link.from.y },
                    cost: link.cost,
                    bidirectional: false,
                    enabled: link.enabled,
                    isReverse: true,
                    parentLinkId: link.id
                };
                if (!this._chunkLinks.has(toIdx)) {
                    this._chunkLinks.set(toIdx, []);
                }
                this._chunkLinks.get(toIdx).push(reverseLink);
            }
        }

        this._chunkLinksById.set(link.id, link);
        this.routeVersion++;
        this._notifyInvalidation({ type: "chunk_link_added", link });
        return link;
    }

    /**
     * Alias for addChunkLink.
     * @param {number|Object} linkOrFromX
     * @param {number} [fromY]
     * @param {number} [toX]
     * @param {number} [toY]
     * @param {Object} [options={}]
     * @returns {Object}
     */
    addPortal(linkOrFromX, fromY, toX, toY, options = {}) {
        return this.addChunkLink(linkOrFromX, fromY, toX, toY, options);
    }

    /**
     * Remove a chunk link by ID.
     * @param {string} id
     * @returns {boolean} True if removed.
     */
    removeChunkLink(id) {
        const link = this._chunkLinksById.get(id);
        if (!link) return false;

        const fromIdx = this._index(link.from.x, link.from.y);
        if (fromIdx !== -1 && this._chunkLinks.has(fromIdx)) {
            const list = this._chunkLinks.get(fromIdx).filter((l) => l.id !== id);
            if (list.length === 0) this._chunkLinks.delete(fromIdx);
            else this._chunkLinks.set(fromIdx, list);
        }

        if (link.bidirectional) {
            const revId = `${id}_reverse`;
            const toIdx = this._index(link.to.x, link.to.y);
            if (toIdx !== -1 && this._chunkLinks.has(toIdx)) {
                const list = this._chunkLinks.get(toIdx).filter((l) => l.id !== revId);
                if (list.length === 0) this._chunkLinks.delete(toIdx);
                else this._chunkLinks.set(toIdx, list);
            }
        }

        this._chunkLinksById.delete(id);
        this.routeVersion++;
        this._notifyInvalidation({ type: "chunk_link_removed", linkId: id });
        return true;
    }

    /**
     * Get outgoing chunk links from coordinate (x, y).
     * @param {number} x
     * @param {number} y
     * @returns {Object[]}
     */
    getChunkLinks(x, y) {
        const idx = this._index(x, y);
        if (idx === -1 || !this._chunkLinks.has(idx)) return [];
        return this._chunkLinks.get(idx).filter((l) => l.enabled !== false);
    }

    /**
     * Clear all chunk links.
     */
    clearChunkLinks() {
        this._chunkLinks.clear();
        this._chunkLinksById.clear();
        this.routeVersion++;
        this._notifyInvalidation({ type: "chunk_links_cleared" });
    }

    // =========================================================================
    // Route Validation and Invalidation
    // =========================================================================

    /**
     * Validate whether an existing path remains walkable and unbroken.
     * @param {Array} path - Sequence of { x, y } step objects
     * @param {Object} [options={}] - Validation options
     * @returns {Object} Validation report { valid, blockedIndex, blockedCell, reason }
     */
    validateRoute(path, options = {}) {
        if (!Array.isArray(path) || path.length === 0) {
            return { valid: true, blockedIndex: -1, blockedCell: null, reason: null };
        }
        const maxClimb = Number.isFinite(options.maxClimbHeight) ? options.maxClimbHeight : this.maxClimbHeight;
        const preventCornerCutting = options.preventCornerCutting !== false;

        for (let i = 0; i < path.length; i++) {
            const step = path[i];
            if (!this.inBounds(step.x, step.y)) {
                return { valid: false, blockedIndex: i, blockedCell: step, reason: "out_of_bounds" };
            }
            if (!this.isWalkable(step.x, step.y)) {
                return {
                    valid: false,
                    blockedIndex: i,
                    blockedCell: step,
                    reason: this.isCellBlockedByObstacle(step.x, step.y) ? "obstacle_blocked" : "cell_unwalkable"
                };
            }

            if (i > 0) {
                const prev = path[i - 1];
                if (step.isChunkLink) {
                    continue;
                }

                const dx = step.x - prev.x;
                const dy = step.y - prev.y;

                const elevDiff = Math.abs(this.getElevation(step.x, step.y) - this.getElevation(prev.x, prev.y));
                if (elevDiff > maxClimb) {
                    return { valid: false, blockedIndex: i, blockedCell: step, reason: "climb_limit_exceeded" };
                }

                if (dx !== 0 && dy !== 0 && preventCornerCutting) {
                    if (!this.isWalkable(prev.x + dx, prev.y) || !this.isWalkable(prev.x, prev.y + dy)) {
                        return { valid: false, blockedIndex: i, blockedCell: step, reason: "corner_cutting_blocked" };
                    }
                }
            }
        }
        return { valid: true, blockedIndex: -1, blockedCell: null, reason: null };
    }

    /**
     * Check if an existing path remains valid.
     * @param {Array} path - Array of { x, y }
     * @param {Object} [options={}]
     * @returns {boolean}
     */
    isRouteValid(path, options = {}) {
        return this.validateRoute(path, options).valid;
    }

    /**
     * Register a route to monitor for invalidation when obstacles change.
     * @param {string} id - Identifier for the route
     * @param {Array} path - Array of { x, y } steps
     */
    registerRoute(id, path) {
        this._registeredRoutes.set(String(id), {
            id: String(id),
            path: Array.from(path),
            registeredVersion: this.routeVersion
        });
    }

    /**
     * Unregister a monitored route.
     * @param {string} id
     * @returns {boolean} True if removed.
     */
    unregisterRoute(id) {
        return this._registeredRoutes.delete(String(id));
    }

    /**
     * Get a registered route by ID.
     * @param {string} id
     * @returns {Array|null}
     */
    getRegisteredRoute(id) {
        const entry = this._registeredRoutes.get(String(id));
        return entry ? entry.path : null;
    }

    /**
     * Query which registered routes are currently invalid.
     * @returns {string[]} List of invalidated route IDs.
     */
    getInvalidatedRoutes() {
        const invalidated = [];
        for (const [id, entry] of this._registeredRoutes) {
            if (!this.isRouteValid(entry.path)) {
                invalidated.push(id);
            }
        }
        return invalidated;
    }

    /**
     * Explicitly invalidate routes and increment version.
     * @returns {string[]} IDs of registered routes that are invalid.
     */
    invalidateRoutes() {
        this.routeVersion++;
        const invalidated = this.getInvalidatedRoutes();
        this._notifyInvalidation({ type: "routes_invalidated", invalidatedRoutes: invalidated });
        return invalidated;
    }

    /**
     * Subscribe to route invalidation events.
     * @param {Function} callback - Event listener
     * @returns {Function} Unsubscribe function
     */
    onRouteInvalidated(callback) {
        if (typeof callback === "function") {
            this._invalidationListeners.add(callback);
        }
        return () => this.offRouteInvalidated(callback);
    }

    /**
     * Remove an invalidation listener.
     * @param {Function} callback
     */
    offRouteInvalidated(callback) {
        this._invalidationListeners.delete(callback);
    }

    /**
     * @private
     */
    _notifyInvalidation(event) {
        if (this._invalidationListeners.size === 0) return;
        for (const listener of this._invalidationListeners) {
            try {
                listener({ ...event, version: this.routeVersion });
            } catch (_) {
                // Ignore listener exceptions
            }
        }
    }

    // =========================================================================
    // A* Pathfinding
    // =========================================================================

    /**
     * Compute the lowest-cost path from start to goal using A*.
     * Supports both findPath(start, goal, options) and findPath(startX, startY, goalX, goalY, options).
     * @param {Object|Array|number} startArg - Starting point { x, y }, [x, y], or startX number
     * @param {Object|Array|number} goalArg - Goal point { x, y }, [x, y], or startY number
     * @param {Object|number} [optionsOrGoalX] - Options object, or goalX number
     * @param {number} [goalY] - goalY number if coordinates were passed numerically
     * @param {Object} [options] - Options object if coordinates were passed numerically
     * @param {boolean} [options.allowDiagonal] - Allow diagonal steps (default this.allowDiagonal)
     * @param {boolean} [options.preventCornerCutting=true] - Strict corner-cutting prevention past solid walls
     * @param {number} [options.maxClimbHeight] - Max traversable height diff (default this.maxClimbHeight)
     * @param {number} [options.diagonalCostMultiplier] - Multiplier for diagonal steps
     * @param {boolean} [options.includeStart=false] - Whether to include the starting tile in the path
     * @param {boolean} [options.useChunkLinks=true] - Whether to traverse chunk links/portals
     * @param {number} [options.maxCost] - Search cost cutoff limit
     * @param {Function} [options.isWalkable] - Custom walkability predicate (x, y) => boolean
     * @returns {NavigationPath} Path result containing status, success, cost, and steps.
     */
    findPath(startArg, goalArg, optionsOrGoalX, goalY, options) {
        let start = null;
        let goal = null;
        let opts = {};

        if (
            typeof startArg === "number" &&
            typeof goalArg === "number" &&
            typeof optionsOrGoalX === "number" &&
            typeof goalY === "number"
        ) {
            start = { x: Math.floor(startArg), y: Math.floor(goalArg) };
            goal = { x: Math.floor(optionsOrGoalX), y: Math.floor(goalY) };
            opts = options || {};
        } else {
            const normalize = (pt) => {
                if (!pt) return null;
                if (Array.isArray(pt)) return { x: Math.floor(pt[0]), y: Math.floor(pt[1]) };
                if (typeof pt === "object" && Number.isFinite(pt.x) && Number.isFinite(pt.y)) {
                    return { x: Math.floor(pt.x), y: Math.floor(pt.y) };
                }
                return null;
            };
            start = normalize(startArg);
            goal = normalize(goalArg);
            opts = (typeof optionsOrGoalX === "object" && optionsOrGoalX !== null) ? optionsOrGoalX : (options || {});
        }

        // Edge case: out of bounds start or goal returns safely without throwing
        if (!start || !goal || !this.inBounds(start.x, start.y) || !this.inBounds(goal.x, goal.y)) {
            return new NavigationPath({
                status: "out_of_bounds",
                success: false,
                path: [],
                cost: Infinity,
                visitedNodes: 0
            });
        }

        // Edge case: same start and goal returns immediately
        if (start.x === goal.x && start.y === goal.y) {
            const path = opts.includeStart ? [{ x: start.x, y: start.y, cost: 0 }] : [];
            return new NavigationPath({
                status: "same_start_goal",
                success: true,
                path,
                cost: 0,
                visitedNodes: 0
            });
        }

        const customWalkable = typeof opts.isWalkable === "function" ? opts.isWalkable : null;
        const isTileWalkable = (tx, ty) => {
            if (customWalkable) return customWalkable(tx, ty);
            return this.isWalkable(tx, ty);
        };

        // Edge case: start or goal cell is not walkable
        if (!isTileWalkable(start.x, start.y) || !isTileWalkable(goal.x, goal.y)) {
            return new NavigationPath({
                status: "unreachable",
                success: false,
                path: [],
                cost: Infinity,
                visitedNodes: 0
            });
        }

        const allowDiagonal = opts.allowDiagonal !== undefined ? Boolean(opts.allowDiagonal) : this.allowDiagonal;
        const preventCornerCutting = opts.preventCornerCutting !== false;
        const maxClimb = Number.isFinite(opts.maxClimbHeight) ? opts.maxClimbHeight : this.maxClimbHeight;
        const diagMultiplier = Number.isFinite(opts.diagonalCostMultiplier)
            ? opts.diagonalCostMultiplier
            : this.diagonalCostMultiplier;
        const useChunkLinks = opts.useChunkLinks !== false;
        const maxCost = Number.isFinite(opts.maxCost) ? opts.maxCost : Infinity;

        const baseDistance = (x1, y1, x2, y2) => {
            const dx = Math.abs(x1 - x2);
            const dy = Math.abs(y1 - y2);
            if (allowDiagonal) {
                const minD = Math.min(dx, dy);
                const maxD = Math.max(dx, dy);
                return minD * diagMultiplier + (maxD - minD);
            }
            return dx + dy;
        };

        const activePortals = [];
        if (useChunkLinks && this._chunkLinks.size > 0) {
            for (const linkList of this._chunkLinks.values()) {
                for (let i = 0; i < linkList.length; i++) {
                    const l = linkList[i];
                    if (l.enabled !== false && this.inBounds(l.to.x, l.to.y) && isTileWalkable(l.to.x, l.to.y)) {
                        activePortals.push({
                            from: l.from,
                            to: l.to,
                            cost: l.cost,
                            toGoal: baseDistance(l.to.x, l.to.y, goal.x, goal.y) + l.cost
                        });
                    }
                }
            }
        }

        // Admissible heuristic function (portal-aware)
        const heuristic = (x, y) => {
            let minH = baseDistance(x, y, goal.x, goal.y);
            for (let p = 0; p < activePortals.length; p++) {
                const port = activePortals[p];
                const via = baseDistance(x, y, port.from.x, port.from.y) + port.toGoal;
                if (via < minH) minH = via;
            }
            return minH;
        };

        const startIdx = this._index(start.x, start.y);
        const goalIdx = this._index(goal.x, goal.y);

        const queue = new MinHeap();
        const gScores = new Map();
        const cameFrom = new Map();
        const closedSet = new Set();
        let insertionOrder = 0;
        let visitedNodesCount = 0;

        gScores.set(startIdx, 0);
        const startH = heuristic(start.x, start.y);
        queue.push({
            index: startIdx,
            x: start.x,
            y: start.y,
            g: 0,
            h: startH,
            f: startH,
            order: insertionOrder++
        });

        // 8-way and 4-way direction vectors
        const directions = allowDiagonal
            ? [
                [0, -1], [1, 0], [0, 1], [-1, 0],
                [-1, -1], [1, -1], [1, 1], [-1, 1]
            ]
            : [
                [0, -1], [1, 0], [0, 1], [-1, 0]
            ];

        while (!queue.isEmpty()) {
            const current = queue.pop();
            if (!current) break;

            if (closedSet.has(current.index)) continue;
            if (current.g > (gScores.get(current.index) ?? Infinity)) continue;

            closedSet.add(current.index);
            visitedNodesCount++;

            // Reached goal!
            if (current.index === goalIdx) {
                const steps = [];
                let stepIdx = current.index;

                while (stepIdx !== startIdx) {
                    const edge = cameFrom.get(stepIdx);
                    if (!edge) break;
                    const stepObj = {
                        x: edge.toX,
                        y: edge.toY,
                        cost: edge.stepCost
                    };
                    if (edge.isChunkLink) {
                        stepObj.isChunkLink = true;
                        if (edge.linkId) stepObj.linkId = edge.linkId;
                    }
                    steps.push(stepObj);
                    stepIdx = edge.fromIdx;
                }

                if (opts.includeStart) {
                    steps.push({ x: start.x, y: start.y, cost: 0 });
                }

                steps.reverse();

                return new NavigationPath({
                    status: "success",
                    success: true,
                    path: steps,
                    cost: current.g,
                    visitedNodes: visitedNodesCount
                });
            }

            // 1. Chunk links / portals originating from current cell
            if (useChunkLinks) {
                const links = this.getChunkLinks(current.x, current.y);
                for (let i = 0; i < links.length; i++) {
                    const link = links[i];
                    const tx = link.to.x;
                    const ty = link.to.y;

                    if (!this.inBounds(tx, ty) || !isTileWalkable(tx, ty)) continue;
                    const tIdx = this._index(tx, ty);
                    if (closedSet.has(tIdx)) continue;

                    const stepCost = link.cost;
                    const tentG = current.g + stepCost;
                    if (tentG > maxCost) continue;

                    if (tentG < (gScores.get(tIdx) ?? Infinity)) {
                        gScores.set(tIdx, tentG);
                        cameFrom.set(tIdx, {
                            fromIdx: current.index,
                            toX: tx,
                            toY: ty,
                            stepCost,
                            isChunkLink: true,
                            linkId: link.id
                        });
                        const h = heuristic(tx, ty);
                        queue.push({
                            index: tIdx,
                            x: tx,
                            y: ty,
                            g: tentG,
                            h,
                            f: tentG + h,
                            order: insertionOrder++
                        });
                    }
                }
            }

            // 2. Adjacent grid neighbors
            for (let d = 0; d < directions.length; d++) {
                const [dx, dy] = directions[d];
                const nx = current.x + dx;
                const ny = current.y + dy;

                if (!this.inBounds(nx, ny)) continue;
                if (!isTileWalkable(nx, ny)) continue;

                const nIdx = this._index(nx, ny);
                if (closedSet.has(nIdx)) continue;

                // Elevation rule: traversal between adjacent cells blocked if difference exceeds maxClimbHeight
                const elevDiff = Math.abs(this._elevation[nIdx] - this._elevation[current.index]);
                if (elevDiff > maxClimb) continue;

                // Diagonal movement: strict corner-cutting prevention past solid walls
                const isDiagonal = (dx !== 0 && dy !== 0);
                if (isDiagonal && preventCornerCutting) {
                    const ortho1 = isTileWalkable(current.x + dx, current.y);
                    const ortho2 = isTileWalkable(current.x, current.y + dy);
                    if (!ortho1 || !ortho2) {
                        continue;
                    }
                }

                // Movement cost affects path weighting
                const distance = isDiagonal ? diagMultiplier : 1.0;
                const cellCost = this._cost[nIdx];
                const stepCost = distance * cellCost;

                const tentG = current.g + stepCost;
                if (tentG > maxCost) continue;

                if (tentG < (gScores.get(nIdx) ?? Infinity)) {
                    gScores.set(nIdx, tentG);
                    cameFrom.set(nIdx, {
                        fromIdx: current.index,
                        toX: nx,
                        toY: ny,
                        stepCost,
                        isChunkLink: false
                    });
                    const h = heuristic(nx, ny);
                    queue.push({
                        index: nIdx,
                        x: nx,
                        y: ny,
                        g: tentG,
                        h,
                        f: tentG + h,
                        order: insertionOrder++
                    });
                }
            }
        }

        // Unreachable goal returns unreachable status
        return new NavigationPath({
            status: "unreachable",
            success: false,
            path: [],
            cost: Infinity,
            visitedNodes: visitedNodesCount
        });
    }

    /**
     * Create a clone of this NavigationGrid.
     * @returns {NavigationGrid}
     */
    clone() {
        const copy = new NavigationGrid(this.width, this.height, {
            defaultCost: this.defaultCost,
            defaultWalkable: this.defaultWalkable,
            defaultElevation: this.defaultElevation,
            maxClimbHeight: this.maxClimbHeight,
            allowDiagonal: this.allowDiagonal,
            diagonalCostMultiplier: this.diagonalCostMultiplier
        });
        copy._walkable.set(this._walkable);
        copy._cost.set(this._cost);
        copy._elevation.set(this._elevation);

        for (const [id, obs] of this._obstacles) {
            copy.addObstacle({ ...obs });
        }
        for (const [id, link] of this._chunkLinksById) {
            copy.addChunkLink({ ...link });
        }
        return copy;
    }

    /**
     * Construct a NavigationGrid from a Thalassa Tilemap.
     * @param {Object} tilemap - Tilemap instance
     * @param {Object} [options={}] - Grid options
     * @returns {NavigationGrid}
     */
    static fromTilemap(tilemap, options = {}) {
        if (!tilemap || typeof tilemap.width !== "number" || typeof tilemap.height !== "number") {
            throw new TypeError("fromTilemap requires a Tilemap instance with width and height");
        }
        const grid = new NavigationGrid(tilemap.width, tilemap.height, options);
        for (let y = 0; y < tilemap.height; y++) {
            for (let x = 0; x < tilemap.width; x++) {
                const meta = typeof tilemap.getResolvedMetadata === "function"
                    ? tilemap.getResolvedMetadata(x, y)
                    : null;
                if (meta) {
                    if (meta.walkable !== undefined) {
                        grid.setWalkable(x, y, meta.walkable);
                    }
                    if (Number.isFinite(meta.movementCost) && meta.movementCost >= 1) {
                        grid.setCost(x, y, meta.movementCost);
                    }
                    if (Number.isFinite(meta.elevation)) {
                        grid.setElevation(x, y, meta.elevation);
                    }
                }
            }
        }
        return grid;
    }

    /**
     * Construct a NavigationGrid from an ASCII layout.
     * Legend maps characters to properties like { walkable, cost, elevation }.
     * @param {string} ascii - Multiline text representation of the grid
     * @param {Object} [legend={}] - Mapping from character to cell properties
     * @param {Object} [options={}] - Grid options
     * @returns {NavigationGrid}
     */
    static fromAscii(ascii, legend = {}, options = {}) {
        if (typeof ascii !== "string") {
            throw new TypeError("fromAscii expects an ASCII string");
        }
        const rawLines = ascii
            .split("\n")
            .filter((line) => line.trim().length > 0);

        if (rawLines.length === 0) {
            throw new Error("fromAscii received empty grid string");
        }

        let minIndent = Infinity;
        for (let i = 0; i < rawLines.length; i++) {
            const match = rawLines[i].match(/^(\s*)/);
            if (match) {
                minIndent = Math.min(minIndent, match[1].length);
            }
        }
        if (!Number.isFinite(minIndent)) minIndent = 0;

        const lines = rawLines.map((line) => line.slice(minIndent).trimEnd());
        const height = lines.length;
        const width = Math.max(...lines.map((l) => l.length));

        const grid = new NavigationGrid(width, height, options);
        for (let y = 0; y < height; y++) {
            const line = lines[y];
            for (let x = 0; x < width; x++) {
                const ch = line[x] || " ";
                const def = legend[ch];
                if (def) {
                    if (def.walkable !== undefined) grid.setWalkable(x, y, def.walkable);
                    if (def.cost !== undefined) grid.setCost(x, y, def.cost);
                    if (def.elevation !== undefined) grid.setElevation(x, y, def.elevation);
                } else if (ch === "#") {
                    grid.setWalkable(x, y, false);
                }
            }
        }
        return grid;
    }
}