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
28 const
31 type
35 public
36 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
37 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
43 private
44 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
158 public
159 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
162 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
171 // `false` if `body` is surely invalid
176 //WARNING: don't modify grid while any query is in progress (no checks are made!)
177 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
178 // no callback: return `true` on the first hit
179 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
181 //WARNING: don't modify grid while any query is in progress (no checks are made!)
182 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
183 // no callback: return object on the first hit or nil
184 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
188 //WARNING: don't modify grid while any query is in progress (no checks are made!)
189 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
190 // cb with `(nil)` will be called before processing new tile
191 // no callback: return object of the nearest hit or nil
192 // if `inverted` is true, trace will register bodies *exluding* tagmask
193 //WARNING: don't change tags in callbacks here!
194 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
195 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
197 //WARNING: don't modify grid while any query is in progress (no checks are made!)
198 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
199 // cb with `(nil)` will be called before processing new tile
200 // no callback: return object of the nearest hit or nil
201 // if `inverted` is true, trace will register bodies *exluding* tagmask
202 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
203 //WARNING: don't change tags in callbacks here!
204 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
205 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
207 // return `false` if we're still inside at the end
208 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
209 // `true`: endpoint will point at the last "inside" pixel
210 // `false`: endpoint will be (ax1, ay1)
211 //WARNING: don't change tags in callbacks here!
212 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
214 //WARNING: don't modify grid while any query is in progress (no checks are made!)
215 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
216 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
217 //WARNING: don't change tags in callbacks here!
218 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
220 // trace box with the given velocity; return object hit (if any)
221 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
222 //WARNING: don't change tags in callbacks here!
223 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
225 // debug
230 public
231 //WARNING! no sanity checks!
243 type
244 // common structure for all line tracers
246 public
249 private
256 //xptr, yptr: PInteger;
259 public
260 // call `setyp` after this
265 // this will use `w[xy][01]` to clip coords
266 // return `false` if the whole line was clipped away
267 // on `true`, you should process first point, and go on
270 // call this *after* doing a step
271 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
274 // as you will prolly call `done()` after doing a step anyway, this will do it for you
275 // move to next point, return `true` when the line is complete (i.e. you should stop)
278 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
281 // hack for line-vs-aabb; NOT PROPERLY TESTED!
284 // current coords
290 // move directions; always [-1..1] (can be zero!)
296 // you are not supposed to understand this
297 // returns `true` if there is an intersection, and enter coords
298 // enter coords will be equal to (x0, y0) if starting point is inside the box
299 // if result is `false`, `inx` and `iny` are undefined
300 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
302 // sweep two AABB's to see if and when they are overlapping
303 // returns `true` if collision was detected (but boxes doesn't overlap)
304 // u1 and u1 has no sense if no collision was detected
305 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
306 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
307 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
308 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
309 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
315 //function minInt (a, b: Integer): Integer; inline;
316 //function maxInt (a, b: Integer): Integer; inline;
319 implementation
321 uses
325 // ////////////////////////////////////////////////////////////////////////// //
326 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
327 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
328 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
329 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
331 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
334 // ////////////////////////////////////////////////////////////////////////// //
336 begin
341 begin
342 // clip rectange
352 begin
359 var
366 begin
374 // ortho?
376 begin
377 // only xd
378 //assert(lsty <> 0);
380 begin
381 // xd: to left edge
384 exit;
385 end
386 else
387 begin
388 // xd: to right edge
391 exit;
395 // not ortho
396 //assert(lstx <> 0); // invariant
403 // calculate xwalk
405 begin
408 end
409 else
410 begin
415 // calculate ywalk
417 begin
420 end
421 else
422 begin
428 begin
429 // in which dir we want to walk?
431 // walk x
433 begin
436 end
437 else
438 begin
442 // walk y
448 //assert((xd div TileSize <> lxd div TileSize) or (yd div TileSize <> lyd div TileSize));
454 // NOT TESTED!
456 begin
457 //writeln('e=', e, '; dx2=', dx2, '; dy2=', dy2);
459 begin
462 end
463 else
464 begin
470 function TLineWalker.x (): Integer; inline; begin if xyswapped then result := yd else result := xd; end;
471 function TLineWalker.y (): Integer; inline; begin if xyswapped then result := xd else result := yd; end;
472 procedure TLineWalker.getXY (out ox, oy: Integer); inline; begin if xyswapped then begin ox := yd; oy := xd; end else begin ox := xd; oy := yd; end; end;
474 function TLineWalker.dx (): Integer; inline; begin if xyswapped then result := stx else result := sty; end;
475 function TLineWalker.dy (): Integer; inline; begin if xyswapped then result := sty else result := stx; end;
478 procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
479 var
484 begin
488 // horizontal setup
490 begin
491 // from left to right
494 end
495 else
496 begin
497 // from right to left
507 // vertical setup
509 begin
510 // from top to bottom
513 end
514 else
515 begin
516 // from bottom to top
530 begin
532 //xptr := @yd;
533 //yptr := @xd;
540 end
541 else
542 begin
543 //xptr := @xd;
544 //yptr := @yd;
556 begin
557 // clip at top
563 begin
566 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
573 begin
574 // clip at left
585 begin
586 // clip at bottom
596 //if (term = xd) then exit; // this is the only point, get out of here
606 // ////////////////////////////////////////////////////////////////////////// //
607 // you are not supposed to understand this
608 // returns `true` if there is an intersection, and enter coords
609 // enter coords will be equal to (x0, y0) if starting point is inside the box
610 // if result is `false`, `inx` and `iny` are undefined
611 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
612 var
620 //!term: Integer;
624 begin
626 // why not
632 begin
633 // check this point
635 exit;
638 // check if staring point is inside the box
639 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
641 // clip rectange
647 // horizontal setup
649 begin
650 // from left to right
653 end
654 else
655 begin
656 // from right to left
666 // vertical setup
668 begin
669 // from top to bottom
672 end
673 else
674 begin
675 // from bottom to top
689 begin
698 end
699 else
700 begin
710 //!term := x1;
714 begin
715 // clip at top
721 begin
724 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
731 begin
732 // clip at left
742 (*
743 if (y1 > wy1) then
744 begin
745 // clip at bottom
746 temp := dx2*(wy1-y0)+dsx;
747 term := x0+temp div dy2;
748 rem := temp mod dy2;
749 if (rem = 0) then Dec(term);
750 end;
752 if (term > wx1) then term := wx1; // clip at right
754 Inc(term); // draw last point
755 //if (term = xd) then exit; // this is the only point, get out of here
756 *)
760 //!dx2 -= dy2;
768 // ////////////////////////////////////////////////////////////////////////// //
769 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
771 var
775 var
777 begin
781 begin
785 end
787 begin
794 begin
797 end
799 begin
807 var
810 begin
823 // check if they are overlapping right now (SAT)
824 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
828 // treat b as stationary, so invert v to get relative velocity
842 begin
848 // ////////////////////////////////////////////////////////////////////////// //
849 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
850 begin
863 begin
868 begin
873 begin
878 begin
883 begin
888 begin
893 // ////////////////////////////////////////////////////////////////////////// //
894 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
895 begin
904 begin
906 begin
908 begin
912 exit;
922 begin
927 // ////////////////////////////////////////////////////////////////////////// //
928 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
929 var
931 begin
933 {$IF DEFINED(D2F_DEBUG)}
935 {$ENDIF}
936 {
937 if aTileSize < 1 then aTileSize := 1;
938 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
939 mTileSize := aTileSize;
940 }
951 // init free list
953 begin
959 // init grid
961 // init proxies
969 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
974 begin
982 // ////////////////////////////////////////////////////////////////////////// //
984 var
986 begin
989 begin
993 begin
999 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);
1004 var
1007 begin
1010 begin
1013 begin
1016 begin
1018 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
1020 // next cell
1028 var
1031 begin
1039 begin
1042 begin
1044 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
1046 // next cell
1052 // ////////////////////////////////////////////////////////////////////////// //
1053 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
1054 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
1058 begin
1059 // fix coords
1067 begin
1069 begin
1072 end
1073 else
1074 begin
1083 begin
1085 begin
1088 end
1089 else
1090 begin
1098 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
1099 begin
1101 begin
1104 end
1105 else
1106 begin
1117 // ////////////////////////////////////////////////////////////////////////// //
1119 begin
1120 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1125 begin
1127 begin
1129 begin
1131 end
1132 else
1133 begin
1141 begin
1146 // ////////////////////////////////////////////////////////////////////////// //
1148 var
1151 begin
1153 begin
1154 // no free cells, want more
1158 begin
1170 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1175 begin
1177 begin
1179 begin
1190 // ////////////////////////////////////////////////////////////////////////// //
1191 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1192 var
1195 begin
1197 begin
1198 // no free proxies, resize list
1205 // get one from list
1210 // add to used list
1212 // statistics
1218 begin
1220 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1221 // add to free list
1229 // ////////////////////////////////////////////////////////////////////////// //
1230 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1231 var
1235 begin
1238 // fix coords
1241 // go on
1250 // clip rect
1256 // do the work
1258 begin
1260 begin
1268 // ////////////////////////////////////////////////////////////////////////// //
1270 var
1275 begin
1277 // add body to the given grid cell
1280 begin
1281 {$IF DEFINED(D2F_DEBUG)}
1284 begin
1287 begin
1289 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1293 {$ENDIF}
1296 begin
1298 // check "has room" flag
1300 begin
1301 // can add here
1303 begin
1305 begin
1308 exit;
1313 // no room, go to next cell in list (if there is any)
1316 // no room in cells, add new cell to list
1318 // either no room, or no cell at all
1328 // assume that we cannot have one object added to bucket twice
1330 var
1334 begin
1336 // find and remove cell
1340 begin
1343 begin
1345 begin
1346 // i found her!
1348 begin
1349 // this cell contains no elements, remove it
1352 exit;
1354 // remove element from bucket
1356 begin
1361 exit;
1370 // ////////////////////////////////////////////////////////////////////////// //
1371 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1372 begin
1375 //insertInternal(result);
1381 var
1383 begin
1386 //removeInternal(body);
1392 // ////////////////////////////////////////////////////////////////////////// //
1394 var
1397 begin
1404 {$IF DEFINED(D2F_DEBUG_MOVER)}
1405 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);
1406 {$ENDIF}
1408 // map -> grid
1413 // did any corner crossed tile boundary?
1418 begin
1419 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1420 //removeInternal(body);
1426 //insertInternal(body);
1428 end
1429 else
1430 begin
1439 //TODO: optimize for horizontal/vertical moves
1441 var
1449 begin
1451 // check if tile coords was changed
1456 // map -> grid
1461 // check for heavy work
1472 {$IF DEFINED(D2F_DEBUG_MOVER)}
1473 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);
1474 {$ENDIF}
1476 begin
1477 // crossed tile boundary, do heavy work
1480 // cycle with old rect, remove body where it is necessary
1481 // optimized for horizontal moves
1482 {$IF DEFINED(D2F_DEBUG_MOVER)}
1483 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);
1484 {$ENDIF}
1485 // remove stale marks
1488 begin
1493 {$IF DEFINED(D2F_DEBUG_MOVER)}
1495 {$ENDIF}
1497 begin
1499 begin
1500 // this column is completely outside of new rect
1502 begin
1503 {$IF DEFINED(D2F_DEBUG_MOVER)}
1505 {$ENDIF}
1508 end
1509 else
1510 begin
1511 // heavy checks
1513 begin
1515 begin
1516 {$IF DEFINED(D2F_DEBUG_MOVER)}
1518 {$ENDIF}
1525 // cycle with new rect, add body where it is necessary
1528 begin
1533 {$IF DEFINED(D2F_DEBUG_MOVER)}
1535 {$ENDIF}
1537 begin
1539 begin
1540 // this column is completely outside of old rect
1542 begin
1543 {$IF DEFINED(D2F_DEBUG_MOVER)}
1545 {$ENDIF}
1548 end
1549 else
1550 begin
1551 // heavy checks
1553 begin
1555 begin
1556 {$IF DEFINED(D2F_DEBUG_MOVER)}
1558 {$ENDIF}
1565 // done
1566 end
1567 else
1568 begin
1569 {$IF DEFINED(D2F_DEBUG_MOVER)}
1570 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);
1571 {$ENDIF}
1573 // update coordinates
1580 var
1583 begin
1585 // check if tile coords was changed
1591 {$IF DEFINED(D2F_DEBUG_MOVER)}
1592 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);
1593 {$ENDIF}
1596 begin
1597 // crossed tile boundary, do heavy work
1598 //removeInternal(body);
1602 //insertInternal(body);
1604 end
1605 else
1606 begin
1607 // nothing to do with the grid, just fix size
1614 // ////////////////////////////////////////////////////////////////////////// //
1616 var
1618 begin
1621 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1626 // ////////////////////////////////////////////////////////////////////////// //
1627 // no callback: return `true` on the first hit
1628 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1629 var
1636 begin
1642 {$IF DEFINED(D2F_DEBUG_XXQ)}
1644 {$ENDIF}
1646 // make coords (0,0)-based
1653 {$IF DEFINED(D2F_DEBUG_XXQ)}
1654 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);
1655 {$ENDIF}
1657 // restore coords
1661 // increase query counter
1664 begin
1665 // just in case of overflow
1671 {$IF DEFINED(D2F_DEBUG_XXQ)}
1672 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1673 {$ENDIF}
1676 begin
1677 {$IF DEFINED(D2F_DEBUG_XXQ)}
1679 {$ENDIF}
1682 begin
1685 {$IF DEFINED(D2F_DEBUG_XXQ)}
1686 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);
1687 {$ENDIF}
1688 // shit. has to do it this way, so i can change tag in callback
1690 begin
1695 begin
1697 begin
1699 begin
1702 exit;
1704 end
1705 else
1706 begin
1709 exit;
1719 // ////////////////////////////////////////////////////////////////////////// //
1720 // no callback: return `true` on the first hit
1721 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1722 var
1734 begin
1743 // fix coords
1758 // clip rect
1765 // has something to do
1769 // increase query counter
1772 begin
1773 // just in case of overflow
1777 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1780 // go on
1782 begin
1784 begin
1785 // process cells
1788 begin
1791 begin
1794 // shit! has to do it this way, so i can change tag in callback
1803 begin
1805 end
1806 else
1807 begin
1810 exit;
1822 // ////////////////////////////////////////////////////////////////////////// //
1823 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1824 var
1835 //px0, py0, px1, py1: Integer;
1836 begin
1847 // make query coords (0,0)-based
1859 // increase query counter
1862 begin
1863 // just in case of overflow
1869 repeat
1871 // check tile
1873 // process cells
1875 begin
1878 begin
1883 begin
1886 begin
1889 exit;
1893 // next cell
1896 // done processing cells, move to next tile
1903 // ////////////////////////////////////////////////////////////////////////// //
1904 // trace box with the given velocity; return object hit (if any)
1905 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1906 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1907 var
1918 begin
1932 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1938 // just in case
1944 // increase query counter
1947 begin
1948 // just in case of overflow
1955 begin
1957 begin
1960 begin
1963 begin
1968 begin
1971 begin
1974 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1976 begin
1981 begin
1985 exit;
1990 // next cell
1997 begin
2000 // just in case, compensate for floating point inexactness
2001 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
2002 begin
2012 // ////////////////////////////////////////////////////////////////////////// //
2013 {.$DEFINE D2F_DEBUG_OTR}
2014 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2015 var
2026 {$IF DEFINED(D2F_DEBUG_OTR)}
2028 {$ENDIF}
2029 begin
2043 // offset query coords to (0,0)-based
2050 begin
2052 // vertical
2054 begin
2055 // down
2057 //if (ay0 < 0) then ay0 := 0;
2061 end
2062 else
2063 begin
2064 // up
2066 //if (ay1 < 0) then ay1 := 0;
2071 // check tile
2073 begin
2079 begin
2082 begin
2088 begin
2089 // bound c0 and c1 to cell
2092 // fill the thing
2093 {$IF DEFINED(D2F_DEBUG_OTR)}
2094 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)]);
2095 {$ENDIF}
2096 //assert(c0 <= c1);
2100 // next cell
2103 {$IF DEFINED(D2F_DEBUG_OTR)}
2104 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2108 {$ENDIF}
2109 // now go till we hit cell boundary or empty space
2111 begin
2112 // up
2114 begin
2115 {$IF DEFINED(D2F_DEBUG_OTR)}
2116 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2117 {$ENDIF}
2121 {$IF DEFINED(D2F_DEBUG_OTR)}
2122 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2123 {$ENDIF}
2125 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2126 end
2127 else
2128 begin
2129 // down
2135 end
2136 else
2137 begin
2138 // horizontal
2144 // ////////////////////////////////////////////////////////////////////////// //
2145 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2146 var
2148 begin
2153 // no callback: return `true` on the nearest hit
2154 // you are not supposed to understand this
2155 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2156 var
2171 begin
2181 // make query coords (0,0)-based
2197 // increase query counter
2200 begin
2201 // just in case of overflow
2207 repeat
2209 // check tile
2211 // process cells
2214 begin
2217 begin
2222 begin
2225 begin
2228 // get adjusted proxy coords
2233 // inside?
2235 begin
2236 // oops
2241 exit;
2243 // do line-vs-aabb test
2246 begin
2247 // hit detected
2251 begin
2256 // if this is not a first cell, get outta here
2263 // next cell
2266 // done processing cells; exit if we registered a hit
2267 // next cells can't have better candidates, obviously
2270 // move to next tile
2277 // ////////////////////////////////////////////////////////////////////////// //
2278 // no callback: return `true` on the nearest hit
2279 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2280 var
2282 begin
2287 // no callback: return `true` on the nearest hit
2288 // you are not supposed to understand this
2289 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2290 var
2316 //swapped: Boolean = false; // true: xd is yd, and vice versa
2317 // horizontal walker
2318 {$IFDEF GRID_USE_ORTHO_ACCEL}
2320 //wksign: Integer;
2322 {$ENDIF}
2323 // skipper
2325 begin
2334 begin
2337 begin
2340 exit;
2352 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2353 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);
2354 {$ENDIF}
2361 // offset query coords to (0,0)-based
2367 // clip rectange
2373 // horizontal setup
2375 begin
2376 // from left to right
2379 end
2380 else
2381 begin
2382 // from right to left
2392 // vertical setup
2394 begin
2395 // from top to bottom
2398 end
2399 else
2400 begin
2401 // from bottom to top
2415 begin
2416 //swapped := true;
2425 end
2426 else
2427 begin
2441 begin
2442 // clip at top
2448 begin
2451 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2458 begin
2459 // clip at left
2470 begin
2471 // clip at bottom
2481 //if (term = xd) then exit; // this is the only point, get out of here
2487 // first move, to skip starting point
2488 // DON'T DO THIS! loop will take care of that
2490 begin
2491 //FIXME!
2494 begin
2496 begin
2498 begin
2501 end
2502 else
2503 begin
2506 end
2507 else
2508 begin
2513 exit;
2518 (*
2519 // move coords
2520 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2521 xd += stx;
2522 // done?
2523 if (xd = term) then exit;
2524 *)
2526 {$IF DEFINED(D2F_DEBUG)}
2527 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2528 {$ENDIF}
2529 // DON'T DO THIS! loop will take care of that
2530 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2531 //ccidx := mGrid[lastGA];
2533 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2534 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2535 {$ENDIF}
2537 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2542 // increase query counter
2545 begin
2546 // just in case of overflow
2552 {$IFDEF GRID_USE_ORTHO_ACCEL}
2553 // if this is strict horizontal/vertical trace, use optimized codepath
2555 begin
2556 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2557 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2558 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2559 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2561 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2562 {$IF DEFINED(D2F_DEBUG)}
2564 {$ENDIF}
2566 // one of those will never change
2570 begin
2571 {$IF DEFINED(D2F_DEBUG)}
2572 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2573 {$ENDIF}
2574 // new tile?
2576 begin
2579 // convert coords to map (to avoid ajdusting coords inside the loop)
2582 begin
2585 begin
2590 // constant coord should be inside
2593 begin
2595 // inside the proxy?
2598 begin
2599 // setup prev[xy]
2601 begin
2603 begin
2608 exit;
2610 end
2611 else
2612 begin
2614 {$IF DEFINED(D2F_DEBUG)}
2615 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]);
2616 {$ENDIF}
2618 begin
2623 exit;
2626 continue;
2628 // remember this hitpoint if it is nearer than an old one
2629 // setup prev[xy]
2631 begin
2632 // horizontal trace
2636 begin
2637 // going left
2641 end
2642 else
2643 begin
2644 // going right
2649 end
2650 else
2651 begin
2652 // vertical trace
2656 begin
2657 // going up
2661 end
2662 else
2663 begin
2664 // going down
2671 begin
2673 begin
2678 exit;
2680 end
2681 else
2682 begin
2684 {$IF DEFINED(D2F_DEBUG)}
2685 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]);
2686 {$ENDIF}
2688 begin
2698 // next cell
2702 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2704 // skip to next tile
2706 begin
2708 begin
2709 // to the right
2711 {$IF DEFINED(D2F_DEBUG)}
2713 {$ENDIF}
2717 end
2718 else
2719 begin
2720 // to the left
2722 {$IF DEFINED(D2F_DEBUG)}
2724 {$ENDIF}
2729 end
2730 else
2731 begin
2733 begin
2734 // to the down
2736 {$IF DEFINED(D2F_DEBUG)}
2738 {$ENDIF}
2742 end
2743 else
2744 begin
2745 // to the up
2747 {$IF DEFINED(D2F_DEBUG)}
2749 {$ENDIF}
2757 // we can travel less than one cell
2760 exit;
2762 {$ENDIF}
2764 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2765 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2766 {$ENDIF}
2768 //e_LogWritefln('*********************', []);
2770 // can omit checks
2772 begin
2773 // check cell(s)
2774 {$IF DEFINED(D2F_DEBUG)}
2775 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2776 {$ENDIF}
2777 // new tile?
2779 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2780 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);
2781 {$ENDIF}
2783 begin
2784 // yes
2785 {$IF DEFINED(D2F_DEBUG)}
2786 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2787 {$ENDIF}
2789 begin
2790 // signal cell completion
2792 begin
2793 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2794 end
2796 begin
2799 exit;
2805 // has something to process in this tile?
2807 begin
2808 // process cell
2810 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2811 // convert coords to map (to avoid ajdusting coords inside the loop)
2814 // process cell list
2816 begin
2819 begin
2824 begin
2825 // can we process this proxy?
2827 begin
2830 begin
2832 begin
2837 exit;
2839 end
2840 else
2841 begin
2842 // remember this hitpoint if it is nearer than an old one
2844 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2845 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);
2846 {$ENDIF}
2848 begin
2856 end
2857 else
2858 begin
2859 // this is possibly interesting proxy, set "has more to check" flag
2864 // next cell
2867 // still has something interesting in this cell?
2869 begin
2870 // nope, don't process this cell anymore; signal cell completion
2873 begin
2875 end
2877 begin
2880 exit;
2885 begin
2886 // move to cell edge, as we have nothing to trace here anymore
2889 //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]);
2891 begin
2892 // step
2895 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2898 //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]);
2901 //putPixel(xptr^, yptr^);
2902 // move coords
2908 // we can travel less than one cell
2910 begin
2912 end
2913 else
2914 begin