<?phpnamespace 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]; }}