<?phpnamespace App\Game;/** Static brush broad phase and bounded, radius-aware navigation through room portals. * Paths contain feet positions. No geometry or actor positions are ever changed here. */final class Navigation{ public const CELL = 0.6; public const MAX_EXPANSIONS = 2048; private array $buckets = []; private array $rooms = []; private array $links = []; private array $roomRoutes = []; private array $jobs = []; private array $ready = []; private array $queue = []; public const EXPANSIONS_PER_FRAME = 96; public int $searches = 0; public int $expansions = 0; public int $failed = 0; public int $budgetExhausted = 0; public function __construct(private readonly BrushMap $map) { foreach ($map->solids as $id => $s) { for ($x=(int)floor($s['min'][0]/4);$x<=(int)floor($s['max'][0]/4);$x++) for ($z=(int)floor($s['min'][2]/4);$z<=(int)floor($s['max'][2]/4);$z++) $this->buckets["$x:$z"][]=$id; } } public function setRooms(array $rooms): void { $this->rooms=$rooms;$this->links=[];$this->roomRoutes=[]; foreach($rooms as $i=>$a)foreach($rooms as $j=>$b){ if($i===$j)continue; foreach($a['connectors'] as $ca)foreach($b['connectors'] as $cb){ $p=$ca['position'];$q=$cb['position']; if(hypot($p[0]-$q[0],$p[2]-$q[2])<.05 && abs($p[1]-$q[1])<.05){ $this->links[$i][$j]=$p; } } } } private function solids(float $x,float $z,float $radius): array { $ids=[]; for($ix=(int)floor(($x-$radius)/4);$ix<=(int)floor(($x+$radius)/4);$ix++) for($iz=(int)floor(($z-$radius)/4);$iz<=(int)floor(($z+$radius)/4);$iz++) foreach($this->buckets["$ix:$iz"]??[] as $id)$ids[$id]=true; return $ids; } public function collides(float $x,float $y,float $z,float $radius,float $half): bool { foreach($this->solids($x,$z,$radius) as $id=>$_){ $s=$this->map->solids[$id]; if($y+$half<=$s['min'][1]+.001||$y-$half>=$s['max'][1]-.001)continue; $dx=$x-max($s['min'][0],min($s['max'][0],$x));$dz=$z-max($s['min'][2],min($s['max'][2],$z)); if($dx*$dx+$dz*$dz<$radius*$radius)return true; } return false; } public function support(float $x,float $z,float $radius,float $ceiling): ?float { $top=null; foreach($this->solids($x,$z,$radius) as $id=>$_){ $s=$this->map->solids[$id];$h=$s['max'][1]; if($h>$ceiling+.002||($top!==null&&$h<$top))continue; $dx=$x-max($s['min'][0],min($s['max'][0],$x));$dz=$z-max($s['min'][2],min($s['max'][2],$z)); if($dx*$dx+$dz*$dz<$radius*$radius)$top=$h; } return $top; } /** Sweep with real support, step-up and drop limits; prevents corner cutting and floor shortcuts. */ public function traverse(array $from,array $to,float $radius,float $half=.55): ?array { $n=max(1,(int)ceil(hypot($to[0]-$from[0],$to[2]-$from[2])/.2));$floor=$from[1]; for($i=1;$i<=$n;$i++){ $x=$from[0]+($to[0]-$from[0])*$i/$n;$z=$from[2]+($to[2]-$from[2])*$i/$n; $h=$this->support($x,$z,$radius,$floor+.58); if($h===null||$h<$floor-.8||$this->collides($x,$h+$half,$z,$radius,$half))return null; $floor=$h; } return [$to[0],$floor,$to[2]]; } private function roomAt(array $p): ?int { $best=null;$score=INF; foreach($this->rooms as $id=>$r){$b=$r['bounds']; if($p[0]<$b['min'][0]-.1||$p[0]>$b['max'][0]+.1||$p[2]<$b['min'][2]-.1||$p[2]>$b['max'][2]+.1)continue; // Bounds include walls/ceilings; connectors give the actual floor range. $ys=array_column(array_column($r['connectors'],'position'),1); $d=max(min($ys)-$p[1],$p[1]-max($ys),0); if($d<$score){$score=$d;$best=$id;} } return $best; } private function portal(array $from,array $to): array { $a=$this->roomAt($from);$b=$this->roomAt($to); if($a===null||$b===null||$a===$b)return $to; $key="$a:$b"; if(!array_key_exists($key,$this->roomRoutes)){ $q=[$a];$previous=[$a=>null]; for($i=0;$i<count($q)&&!array_key_exists($b,$previous);$i++)foreach($this->links[$q[$i]]??[] as $next=>$_){ if(array_key_exists($next,$previous))continue;$previous[$next]=$q[$i];$q[]=$next; } $next=$b; if(!array_key_exists($b,$previous))$next=null; else while($previous[$next]!==$a)$next=$previous[$next]; $this->roomRoutes[$key]=$next; } $next=$this->roomRoutes[$key]; if($next===null)return $to; $p=$this->links[$a][$next]; // Go beyond the shared doorway so room selection advances unambiguously. $r=$this->rooms[$next]['bounds'];$cx=($r['min'][0]+$r['max'][0])/2;$cz=($r['min'][2]+$r['max'][2])/2; $d=max(.001,hypot($cx-$p[0],$cz-$p[2])); return [$p[0]+($cx-$p[0])/$d*.9,$p[1],$p[2]+($cz-$p[2])/$d*.9]; } /** Local A* toward the next portal; deterministic bounded search, never a partial unsafe shortcut. */ public function path(array $from,array $to,float $radius,float $half=.55): array { $search=$this->search($from,$to,$radius,$half); foreach($search as $_) {} return $search->getReturn(); } /** Enemies share a frame budget; expensive searches resume instead of blocking a frame. */ public function request(int $id,array $from,array $to,float $radius): ?array { if(isset($this->jobs[$id]))return null; unset($this->ready[$id]); $g=$this->search($from,$to,$radius,.55); if(!$g->valid())return $g->getReturn(); $this->jobs[$id]=$g;$this->queue[]=$id; return null; } public function poll(int $id): ?array { if(!array_key_exists($id,$this->ready))return null; $path=$this->ready[$id];unset($this->ready[$id]);return $path; } public function pump(array $liveIds): void { for($i=0;$i<self::EXPANSIONS_PER_FRAME&&$this->queue!==[];$i++){ $id=array_shift($this->queue); if(!isset($liveIds[$id])){unset($this->jobs[$id],$this->ready[$id]);continue;} $g=$this->jobs[$id];$g->next(); if($g->valid())$this->queue[]=$id; else{$this->ready[$id]=$g->getReturn();unset($this->jobs[$id]);} } foreach($this->ready as $id=>$_)if(!isset($liveIds[$id]))unset($this->ready[$id]); } private function search(array $from,array $to,float $radius,float $half): \Generator { $this->searches++; $goal=$this->portal($from,$to); // The player can fit closer to a wall than a guardian or brute. Aim for // reachable melee distance instead of searching forever for that exact point. if($this->collides($goal[0],$goal[1]+$half,$goal[2],$radius,$half)){ $best=null;$distance=INF; for($i=0;$i<16;$i++){ $a=$i*M_PI/8;$p=[$goal[0]+sin($a)*.5,$goal[1],$goal[2]+cos($a)*.5]; $h=$this->support($p[0],$p[2],$radius,$goal[1]+.58); if($h===null||abs($h-$goal[1])>.8||$this->collides($p[0],$h+$half,$p[2],$radius,$half))continue; $p[1]=$h; if($this->traverse($p,$goal,.01,$half)===null)continue; $d=hypot($from[0]-$p[0],$from[2]-$p[2]);if($d<$distance){$distance=$d;$best=$p;} } if($best!==null)$goal=$best; } $direct=$this->traverse($from,$goal,$radius,$half); if($direct!==null && abs($direct[1]-$goal[1])<.81)return [$direct]; $open=new \SplPriorityQueue();$open->setExtractFlags(\SplPriorityQueue::EXTR_DATA); $open->insert('start',0);$points=['start'=>$from];$cost=['start'=>0];$previous=[];$closed=[]; $found=null;$count=0; while(!$open->isEmpty()&&$count<self::MAX_EXPANSIONS){ $key=$open->extract();if(isset($closed[$key]))continue;$closed[$key]=true;$count++;$this->expansions++;yield null;$p=$points[$key]; if(hypot($goal[0]-$p[0],$goal[2]-$p[2])<1.0){ $end=$this->traverse($p,$goal,$radius,$half); if($end!==null&&abs($end[1]-$goal[1])<.81){$found=$key;break;} } foreach([[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]] as [$dx,$dz]){ $ix=(int)round($p[0]/self::CELL)+$dx;$iz=(int)round($p[2]/self::CELL)+$dz; $n=$this->traverse($p,[$ix*self::CELL,$p[1],$iz*self::CELL],$radius,$half);if($n===null)continue; $nk="$ix:$iz:".(int)round($n[1]*100);if(isset($closed[$nk]))continue; $g=$cost[$key]+hypot($n[0]-$p[0],$n[2]-$p[2]); if($g>=($cost[$nk]??INF))continue; $points[$nk]=$n;$cost[$nk]=$g;$previous[$nk]=$key; $open->insert($nk,-($g+hypot($goal[0]-$n[0],$goal[2]-$n[2]))); } } if($found===null){$this->failed++;if($count===self::MAX_EXPANSIONS)$this->budgetExhausted++;return [];} $path=[$end]; while($found!=='start'){$path[]=$points[$found];$found=$previous[$found];} return array_reverse($path); }}