/*
File: swMaze.js
Date: 2026-03-18
Author: klp
Workspace: SWIslandRecurnSaga2026-03-16-Stg1
Purpose: SWMaze — a perfect maze (exactly one path between any two cells) built by
         recursive DFS and solved by recursive DFS backtracking.
         Mirrors the SWIsland/SWGrid pattern from the island saga.

=== Design ===
  A "perfect maze" is a grid where every cell is reachable from every other cell
  via exactly one path — no loops, no isolated regions.  This guarantees:
    • buildMaze() always produces a solvable maze.
    • solveMaze() always visits dead-end branches before the final solution path,
      making backtracking clearly visible.

=== Two Recursions ===
  1. GENERATION (build phase) — Recursive DFS carves walls:
       Visit an unvisited neighbor → carve the shared wall → recurse → backtrack.
       Records BUILD_CARVE and BUILD_BACKTRACK steps.

  2. SOLVING (solve phase) — Recursive DFS path finding:
       Try a reachable unvisited neighbor → recurse → if it fails, backtrack.
       Records SOLVE_TRY and SOLVE_BACKTRACK steps.
       On success records a SOLVE_SUCCESS step.

=== Cell Representation ===
  this._cells[r][c] = {
      walls: { N: bool, S: bool, E: bool, W: bool },  // true = wall present
      visited: bool                                     // scratch flag for DFS passes
  }
  All walls start as true (closed).  Generation carves them to false (open).

=== Step Queue Consumers ===
  The sketch consumes two step queues:
    getBuildStepQueue() → array of objects used to animate maze carving
    getSolveStepQueue() → array of objects used to animate maze solving

  Each step is a plain object { type, ... } — see STEP TYPES below.

=== STEP TYPES ===
  Build steps:
    { type: 'BUILD_CARVE',     fromRow, fromCol, toRow, toCol, dir }
      — wall between (fromRow,fromCol) and (toRow,toCol) was opened in direction dir.
    { type: 'BUILD_BACKTRACK', row, col }
      — DFS backed up to (row, col) after finishing all neighbors from there.

  Solve steps:
    { type: 'SOLVE_TRY',       row, col }
      — (row, col) is being added to the current path exploration.
    { type: 'SOLVE_BACKTRACK', row, col }
      — (row, col) was a dead end; removing from current path.
    { type: 'SOLVE_SUCCESS' }
      — The treasure cell has been reached; the current path IS the solution.

=== Direction Conventions ===
  N → row - 1 (up on screen, decreasing row index)
  S → row + 1 (down on screen, increasing row index)
  E → col + 1 (right)
  W → col - 1 (left)
*/

console.log("[swMaze.js] SWMaze class loaded.");

class SWMaze {

    // ── Direction table ───────────────────────────────────────────────────────
    //
    // Each entry: { dr, dc, wall, opposite }
    //   dr, dc     — row/col offset to reach the neighbor in this direction
    //   wall       — the wall key on THIS cell that faces the neighbor
    //   opposite   — the wall key on the NEIGHBOR cell that faces back
    static DIR = {
        N: { dr: -1, dc:  0, wall: 'N', opposite: 'S' },
        S: { dr:  1, dc:  0, wall: 'S', opposite: 'N' },
        E: { dr:  0, dc:  1, wall: 'E', opposite: 'W' },
        W: { dr:  0, dc: -1, wall: 'W', opposite: 'E' },
    };

    static DIRECTIONS = ['N', 'S', 'E', 'W'];

    // ── Constructor ───────────────────────────────────────────────────────────

    /**
     * Creates an ungenerated ROWS × COLS maze (all walls present).
     * Call generate() before using.
     *
     * @param {number} rows
     * @param {number} cols
     */
    constructor(rows, cols) {
        this._rows = rows;
        this._cols = cols;
        this._cells = this._makeBlankCells();
        this._buildStepQueue = [];
        this._solveStepQueue = [];
        this._solutionPath   = null;
        this._generated      = false;
    }//end constructor

    // ── Private factory: blank cell grid ─────────────────────────────────────

    _makeBlankCells() {
        return Array.from({ length: this._rows }, () =>
            Array.from({ length: this._cols }, () => ({
                walls:   { N: true, S: true, E: true, W: true },
                visited: false,
            }))
        );
    }//end _makeBlankCells

