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
1733 begin
1742 // fix coords
1747 //tsize := mTileSize;
1755 // increase query counter
1758 begin
1759 // just in case of overflow
1763 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1766 // go on
1768 begin
1772 begin
1775 // process cells
1778 begin
1781 begin
1784 // shit. has to do it this way, so i can change tag in callback
1793 begin
1795 end
1796 else
1797 begin
1800 exit;
1812 // ////////////////////////////////////////////////////////////////////////// //
1813 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1814 var
1825 //px0, py0, px1, py1: Integer;
1826 begin
1837 // make query coords (0,0)-based
1849 // increase query counter
1852 begin
1853 // just in case of overflow
1859 repeat
1861 // check tile
1863 // process cells
1865 begin
1868 begin
1873 begin
1876 begin
1879 exit;
1883 // next cell
1886 // done processing cells, move to next tile
1893 // ////////////////////////////////////////////////////////////////////////// //
1894 // trace box with the given velocity; return object hit (if any)
1895 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1896 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1897 var
1908 begin
1922 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1928 // just in case
1934 // increase query counter
1937 begin
1938 // just in case of overflow
1945 begin
1947 begin
1950 begin
1953 begin
1958 begin
1961 begin
1964 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1966 begin
1971 begin
1975 exit;
1980 // next cell
1987 begin
1990 // just in case, compensate for floating point inexactness
1991 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1992 begin
2002 // ////////////////////////////////////////////////////////////////////////// //
2003 {.$DEFINE D2F_DEBUG_OTR}
2004 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2005 var
2016 {$IF DEFINED(D2F_DEBUG_OTR)}
2018 {$ENDIF}
2019 begin
2033 // offset query coords to (0,0)-based
2040 begin
2042 // vertical
2044 begin
2045 // down
2047 //if (ay0 < 0) then ay0 := 0;
2051 end
2052 else
2053 begin
2054 // up
2056 //if (ay1 < 0) then ay1 := 0;
2061 // check tile
2063 begin
2069 begin
2072 begin
2078 begin
2079 // bound c0 and c1 to cell
2082 // fill the thing
2083 {$IF DEFINED(D2F_DEBUG_OTR)}
2084 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)]);
2085 {$ENDIF}
2086 //assert(c0 <= c1);
2090 // next cell
2093 {$IF DEFINED(D2F_DEBUG_OTR)}
2094 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2098 {$ENDIF}
2099 // now go till we hit cell boundary or empty space
2101 begin
2102 // up
2104 begin
2105 {$IF DEFINED(D2F_DEBUG_OTR)}
2106 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2107 {$ENDIF}
2111 {$IF DEFINED(D2F_DEBUG_OTR)}
2112 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2113 {$ENDIF}
2115 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2116 end
2117 else
2118 begin
2119 // down
2125 end
2126 else
2127 begin
2128 // horizontal
2134 // ////////////////////////////////////////////////////////////////////////// //
2135 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2136 var
2138 begin
2143 // no callback: return `true` on the nearest hit
2144 // you are not supposed to understand this
2145 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2146 var
2161 begin
2171 // make query coords (0,0)-based
2187 // increase query counter
2190 begin
2191 // just in case of overflow
2197 repeat
2199 // check tile
2201 // process cells
2204 begin
2207 begin
2212 begin
2215 begin
2218 // get adjusted proxy coords
2223 // inside?
2225 begin
2226 // oops
2231 exit;
2233 // do line-vs-aabb test
2236 begin
2237 // hit detected
2241 begin
2246 // if this is not a first cell, get outta here
2253 // next cell
2256 // done processing cells; exit if we registered a hit
2257 // next cells can't have better candidates, obviously
2260 // move to next tile
2267 // ////////////////////////////////////////////////////////////////////////// //
2268 // no callback: return `true` on the nearest hit
2269 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2270 var
2272 begin
2277 // no callback: return `true` on the nearest hit
2278 // you are not supposed to understand this
2279 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2280 var
2306 //swapped: Boolean = false; // true: xd is yd, and vice versa
2307 // horizontal walker
2308 {$IFDEF GRID_USE_ORTHO_ACCEL}
2310 //wksign: Integer;
2312 {$ENDIF}
2313 // skipper
2315 begin
2324 begin
2327 begin
2330 exit;
2342 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2343 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);
2344 {$ENDIF}
2351 // offset query coords to (0,0)-based
2357 // clip rectange
2363 // horizontal setup
2365 begin
2366 // from left to right
2369 end
2370 else
2371 begin
2372 // from right to left
2382 // vertical setup
2384 begin
2385 // from top to bottom
2388 end
2389 else
2390 begin
2391 // from bottom to top
2405 begin
2406 //swapped := true;
2415 end
2416 else
2417 begin
2431 begin
2432 // clip at top
2438 begin
2441 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2448 begin
2449 // clip at left
2460 begin
2461 // clip at bottom
2471 //if (term = xd) then exit; // this is the only point, get out of here
2477 // first move, to skip starting point
2478 // DON'T DO THIS! loop will take care of that
2480 begin
2481 //FIXME!
2484 begin
2486 begin
2488 begin
2491 end
2492 else
2493 begin
2496 end
2497 else
2498 begin
2503 exit;
2508 (*
2509 // move coords
2510 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2511 xd += stx;
2512 // done?
2513 if (xd = term) then exit;
2514 *)
2516 {$IF DEFINED(D2F_DEBUG)}
2517 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2518 {$ENDIF}
2519 // DON'T DO THIS! loop will take care of that
2520 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2521 //ccidx := mGrid[lastGA];
2523 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2524 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2525 {$ENDIF}
2527 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2532 // increase query counter
2535 begin
2536 // just in case of overflow
2542 {$IFDEF GRID_USE_ORTHO_ACCEL}
2543 // if this is strict horizontal/vertical trace, use optimized codepath
2545 begin
2546 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2547 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2548 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2549 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2551 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2552 {$IF DEFINED(D2F_DEBUG)}
2554 {$ENDIF}
2556 // one of those will never change
2560 begin
2561 {$IF DEFINED(D2F_DEBUG)}
2562 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2563 {$ENDIF}
2564 // new tile?
2566 begin
2569 // convert coords to map (to avoid ajdusting coords inside the loop)
2572 begin
2575 begin
2580 // constant coord should be inside
2583 begin
2585 // inside the proxy?
2588 begin
2589 // setup prev[xy]
2591 begin
2593 begin
2598 exit;
2600 end
2601 else
2602 begin
2604 {$IF DEFINED(D2F_DEBUG)}
2605 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]);
2606 {$ENDIF}
2608 begin
2613 exit;
2616 continue;
2618 // remember this hitpoint if it is nearer than an old one
2619 // setup prev[xy]
2621 begin
2622 // horizontal trace
2626 begin
2627 // going left
2631 end
2632 else
2633 begin
2634 // going right
2639 end
2640 else
2641 begin
2642 // vertical trace
2646 begin
2647 // going up
2651 end
2652 else
2653 begin
2654 // going down
2661 begin
2663 begin
2668 exit;
2670 end
2671 else
2672 begin
2674 {$IF DEFINED(D2F_DEBUG)}
2675 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]);
2676 {$ENDIF}
2678 begin
2688 // next cell
2692 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2694 // skip to next tile
2696 begin
2698 begin
2699 // to the right
2701 {$IF DEFINED(D2F_DEBUG)}
2703 {$ENDIF}
2707 end
2708 else
2709 begin
2710 // to the left
2712 {$IF DEFINED(D2F_DEBUG)}
2714 {$ENDIF}
2719 end
2720 else
2721 begin
2723 begin
2724 // to the down
2726 {$IF DEFINED(D2F_DEBUG)}
2728 {$ENDIF}
2732 end
2733 else
2734 begin
2735 // to the up
2737 {$IF DEFINED(D2F_DEBUG)}
2739 {$ENDIF}
2747 // we can travel less than one cell
2750 exit;
2752 {$ENDIF}
2754 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2755 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2756 {$ENDIF}
2758 //e_LogWritefln('*********************', []);
2760 // can omit checks
2762 begin
2763 // check cell(s)
2764 {$IF DEFINED(D2F_DEBUG)}
2765 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2766 {$ENDIF}
2767 // new tile?
2769 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2770 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);
2771 {$ENDIF}
2773 begin
2774 // yes
2775 {$IF DEFINED(D2F_DEBUG)}
2776 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2777 {$ENDIF}
2779 begin
2780 // signal cell completion
2782 begin
2783 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2784 end
2786 begin
2789 exit;
2795 // has something to process in this tile?
2797 begin
2798 // process cell
2800 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2801 // convert coords to map (to avoid ajdusting coords inside the loop)
2804 // process cell list
2806 begin
2809 begin
2814 begin
2815 // can we process this proxy?
2817 begin
2820 begin
2822 begin
2827 exit;
2829 end
2830 else
2831 begin
2832 // remember this hitpoint if it is nearer than an old one
2834 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2835 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);
2836 {$ENDIF}
2838 begin
2846 end
2847 else
2848 begin
2849 // this is possibly interesting proxy, set "has more to check" flag
2854 // next cell
2857 // still has something interesting in this cell?
2859 begin
2860 // nope, don't process this cell anymore; signal cell completion
2863 begin
2865 end
2867 begin
2870 exit;
2875 begin
2876 // move to cell edge, as we have nothing to trace here anymore
2879 //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]);
2881 begin
2882 // step
2885 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2888 //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]);
2891 //putPixel(xptr^, yptr^);
2892 // move coords
2898 // we can travel less than one cell
2900 begin
2902 end
2903 else
2904 begin