79b87ca5a4bf44859ea618fac4f29aec91fd1e28
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 {$IF DEFINED(D2F_DEBUG)}
19 {.$DEFINE D2F_DEBUG_RAYTRACE}
20 {.$DEFINE D2F_DEBUG_XXQ}
21 {.$DEFINE D2F_DEBUG_MOVER}
22 {$ENDIF}
23 {.$DEFINE GRID_USE_ORTHO_ACCEL}
24 {$DEFINE LINEAABB2}
27 interface
29 uses
30 mempool;
32 (*
33 * In order to make this usable for kind-of-recursive calls,
34 * we'll use "frame memory pool" to return results. That is,
35 * we will allocate a memory pool that will be cleared on
36 * frame start, and then used as a simple "no-free" allocator.
37 * Grid will put results into this pool, and will never bother
38 * to free it. Caller should call "release" on result, and
39 * the pool will throw away everything.
40 * No more callbacks, of course.
41 *)
43 const
46 type
55 type
59 public
68 private
69 const
72 public
73 type
76 private
83 private
95 public
110 private
111 type
120 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
122 private
123 //mTileSize: Integer;
127 public
130 type
132 private
136 public
143 private
156 public
158 {$IF DEFINED(D2F_DEBUG)}
160 {$ENDIF}
162 private
182 public
183 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
186 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
195 // `false` if `body` is surely invalid
200 // return number of ITP thingys put into frame pool
201 // if `firstHit` is `true`, return on first hit (obviously)
202 function forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Iter;
204 // return number of ITP thingys put into frame pool
205 // if `firstHit` is `true`, return on first hit (obviously)
206 function forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Iter;
210 // return object of the nearest hit or nil
212 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
214 // return `false` if we're still inside at the end
215 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
216 // `true`: endpoint will point at the last "inside" pixel
217 // `false`: endpoint will be (ax1, ay1)
218 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
220 // trace line along the grid, put all objects from passed cells into frame pool, in no particular order
221 // return number of ITP thingys put into frame pool
222 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1; log: Boolean=false): Iter;
224 // trace box with the given velocity; return object hit (if any)
225 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
226 //WARNING: don't change tags in callbacks here!
227 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; tagmask: Integer=-1): ITP;
229 // debug
230 function forEachBodyCell (body: TBodyProxyId): CellCoordIter; // this puts `TGridCellCoord` into frame pool for each cell
234 public
235 //WARNING! no sanity checks!
247 type
248 // common structure for all line tracers
250 public
253 private
261 public
262 // call `setyp` after this
267 // this will use `w[xy][01]` to clip coords
268 // return `false` if the whole line was clipped away
269 // on `true`, you should process first point, and go on
272 // call this *after* doing a step
273 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
276 // as you will prolly call `done()` after doing a step anyway, this will do it for you
277 // move to next point, return `true` when the line is complete (i.e. you should stop)
280 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
285 public
286 // current coords
293 //function minInt (a, b: Integer): Integer; inline;
294 //function maxInt (a, b: Integer): Integer; inline;
297 implementation
299 uses
303 // ////////////////////////////////////////////////////////////////////////// //
304 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
305 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
306 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
307 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
310 // ////////////////////////////////////////////////////////////////////////// //
312 begin
317 begin
318 // clip rectange
326 var
328 begin
329 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
333 begin
335 end
336 else
337 begin
346 // check for ortho lines
348 begin
349 // horizontal
356 end
358 begin
359 // vertical
366 end
367 else
368 begin
369 // diagonal
371 begin
372 // horizontal
376 end
377 else
378 begin
379 // vertical
395 // true: done
397 begin
399 begin
403 end
404 else
405 begin
414 // true: done
416 var
420 begin
425 // strictly horizontal?
427 begin
428 // only xd
430 begin
431 // xd: to left edge
434 end
435 else
436 begin
437 // xd: to right edge
443 exit;
446 // strictly vertical?
448 begin
449 // only xd
451 begin
452 // yd: to top edge
455 end
456 else
457 begin
458 // yd: to bottom edge
464 exit;
467 // diagonal
469 // calculate xwalk
471 begin
474 end
475 else
476 begin
481 // calculate ywalk
483 begin
486 end
487 else
488 begin
493 {
494 while (xd <> ex) and (yd <> ey) do
495 begin
496 if horiz then
497 begin
498 xd += stx;
499 err += errinc;
500 if (err >= 0) then begin err -= errmax; yd += sty; end;
501 end
502 else
503 begin
504 yd += sty;
505 err += errinc;
506 if (err >= 0) then begin err -= errmax; xd += stx; end;
507 end;
508 Dec(stleft);
509 if (stleft < 1) then begin result := true; exit; end;
510 end;
511 }
515 begin
516 // in which dir we want to walk?
520 begin
523 begin
527 end
528 else
529 begin
532 begin
537 // check for walk completion
546 // ////////////////////////////////////////////////////////////////////////// //
547 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
548 begin
561 begin
566 begin
571 begin
576 begin
581 begin
586 begin
591 // ////////////////////////////////////////////////////////////////////////// //
592 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
593 begin
602 begin
604 begin
606 begin
610 exit;
620 begin
625 // ////////////////////////////////////////////////////////////////////////// //
626 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
627 var
629 begin
631 {$IF DEFINED(D2F_DEBUG)}
633 {$ENDIF}
634 {
635 if aTileSize < 1 then aTileSize := 1;
636 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
637 mTileSize := aTileSize;
638 }
649 // init free list
651 begin
657 // init grid
659 // init proxies
667 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
672 begin
680 // ////////////////////////////////////////////////////////////////////////// //
682 var
684 begin
687 begin
691 begin
697 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]), TMsgType.Notify);
702 var
706 begin
710 begin
713 begin
716 begin
719 begin
723 //cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
726 // next cell
735 var
739 begin
743 if (x < 0) or (y < 0) or (x >= mWidth*mTileSize) or (y > mHeight*mTileSize) then begin result.finishIt(); exit; end;
746 begin
749 begin
751 //if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
753 //presobj^ := mProxies[cc.bodies[f]].mObj;
756 // next cell
763 // ////////////////////////////////////////////////////////////////////////// //
764 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
765 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
769 begin
770 // fix coords
778 begin
780 begin
783 end
784 else
785 begin
794 begin
796 begin
799 end
800 else
801 begin
809 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
810 begin
812 begin
815 end
816 else
817 begin
828 // ////////////////////////////////////////////////////////////////////////// //
830 begin
831 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
836 begin
838 begin
840 begin
842 end
843 else
844 begin
852 begin
857 // ////////////////////////////////////////////////////////////////////////// //
859 var
862 begin
864 begin
865 // no free cells, want more
869 begin
881 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
886 begin
888 begin
890 begin
901 // ////////////////////////////////////////////////////////////////////////// //
902 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
903 var
906 begin
908 begin
909 // no free proxies, resize list
916 // get one from list
921 // add to used list
923 // statistics
929 begin
931 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
932 // add to free list
940 // ////////////////////////////////////////////////////////////////////////// //
941 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
942 var
946 begin
949 // fix coords
952 // go on
961 // clip rect
967 // do the work
969 begin
971 begin
979 // ////////////////////////////////////////////////////////////////////////// //
981 var
986 begin
988 // add body to the given grid cell
991 begin
992 {$IF DEFINED(D2F_DEBUG)}
995 begin
998 begin
1000 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1004 {$ENDIF}
1007 begin
1009 // check "has room" flag
1011 begin
1012 // can add here
1014 begin
1016 begin
1019 exit;
1024 // no room, go to next cell in list (if there is any)
1027 // no room in cells, add new cell to list
1029 // either no room, or no cell at all
1039 // assume that we cannot have one object added to bucket twice
1041 var
1045 begin
1047 // find and remove cell
1051 begin
1054 begin
1056 begin
1057 // i found her!
1059 begin
1060 // this cell contains no elements, remove it
1063 exit;
1065 // remove element from bucket
1067 begin
1072 exit;
1081 // ////////////////////////////////////////////////////////////////////////// //
1082 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1083 begin
1086 //insertInternal(result);
1092 var
1094 begin
1097 //removeInternal(body);
1103 // ////////////////////////////////////////////////////////////////////////// //
1105 var
1108 begin
1115 {$IF DEFINED(D2F_DEBUG_MOVER)}
1116 e_WriteLog(Format('proxy #%d: MOVERESIZE: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d;nw=%d;nh=%d', [body, x0-mMinX, y0-mMinY, w, h, nx-mMinX, ny-mMinY, nw, nh]), MSG_NOTIFY);
1117 {$ENDIF}
1119 // map -> grid
1124 // did any corner crossed tile boundary?
1129 begin
1130 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1131 //removeInternal(body);
1137 //insertInternal(body);
1139 end
1140 else
1141 begin
1150 //TODO: optimize for horizontal/vertical moves
1152 var
1160 begin
1162 // check if tile coords was changed
1167 // map -> grid
1172 // check for heavy work
1183 {$IF DEFINED(D2F_DEBUG_MOVER)}
1184 e_WriteLog(Format('proxy #%d: checkmove: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [body, x0, y0, pw, ph, nx, ny, ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY);
1185 {$ENDIF}
1187 begin
1188 // crossed tile boundary, do heavy work
1191 // cycle with old rect, remove body where it is necessary
1192 // optimized for horizontal moves
1193 {$IF DEFINED(D2F_DEBUG_MOVER)}
1194 e_WriteLog(Format('proxy #%d: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [body, x0, y0, pw, ph, nx, ny, ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY);
1195 {$ENDIF}
1196 // remove stale marks
1199 begin
1204 {$IF DEFINED(D2F_DEBUG_MOVER)}
1206 {$ENDIF}
1208 begin
1210 begin
1211 // this column is completely outside of new rect
1213 begin
1214 {$IF DEFINED(D2F_DEBUG_MOVER)}
1216 {$ENDIF}
1219 end
1220 else
1221 begin
1222 // heavy checks
1224 begin
1226 begin
1227 {$IF DEFINED(D2F_DEBUG_MOVER)}
1229 {$ENDIF}
1236 // cycle with new rect, add body where it is necessary
1239 begin
1244 {$IF DEFINED(D2F_DEBUG_MOVER)}
1246 {$ENDIF}
1248 begin
1250 begin
1251 // this column is completely outside of old rect
1253 begin
1254 {$IF DEFINED(D2F_DEBUG_MOVER)}
1256 {$ENDIF}
1259 end
1260 else
1261 begin
1262 // heavy checks
1264 begin
1266 begin
1267 {$IF DEFINED(D2F_DEBUG_MOVER)}
1269 {$ENDIF}
1276 // done
1277 end
1278 else
1279 begin
1280 {$IF DEFINED(D2F_DEBUG_MOVER)}
1281 e_WriteLog(Format('proxy #%d: GRID OK: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [body, x0, y0, pw, ph, nx, ny, ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY);
1282 {$ENDIF}
1284 // update coordinates
1291 var
1294 begin
1296 // check if tile coords was changed
1302 {$IF DEFINED(D2F_DEBUG_MOVER)}
1303 e_WriteLog(Format('proxy #%d: RESIZE: xg=%d;yg=%d;w=%d;h=%d;nw=%d;nh=%d', [body, x0, y0, w, h, nw, nh]), MSG_NOTIFY);
1304 {$ENDIF}
1307 begin
1308 // crossed tile boundary, do heavy work
1309 //removeInternal(body);
1313 //insertInternal(body);
1315 end
1316 else
1317 begin
1318 // nothing to do with the grid, just fix size
1325 // ////////////////////////////////////////////////////////////////////////// //
1327 var
1329 begin
1332 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1337 // ////////////////////////////////////////////////////////////////////////// //
1338 // no callback: return `true` on the first hit
1339 function TBodyGridBase.forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Iter;
1340 var
1348 begin
1353 {$IF DEFINED(D2F_DEBUG_XXQ)}
1355 {$ENDIF}
1357 // make coords (0,0)-based
1360 if (x < 0) or (y < 0) or (x >= mWidth*mTileSize) or (y >= mHeight*mTileSize) then begin result.finishIt(); exit; end;
1364 {$IF DEFINED(D2F_DEBUG_XXQ)}
1365 if (assigned(cb)) then e_WriteLog(Format('1: grid pointquery: (%d,%d) (%d,%d) %d', [x, y, (x div mTileSize), (y div mTileSize), curci]), MSG_NOTIFY);
1366 {$ENDIF}
1368 // restore coords
1372 // increase query counter
1375 begin
1376 // just in case of overflow
1382 {$IF DEFINED(D2F_DEBUG_XXQ)}
1383 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1384 {$ENDIF}
1387 begin
1388 {$IF DEFINED(D2F_DEBUG_XXQ)}
1389 //if (assigned(cb)) then e_WriteLog(Format(' cell #%d', [curci]), MSG_NOTIFY);
1390 {$ENDIF}
1393 begin
1396 {$IF DEFINED(D2F_DEBUG_XXQ)}
1397 //if (assigned(cb)) then e_WriteLog(Format(' proxy #%d; qm:%u; tag:%08x; tagflag:%d %u', [cc.bodies[f], px.mQueryMark, px.mTag, (px.mTag and tagmask), LongWord(px.mObj)]), MSG_NOTIFY);
1398 {$ENDIF}
1405 begin
1417 // ////////////////////////////////////////////////////////////////////////// //
1418 // no callback: return `true` on the first hit
1419 // return number of ITP thingys put into frame pool
1420 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Iter;
1421 var
1434 begin
1436 begin
1438 exit;
1450 // fix coords
1465 // clip rect
1472 // has something to do
1474 // increase query counter
1477 begin
1478 // just in case of overflow
1482 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1485 // go on
1487 begin
1489 begin
1490 // process cells
1493 begin
1496 begin
1499 // shit! has to do it this way, so i can change tag in callback
1519 // ////////////////////////////////////////////////////////////////////////// //
1520 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1; log: Boolean=false): Iter;
1521 var
1532 //px0, py0, px1, py1: Integer;
1534 begin
1545 // make query coords (0,0)-based
1554 // increase query counter
1557 begin
1558 // just in case of overflow
1564 repeat
1566 // check tile
1568 // process cells
1570 begin
1573 begin
1578 begin
1584 // next cell
1587 // done processing cells, move to next tile
1593 // ////////////////////////////////////////////////////////////////////////// //
1594 // trace box with the given velocity; return object hit (if any)
1595 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; tagmask: Integer=-1): ITP;
1596 var
1607 begin
1621 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1627 // just in case
1630 // increase query counter
1633 begin
1634 // just in case of overflow
1641 begin
1643 begin
1646 begin
1649 begin
1654 begin
1656 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1658 begin
1663 begin
1666 exit;
1671 // next cell
1678 begin
1681 // just in case, compensate for floating point inexactness
1682 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1683 begin
1691 // ////////////////////////////////////////////////////////////////////////// //
1692 {.$DEFINE D2F_DEBUG_OTR}
1693 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1694 var
1705 {$IF DEFINED(D2F_DEBUG_OTR)}
1707 {$ENDIF}
1709 begin
1725 // offset query coords to (0,0)-based
1732 begin
1734 // vertical
1736 begin
1737 // down
1739 //if (ay0 < 0) then ay0 := 0;
1743 end
1744 else
1745 begin
1746 // up
1748 //if (ay1 < 0) then ay1 := 0;
1753 // check tile
1755 begin
1761 begin
1764 begin
1770 begin
1771 // bound c0 and c1 to cell
1774 // fill the thing
1775 {$IF DEFINED(D2F_DEBUG_OTR)}
1776 e_LogWritefln('**px.y0=%s; px.y1=%s; c0=%s; c1=%s; celly0=%s; celly1=%s; [%s..%s]', [px.y0-miny, px.y1-miny, c0, c1, celly0, celly1, c0-celly0, (c0-celly0)+(c1-c0)]);
1777 {$ENDIF}
1778 //assert(c0 <= c1);
1782 // next cell
1785 {$IF DEFINED(D2F_DEBUG_OTR)}
1786 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1790 {$ENDIF}
1791 // now go till we hit cell boundary or empty space
1793 begin
1794 // up
1796 begin
1797 {$IF DEFINED(D2F_DEBUG_OTR)}
1798 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1799 {$ENDIF}
1803 {$IF DEFINED(D2F_DEBUG_OTR)}
1804 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1805 {$ENDIF}
1807 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1808 end
1809 else
1810 begin
1811 // down
1817 end
1818 else
1819 begin
1820 // horizontal
1826 // ////////////////////////////////////////////////////////////////////////// //
1828 var
1830 begin
1835 // you are not supposed to understand this
1836 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
1837 var
1852 begin
1862 // make query coords (0,0)-based
1873 {$IF DEFINED(D2F_DEBUG)}
1874 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1875 {$ENDIF}
1877 // increase query counter
1880 begin
1881 // just in case of overflow
1887 repeat
1889 {$IF DEFINED(D2F_DEBUG)}
1891 {$ENDIF}
1892 // check tile
1894 // process cells
1897 begin
1900 begin
1905 begin
1907 // get adjusted proxy coords
1912 {$IF DEFINED(D2F_DEBUG)}
1913 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1914 {$ENDIF}
1915 // inside?
1917 begin
1918 // oops
1922 {$IF DEFINED(D2F_DEBUG)}
1924 {$ENDIF}
1925 exit;
1927 // do line-vs-aabb test
1929 begin
1930 // hit detected
1932 {$IF DEFINED(D2F_DEBUG)}
1933 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1934 {$ENDIF}
1936 begin
1946 // next cell
1949 // done processing cells; exit if we registered a hit
1950 // next cells can't have better candidates, obviously
1953 // move to next tile