    // ── Getters ───────────────────────────────────────────────────────────────

    getRows()           { return this._rows;           }
    getCols()           { return this._cols;           }
    getCell(r, c)       { return this._cells[r][c];    }
    isGenerated()       { return this._generated;      }
    getSolutionPath()   { return this._solutionPath;   }
    getBuildStepQueue() { return this._buildStepQueue; }
    getSolveStepQueue() { return this._solveStepQueue; }

    /**
     * Returns true if the wall in direction dir is open (no wall) between
     * (r, c) and its neighbor.
     * @param {number} r @param {number} c @param {string} dir
     * @returns {boolean}
     */
    isOpen(r, c, dir) {
        return !this._cells[r][c].walls[dir];
    }//end isOpen

    // ── Private: Fisher-Yates shuffle ────────────────────────────────────────

    _shuffle(arr) {
        for (let i = arr.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
        return arr;
    }//end _shuffle

    // ── Private: bounds check ─────────────────────────────────────────────────

    _inBounds(r, c) {
        return r >= 0 && r < this._rows && c >= 0 && c < this._cols;
    }//end _inBounds

    // ── Generation: recursive DFS (private) ──────────────────────────────────

    /**
     * Recursive DFS maze carver.
     * Visits every unvisited neighbor in shuffled order, carving the shared wall.
     * Records BUILD_CARVE steps (wall opened) and BUILD_BACKTRACK steps (return).
     *
     * @param {number} r  Current row
     * @param {number} c  Current col
     */
    _generateDFS(r, c) {
        this._cells[r][c].visited = true;

        const dirs = this._shuffle([...SWMaze.DIRECTIONS]);

        for (const dir of dirs) {
            const { dr, dc, wall, opposite } = SWMaze.DIR[dir];
            const nr = r + dr;
            const nc = c + dc;

            if (!this._inBounds(nr, nc) || this._cells[nr][nc].visited) continue;

            // Carve: remove the shared wall between (r,c) and (nr,nc)
            this._cells[r][c].walls[wall]        = false;
            this._cells[nr][nc].walls[opposite]  = false;

            this._buildStepQueue.push({
                type:    'BUILD_CARVE',
                fromRow: r,  fromCol: c,
                toRow:   nr, toCol:   nc,
                dir:     dir,
            });

            this._generateDFS(nr, nc);

            // Record the backtrack step (DFS returns to this cell)
            this._buildStepQueue.push({
                type: 'BUILD_BACKTRACK',
                row:  r,
                col:  c,
            });
        }
    }//end _generateDFS

    // ── Public: generate ─────────────────────────────────────────────────────

    /**
     * Generates a perfect maze using recursive DFS starting from (startRow, startCol).
     * Resets all cells and rebuilds step queues on each call.
     * Resets visited flags after generation (for later solver use).
     *
     * @param {number} [startRow=0]
     * @param {number} [startCol=0]
     */
    generate(startRow = 0, startCol = 0) {
        // Full reset
        this._cells          = this._makeBlankCells();
        this._buildStepQueue = [];
        this._solveStepQueue = [];
        this._solutionPath   = null;
        this._generated      = false;

        // Carve the maze
        this._generateDFS(startRow, startCol);
        this._generated = true;

        // Reset visited flags for the solver
        this._clearVisited();
    }//end generate

    // ── Private: reset visited flags ─────────────────────────────────────────

    _clearVisited() {
        for (let r = 0; r < this._rows; r++) {
            for (let c = 0; c < this._cols; c++) {
                this._cells[r][c].visited = false;
            }
        }
    }//end _clearVisited

    // ── BFS: find solution path (View Solution) ───────────────────────────────

    /**
     * BFS shortest path from (startRow, startCol) to (endRow, endCol).
     * Does NOT require the maze to have been solved first.
     * Stores (and returns) the path as an array of {row, col} objects.
     * In a perfect maze this path is guaranteed to exist and to be unique.
     *
     * @param {number} startRow @param {number} startCol
     * @param {number} endRow   @param {number} endCol
     * @returns {{ row: number, col: number }[]}
     */
    findSolutionPath(startRow, startCol, endRow, endCol) {
        const visited = Array.from({ length: this._rows }, () => Array(this._cols).fill(false));
        const parent  = Array.from({ length: this._rows }, () => Array(this._cols).fill(null));
        const queue   = [[startRow, startCol]];
        visited[startRow][startCol] = true;

        outer:
        while (queue.length > 0) {
            const [r, c] = queue.shift();
            for (const dir of SWMaze.DIRECTIONS) {
                if (this._cells[r][c].walls[dir]) continue;   // wall blocks passage
                const { dr, dc } = SWMaze.DIR[dir];
                const nr = r + dr;
                const nc = c + dc;
                if (!this._inBounds(nr, nc) || visited[nr][nc]) continue;
                visited[nr][nc]  = true;
                parent[nr][nc]   = { r, c };
                if (nr === endRow && nc === endCol) break outer;
                queue.push([nr, nc]);
            }
        }

        // Reconstruct path by following parent pointers back to start
        const path = [];
        let cur = { r: endRow, c: endCol };
        while (cur !== null) {
            path.unshift({ row: cur.r, col: cur.c });
            cur = parent[cur.r][cur.c];
        }

        this._solutionPath = path;
        return path;
    }//end findSolutionPath

    // ── Solve: recursive DFS (private) ───────────────────────────────────────

    /**
     * Recursive DFS maze solver — mirrors grow() from SWIsland in structure.
     * Records SOLVE_TRY and SOLVE_BACKTRACK steps.
     *
     * @param {number} r
     * @param {number} c
     * @param {number} endRow
     * @param {number} endCol
     * @param {boolean} useRandom  true = shuffle direction order (organic path)
     * @returns {boolean}
     */
    _solveDFS(r, c, endRow, endCol, useRandom) {

        // ── BASE CASE ────────────────────────────────────────────────────────
        if (r === endRow && c === endCol) return true;

        this._cells[r][c].visited = true;

        const dirs = useRandom
            ? this._shuffle([...SWMaze.DIRECTIONS])
            : [...SWMaze.DIRECTIONS];   // N, S, E, W — deterministic

        for (const dir of dirs) {
            if (this._cells[r][c].walls[dir]) continue;   // wall: can't go that way

            const { dr, dc } = SWMaze.DIR[dir];
            const nr = r + dr;
            const nc = c + dc;

            if (!this._inBounds(nr, nc) || this._cells[nr][nc].visited) continue;

            // TRY — step into this neighbor
            this._solveStepQueue.push({ type: 'SOLVE_TRY', row: nr, col: nc });

            if (this._solveDFS(nr, nc, endRow, endCol, useRandom)) {
                return true;   // propagate success
            }

            // BACKTRACK — this direction led to a dead end
            this._solveStepQueue.push({ type: 'SOLVE_BACKTRACK', row: nr, col: nc });
        }

        return false;   // no direction worked from (r, c)
    }//end _solveDFS

    // ── Public: solve ─────────────────────────────────────────────────────────

    /**
     * Solves the maze from (startRow, startCol) to (endRow, endCol) using
     * recursive DFS.  Records all SOLVE_TRY / SOLVE_BACKTRACK steps so the
     * sketch can animate the solver.
     *
     * Returns true if solved (always true for a perfect maze).
     *
     * @param {number}  startRow @param {number} startCol
     * @param {number}  endRow   @param {number} endCol
     * @param {boolean} [useRandom=true]
     * @returns {boolean}
     */
    solve(startRow, startCol, endRow, endCol, useRandom = true) {
        this._clearVisited();
        this._solveStepQueue = [];

        // Push the start cell as the first TRY
        this._solveStepQueue.push({ type: 'SOLVE_TRY', row: startRow, col: startCol });

        const success = this._solveDFS(startRow, startCol, endRow, endCol, useRandom);

        if (success) {
            this._solveStepQueue.push({ type: 'SOLVE_SUCCESS' });
        }

        this._clearVisited();
        return success;
    }//end solve

    // ── toString ──────────────────────────────────────────────────────────────

    /**
     * Returns a brief description of this maze.
     * @returns {string}
     */
    toString() {
        const cells = this._rows * this._cols;
        const steps = this._solveStepQueue.length;
        return `SWMaze [${this._rows}×${this._cols}, ${cells} cells, solveSteps=${steps}]`;
    }//end toString

}//end class SWMaze
