// Isometric map with houses
// Using modified isometric projection: 1 tile 10x10m = 2:1 (width:height)

// ============================================
// 1. CONFIGURATION AND CONSTANTS
// ============================================

const GRID_SIZE = 10; // min=1 max=20 step=1 Size of one grid tile in meters
const ISO_WIDTH = 2;  // Tile width in isometric projection
const ISO_HEIGHT = 1; // Tile height in isometric projection
const MAP_SIZE = 15;  // min=5 max=30 step=1 Number of tiles along one side of the map
const NUM_BUILDINGS = 15; // min=1 max=50 step=1 Number of buildings to generate
const BUILDING_MARGIN = 1; // Visual margin of building from tile edge

// ============================================
// 2. HELPER FUNCTIONS - COORDINATE CONVERSION
// ============================================

// Convert 3D coordinates (x, y, z) to 2D isometric
// Point [0,0,0] is in the center bottom
// x grows RIGHT upward ↗️
// y grows LEFT upward ↖️
// z grows straight upward ↑
function to_iso(x, y, z) {
    // Offset so [0,0,0] is in the center: subtract half of the map
    const offset_x = MAP_SIZE * GRID_SIZE / 2;
    const offset_y = MAP_SIZE * GRID_SIZE / 2;
    
    const adjusted_x = x - offset_x;
    const adjusted_y = y - offset_y;
    
    // 180° rotation: X right (inverted), Y left (inverted)
    const rotated_x = -adjusted_x;
    const rotated_y = -adjusted_y;
    
    const iso_x = (rotated_x - rotated_y) * ISO_WIDTH / 2;
    const iso_y = (rotated_x + rotated_y) * ISO_HEIGHT / 2 - z;
    return [iso_x, iso_y];
}

// Calculate depth for sorting (the higher, the further)
function get_depth(x, y, z) {
    return x + y; //- z * 0.01; // Z has little effect so buildings overlap correctly
}

// ============================================
// 3. MAP AND HOUSE GENERATION
// ============================================

function generate_map() {
    const buildings = [];
    const used_positions = new Set();
    
    for (let i = 0; i < NUM_BUILDINGS; i++) {
        let x, y, w, h, height;
        let attempts = 0;
        
        // Find free position
        do {
            w = Math.floor(Math.random() * 3) + 1; // Width 1-3 tiles
            h = Math.floor(Math.random() * 3) + 1; // Depth 1-3 tiles
            x = Math.floor(Math.random() * (MAP_SIZE - w));
            y = Math.floor(Math.random() * (MAP_SIZE - h));
            height = Math.floor(Math.random() * 4) + 1.5; // Height 1-4 tiles
            attempts++;
        } while (check_collision(x, y, w, h, used_positions) && attempts < 50);
        
        if (attempts < 50) {
            // Mark position as used
            for (let dx = 0; dx < w; dx++) {
                for (let dy = 0; dy < h; dy++) {
                    used_positions.add(`${x + dx},${y + dy}`);
                }
            }
            
            buildings.push({
                x: x * GRID_SIZE,
                y: y * GRID_SIZE,
                w: w * GRID_SIZE,
                h: h * GRID_SIZE,
                height: height * GRID_SIZE,
                windowSize: (GRID_SIZE/4) + Math.random() * (GRID_SIZE/3)  // Random window size 1-3
            });
        }
    }
    
    return buildings;
}

function check_collision(x, y, w, h, used_positions) {
    // Check with 1 tile spacing around building
    for (let dx = -1; dx <= w; dx++) {
        for (let dy = -1; dy <= h; dy++) {
            if (used_positions.has(`${x + dx},${y + dy}`)) {
                return true;
            }
        }
    }
    return false;
}

// ============================================
// 4. SURFACE GENERATION (for overlap detection)
// ============================================

