import * as THREE from 'three';

const GRID = 11;
const CELL = 92 / GRID;
const HALF = 46;
const WALL_THICK = 1;
const WALL_HEIGHT = 2.5;

interface WallBox {
  minX: number;
  maxX: number;
  minZ: number;
  maxZ: number;
}

// Labyrinth-Zwischenboss: randomisierter Prim auf einem 11x11-Grid.
// Erzeugt ein "perfektes" Labyrinth (jede Zelle erreichbar, genau ein Pfad
// zwischen zwei beliebigen Zellen) mit kurzen, verzweigten Lösungswegen.
export class Maze {
  private scene: THREE.Scene;
  private wallMeshes: THREE.Mesh[] = [];
  private wallBoxes: WallBox[] = [];
  private openH: boolean[][] = []; // Passage (i,j)-(i+1,j)
  private openV: boolean[][] = []; // Passage (i,j)-(i,j+1)

  constructor(scene: THREE.Scene) {
    this.scene = scene;
    this.generate();
    this.buildWalls();
  }

  // Start-Ecke = Zelle (0,0), Ziel = Zelle (10,10)
  startPosition(): THREE.Vector3 {
    return this.cellCenter(0, 0);
  }

  // goalIndex 0 = Ziel-Ecke (max,max), 1 = Neben-Ecke (min,max) für 2x-Finden
  goalPosition(goalIndex: number): THREE.Vector3 {
    if (goalIndex === 1) return this.cellCenter(0, GRID - 1);
    return this.cellCenter(GRID - 1, GRID - 1);
  }

  private cellCenter(i: number, j: number): THREE.Vector3 {
    return new THREE.Vector3(-HALF + (i + 0.5) * CELL, 0, -HALF + (j + 0.5) * CELL);
  }

  private generate() {
    for (let i = 0; i < GRID; i++) {
      this.openH.push(new Array(GRID - 1).fill(false));
      this.openV.push(new Array(GRID - 1).fill(false));
    }

    // Randomized Prim: startet bei Zelle (0,0), wählt zufällige Frontier-Kante
    const visited: boolean[][] = Array.from({ length: GRID }, () => new Array(GRID).fill(false));
    const frontier: { i: number; j: number; dir: 'h' | 'v' }[] = [];
    const addFrontier = (i: number, j: number) => {
      if (i < GRID - 1 && !visited[i + 1][j]) frontier.push({ i, j, dir: 'h' });
      if (i > 0 && !visited[i - 1][j]) frontier.push({ i: i - 1, j, dir: 'h' });
      if (j < GRID - 1 && !visited[i][j + 1]) frontier.push({ i, j, dir: 'v' });
      if (j > 0 && !visited[i][j - 1]) frontier.push({ i, j: j - 1, dir: 'v' });
    };

    visited[0][0] = true;
    addFrontier(0, 0);
    while (frontier.length > 0) {
      const idx = Math.floor(Math.random() * frontier.length);
      const { i, j, dir } = frontier[idx];
      frontier.splice(idx, 1);
      const ci = dir === 'h' ? i + 1 : i;
      const cj = dir === 'h' ? j : j + 1;
      if (visited[ci][cj]) continue;
      visited[ci][cj] = true;
      if (dir === 'h') this.openH[i][j] = true;
      else this.openV[i][j] = true;
      addFrontier(ci, cj);
    }
  }

  private buildWalls() {
    const wallMat = new THREE.MeshToonMaterial({ color: 0x776677 });

    // Außenwände: Labyrinth bis zur Begrenzung abdichten,
    // damit man nicht außen herumlaufen kann
    const outer = HALF + WALL_THICK / 2;
    this.addWall(-outer, -HALF + WALL_THICK / 2, -outer, outer, WALL_THICK, 2 * outer, -HALF, 0, 0, wallMat);
    this.addWall(HALF - WALL_THICK / 2, outer, -outer, outer, WALL_THICK, 2 * outer, HALF, 0, 0, wallMat);
    this.addWall(-outer, outer, -outer, -HALF + WALL_THICK / 2, 2 * outer, WALL_THICK, 0, 0, -HALF, wallMat);
    this.addWall(-outer, outer, HALF - WALL_THICK / 2, outer, 2 * outer, WALL_THICK, 0, 0, HALF, wallMat);

    // Vertikale Gitterlinien (konstantes x): Wand blockiert Bewegung in x
    for (let i = 1; i < GRID; i++) {
      const bx = -HALF + i * CELL;
      for (let j = 0; j < GRID; j++) {
        if (this.openH[i - 1][j]) continue;
        const zc = -HALF + (j + 0.5) * CELL;
        this.addWall(bx - WALL_THICK / 2, bx + WALL_THICK / 2, zc - CELL / 2, zc + CELL / 2, WALL_THICK, CELL, bx, 0, zc, wallMat);
      }
    }

    // Horizontale Gitterlinien (konstantes z): Wand blockiert Bewegung in z
    for (let j = 1; j < GRID; j++) {
      const bz = -HALF + j * CELL;
      for (let i = 0; i < GRID; i++) {
        if (this.openV[i][j - 1]) continue;
        const xc = -HALF + (i + 0.5) * CELL;
        this.addWall(xc - CELL / 2, xc + CELL / 2, bz - WALL_THICK / 2, bz + WALL_THICK / 2, CELL, WALL_THICK, xc, 0, bz, wallMat);
      }
    }
  }

