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 //function traceOrthoRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload;
201 //function traceOrthoRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
203 //WARNING: don't modify grid while any query is in progress (no checks are made!)
204 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
205 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
206 //WARNING: don't change tags in callbacks here!
207 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
209 // debug
214 public
215 //WARNING! no sanity checks!
227 // you are not supposed to understand this
228 // returns `true` if there is an intersection, and enter coords
229 // enter coords will be equal to (x0, y0) if starting point is inside the box
230 // if result is `false`, `inx` and `iny` are undefined
231 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
240 implementation
242 uses
246 // ////////////////////////////////////////////////////////////////////////// //
247 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
248 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
249 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
251 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
254 // ////////////////////////////////////////////////////////////////////////// //
255 // you are not supposed to understand this
256 // returns `true` if there is an intersection, and enter coords
257 // enter coords will be equal to (x0, y0) if starting point is inside the box
258 // if result is `false`, `inx` and `iny` are undefined
259 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
260 var
268 //!term: Integer;
272 begin
274 // why not
280 begin
281 // check this point
283 exit;
286 // check if staring point is inside the box
287 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
289 // clip rectange
295 // horizontal setup
297 begin
298 // from left to right
301 end
302 else
303 begin
304 // from right to left
314 // vertical setup
316 begin
317 // from top to bottom
320 end
321 else
322 begin
323 // from bottom to top
337 begin
346 end
347 else
348 begin
358 //!term := x1;
362 begin
363 // clip at top
369 begin
378 begin
379 // clip at left
389 (*
390 if (y1 > wy1) then
391 begin
392 // clip at bottom
393 temp := dx2*(wy1-y0)+dsx;
394 term := x0+temp div dy2;
395 rem := temp mod dy2;
396 if (rem = 0) then Dec(term);
397 end;
399 if (term > wx1) then term := wx1; // clip at right
401 Inc(term); // draw last point
402 //if (term = xd) then exit; // this is the only point, get out of here
403 *)
407 //!dx2 -= dy2;
415 // ////////////////////////////////////////////////////////////////////////// //
416 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
417 begin
430 begin
435 begin
440 begin
445 begin
450 begin
455 begin
460 // ////////////////////////////////////////////////////////////////////////// //
461 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
462 begin
471 begin
473 begin
475 begin
479 exit;
489 begin
494 // ////////////////////////////////////////////////////////////////////////// //
495 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
496 var
498 begin
500 {$IF DEFINED(D2F_DEBUG)}
502 {$ENDIF}
503 {
504 if aTileSize < 1 then aTileSize := 1;
505 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
506 mTileSize := aTileSize;
507 }
518 // init free list
520 begin
526 // init grid
528 // init proxies
536 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
541 begin
549 // ////////////////////////////////////////////////////////////////////////// //
551 var
553 begin
556 begin
560 begin
566 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);
571 var
574 begin
577 begin
580 begin
583 begin
585 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
587 // next cell
595 var
598 begin
606 begin
609 begin
611 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
613 // next cell
619 // ////////////////////////////////////////////////////////////////////////// //
620 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
621 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
625 begin
626 // fix coords
634 begin
636 begin
639 end
640 else
641 begin
650 begin
652 begin
655 end
656 else
657 begin
665 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
666 begin
668 begin
671 end
672 else
673 begin
684 // ////////////////////////////////////////////////////////////////////////// //
686 begin
692 begin
694 begin
696 begin
698 end
699 else
700 begin
708 begin
713 // ////////////////////////////////////////////////////////////////////////// //
715 var
718 begin
720 begin
721 // no free cells, want more
725 begin
737 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
742 begin
744 begin
746 begin
757 // ////////////////////////////////////////////////////////////////////////// //
758 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
759 var
762 begin
764 begin
765 // no free proxies, resize list
772 // get one from list
777 // add to used list
779 // statistics
785 begin
787 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
788 // add to free list
796 // ////////////////////////////////////////////////////////////////////////// //
797 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
798 const
800 var
803 begin
806 // fix coords
809 // go on
813 //tsize := mTileSize;
816 begin
820 begin
830 // ////////////////////////////////////////////////////////////////////////// //
832 var
837 begin
839 // add body to the given grid cell
842 begin
843 {$IF DEFINED(D2F_DEBUG)}
846 begin
849 begin
851 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
855 {$ENDIF}
858 begin
860 // check "has room" flag
862 begin
863 // can add here
865 begin
867 begin
870 exit;
875 // no room, go to next cell in list (if there is any)
878 // no room in cells, add new cell to list
880 // either no room, or no cell at all
890 var
892 begin
899 // assume that we cannot have one object added to bucket twice
901 var
905 begin
907 // find and remove cell
911 begin
914 begin
916 begin
917 // i found her!
919 begin
920 // this cell contains no elements, remove it
923 exit;
925 // remove element from bucket
927 begin
932 exit;
941 var
943 begin
950 // ////////////////////////////////////////////////////////////////////////// //
951 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
952 begin
960 begin
967 // ////////////////////////////////////////////////////////////////////////// //
969 var
972 begin
979 {$IF DEFINED(D2F_DEBUG_MOVER)}
980 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);
981 {$ENDIF}
983 // map -> grid
988 // did any corner crossed tile boundary?
993 begin
1000 end
1001 else
1002 begin
1010 //TODO: optimize for horizontal/vertical moves
1012 var
1020 begin
1022 // check if tile coords was changed
1027 // map -> grid
1032 // check for heavy work
1043 {$IF DEFINED(D2F_DEBUG_MOVER)}
1044 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);
1045 {$ENDIF}
1047 begin
1048 // crossed tile boundary, do heavy work
1051 // cycle with old rect, remove body where it is necessary
1052 // optimized for horizontal moves
1053 {$IF DEFINED(D2F_DEBUG_MOVER)}
1054 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);
1055 {$ENDIF}
1056 // remove stale marks
1059 begin
1064 {$IF DEFINED(D2F_DEBUG_MOVER)}
1066 {$ENDIF}
1068 begin
1070 begin
1071 // this column is completely outside of new rect
1073 begin
1074 {$IF DEFINED(D2F_DEBUG_MOVER)}
1076 {$ENDIF}
1079 end
1080 else
1081 begin
1082 // heavy checks
1084 begin
1086 begin
1087 {$IF DEFINED(D2F_DEBUG_MOVER)}
1089 {$ENDIF}
1096 // cycle with new rect, add body where it is necessary
1099 begin
1104 {$IF DEFINED(D2F_DEBUG_MOVER)}
1106 {$ENDIF}
1108 begin
1110 begin
1111 // this column is completely outside of old rect
1113 begin
1114 {$IF DEFINED(D2F_DEBUG_MOVER)}
1116 {$ENDIF}
1119 end
1120 else
1121 begin
1122 // heavy checks
1124 begin
1126 begin
1127 {$IF DEFINED(D2F_DEBUG_MOVER)}
1129 {$ENDIF}
1136 // done
1137 end
1138 else
1139 begin
1140 {$IF DEFINED(D2F_DEBUG_MOVER)}
1141 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);
1142 {$ENDIF}
1144 // update coordinates
1150 var
1153 begin
1155 // check if tile coords was changed
1161 {$IF DEFINED(D2F_DEBUG_MOVER)}
1162 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);
1163 {$ENDIF}
1166 begin
1167 // crossed tile boundary, do heavy work
1172 end
1173 else
1174 begin
1175 // nothing to do with the grid, just fix size
1182 // ////////////////////////////////////////////////////////////////////////// //
1184 var
1186 begin
1189 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then cidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1194 // ////////////////////////////////////////////////////////////////////////// //
1195 // no callback: return `true` on the first hit
1196 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1197 var
1204 begin
1210 {$IF DEFINED(D2F_DEBUG_XXQ)}
1212 {$ENDIF}
1214 // make coords (0,0)-based
1221 {$IF DEFINED(D2F_DEBUG_XXQ)}
1222 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);
1223 {$ENDIF}
1225 // restore coords
1229 // increase query counter
1232 begin
1233 // just in case of overflow
1239 {$IF DEFINED(D2F_DEBUG_XXQ)}
1240 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1241 {$ENDIF}
1244 begin
1245 {$IF DEFINED(D2F_DEBUG_XXQ)}
1247 {$ENDIF}
1250 begin
1253 {$IF DEFINED(D2F_DEBUG_XXQ)}
1254 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);
1255 {$ENDIF}
1256 // shit. has to do it this way, so i can change tag in callback
1258 begin
1263 begin
1265 begin
1267 begin
1270 exit;
1272 end
1273 else
1274 begin
1277 exit;
1287 // ////////////////////////////////////////////////////////////////////////// //
1288 // no callback: return `true` on the first hit
1289 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1290 const
1292 var
1303 begin
1312 // fix coords
1317 //tsize := mTileSize;
1325 // increase query counter
1328 begin
1329 // just in case of overflow
1333 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1336 // go on
1338 begin
1342 begin
1345 // process cells
1348 begin
1351 begin
1354 // shit. has to do it this way, so i can change tag in callback
1363 begin
1365 end
1366 else
1367 begin
1370 exit;
1382 // ////////////////////////////////////////////////////////////////////////// //
1383 // no callback: return `true` on the nearest hit
1384 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1385 var
1387 begin
1392 // no callback: return `true` on the nearest hit
1393 // you are not supposed to understand this
1394 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1395 const
1397 var
1423 //swapped: Boolean = false; // true: xd is yd, and vice versa
1424 // horizontal walker
1425 {$IFDEF GRID_USE_ORTHO_ACCEL}
1427 //wksign: Integer;
1429 {$ENDIF}
1430 // skipper
1432 begin
1441 begin
1444 begin
1447 exit;
1459 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1460 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);
1461 {$ENDIF}
1468 // offset query coords to (0,0)-based
1474 // clip rectange
1480 // horizontal setup
1482 begin
1483 // from left to right
1486 end
1487 else
1488 begin
1489 // from right to left
1499 // vertical setup
1501 begin
1502 // from top to bottom
1505 end
1506 else
1507 begin
1508 // from bottom to top
1522 begin
1523 //swapped := true;
1532 end
1533 else
1534 begin
1548 begin
1549 // clip at top
1555 begin
1564 begin
1565 // clip at left
1576 begin
1577 // clip at bottom
1587 //if (term = xd) then exit; // this is the only point, get out of here
1593 // first move, to skip starting point
1594 // DON'T DO THIS! loop will take care of that
1596 begin
1597 //FIXME!
1600 begin
1602 begin
1604 begin
1607 end
1608 else
1609 begin
1612 end
1613 else
1614 begin
1619 exit;
1624 (*
1625 // move coords
1626 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1627 xd += stx;
1628 // done?
1629 if (xd = term) then exit;
1630 *)
1632 {$IF DEFINED(D2F_DEBUG)}
1633 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1634 {$ENDIF}
1635 // DON'T DO THIS! loop will take care of that
1636 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1637 //ccidx := mGrid[lastGA];
1639 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1640 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1641 {$ENDIF}
1643 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1648 // increase query counter
1651 begin
1652 // just in case of overflow
1658 {$IFDEF GRID_USE_ORTHO_ACCEL}
1659 // if this is strict horizontal/vertical trace, use optimized codepath
1661 begin
1662 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1663 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1664 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1665 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1667 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1668 {$IF DEFINED(D2F_DEBUG)}
1670 {$ENDIF}
1672 // one of those will never change
1676 begin
1677 {$IF DEFINED(D2F_DEBUG)}
1678 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1679 {$ENDIF}
1680 // new tile?
1682 begin
1685 // convert coords to map (to avoid ajdusting coords inside the loop)
1688 begin
1691 begin
1696 // constant coord should be inside
1699 begin
1701 // inside the proxy?
1704 begin
1705 // setup prev[xy]
1707 begin
1709 begin
1714 exit;
1716 end
1717 else
1718 begin
1720 {$IF DEFINED(D2F_DEBUG)}
1721 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]);
1722 {$ENDIF}
1724 begin
1729 exit;
1732 continue;
1734 // remember this hitpoint if it is nearer than an old one
1735 // setup prev[xy]
1737 begin
1738 // horizontal trace
1742 begin
1743 // going left
1747 end
1748 else
1749 begin
1750 // going right
1755 end
1756 else
1757 begin
1758 // vertical trace
1762 begin
1763 // going up
1767 end
1768 else
1769 begin
1770 // going down
1777 begin
1779 begin
1784 exit;
1786 end
1787 else
1788 begin
1790 {$IF DEFINED(D2F_DEBUG)}
1791 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]);
1792 {$ENDIF}
1794 begin
1804 // next cell
1808 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1810 // skip to next tile
1812 begin
1814 begin
1815 // to the right
1817 {$IF DEFINED(D2F_DEBUG)}
1819 {$ENDIF}
1823 end
1824 else
1825 begin
1826 // to the left
1828 {$IF DEFINED(D2F_DEBUG)}
1830 {$ENDIF}
1835 end
1836 else
1837 begin
1839 begin
1840 // to the down
1842 {$IF DEFINED(D2F_DEBUG)}
1844 {$ENDIF}
1848 end
1849 else
1850 begin
1851 // to the up
1853 {$IF DEFINED(D2F_DEBUG)}
1855 {$ENDIF}
1863 // we can travel less than one cell
1866 exit;
1868 {$ENDIF}
1870 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1871 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1872 {$ENDIF}
1874 //e_LogWritefln('*********************', []);
1876 // can omit checks
1878 begin
1879 // check cell(s)
1880 {$IF DEFINED(D2F_DEBUG)}
1881 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1882 {$ENDIF}
1883 // new tile?
1885 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1886 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);
1887 {$ENDIF}
1889 begin
1890 // yes
1891 {$IF DEFINED(D2F_DEBUG)}
1892 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1893 {$ENDIF}
1895 begin
1896 // signal cell completion
1898 begin
1899 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1900 end
1902 begin
1905 exit;
1911 // has something to process in this tile?
1913 begin
1914 // process cell
1916 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1917 // convert coords to map (to avoid ajdusting coords inside the loop)
1920 // process cell list
1922 begin
1925 begin
1930 begin
1931 // can we process this proxy?
1933 begin
1936 begin
1938 begin
1943 exit;
1945 end
1946 else
1947 begin
1948 // remember this hitpoint if it is nearer than an old one
1950 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1951 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);
1952 {$ENDIF}
1954 begin
1962 end
1963 else
1964 begin
1965 // this is possibly interesting proxy, set "has more to check" flag
1970 // next cell
1973 // still has something interesting in this cell?
1975 begin
1976 // nope, don't process this cell anymore; signal cell completion
1979 begin
1981 end
1983 begin
1986 exit;
1991 begin
1992 // move to cell edge, as we have nothing to trace here anymore
1995 //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]);
1997 begin
1998 // step
2001 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2004 //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]);
2007 //putPixel(xptr^, yptr^);
2008 // move coords
2014 // we can travel less than one cell
2016 begin
2018 end
2019 else
2020 begin
2029 // ////////////////////////////////////////////////////////////////////////// //
2030 //FIXME! optimize this with real tile walking
2031 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2032 const
2034 var
2055 //swapped: Boolean = false; // true: xd is yd, and vice versa
2056 // horizontal walker
2057 {$IFDEF GRID_USE_ORTHO_ACCEL}
2059 //wksign: Integer;
2061 {$ENDIF}
2062 // skipper
2064 begin
2071 begin
2073 exit;
2088 // offset query coords to (0,0)-based
2094 // clip rectange
2100 // horizontal setup
2102 begin
2103 // from left to right
2106 end
2107 else
2108 begin
2109 // from right to left
2119 // vertical setup
2121 begin
2122 // from top to bottom
2125 end
2126 else
2127 begin
2128 // from bottom to top
2142 begin
2143 //swapped := true;
2152 end
2153 else
2154 begin
2168 begin
2169 // clip at top
2175 begin
2184 begin
2185 // clip at left
2196 begin
2197 // clip at bottom
2207 //if (term = xd) then exit; // this is the only point, get out of here
2213 // first move, to skip starting point
2214 // DON'T DO THIS! loop will take care of that
2216 begin
2218 exit;
2221 (*
2222 // move coords
2223 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2224 xd += stx;
2225 // done?
2226 if (xd = term) then exit;
2227 *)
2229 {$IF DEFINED(D2F_DEBUG)}
2230 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2231 {$ENDIF}
2232 // DON'T DO THIS! loop will take care of that
2233 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2234 //ccidx := mGrid[lastGA];
2239 // increase query counter
2242 begin
2243 // just in case of overflow
2249 {$IFDEF GRID_USE_ORTHO_ACCEL}
2250 // if this is strict horizontal/vertical trace, use optimized codepath
2252 begin
2253 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2254 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2255 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2256 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2258 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2259 {$IF DEFINED(D2F_DEBUG)}
2261 {$ENDIF}
2264 begin
2265 {$IF DEFINED(D2F_DEBUG)}
2266 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2267 {$ENDIF}
2268 // new tile?
2270 begin
2273 // convert coords to map (to avoid ajdusting coords inside the loop)
2275 begin
2278 begin
2283 begin
2286 begin
2288 end
2289 else
2290 begin
2293 exit;
2297 // next cell
2301 // skip to next tile
2303 begin
2305 begin
2306 // to the right
2308 {$IF DEFINED(D2F_DEBUG)}
2310 {$ENDIF}
2314 end
2315 else
2316 begin
2317 // to the left
2319 {$IF DEFINED(D2F_DEBUG)}
2321 {$ENDIF}
2326 end
2327 else
2328 begin
2330 begin
2331 // to the down
2333 {$IF DEFINED(D2F_DEBUG)}
2335 {$ENDIF}
2339 end
2340 else
2341 begin
2342 // to the up
2344 {$IF DEFINED(D2F_DEBUG)}
2346 {$ENDIF}
2355 exit;
2357 {$ENDIF}
2359 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2360 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2361 {$ENDIF}
2364 // can omit checks
2366 begin
2367 // check cell(s)
2368 {$IF DEFINED(D2F_DEBUG)}
2369 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2370 {$ENDIF}
2371 // new tile?
2373 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2374 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);
2375 {$ENDIF}
2377 begin
2378 // yes
2379 {$IF DEFINED(D2F_DEBUG)}
2380 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2381 {$ENDIF}
2385 // has something to process in this tile?
2387 begin
2388 // process cell
2390 // process cell list
2392 begin
2395 begin
2400 begin
2403 begin
2405 end
2406 else
2407 begin
2410 exit;
2414 // next cell
2417 // nothing more interesting in this cell
2420 // move to cell edge, as we have nothing to trace here anymore
2423 //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]);
2425 begin
2426 // step
2429 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2432 //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]);
2434 //putPixel(xptr^, yptr^);
2435 // move coords