// Generate surfaces for one building
function generate_building_surfaces(building) {
    const surfaces = [];
    const { x, y, w, h, height } = building;
    const d = get_depth(x + w, y + h, 0);
    
    // Add visual margin
    const vx = x + BUILDING_MARGIN;
    const vy = y + BUILDING_MARGIN;
    const vw = w - 2 * BUILDING_MARGIN;
    const vh = h - 2 * BUILDING_MARGIN;
    
    // Top surface (square from above)
    surfaces.push({
        type: 'top',
        depth: d,
        points: [
            [vx, vy, height],
            [vx + vw, vy, height],
            [vx + vw, vy + vh, height],
            [vx, vy + vh, height]
        ]
    });
    
    // Bottom surface ("grass")
    const padding = 0.01;
    surfaces.push({
        type: 'top',
        depth: d,
        points: [
            [x + padding, y + padding, 0],
            [x + w - padding, y + padding, 0],
            [x + w - padding, y + h, 0],
            [x + padding, y + h, 0]
        ]
    });
    
    // Left wall (along Y axis)
    surfaces.push({
        type: 'left-wall',
        depth: d,
        points: [
            [vx, vy, 0],
            [vx + vw, vy, 0],
            [vx + vw, vy, height],
            [vx, vy, height]
        ]
    });
    
    // Right wall (along X axis)
    surfaces.push({
        type: 'right-wall',
        depth: d,
        points: [
            [vx, vy, 0],
            [vx, vy + vh, 0],
            [vx, vy + vh, height],
            [vx, vy, height]
        ]
    });
    
    return surfaces;
}

// Generate all surfaces from all buildings
function generate_surfaces(buildings) {
    const surfaces = [];
    
    for (const building of buildings) {
        surfaces.push(...generate_building_surfaces(building));
    }
    
    // Sort by depth (furthest = smallest depth)
    surfaces.sort((a, b) => a.depth - b.depth);
    
    return surfaces;
}

// ============================================
// 5. LINE GENERATION
// ============================================

// Generate lines for one building
function generate_building_lines(building) {
    const lines = [];
    const { x, y, w, h, height } = building;
    const depth = get_depth(x + w, y + h, height);
    
    // Add visual margin
    const vx = x + BUILDING_MARGIN;
    const vy = y + BUILDING_MARGIN;
    const vw = w - 2 * BUILDING_MARGIN;
    const vh = h - 2 * BUILDING_MARGIN;
    
    // Top rectangle (4 edges)
    add_line(lines, vx, vy, height, vx + vw, vy, height, depth);
    add_line(lines, vx + vw, vy, height, vx + vw, vy + vh, height, depth);
    add_line(lines, vx + vw, vy + vh, height, vx, vy + vh, height, depth);
    add_line(lines, vx, vy + vh, height, vx, vy, height, depth);
    
    // Vertical edges (3 visible corners)
    add_line(lines, vx, vy, 0, vx, vy, height, depth);           // front left
    add_line(lines, vx + vw, vy, 0, vx + vw, vy, height, depth);   // front right
    add_line(lines, vx, vy + vh, 0, vx, vy + vh, height, depth);   // back left
    
    // Bottom edges (2 visible)
    add_line(lines, vx, vy, 0, vx + vw, vy, 0, depth);    // front
    add_line(lines, vx, vy, 0, vx, vy + vh, 0, depth);    // left
    
    // Windows on right wall (along X axis)
    const win_size = building.windowSize; // Random window size for this building
    
    // Calculate number of columns based on wall width (no margin)
    const num_cols = Math.max(1, Math.floor(vw / 5)); // One column per ~5 units
    const col_width = vw / num_cols;
    
    // Calculate number of rows based on wall height (no margin)
    const num_rows = Math.max(1, Math.floor(height / 5)); // One row per ~5 units
    const row_height = height / num_rows;
    
    // Windows on right wall (along X axis) - place in center of each column
    for (let col = 0; col < num_cols; col++) {
        const col_center = vx + col * col_width + col_width / 2;
        const wx = col_center - win_size / 2; // Center window in column
        
        for (let row = 0; row < num_rows; row++) {
            const row_center = row * row_height + row_height / 2;
            const wz = row_center - win_size / 2; // Center window in row
            
            // Window rectangle (4 lines)
            add_line(lines, wx, vy, wz, wx + win_size, vy, wz, depth);
            add_line(lines, wx + win_size, vy, wz, wx + win_size, vy, wz + win_size, depth);
            add_line(lines, wx + win_size, vy, wz + win_size, wx, vy, wz + win_size, depth);
            add_line(lines, wx, vy, wz + win_size, wx, vy, wz, depth);
        }
    }
    
    // Windows on left wall (along Y axis) - place in center of each column
    const num_cols_left = Math.max(1, Math.floor(vh / 5));
    const col_depth = vh / num_cols_left;
    
    for (let col = 0; col < num_cols_left; col++) {
        const col_center = vy + col * col_depth + col_depth / 2;
        const wy = col_center - win_size / 2; // Center window in column
        
        for (let row = 0; row < num_rows; row++) {
            const row_center = row * row_height + row_height / 2;
            const wz = row_center - win_size / 2; // Center window in row
            
            // Window rectangle (4 lines)
            add_line(lines, vx, wy, wz, vx, wy + win_size, wz, depth);
            add_line(lines, vx, wy + win_size, wz, vx, wy + win_size, wz + win_size, depth);
            add_line(lines, vx, wy + win_size, wz + win_size, vx, wy, wz + win_size, depth);
            add_line(lines, vx, wy, wz + win_size, vx, wy, wz, depth);
        }
    }
    
    return lines;
}

