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     mQueryInProcess: Boolean;
  82
  83   private
  84     function allocCell: Integer;
  85     procedure freeCell (idx: Integer); // `next` is simply overwritten
  86
  87     function allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
  88     procedure freeProxy (body: TBodyProxyId);
  89
  90     procedure insert (body: TBodyProxyId);
  91     procedure remove (body: TBodyProxyId);
  92
  93     function forGridRect (x, y, w, h: Integer; cb: TGridInternalCB): Boolean;
  94
  95     function inserter (grida: Integer): Boolean;
  96     function remover (grida: Integer): Boolean;
  97     function iterator (grida: Integer): Boolean;
  98
  99   public
 100     constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
 101     destructor Destroy (); override;
 102
 103     function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
 104     procedure removeBody (aObj: TBodyProxyId); // WARNING! this WILL destroy proxy!
 105
 106     procedure moveBody (body: TBodyProxyId; dx, dy: Integer);
 107     procedure resizeBody (body: TBodyProxyId; sx, sy: Integer);
 108     procedure moveResizeBody (body: TBodyProxyId; dx, dy, sx, sy: Integer);
 109
 110     //WARNING: can't do recursive queries
 111     function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
 112
 113     //WARNING: can't do recursive queries
 114     // cb with `(nil)` will be called before processing new tile
 115     function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean; overload;
 116
 117     procedure dumpStats ();
 118   end;
 119
 120
 121 implementation
 122
 123 uses
 124   SysUtils, e_log;
 125
 126
 127 // ////////////////////////////////////////////////////////////////////////// //
 128 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
 129 begin
 130   mX := aX;
 131   mY := aY;
 132   mWidth := aWidth;
 133   mHeight := aHeight;
 134   mQueryMark := 0;
 135   mObj := aObj;
 136   mTag := aTag;
 137   nextLink := -1;
 138 end;
 139
 140
 141 // ////////////////////////////////////////////////////////////////////////// //
 142 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
 143 var
 144   idx: Integer;
 145 begin
 146   if aTileSize < 1 then aTileSize := 1;
 147   if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
 148   if aPixWidth < aTileSize then aPixWidth := aTileSize;
 149   if aPixHeight < aTileSize then aPixHeight := aTileSize;
 150   mTileSize := aTileSize;
 151   mMinX := aMinPixX;
 152   mMinY := aMinPixY;
 153   mWidth := (aPixWidth+aTileSize-1) div aTileSize;
 154   mHeight := (aPixHeight+aTileSize-1) div aTileSize;
 155   SetLength(mGrid, mWidth*mHeight);
 156   SetLength(mCells, mWidth*mHeight);
 157   SetLength(mProxies, 8192);
 158   mFreeCell := 0;
 159   // init free list
 160   for idx := 0 to High(mCells) do
 161   begin
 162     {$IFDEF grid_use_buckets}
 163     mCells[idx].bodies[0] := -1;
 164     {$ELSE}
 165     mCells[idx].body := -1;
 166     {$ENDIF}
 167     mCells[idx].next := idx+1;
 168   end;
 169   mCells[High(mCells)].next := -1; // last cell
 170   // init grid
 171   for idx := 0 to High(mGrid) do mGrid[idx] := -1;
 172   // init proxies
 173   for idx := 0 to High(mProxies) do mProxies[idx].nextLink := idx+1;
 174   mProxies[High(mProxies)].nextLink := -1;
 175   mLastQuery := 0;
 176   mUsedCells := 0;
 177   mProxyFree := 0;
 178   mProxyCount := 0;
 179   mProxyMaxCount := 0;
 180   mUData := 0;
 181   mTagMask := -1;
 182   mItCB := nil;
 183   mQueryInProcess := false;
 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       if (cb(gy*mWidth+gx)) then begin result := true; exit; end;
 317     end;
 318   end;
 319 end;
 320
 321
 322 // ////////////////////////////////////////////////////////////////////////// //
 323 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean;
 324 var
 325   i: Integer;
 326   dx, dy: Integer;
 327   xerr, yerr, d: LongWord;
 328   incx, incy: Integer;
 329   x, y: Integer;
 330   maxx, maxy: Integer;
 331   tsize: Integer; // tile size
 332   gw, gh: Integer;
 333   lastGA: Integer = -1;
 334   ga: Integer = -1; // last used grid address
 335   ccidx: Integer = -1;
 336   curci: Integer = -1;
 337   cc: PGridCell = nil;
 338   hasUntried: Boolean;
 339   f: Integer;
 340   px: PBodyProxyRec;
 341   lq: LongWord;
 342   prevX, prevY: Integer;
 343   minx, miny: Integer;
 344 begin
 345   result := False;
 346
 347   if (tagmask = 0) then exit;
 348
 349   // make coords (0,0)-based
 350   minx := mMinX;
 351   miny := mMinY;
 352   Dec(x0, minx);
 353   Dec(y0, miny);
 354   Dec(x1, minx);
 355   Dec(y1, miny);
 356
 357   xerr := 0;
 358   yerr := 0;
 359   dx := x1-x0;
 360   dy := y1-y0;
 361
 362   if (dx > 0) then incx := 1 else if (dx < 0) then incx := -1 else incx := 0;
 363   if (dy > 0) then incy := 1 else if (dy < 0) then incy := -1 else incy := 0;
 364
 365   dx := abs(dx);
 366   dy := abs(dy);
 367
 368   if (dx > dy) then d := dx else d := dy;
 369
 370   x := x0;
 371   y := y0;
 372
 373   // increase query counter
 374   Inc(mLastQuery);
 375   if (mLastQuery = 0) then
 376   begin
 377     // just in case of overflow
 378     mLastQuery := 1;
 379     for i := 0 to High(mProxies) do mProxies[i].mQueryMark := 0;
 380   end;
 381   lq := mLastQuery;
 382
 383   tsize := mTileSize;
 384   gw := mWidth;
 385   gh := mHeight;
 386   maxx := gw*tsize-1;
 387   maxy := gh*tsize-1;
 388
 389   for i := 1 to d do
 390   begin
 391     prevX := x;
 392     prevY := y;
 393     Inc(xerr, dx); if (xerr > d) then begin Dec(xerr, d); Inc(x, incx); end;
 394     Inc(yerr, dy); if (yerr > d) then begin Dec(yerr, d); Inc(y, incy); end;
 395
 396     if (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy) then
 397     begin
 398       ga := (y div tsize)*gw+(x div tsize);
 399       if (lastGA <> ga) then
 400       begin
 401         // new cell
 402         lastGA := ga;
 403         ccidx := mGrid[lastGA];
 404         if (ccidx <> -1) then
 405         begin
 406           result := cb(nil, 0, x+minx, y+miny, prevX+minx, prevY+miny);
 407           if result then exit;
 408         end;
 409       end;
 410     end
 411     else
 412     begin
 413       ccidx := -1;
 414     end;
 415
 416     if (ccidx <> -1) then
 417     begin
 418       curci := ccidx;
 419       hasUntried := false;
 420       while (curci <> -1) do
 421       begin
 422         cc := @mCells[curci];
 423         for f := 0 to High(TGridCell.bodies) do
 424         begin
 425           if (cc.bodies[f] = -1) then break;
 426           px := @mProxies[cc.bodies[f]];
 427           if (px.mQueryMark <> lq) and ((px.mTag and tagmask) <> 0) then
 428           begin
 429             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
 430             begin
 431               px.mQueryMark := lq;
 432               result := cb(px.mObj, px.mTag, x+minx, y+miny, prevX+minx, prevY+miny);
 433               if result then exit;
 434             end
 435             else
 436             begin
 437               hasUntried := true;
 438             end;
 439           end;
 440         end;
 441         curci := cc.next;
 442       end;
 443       if not hasUntried then ccidx := -1; // don't process this cell anymore
 444     end;
 445   end;
 446 end;
 447
 448
 449 function TBodyGridBase.inserter (grida: Integer): Boolean;
 450 var
 451   cidx: Integer;
 452   pc: PInteger;
 453   {$IFDEF grid_use_buckets}
 454   pi: PGridCell;
 455   f: Integer;
 456   {$ENDIF}
 457 begin
 458   result := false; // never stop
 459   // add body to the given grid cell
 460   pc := @mGrid[grida];
 461   {$IFDEF grid_use_buckets}
 462   if (pc^ <> -1) then
 463   begin
 464     pi := @mCells[pc^];
 465     f := 0;
 466     for f := 0 to High(TGridCell.bodies) do
 467     begin
 468       if (pi.bodies[f] = -1) then
 469       begin
 470         // can add here
 471         pi.bodies[f] := mUData;
 472         if (f+1 < Length(TGridCell.bodies)) then pi.bodies[f+1] := -1;
 473         exit;
 474       end;
 475     end;
 476   end;
 477   // either no room, or no cell at all
 478   cidx := allocCell();
 479   mCells[cidx].bodies[0] := mUData;
 480   mCells[cidx].bodies[1] := -1;
 481   mCells[cidx].next := pc^;
 482   pc^ := cidx;
 483   {$ELSE}
 484   cidx := allocCell();
 485   //e_WriteLog(Format('  01: allocated cell for grid coords (%d,%d), body coords:(%d,%d): #%d', [gx, gy, dx, dy, cidx]), MSG_NOTIFY);
 486   mCells[cidx].body := mUData;
 487   mCells[cidx].next := pc^;
 488   pc^ := cidx;
 489   {$ENDIF}
 490 end;
 491
 492
 493 procedure TBodyGridBase.insert (body: TBodyProxyId);
 494 var
 495   px: PBodyProxyRec;
 496 begin
 497   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 498   px := @mProxies[body];
 499   mUData := body;
 500   forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, inserter);
 501 end;
 502
 503
 504 function TBodyGridBase.remover (grida: Integer): Boolean;
 505 var
 506   pidx, idx, tmp, f: Integer;
 507   pc: PGridCell;
 508 begin
 509   result := false; // never stop
 510   // find and remove cell
 511   pidx := -1;
 512   idx := mGrid[grida];
 513   while (idx >= 0) do
 514   begin
 515     tmp := mCells[idx].next;
 516     {$IFDEF grid_use_buckets}
 517     pc := @mCells[idx];
 518     f := 0;
 519     while (f < High(TGridCell.bodies)) do
 520     begin
 521       if (pc.bodies[f] = mUData) then
 522       begin
 523         // i found her!
 524         if (f = 0) and (pc.bodies[1] = -1) then
 525         begin
 526           // this cell contains no elements, remove it
 527           tmp := mCells[idx].next;
 528           if (pidx = -1) then mGrid[grida] := tmp else mCells[pidx].next := tmp;
 529           freeCell(idx);
 530         end
 531         else
 532         begin
 533           // remove element from bucket
 534           Inc(f);
 535           while (f < High(TGridCell.bodies)) do
 536           begin
 537             pc.bodies[f-1] := pc.bodies[f];
 538             if (pc.bodies[f] = -1) then break;
 539             Inc(f);
 540           end;
 541           pc.bodies[High(TGridCell.bodies)] := -1; // just in case
 542         end;
 543         exit; // assume that we cannot have one object added to bucket twice
 544       end;
 545       Inc(f);
 546     end;
 547     {$ELSE}
 548     if (mCells[idx].body = mUData) then
 549     begin
 550       if (pidx = -1) then mGrid[grida] := tmp else mCells[pidx].next := tmp;
 551       freeCell(idx);
 552       exit; // assume that we cannot have one object added to bucket twice
 553     end;
 554     {$ENDIF}
 555     pidx := idx;
 556     idx := tmp;
 557   end;
 558 end;
 559
 560
 561 // absolutely not tested
 562 procedure TBodyGridBase.remove (body: TBodyProxyId);
 563 var
 564   px: PBodyProxyRec;
 565 begin
 566   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 567   px := @mProxies[body];
 568   mUData := body;
 569   forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover);
 570 end;
 571
 572
 573 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
 574 begin
 575   if mQueryInProcess then raise Exception.Create('grid doesn''t support recursive queries');
 576   mQueryInProcess := true;
 577   result := allocProxy(aX, aY, aWidth, aHeight, aObj, aTag);
 578   insert(result);
 579   mQueryInProcess := false;
 580 end;
 581
 582
 583 procedure TBodyGridBase.removeBody (aObj: TBodyProxyId);
 584 begin
 585   if (aObj < 0) or (aObj > High(mProxies)) then exit; // just in case
 586   if mQueryInProcess then raise Exception.Create('grid doesn''t support recursive queries');
 587   mQueryInProcess := true;
 588   remove(aObj);
 589   freeProxy(aObj);
 590   mQueryInProcess := false;
 591 end;
 592
 593
 594 procedure TBodyGridBase.moveResizeBody (body: TBodyProxyId; dx, dy, sx, sy: Integer);
 595 var
 596   px: PBodyProxyRec;
 597 begin
 598   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 599   if ((dx = 0) and (dy = 0) and (sx = 0) and (sy = 0)) then exit;
 600   if mQueryInProcess then raise Exception.Create('grid doesn''t support recursive queries');
 601   mQueryInProcess := true;
 602   remove(body);
 603   px := @mProxies[body];
 604   Inc(px.mX, dx);
 605   Inc(px.mY, dy);
 606   Inc(px.mWidth, sx);
 607   Inc(px.mHeight, sy);
 608   insert(body);
 609   mQueryInProcess := false;
 610 end;
 611
 612 procedure TBodyGridBase.moveBody (body: TBodyProxyId; dx, dy: Integer);
 613 begin
 614   moveResizeBody(body, dx, dy, 0, 0);
 615 end;
 616
 617 procedure TBodyGridBase.resizeBody (body: TBodyProxyId; sx, sy: Integer);
 618 begin
 619   moveResizeBody(body, 0, 0, sx, sy);
 620 end;
 621
 622
 623 function TBodyGridBase.iterator (grida: Integer): Boolean;
 624 var
 625   idx: Integer;
 626   px: PBodyProxyRec;
 627   {$IFDEF grid_use_buckets}
 628   pi: PGridCell;
 629   f: Integer;
 630   {$ENDIF}
 631 begin
 632   result := false;
 633   idx := mGrid[grida];
 634   while (idx >= 0) do
 635   begin
 636     {$IFDEF grid_use_buckets}
 637     pi := @mCells[idx];
 638     for f := 0 to High(TGridCell.bodies) do
 639     begin
 640       if (pi.bodies[f] = -1) then break;
 641       px := @mProxies[pi.bodies[f]];
 642       if (px.mQueryMark <> mLastQuery) and ((mTagMask = -1) or ((px.mTag and mTagMask) <> 0)) then
 643       begin
 644         //e_WriteLog(Format('  query #%d body hit: (%d,%d)-(%dx%d) tag:%d', [mLastQuery, mCells[idx].body.mX, mCells[idx].body.mY, mCells[idx].body.mWidth, mCells[idx].body.mHeight, mCells[idx].body.mTag]), MSG_NOTIFY);
 645         px.mQueryMark := mLastQuery;
 646         if (mItCB(px.mObj, px.mTag)) then begin result := true; exit; end;
 647       end;
 648     end;
 649     idx := pi.next;
 650     {$ELSE}
 651     if (mCells[idx].body <> -1) then
 652     begin
 653       px := @mProxies[mCells[idx].body];
 654       if (px.mQueryMark <> mLastQuery) and ((mTagMask = -1) or ((px.mTag and mTagMask) <> 0)) then
 655       begin
 656         //e_WriteLog(Format('  query #%d body hit: (%d,%d)-(%dx%d) tag:%d', [mLastQuery, mCells[idx].body.mX, mCells[idx].body.mY, mCells[idx].body.mWidth, mCells[idx].body.mHeight, mCells[idx].body.mTag]), MSG_NOTIFY);
 657         px.mQueryMark := mLastQuery;
 658         if (mItCB(px.mObj, px.mTag)) then begin result := true; exit; end;
 659       end;
 660     end;
 661     idx := mCells[idx].next;
 662     {$ENDIF}
 663   end;
 664 end;
 665
 666 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
 667 var
 668   idx: Integer;
 669 begin
 670   result := false;
 671   if not assigned(cb) then exit;
 672
 673   if mQueryInProcess then raise Exception.Create('grid doesn''t support recursive queries');
 674   mQueryInProcess := true;
 675
 676   // increase query counter
 677   Inc(mLastQuery);
 678   if (mLastQuery = 0) then
 679   begin
 680     // just in case of overflow
 681     mLastQuery := 1;
 682     for idx := 0 to High(mProxies) do mProxies[idx].mQueryMark := 0;
 683   end;
 684   //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
 685
 686   mTagMask := tagmask;
 687   mItCB := cb;
 688   result := forGridRect(x, y, w, h, iterator);
 689   mQueryInProcess := false;
 690 end;
 691
 692
 693 end.