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