src/game/g_grid.pas

   1 (* Copyright (C)  DooM 2D:Forever Developers
   2  *
   3  * This program is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  15  *)
  16 // universal spatial grid
  17 {$INCLUDE ../shared/a_modes.inc}
  18 {$DEFINE grid_use_buckets}
  19 unit g_grid;
  20
  21 interface
  22
  23
  24 type
  25   TBodyProxyId = Integer;
  26
  27   generic TBodyGridBase<ITP> = class(TObject)
  28   public
  29     type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
  30     type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
  31
  32   private
  33     const
  34       GridDefaultTileSize = 32;
  35       GridCellBucketSize = 8; // WARNING! can't be less than 2!
  36
  37   private
  38     type
  39       PBodyProxyRec = ^TBodyProxyRec;
  40       TBodyProxyRec = record
  41       private
  42         mX, mY, mWidth, mHeight: Integer; // aabb
  43         mQueryMark: LongWord; // was this object visited at this query?
  44         mObj: ITP;
  45         mTag: Integer;
  46         nextLink: TBodyProxyId; // next free or nothing
  47
  48       private
  49         procedure setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
  50       end;
  51
  52       PGridCell = ^TGridCell;
  53       TGridCell = record
  54         {$IFDEF grid_use_buckets}
  55         bodies: array [0..GridCellBucketSize-1] of Integer; // -1: end of list
  56         {$ELSE}
  57         body: Integer;
  58         {$ENDIF}
  59         next: Integer; // in this cell; index in mCells
  60       end;
  61
  62       TGridInternalCB = function (grida: Integer): Boolean of object; // return `true` to stop
  63
  64   private
  65     mTileSize: Integer;
  66     mMinX, mMinY: Integer; // so grids can start at any origin
  67     mWidth, mHeight: Integer; // in tiles
  68     mGrid: array of Integer; // mWidth*mHeight, index in mCells
  69     mCells: array of TGridCell; // cell pool
  70     mFreeCell: Integer; // first free cell index or -1
  71     mLastQuery: LongWord;
  72     mUsedCells: Integer;
  73     mProxies: array of TBodyProxyRec;
  74     mProxyFree: TBodyProxyId; // free
  75     mProxyCount: Integer; // currently used
  76     mProxyMaxCount: Integer;
  77
  78     mUData: TBodyProxyId; // for inserter/remover
  79     mTagMask: Integer; // for iterator
  80     mItCB: TGridQueryCB; // for iterator
  81
  82   private
  83     function allocCell: Integer;
  84     procedure freeCell (idx: Integer); // `next` is simply overwritten
  85
  86     function allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
  87     procedure freeProxy (body: TBodyProxyId);
  88
  89     procedure insert (body: TBodyProxyId);
  90     procedure remove (body: TBodyProxyId);
  91
  92     function forGridRect (x, y, w, h: Integer; cb: TGridInternalCB): Boolean;
  93
  94     function inserter (grida: Integer): Boolean;
  95     function remover (grida: Integer): Boolean;
  96
  97   public
  98     constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
  99     destructor Destroy (); override;
 100
 101     function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
 102     procedure removeBody (aObj: TBodyProxyId); // WARNING! this WILL destroy proxy!
 103
 104     procedure moveBody (body: TBodyProxyId; dx, dy: Integer);
 105     procedure resizeBody (body: TBodyProxyId; sx, sy: Integer);
 106     procedure moveResizeBody (body: TBodyProxyId; dx, dy, sx, sy: Integer);
 107
 108     //WARNING: can't do recursive queries
 109     function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
 110
 111     //WARNING: can't do recursive queries
 112     function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
 113
 114     //WARNING: can't do recursive queries
 115     // cb with `(nil)` will be called before processing new tile
 116     function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean; overload;
 117
 118     procedure dumpStats ();
 119   end;
 120
 121
 122 implementation
 123
 124 uses
 125   SysUtils, e_log;
 126
 127
 128 // ////////////////////////////////////////////////////////////////////////// //
 129 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
 130 begin
 131   mX := aX;
 132   mY := aY;
 133   mWidth := aWidth;
 134   mHeight := aHeight;
 135   mQueryMark := 0;
 136   mObj := aObj;
 137   mTag := aTag;
 138   nextLink := -1;
 139 end;
 140
 141
 142 // ////////////////////////////////////////////////////////////////////////// //
 143 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
 144 var
 145   idx: Integer;
 146 begin
 147   if aTileSize < 1 then aTileSize := 1;
 148   if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
 149   if aPixWidth < aTileSize then aPixWidth := aTileSize;
 150   if aPixHeight < aTileSize then aPixHeight := aTileSize;
 151   mTileSize := aTileSize;
 152   mMinX := aMinPixX;
 153   mMinY := aMinPixY;
 154   mWidth := (aPixWidth+aTileSize-1) div aTileSize;
 155   mHeight := (aPixHeight+aTileSize-1) div aTileSize;
 156   SetLength(mGrid, mWidth*mHeight);
 157   SetLength(mCells, mWidth*mHeight);
 158   SetLength(mProxies, 8192);
 159   mFreeCell := 0;
 160   // init free list
 161   for idx := 0 to High(mCells) do
 162   begin
 163     {$IFDEF grid_use_buckets}
 164     mCells[idx].bodies[0] := -1;
 165     {$ELSE}
 166     mCells[idx].body := -1;
 167     {$ENDIF}
 168     mCells[idx].next := idx+1;
 169   end;
 170   mCells[High(mCells)].next := -1; // last cell
 171   // init grid
 172   for idx := 0 to High(mGrid) do mGrid[idx] := -1;
 173   // init proxies
 174   for idx := 0 to High(mProxies) do mProxies[idx].nextLink := idx+1;
 175   mProxies[High(mProxies)].nextLink := -1;
 176   mLastQuery := 0;
 177   mUsedCells := 0;
 178   mProxyFree := 0;
 179   mProxyCount := 0;
 180   mProxyMaxCount := 0;
 181   mUData := 0;
 182   mTagMask := -1;
 183   mItCB := nil;
 184   e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
 185 end;
 186
 187
 188 destructor TBodyGridBase.Destroy ();
 189 begin
 190   mCells := nil;
 191   mGrid := nil;
 192   mProxies := nil;
 193   inherited;
 194 end;
 195
 196
 197 procedure TBodyGridBase.dumpStats ();
 198 var
 199   idx, mcb, cidx, cnt: Integer;
 200 begin
 201   mcb := 0;
 202   for idx := 0 to High(mGrid) do
 203   begin
 204     cidx := mGrid[idx];
 205     cnt := 0;
 206     while cidx >= 0 do
 207     begin
 208       Inc(cnt);
 209       cidx := mCells[cidx].next;
 210     end;
 211     if (mcb < cnt) then mcb := cnt;
 212   end;
 213   e_WriteLog(Format('grid size: %dx%d (tile size: %d); pix: %dx%d; used cells: %d; max bodies in cell: %d; max proxies allocated: %d; proxies used: %d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize, mUsedCells, mcb, mProxyMaxCount, mProxyCount]), MSG_NOTIFY);
 214 end;
 215
 216
 217 function TBodyGridBase.allocCell: Integer;
 218 var
 219   idx: Integer;
 220 begin
 221   if (mFreeCell < 0) then
 222   begin
 223     // no free cells, want more
 224     mFreeCell := Length(mCells);
 225     SetLength(mCells, mFreeCell+32768); // arbitrary number
 226     for idx := mFreeCell to High(mCells) do
 227     begin
 228       {$IFDEF grid_use_buckets}
 229       mCells[idx].bodies[0] := -1;
 230       {$ELSE}
 231       mCells[idx].body := -1;
 232       {$ENDIF}
 233       mCells[idx].next := idx+1;
 234     end;
 235     mCells[High(mCells)].next := -1; // last cell
 236   end;
 237   result := mFreeCell;
 238   mFreeCell := mCells[result].next;
 239   mCells[result].next := -1;
 240   Inc(mUsedCells);
 241   //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
 242 end;
 243
 244
 245 procedure TBodyGridBase.freeCell (idx: Integer);
 246 begin
 247   if (idx >= 0) and (idx < High(mCells)) then
 248   begin
 249     //if mCells[idx].body = -1 then exit; // the thing that should not be
 250     //mCells[idx].body := -1;
 251     mCells[idx].next := mFreeCell;
 252     mFreeCell := idx;
 253     Dec(mUsedCells);
 254   end;
 255 end;
 256
 257
 258 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
 259 var
 260   olen, idx: Integer;
 261   px: PBodyProxyRec;
 262 begin
 263   if (mProxyFree = -1) then
 264   begin
 265     // no free proxies, resize list
 266     olen := Length(mProxies);
 267     SetLength(mProxies, olen+8192); // arbitrary number
 268     for idx := olen to High(mProxies) do mProxies[idx].nextLink := idx+1;
 269     mProxies[High(mProxies)].nextLink := -1;
 270     mProxyFree := olen;
 271   end;
 272   // get one from list
 273   result := mProxyFree;
 274   px := @mProxies[result];
 275   mProxyFree := px.nextLink;
 276   px.setup(aX, aY, aWidth, aHeight, aObj, aTag);
 277   // add to used list
 278   px.nextLink := -1;
 279   // statistics
 280   Inc(mProxyCount);
 281   if (mProxyMaxCount < mProxyCount) then mProxyMaxCount := mProxyCount;
 282 end;
 283
 284 procedure TBodyGridBase.freeProxy (body: TBodyProxyId);
 285 begin
 286   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 287   if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
 288   // add to free list
 289   mProxies[body].mObj := nil;
 290   mProxies[body].nextLink := mProxyFree;
 291   mProxyFree := body;
 292   Dec(mProxyCount);
 293 end;
 294
 295
 296 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB): Boolean;
 297 var
 298   gx, gy: Integer;
 299 begin
 300   result := false;
 301   if (w < 1) or (h < 1) or not assigned(cb) then exit;
 302   // fix coords
 303   Dec(x, mMinX);
 304   Dec(y, mMinY);
 305   // go on
 306   if (x+w <= 0) or (y+h <= 0) then exit;
 307   if (x >= mWidth*mTileSize) or (y >= mHeight*mTileSize) then exit;
 308   for gy := y div mTileSize to (y+h-1) div mTileSize do
 309   begin
 310     if (gy < 0) then continue;
 311     if (gy >= mHeight) then break;
 312     for gx := x div mTileSize to (x+w-1) div mTileSize do
 313     begin
 314       if (gx < 0) then continue;
 315       if (gx >= mWidth) then break;
 316       result := cb(gy*mWidth+gx);
 317       if result then exit;
 318     end;
 319   end;
 320 end;
 321
 322
 323 // ////////////////////////////////////////////////////////////////////////// //
 324 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
 325 var
 326   idx, ga, curci: Integer;
 327   f: Integer;
 328   cc: PGridCell = nil;
 329   px: PBodyProxyRec;
 330   lq: LongWord;
 331 begin
 332   result := false;
 333   if not assigned(cb) or (tagmask = 0) then exit;
 334
 335   Dec(x, mMinX);
 336   Dec(y, mMinY);
 337   if (x < 0) or (y < 0) or (x >= mWidth*mTileSize) or (y >= mHeight*mTileSize) then exit;
 338
 339   ga := (y div mTileSize)*mWidth+(x div mTileSize);
 340   curci := mGrid[ga];
 341   Inc(x, mMinX);
 342   Inc(y, mMinY);
 343
 344   // increase query counter
 345   Inc(mLastQuery);
 346   if (mLastQuery = 0) then
 347   begin
 348     // just in case of overflow
 349     mLastQuery := 1;
 350     for idx := 0 to High(mProxies) do mProxies[idx].mQueryMark := 0;
 351   end;
 352   lq := mLastQuery;
 353
 354   while (curci <> -1) do
 355   begin
 356     cc := @mCells[curci];
 357     for f := 0 to High(TGridCell.bodies) do
 358     begin
 359       if (cc.bodies[f] = -1) then break;
 360       px := @mProxies[cc.bodies[f]];
 361       if (px.mQueryMark <> lq) and ((px.mTag and tagmask) <> 0) then
 362       begin
 363         if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
 364         begin
 365           px.mQueryMark := lq;
 366           result := cb(px.mObj, px.mTag);
 367           if result then exit;
 368         end;
 369       end;
 370     end;
 371     curci := cc.next;
 372   end;
 373 end;
 374
 375
 376 // ////////////////////////////////////////////////////////////////////////// //
 377 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean;
 378 var
 379   i: Integer;
 380   dx, dy: Integer;
 381   xerr, yerr, d: LongWord;
 382   incx, incy: Integer;
 383   x, y: Integer;
 384   maxx, maxy: Integer;
 385   tsize: Integer; // tile size
 386   gw, gh: Integer;
 387   lastGA: Integer = -1;
 388   ga: Integer = -1; // last used grid address
 389   ccidx: Integer = -1;
 390   curci: Integer = -1;
 391   cc: PGridCell = nil;
 392   hasUntried: Boolean;
 393   f: Integer;
 394   px: PBodyProxyRec;
 395   lq: LongWord;
 396   prevX, prevY: Integer;
 397   minx, miny: Integer;
 398 begin
 399   result := false;
 400
 401   if (tagmask = 0) then exit;
 402
 403   // make coords (0,0)-based
 404   minx := mMinX;
 405   miny := mMinY;
 406   Dec(x0, minx);
 407   Dec(y0, miny);
 408   Dec(x1, minx);
 409   Dec(y1, miny);
 410
 411   xerr := 0;
 412   yerr := 0;
 413   dx := x1-x0;
 414   dy := y1-y0;
 415
 416   if (dx > 0) then incx := 1 else if (dx < 0) then incx := -1 else incx := 0;
 417   if (dy > 0) then incy := 1 else if (dy < 0) then incy := -1 else incy := 0;
 418
 419   dx := abs(dx);
 420   dy := abs(dy);
 421
 422   if (dx > dy) then d := dx else d := dy;
 423
 424   x := x0;
 425   y := y0;
 426
 427   // increase query counter
 428   Inc(mLastQuery);
 429   if (mLastQuery = 0) then
 430   begin
 431     // just in case of overflow
 432     mLastQuery := 1;
 433     for i := 0 to High(mProxies) do mProxies[i].mQueryMark := 0;
 434   end;
 435   lq := mLastQuery;
 436
 437   tsize := mTileSize;
 438   gw := mWidth;
 439   gh := mHeight;
 440   maxx := gw*tsize-1;
 441   maxy := gh*tsize-1;
 442
 443   for i := 1 to d do
 444   begin
 445     prevX := x;
 446     prevY := y;
 447     Inc(xerr, dx); if (xerr > d) then begin Dec(xerr, d); Inc(x, incx); end;
 448     Inc(yerr, dy); if (yerr > d) then begin Dec(yerr, d); Inc(y, incy); end;
 449
 450     if (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy) then
 451     begin
 452       ga := (y div tsize)*gw+(x div tsize);
 453       if (lastGA <> ga) then
 454       begin
 455         // new cell
 456         lastGA := ga;
 457         ccidx := mGrid[lastGA];
 458         if (ccidx <> -1) then
 459         begin
 460           result := cb(nil, 0, x+minx, y+miny, prevX+minx, prevY+miny);
 461           if result then exit;
 462         end;
 463       end;
 464     end
 465     else
 466     begin
 467       ccidx := -1;
 468     end;
 469
 470     if (ccidx <> -1) then
 471     begin
 472       curci := ccidx;
 473       hasUntried := false;
 474       while (curci <> -1) do
 475       begin
 476         cc := @mCells[curci];
 477         for f := 0 to High(TGridCell.bodies) do
 478         begin
 479           if (cc.bodies[f] = -1) then break;
 480           px := @mProxies[cc.bodies[f]];
 481           if (px.mQueryMark <> lq) and ((px.mTag and tagmask) <> 0) then
 482           begin
 483             if (x+minx >= px.mX) and (y+miny >= px.mY) and (x+minx < px.mX+px.mWidth) and (y+miny < px.mY+px.mHeight) then
 484             begin
 485               px.mQueryMark := lq;
 486               result := cb(px.mObj, px.mTag, x+minx, y+miny, prevX+minx, prevY+miny);
 487               if result then exit;
 488             end
 489             else
 490             begin
 491               hasUntried := true;
 492             end;
 493           end;
 494         end;
 495         curci := cc.next;
 496       end;
 497       if not hasUntried then ccidx := -1; // don't process this cell anymore
 498     end;
 499   end;
 500 end;
 501
 502
 503 function TBodyGridBase.inserter (grida: Integer): Boolean;
 504 var
 505   cidx: Integer;
 506   pc: PInteger;
 507   {$IFDEF grid_use_buckets}
 508   pi: PGridCell;
 509   f: Integer;
 510   {$ENDIF}
 511 begin
 512   result := false; // never stop
 513   // add body to the given grid cell
 514   pc := @mGrid[grida];
 515   {$IFDEF grid_use_buckets}
 516   if (pc^ <> -1) then
 517   begin
 518     pi := @mCells[pc^];
 519     f := 0;
 520     for f := 0 to High(TGridCell.bodies) do
 521     begin
 522       if (pi.bodies[f] = -1) then
 523       begin
 524         // can add here
 525         pi.bodies[f] := mUData;
 526         if (f+1 < Length(TGridCell.bodies)) then pi.bodies[f+1] := -1;
 527         exit;
 528       end;
 529     end;
 530   end;
 531   // either no room, or no cell at all
 532   cidx := allocCell();
 533   mCells[cidx].bodies[0] := mUData;
 534   mCells[cidx].bodies[1] := -1;
 535   mCells[cidx].next := pc^;
 536   pc^ := cidx;
 537   {$ELSE}
 538   cidx := allocCell();
 539   //e_WriteLog(Format('  01: allocated cell for grid coords (%d,%d), body coords:(%d,%d): #%d', [gx, gy, dx, dy, cidx]), MSG_NOTIFY);
 540   mCells[cidx].body := mUData;
 541   mCells[cidx].next := pc^;
 542   pc^ := cidx;
 543   {$ENDIF}
 544 end;
 545
 546
 547 procedure TBodyGridBase.insert (body: TBodyProxyId);
 548 var
 549   px: PBodyProxyRec;
 550 begin
 551   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 552   px := @mProxies[body];
 553   mUData := body;
 554   forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, inserter);
 555 end;
 556
 557
 558 function TBodyGridBase.remover (grida: Integer): Boolean;
 559 var
 560   pidx, idx, tmp, f: Integer;
 561   pc: PGridCell;
 562 begin
 563   result := false; // never stop
 564   // find and remove cell
 565   pidx := -1;
 566   idx := mGrid[grida];
 567   while (idx >= 0) do
 568   begin
 569     tmp := mCells[idx].next;
 570     {$IFDEF grid_use_buckets}
 571     pc := @mCells[idx];
 572     f := 0;
 573     while (f < High(TGridCell.bodies)) do
 574     begin
 575       if (pc.bodies[f] = mUData) then
 576       begin
 577         // i found her!
 578         if (f = 0) and (pc.bodies[1] = -1) then
 579         begin
 580           // this cell contains no elements, remove it
 581           tmp := mCells[idx].next;
 582           if (pidx = -1) then mGrid[grida] := tmp else mCells[pidx].next := tmp;
 583           freeCell(idx);
 584         end
 585         else
 586         begin
 587           // remove element from bucket
 588           Inc(f);
 589           while (f < High(TGridCell.bodies)) do
 590           begin
 591             pc.bodies[f-1] := pc.bodies[f];
 592             if (pc.bodies[f] = -1) then break;
 593             Inc(f);
 594           end;
 595           pc.bodies[High(TGridCell.bodies)] := -1; // just in case
 596         end;
 597         exit; // assume that we cannot have one object added to bucket twice
 598       end;
 599       Inc(f);
 600     end;
 601     {$ELSE}
 602     if (mCells[idx].body = mUData) then
 603     begin
 604       if (pidx = -1) then mGrid[grida] := tmp else mCells[pidx].next := tmp;
 605       freeCell(idx);
 606       exit; // assume that we cannot have one object added to bucket twice
 607     end;
 608     {$ENDIF}
 609     pidx := idx;
 610     idx := tmp;
 611   end;
 612 end;
 613
 614
 615 // absolutely not tested
 616 procedure TBodyGridBase.remove (body: TBodyProxyId);
 617 var
 618   px: PBodyProxyRec;
 619 begin
 620   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 621   px := @mProxies[body];
 622   mUData := body;
 623   forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover);
 624 end;
 625
 626
 627 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
 628 begin
 629   result := allocProxy(aX, aY, aWidth, aHeight, aObj, aTag);
 630   insert(result);
 631 end;
 632
 633
 634 procedure TBodyGridBase.removeBody (aObj: TBodyProxyId);
 635 begin
 636   if (aObj < 0) or (aObj > High(mProxies)) then exit; // just in case
 637   remove(aObj);
 638   freeProxy(aObj);
 639 end;
 640
 641
 642 procedure TBodyGridBase.moveResizeBody (body: TBodyProxyId; dx, dy, sx, sy: Integer);
 643 var
 644   px: PBodyProxyRec;
 645 begin
 646   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 647   if ((dx = 0) and (dy = 0) and (sx = 0) and (sy = 0)) then exit;
 648   remove(body);
 649   px := @mProxies[body];
 650   Inc(px.mX, dx);
 651   Inc(px.mY, dy);
 652   Inc(px.mWidth, sx);
 653   Inc(px.mHeight, sy);
 654   insert(body);
 655 end;
 656
 657 procedure TBodyGridBase.moveBody (body: TBodyProxyId; dx, dy: Integer);
 658 begin
 659   moveResizeBody(body, dx, dy, 0, 0);
 660 end;
 661
 662 procedure TBodyGridBase.resizeBody (body: TBodyProxyId; sx, sy: Integer);
 663 begin
 664   moveResizeBody(body, 0, 0, sx, sy);
 665 end;
 666
 667
 668 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
 669 var
 670   idx: Integer;
 671   gx, gy: Integer;
 672   curci: Integer;
 673   f: Integer;
 674   cc: PGridCell = nil;
 675   px: PBodyProxyRec;
 676   lq: LongWord;
 677   tsize, gw: Integer;
 678   x0, y0: Integer;
 679 begin
 680   result := false;
 681   if (w < 1) or (h < 1) or not assigned(cb) then exit;
 682
 683   x0 := x;
 684   y0 := y;
 685
 686   // fix coords
 687   Dec(x, mMinX);
 688   Dec(y, mMinY);
 689
 690   gw := mWidth;
 691   tsize := mTileSize;
 692
 693   if (x+w <= 0) or (y+h <= 0) then exit;
 694   if (x >= gw*tsize) or (y >= mHeight*tsize) then exit;
 695
 696   // increase query counter
 697   Inc(mLastQuery);
 698   if (mLastQuery = 0) then
 699   begin
 700     // just in case of overflow
 701     mLastQuery := 1;
 702     for idx := 0 to High(mProxies) do mProxies[idx].mQueryMark := 0;
 703   end;
 704   //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
 705   lq := mLastQuery;
 706
 707   // go on
 708   for gy := y div tsize to (y+h-1) div tsize do
 709   begin
 710     if (gy < 0) then continue;
 711     if (gy >= mHeight) then break;
 712     for gx := x div tsize to (x+w-1) div tsize do
 713     begin
 714       if (gx < 0) then continue;
 715       if (gx >= gw) then break;
 716       // process cells
 717       curci := mGrid[gy*gw+gx];
 718       while (curci <> -1) do
 719       begin
 720         cc := @mCells[curci];
 721         for f := 0 to High(TGridCell.bodies) do
 722         begin
 723           if (cc.bodies[f] = -1) then break;
 724           px := @mProxies[cc.bodies[f]];
 725           if (px.mQueryMark <> lq) and ((px.mTag and tagmask) <> 0) then
 726           begin
 727             if (x0 >= px.mX+px.mWidth) or (y0 >= px.mY+px.mHeight) then continue;
 728             if (x0+w <= px.mX) or (y0+h <= px.mY) then continue;
 729             px.mQueryMark := lq;
 730             result := cb(px.mObj, px.mTag);
 731             if result then exit;
 732           end;
 733         end;
 734         curci := cc.next;
 735       end;
 736     end;
 737   end;
 738 end;
 739
 740
 741 end.