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 // `true`: endpoint will point at the last "inside" pixel
203 // `false`: endpoint will be (ax1, ay1)
204 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
206 //WARNING: don't modify grid while any query is in progress (no checks are made!)
207 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
208 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
209 //WARNING: don't change tags in callbacks here!
210 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
212 // debug
217 public
218 //WARNING! no sanity checks!
230 // you are not supposed to understand this
231 // returns `true` if there is an intersection, and enter coords
232 // enter coords will be equal to (x0, y0) if starting point is inside the box
233 // if result is `false`, `inx` and `iny` are undefined
234 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
243 implementation
245 uses
249 // ////////////////////////////////////////////////////////////////////////// //
250 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
251 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
252 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
254 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
257 // ////////////////////////////////////////////////////////////////////////// //
258 // you are not supposed to understand this
259 // returns `true` if there is an intersection, and enter coords
260 // enter coords will be equal to (x0, y0) if starting point is inside the box
261 // if result is `false`, `inx` and `iny` are undefined
262 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
263 var
271 //!term: Integer;
275 begin
277 // why not
283 begin
284 // check this point
286 exit;
289 // check if staring point is inside the box
290 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
292 // clip rectange
298 // horizontal setup
300 begin
301 // from left to right
304 end
305 else
306 begin
307 // from right to left
317 // vertical setup
319 begin
320 // from top to bottom
323 end
324 else
325 begin
326 // from bottom to top
340 begin
349 end
350 else
351 begin
361 //!term := x1;
365 begin
366 // clip at top
372 begin
381 begin
382 // clip at left
392 (*
393 if (y1 > wy1) then
394 begin
395 // clip at bottom
396 temp := dx2*(wy1-y0)+dsx;
397 term := x0+temp div dy2;
398 rem := temp mod dy2;
399 if (rem = 0) then Dec(term);
400 end;
402 if (term > wx1) then term := wx1; // clip at right
404 Inc(term); // draw last point
405 //if (term = xd) then exit; // this is the only point, get out of here
406 *)
410 //!dx2 -= dy2;
418 // ////////////////////////////////////////////////////////////////////////// //
419 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
420 begin
433 begin
438 begin
443 begin
448 begin
453 begin
458 begin
463 // ////////////////////////////////////////////////////////////////////////// //
464 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
465 begin
474 begin
476 begin
478 begin
482 exit;
492 begin
497 // ////////////////////////////////////////////////////////////////////////// //
498 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
499 var
501 begin
503 {$IF DEFINED(D2F_DEBUG)}
505 {$ENDIF}
506 {
507 if aTileSize < 1 then aTileSize := 1;
508 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
509 mTileSize := aTileSize;
510 }
521 // init free list
523 begin
529 // init grid
531 // init proxies
539 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
544 begin
552 // ////////////////////////////////////////////////////////////////////////// //
554 var
556 begin
559 begin
563 begin
569 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);
574 var
577 begin
580 begin
583 begin
586 begin
588 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
590 // next cell
598 var
601 begin
609 begin
612 begin
614 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
616 // next cell
622 // ////////////////////////////////////////////////////////////////////////// //
623 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
624 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
628 begin
629 // fix coords
637 begin
639 begin
642 end
643 else
644 begin
653 begin
655 begin
658 end
659 else
660 begin
668 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
669 begin
671 begin
674 end
675 else
676 begin
687 // ////////////////////////////////////////////////////////////////////////// //
689 begin
690 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
695 begin
697 begin
699 begin
701 end
702 else
703 begin
711 begin
716 // ////////////////////////////////////////////////////////////////////////// //
718 var
721 begin
723 begin
724 // no free cells, want more
728 begin
740 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
745 begin
747 begin
749 begin
760 // ////////////////////////////////////////////////////////////////////////// //
761 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
762 var
765 begin
767 begin
768 // no free proxies, resize list
775 // get one from list
780 // add to used list
782 // statistics
788 begin
790 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
791 // add to free list
799 // ////////////////////////////////////////////////////////////////////////// //
800 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
801 const
803 var
806 begin
809 // fix coords
812 // go on
816 //tsize := mTileSize;
819 begin
823 begin
833 // ////////////////////////////////////////////////////////////////////////// //
835 var
840 begin
842 // add body to the given grid cell
845 begin
846 {$IF DEFINED(D2F_DEBUG)}
849 begin
852 begin
854 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
858 {$ENDIF}
861 begin
863 // check "has room" flag
865 begin
866 // can add here
868 begin
870 begin
873 exit;
878 // no room, go to next cell in list (if there is any)
881 // no room in cells, add new cell to list
883 // either no room, or no cell at all
893 var
895 begin
902 // assume that we cannot have one object added to bucket twice
904 var
908 begin
910 // find and remove cell
914 begin
917 begin
919 begin
920 // i found her!
922 begin
923 // this cell contains no elements, remove it
926 exit;
928 // remove element from bucket
930 begin
935 exit;
944 var
946 begin
953 // ////////////////////////////////////////////////////////////////////////// //
954 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
955 begin
963 begin
970 // ////////////////////////////////////////////////////////////////////////// //
972 var
975 begin
982 {$IF DEFINED(D2F_DEBUG_MOVER)}
983 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);
984 {$ENDIF}
986 // map -> grid
991 // did any corner crossed tile boundary?
996 begin
1003 end
1004 else
1005 begin
1013 //TODO: optimize for horizontal/vertical moves
1015 var
1023 begin
1025 // check if tile coords was changed
1030 // map -> grid
1035 // check for heavy work
1046 {$IF DEFINED(D2F_DEBUG_MOVER)}
1047 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);
1048 {$ENDIF}
1050 begin
1051 // crossed tile boundary, do heavy work
1054 // cycle with old rect, remove body where it is necessary
1055 // optimized for horizontal moves
1056 {$IF DEFINED(D2F_DEBUG_MOVER)}
1057 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);
1058 {$ENDIF}
1059 // remove stale marks
1062 begin
1067 {$IF DEFINED(D2F_DEBUG_MOVER)}
1069 {$ENDIF}
1071 begin
1073 begin
1074 // this column is completely outside of new rect
1076 begin
1077 {$IF DEFINED(D2F_DEBUG_MOVER)}
1079 {$ENDIF}
1082 end
1083 else
1084 begin
1085 // heavy checks
1087 begin
1089 begin
1090 {$IF DEFINED(D2F_DEBUG_MOVER)}
1092 {$ENDIF}
1099 // cycle with new rect, add body where it is necessary
1102 begin
1107 {$IF DEFINED(D2F_DEBUG_MOVER)}
1109 {$ENDIF}
1111 begin
1113 begin
1114 // this column is completely outside of old rect
1116 begin
1117 {$IF DEFINED(D2F_DEBUG_MOVER)}
1119 {$ENDIF}
1122 end
1123 else
1124 begin
1125 // heavy checks
1127 begin
1129 begin
1130 {$IF DEFINED(D2F_DEBUG_MOVER)}
1132 {$ENDIF}
1139 // done
1140 end
1141 else
1142 begin
1143 {$IF DEFINED(D2F_DEBUG_MOVER)}
1144 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);
1145 {$ENDIF}
1147 // update coordinates
1153 var
1156 begin
1158 // check if tile coords was changed
1164 {$IF DEFINED(D2F_DEBUG_MOVER)}
1165 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);
1166 {$ENDIF}
1169 begin
1170 // crossed tile boundary, do heavy work
1175 end
1176 else
1177 begin
1178 // nothing to do with the grid, just fix size
1185 // ////////////////////////////////////////////////////////////////////////// //
1187 var
1189 begin
1192 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then cidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1197 // ////////////////////////////////////////////////////////////////////////// //
1198 // no callback: return `true` on the first hit
1199 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1200 var
1207 begin
1213 {$IF DEFINED(D2F_DEBUG_XXQ)}
1215 {$ENDIF}
1217 // make coords (0,0)-based
1224 {$IF DEFINED(D2F_DEBUG_XXQ)}
1225 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);
1226 {$ENDIF}
1228 // restore coords
1232 // increase query counter
1235 begin
1236 // just in case of overflow
1242 {$IF DEFINED(D2F_DEBUG_XXQ)}
1243 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1244 {$ENDIF}
1247 begin
1248 {$IF DEFINED(D2F_DEBUG_XXQ)}
1250 {$ENDIF}
1253 begin
1256 {$IF DEFINED(D2F_DEBUG_XXQ)}
1257 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);
1258 {$ENDIF}
1259 // shit. has to do it this way, so i can change tag in callback
1261 begin
1266 begin
1268 begin
1270 begin
1273 exit;
1275 end
1276 else
1277 begin
1280 exit;
1290 // ////////////////////////////////////////////////////////////////////////// //
1291 // no callback: return `true` on the first hit
1292 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1293 const
1295 var
1306 begin
1315 // fix coords
1320 //tsize := mTileSize;
1328 // increase query counter
1331 begin
1332 // just in case of overflow
1336 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1339 // go on
1341 begin
1345 begin
1348 // process cells
1351 begin
1354 begin
1357 // shit. has to do it this way, so i can change tag in callback
1366 begin
1368 end
1369 else
1370 begin
1373 exit;
1385 // ////////////////////////////////////////////////////////////////////////// //
1386 // no callback: return `true` on the nearest hit
1387 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1388 var
1390 begin
1395 // no callback: return `true` on the nearest hit
1396 // you are not supposed to understand this
1397 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1398 const
1400 var
1426 //swapped: Boolean = false; // true: xd is yd, and vice versa
1427 // horizontal walker
1428 {$IFDEF GRID_USE_ORTHO_ACCEL}
1430 //wksign: Integer;
1432 {$ENDIF}
1433 // skipper
1435 begin
1444 begin
1447 begin
1450 exit;
1462 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1463 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);
1464 {$ENDIF}
1471 // offset query coords to (0,0)-based
1477 // clip rectange
1483 // horizontal setup
1485 begin
1486 // from left to right
1489 end
1490 else
1491 begin
1492 // from right to left
1502 // vertical setup
1504 begin
1505 // from top to bottom
1508 end
1509 else
1510 begin
1511 // from bottom to top
1525 begin
1526 //swapped := true;
1535 end
1536 else
1537 begin
1551 begin
1552 // clip at top
1558 begin
1567 begin
1568 // clip at left
1579 begin
1580 // clip at bottom
1590 //if (term = xd) then exit; // this is the only point, get out of here
1596 // first move, to skip starting point
1597 // DON'T DO THIS! loop will take care of that
1599 begin
1600 //FIXME!
1603 begin
1605 begin
1607 begin
1610 end
1611 else
1612 begin
1615 end
1616 else
1617 begin
1622 exit;
1627 (*
1628 // move coords
1629 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1630 xd += stx;
1631 // done?
1632 if (xd = term) then exit;
1633 *)
1635 {$IF DEFINED(D2F_DEBUG)}
1636 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1637 {$ENDIF}
1638 // DON'T DO THIS! loop will take care of that
1639 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1640 //ccidx := mGrid[lastGA];
1642 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1643 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1644 {$ENDIF}
1646 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1651 // increase query counter
1654 begin
1655 // just in case of overflow
1661 {$IFDEF GRID_USE_ORTHO_ACCEL}
1662 // if this is strict horizontal/vertical trace, use optimized codepath
1664 begin
1665 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1666 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1667 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1668 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1670 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1671 {$IF DEFINED(D2F_DEBUG)}
1673 {$ENDIF}
1675 // one of those will never change
1679 begin
1680 {$IF DEFINED(D2F_DEBUG)}
1681 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1682 {$ENDIF}
1683 // new tile?
1685 begin
1688 // convert coords to map (to avoid ajdusting coords inside the loop)
1691 begin
1694 begin
1699 // constant coord should be inside
1702 begin
1704 // inside the proxy?
1707 begin
1708 // setup prev[xy]
1710 begin
1712 begin
1717 exit;
1719 end
1720 else
1721 begin
1723 {$IF DEFINED(D2F_DEBUG)}
1724 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]);
1725 {$ENDIF}
1727 begin
1732 exit;
1735 continue;
1737 // remember this hitpoint if it is nearer than an old one
1738 // setup prev[xy]
1740 begin
1741 // horizontal trace
1745 begin
1746 // going left
1750 end
1751 else
1752 begin
1753 // going right
1758 end
1759 else
1760 begin
1761 // vertical trace
1765 begin
1766 // going up
1770 end
1771 else
1772 begin
1773 // going down
1780 begin
1782 begin
1787 exit;
1789 end
1790 else
1791 begin
1793 {$IF DEFINED(D2F_DEBUG)}
1794 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]);
1795 {$ENDIF}
1797 begin
1807 // next cell
1811 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1813 // skip to next tile
1815 begin
1817 begin
1818 // to the right
1820 {$IF DEFINED(D2F_DEBUG)}
1822 {$ENDIF}
1826 end
1827 else
1828 begin
1829 // to the left
1831 {$IF DEFINED(D2F_DEBUG)}
1833 {$ENDIF}
1838 end
1839 else
1840 begin
1842 begin
1843 // to the down
1845 {$IF DEFINED(D2F_DEBUG)}
1847 {$ENDIF}
1851 end
1852 else
1853 begin
1854 // to the up
1856 {$IF DEFINED(D2F_DEBUG)}
1858 {$ENDIF}
1866 // we can travel less than one cell
1869 exit;
1871 {$ENDIF}
1873 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1874 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1875 {$ENDIF}
1877 //e_LogWritefln('*********************', []);
1879 // can omit checks
1881 begin
1882 // check cell(s)
1883 {$IF DEFINED(D2F_DEBUG)}
1884 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1885 {$ENDIF}
1886 // new tile?
1888 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1889 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);
1890 {$ENDIF}
1892 begin
1893 // yes
1894 {$IF DEFINED(D2F_DEBUG)}
1895 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1896 {$ENDIF}
1898 begin
1899 // signal cell completion
1901 begin
1902 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1903 end
1905 begin
1908 exit;
1914 // has something to process in this tile?
1916 begin
1917 // process cell
1919 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1920 // convert coords to map (to avoid ajdusting coords inside the loop)
1923 // process cell list
1925 begin
1928 begin
1933 begin
1934 // can we process this proxy?
1936 begin
1939 begin
1941 begin
1946 exit;
1948 end
1949 else
1950 begin
1951 // remember this hitpoint if it is nearer than an old one
1953 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1954 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);
1955 {$ENDIF}
1957 begin
1965 end
1966 else
1967 begin
1968 // this is possibly interesting proxy, set "has more to check" flag
1973 // next cell
1976 // still has something interesting in this cell?
1978 begin
1979 // nope, don't process this cell anymore; signal cell completion
1982 begin
1984 end
1986 begin
1989 exit;
1994 begin
1995 // move to cell edge, as we have nothing to trace here anymore
1998 //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]);
2000 begin
2001 // step
2004 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2007 //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]);
2010 //putPixel(xptr^, yptr^);
2011 // move coords
2017 // we can travel less than one cell
2019 begin
2021 end
2022 else
2023 begin
2032 // ////////////////////////////////////////////////////////////////////////// //
2033 //FIXME! optimize this with real tile walking
2034 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2035 const
2037 var
2058 //swapped: Boolean = false; // true: xd is yd, and vice versa
2059 // horizontal walker
2060 {$IFDEF GRID_USE_ORTHO_ACCEL}
2062 //wksign: Integer;
2064 {$ENDIF}
2065 // skipper
2067 begin
2074 begin
2076 exit;
2091 // offset query coords to (0,0)-based
2097 // clip rectange
2103 // horizontal setup
2105 begin
2106 // from left to right
2109 end
2110 else
2111 begin
2112 // from right to left
2122 // vertical setup
2124 begin
2125 // from top to bottom
2128 end
2129 else
2130 begin
2131 // from bottom to top
2145 begin
2146 //swapped := true;
2155 end
2156 else
2157 begin
2171 begin
2172 // clip at top
2178 begin
2187 begin
2188 // clip at left
2199 begin
2200 // clip at bottom
2210 //if (term = xd) then exit; // this is the only point, get out of here
2216 // first move, to skip starting point
2217 // DON'T DO THIS! loop will take care of that
2219 begin
2221 exit;
2224 (*
2225 // move coords
2226 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2227 xd += stx;
2228 // done?
2229 if (xd = term) then exit;
2230 *)
2232 {$IF DEFINED(D2F_DEBUG)}
2233 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2234 {$ENDIF}
2235 // DON'T DO THIS! loop will take care of that
2236 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2237 //ccidx := mGrid[lastGA];
2242 // increase query counter
2245 begin
2246 // just in case of overflow
2252 {$IFDEF GRID_USE_ORTHO_ACCEL}
2253 // if this is strict horizontal/vertical trace, use optimized codepath
2255 begin
2256 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2257 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2258 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2259 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2261 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2262 {$IF DEFINED(D2F_DEBUG)}
2264 {$ENDIF}
2267 begin
2268 {$IF DEFINED(D2F_DEBUG)}
2269 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2270 {$ENDIF}
2271 // new tile?
2273 begin
2276 // convert coords to map (to avoid ajdusting coords inside the loop)
2278 begin
2281 begin
2286 begin
2289 begin
2291 end
2292 else
2293 begin
2296 exit;
2300 // next cell
2304 // skip to next tile
2306 begin
2308 begin
2309 // to the right
2311 {$IF DEFINED(D2F_DEBUG)}
2313 {$ENDIF}
2317 end
2318 else
2319 begin
2320 // to the left
2322 {$IF DEFINED(D2F_DEBUG)}
2324 {$ENDIF}
2329 end
2330 else
2331 begin
2333 begin
2334 // to the down
2336 {$IF DEFINED(D2F_DEBUG)}
2338 {$ENDIF}
2342 end
2343 else
2344 begin
2345 // to the up
2347 {$IF DEFINED(D2F_DEBUG)}
2349 {$ENDIF}
2358 exit;
2360 {$ENDIF}
2362 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2363 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2364 {$ENDIF}
2367 // can omit checks
2369 begin
2370 // check cell(s)
2371 {$IF DEFINED(D2F_DEBUG)}
2372 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2373 {$ENDIF}
2374 // new tile?
2376 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2377 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);
2378 {$ENDIF}
2380 begin
2381 // yes
2382 {$IF DEFINED(D2F_DEBUG)}
2383 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2384 {$ENDIF}
2388 // has something to process in this tile?
2390 begin
2391 // process cell
2393 // process cell list
2395 begin
2398 begin
2403 begin
2406 begin
2408 end
2409 else
2410 begin
2413 exit;
2417 // next cell
2420 // nothing more interesting in this cell
2423 // move to cell edge, as we have nothing to trace here anymore
2426 //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]);
2428 begin
2429 // step
2432 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2435 //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]);
2437 //putPixel(xptr^, yptr^);
2438 // move coords
2447 {.$DEFINE D2F_DEBUG_OTR}
2448 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2449 var
2460 {$IF DEFINED(D2F_DEBUG_OTR)}
2462 {$ENDIF}
2463 begin
2477 // offset query coords to (0,0)-based
2484 begin
2486 // vertical
2488 begin
2489 // down
2491 //if (ay0 < 0) then ay0 := 0;
2495 end
2496 else
2497 begin
2498 // up
2500 //if (ay1 < 0) then ay1 := 0;
2505 // check tile
2507 begin
2513 begin
2516 begin
2522 begin
2523 // bound c0 and c1 to cell
2526 // fill the thing
2527 {$IF DEFINED(D2F_DEBUG_OTR)}
2528 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)]);
2529 {$ENDIF}
2530 //assert(c0 <= c1);
2534 // next cell
2537 {$IF DEFINED(D2F_DEBUG_OTR)}
2538 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2542 {$ENDIF}
2543 // now go till we hit cell boundary or empty space
2545 begin
2546 // up
2548 begin
2549 {$IF DEFINED(D2F_DEBUG_OTR)}
2550 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2551 {$ENDIF}
2555 {$IF DEFINED(D2F_DEBUG_OTR)}
2556 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2557 {$ENDIF}
2559 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2560 end
2561 else
2562 begin
2563 // down
2569 end
2570 else
2571 begin
2572 // horizontal