<?php

namespace App\Engine\Map;

/**
 * Builds the BSP tree of a level (what the original engine's maps carry precomputed, made by a node builder):
 * the segs are split by partition lines until each leaf is convex. The renderer walks this tree front to back,
 * the game uses it to find the sector under a point.
 */
final class NodeBuilder
{
    private const EPS = 0.01;

    /** @var Node[] */
    public array $nodes = [];
    /** @var Subsector[] */
    public array $subsectors = [];
    public int $root = 0;

    /** @param Line[] $lines */
    public function __construct(array $lines)
    {
        $segs = [];
        foreach ($lines as $line) {
            $segs[] = new Seg($line->x1, $line->y1, $line->x2, $line->y2, $line, 0, 0.0);
            if ($line->back !== null) {
                $segs[] = new Seg($line->x2, $line->y2, $line->x1, $line->y1, $line, 1, 0.0);
            }
        }
        $this->root = $this->build($segs);
    }

    /** @param Seg[] $segs  @return int child id (node index, or -1 - subsector index) */
    private function build(array $segs): int
    {
        $best = $this->choose($segs);
        if ($best === null) {
            $this->subsectors[] = new Subsector($segs[0]->frontSector, $segs);
            return -1 - (count($this->subsectors) - 1);
        }
        [$px, $py, $pdx, $pdy] = $best;
        $front = [];
        $back = [];
        foreach ($segs as $s) {
            $a = self::cross($px, $py, $pdx, $pdy, $s->x1, $s->y1);
            $b = self::cross($px, $py, $pdx, $pdy, $s->x2, $s->y2);
            $sa = abs($a) < self::EPS ? 0 : ($a > 0 ? 1 : -1);
            $sb = abs($b) < self::EPS ? 0 : ($b > 0 ? 1 : -1);
            if ($sa === 0 && $sb === 0) {
                // on the partition: same direction goes front
                if (($s->x2 - $s->x1) * $pdx + ($s->y2 - $s->y1) * $pdy > 0) {
                    $front[] = $s;
                } else {
                    $back[] = $s;
                }
            } elseif ($sa >= 0 && $sb >= 0) {
                $front[] = $s;
            } elseif ($sa <= 0 && $sb <= 0) {
                $back[] = $s;
            } else {
                // split at the crossing point
                $t = $a / ($a - $b);
                $ix = $s->x1 + ($s->x2 - $s->x1) * $t;
                $iy = $s->y1 + ($s->y2 - $s->y1) * $t;
                $len = sqrt(($ix - $s->x1) ** 2 + ($iy - $s->y1) ** 2);
                $first = new Seg($s->x1, $s->y1, $ix, $iy, $s->line, $s->side, $s->offset);
                $second = new Seg($ix, $iy, $s->x2, $s->y2, $s->line, $s->side, $s->offset + $len);
                if ($sa > 0) {
                    $front[] = $first;
                    $back[] = $second;
                } else {
                    $back[] = $first;
                    $front[] = $second;
                }
            }
        }
        $node = new Node($px, $py, $pdx, $pdy);
        $index = count($this->nodes);
        $this->nodes[] = $node;
        $node->bbox = [self::bbox($front), self::bbox($back)];
        $node->children = [$this->build($front), $this->build($back)];
        return $index;
    }

    /** The best partition (a seg's line), or null when the segs already form a convex leaf. */
    private function choose(array $segs): ?array
    {
        $n = count($segs);
        if ($this->convex($segs)) {
            return null;
        }
        $step = max(1, intdiv($n, 48));
        $bestCost = PHP_INT_MAX;
        $best = null;
        for ($i = 0; $i < $n; $i += $step) {
            $p = $segs[$i];
            $pdx = $p->x2 - $p->x1;
            $pdy = $p->y2 - $p->y1;
            $front = $back = $splits = 0;
            foreach ($segs as $s) {
                $a = self::cross($p->x1, $p->y1, $pdx, $pdy, $s->x1, $s->y1);
                $b = self::cross($p->x1, $p->y1, $pdx, $pdy, $s->x2, $s->y2);
                $sa = abs($a) < self::EPS ? 0 : ($a > 0 ? 1 : -1);
                $sb = abs($b) < self::EPS ? 0 : ($b > 0 ? 1 : -1);
                if ($sa === 0 && $sb === 0) {
                    (($s->x2 - $s->x1) * $pdx + ($s->y2 - $s->y1) * $pdy > 0) ? $front++ : $back++;
                } elseif ($sa >= 0 && $sb >= 0) {
                    $front++;
                } elseif ($sa <= 0 && $sb <= 0) {
                    $back++;
                } else {
                    $splits++;
                }
            }
            if ($back === 0 && $splits === 0) {
                continue;     // everything in front: not a partition
            }
            $cost = $splits * 6 + abs($front - $back);
            // prefer axis-aligned partitions a little (fewer odd splits)
            if (abs($pdx) > self::EPS && abs($pdy) > self::EPS) {
                $cost += 4;
            }
            if ($cost < $bestCost) {
                $bestCost = $cost;
                $best = [$p->x1, $p->y1, $pdx, $pdy];
            }
        }
        if ($best === null) {
            // sampling missed every partition: try them all
            foreach ($segs as $p) {
                $pdx = $p->x2 - $p->x1;
                $pdy = $p->y2 - $p->y1;
                foreach ($segs as $s) {
                    if (self::cross($p->x1, $p->y1, $pdx, $pdy, $s->x1, $s->y1) < -self::EPS
                        || self::cross($p->x1, $p->y1, $pdx, $pdy, $s->x2, $s->y2) < -self::EPS) {
                        return [$p->x1, $p->y1, $pdx, $pdy];
                    }
                }
            }
        }
        return $best;
    }

    /** Every seg in front of every other one's line, and one sector. */
    private function convex(array $segs): bool
    {
        $sector = $segs[0]->frontSector;
        foreach ($segs as $p) {
            if ($p->frontSector !== $sector) {
                return false;
            }
            $pdx = $p->x2 - $p->x1;
            $pdy = $p->y2 - $p->y1;
            foreach ($segs as $s) {
                if (self::cross($p->x1, $p->y1, $pdx, $pdy, $s->x1, $s->y1) < -self::EPS
                    || self::cross($p->x1, $p->y1, $pdx, $pdy, $s->x2, $s->y2) < -self::EPS) {
                    return false;
                }
            }
        }
        return true;
    }

    /** > 0 when (x, y) is on the right (front) of the line through (px, py) along (dx, dy). */
    private static function cross(float $px, float $py, float $dx, float $dy, float $x, float $y): float
    {
        $len = sqrt($dx * $dx + $dy * $dy) ?: 1.0;
        return (($x - $px) * $dy - ($y - $py) * $dx) / $len;
    }

    /** @param Seg[] $segs  @return array{0: float, 1: float, 2: float, 3: float} top, bottom, left, right */
    private static function bbox(array $segs): array
    {
        $t = $r = -INF;
        $b = $l = INF;
        foreach ($segs as $s) {
            $t = max($t, $s->y1, $s->y2);
            $b = min($b, $s->y1, $s->y2);
            $l = min($l, $s->x1, $s->x2);
            $r = max($r, $s->x1, $s->x2);
        }
        return [$t, $b, $l, $r];
    }
}