// Generate grid lines
function generate_grid_lines() {
    const lines = [];
    
    for (let i = 0; i <= MAP_SIZE; i++) {
        // Horizontal lines
        add_line(lines, 0, i * GRID_SIZE, 0, MAP_SIZE * GRID_SIZE, i * GRID_SIZE, 0, 1000);
        // Vertical lines
        add_line(lines, i * GRID_SIZE, 0, 0, i * GRID_SIZE, MAP_SIZE * GRID_SIZE, 0, 1000);
    }
    
    return lines;
}

// Generate all lines (buildings + grid)
function generate_lines(buildings) {
    const lines = [];
    
    // Add lines from buildings
    for (const building of buildings) {
        lines.push(...generate_building_lines(building));
    }
    
    // Add grid
    lines.push(...generate_grid_lines());
    
    // Sort by depth (highest depth = drawn first)
    lines.sort((a, b) => b.depth - a.depth);
    
    return lines;
}

function add_line(lines, x1, y1, z1, x2, y2, z2, depth = 0) {
    //const depth = (get_depth(x1, y1, z1) + get_depth(x2, y2, z2)) / 2 + depthOffset;
    lines.push({
        start: [x1, y1, z1],
        end: [x2, y2, z2],
        depth: depth
    });
}

// ============================================
// 6. OVERLAP DETECTION AND LINE CLIPPING
// ============================================

function clip_line_by_surfaces(line, surfaces) {
    let segments = [{ start: line.start, end: line.end }];
    
    // Go through all surfaces with smaller depth (closer to observer)
    for (const surface of surfaces) {
        if (surface.depth >= line.depth) continue;
        
        const newSegments = [];
        for (const segment of segments) {
            const clipped = clip_segment_by_surface(segment, surface);
            newSegments.push(...clipped);
        }
        segments = newSegments;
        
        if (segments.length === 0) break;
    }
    
    return segments;
}

function clip_segment_by_surface(segment, surface) {
    const [x1, y1, z1] = segment.start;
    const [x2, y2, z2] = segment.end;
    
    // Convert to 2D isometric space
    const [sx, sy] = to_iso(x1, y1, z1);
    const [ex, ey] = to_iso(x2, y2, z2);
    
    // Convert surface to 2D
    const poly = surface.points.map(p => to_iso(p[0], p[1], p[2]));
    
    // Find all intersections with polygon
    const intersections = find_line_polygon_intersections(sx, sy, ex, ey, poly);
    
    // Check if points are inside polygon
    const startInside = point_in_polygon(sx, sy, poly);
    const endInside = point_in_polygon(ex, ey, poly);
    
    // If there are no intersections
    if (intersections.length === 0) {
        if (startInside && endInside) {
            return []; // Entire line hidden
        } else {
            return [segment]; // Entire line visible
        }
    }
    
    // Sort intersections by parameter t
    intersections.sort((a, b) => a.t - b.t);
    
    // Create list of all critical points (start, intersections, end)
    const points = [
        { t: 0, inside: startInside }
    ];
    
    for (const inter of intersections) {
        points.push({ t: inter.t, inside: null }); // Intersection = transition
    }
    
    points.push({ t: 1, inside: endInside });
    
    // Go through all segments between critical points
    const resultSegments = [];
    
    for (let i = 0; i < points.length - 1; i++) {
        const p1 = points[i];
        const p2 = points[i + 1];
        
        // Check if segment middle is visible
        const midT = (p1.t + p2.t) / 2;
        const [midX, midY, midZ] = lerp_3d(segment.start, segment.end, midT);
        const [midIsoX, midIsoY] = to_iso(midX, midY, midZ);
        const midInside = point_in_polygon(midIsoX, midIsoY, poly);
        
        // If middle is outside (visible), add segment
        if (!midInside) {
            const [sx1, sy1, sz1] = lerp_3d(segment.start, segment.end, p1.t);
            const [sx2, sy2, sz2] = lerp_3d(segment.start, segment.end, p2.t);
            
            // Add only if it has non-zero length
            if (Math.abs(p2.t - p1.t) > 0.001) {
                resultSegments.push({
                    start: [sx1, sy1, sz1],
                    end: [sx2, sy2, sz2]
                });
            }
        }
    }
    
    return resultSegments;
}

