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