/**
 * Path Generation Module
 * 
 * This module demonstrates several advanced game development concepts:
 * 1. Procedural Content Generation (PCG)
 * 2. Pathfinding algorithms
 * 3. Constraint-based generation
 * 
 * @module path
 */

/**
 * Generates a valid path through the game grid using a modified depth-first search.
 * This algorithm ensures:
 * - Path always moves from left to right
 * - No diagonal movements
 * - No path segments touch each other (except at turns)
 * - Path is always completable
 * 
 * @param {Array<Array<string>>} grid - 2D array representing the game grid
 * @returns {Promise<Array<{x: number, y: number}>>} Promise resolving to array of path coordinates
 * 
 * Implementation uses:
 * - Backtracking algorithm pattern
 * - Constraint satisfaction
 * - Random selection for variety
 */
function generatePath(grid) {
    const width = grid[0].length;
    const height = grid.length;
    
    // Initialize with random start point on left edge
    const startY = Math.floor(Math.random() * height);
    let currentPos = { x: 0, y: startY };
    
    const path = [currentPos];
    grid[startY][0] = 'path';
    
    /**
     * Determines valid moves from current position based on game rules
     * Uses constraint checking to ensure path validity
     * 
     * @param {Object} pos - Current position {x, y}
     * @returns {Array<{x: number, y: number}>} Array of valid next positions
     */
    function getValidMoves(pos) {
        const moves = [];
        // Prioritize right movement for path progression
        const directions = [
            { x: 1, y: 0 },  // right
            { x: 0, y: -1 }, // up
            { x: 0, y: 1 }   // down
        ];
        
        for (const dir of directions) {
            const newX = pos.x + dir.x;
            const newY = pos.y + dir.y;
            
            // Enforce boundary constraints
            if (newX < 0 || newX >= width || newY < 0 || newY >= height) {
                continue;
            }
            
            // Check path isolation constraint
            if (grid[newY][newX] === 'empty' && !hasAdjacentPath(newX, newY, grid)) {
                moves.push({ x: newX, y: newY });
            }
        }
        
        return moves;
    }
    
    /**
     * Checks if a position has adjacent path tiles (excluding previous path tile)
     * Implements path isolation constraint
     * 
     * @param {number} x - X coordinate to check
     * @param {number} y - Y coordinate to check
     * @param {Array<Array<string>>} grid - Current grid state
     * @returns {boolean} True if position has adjacent path tiles
     */
    function hasAdjacentPath(x, y, grid) {
        const adjacentCells = [
            { x: x, y: y - 1 },     // up
            { x: x, y: y + 1 },     // down
            { x: x - 1, y: y },     // left
            { x: x + 1, y: y },     // right
        ];
        
        return adjacentCells.some(cell => {
            if (cell.x < 0 || cell.x >= width || cell.y < 0 || cell.y >= height) {
                return false;
            }
            return grid[cell.y][cell.x] === 'path' && 
                   !path.some(p => p.x === cell.x && p.y === cell.y);
        });
    }
    
    // Main path generation loop with backtracking
    while (currentPos.x < width - 1) {
        const moves = getValidMoves(currentPos);
        
        if (moves.length === 0) {
            // Backtrack when no valid moves exist
            if (path.length <= 1) {
                // Restart if backtracking fails
                return generatePath(grid);
            }
            
            path.pop();
            const lastPos = path[path.length - 1];
            grid[currentPos.y][currentPos.x] = 'empty';
            currentPos = lastPos;
            continue;
        }
        
        // Random selection for path variety
        const nextMove = moves[Math.floor(Math.random() * moves.length)];
        currentPos = nextMove;
        path.push(currentPos);
        grid[currentPos.y][currentPos.x] = 'path';
    }
    
    return Promise.resolve(path);
}

/**
 * Calculates a position along the path based on a progress value
 * Implements smooth entity movement along path segments
 * 
 * @param {number} progress - Progress along path (0-1)
 * @param {Array<{x: number, y: number}>} path - Array of path coordinates
 * @returns {{x: number, y: number}} Interpolated position along path
 * 
 * Uses:
 * - Linear interpolation (lerp)
 * - Path segment traversal
 * - Normalized progress tracking
 */
function getPathPosition(progress, path) {
    // Normalize progress to valid range
    progress = Math.max(0, Math.min(1, progress));
    
    // Calculate total path length for normalization
    let totalLength = 0;
    for (let i = 1; i < path.length; i++) {
        const dx = path[i].x - path[i-1].x;
        const dy = path[i].y - path[i-1].y;
        totalLength += Math.sqrt(dx * dx + dy * dy);
    }
    
    // Convert progress to distance along path
    const targetDistance = progress * totalLength;
    
    // Find appropriate path segment
    let currentDistance = 0;
    for (let i = 1; i < path.length; i++) {
        const dx = path[i].x - path[i-1].x;
        const dy = path[i].y - path[i-1].y;
        const segmentLength = Math.sqrt(dx * dx + dy * dy);
        
        if (currentDistance + segmentLength >= targetDistance) {
            // Linear interpolation within segment
            const segmentProgress = (targetDistance - currentDistance) / segmentLength;
            return {
                x: path[i-1].x + dx * segmentProgress,
                y: path[i-1].y + dy * segmentProgress
            };
        }
        
        currentDistance += segmentLength;
    }
    
    // Fallback to end of path
    return { ...path[path.length - 1] };
}