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 unit g_grid;
  19
  20 interface
  21
  22
  23 type
  24   TBodyProxyId = Integer;
  25
  26   generic TBodyGridBase<ITP> = class(TObject)
  27   public
  28     type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
  29     type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
  30     type TGridAlongQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
  31
  32     const TagDisabled = $40000000;
  33     const TagFullMask = $3fffffff;
  34
  35   private
  36     const
  37       GridDefaultTileSize = 32;
  38       GridCellBucketSize = 8; // WARNING! can't be less than 2!
  39
  40   private
  41     type
  42       PBodyProxyRec = ^TBodyProxyRec;
  43       TBodyProxyRec = record
  44       private
  45         mX, mY, mWidth, mHeight: Integer; // aabb
  46         mQueryMark: LongWord; // was this object visited at this query?
  47         mObj: ITP;
  48         mTag: Integer; // `TagDisabled` set: disabled ;-)
  49         nextLink: TBodyProxyId; // next free or nothing
  50
  51       private
  52         procedure setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
  53       end;
  54
  55       PGridCell = ^TGridCell;
  56       TGridCell = record
  57         bodies: array [0..GridCellBucketSize-1] of Integer; // -1: end of list
  58         next: Integer; // in this cell; index in mCells
  59       end;
  60
  61       TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
  62
  63   private
  64     //mTileSize: Integer;
  65     const mTileSize = GridDefaultTileSize;
  66
  67   private
  68     mMinX, mMinY: Integer; // so grids can start at any origin
  69     mWidth, mHeight: Integer; // in tiles
  70     mGrid: array of Integer; // mWidth*mHeight, index in mCells
  71     mCells: array of TGridCell; // cell pool
  72     mFreeCell: Integer; // first free cell index or -1
  73     mLastQuery: LongWord;
  74     mUsedCells: Integer;
  75     mProxies: array of TBodyProxyRec;
  76     mProxyFree: TBodyProxyId; // free
  77     mProxyCount: Integer; // currently used
  78     mProxyMaxCount: Integer;
  79
  80   private
  81     function allocCell (): Integer;
  82     procedure freeCell (idx: Integer); // `next` is simply overwritten
  83
  84     function allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
  85     procedure freeProxy (body: TBodyProxyId);
  86
  87     procedure insertInternal (body: TBodyProxyId);
  88     procedure removeInternal (body: TBodyProxyId);
  89
  90     function forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
  91
  92     function inserter (grida: Integer; bodyId: TBodyProxyId): Boolean;
  93     function remover (grida: Integer; bodyId: TBodyProxyId): Boolean;
  94
  95     function getProxyEnabled (pid: TBodyProxyId): Boolean; inline;
  96     procedure setProxyEnabled (pid: TBodyProxyId; val: Boolean); inline;
  97
  98     function getGridWidthPx (): Integer; inline;
  99     function getGridHeightPx (): Integer; inline;
 100
 101   public
 102     constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
 103     destructor Destroy (); override;
 104
 105     function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
 106     procedure removeBody (body: TBodyProxyId); // WARNING! this WILL destroy proxy!
 107
 108     procedure moveBody (body: TBodyProxyId; dx, dy: Integer);
 109     procedure resizeBody (body: TBodyProxyId; sx, sy: Integer);
 110     procedure moveResizeBody (body: TBodyProxyId; dx, dy, sx, sy: Integer);
 111
 112     function insideGrid (x, y: Integer): Boolean; inline;
 113
 114     // `false` if `body` is surely invalid
 115     function getBodyXY (body: TBodyProxyId; out rx, ry: Integer): Boolean; inline;
 116
 117     //WARNING: don't modify grid while any query is in progress (no checks are made!)
 118     //         you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
 119     // no callback: return `true` on the first hit
 120     function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
 121
 122     //WARNING: don't modify grid while any query is in progress (no checks are made!)
 123     //         you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
 124     // no callback: return `true` on the first hit
 125     function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
 126
 127     //WARNING: don't modify grid while any query is in progress (no checks are made!)
 128     //         you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
 129     // cb with `(nil)` will be called before processing new tile
 130     // no callback: return `true` on the nearest hit
 131     function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
 132     function traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
 133
 134     //WARNING: don't modify grid while any query is in progress (no checks are made!)
 135     //         you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
 136     // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
 137     function forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
 138
 139     procedure dumpStats ();
 140
 141     //WARNING! no sanity checks!
 142     property proxyEnabled[pid: TBodyProxyId]: Boolean read getProxyEnabled write setProxyEnabled;
 143
 144     property gridX0: Integer read mMinX;
 145     property gridY0: Integer read mMinY;
 146     property gridWidth: Integer read getGridWidthPx; // in pixels
 147     property gridHeight: Integer read getGridHeightPx; // in pixels
 148   end;
 149
 150
 151 // you are not supposed to understand this
 152 // returns `true` if there is an intersection, and enter coords
 153 // enter coords will be equal to (x0, y0) if starting point is inside the box
 154 // if result is `false`, `inx` and `iny` are undefined
 155 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
 156
 157
 158 procedure swapInt (var a: Integer; var b: Integer); inline;
 159 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline;
 160
 161
 162 implementation
 163
 164 uses
 165   SysUtils, e_log;
 166
 167
 168 // ////////////////////////////////////////////////////////////////////////// //
 169 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
 170
 171 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
 172
 173
 174 // ////////////////////////////////////////////////////////////////////////// //
 175 // you are not supposed to understand this
 176 // returns `true` if there is an intersection, and enter coords
 177 // enter coords will be equal to (x0, y0) if starting point is inside the box
 178 // if result is `false`, `inx` and `iny` are undefined
 179 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
 180 var
 181   wx0, wy0, wx1, wy1: Integer; // window coordinates
 182   stx, sty: Integer; // "steps" for x and y axes
 183   dsx, dsy: Integer; // "lengthes" for x and y axes
 184   dx2, dy2: Integer; // "double lengthes" for x and y axes
 185   xd, yd: Integer; // current coord
 186   e: Integer; // "error" (as in bresenham algo)
 187   rem: Integer;
 188   term: Integer;
 189   d0, d1: PInteger;
 190   xfixed: Boolean;
 191   temp: Integer;
 192 begin
 193   result := false;
 194   // why not
 195   inx := x0;
 196   iny := y0;
 197   if (bw < 1) or (bh < 1) then exit; // impossible box
 198
 199   if (x0 = x1) and (y0 = y1) then
 200   begin
 201     // check this point
 202     result := (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh);
 203     exit;
 204   end;
 205
 206   // check if staring point is inside the box
 207   if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
 208
 209   // clip rectange
 210   wx0 := bx;
 211   wy0 := by;
 212   wx1 := bx+bw-1;
 213   wy1 := by+bh-1;
 214
 215   // horizontal setup
 216   if (x0 < x1) then
 217   begin
 218     // from left to right
 219     if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
 220     stx := 1; // going right
 221   end
 222   else
 223   begin
 224     // from right to left
 225     if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
 226     stx := -1; // going left
 227     x0 := -x0;
 228     x1 := -x1;
 229     wx0 := -wx0;
 230     wx1 := -wx1;
 231     swapInt(wx0, wx1);
 232   end;
 233
 234   // vertical setup
 235   if (y0 < y1) then
 236   begin
 237     // from top to bottom
 238     if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
 239     sty := 1; // going down
 240   end
 241   else
 242   begin
 243     // from bottom to top
 244     if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
 245     sty := -1; // going up
 246     y0 := -y0;
 247     y1 := -y1;
 248     wy0 := -wy0;
 249     wy1 := -wy1;
 250     swapInt(wy0, wy1);
 251   end;
 252
 253   dsx := x1-x0;
 254   dsy := y1-y0;
 255
 256   if (dsx < dsy) then
 257   begin
 258     d0 := @yd;
 259     d1 := @xd;
 260     swapInt(x0, y0);
 261     swapInt(x1, y1);
 262     swapInt(dsx, dsy);
 263     swapInt(wx0, wy0);
 264     swapInt(wx1, wy1);
 265     swapInt(stx, sty);
 266   end
 267   else
 268   begin
 269     d0 := @xd;
 270     d1 := @yd;
 271   end;
 272
 273   dx2 := 2*dsx;
 274   dy2 := 2*dsy;
 275   xd := x0;
 276   yd := y0;
 277   e := 2*dsy-dsx;
 278   term := x1;
 279
 280   xfixed := false;
 281   if (y0 < wy0) then
 282   begin
 283     // clip at top
 284     temp := dx2*(wy0-y0)-dsx;
 285     xd += temp div dy2;
 286     rem := temp mod dy2;
 287     if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
 288     if (xd+1 >= wx0) then
 289     begin
 290       yd := wy0;
 291       e -= rem+dsx;
 292       if (rem > 0) then begin Inc(xd); e += dy2; end;
 293       xfixed := true;
 294     end;
 295   end;
 296
 297   if (not xfixed) and (x0 < wx0) then
 298   begin
 299     // clip at left
 300     temp := dy2*(wx0-x0);
 301     yd += temp div dx2;
 302     rem := temp mod dx2;
 303     if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
 304     xd := wx0;
 305     e += rem;
 306     if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
 307   end;
 308
 309   if (y1 > wy1) then
 310   begin
 311     // clip at bottom
 312     temp := dx2*(wy1-y0)+dsx;
 313     term := x0+temp div dy2;
 314     rem := temp mod dy2;
 315     if (rem = 0) then Dec(term);
 316   end;
 317
 318   if (term > wx1) then term := wx1; // clip at right
 319
 320   Inc(term); // draw last point
 321   //if (term = xd) then exit; // this is the only point, get out of here
 322
 323   if (sty = -1) then yd := -yd;
 324   if (stx = -1) then begin xd := -xd; term := -term; end;
 325   dx2 -= dy2;
 326
 327   inx := d0^;
 328   iny := d1^;
 329   result := true;
 330 end;
 331
 332
 333 // ////////////////////////////////////////////////////////////////////////// //
 334 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
 335 begin
 336   mX := aX;
 337   mY := aY;
 338   mWidth := aWidth;
 339   mHeight := aHeight;
 340   mQueryMark := 0;
 341   mObj := aObj;
 342   mTag := aTag;
 343   nextLink := -1;
 344 end;
 345
 346
 347 // ////////////////////////////////////////////////////////////////////////// //
 348 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
 349 var
 350   idx: Integer;
 351 begin
 352   {
 353   if aTileSize < 1 then aTileSize := 1;
 354   if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
 355   mTileSize := aTileSize;
 356   }
 357   if (aPixWidth < mTileSize) then aPixWidth := mTileSize;
 358   if (aPixHeight < mTileSize) then aPixHeight := mTileSize;
 359   mMinX := aMinPixX;
 360   mMinY := aMinPixY;
 361   mWidth := (aPixWidth+mTileSize-1) div mTileSize;
 362   mHeight := (aPixHeight+mTileSize-1) div mTileSize;
 363   SetLength(mGrid, mWidth*mHeight);
 364   SetLength(mCells, mWidth*mHeight);
 365   SetLength(mProxies, 8192);
 366   mFreeCell := 0;
 367   // init free list
 368   for idx := 0 to High(mCells) do
 369   begin
 370     mCells[idx].bodies[0] := -1;
 371     mCells[idx].next := idx+1;
 372   end;
 373   mCells[High(mCells)].next := -1; // last cell
 374   // init grid
 375   for idx := 0 to High(mGrid) do mGrid[idx] := -1;
 376   // init proxies
 377   for idx := 0 to High(mProxies) do mProxies[idx].nextLink := idx+1;
 378   mProxies[High(mProxies)].nextLink := -1;
 379   mLastQuery := 0;
 380   mUsedCells := 0;
 381   mProxyFree := 0;
 382   mProxyCount := 0;
 383   mProxyMaxCount := 0;
 384   e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
 385 end;
 386
 387
 388 destructor TBodyGridBase.Destroy ();
 389 begin
 390   mCells := nil;
 391   mGrid := nil;
 392   mProxies := nil;
 393   inherited;
 394 end;
 395
 396
 397 // ////////////////////////////////////////////////////////////////////////// //
 398 procedure TBodyGridBase.dumpStats ();
 399 var
 400   idx, mcb, cidx, cnt: Integer;
 401 begin
 402   mcb := 0;
 403   for idx := 0 to High(mGrid) do
 404   begin
 405     cidx := mGrid[idx];
 406     cnt := 0;
 407     while cidx >= 0 do
 408     begin
 409       Inc(cnt);
 410       cidx := mCells[cidx].next;
 411     end;
 412     if (mcb < cnt) then mcb := cnt;
 413   end;
 414   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);
 415 end;
 416
 417
 418 // ////////////////////////////////////////////////////////////////////////// //
 419 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
 420 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
 421
 422
 423 function TBodyGridBase.insideGrid (x, y: Integer): Boolean; inline;
 424 begin
 425   // fix coords
 426   Dec(x, mMinX);
 427   Dec(y, mMinY);
 428   result := (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize);
 429 end;
 430
 431
 432 function TBodyGridBase.getBodyXY (body: TBodyProxyId; out rx, ry: Integer): Boolean; inline;
 433 begin
 434   if (body >= 0) and (body < Length(mProxies)) then
 435   begin
 436     with mProxies[body] do begin rx := mX; ry := mY; end;
 437     result := true;
 438   end
 439   else
 440   begin
 441     rx := 0;
 442     ry := 0;
 443     result := false;
 444   end;
 445 end;
 446
 447
 448 // ////////////////////////////////////////////////////////////////////////// //
 449 function TBodyGridBase.getProxyEnabled (pid: TBodyProxyId): Boolean; inline;
 450 begin
 451   if (pid >= 0) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
 452 end;
 453
 454
 455 procedure TBodyGridBase.setProxyEnabled (pid: TBodyProxyId; val: Boolean); inline;
 456 begin
 457   if (pid >= 0) then
 458   begin
 459     if val then
 460     begin
 461       mProxies[pid].mTag := mProxies[pid].mTag and not TagDisabled;
 462     end
 463     else
 464     begin
 465       mProxies[pid].mTag := mProxies[pid].mTag or TagDisabled;
 466     end;
 467   end;
 468 end;
 469
 470
 471 // ////////////////////////////////////////////////////////////////////////// //
 472 function TBodyGridBase.allocCell (): Integer;
 473 var
 474   idx: Integer;
 475 begin
 476   if (mFreeCell < 0) then
 477   begin
 478     // no free cells, want more
 479     mFreeCell := Length(mCells);
 480     SetLength(mCells, mFreeCell+32768); // arbitrary number
 481     for idx := mFreeCell to High(mCells) do
 482     begin
 483       mCells[idx].bodies[0] := -1;
 484       mCells[idx].next := idx+1;
 485     end;
 486     mCells[High(mCells)].next := -1; // last cell
 487   end;
 488   result := mFreeCell;
 489   mFreeCell := mCells[result].next;
 490   mCells[result].next := -1;
 491   mCells[result].bodies[0] := -1;
 492   Inc(mUsedCells);
 493   //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
 494 end;
 495
 496
 497 procedure TBodyGridBase.freeCell (idx: Integer);
 498 begin
 499   if (idx >= 0) and (idx < Length(mCells)) then
 500   begin
 501     //if mCells[idx].body = -1 then exit; // the thing that should not be
 502     mCells[idx].bodies[0] := -1;
 503     mCells[idx].next := mFreeCell;
 504     mFreeCell := idx;
 505     Dec(mUsedCells);
 506   end;
 507 end;
 508
 509
 510 // ////////////////////////////////////////////////////////////////////////// //
 511 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
 512 var
 513   olen, idx: Integer;
 514   px: PBodyProxyRec;
 515 begin
 516   if (mProxyFree = -1) then
 517   begin
 518     // no free proxies, resize list
 519     olen := Length(mProxies);
 520     SetLength(mProxies, olen+8192); // arbitrary number
 521     for idx := olen to High(mProxies) do mProxies[idx].nextLink := idx+1;
 522     mProxies[High(mProxies)].nextLink := -1;
 523     mProxyFree := olen;
 524   end;
 525   // get one from list
 526   result := mProxyFree;
 527   px := @mProxies[result];
 528   mProxyFree := px.nextLink;
 529   px.setup(aX, aY, aWidth, aHeight, aObj, aTag);
 530   // add to used list
 531   px.nextLink := -1;
 532   // statistics
 533   Inc(mProxyCount);
 534   if (mProxyMaxCount < mProxyCount) then mProxyMaxCount := mProxyCount;
 535 end;
 536
 537 procedure TBodyGridBase.freeProxy (body: TBodyProxyId);
 538 begin
 539   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 540   if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
 541   // add to free list
 542   mProxies[body].mObj := nil;
 543   mProxies[body].nextLink := mProxyFree;
 544   mProxyFree := body;
 545   Dec(mProxyCount);
 546 end;
 547
 548
 549 // ////////////////////////////////////////////////////////////////////////// //
 550 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
 551 const
 552   tsize = mTileSize;
 553 var
 554   gx, gy: Integer;
 555   gw, gh: Integer;
 556 begin
 557   result := false;
 558   if (w < 1) or (h < 1) or not assigned(cb) then exit;
 559   // fix coords
 560   Dec(x, mMinX);
 561   Dec(y, mMinY);
 562   // go on
 563   if (x+w <= 0) or (y+h <= 0) then exit;
 564   gw := mWidth;
 565   gh := mHeight;
 566   //tsize := mTileSize;
 567   if (x >= gw*tsize) or (y >= gh*tsize) then exit;
 568   for gy := y div tsize to (y+h-1) div tsize do
 569   begin
 570     if (gy < 0) then continue;
 571     if (gy >= gh) then break;
 572     for gx := x div tsize to (x+w-1) div tsize do
 573     begin
 574       if (gx < 0) then continue;
 575       if (gx >= gw) then break;
 576       result := cb(gy*gw+gx, bodyId);
 577       if result then exit;
 578     end;
 579   end;
 580 end;
 581
 582
 583 // ////////////////////////////////////////////////////////////////////////// //
 584 function TBodyGridBase.inserter (grida: Integer; bodyId: TBodyProxyId): Boolean;
 585 var
 586   cidx: Integer;
 587   pc: Integer;
 588   pi: PGridCell;
 589   f: Integer;
 590 begin
 591   result := false; // never stop
 592   // add body to the given grid cell
 593   pc := mGrid[grida];
 594   if (pc <> -1) then
 595   begin
 596     pi := @mCells[pc];
 597     f := 0;
 598     for f := 0 to High(TGridCell.bodies) do
 599     begin
 600       if (pi.bodies[f] = -1) then
 601       begin
 602         // can add here
 603         pi.bodies[f] := bodyId;
 604         if (f+1 < Length(TGridCell.bodies)) then pi.bodies[f+1] := -1;
 605         exit;
 606       end;
 607     end;
 608   end;
 609   // either no room, or no cell at all
 610   cidx := allocCell();
 611   mCells[cidx].bodies[0] := bodyId;
 612   mCells[cidx].bodies[1] := -1;
 613   mCells[cidx].next := pc;
 614   mGrid[grida] := cidx;
 615 end;
 616
 617 procedure TBodyGridBase.insertInternal (body: TBodyProxyId);
 618 var
 619   px: PBodyProxyRec;
 620 begin
 621   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 622   px := @mProxies[body];
 623   forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, inserter, body);
 624 end;
 625
 626
 627 // absolutely not tested
 628 function TBodyGridBase.remover (grida: Integer; bodyId: TBodyProxyId): Boolean;
 629 var
 630   f: Integer;
 631   pidx, idx, tmp: Integer;
 632   pc: PGridCell;
 633 begin
 634   result := false; // never stop
 635   // find and remove cell
 636   pidx := -1;
 637   idx := mGrid[grida];
 638   while (idx >= 0) do
 639   begin
 640     tmp := mCells[idx].next;
 641     pc := @mCells[idx];
 642     f := 0;
 643     while (f < High(TGridCell.bodies)) do
 644     begin
 645       if (pc.bodies[f] = bodyId) then
 646       begin
 647         // i found her!
 648         if (f = 0) and (pc.bodies[1] = -1) then
 649         begin
 650           // this cell contains no elements, remove it
 651           tmp := mCells[idx].next;
 652           if (pidx = -1) then mGrid[grida] := tmp else mCells[pidx].next := tmp;
 653           freeCell(idx);
 654         end
 655         else
 656         begin
 657           // remove element from bucket
 658           Inc(f);
 659           while (f < High(TGridCell.bodies)) do
 660           begin
 661             pc.bodies[f-1] := pc.bodies[f];
 662             if (pc.bodies[f] = -1) then break;
 663             Inc(f);
 664           end;
 665           pc.bodies[High(TGridCell.bodies)] := -1; // just in case
 666         end;
 667         exit; // assume that we cannot have one object added to bucket twice
 668       end;
 669       Inc(f);
 670     end;
 671     pidx := idx;
 672     idx := tmp;
 673   end;
 674 end;
 675
 676 // absolutely not tested
 677 procedure TBodyGridBase.removeInternal (body: TBodyProxyId);
 678 var
 679   px: PBodyProxyRec;
 680 begin
 681   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 682   px := @mProxies[body];
 683   forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover, body);
 684 end;
 685
 686
 687 // ////////////////////////////////////////////////////////////////////////// //
 688 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
 689 begin
 690   aTag := aTag and TagFullMask;
 691   result := allocProxy(aX, aY, aWidth, aHeight, aObj, aTag);
 692   insertInternal(result);
 693 end;
 694
 695
 696 procedure TBodyGridBase.removeBody (body: TBodyProxyId);
 697 begin
 698   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 699   removeInternal(body);
 700   freeProxy(body);
 701 end;
 702
 703
 704 // ////////////////////////////////////////////////////////////////////////// //
 705 procedure TBodyGridBase.moveResizeBody (body: TBodyProxyId; dx, dy, sx, sy: Integer);
 706 var
 707   px: PBodyProxyRec;
 708   x0, y0, w, h: Integer;
 709 begin
 710   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 711   if (dx = 0) and (dy = 0) and (sx = 0) and (sy = 0) then exit;
 712   px := @mProxies[body];
 713   x0 := px.mX;
 714   y0 := px.mY;
 715   w := px.mWidth;
 716   h := px.mHeight;
 717   // did any corner crossed tile boundary?
 718   if (x0 div mTileSize <> (x0+dx) div mTileSize) or
 719      (y0 div mTileSize <> (y0+dx) div mTileSize) or
 720      ((x0+w) div mTileSize <> (x0+w+sx) div mTileSize) or
 721      ((y0+h) div mTileSize <> (y0+h+sy) div mTileSize) then
 722   begin
 723     removeInternal(body);
 724     Inc(px.mX, dx);
 725     Inc(px.mY, dy);
 726     Inc(px.mWidth, sx);
 727     Inc(px.mHeight, sy);
 728     insertInternal(body);
 729   end
 730   else
 731   begin
 732     Inc(px.mX, dx);
 733     Inc(px.mY, dy);
 734     Inc(px.mWidth, sx);
 735     Inc(px.mHeight, sy);
 736   end;
 737 end;
 738
 739 procedure TBodyGridBase.moveBody (body: TBodyProxyId; dx, dy: Integer);
 740 var
 741   px: PBodyProxyRec;
 742   nx, ny: Integer;
 743 begin
 744   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 745   if (dx = 0) and (dy = 0) then exit;
 746   // check if tile coords was changed
 747   px := @mProxies[body];
 748   nx := px.mX+dx;
 749   ny := px.mY+dy;
 750   if (nx div mTileSize <> px.mX div mTileSize) or (ny div mTileSize <> px.mY div mTileSize) then
 751   begin
 752     // crossed tile boundary, do heavy work
 753     moveResizeBody(body, dx, dy, 0, 0);
 754   end
 755   else
 756   begin
 757     // nothing to do with the grid, just fix coordinates
 758     px.mX := nx;
 759     px.mY := ny;
 760   end;
 761 end;
 762
 763 procedure TBodyGridBase.resizeBody (body: TBodyProxyId; sx, sy: Integer);
 764 var
 765   px: PBodyProxyRec;
 766   x0, y0: Integer;
 767   nw, nh: Integer;
 768 begin
 769   if (body < 0) or (body > High(mProxies)) then exit; // just in case
 770   if (sx = 0) and (sy = 0) then exit;
 771   // check if tile coords was changed
 772   px := @mProxies[body];
 773   x0 := px.mX;
 774   y0 := px.mY;
 775   nw := px.mWidth+sx;
 776   nh := px.mHeight+sy;
 777   if ((x0+px.mWidth) div mTileSize <> (x0+nw) div mTileSize) or
 778      ((y0+px.mHeight) div mTileSize <> (y0+nh) div mTileSize) then
 779   begin
 780     // crossed tile boundary, do heavy work
 781     moveResizeBody(body, 0, 0, sx, sy);
 782   end
 783   else
 784   begin
 785     // nothing to do with the grid, just fix size
 786     px.mWidth := nw;
 787     px.mHeight := nh;
 788   end;
 789 end;
 790
 791
 792 // ////////////////////////////////////////////////////////////////////////// //
 793 // no callback: return `true` on the first hit
 794 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
 795 var
 796   f: Integer;
 797   idx, curci: Integer;
 798   cc: PGridCell = nil;
 799   px: PBodyProxyRec;
 800   lq: LongWord;
 801   ptag: Integer;
 802 begin
 803   result := Default(ITP);
 804   tagmask := tagmask and TagFullMask;
 805   if (tagmask = 0) then exit;
 806
 807   // make coords (0,0)-based
 808   Dec(x, mMinX);
 809   Dec(y, mMinY);
 810   if (x < 0) or (y < 0) or (x >= mWidth*mTileSize) or (y >= mHeight*mTileSize) then exit;
 811
 812   curci := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
 813   // restore coords
 814   Inc(x, mMinX);
 815   Inc(y, mMinY);
 816
 817   // increase query counter
 818   Inc(mLastQuery);
 819   if (mLastQuery = 0) then
 820   begin
 821     // just in case of overflow
 822     mLastQuery := 1;
 823     for idx := 0 to High(mProxies) do mProxies[idx].mQueryMark := 0;
 824   end;
 825   lq := mLastQuery;
 826
 827   while (curci <> -1) do
 828   begin
 829     cc := @mCells[curci];
 830     for f := 0 to High(TGridCell.bodies) do
 831     begin
 832       if (cc.bodies[f] = -1) then break;
 833       px := @mProxies[cc.bodies[f]];
 834       ptag := px.mTag;
 835       if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
 836       begin
 837         if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
 838         begin
 839           px.mQueryMark := lq;
 840           if assigned(cb) then
 841           begin
 842             if cb(px.mObj, ptag) then begin result := px.mObj; exit; end;
 843           end
 844           else
 845           begin
 846             result := px.mObj;
 847             exit;
 848           end;
 849         end;
 850       end;
 851     end;
 852     curci := cc.next;
 853   end;
 854 end;
 855
 856
 857 // ////////////////////////////////////////////////////////////////////////// //
 858 // no callback: return `true` on the first hit
 859 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
 860 const
 861   tsize = mTileSize;
 862 var
 863   idx: Integer;
 864   gx, gy: Integer;
 865   curci: Integer;
 866   f: Integer;
 867   cc: PGridCell = nil;
 868   px: PBodyProxyRec;
 869   lq: LongWord;
 870   gw: Integer;
 871   x0, y0: Integer;
 872   ptag: Integer;
 873 begin
 874   result := Default(ITP);
 875   if (w < 1) or (h < 1) then exit;
 876   tagmask := tagmask and TagFullMask;
 877   if (tagmask = 0) then exit;
 878
 879   x0 := x;
 880   y0 := y;
 881
 882   // fix coords
 883   Dec(x, mMinX);
 884   Dec(y, mMinY);
 885
 886   gw := mWidth;
 887   //tsize := mTileSize;
 888
 889   if (x+w <= 0) or (y+h <= 0) then exit;
 890   if (x >= gw*tsize) or (y >= mHeight*tsize) then exit;
 891
 892   // increase query counter
 893   Inc(mLastQuery);
 894   if (mLastQuery = 0) then
 895   begin
 896     // just in case of overflow
 897     mLastQuery := 1;
 898     for idx := 0 to High(mProxies) do mProxies[idx].mQueryMark := 0;
 899   end;
 900   //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
 901   lq := mLastQuery;
 902
 903   // go on
 904   for gy := y div tsize to (y+h-1) div tsize do
 905   begin
 906     if (gy < 0) then continue;
 907     if (gy >= mHeight) then break;
 908     for gx := x div tsize to (x+w-1) div tsize do
 909     begin
 910       if (gx < 0) then continue;
 911       if (gx >= gw) then break;
 912       // process cells
 913       curci := mGrid[gy*gw+gx];
 914       while (curci <> -1) do
 915       begin
 916         cc := @mCells[curci];
 917         for f := 0 to High(TGridCell.bodies) do
 918         begin
 919           if (cc.bodies[f] = -1) then break;
 920           px := @mProxies[cc.bodies[f]];
 921           ptag := px.mTag;
 922           if (not allowDisabled) and ((ptag and TagDisabled) <> 0) then continue;
 923           if ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
 924           //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
 925           //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
 926           begin
 927             if (x0 >= px.mX+px.mWidth) or (y0 >= px.mY+px.mHeight) then continue;
 928             if (x0+w <= px.mX) or (y0+h <= px.mY) then continue;
 929             px.mQueryMark := lq;
 930             if assigned(cb) then
 931             begin
 932               if cb(px.mObj, ptag) then begin result := px.mObj; exit; end;
 933             end
 934             else
 935             begin
 936               result := px.mObj;
 937               exit;
 938             end;
 939           end;
 940         end;
 941         curci := cc.next;
 942       end;
 943     end;
 944   end;
 945 end;
 946
 947
 948 // ////////////////////////////////////////////////////////////////////////// //
 949 // no callback: return `true` on the nearest hit
 950 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
 951 var
 952   ex, ey: Integer;
 953 begin
 954   result := traceRay(ex, ey, x0, y0, x1, y1, cb, tagmask);
 955 end;
 956
 957
 958 // no callback: return `true` on the nearest hit
 959 function TBodyGridBase.traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
 960 const
 961   tsize = mTileSize;
 962 var
 963   i: Integer;
 964   dx, dy, d: Integer;
 965   xerr, yerr: Integer;
 966   incx, incy: Integer;
 967   stepx, stepy: Integer;
 968   x, y: Integer;
 969   maxx, maxy: Integer;
 970   gw, gh: Integer;
 971   ccidx: Integer;
 972   curci: Integer;
 973   cc: PGridCell;
 974   hasUntried: Boolean;
 975   px: PBodyProxyRec;
 976   lq: LongWord;
 977   prevX, prevY: Integer;
 978   minx, miny: Integer;
 979   ptag: Integer;
 980   lastDistSq, distSq: Integer;
 981   wasHit: Boolean = false;
 982   lastObj: ITP;
 983   lastWasInGrid: Boolean;
 984   tbcross: Boolean;
 985   f: Integer;
 986 begin
 987   result := Default(ITP);
 988   lastObj := Default(ITP);
 989   tagmask := tagmask and TagFullMask;
 990   if (tagmask = 0) then begin ex := x0; ey := y0; exit; end;
 991
 992   minx := mMinX;
 993   miny := mMinY;
 994
 995   dx := x1-x0;
 996   dy := y1-y0;
 997
 998   if (dx > 0) then incx := 1 else if (dx < 0) then incx := -1 else incx := 0;
 999   if (dy > 0) then incy := 1 else if (dy < 0) then incy := -1 else incy := 0;
