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