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}
26 interface
29 type
33 public
34 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
35 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
42 private
43 const
47 public
48 type
51 private
58 private
70 public
85 private
86 type
95 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
97 private
98 //mTileSize: Integer;
102 public
105 type
107 private
111 public
118 private
132 public
134 {$IF DEFINED(D2F_DEBUG)}
136 {$ENDIF}
138 private
161 public
162 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
165 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
174 // `false` if `body` is surely invalid
179 //WARNING: don't modify grid while any query is in progress (no checks are made!)
180 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
181 // no callback: return `true` on the first hit
182 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
184 //WARNING: don't modify grid while any query is in progress (no checks are made!)
185 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
186 // no callback: return object on the first hit or nil
187 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
191 //WARNING: don't modify grid while any query is in progress (no checks are made!)
192 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
193 // cb with `(nil)` will be called before processing new tile
194 // no callback: return object of the nearest hit or nil
195 // if `inverted` is true, trace will register bodies *exluding* tagmask
196 //WARNING: don't change tags in callbacks here!
197 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
198 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
200 // return `false` if we're still inside at the end
201 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
202 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
204 //WARNING: don't modify grid while any query is in progress (no checks are made!)
205 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
206 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
207 //WARNING: don't change tags in callbacks here!
208 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
210 // debug
215 public
216 //WARNING! no sanity checks!
228 // you are not supposed to understand this
229 // returns `true` if there is an intersection, and enter coords
230 // enter coords will be equal to (x0, y0) if starting point is inside the box
231 // if result is `false`, `inx` and `iny` are undefined
232 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
241 implementation
243 uses
247 // ////////////////////////////////////////////////////////////////////////// //
248 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
249 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
250 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
252 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
255 // ////////////////////////////////////////////////////////////////////////// //
256 // you are not supposed to understand this
257 // returns `true` if there is an intersection, and enter coords
258 // enter coords will be equal to (x0, y0) if starting point is inside the box
259 // if result is `false`, `inx` and `iny` are undefined
260 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
261 var
269 //!term: Integer;
273 begin
275 // why not
281 begin
282 // check this point
284 exit;
287 // check if staring point is inside the box
288 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
290 // clip rectange
296 // horizontal setup
298 begin
299 // from left to right
302 end
303 else
304 begin
305 // from right to left
315 // vertical setup
317 begin
318 // from top to bottom
321 end
322 else
323 begin
324 // from bottom to top
338 begin
347 end
348 else
349 begin
359 //!term := x1;
363 begin
364 // clip at top
370 begin
379 begin
380 // clip at left
390 (*
391 if (y1 > wy1) then
392 begin
393 // clip at bottom
394 temp := dx2*(wy1-y0)+dsx;
395 term := x0+temp div dy2;
396 rem := temp mod dy2;
397 if (rem = 0) then Dec(term);
398 end;
400 if (term > wx1) then term := wx1; // clip at right
402 Inc(term); // draw last point
403 //if (term = xd) then exit; // this is the only point, get out of here
404 *)
408 //!dx2 -= dy2;
416 // ////////////////////////////////////////////////////////////////////////// //
417 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
418 begin
431 begin
436 begin
441 begin
446 begin
451 begin
456 begin
461 // ////////////////////////////////////////////////////////////////////////// //
462 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
463 begin
472 begin
474 begin
476 begin
480 exit;
490 begin
495 // ////////////////////////////////////////////////////////////////////////// //
496 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
497 var
499 begin
501 {$IF DEFINED(D2F_DEBUG)}
503 {$ENDIF}
504 {
505 if aTileSize < 1 then aTileSize := 1;
506 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
507 mTileSize := aTileSize;
508 }
519 // init free list
521 begin
527 // init grid
529 // init proxies
537 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
542 begin
550 // ////////////////////////////////////////////////////////////////////////// //
552 var
554 begin
557 begin
561 begin
567 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);
572 var
575 begin
578 begin
581 begin
584 begin
586 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
588 // next cell
596 var
599 begin
607 begin
610 begin
612 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
614 // next cell
620 // ////////////////////////////////////////////////////////////////////////// //
621 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
622 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
626 begin
627 // fix coords
635 begin
637 begin
640 end
641 else
642 begin
651 begin
653 begin
656 end
657 else
658 begin
666 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
667 begin
669 begin
672 end
673 else
674 begin
685 // ////////////////////////////////////////////////////////////////////////// //
687 begin
693 begin
695 begin
697 begin
699 end
700 else
701 begin
709 begin
714 // ////////////////////////////////////////////////////////////////////////// //
716 var
719 begin
721 begin
722 // no free cells, want more
726 begin
738 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
743 begin
745 begin
747 begin
758 // ////////////////////////////////////////////////////////////////////////// //
759 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
760 var
763 begin
765 begin
766 // no free proxies, resize list
773 // get one from list
778 // add to used list
780 // statistics
786 begin
788 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
789 // add to free list
797 // ////////////////////////////////////////////////////////////////////////// //
798 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
799 const
801 var
804 begin
807 // fix coords
810 // go on
814 //tsize := mTileSize;
817 begin
821 begin
831 // ////////////////////////////////////////////////////////////////////////// //
833 var
838 begin
840 // add body to the given grid cell
843 begin
844 {$IF DEFINED(D2F_DEBUG)}
847 begin
850 begin
852 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
856 {$ENDIF}
859 begin
861 // check "has room" flag
863 begin
864 // can add here
866 begin
868 begin
871 exit;
876 // no room, go to next cell in list (if there is any)
879 // no room in cells, add new cell to list
881 // either no room, or no cell at all
891 var
893 begin
900 // assume that we cannot have one object added to bucket twice
902 var
906 begin
908 // find and remove cell
912 begin
915 begin
917 begin
918 // i found her!
920 begin
921 // this cell contains no elements, remove it
924 exit;
926 // remove element from bucket
928 begin
933 exit;
942 var
944 begin
951 // ////////////////////////////////////////////////////////////////////////// //
952 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
953 begin
961 begin
968 // ////////////////////////////////////////////////////////////////////////// //
970 var
973 begin
980 {$IF DEFINED(D2F_DEBUG_MOVER)}
981 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);
982 {$ENDIF}
984 // map -> grid
989 // did any corner crossed tile boundary?
994 begin
1001 end
1002 else
1003 begin
1011 //TODO: optimize for horizontal/vertical moves
1013 var
1021 begin
1023 // check if tile coords was changed
1028 // map -> grid
1033 // check for heavy work
1044 {$IF DEFINED(D2F_DEBUG_MOVER)}
1045 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);
1046 {$ENDIF}
1048 begin
1049 // crossed tile boundary, do heavy work
1052 // cycle with old rect, remove body where it is necessary
1053 // optimized for horizontal moves
1054 {$IF DEFINED(D2F_DEBUG_MOVER)}
1055 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);
1056 {$ENDIF}
1057 // remove stale marks
1060 begin
1065 {$IF DEFINED(D2F_DEBUG_MOVER)}
1067 {$ENDIF}
1069 begin
1071 begin
1072 // this column is completely outside of new rect
1074 begin
1075 {$IF DEFINED(D2F_DEBUG_MOVER)}
1077 {$ENDIF}
1080 end
1081 else
1082 begin
1083 // heavy checks
1085 begin
1087 begin
1088 {$IF DEFINED(D2F_DEBUG_MOVER)}
1090 {$ENDIF}
1097 // cycle with new rect, add body where it is necessary
1100 begin
1105 {$IF DEFINED(D2F_DEBUG_MOVER)}
1107 {$ENDIF}
1109 begin
1111 begin
1112 // this column is completely outside of old rect
1114 begin
1115 {$IF DEFINED(D2F_DEBUG_MOVER)}
1117 {$ENDIF}
1120 end
1121 else
1122 begin
1123 // heavy checks
1125 begin
1127 begin
1128 {$IF DEFINED(D2F_DEBUG_MOVER)}
1130 {$ENDIF}
1137 // done
1138 end
1139 else
1140 begin
1141 {$IF DEFINED(D2F_DEBUG_MOVER)}
1142 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);
1143 {$ENDIF}
1145 // update coordinates
1151 var
1154 begin
1156 // check if tile coords was changed
1162 {$IF DEFINED(D2F_DEBUG_MOVER)}
1163 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);
1164 {$ENDIF}
1167 begin
1168 // crossed tile boundary, do heavy work
1173 end
1174 else
1175 begin
1176 // nothing to do with the grid, just fix size
1183 // ////////////////////////////////////////////////////////////////////////// //
1185 var
1187 begin
1190 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then cidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1195 // ////////////////////////////////////////////////////////////////////////// //
1196 // no callback: return `true` on the first hit
1197 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1198 var
1205 begin
1211 {$IF DEFINED(D2F_DEBUG_XXQ)}
1213 {$ENDIF}
1215 // make coords (0,0)-based
1222 {$IF DEFINED(D2F_DEBUG_XXQ)}
1223 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);
1224 {$ENDIF}
1226 // restore coords
1230 // increase query counter
1233 begin
1234 // just in case of overflow
1240 {$IF DEFINED(D2F_DEBUG_XXQ)}
1241 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1242 {$ENDIF}
1245 begin
1246 {$IF DEFINED(D2F_DEBUG_XXQ)}
1248 {$ENDIF}
1251 begin
1254 {$IF DEFINED(D2F_DEBUG_XXQ)}
1255 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);
1256 {$ENDIF}
1257 // shit. has to do it this way, so i can change tag in callback
1259 begin
1264 begin
1266 begin
1268 begin
1271 exit;
1273 end
1274 else
1275 begin
1278 exit;
1288 // ////////////////////////////////////////////////////////////////////////// //
1289 // no callback: return `true` on the first hit
1290 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1291 const
1293 var
1304 begin
1313 // fix coords
1318 //tsize := mTileSize;
1326 // increase query counter
1329 begin
1330 // just in case of overflow
1334 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1337 // go on
1339 begin
1343 begin
1346 // process cells
1349 begin
1352 begin
1355 // shit. has to do it this way, so i can change tag in callback
1364 begin
1366 end
1367 else
1368 begin
1371 exit;
1383 // ////////////////////////////////////////////////////////////////////////// //
1384 // no callback: return `true` on the nearest hit
1385 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1386 var
1388 begin
1393 // no callback: return `true` on the nearest hit
1394 // you are not supposed to understand this
1395 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1396 const
1398 var
1424 //swapped: Boolean = false; // true: xd is yd, and vice versa
1425 // horizontal walker
1426 {$IFDEF GRID_USE_ORTHO_ACCEL}
1428 //wksign: Integer;
1430 {$ENDIF}
1431 // skipper
1433 begin
1442 begin
1445 begin
1448 exit;
1460 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1461 if assigned(dbgRayTraceTileHitCB) then e_WriteLog(Format('TRACING: (%d,%d)-(%d,%d) [(%d,%d)-(%d,%d)]; maxdistsq=%d', [ax0, ay0, ax1, ay1, minx, miny, maxx, maxy, lastDistSq]), MSG_NOTIFY);
1462 {$ENDIF}
1469 // offset query coords to (0,0)-based
1475 // clip rectange
1481 // horizontal setup
1483 begin
1484 // from left to right
1487 end
1488 else
1489 begin
1490 // from right to left
1500 // vertical setup
1502 begin
1503 // from top to bottom
1506 end
1507 else
1508 begin
1509 // from bottom to top
1523 begin
1524 //swapped := true;
1533 end
1534 else
1535 begin
1549 begin
1550 // clip at top
1556 begin
1565 begin
1566 // clip at left
1577 begin
1578 // clip at bottom
1588 //if (term = xd) then exit; // this is the only point, get out of here
1594 // first move, to skip starting point
1595 // DON'T DO THIS! loop will take care of that
1597 begin
1598 //FIXME!
1601 begin
1603 begin
1605 begin
1608 end
1609 else
1610 begin
1613 end
1614 else
1615 begin
1620 exit;
1625 (*
1626 // move coords
1627 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1628 xd += stx;
1629 // done?
1630 if (xd = term) then exit;
1631 *)
1633 {$IF DEFINED(D2F_DEBUG)}
1634 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1635 {$ENDIF}
1636 // DON'T DO THIS! loop will take care of that
1637 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1638 //ccidx := mGrid[lastGA];
1640 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1641 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1642 {$ENDIF}
1644 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1649 // increase query counter
1652 begin
1653 // just in case of overflow
1659 {$IFDEF GRID_USE_ORTHO_ACCEL}
1660 // if this is strict horizontal/vertical trace, use optimized codepath
1662 begin
1663 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1664 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1665 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1666 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1668 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1669 {$IF DEFINED(D2F_DEBUG)}
1671 {$ENDIF}
1673 // one of those will never change
1677 begin
1678 {$IF DEFINED(D2F_DEBUG)}
1679 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1680 {$ENDIF}
1681 // new tile?
1683 begin
1686 // convert coords to map (to avoid ajdusting coords inside the loop)
1689 begin
1692 begin
1697 // constant coord should be inside
1700 begin
1702 // inside the proxy?
1705 begin
1706 // setup prev[xy]
1708 begin
1710 begin
1715 exit;
1717 end
1718 else
1719 begin
1721 {$IF DEFINED(D2F_DEBUG)}
1722 if dbgShowTraceLog then e_LogWritefln(' EMBEDDED hhit(%d): a=(%d,%d), h=(%d,%d), distsq=%d; lastsq=%d', [cc.bodies[f], ax0, ay0, x, y, distSq, lastDistSq]);
1723 {$ENDIF}
1725 begin
1730 exit;
1733 continue;
1735 // remember this hitpoint if it is nearer than an old one
1736 // setup prev[xy]
1738 begin
1739 // horizontal trace
1743 begin
1744 // going left
1748 end
1749 else
1750 begin
1751 // going right
1756 end
1757 else
1758 begin
1759 // vertical trace
1763 begin
1764 // going up
1768 end
1769 else
1770 begin
1771 // going down
1778 begin
1780 begin
1785 exit;
1787 end
1788 else
1789 begin
1791 {$IF DEFINED(D2F_DEBUG)}
1792 if dbgShowTraceLog then e_LogWritefln(' hhit(%d): a=(%d,%d), h=(%d,%d), p=(%d,%d), distsq=%d; lastsq=%d', [cc.bodies[f], ax0, ay0, x, y, prevx, prevy, distSq, lastDistSq]);
1793 {$ENDIF}
1795 begin
1805 // next cell
1809 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1811 // skip to next tile
1813 begin
1815 begin
1816 // to the right
1818 {$IF DEFINED(D2F_DEBUG)}
1820 {$ENDIF}
1824 end
1825 else
1826 begin
1827 // to the left
1829 {$IF DEFINED(D2F_DEBUG)}
1831 {$ENDIF}
1836 end
1837 else
1838 begin
1840 begin
1841 // to the down
1843 {$IF DEFINED(D2F_DEBUG)}
1845 {$ENDIF}
1849 end
1850 else
1851 begin
1852 // to the up
1854 {$IF DEFINED(D2F_DEBUG)}
1856 {$ENDIF}
1864 // we can travel less than one cell
1867 exit;
1869 {$ENDIF}
1871 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1872 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1873 {$ENDIF}
1875 //e_LogWritefln('*********************', []);
1877 // can omit checks
1879 begin
1880 // check cell(s)
1881 {$IF DEFINED(D2F_DEBUG)}
1882 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1883 {$ENDIF}
1884 // new tile?
1886 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1887 if assigned(dbgRayTraceTileHitCB) then e_WriteLog(Format(' xd=%d; term=%d; gx=%d; gy=%d; ga=%d; lastga=%d', [xd, term, xptr^, yptr^, ga, lastGA]), MSG_NOTIFY);
1888 {$ENDIF}
1890 begin
1891 // yes
1892 {$IF DEFINED(D2F_DEBUG)}
1893 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1894 {$ENDIF}
1896 begin
1897 // signal cell completion
1899 begin
1900 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1901 end
1903 begin
1906 exit;
1912 // has something to process in this tile?
1914 begin
1915 // process cell
1917 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1918 // convert coords to map (to avoid ajdusting coords inside the loop)
1921 // process cell list
1923 begin
1926 begin
1931 begin
1932 // can we process this proxy?
1934 begin
1937 begin
1939 begin
1944 exit;
1946 end
1947 else
1948 begin
1949 // remember this hitpoint if it is nearer than an old one
1951 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1952 if assigned(dbgRayTraceTileHitCB) then e_WriteLog(Format(' hit(%d): a=(%d,%d), h=(%d,%d), p=(%d,%d); distsq=%d; lastsq=%d', [cc.bodies[f], ax0, ay0, x, y, prevx, prevy, distSq, lastDistSq]), MSG_NOTIFY);
1953 {$ENDIF}
1955 begin
1963 end
1964 else
1965 begin
1966 // this is possibly interesting proxy, set "has more to check" flag
1971 // next cell
1974 // still has something interesting in this cell?
1976 begin
1977 // nope, don't process this cell anymore; signal cell completion
1980 begin
1982 end
1984 begin
1987 exit;
1992 begin
1993 // move to cell edge, as we have nothing to trace here anymore
1996 //e_LogWritefln('0: swapped=%d; xd=%d; yd=%d; stx=%d; sty=%d; e=%d; dx2=%d; dy2=%d; term=%d; xdist=%d; ydist=%d', [swapped, xd, yd, stx, sty, e, dx2, dy2, term, xdist, ydist]);
1998 begin
1999 // step
2002 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2005 //e_LogWritefln('1: swapped=%d; xd=%d; yd=%d; stx=%d; sty=%d; e=%d; dx2=%d; dy2=%d; term=%d; xdist=%d; ydist=%d', [swapped, xd, yd, stx, sty, e, dx2, dy2, term, xdist, ydist]);
2008 //putPixel(xptr^, yptr^);
2009 // move coords
2015 // we can travel less than one cell
2017 begin
2019 end
2020 else
2021 begin
2030 // ////////////////////////////////////////////////////////////////////////// //
2031 //FIXME! optimize this with real tile walking
2032 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2033 const
2035 var
2056 //swapped: Boolean = false; // true: xd is yd, and vice versa
2057 // horizontal walker
2058 {$IFDEF GRID_USE_ORTHO_ACCEL}
2060 //wksign: Integer;
2062 {$ENDIF}
2063 // skipper
2065 begin
2072 begin
2074 exit;
2089 // offset query coords to (0,0)-based
2095 // clip rectange
2101 // horizontal setup
2103 begin
2104 // from left to right
2107 end
2108 else
2109 begin
2110 // from right to left
2120 // vertical setup
2122 begin
2123 // from top to bottom
2126 end
2127 else
2128 begin
2129 // from bottom to top
2143 begin
2144 //swapped := true;
2153 end
2154 else
2155 begin
2169 begin
2170 // clip at top
2176 begin
2185 begin
2186 // clip at left
2197 begin
2198 // clip at bottom
2208 //if (term = xd) then exit; // this is the only point, get out of here
2214 // first move, to skip starting point
2215 // DON'T DO THIS! loop will take care of that
2217 begin
2219 exit;
2222 (*
2223 // move coords
2224 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2225 xd += stx;
2226 // done?
2227 if (xd = term) then exit;
2228 *)
2230 {$IF DEFINED(D2F_DEBUG)}
2231 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2232 {$ENDIF}
2233 // DON'T DO THIS! loop will take care of that
2234 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2235 //ccidx := mGrid[lastGA];
2240 // increase query counter
2243 begin
2244 // just in case of overflow
2250 {$IFDEF GRID_USE_ORTHO_ACCEL}
2251 // if this is strict horizontal/vertical trace, use optimized codepath
2253 begin
2254 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2255 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2256 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2257 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2259 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2260 {$IF DEFINED(D2F_DEBUG)}
2262 {$ENDIF}
2265 begin
2266 {$IF DEFINED(D2F_DEBUG)}
2267 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2268 {$ENDIF}
2269 // new tile?
2271 begin
2274 // convert coords to map (to avoid ajdusting coords inside the loop)
2276 begin
2279 begin
2284 begin
2287 begin
2289 end
2290 else
2291 begin
2294 exit;
2298 // next cell
2302 // skip to next tile
2304 begin
2306 begin
2307 // to the right
2309 {$IF DEFINED(D2F_DEBUG)}
2311 {$ENDIF}
2315 end
2316 else
2317 begin
2318 // to the left
2320 {$IF DEFINED(D2F_DEBUG)}
2322 {$ENDIF}
2327 end
2328 else
2329 begin
2331 begin
2332 // to the down
2334 {$IF DEFINED(D2F_DEBUG)}
2336 {$ENDIF}
2340 end
2341 else
2342 begin
2343 // to the up
2345 {$IF DEFINED(D2F_DEBUG)}
2347 {$ENDIF}
2356 exit;
2358 {$ENDIF}
2360 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2361 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2362 {$ENDIF}
2365 // can omit checks
2367 begin
2368 // check cell(s)
2369 {$IF DEFINED(D2F_DEBUG)}
2370 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2371 {$ENDIF}
2372 // new tile?
2374 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2375 if assigned(dbgRayTraceTileHitCB) then e_WriteLog(Format(' xd=%d; term=%d; gx=%d; gy=%d; ga=%d; lastga=%d', [xd, term, xptr^, yptr^, ga, lastGA]), MSG_NOTIFY);
2376 {$ENDIF}
2378 begin
2379 // yes
2380 {$IF DEFINED(D2F_DEBUG)}
2381 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2382 {$ENDIF}
2386 // has something to process in this tile?
2388 begin
2389 // process cell
2391 // process cell list
2393 begin
2396 begin
2401 begin
2404 begin
2406 end
2407 else
2408 begin
2411 exit;
2415 // next cell
2418 // nothing more interesting in this cell
2421 // move to cell edge, as we have nothing to trace here anymore
2424 //e_LogWritefln('0: swapped=%d; xd=%d; yd=%d; stx=%d; sty=%d; e=%d; dx2=%d; dy2=%d; term=%d; xdist=%d; ydist=%d', [swapped, xd, yd, stx, sty, e, dx2, dy2, term, xdist, ydist]);
2426 begin
2427 // step
2430 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2433 //e_LogWritefln('1: swapped=%d; xd=%d; yd=%d; stx=%d; sty=%d; e=%d; dx2=%d; dy2=%d; term=%d; xdist=%d; ydist=%d', [swapped, xd, yd, stx, sty, e, dx2, dy2, term, xdist, ydist]);
2435 //putPixel(xptr^, yptr^);
2436 // move coords
2445 {.$DEFINE D2F_DEBUG_OTR}
2446 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2447 var
2458 {$IF DEFINED(D2F_DEBUG_OTR)}
2460 {$ENDIF}
2461 begin
2475 // offset query coords to (0,0)-based
2482 begin
2484 // vertical
2486 begin
2487 // down
2489 //if (ay0 < 0) then ay0 := 0;
2493 end
2494 else
2495 begin
2496 // up
2498 //if (ay1 < 0) then ay1 := 0;
2503 // check tile
2505 begin
2511 begin
2514 begin
2520 begin
2521 // bound c0 and c1 to cell
2524 // fill the thing
2525 {$IF DEFINED(D2F_DEBUG_OTR)}
2526 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)]);
2527 {$ENDIF}
2528 //assert(c0 <= c1);
2532 // next cell
2535 {$IF DEFINED(D2F_DEBUG_OTR)}
2536 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2540 {$ENDIF}
2541 // now go till we hit cell boundary or empty space
2543 begin
2544 // up
2546 begin
2547 {$IF DEFINED(D2F_DEBUG_OTR)}
2548 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2549 {$ENDIF}
2553 {$IF DEFINED(D2F_DEBUG_OTR)}
2554 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2555 {$ENDIF}
2557 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2558 end
2559 else
2560 begin
2561 // down
2567 end
2568 else
2569 begin
2570 // horizontal