1000
1001   dx := abs(dx);
1002   dy := abs(dy);
1003
1004   if (dx > dy) then d := dx else d := dy;
1005
1006   // `x` and `y` will be in grid coords
1007   x := x0-minx;
1008   y := y0-miny;
1009
1010   // increase query counter
1011   Inc(mLastQuery);
1012   if (mLastQuery = 0) then
1013   begin
1014     // just in case of overflow
1015     mLastQuery := 1;
1016     for i := 0 to High(mProxies) do mProxies[i].mQueryMark := 0;
1017   end;
1018   lq := mLastQuery;
1019
1020   // cache various things
1021   //tsize := mTileSize;
1022   gw := mWidth;
1023   gh := mHeight;
1024   maxx := gw*tsize-1;
1025   maxy := gh*tsize-1;
1026
1027   // setup distance and flags
1028   lastDistSq := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)+1;
1029   lastWasInGrid := (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy);
1030
1031   // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1032   if lastWasInGrid then ccidx := mGrid[(y div tsize)*gw+(x div tsize)] else ccidx := -1;
1033
1034   // it is slightly faster this way
1035   xerr := -d;
1036   yerr := -d;
1037
1038   // now trace
1039   for i := 1 to d do
1040   begin
1041     // prevs are always in map coords
1042     prevX := x+minx;
1043     prevY := y+miny;
1044     // do one step
1045     xerr += dx;
1046     yerr += dy;
1047     // invariant: one of those always changed
1048     if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1049     if (xerr >= 0) then begin xerr -= d; x += incx; stepx := incx; end else stepx := 0;
1050     if (yerr >= 0) then begin yerr -= d; y += incy; stepy := incy; end else stepy := 0;
1051     // invariant: we always doing a step
1052     if ((stepx or stepy) = 0) then raise Exception.Create('internal bug in grid raycaster (1)');
1053     begin
1054       // check for crossing tile/grid boundary
1055       if (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy) then
1056       begin
1057         // we're still in grid
1058         lastWasInGrid := true;
1059         // check for tile edge crossing
1060              if (stepx < 0) and ((x mod tsize) = tsize-1) then tbcross := true
1061         else if (stepx > 0) and ((x mod tsize) = 0) then tbcross := true
1062         else if (stepy < 0) and ((y mod tsize) = tsize-1) then tbcross := true
1063         else if (stepy > 0) and ((y mod tsize) = 0) then tbcross := true
1064         else tbcross := false;
1065         // crossed tile edge?
1066         if tbcross then
1067         begin
1068           // had something in the cell we're leaving?
1069           if (ccidx <> -1) then
1070           begin
1071             // yes, signal cell completion
1072             if assigned(cb) then
1073             begin
1074               if cb(nil, 0, x+minx, y+miny, prevX, prevY) then begin result := lastObj; exit; end;
1075             end
1076             else if wasHit then
1077             begin
1078               result := lastObj;
1079               exit;
1080             end;
1081           end;
1082           // setup new cell index
1083           ccidx := mGrid[(y div tsize)*gw+(x div tsize)];
1084         end;
1085       end
1086       else
1087       begin
1088         // out of grid, had something in the last processed cell?
1089         if (ccidx <> -1) then
1090         begin
1091           // yes, signal cell completion
1092           ccidx := -1;
1093           if assigned(cb) then
1094           begin
1095             if cb(nil, 0, x+minx, y+miny, prevX, prevY) then begin result := lastObj; exit; end;
1096           end
1097           else if wasHit then
1098           begin
1099             result := lastObj;
1100             exit;
1101           end;
1102         end;
1103         if lastWasInGrid then exit; // oops, stepped out of the grid -- there is no way to return
1104       end;
1105     end;
1106
1107     // has something to process in the current cell?
1108     if (ccidx <> -1) then
1109     begin
1110       // process cell
1111       curci := ccidx;
1112       hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1113       // convert coords to map (to avoid ajdusting coords inside the loop)
1114       Inc(x, minx);
1115       Inc(y, miny);
1116       // process cell list
1117       while (curci <> -1) do
1118       begin
1119         cc := @mCells[curci];
1120         for f := 0 to High(TGridCell.bodies) do
1121         begin
1122           if (cc.bodies[f] = -1) then break;
1123           px := @mProxies[cc.bodies[f]];
1124           ptag := px.mTag;
1125           if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
1126           begin
1127             // can we process this proxy?
1128             if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
1129             begin
1130               px.mQueryMark := lq; // mark as processed
1131               if assigned(cb) then
1132               begin
1133                 if cb(px.mObj, ptag, x, y, prevX, prevY) then
1134                 begin
1135                   result := lastObj;
1136                   ex := prevX;
1137                   ey := prevY;
1138                   exit;
1139                 end;
1140               end
1141               else
1142               begin
1143                 // remember this hitpoint if it is nearer than an old one
1144                 distSq := (prevX-x0)*(prevX-x0)+(prevY-y0)*(prevY-y0);
1145                 if (distSq < lastDistSq) then
1146                 begin
1147                   wasHit := true;
1148                   lastDistSq := distSq;
1149                   ex := prevX;
1150                   ey := prevY;
1151                   lastObj := px.mObj;
1152                 end;
1153               end;
1154             end
1155             else
1156             begin
1157               // this is possibly interesting proxy, set "has more to check" flag
1158               hasUntried := true;
1159             end;
1160           end;
1161         end;
1162         // next cell
1163         curci := cc.next;
1164       end;
1165       // still has something interesting in this cell?
1166       if not hasUntried then
1167       begin
1168         // nope, don't process this cell anymore; signal cell completion
1169         ccidx := -1;
1170         if assigned(cb) then
1171         begin
1172           if cb(nil, 0, x, y, prevX, prevY) then begin result := lastObj; exit; end;
1173         end
1174         else if wasHit then
1175         begin
1176           result := lastObj;
1177           exit;
1178         end;
1179       end;
1180       // convert coords to grid
1181       Dec(x, minx);
1182       Dec(y, miny);
1183     end;
1184   end;
1185 end;
1186
1187
1188 // ////////////////////////////////////////////////////////////////////////// //
1189 function TBodyGridBase.forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
1190 const
1191   tsize = mTileSize;
1192 var
1193   i: Integer;
1194   dx, dy, d: Integer;
1195   xerr, yerr: Integer;
1196   incx, incy: Integer;
1197   stepx, stepy: Integer;
1198   x, y: Integer;
1199   maxx, maxy: Integer;
1200   gw, gh: Integer;
1201   ccidx: Integer;
1202   curci: Integer;
1203   cc: PGridCell;
1204   px: PBodyProxyRec;
1205   lq: LongWord;
1206   minx, miny: Integer;
1207   ptag: Integer;
1208   lastWasInGrid: Boolean;
1209   tbcross: Boolean;
1210   f: Integer;
1211 begin
1212   result := Default(ITP);
1213   tagmask := tagmask and TagFullMask;
1214   if (tagmask = 0) then exit;
1215
1216   minx := mMinX;
1217   miny := mMinY;
1218
1219   dx := x1-x0;
1220   dy := y1-y0;
1221
1222   if (dx > 0) then incx := 1 else if (dx < 0) then incx := -1 else incx := 0;
1223   if (dy > 0) then incy := 1 else if (dy < 0) then incy := -1 else incy := 0;
1224
1225   dx := abs(dx);
1226   dy := abs(dy);
1227
1228   if (dx > dy) then d := dx else d := dy;
1229
1230   // `x` and `y` will be in grid coords
1231   x := x0-minx;
1232   y := y0-miny;
1233
1234   // increase query counter
1235   Inc(mLastQuery);
1236   if (mLastQuery = 0) then
1237   begin
1238     // just in case of overflow
1239     mLastQuery := 1;
1240     for i := 0 to High(mProxies) do mProxies[i].mQueryMark := 0;
1241   end;
1242   lq := mLastQuery;
1243
1244   // cache various things
1245   //tsize := mTileSize;
1246   gw := mWidth;
1247   gh := mHeight;
1248   maxx := gw*tsize-1;
1249   maxy := gh*tsize-1;
1250
1251   // setup distance and flags
1252   lastWasInGrid := (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy);
1253
1254   // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1255   if lastWasInGrid then ccidx := mGrid[(y div tsize)*gw+(x div tsize)] else ccidx := -1;
1256
1257   // it is slightly faster this way
1258   xerr := -d;
1259   yerr := -d;
1260
1261   // now trace
1262   for i := 1 to d do
1263   begin
1264     // do one step
1265     xerr += dx;
1266     yerr += dy;
1267     // invariant: one of those always changed
1268     if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1269     if (xerr >= 0) then begin xerr -= d; x += incx; stepx := incx; end else stepx := 0;
1270     if (yerr >= 0) then begin yerr -= d; y += incy; stepy := incy; end else stepy := 0;
1271     // invariant: we always doing a step
1272     if ((stepx or stepy) = 0) then raise Exception.Create('internal bug in grid raycaster (1)');
1273     begin
1274       // check for crossing tile/grid boundary
1275       if (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy) then
1276       begin
1277         // we're still in grid
1278         lastWasInGrid := true;
1279         // check for tile edge crossing
1280              if (stepx < 0) and ((x mod tsize) = tsize-1) then tbcross := true
1281         else if (stepx > 0) and ((x mod tsize) = 0) then tbcross := true
1282         else if (stepy < 0) and ((y mod tsize) = tsize-1) then tbcross := true
1283         else if (stepy > 0) and ((y mod tsize) = 0) then tbcross := true
1284         else tbcross := false;
1285         // crossed tile edge?
1286         if tbcross then
1287         begin
1288           // setup new cell index
1289           ccidx := mGrid[(y div tsize)*gw+(x div tsize)];
1290         end;
1291       end
1292       else
1293       begin
1294         // out of grid
1295         if lastWasInGrid then exit; // oops, stepped out of the grid -- there is no way to return
1296       end;
1297     end;
1298
1299     // has something to process in the current cell?
1300     if (ccidx <> -1) then
1301     begin
1302       // process cell
1303       curci := ccidx;
1304       // convert coords to map (to avoid ajdusting coords inside the loop)
1305       Inc(x, minx);
1306       Inc(y, miny);
1307       // process cell list
1308       while (curci <> -1) do
1309       begin
1310         cc := @mCells[curci];
1311         for f := 0 to High(TGridCell.bodies) do
1312         begin
1313           if (cc.bodies[f] = -1) then break;
1314           px := @mProxies[cc.bodies[f]];
1315           ptag := px.mTag;
1316           if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
1317           begin
1318             px.mQueryMark := lq; // mark as processed
1319             if cb(px.mObj, ptag) then begin result := px.mObj; exit; end;
1320           end;
1321         end;
1322         // next cell
1323         curci := cc.next;
1324       end;
1325       ccidx := -1; // don't process this anymore
1326       // convert coords to grid
1327       Dec(x, minx);
1328       Dec(y, miny);
1329     end;
1330   end;
1331 end;
1332
1333
1334 end.