🧮 Algoritmid Mängudes

interface Node {
  x: number;
  y: number;
  g: number;  // Tegelik kulu algusest
  h: number;  // Heuristiline kulu lõpuni
  f: number;  // g + h
  parent: Node | null;
  walkable: boolean;
}

class AStar {
  private grid: Node[][];
  private cols: number;
  private rows: number;

  constructor(walkableMap: boolean[][]) {
    this.rows = walkableMap.length;
    this.cols = walkableMap[0].length;
    this.grid = walkableMap.map((row, y) =>
      row.map((walkable, x) => ({
        x, y, g: 0, h: 0, f: 0, parent: null, walkable
      }))
    );
  }

  // Manhattan kaugus (4 suunda)
  private heuristic(a: Node, b: Node): number {
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
  }

  // Naabrid (4 suunda + 4 diagonaali)
  private getNeighbors(node: Node): Node[] {
    const dirs = [
      [0, -1], [0, 1], [-1, 0], [1, 0],   // Üles, alla, vasak, parem
      [-1,-1], [1,-1], [-1, 1], [1, 1]     // Diagonaalid
    ];
    const neighbors: Node[] = [];

    for (const [dx, dy] of dirs) {
      const nx = node.x + dx;
      const ny = node.y + dy;
      if (nx >= 0 && nx < this.cols && ny >= 0 && ny < this.rows) {
        if (this.grid[ny][nx].walkable) {
          neighbors.push(this.grid[ny][nx]);
        }
      }
    }
    return neighbors;
  }

  findPath(startX: number, startY: number, endX: number, endY: number): {x: number, y: number}[] {
    // Reset grid
    for (const row of this.grid) {
      for (const node of row) {
        node.g = 0; node.h = 0; node.f = 0; node.parent = null;
      }
    }

    const start = this.grid[startY][startX];
    const end = this.grid[endY][endX];
    const openSet: Node[] = [start];
    const closedSet = new Set<Node>();

    while (openSet.length > 0) {
      // Leia väiksima f-väärtusega sõlm
      let current = openSet[0];
      let lowestIndex = 0;
      for (let i = 1; i < openSet.length; i++) {
        if (openSet[i].f < current.f) {
          current = openSet[i];
          lowestIndex = i;
        }
      }

      // Leidsime lõppu!
      if (current === end) {
        return this.reconstructPath(current);
      }

      openSet.splice(lowestIndex, 1);
      closedSet.add(current);

      for (const neighbor of this.getNeighbors(current)) {
        if (closedSet.has(neighbor)) continue;

        const isDiagonal = neighbor.x !== current.x && neighbor.y !== current.y;
        const tentativeG = current.g + (isDiagonal ? 1.414 : 1);

        const inOpen = openSet.includes(neighbor);
        if (!inOpen || tentativeG < neighbor.g) {
          neighbor.g = tentativeG;
          neighbor.h = this.heuristic(neighbor, end);
          neighbor.f = neighbor.g + neighbor.h;
          neighbor.parent = current;

          if (!inOpen) openSet.push(neighbor);
        }
      }
    }

    return []; // Teed ei leitud
  }

  private reconstructPath(node: Node): {x: number, y: number}[] {
    const path: {x: number, y: number}[] = [];
    let current: Node | null = node;
    while (current) {
      path.unshift({ x: current.x, y: current.y });
      current = current.parent;
    }
    return path;
  }
}

class SpatialHash<T extends { x: number; y: number; width: number; height: number }> {
  private cellSize: number;
  private cells = new Map<string, Set<T>>();

  constructor(cellSize: number = 64) {
    this.cellSize = cellSize;
  }

  private key(cx: number, cy: number): string {
    return `${cx},${cy}`;
  }

  clear(): void {
    this.cells.clear();
  }

  insert(obj: T): void {
    const minCX = Math.floor(obj.x / this.cellSize);
    const minCY = Math.floor(obj.y / this.cellSize);
    const maxCX = Math.floor((obj.x + obj.width) / this.cellSize);
    const maxCY = Math.floor((obj.y + obj.height) / this.cellSize);

    for (let cx = minCX; cx <= maxCX; cx++) {
      for (let cy = minCY; cy <= maxCY; cy++) {
        const k = this.key(cx, cy);
        if (!this.cells.has(k)) this.cells.set(k, new Set());
        this.cells.get(k)!.add(obj);
      }
    }
  }

  // Leia potentsiaalsed kokkupõrked (broadphase)
  query(obj: T): Set<T> {
    const result = new Set<T>();
    const minCX = Math.floor(obj.x / this.cellSize);
    const minCY = Math.floor(obj.y / this.cellSize);
    const maxCX = Math.floor((obj.x + obj.width) / this.cellSize);
    const maxCY = Math.floor((obj.y + obj.height) / this.cellSize);

    for (let cx = minCX; cx <= maxCX; cx++) {
      for (let cy = minCY; cy <= maxCY; cy++) {
        const cell = this.cells.get(this.key(cx, cy));
        if (cell) {
          for (const other of cell) {
            if (other !== obj) result.add(other);
          }
        }
      }
    }
    return result;
  }
}

// 1000 objekti — ilma: 1000×1000 = 1M kontrolli
// Spatial hashiga: ainult lähedalasuvad — ~5000 kontrolli!

interface Rect {
  x: number; y: number; width: number; height: number;
}

class QuadTree<T extends Rect> {
  private objects: T[] = [];
  private children: QuadTree<T>[] | null = null;
  private maxObjects = 10;
  private maxDepth = 5;
  private depth: number;
  private bounds: Rect;

  constructor(bounds: Rect, depth = 0) {
    this.bounds = bounds;
    this.depth = depth;
  }

  clear(): void {
    this.objects = [];
    this.children = null;
  }

  private split(): void {
    const { x, y, width, height } = this.bounds;
    const hw = width / 2, hh = height / 2;
    const d = this.depth + 1;
    this.children = [
      new QuadTree({ x, y, width: hw, height: hh }, d),
      new QuadTree({ x: x + hw, y, width: hw, height: hh }, d),
      new QuadTree({ x, y: y + hh, width: hw, height: hh }, d),
      new QuadTree({ x: x + hw, y: y + hh, width: hw, height: hh }, d),
    ];
  }

  insert(obj: T): void {
    if (this.children) {
      for (const child of this.children) {
        if (this.intersects(obj, child.bounds)) {
          child.insert(obj);
        }
      }
      return;
    }

    this.objects.push(obj);

    if (this.objects.length > this.maxObjects && this.depth < this.maxDepth) {
      this.split();
      for (const o of this.objects) {
        for (const child of this.children!) {
          if (this.intersects(o, child.bounds)) child.insert(o);
        }
      }
      this.objects = [];
    }
  }

  query(range: Rect): T[] {
    const found: T[] = [];
    if (!this.intersects(range, this.bounds)) return found;

    for (const obj of this.objects) {
      if (this.intersects(obj, range)) found.push(obj);
    }

    if (this.children) {
      for (const child of this.children) {
        found.push(...child.query(range));
      }
    }
    return found;
  }

  private intersects(a: Rect, b: Rect): boolean {
    return a.x < b.x + b.width && a.x + a.width > b.x &&
           a.y < b.y + b.height && a.y + a.height > b.y;
  }
}