// Path generation using a modified depth-first search algorithm
function generatePath(grid) {
    const width = grid[0].length;
    const height = grid.length;
    
    // Pick random start point on left edge
    const startY = Math.floor(Math.random() * height);
    let currentPos = { x: 0, y: startY };
    
    // Initialize path with start position
    const path = [currentPos];
    grid[startY][0] = 'path';
    
    function getValidMoves(pos) {
        const moves = [];
        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;
            
            // Check bounds
            if (newX < 0 || newX >= width || newY < 0 || newY >= height) {
                continue;
            }
            
            // Check if cell is empty and not adjacent to path (except previous cell)
            if (grid[newY][newX] === 'empty' && !hasAdjacentPath(newX, newY, grid)) {
                moves.push({ x: newX, y: newY });
            }
        }
        
        return moves;
    }
    
    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);
        });
    }
    
    // Generate path until we reach the right edge
    while (currentPos.x < width - 1) {
        const moves = getValidMoves(currentPos);
        
        if (moves.length === 0) {
            // If no valid moves, backtrack
            if (path.length <= 1) {
                // Start over if we can't backtrack
                return generatePath(grid);
            }
            
            path.pop();
            const lastPos = path[path.length - 1];
            grid[currentPos.y][currentPos.x] = 'empty';
            currentPos = lastPos;
            continue;
        }
        
        // Choose random valid move
        const nextMove = moves[Math.floor(Math.random() * moves.length)];
        currentPos = nextMove;
        path.push(currentPos);
        grid[currentPos.y][currentPos.x] = 'path';
    }
    
    return Promise.resolve(path);
}

function getPathPosition(progress, path) {
    // Ensure progress is between 0 and 1
    progress = Math.max(0, Math.min(1, progress));
    
    // Get the total path length
    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);
    }
    
    // Find target distance along path
    const targetDistance = progress * totalLength;
    
    // Find the segment where the target position lies
    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) {
            // Calculate position within this segment
            const segmentProgress = (targetDistance - currentDistance) / segmentLength;
            return {
                x: path[i-1].x + dx * segmentProgress,
                y: path[i-1].y + dy * segmentProgress
            };
        }
        
        currentDistance += segmentLength;
    }
    
    // If we somehow exceed the path length, return the last point
    return { ...path[path.length - 1] };
}