// Find all intersections of line with polygon
function find_line_polygon_intersections(x1, y1, x2, y2, polygon) {
    const intersections = [];
    
    for (let i = 0; i < polygon.length; i++) {
        const j = (i + 1) % polygon.length;
        const [px1, py1] = polygon[i];
        const [px2, py2] = polygon[j];
        
        const intersection = line_intersection_point(x1, y1, x2, y2, px1, py1, px2, py2);
        if (intersection !== null) {
            intersections.push(intersection);
        }
    }
    
    return intersections;
}

// Find intersection of two lines and return parameter t on first line
function line_intersection_point(x1, y1, x2, y2, x3, y3, x4, y4) {
    const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    if (Math.abs(denom) < 0.0001) return null;
    
    const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
    const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom;
    
    if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
        return { t: t };
    }
    
    return null;
}

// Linear interpolation between two 3D points
function lerp_3d(start, end, t) {
    return [
        start[0] + (end[0] - start[0]) * t,
        start[1] + (end[1] - start[1]) * t,
        start[2] + (end[2] - start[2]) * t
    ];
}

function point_in_polygon(x, y, polygon) {
    let inside = false;
    for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
        const xi = polygon[i][0], yi = polygon[i][1];
        const xj = polygon[j][0], yj = polygon[j][1];
        
        const intersect = ((yi > y) !== (yj > y))
            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
        if (intersect) inside = !inside;
    }
    return inside;
}

function line_intersects_polygon(x1, y1, x2, y2, polygon) {
    for (let i = 0; i < polygon.length; i++) {
        const j = (i + 1) % polygon.length;
        const [px1, py1] = polygon[i];
        const [px2, py2] = polygon[j];
        
        if (lines_intersect(x1, y1, x2, y2, px1, py1, px2, py2)) {
            return true;
        }
    }
    return false;
}

function lines_intersect(x1, y1, x2, y2, x3, y3, x4, y4) {
    const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    if (Math.abs(denom) < 0.0001) return false;
    
    const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
    const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom;
    
    return t >= 0 && t <= 1 && u >= 0 && u <= 1;
}

// ============================================
// 7. MAIN DRAWING FUNCTION
// ============================================

// Global variables to store state between calls
let buildings = null;
let surfaces = [];
let lines = null;
let currentLineIndex = 0;
const t = new Turtle();

buildings = generate_map();
surfaces = generate_surfaces(buildings);
lines = generate_lines(buildings);

// Debug: Display axis directions in isometry
console.log("Axis orientation in isometry:");
console.log("X axis [10,0,0]:", to_iso(10, 0, 0), "→ right upward");
console.log("Y axis [0,10,0]:", to_iso(0, 10, 0), "→ left upward");
console.log("Z axis [0,0,10]:", to_iso(0, 0, 10), "→ straight upward");

lines.sort((a, b) => b.depth - a.depth);
currentLineIndex = 0;

function walk(i) {
    
    // If we have drawn all lines, finish
    if (currentLineIndex >= lines.length) {
        return false;
    }
    
    // Draw current line
    const line = lines[currentLineIndex];
    const segments = clip_line_by_surfaces(line, surfaces);
    
    currentLineIndex++;
    
    // If there are any visible segments, draw them
    for (const segment of segments) {
        const [sx, sy] = to_iso(segment.start[0], segment.start[1], segment.start[2]);
        const [ex, ey] = to_iso(segment.end[0], segment.end[1], segment.end[2]);
        
        t.penup();
        t.goto(sx, sy);
        t.pendown();
        t.goto(ex, ey);
    }
    
    return t;
}

// ============================================
// DEBUG: Display information
// ============================================

// For debugging you can uncomment:
/*
const testBuildings = generate_map();
console.log('Number of buildings:', testBuildings.length);
console.log('Buildings:', testBuildings);
*/