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 // trace box with the given velocity; return object hit (if any)
213 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
214 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
216 // debug
221 public
222 //WARNING! no sanity checks!
234 // you are not supposed to understand this
235 // returns `true` if there is an intersection, and enter coords
236 // enter coords will be equal to (x0, y0) if starting point is inside the box
237 // if result is `false`, `inx` and `iny` are undefined
238 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
240 // sweep two AABB's to see if and when they are overlapping
241 // returns `true` if collision was detected (but boxes doesn't overlap)
242 // u1 and u1 has no sense if no collision was detected
243 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
244 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
245 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
246 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
247 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
257 implementation
259 uses
263 // ////////////////////////////////////////////////////////////////////////// //
264 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
265 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
266 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
268 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
271 // ////////////////////////////////////////////////////////////////////////// //
272 // you are not supposed to understand this
273 // returns `true` if there is an intersection, and enter coords
274 // enter coords will be equal to (x0, y0) if starting point is inside the box
275 // if result is `false`, `inx` and `iny` are undefined
276 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
277 var
285 //!term: Integer;
289 begin
291 // why not
297 begin
298 // check this point
300 exit;
303 // check if staring point is inside the box
304 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
306 // clip rectange
312 // horizontal setup
314 begin
315 // from left to right
318 end
319 else
320 begin
321 // from right to left
331 // vertical setup
333 begin
334 // from top to bottom
337 end
338 else
339 begin
340 // from bottom to top
354 begin
363 end
364 else
365 begin
375 //!term := x1;
379 begin
380 // clip at top
386 begin
395 begin
396 // clip at left
406 (*
407 if (y1 > wy1) then
408 begin
409 // clip at bottom
410 temp := dx2*(wy1-y0)+dsx;
411 term := x0+temp div dy2;
412 rem := temp mod dy2;
413 if (rem = 0) then Dec(term);
414 end;
416 if (term > wx1) then term := wx1; // clip at right
418 Inc(term); // draw last point
419 //if (term = xd) then exit; // this is the only point, get out of here
420 *)
424 //!dx2 -= dy2;
432 // ////////////////////////////////////////////////////////////////////////// //
433 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
435 var
439 var
441 begin
445 begin
449 end
451 begin
458 begin
461 end
463 begin
471 var
474 begin
487 // check if they are overlapping right now (SAT)
488 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
492 // treat b as stationary, so invert v to get relative velocity
506 begin
512 // ////////////////////////////////////////////////////////////////////////// //
513 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
514 begin
527 begin
532 begin
537 begin
542 begin
547 begin
552 begin
557 // ////////////////////////////////////////////////////////////////////////// //
558 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
559 begin
568 begin
570 begin
572 begin
576 exit;
586 begin
591 // ////////////////////////////////////////////////////////////////////////// //
592 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
593 var
595 begin
597 {$IF DEFINED(D2F_DEBUG)}
599 {$ENDIF}
600 {
601 if aTileSize < 1 then aTileSize := 1;
602 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
603 mTileSize := aTileSize;
604 }
615 // init free list
617 begin
623 // init grid
625 // init proxies
633 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
638 begin
646 // ////////////////////////////////////////////////////////////////////////// //
648 var
650 begin
653 begin
657 begin
663 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);
668 var
671 begin
674 begin
677 begin
680 begin
682 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
684 // next cell
692 var
695 begin
703 begin
706 begin
708 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
710 // next cell
716 // ////////////////////////////////////////////////////////////////////////// //
717 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
718 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
722 begin
723 // fix coords
731 begin
733 begin
736 end
737 else
738 begin
747 begin
749 begin
752 end
753 else
754 begin
762 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
763 begin
765 begin
768 end
769 else
770 begin
781 // ////////////////////////////////////////////////////////////////////////// //
783 begin
784 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
789 begin
791 begin
793 begin
795 end
796 else
797 begin
805 begin
810 // ////////////////////////////////////////////////////////////////////////// //
812 var
815 begin
817 begin
818 // no free cells, want more
822 begin
834 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
839 begin
841 begin
843 begin
854 // ////////////////////////////////////////////////////////////////////////// //
855 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
856 var
859 begin
861 begin
862 // no free proxies, resize list
869 // get one from list
874 // add to used list
876 // statistics
882 begin
884 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
885 // add to free list
893 // ////////////////////////////////////////////////////////////////////////// //
894 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
895 const
897 var
900 begin
903 // fix coords
906 // go on
910 //tsize := mTileSize;
913 begin
917 begin
927 // ////////////////////////////////////////////////////////////////////////// //
929 var
934 begin
936 // add body to the given grid cell
939 begin
940 {$IF DEFINED(D2F_DEBUG)}
943 begin
946 begin
948 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
952 {$ENDIF}
955 begin
957 // check "has room" flag
959 begin
960 // can add here
962 begin
964 begin
967 exit;
972 // no room, go to next cell in list (if there is any)
975 // no room in cells, add new cell to list
977 // either no room, or no cell at all
987 var
989 begin
996 // assume that we cannot have one object added to bucket twice
998 var
1002 begin
1004 // find and remove cell
1008 begin
1011 begin
1013 begin
1014 // i found her!
1016 begin
1017 // this cell contains no elements, remove it
1020 exit;
1022 // remove element from bucket
1024 begin
1029 exit;
1038 var
1040 begin
1047 // ////////////////////////////////////////////////////////////////////////// //
1048 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1049 begin
1057 begin
1064 // ////////////////////////////////////////////////////////////////////////// //
1066 var
1069 begin
1076 {$IF DEFINED(D2F_DEBUG_MOVER)}
1077 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);
1078 {$ENDIF}
1080 // map -> grid
1085 // did any corner crossed tile boundary?
1090 begin
1097 end
1098 else
1099 begin
1107 //TODO: optimize for horizontal/vertical moves
1109 var
1117 begin
1119 // check if tile coords was changed
1124 // map -> grid
1129 // check for heavy work
1140 {$IF DEFINED(D2F_DEBUG_MOVER)}
1141 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);
1142 {$ENDIF}
1144 begin
1145 // crossed tile boundary, do heavy work
1148 // cycle with old rect, remove body where it is necessary
1149 // optimized for horizontal moves
1150 {$IF DEFINED(D2F_DEBUG_MOVER)}
1151 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);
1152 {$ENDIF}
1153 // remove stale marks
1156 begin
1161 {$IF DEFINED(D2F_DEBUG_MOVER)}
1163 {$ENDIF}
1165 begin
1167 begin
1168 // this column is completely outside of new rect
1170 begin
1171 {$IF DEFINED(D2F_DEBUG_MOVER)}
1173 {$ENDIF}
1176 end
1177 else
1178 begin
1179 // heavy checks
1181 begin
1183 begin
1184 {$IF DEFINED(D2F_DEBUG_MOVER)}
1186 {$ENDIF}
1193 // cycle with new rect, add body where it is necessary
1196 begin
1201 {$IF DEFINED(D2F_DEBUG_MOVER)}
1203 {$ENDIF}
1205 begin
1207 begin
1208 // this column is completely outside of old rect
1210 begin
1211 {$IF DEFINED(D2F_DEBUG_MOVER)}
1213 {$ENDIF}
1216 end
1217 else
1218 begin
1219 // heavy checks
1221 begin
1223 begin
1224 {$IF DEFINED(D2F_DEBUG_MOVER)}
1226 {$ENDIF}
1233 // done
1234 end
1235 else
1236 begin
1237 {$IF DEFINED(D2F_DEBUG_MOVER)}
1238 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);
1239 {$ENDIF}
1241 // update coordinates
1247 var
1250 begin
1252 // check if tile coords was changed
1258 {$IF DEFINED(D2F_DEBUG_MOVER)}
1259 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);
1260 {$ENDIF}
1263 begin
1264 // crossed tile boundary, do heavy work
1269 end
1270 else
1271 begin
1272 // nothing to do with the grid, just fix size
1279 // ////////////////////////////////////////////////////////////////////////// //
1281 var
1283 begin
1286 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then cidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1291 // ////////////////////////////////////////////////////////////////////////// //
1292 // no callback: return `true` on the first hit
1293 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1294 var
1301 begin
1307 {$IF DEFINED(D2F_DEBUG_XXQ)}
1309 {$ENDIF}
1311 // make coords (0,0)-based
1318 {$IF DEFINED(D2F_DEBUG_XXQ)}
1319 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);
1320 {$ENDIF}
1322 // restore coords
1326 // increase query counter
1329 begin
1330 // just in case of overflow
1336 {$IF DEFINED(D2F_DEBUG_XXQ)}
1337 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1338 {$ENDIF}
1341 begin
1342 {$IF DEFINED(D2F_DEBUG_XXQ)}
1344 {$ENDIF}
1347 begin
1350 {$IF DEFINED(D2F_DEBUG_XXQ)}
1351 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);
1352 {$ENDIF}
1353 // shit. has to do it this way, so i can change tag in callback
1355 begin
1360 begin
1362 begin
1364 begin
1367 exit;
1369 end
1370 else
1371 begin
1374 exit;
1384 // ////////////////////////////////////////////////////////////////////////// //
1385 // no callback: return `true` on the first hit
1386 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1387 const
1389 var
1400 begin
1409 // fix coords
1414 //tsize := mTileSize;
1422 // increase query counter
1425 begin
1426 // just in case of overflow
1430 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1433 // go on
1435 begin
1439 begin
1442 // process cells
1445 begin
1448 begin
1451 // shit. has to do it this way, so i can change tag in callback
1460 begin
1462 end
1463 else
1464 begin
1467 exit;
1479 // ////////////////////////////////////////////////////////////////////////// //
1480 // no callback: return `true` on the nearest hit
1481 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1482 var
1484 begin
1489 // no callback: return `true` on the nearest hit
1490 // you are not supposed to understand this
1491 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1492 const
1494 var
1520 //swapped: Boolean = false; // true: xd is yd, and vice versa
1521 // horizontal walker
1522 {$IFDEF GRID_USE_ORTHO_ACCEL}
1524 //wksign: Integer;
1526 {$ENDIF}
1527 // skipper
1529 begin
1538 begin
1541 begin
1544 exit;
1556 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1557 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);
1558 {$ENDIF}
1565 // offset query coords to (0,0)-based
1571 // clip rectange
1577 // horizontal setup
1579 begin
1580 // from left to right
1583 end
1584 else
1585 begin
1586 // from right to left
1596 // vertical setup
1598 begin
1599 // from top to bottom
1602 end
1603 else
1604 begin
1605 // from bottom to top
1619 begin
1620 //swapped := true;
1629 end
1630 else
1631 begin
1645 begin
1646 // clip at top
1652 begin
1661 begin
1662 // clip at left
1673 begin
1674 // clip at bottom
1684 //if (term = xd) then exit; // this is the only point, get out of here
1690 // first move, to skip starting point
1691 // DON'T DO THIS! loop will take care of that
1693 begin
1694 //FIXME!
1697 begin
1699 begin
1701 begin
1704 end
1705 else
1706 begin
1709 end
1710 else
1711 begin
1716 exit;
1721 (*
1722 // move coords
1723 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1724 xd += stx;
1725 // done?
1726 if (xd = term) then exit;
1727 *)
1729 {$IF DEFINED(D2F_DEBUG)}
1730 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1731 {$ENDIF}
1732 // DON'T DO THIS! loop will take care of that
1733 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1734 //ccidx := mGrid[lastGA];
1736 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1737 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1738 {$ENDIF}
1740 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1745 // increase query counter
1748 begin
1749 // just in case of overflow
1755 {$IFDEF GRID_USE_ORTHO_ACCEL}
1756 // if this is strict horizontal/vertical trace, use optimized codepath
1758 begin
1759 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1760 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1761 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1762 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1764 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1765 {$IF DEFINED(D2F_DEBUG)}
1767 {$ENDIF}
1769 // one of those will never change
1773 begin
1774 {$IF DEFINED(D2F_DEBUG)}
1775 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1776 {$ENDIF}
1777 // new tile?
1779 begin
1782 // convert coords to map (to avoid ajdusting coords inside the loop)
1785 begin
1788 begin
1793 // constant coord should be inside
1796 begin
1798 // inside the proxy?
1801 begin
1802 // setup prev[xy]
1804 begin
1806 begin
1811 exit;
1813 end
1814 else
1815 begin
1817 {$IF DEFINED(D2F_DEBUG)}
1818 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]);
1819 {$ENDIF}
1821 begin
1826 exit;
1829 continue;
1831 // remember this hitpoint if it is nearer than an old one
1832 // setup prev[xy]
1834 begin
1835 // horizontal trace
1839 begin
1840 // going left
1844 end
1845 else
1846 begin
1847 // going right
1852 end
1853 else
1854 begin
1855 // vertical trace
1859 begin
1860 // going up
1864 end
1865 else
1866 begin
1867 // going down
1874 begin
1876 begin
1881 exit;
1883 end
1884 else
1885 begin
1887 {$IF DEFINED(D2F_DEBUG)}
1888 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]);
1889 {$ENDIF}
1891 begin
1901 // next cell
1905 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1907 // skip to next tile
1909 begin
1911 begin
1912 // to the right
1914 {$IF DEFINED(D2F_DEBUG)}
1916 {$ENDIF}
1920 end
1921 else
1922 begin
1923 // to the left
1925 {$IF DEFINED(D2F_DEBUG)}
1927 {$ENDIF}
1932 end
1933 else
1934 begin
1936 begin
1937 // to the down
1939 {$IF DEFINED(D2F_DEBUG)}
1941 {$ENDIF}
1945 end
1946 else
1947 begin
1948 // to the up
1950 {$IF DEFINED(D2F_DEBUG)}
1952 {$ENDIF}
1960 // we can travel less than one cell
1963 exit;
1965 {$ENDIF}
1967 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1968 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1969 {$ENDIF}
1971 //e_LogWritefln('*********************', []);
1973 // can omit checks
1975 begin
1976 // check cell(s)
1977 {$IF DEFINED(D2F_DEBUG)}
1978 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1979 {$ENDIF}
1980 // new tile?
1982 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1983 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);
1984 {$ENDIF}
1986 begin
1987 // yes
1988 {$IF DEFINED(D2F_DEBUG)}
1989 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1990 {$ENDIF}
1992 begin
1993 // signal cell completion
1995 begin
1996 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1997 end
1999 begin
2002 exit;
2008 // has something to process in this tile?
2010 begin
2011 // process cell
2013 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2014 // convert coords to map (to avoid ajdusting coords inside the loop)
2017 // process cell list
2019 begin
2022 begin
2027 begin
2028 // can we process this proxy?
2030 begin
2033 begin
2035 begin
2040 exit;
2042 end
2043 else
2044 begin
2045 // remember this hitpoint if it is nearer than an old one
2047 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2048 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);
2049 {$ENDIF}
2051 begin
2059 end
2060 else
2061 begin
2062 // this is possibly interesting proxy, set "has more to check" flag
2067 // next cell
2070 // still has something interesting in this cell?
2072 begin
2073 // nope, don't process this cell anymore; signal cell completion
2076 begin
2078 end
2080 begin
2083 exit;
2088 begin
2089 // move to cell edge, as we have nothing to trace here anymore
2092 //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]);
2094 begin
2095 // step
2098 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2101 //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]);
2104 //putPixel(xptr^, yptr^);
2105 // move coords
2111 // we can travel less than one cell
2113 begin
2115 end
2116 else
2117 begin
2126 // ////////////////////////////////////////////////////////////////////////// //
2127 //FIXME! optimize this with real tile walking
2128 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2129 const
2131 var
2152 //swapped: Boolean = false; // true: xd is yd, and vice versa
2153 // horizontal walker
2154 {$IFDEF GRID_USE_ORTHO_ACCEL}
2156 //wksign: Integer;
2158 {$ENDIF}
2159 // skipper
2161 begin
2168 begin
2170 exit;
2185 // offset query coords to (0,0)-based
2191 // clip rectange
2197 // horizontal setup
2199 begin
2200 // from left to right
2203 end
2204 else
2205 begin
2206 // from right to left
2216 // vertical setup
2218 begin
2219 // from top to bottom
2222 end
2223 else
2224 begin
2225 // from bottom to top
2239 begin
2240 //swapped := true;
2249 end
2250 else
2251 begin
2265 begin
2266 // clip at top
2272 begin
2281 begin
2282 // clip at left
2293 begin
2294 // clip at bottom
2304 //if (term = xd) then exit; // this is the only point, get out of here
2310 // first move, to skip starting point
2311 // DON'T DO THIS! loop will take care of that
2313 begin
2315 exit;
2318 (*
2319 // move coords
2320 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2321 xd += stx;
2322 // done?
2323 if (xd = term) then exit;
2324 *)
2326 {$IF DEFINED(D2F_DEBUG)}
2327 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2328 {$ENDIF}
2329 // DON'T DO THIS! loop will take care of that
2330 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2331 //ccidx := mGrid[lastGA];
2336 // increase query counter
2339 begin
2340 // just in case of overflow
2346 {$IFDEF GRID_USE_ORTHO_ACCEL}
2347 // if this is strict horizontal/vertical trace, use optimized codepath
2349 begin
2350 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2351 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2352 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2353 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2355 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2356 {$IF DEFINED(D2F_DEBUG)}
2358 {$ENDIF}
2361 begin
2362 {$IF DEFINED(D2F_DEBUG)}
2363 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2364 {$ENDIF}
2365 // new tile?
2367 begin
2370 // convert coords to map (to avoid ajdusting coords inside the loop)
2372 begin
2375 begin
2380 begin
2383 begin
2385 end
2386 else
2387 begin
2390 exit;
2394 // next cell
2398 // skip to next tile
2400 begin
2402 begin
2403 // to the right
2405 {$IF DEFINED(D2F_DEBUG)}
2407 {$ENDIF}
2411 end
2412 else
2413 begin
2414 // to the left
2416 {$IF DEFINED(D2F_DEBUG)}
2418 {$ENDIF}
2423 end
2424 else
2425 begin
2427 begin
2428 // to the down
2430 {$IF DEFINED(D2F_DEBUG)}
2432 {$ENDIF}
2436 end
2437 else
2438 begin
2439 // to the up
2441 {$IF DEFINED(D2F_DEBUG)}
2443 {$ENDIF}
2452 exit;
2454 {$ENDIF}
2456 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2457 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2458 {$ENDIF}
2461 // can omit checks
2463 begin
2464 // check cell(s)
2465 {$IF DEFINED(D2F_DEBUG)}
2466 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2467 {$ENDIF}
2468 // new tile?
2470 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2471 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);
2472 {$ENDIF}
2474 begin
2475 // yes
2476 {$IF DEFINED(D2F_DEBUG)}
2477 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2478 {$ENDIF}
2482 // has something to process in this tile?
2484 begin
2485 // process cell
2487 // process cell list
2489 begin
2492 begin
2497 begin
2500 begin
2502 end
2503 else
2504 begin
2507 exit;
2511 // next cell
2514 // nothing more interesting in this cell
2517 // move to cell edge, as we have nothing to trace here anymore
2520 //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]);
2522 begin
2523 // step
2526 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2529 //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]);
2531 //putPixel(xptr^, yptr^);
2532 // move coords
2541 // ////////////////////////////////////////////////////////////////////////// //
2542 // trace box with the given velocity; return object hit (if any)
2543 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
2544 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2545 var
2556 begin
2573 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
2579 // just in case
2582 // increase query counter
2585 begin
2586 // just in case of overflow
2593 begin
2595 begin
2598 begin
2601 begin
2606 begin
2609 begin
2612 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0, @hedge, @u1) then
2613 begin
2614 {
2615 if (u1 >= 0) then
2616 begin
2617 // overlapping
2618 ex := ax0;
2619 ey := ay0;
2620 result := px.mObj;
2621 mInQuery := false;
2622 exit;
2623 end;
2624 }
2625 continue;
2628 begin
2632 begin
2636 exit;
2641 // next cell
2648 begin
2657 // ////////////////////////////////////////////////////////////////////////// //
2658 {.$DEFINE D2F_DEBUG_OTR}
2659 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2660 var
2671 {$IF DEFINED(D2F_DEBUG_OTR)}
2673 {$ENDIF}
2674 begin
2688 // offset query coords to (0,0)-based
2695 begin
2697 // vertical
2699 begin
2700 // down
2702 //if (ay0 < 0) then ay0 := 0;
2706 end
2707 else
2708 begin
2709 // up
2711 //if (ay1 < 0) then ay1 := 0;
2716 // check tile
2718 begin
2724 begin
2727 begin
2733 begin
2734 // bound c0 and c1 to cell
2737 // fill the thing
2738 {$IF DEFINED(D2F_DEBUG_OTR)}
2739 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)]);
2740 {$ENDIF}
2741 //assert(c0 <= c1);
2745 // next cell
2748 {$IF DEFINED(D2F_DEBUG_OTR)}
2749 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2753 {$ENDIF}
2754 // now go till we hit cell boundary or empty space
2756 begin
2757 // up
2759 begin
2760 {$IF DEFINED(D2F_DEBUG_OTR)}
2761 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2762 {$ENDIF}
2766 {$IF DEFINED(D2F_DEBUG_OTR)}
2767 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2768 {$ENDIF}
2770 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2771 end
2772 else
2773 begin
2774 // down
2780 end
2781 else
2782 begin
2783 // horizontal