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 (or boxes overlaps)
242 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
243 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
244 // if no collision was detected:
245 // u1 < 0: no collision at all
246 // u1 >= 0: boxes are overlapping at the start; u0 has no meaning, u1 is exit time, hitedge is undefined
247 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
248 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
249 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
259 implementation
261 uses
265 // ////////////////////////////////////////////////////////////////////////// //
266 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
267 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
268 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
270 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
273 // ////////////////////////////////////////////////////////////////////////// //
274 // you are not supposed to understand this
275 // returns `true` if there is an intersection, and enter coords
276 // enter coords will be equal to (x0, y0) if starting point is inside the box
277 // if result is `false`, `inx` and `iny` are undefined
278 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
279 var
287 //!term: Integer;
291 begin
293 // why not
299 begin
300 // check this point
302 exit;
305 // check if staring point is inside the box
306 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
308 // clip rectange
314 // horizontal setup
316 begin
317 // from left to right
320 end
321 else
322 begin
323 // from right to left
333 // vertical setup
335 begin
336 // from top to bottom
339 end
340 else
341 begin
342 // from bottom to top
356 begin
365 end
366 else
367 begin
377 //!term := x1;
381 begin
382 // clip at top
388 begin
397 begin
398 // clip at left
408 (*
409 if (y1 > wy1) then
410 begin
411 // clip at bottom
412 temp := dx2*(wy1-y0)+dsx;
413 term := x0+temp div dy2;
414 rem := temp mod dy2;
415 if (rem = 0) then Dec(term);
416 end;
418 if (term > wx1) then term := wx1; // clip at right
420 Inc(term); // draw last point
421 //if (term = xd) then exit; // this is the only point, get out of here
422 *)
426 //!dx2 -= dy2;
434 // ////////////////////////////////////////////////////////////////////////// //
435 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
437 var
441 var
443 begin
447 begin
451 end
453 begin
460 begin
463 end
465 begin
473 var
476 begin
489 // check if they are overlapping right now (SAT)
490 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
494 // treat b as stationary, so invert v to get relative velocity
508 begin
514 // ////////////////////////////////////////////////////////////////////////// //
515 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
516 begin
529 begin
534 begin
539 begin
544 begin
549 begin
554 begin
559 // ////////////////////////////////////////////////////////////////////////// //
560 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
561 begin
570 begin
572 begin
574 begin
578 exit;
588 begin
593 // ////////////////////////////////////////////////////////////////////////// //
594 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
595 var
597 begin
599 {$IF DEFINED(D2F_DEBUG)}
601 {$ENDIF}
602 {
603 if aTileSize < 1 then aTileSize := 1;
604 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
605 mTileSize := aTileSize;
606 }
617 // init free list
619 begin
625 // init grid
627 // init proxies
635 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
640 begin
648 // ////////////////////////////////////////////////////////////////////////// //
650 var
652 begin
655 begin
659 begin
665 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);
670 var
673 begin
676 begin
679 begin
682 begin
684 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
686 // next cell
694 var
697 begin
705 begin
708 begin
710 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
712 // next cell
718 // ////////////////////////////////////////////////////////////////////////// //
719 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
720 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
724 begin
725 // fix coords
733 begin
735 begin
738 end
739 else
740 begin
749 begin
751 begin
754 end
755 else
756 begin
764 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
765 begin
767 begin
770 end
771 else
772 begin
783 // ////////////////////////////////////////////////////////////////////////// //
785 begin
786 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
791 begin
793 begin
795 begin
797 end
798 else
799 begin
807 begin
812 // ////////////////////////////////////////////////////////////////////////// //
814 var
817 begin
819 begin
820 // no free cells, want more
824 begin
836 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
841 begin
843 begin
845 begin
856 // ////////////////////////////////////////////////////////////////////////// //
857 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
858 var
861 begin
863 begin
864 // no free proxies, resize list
871 // get one from list
876 // add to used list
878 // statistics
884 begin
886 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
887 // add to free list
895 // ////////////////////////////////////////////////////////////////////////// //
896 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
897 const
899 var
902 begin
905 // fix coords
908 // go on
912 //tsize := mTileSize;
915 begin
919 begin
929 // ////////////////////////////////////////////////////////////////////////// //
931 var
936 begin
938 // add body to the given grid cell
941 begin
942 {$IF DEFINED(D2F_DEBUG)}
945 begin
948 begin
950 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
954 {$ENDIF}
957 begin
959 // check "has room" flag
961 begin
962 // can add here
964 begin
966 begin
969 exit;
974 // no room, go to next cell in list (if there is any)
977 // no room in cells, add new cell to list
979 // either no room, or no cell at all
989 var
991 begin
998 // assume that we cannot have one object added to bucket twice
1000 var
1004 begin
1006 // find and remove cell
1010 begin
1013 begin
1015 begin
1016 // i found her!
1018 begin
1019 // this cell contains no elements, remove it
1022 exit;
1024 // remove element from bucket
1026 begin
1031 exit;
1040 var
1042 begin
1049 // ////////////////////////////////////////////////////////////////////////// //
1050 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1051 begin
1059 begin
1066 // ////////////////////////////////////////////////////////////////////////// //
1068 var
1071 begin
1078 {$IF DEFINED(D2F_DEBUG_MOVER)}
1079 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);
1080 {$ENDIF}
1082 // map -> grid
1087 // did any corner crossed tile boundary?
1092 begin
1099 end
1100 else
1101 begin
1109 //TODO: optimize for horizontal/vertical moves
1111 var
1119 begin
1121 // check if tile coords was changed
1126 // map -> grid
1131 // check for heavy work
1142 {$IF DEFINED(D2F_DEBUG_MOVER)}
1143 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);
1144 {$ENDIF}
1146 begin
1147 // crossed tile boundary, do heavy work
1150 // cycle with old rect, remove body where it is necessary
1151 // optimized for horizontal moves
1152 {$IF DEFINED(D2F_DEBUG_MOVER)}
1153 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);
1154 {$ENDIF}
1155 // remove stale marks
1158 begin
1163 {$IF DEFINED(D2F_DEBUG_MOVER)}
1165 {$ENDIF}
1167 begin
1169 begin
1170 // this column is completely outside of new rect
1172 begin
1173 {$IF DEFINED(D2F_DEBUG_MOVER)}
1175 {$ENDIF}
1178 end
1179 else
1180 begin
1181 // heavy checks
1183 begin
1185 begin
1186 {$IF DEFINED(D2F_DEBUG_MOVER)}
1188 {$ENDIF}
1195 // cycle with new rect, add body where it is necessary
1198 begin
1203 {$IF DEFINED(D2F_DEBUG_MOVER)}
1205 {$ENDIF}
1207 begin
1209 begin
1210 // this column is completely outside of old rect
1212 begin
1213 {$IF DEFINED(D2F_DEBUG_MOVER)}
1215 {$ENDIF}
1218 end
1219 else
1220 begin
1221 // heavy checks
1223 begin
1225 begin
1226 {$IF DEFINED(D2F_DEBUG_MOVER)}
1228 {$ENDIF}
1235 // done
1236 end
1237 else
1238 begin
1239 {$IF DEFINED(D2F_DEBUG_MOVER)}
1240 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);
1241 {$ENDIF}
1243 // update coordinates
1249 var
1252 begin
1254 // check if tile coords was changed
1260 {$IF DEFINED(D2F_DEBUG_MOVER)}
1261 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);
1262 {$ENDIF}
1265 begin
1266 // crossed tile boundary, do heavy work
1271 end
1272 else
1273 begin
1274 // nothing to do with the grid, just fix size
1281 // ////////////////////////////////////////////////////////////////////////// //
1283 var
1285 begin
1288 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then cidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1293 // ////////////////////////////////////////////////////////////////////////// //
1294 // no callback: return `true` on the first hit
1295 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1296 var
1303 begin
1309 {$IF DEFINED(D2F_DEBUG_XXQ)}
1311 {$ENDIF}
1313 // make coords (0,0)-based
1320 {$IF DEFINED(D2F_DEBUG_XXQ)}
1321 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);
1322 {$ENDIF}
1324 // restore coords
1328 // increase query counter
1331 begin
1332 // just in case of overflow
1338 {$IF DEFINED(D2F_DEBUG_XXQ)}
1339 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1340 {$ENDIF}
1343 begin
1344 {$IF DEFINED(D2F_DEBUG_XXQ)}
1346 {$ENDIF}
1349 begin
1352 {$IF DEFINED(D2F_DEBUG_XXQ)}
1353 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);
1354 {$ENDIF}
1355 // shit. has to do it this way, so i can change tag in callback
1357 begin
1362 begin
1364 begin
1366 begin
1369 exit;
1371 end
1372 else
1373 begin
1376 exit;
1386 // ////////////////////////////////////////////////////////////////////////// //
1387 // no callback: return `true` on the first hit
1388 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1389 const
1391 var
1402 begin
1411 // fix coords
1416 //tsize := mTileSize;
1424 // increase query counter
1427 begin
1428 // just in case of overflow
1432 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1435 // go on
1437 begin
1441 begin
1444 // process cells
1447 begin
1450 begin
1453 // shit. has to do it this way, so i can change tag in callback
1462 begin
1464 end
1465 else
1466 begin
1469 exit;
1481 // ////////////////////////////////////////////////////////////////////////// //
1482 // no callback: return `true` on the nearest hit
1483 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1484 var
1486 begin
1491 // no callback: return `true` on the nearest hit
1492 // you are not supposed to understand this
1493 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1494 const
1496 var
1522 //swapped: Boolean = false; // true: xd is yd, and vice versa
1523 // horizontal walker
1524 {$IFDEF GRID_USE_ORTHO_ACCEL}
1526 //wksign: Integer;
1528 {$ENDIF}
1529 // skipper
1531 begin
1540 begin
1543 begin
1546 exit;
1558 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1559 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);
1560 {$ENDIF}
1567 // offset query coords to (0,0)-based
1573 // clip rectange
1579 // horizontal setup
1581 begin
1582 // from left to right
1585 end
1586 else
1587 begin
1588 // from right to left
1598 // vertical setup
1600 begin
1601 // from top to bottom
1604 end
1605 else
1606 begin
1607 // from bottom to top
1621 begin
1622 //swapped := true;
1631 end
1632 else
1633 begin
1647 begin
1648 // clip at top
1654 begin
1663 begin
1664 // clip at left
1675 begin
1676 // clip at bottom
1686 //if (term = xd) then exit; // this is the only point, get out of here
1692 // first move, to skip starting point
1693 // DON'T DO THIS! loop will take care of that
1695 begin
1696 //FIXME!
1699 begin
1701 begin
1703 begin
1706 end
1707 else
1708 begin
1711 end
1712 else
1713 begin
1718 exit;
1723 (*
1724 // move coords
1725 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1726 xd += stx;
1727 // done?
1728 if (xd = term) then exit;
1729 *)
1731 {$IF DEFINED(D2F_DEBUG)}
1732 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1733 {$ENDIF}
1734 // DON'T DO THIS! loop will take care of that
1735 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1736 //ccidx := mGrid[lastGA];
1738 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1739 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1740 {$ENDIF}
1742 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1747 // increase query counter
1750 begin
1751 // just in case of overflow
1757 {$IFDEF GRID_USE_ORTHO_ACCEL}
1758 // if this is strict horizontal/vertical trace, use optimized codepath
1760 begin
1761 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1762 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1763 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1764 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1766 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1767 {$IF DEFINED(D2F_DEBUG)}
1769 {$ENDIF}
1771 // one of those will never change
1775 begin
1776 {$IF DEFINED(D2F_DEBUG)}
1777 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1778 {$ENDIF}
1779 // new tile?
1781 begin
1784 // convert coords to map (to avoid ajdusting coords inside the loop)
1787 begin
1790 begin
1795 // constant coord should be inside
1798 begin
1800 // inside the proxy?
1803 begin
1804 // setup prev[xy]
1806 begin
1808 begin
1813 exit;
1815 end
1816 else
1817 begin
1819 {$IF DEFINED(D2F_DEBUG)}
1820 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]);
1821 {$ENDIF}
1823 begin
1828 exit;
1831 continue;
1833 // remember this hitpoint if it is nearer than an old one
1834 // setup prev[xy]
1836 begin
1837 // horizontal trace
1841 begin
1842 // going left
1846 end
1847 else
1848 begin
1849 // going right
1854 end
1855 else
1856 begin
1857 // vertical trace
1861 begin
1862 // going up
1866 end
1867 else
1868 begin
1869 // going down
1876 begin
1878 begin
1883 exit;
1885 end
1886 else
1887 begin
1889 {$IF DEFINED(D2F_DEBUG)}
1890 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]);
1891 {$ENDIF}
1893 begin
1903 // next cell
1907 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1909 // skip to next tile
1911 begin
1913 begin
1914 // to the right
1916 {$IF DEFINED(D2F_DEBUG)}
1918 {$ENDIF}
1922 end
1923 else
1924 begin
1925 // to the left
1927 {$IF DEFINED(D2F_DEBUG)}
1929 {$ENDIF}
1934 end
1935 else
1936 begin
1938 begin
1939 // to the down
1941 {$IF DEFINED(D2F_DEBUG)}
1943 {$ENDIF}
1947 end
1948 else
1949 begin
1950 // to the up
1952 {$IF DEFINED(D2F_DEBUG)}
1954 {$ENDIF}
1962 // we can travel less than one cell
1965 exit;
1967 {$ENDIF}
1969 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1970 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1971 {$ENDIF}
1973 //e_LogWritefln('*********************', []);
1975 // can omit checks
1977 begin
1978 // check cell(s)
1979 {$IF DEFINED(D2F_DEBUG)}
1980 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1981 {$ENDIF}
1982 // new tile?
1984 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1985 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);
1986 {$ENDIF}
1988 begin
1989 // yes
1990 {$IF DEFINED(D2F_DEBUG)}
1991 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1992 {$ENDIF}
1994 begin
1995 // signal cell completion
1997 begin
1998 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1999 end
2001 begin
2004 exit;
2010 // has something to process in this tile?
2012 begin
2013 // process cell
2015 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2016 // convert coords to map (to avoid ajdusting coords inside the loop)
2019 // process cell list
2021 begin
2024 begin
2029 begin
2030 // can we process this proxy?
2032 begin
2035 begin
2037 begin
2042 exit;
2044 end
2045 else
2046 begin
2047 // remember this hitpoint if it is nearer than an old one
2049 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2050 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);
2051 {$ENDIF}
2053 begin
2061 end
2062 else
2063 begin
2064 // this is possibly interesting proxy, set "has more to check" flag
2069 // next cell
2072 // still has something interesting in this cell?
2074 begin
2075 // nope, don't process this cell anymore; signal cell completion
2078 begin
2080 end
2082 begin
2085 exit;
2090 begin
2091 // move to cell edge, as we have nothing to trace here anymore
2094 //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]);
2096 begin
2097 // step
2100 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2103 //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]);
2106 //putPixel(xptr^, yptr^);
2107 // move coords
2113 // we can travel less than one cell
2115 begin
2117 end
2118 else
2119 begin
2128 // ////////////////////////////////////////////////////////////////////////// //
2129 //FIXME! optimize this with real tile walking
2130 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2131 const
2133 var
2154 //swapped: Boolean = false; // true: xd is yd, and vice versa
2155 // horizontal walker
2156 {$IFDEF GRID_USE_ORTHO_ACCEL}
2158 //wksign: Integer;
2160 {$ENDIF}
2161 // skipper
2163 begin
2170 begin
2172 exit;
2187 // offset query coords to (0,0)-based
2193 // clip rectange
2199 // horizontal setup
2201 begin
2202 // from left to right
2205 end
2206 else
2207 begin
2208 // from right to left
2218 // vertical setup
2220 begin
2221 // from top to bottom
2224 end
2225 else
2226 begin
2227 // from bottom to top
2241 begin
2242 //swapped := true;
2251 end
2252 else
2253 begin
2267 begin
2268 // clip at top
2274 begin
2283 begin
2284 // clip at left
2295 begin
2296 // clip at bottom
2306 //if (term = xd) then exit; // this is the only point, get out of here
2312 // first move, to skip starting point
2313 // DON'T DO THIS! loop will take care of that
2315 begin
2317 exit;
2320 (*
2321 // move coords
2322 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2323 xd += stx;
2324 // done?
2325 if (xd = term) then exit;
2326 *)
2328 {$IF DEFINED(D2F_DEBUG)}
2329 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2330 {$ENDIF}
2331 // DON'T DO THIS! loop will take care of that
2332 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2333 //ccidx := mGrid[lastGA];
2338 // increase query counter
2341 begin
2342 // just in case of overflow
2348 {$IFDEF GRID_USE_ORTHO_ACCEL}
2349 // if this is strict horizontal/vertical trace, use optimized codepath
2351 begin
2352 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2353 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2354 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2355 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2357 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2358 {$IF DEFINED(D2F_DEBUG)}
2360 {$ENDIF}
2363 begin
2364 {$IF DEFINED(D2F_DEBUG)}
2365 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2366 {$ENDIF}
2367 // new tile?
2369 begin
2372 // convert coords to map (to avoid ajdusting coords inside the loop)
2374 begin
2377 begin
2382 begin
2385 begin
2387 end
2388 else
2389 begin
2392 exit;
2396 // next cell
2400 // skip to next tile
2402 begin
2404 begin
2405 // to the right
2407 {$IF DEFINED(D2F_DEBUG)}
2409 {$ENDIF}
2413 end
2414 else
2415 begin
2416 // to the left
2418 {$IF DEFINED(D2F_DEBUG)}
2420 {$ENDIF}
2425 end
2426 else
2427 begin
2429 begin
2430 // to the down
2432 {$IF DEFINED(D2F_DEBUG)}
2434 {$ENDIF}
2438 end
2439 else
2440 begin
2441 // to the up
2443 {$IF DEFINED(D2F_DEBUG)}
2445 {$ENDIF}
2454 exit;
2456 {$ENDIF}
2458 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2459 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2460 {$ENDIF}
2463 // can omit checks
2465 begin
2466 // check cell(s)
2467 {$IF DEFINED(D2F_DEBUG)}
2468 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2469 {$ENDIF}
2470 // new tile?
2472 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2473 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);
2474 {$ENDIF}
2476 begin
2477 // yes
2478 {$IF DEFINED(D2F_DEBUG)}
2479 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2480 {$ENDIF}
2484 // has something to process in this tile?
2486 begin
2487 // process cell
2489 // process cell list
2491 begin
2494 begin
2499 begin
2502 begin
2504 end
2505 else
2506 begin
2509 exit;
2513 // next cell
2516 // nothing more interesting in this cell
2519 // move to cell edge, as we have nothing to trace here anymore
2522 //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]);
2524 begin
2525 // step
2528 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2531 //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]);
2533 //putPixel(xptr^, yptr^);
2534 // move coords
2543 // ////////////////////////////////////////////////////////////////////////// //
2544 // trace box with the given velocity; return object hit (if any)
2545 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
2546 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2547 var
2558 begin
2575 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
2581 // just in case
2584 // increase query counter
2587 begin
2588 // just in case of overflow
2596 begin
2599 begin
2602 begin
2605 begin
2610 begin
2613 begin
2616 if not sweepAABB(cx0+mMinX, cy0+mMinY, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0, @hedge) then
2617 begin
2618 continue;
2621 begin
2625 begin
2629 exit;
2634 // next cell
2643 begin
2652 // ////////////////////////////////////////////////////////////////////////// //
2653 {.$DEFINE D2F_DEBUG_OTR}
2654 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2655 var
2666 {$IF DEFINED(D2F_DEBUG_OTR)}
2668 {$ENDIF}
2669 begin
2683 // offset query coords to (0,0)-based
2690 begin
2692 // vertical
2694 begin
2695 // down
2697 //if (ay0 < 0) then ay0 := 0;
2701 end
2702 else
2703 begin
2704 // up
2706 //if (ay1 < 0) then ay1 := 0;
2711 // check tile
2713 begin
2719 begin
2722 begin
2728 begin
2729 // bound c0 and c1 to cell
2732 // fill the thing
2733 {$IF DEFINED(D2F_DEBUG_OTR)}
2734 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)]);
2735 {$ENDIF}
2736 //assert(c0 <= c1);
2740 // next cell
2743 {$IF DEFINED(D2F_DEBUG_OTR)}
2744 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2748 {$ENDIF}
2749 // now go till we hit cell boundary or empty space
2751 begin
2752 // up
2754 begin
2755 {$IF DEFINED(D2F_DEBUG_OTR)}
2756 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2757 {$ENDIF}
2761 {$IF DEFINED(D2F_DEBUG_OTR)}
2762 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2763 {$ENDIF}
2765 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2766 end
2767 else
2768 begin
2769 // down
2775 end
2776 else
2777 begin
2778 // horizontal