// Continuous circles and rotated fallen-log rectangles.
// A uniform spatial index limits swept collision checks to nearby obstacles.
import {W as WIDTH,H as HEIGHT} from './world-size.js?v=45';
const SIZE=120,EPS=.0001;
const clamp=(v,a,b)=>Math.max(a,Math.min(b,v));
const local=(c,x,y)=>{const co=Math.cos(c.angle||0),si=Math.sin(c.angle||0),dx=x-c.x,dy=y-c.y;return {x:co*dx+si*dy,y:-si*dx+co*dy}};
const world=(c,x,y)=>{const co=Math.cos(c.angle||0),si=Math.sin(c.angle||0);return {x:c.x+co*x-si*y,y:c.y+si*x+co*y}};
const rectOverlap=(c,x,y,r)=>{const q=local(c,x,y),dx=Math.max(Math.abs(q.x)-c.w/2,0),dy=Math.max(Math.abs(q.y)-c.h/2,0);return dx*dx+dy*dy<(r-EPS)**2||(dx===0&&dy===0)};
function roundedRectHit(c,x,y,dx,dy,r){
 const p=local(c,x,y),co=Math.cos(c.angle||0),si=Math.sin(c.angle||0),vx=co*dx+si*dy,vy=-si*dx+co*dy,hx=c.w/2,hy=c.h/2;
 let first=Infinity,nx=0,ny=0;
 const check=(t,a,b)=>{if(t>=0&&t<first&&t<=1){first=t;nx=a;ny=b}};
 if(vx){for(const sign of [-1,1]){const t=(sign*(hx+r+EPS)-p.x)/vx,y=p.y+vy*t;if(sign*vx<0&&Math.abs(y)<=hy)check(t,sign,0)}}
 if(vy){for(const sign of [-1,1]){const t=(sign*(hy+r+EPS)-p.y)/vy,x=p.x+vx*t;if(sign*vy<0&&Math.abs(x)<=hx)check(t,0,sign)}}
 const len=vx*vx+vy*vy;if(len)for(const sx of [-1,1])for(const sy of [-1,1]){
  const cx=sx*hx,cy=sy*hy,px=p.x-cx,py=p.y-cy,b=px*vx+py*vy,rr=r+EPS,disc=b*b-len*(px*px+py*py-rr*rr);
  if(b>=0||disc<0)continue;const t=(-b-Math.sqrt(disc))/len,xx=p.x+vx*t,yy=p.y+vy*t;
  if(sx*(xx-cx)<-EPS||sy*(yy-cy)<-EPS)continue;
  const n=Math.hypot(xx-cx,yy-cy)||1;check(t,(xx-cx)/n,(yy-cy)/n);
 }
 return first<=1?{t:first,x:co*nx-si*ny,y:si*nx+co*ny}:null;
}
const outputPosition=(out,x,y)=>{if(out){out.x=x;out.y=y;return out}return {x,y}};
export class RockField {
 constructor(circles=[],rects=[],preserveReferences=false){
  this.cellSize=SIZE;
  this.nx=Math.ceil(WIDTH/SIZE);this.ny=Math.ceil(HEIGHT/SIZE);
  this.cells=Array.from({length:this.nx*this.ny},()=>[]);
  this.circles=preserveReferences?circles:circles.map(c=>({...c}));this.rects=rects.map(r=>({...r}));
  this.shapes=[...this.circles.map(c=>preserveReferences?c:{...c,kind:'circle'}),...this.rects.map(r=>({...r,kind:'rect'}))];
  this.marks=new Uint32Array(this.shapes.length);this.stamp=0;
  for(let id=0;id<this.shapes.length;id++){
   const c=this.shapes[id],co=Math.cos(c.angle||0),si=Math.sin(c.angle||0),hx=c.kind==='circle'?c.r:Math.abs(co)*c.w/2+Math.abs(si)*c.h/2,hy=c.kind==='circle'?c.r:Math.abs(si)*c.w/2+Math.abs(co)*c.h/2,x0=c.x-hx,x1=c.x+hx,y0=c.y-hy,y1=c.y+hy;
   for(let x=Math.max(0,Math.floor(x0/SIZE));x<=Math.min(this.nx-1,Math.floor(x1/SIZE));x++)for(let y=Math.max(0,Math.floor(y0/SIZE));y<=Math.min(this.ny-1,Math.floor(y1/SIZE));y++)this.cells[x*this.ny+y].push(id);
  }
 }
 candidates(x0,y0,x1,y1,r){
  const out=[];this.stamp=(this.stamp+1)>>>0;if(!this.stamp){this.marks.fill(0);this.stamp=1}
  for(let x=Math.max(0,Math.floor((Math.min(x0,x1)-r)/SIZE));x<=Math.min(this.nx-1,Math.floor((Math.max(x0,x1)+r)/SIZE));x++)for(let y=Math.max(0,Math.floor((Math.min(y0,y1)-r)/SIZE));y<=Math.min(this.ny-1,Math.floor((Math.max(y0,y1)+r)/SIZE));y++)for(const id of this.cells[x*this.ny+y])if(this.marks[id]!==this.stamp){this.marks[id]=this.stamp;out.push(this.shapes[id])}
  return out;
 }
 free(x,y,r){
  if(x<r||x>WIDTH-r||y<r||y>HEIGHT-r)return false;
  for(const c of this.candidates(x,y,x,y,r)){
   if(c.kind==='rect'){if(rectOverlap(c,x,y,r))return false}
   else if((x-c.x)**2+(y-c.y)**2<(c.r+r-EPS)**2)return false;
  }
  return true;
 }
 freePoint(x,y){
  if(x<0||x>WIDTH||y<0||y>HEIGHT)return false;
  const ix=Math.min(this.nx-1,Math.floor(x/SIZE)),iy=Math.min(this.ny-1,Math.floor(y/SIZE));
  for(const id of this.cells[ix*this.ny+iy]){
   const c=this.shapes[id];
   if(c.kind==='rect'){if(rectOverlap(c,x,y,0))return false}
   else if((x-c.x)**2+(y-c.y)**2<(c.r-EPS)**2)return false;
  }
  return true;
 }
 findFree(x,y,r){
  if(this.free(x,y,r))return {x,y};let px=clamp(x,r+EPS,WIDTH-r-EPS),py=clamp(y,r+EPS,HEIGHT-r-EPS);
  for(let pass=0;pass<16;pass++){
   for(const c of this.candidates(px,py,px,py,r)){
    if(c.kind==='rect'){
     const q=local(c,px,py),left=-c.w/2-r-EPS,right=c.w/2+r+EPS,top=-c.h/2-r-EPS,bottom=c.h/2+r+EPS;
     if(q.x>left&&q.x<right&&q.y>top&&q.y<bottom){const choices=[{d:q.x-left,x:left,y:q.y},{d:right-q.x,x:right,y:q.y},{d:q.y-top,x:q.x,y:top},{d:bottom-q.y,x:q.x,y:bottom}].sort((a,b)=>a.d-b.d),p=world(c,choices[0].x,choices[0].y);px=clamp(p.x,r+EPS,WIDTH-r-EPS);py=clamp(p.y,r+EPS,HEIGHT-r-EPS)}
    }else{const dx=px-c.x,dy=py-c.y,d=Math.hypot(dx,dy),limit=c.r+r+EPS;if(d<limit){px=clamp(c.x+(d?dx/d:1)*limit,r+EPS,WIDTH-r-EPS);py=clamp(c.y+(d?dy/d:0)*limit,r+EPS,HEIGHT-r-EPS)}}
   }
   if(this.free(px,py,r))return {x:px,y:py};
  }
  let best=null,dist=Infinity;const consider=(qx,qy)=>{const d=(qx-x)**2+(qy-y)**2;if(d<dist&&this.free(qx,qy,r)){best={x:qx,y:qy};dist=d}};
  for(const c of this.shapes){if(c.kind==='rect'){for(const [qx,qy] of [[-c.w/2-r-.01,0],[c.w/2+r+.01,0],[0,-c.h/2-r-.01],[0,c.h/2+r+.01]]){const p=world(c,qx,qy);consider(p.x,p.y)}}else for(let j=0;j<24;j++){const a=j*Math.PI/12;consider(c.x+Math.cos(a)*(c.r+r+.01),c.y+Math.sin(a)*(c.r+r+.01))}}
  if(!best)for(let qx=r+1;qx<WIDTH-r;qx+=60)for(let qy=r+1;qy<HEIGHT-r;qy+=60)consider(qx,qy);return best;
 }
 move(x,y,dx,dy,r,out=null){
  if(!this.free(x,y,r)){const p=this.findFree(x,y,r);if(!p)return outputPosition(out,x,y);x=p.x;y=p.y}const startX=x,startY=y;
  for(let pass=0;pass<4;pass++){
   const targetX=clamp(x+dx,r+EPS,WIDTH-r-EPS),targetY=clamp(y+dy,r+EPS,HEIGHT-r-EPS);dx=targetX-x;dy=targetY-y;const len=dx*dx+dy*dy;if(len<1e-14)break;
   let hit=null,first=1,normalX=0,normalY=0;
   for(const c of this.candidates(x,y,targetX,targetY,r)){
    if(c.kind==='rect'){
     const contact=roundedRectHit(c,x,y,dx,dy,r);
     if(contact&&contact.t<first){first=contact.t;hit=c;normalX=contact.x;normalY=contact.y}
    }else{
     const px=x-c.x,py=y-c.y,b=px*dx+py*dy,rr=c.r+r+EPS,disc=b*b-len*(px*px+py*py-rr*rr);if(b>=0||disc<0)continue;
     const t=(-b-Math.sqrt(disc))/len;if(t>=-EPS&&t<first){first=Math.max(0,t);hit=c;normalX=normalY=0}
    }
   }
   if(!hit){x=targetX;y=targetY;break}
   x+=dx*first;y+=dy*first;
   if(hit.kind==='circle'){const nx=x-hit.x,ny=y-hit.y,n=Math.hypot(nx,ny)||1;normalX=nx/n;normalY=ny/n}
   dx*=1-first;dy*=1-first;const inward=Math.min(0,dx*normalX+dy*normalY);dx-=inward*normalX;dy-=inward*normalY;
  }
  return this.free(x,y,r)?outputPosition(out,x,y):outputPosition(out,startX,startY);
 }
 steer(x,y,dx,dy,r,side,targetTreeId=null,out=null){
  const n=Math.hypot(dx,dy)||1,ux=dx/n,uy=dy/n;
  for(const c of this.candidates(x,y,x+ux*32,y+uy*32,r)){
   if(c.steer===false||(targetTreeId!==null&&c.treeId===targetTreeId))continue;
   if(c.kind==='rect'){
    const q=local(c,x,y),lx=q.x-clamp(q.x,-c.w/2,c.w/2),ly=q.y-clamp(q.y,-c.h/2,c.h/2),distance=Math.hypot(lx,ly);
    if(distance>0&&distance<r+1){const co=Math.cos(c.angle||0),si=Math.sin(c.angle||0),nx=(co*lx-si*ly)/distance,ny=(si*lx+co*ly)/distance;if(ux*nx+uy*ny<0)return outputPosition(out,-ny*side+nx*.15,nx*side+ny*.15)}
    continue;
   }
   const px=x-c.x,py=y-c.y,d=Math.hypot(px,py)||1,limit=c.r+r+(c.treeId?12:6);
   if(d<limit&&ux*px+uy*py<0){const nx=px/d,ny=py/d;return outputPosition(out,-ny*side+nx*.15,nx*side+ny*.15)}
  }
  return outputPosition(out,dx,dy);
 }
}