  private addWall(
    minX: number, maxX: number, minZ: number, maxZ: number,
    sizeX: number, sizeZ: number,
    px: number, py: number, pz: number,
    mat: THREE.Material
  ) {
    const geom = new THREE.BoxGeometry(sizeX, WALL_HEIGHT, sizeZ);
    const mesh = new THREE.Mesh(geom, mat);
    mesh.position.set(px, py + WALL_HEIGHT / 2, pz);
    mesh.castShadow = true;
    mesh.receiveShadow = true;
    this.scene.add(mesh);
    this.wallMeshes.push(mesh);
    this.wallBoxes.push({ minX, maxX, minZ, maxZ });
  }

  // Circle-vs-AABB-Kollision: Spieler aus Wänden schieben (3 Durchgänge)
  collidePlayer(pos: THREE.Vector3, radius: number) {
    for (let pass = 0; pass < 3; pass++) {
      let moved = false;
      for (const w of this.wallBoxes) {
        const cx = Math.max(w.minX, Math.min(pos.x, w.maxX));
        const cz = Math.max(w.minZ, Math.min(pos.z, w.maxZ));
        const dx = pos.x - cx;
        const dz = pos.z - cz;
        const d2 = dx * dx + dz * dz;
        if (d2 < radius * radius) {
          if (d2 > 1e-6) {
            const d = Math.sqrt(d2);
            pos.x += (dx / d) * (radius - d);
            pos.z += (dz / d) * (radius - d);
          } else {
            // Mittelpunkt in der Wand: kleinste Überlappung wählen
            const ox = Math.min(pos.x - w.minX, w.maxX - pos.x);
            const oz = Math.min(pos.z - w.minZ, w.maxZ - pos.z);
            if (ox < oz) {
              pos.x += (pos.x < (w.minX + w.maxX) / 2 ? -1 : 1) * (radius + ox);
            } else {
              pos.z += (pos.z < (w.minZ + w.maxZ) / 2 ? -1 : 1) * (radius + oz);
            }
          }
          moved = true;
        }
      }
      if (!moved) break;
    }
  }

  // Sichtlinie: Segment alle ~0.8 m abtasten, Wand dazwischen = kein Sichtkontakt
  hasLineOfSight(a: THREE.Vector3, b: THREE.Vector3): boolean {
    const dx = b.x - a.x;
    const dz = b.z - a.z;
    const dist = Math.hypot(dx, dz);
    const steps = Math.max(1, Math.ceil(dist / 0.8));
    for (let s = 1; s < steps; s++) {
      const t = s / steps;
      const px = a.x + dx * t;
      const pz = a.z + dz * t;
      for (const w of this.wallBoxes) {
        if (px > w.minX - 0.3 && px < w.maxX + 0.3 &&
            pz > w.minZ - 0.3 && pz < w.maxZ + 0.3) {
          return false;
        }
      }
    }
    return true;
  }

  // Wächter-Positionen: gleichmäßig verteilte Zellen entlang des Lösungswegs
  guardPositions(count: number): THREE.Vector3[] {
    if (count <= 0) return [];

    // BFS von (0,0) zu (10,10)
    const prev: ([number, number] | null)[][] = Array.from(
      { length: GRID },
      () => new Array<[number, number] | null>(GRID).fill(null)
    );
    const queue: [number, number][] = [[0, 0]];
    prev[0][0] = [0, 0];
    while (queue.length > 0) {
      const [i, j] = queue.shift()!;
      if (i === GRID - 1 && j === GRID - 1) break;
      const neigh: [number, number][] = [];
      if (i < GRID - 1 && this.openH[i][j]) neigh.push([i + 1, j]);
      if (i > 0 && this.openH[i - 1][j]) neigh.push([i - 1, j]);
      if (j < GRID - 1 && this.openV[i][j]) neigh.push([i, j + 1]);
      if (j > 0 && this.openV[i][j - 1]) neigh.push([i, j - 1]);
      for (const [ni, nj] of neigh) {
        if (prev[ni][nj]) continue;
        prev[ni][nj] = [i, j];
        queue.push([ni, nj]);
      }
    }

    // Pfad rekonstruieren
    const path: [number, number][] = [];
    let cur: [number, number] | null = [GRID - 1, GRID - 1];
    while (cur) {
      path.push(cur);
      const p: [number, number] | null = prev[cur[0]][cur[1]];
      if (!p || (p[0] === cur[0] && p[1] === cur[1])) break;
      cur = p;
    }
    path.reverse();
    if (path.length < 3) return [];

    // count Zellen gleichmäßig auf dem Weg verteilen (ohne Start/Ziel)
    const res: THREE.Vector3[] = [];
    const used = new Set<string>();
    for (let k = 1; k <= count; k++) {
      const idx = Math.min(path.length - 2, Math.max(1, Math.round((k * path.length) / (count + 1))));
      const [i, j] = path[idx];
      const key = `${i},${j}`;
      if (used.has(key)) continue;
      used.add(key);
      res.push(this.cellCenter(i, j));
    }
    return res;
  }

  dispose() {
    for (const mesh of this.wallMeshes) {
      this.scene.remove(mesh);
      mesh.geometry.dispose();
      (mesh.material as THREE.Material).dispose();
    }
    this.wallMeshes = [];
    this.wallBoxes = [];
  }
}
