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
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 traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
198 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
200 //WARNING: don't modify grid while any query is in progress (no checks are made!)
201 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
202 // cb with `(nil)` will be called before processing new tile
203 // no callback: return object of the nearest hit or nil
204 // if `inverted` is true, trace will register bodies *exluding* tagmask
205 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
206 //WARNING: don't change tags in callbacks here!
207 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
208 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
210 // return `false` if we're still inside at the end
211 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
212 // `true`: endpoint will point at the last "inside" pixel
213 // `false`: endpoint will be (ax1, ay1)
214 //WARNING: don't change tags in callbacks here!
215 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
217 //WARNING: don't modify grid while any query is in progress (no checks are made!)
218 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
219 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
220 //WARNING: don't change tags in callbacks here!
221 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
223 // trace box with the given velocity; return object hit (if any)
224 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
225 //WARNING: don't change tags in callbacks here!
226 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
228 // debug
233 public
234 //WARNING! no sanity checks!
246 type
247 // common structure for all line tracers
249 public
252 private
259 //xptr, yptr: PInteger;
262 public
263 // call `setyp` after this
268 // this will use `w[xy][01]` to clip coords
269 // return `false` if the whole line was clipped away
270 // on `true`, you should process first point, and go on
273 // call this *after* doing a step
274 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
277 // as you will prolly call `done()` after doing a step anyway, this will do it for you
278 // move to next point, return `true` when the line is complete (i.e. you should stop)
281 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
284 // hack for line-vs-aabb; NOT PROPERLY TESTED!
287 // current coords
293 // move directions; always [-1..1] (can be zero!)
299 // you are not supposed to understand this
300 // returns `true` if there is an intersection, and enter coords
301 // enter coords will be equal to (x0, y0) if starting point is inside the box
302 // if result is `false`, `inx` and `iny` are undefined
303 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
305 // sweep two AABB's to see if and when they are overlapping
306 // returns `true` if collision was detected (but boxes doesn't overlap)
307 // u1 and u1 has no sense if no collision was detected
308 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
309 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
310 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
311 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
312 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
318 //function minInt (a, b: Integer): Integer; inline;
319 //function maxInt (a, b: Integer): Integer; inline;
322 implementation
324 uses
328 // ////////////////////////////////////////////////////////////////////////// //
329 //procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
330 procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
331 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
332 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
334 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
337 // ////////////////////////////////////////////////////////////////////////// //
339 begin
344 begin
345 // clip rectange
355 begin
362 var
369 begin
377 // ortho?
379 begin
380 // only xd
381 //assert(lsty <> 0);
383 begin
384 // xd: to left edge
387 exit;
388 end
389 else
390 begin
391 // xd: to right edge
394 exit;
398 // not ortho
399 //assert(lstx <> 0); // invariant
406 // calculate xwalk
408 begin
411 end
412 else
413 begin
418 // calculate ywalk
420 begin
423 end
424 else
425 begin
431 begin
432 // in which dir we want to walk?
434 // walk x
436 begin
439 end
440 else
441 begin
445 // walk y
451 //assert((xd div TileSize <> lxd div TileSize) or (yd div TileSize <> lyd div TileSize));
457 // NOT TESTED!
459 begin
460 //writeln('e=', e, '; dx2=', dx2, '; dy2=', dy2);
462 begin
465 end
466 else
467 begin
473 function TLineWalker.x (): Integer; inline; begin if xyswapped then result := yd else result := xd; end;
474 function TLineWalker.y (): Integer; inline; begin if xyswapped then result := xd else result := yd; end;
475 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;
477 function TLineWalker.dx (): Integer; inline; begin if xyswapped then result := stx else result := sty; end;
478 function TLineWalker.dy (): Integer; inline; begin if xyswapped then result := sty else result := stx; end;
481 procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
482 var
487 begin
491 // horizontal setup
493 begin
494 // from left to right
497 end
498 else
499 begin
500 // from right to left
510 // vertical setup
512 begin
513 // from top to bottom
516 end
517 else
518 begin
519 // from bottom to top
533 begin
535 //xptr := @yd;
536 //yptr := @xd;
543 end
544 else
545 begin
546 //xptr := @xd;
547 //yptr := @yd;
559 begin
560 // clip at top
566 begin
569 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
576 begin
577 // clip at left
588 begin
589 // clip at bottom
599 //if (term = xd) then exit; // this is the only point, get out of here
609 // ////////////////////////////////////////////////////////////////////////// //
610 // you are not supposed to understand this
611 // returns `true` if there is an intersection, and enter coords
612 // enter coords will be equal to (x0, y0) if starting point is inside the box
613 // if result is `false`, `inx` and `iny` are undefined
614 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
615 var
623 //!term: Integer;
627 begin
629 // why not
635 begin
636 // check this point
638 exit;
641 // check if staring point is inside the box
642 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
644 // clip rectange
650 // horizontal setup
652 begin
653 // from left to right
656 end
657 else
658 begin
659 // from right to left
669 // vertical setup
671 begin
672 // from top to bottom
675 end
676 else
677 begin
678 // from bottom to top
692 begin
701 end
702 else
703 begin
713 //!term := x1;
717 begin
718 // clip at top
724 begin
727 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
734 begin
735 // clip at left
745 (*
746 if (y1 > wy1) then
747 begin
748 // clip at bottom
749 temp := dx2*(wy1-y0)+dsx;
750 term := x0+temp div dy2;
751 rem := temp mod dy2;
752 if (rem = 0) then Dec(term);
753 end;
755 if (term > wx1) then term := wx1; // clip at right
757 Inc(term); // draw last point
758 //if (term = xd) then exit; // this is the only point, get out of here
759 *)
763 //!dx2 -= dy2;
771 // ////////////////////////////////////////////////////////////////////////// //
772 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
774 var
778 var
780 begin
784 begin
788 end
790 begin
797 begin
800 end
802 begin
810 var
813 begin
826 // check if they are overlapping right now (SAT)
827 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
831 // treat b as stationary, so invert v to get relative velocity
845 begin
851 // ////////////////////////////////////////////////////////////////////////// //
852 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
853 begin
866 begin
871 begin
876 begin
881 begin
886 begin
891 begin
896 // ////////////////////////////////////////////////////////////////////////// //
897 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
898 begin
907 begin
909 begin
911 begin
915 exit;
925 begin
930 // ////////////////////////////////////////////////////////////////////////// //
931 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
932 var
934 begin
936 {$IF DEFINED(D2F_DEBUG)}
938 {$ENDIF}
939 {
940 if aTileSize < 1 then aTileSize := 1;
941 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
942 mTileSize := aTileSize;
943 }
954 // init free list
956 begin
962 // init grid
964 // init proxies
972 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
977 begin
985 // ////////////////////////////////////////////////////////////////////////// //
987 var
989 begin
992 begin
996 begin
1002 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);
1007 var
1010 begin
1013 begin
1016 begin
1019 begin
1021 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
1023 // next cell
1031 var
1034 begin
1042 begin
1045 begin
1047 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
1049 // next cell
1055 // ////////////////////////////////////////////////////////////////////////// //
1056 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
1057 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
1061 begin
1062 // fix coords
1070 begin
1072 begin
1075 end
1076 else
1077 begin
1086 begin
1088 begin
1091 end
1092 else
1093 begin
1101 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
1102 begin
1104 begin
1107 end
1108 else
1109 begin
1120 // ////////////////////////////////////////////////////////////////////////// //
1122 begin
1123 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1128 begin
1130 begin
1132 begin
1134 end
1135 else
1136 begin
1144 begin
1149 // ////////////////////////////////////////////////////////////////////////// //
1151 var
1154 begin
1156 begin
1157 // no free cells, want more
1161 begin
1173 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1178 begin
1180 begin
1182 begin
1193 // ////////////////////////////////////////////////////////////////////////// //
1194 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1195 var
1198 begin
1200 begin
1201 // no free proxies, resize list
1208 // get one from list
1213 // add to used list
1215 // statistics
1221 begin
1223 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1224 // add to free list
1232 // ////////////////////////////////////////////////////////////////////////// //
1233 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1234 var
1237 begin
1240 // fix coords
1243 // go on
1247 //tsize := mTileSize;
1250 begin
1254 begin
1264 // ////////////////////////////////////////////////////////////////////////// //
1266 var
1271 begin
1273 // add body to the given grid cell
1276 begin
1277 {$IF DEFINED(D2F_DEBUG)}
1280 begin
1283 begin
1285 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1289 {$ENDIF}
1292 begin
1294 // check "has room" flag
1296 begin
1297 // can add here
1299 begin
1301 begin
1304 exit;
1309 // no room, go to next cell in list (if there is any)
1312 // no room in cells, add new cell to list
1314 // either no room, or no cell at all
1324 var
1326 begin
1333 // assume that we cannot have one object added to bucket twice
1335 var
1339 begin
1341 // find and remove cell
1345 begin
1348 begin
1350 begin
1351 // i found her!
1353 begin
1354 // this cell contains no elements, remove it
1357 exit;
1359 // remove element from bucket
1361 begin
1366 exit;
1375 var
1377 begin
1384 // ////////////////////////////////////////////////////////////////////////// //
1385 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1386 begin
1394 begin
1401 // ////////////////////////////////////////////////////////////////////////// //
1403 var
1406 begin
1413 {$IF DEFINED(D2F_DEBUG_MOVER)}
1414 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);
1415 {$ENDIF}
1417 // map -> grid
1422 // did any corner crossed tile boundary?
1427 begin
1434 end
1435 else
1436 begin
1444 //TODO: optimize for horizontal/vertical moves
1446 var
1454 begin
1456 // check if tile coords was changed
1461 // map -> grid
1466 // check for heavy work
1477 {$IF DEFINED(D2F_DEBUG_MOVER)}
1478 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);
1479 {$ENDIF}
1481 begin
1482 // crossed tile boundary, do heavy work
1485 // cycle with old rect, remove body where it is necessary
1486 // optimized for horizontal moves
1487 {$IF DEFINED(D2F_DEBUG_MOVER)}
1488 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);
1489 {$ENDIF}
1490 // remove stale marks
1493 begin
1498 {$IF DEFINED(D2F_DEBUG_MOVER)}
1500 {$ENDIF}
1502 begin
1504 begin
1505 // this column is completely outside of new rect
1507 begin
1508 {$IF DEFINED(D2F_DEBUG_MOVER)}
1510 {$ENDIF}
1513 end
1514 else
1515 begin
1516 // heavy checks
1518 begin
1520 begin
1521 {$IF DEFINED(D2F_DEBUG_MOVER)}
1523 {$ENDIF}
1530 // cycle with new rect, add body where it is necessary
1533 begin
1538 {$IF DEFINED(D2F_DEBUG_MOVER)}
1540 {$ENDIF}
1542 begin
1544 begin
1545 // this column is completely outside of old rect
1547 begin
1548 {$IF DEFINED(D2F_DEBUG_MOVER)}
1550 {$ENDIF}
1553 end
1554 else
1555 begin
1556 // heavy checks
1558 begin
1560 begin
1561 {$IF DEFINED(D2F_DEBUG_MOVER)}
1563 {$ENDIF}
1570 // done
1571 end
1572 else
1573 begin
1574 {$IF DEFINED(D2F_DEBUG_MOVER)}
1575 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);
1576 {$ENDIF}
1578 // update coordinates
1584 var
1587 begin
1589 // check if tile coords was changed
1595 {$IF DEFINED(D2F_DEBUG_MOVER)}
1596 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);
1597 {$ENDIF}
1600 begin
1601 // crossed tile boundary, do heavy work
1606 end
1607 else
1608 begin
1609 // nothing to do with the grid, just fix size
1616 // ////////////////////////////////////////////////////////////////////////// //
1618 var
1620 begin
1623 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1628 // ////////////////////////////////////////////////////////////////////////// //
1629 // no callback: return `true` on the first hit
1630 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1631 var
1638 begin
1644 {$IF DEFINED(D2F_DEBUG_XXQ)}
1646 {$ENDIF}
1648 // make coords (0,0)-based
1655 {$IF DEFINED(D2F_DEBUG_XXQ)}
1656 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);
1657 {$ENDIF}
1659 // restore coords
1663 // increase query counter
1666 begin
1667 // just in case of overflow
1673 {$IF DEFINED(D2F_DEBUG_XXQ)}
1674 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1675 {$ENDIF}
1678 begin
1679 {$IF DEFINED(D2F_DEBUG_XXQ)}
1681 {$ENDIF}
1684 begin
1687 {$IF DEFINED(D2F_DEBUG_XXQ)}
1688 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);
1689 {$ENDIF}
1690 // shit. has to do it this way, so i can change tag in callback
1692 begin
1697 begin
1699 begin
1701 begin
1704 exit;
1706 end
1707 else
1708 begin
1711 exit;
1721 // ////////////////////////////////////////////////////////////////////////// //
1722 // no callback: return `true` on the first hit
1723 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1724 var
1735 begin
1744 // fix coords
1749 //tsize := mTileSize;
1757 // increase query counter
1760 begin
1761 // just in case of overflow
1765 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1768 // go on
1770 begin
1774 begin
1777 // process cells
1780 begin
1783 begin
1786 // shit. has to do it this way, so i can change tag in callback
1795 begin
1797 end
1798 else
1799 begin
1802 exit;
1814 // ////////////////////////////////////////////////////////////////////////// //
1815 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1816 var
1827 //px0, py0, px1, py1: Integer;
1828 begin
1839 // make query coords (0,0)-based
1851 // increase query counter
1854 begin
1855 // just in case of overflow
1861 repeat
1863 // check tile
1865 // process cells
1867 begin
1870 begin
1875 begin
1878 begin
1881 exit;
1885 // next cell
1888 // done processing cells, move to next tile
1895 // ////////////////////////////////////////////////////////////////////////// //
1896 // trace box with the given velocity; return object hit (if any)
1897 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1898 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1899 var
1910 begin
1924 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1930 // just in case
1936 // increase query counter
1939 begin
1940 // just in case of overflow
1947 begin
1949 begin
1952 begin
1955 begin
1960 begin
1963 begin
1966 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1968 begin
1973 begin
1977 exit;
1982 // next cell
1989 begin
1992 // just in case, compensate for floating point inexactness
1993 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1994 begin
2004 // ////////////////////////////////////////////////////////////////////////// //
2005 {.$DEFINE D2F_DEBUG_OTR}
2006 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2007 var
2018 {$IF DEFINED(D2F_DEBUG_OTR)}
2020 {$ENDIF}
2021 begin
2035 // offset query coords to (0,0)-based
2042 begin
2044 // vertical
2046 begin
2047 // down
2049 //if (ay0 < 0) then ay0 := 0;
2053 end
2054 else
2055 begin
2056 // up
2058 //if (ay1 < 0) then ay1 := 0;
2063 // check tile
2065 begin
2071 begin
2074 begin
2080 begin
2081 // bound c0 and c1 to cell
2084 // fill the thing
2085 {$IF DEFINED(D2F_DEBUG_OTR)}
2086 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)]);
2087 {$ENDIF}
2088 //assert(c0 <= c1);
2092 // next cell
2095 {$IF DEFINED(D2F_DEBUG_OTR)}
2096 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2100 {$ENDIF}
2101 // now go till we hit cell boundary or empty space
2103 begin
2104 // up
2106 begin
2107 {$IF DEFINED(D2F_DEBUG_OTR)}
2108 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2109 {$ENDIF}
2113 {$IF DEFINED(D2F_DEBUG_OTR)}
2114 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2115 {$ENDIF}
2117 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2118 end
2119 else
2120 begin
2121 // down
2127 end
2128 else
2129 begin
2130 // horizontal
2136 // ////////////////////////////////////////////////////////////////////////// //
2137 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2138 var
2140 begin
2145 // no callback: return `true` on the nearest hit
2146 // you are not supposed to understand this
2147 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2148 var
2163 begin
2173 // make query coords (0,0)-based
2189 // increase query counter
2192 begin
2193 // just in case of overflow
2199 repeat
2201 // check tile
2203 // process cells
2206 begin
2209 begin
2214 begin
2217 begin
2220 // get adjusted proxy coords
2225 // inside?
2227 begin
2228 // oops
2233 exit;
2235 // do line-vs-aabb test
2238 begin
2239 // hit detected
2243 begin
2248 // if this is not a first cell, get outta here
2255 // next cell
2258 // done processing cells; exit if we registered a hit
2259 // next cells can't have better candidates, obviously
2262 // move to next tile
2269 // ////////////////////////////////////////////////////////////////////////// //
2270 // no callback: return `true` on the nearest hit
2271 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2272 var
2274 begin
2279 // no callback: return `true` on the nearest hit
2280 // you are not supposed to understand this
2281 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2282 var
2308 //swapped: Boolean = false; // true: xd is yd, and vice versa
2309 // horizontal walker
2310 {$IFDEF GRID_USE_ORTHO_ACCEL}
2312 //wksign: Integer;
2314 {$ENDIF}
2315 // skipper
2317 begin
2326 begin
2329 begin
2332 exit;
2344 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2345 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);
2346 {$ENDIF}
2353 // offset query coords to (0,0)-based
2359 // clip rectange
2365 // horizontal setup
2367 begin
2368 // from left to right
2371 end
2372 else
2373 begin
2374 // from right to left
2384 // vertical setup
2386 begin
2387 // from top to bottom
2390 end
2391 else
2392 begin
2393 // from bottom to top
2407 begin
2408 //swapped := true;
2417 end
2418 else
2419 begin
2433 begin
2434 // clip at top
2440 begin
2443 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2450 begin
2451 // clip at left
2462 begin
2463 // clip at bottom
2473 //if (term = xd) then exit; // this is the only point, get out of here
2479 // first move, to skip starting point
2480 // DON'T DO THIS! loop will take care of that
2482 begin
2483 //FIXME!
2486 begin
2488 begin
2490 begin
2493 end
2494 else
2495 begin
2498 end
2499 else
2500 begin
2505 exit;
2510 (*
2511 // move coords
2512 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2513 xd += stx;
2514 // done?
2515 if (xd = term) then exit;
2516 *)
2518 {$IF DEFINED(D2F_DEBUG)}
2519 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2520 {$ENDIF}
2521 // DON'T DO THIS! loop will take care of that
2522 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2523 //ccidx := mGrid[lastGA];
2525 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2526 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2527 {$ENDIF}
2529 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2534 // increase query counter
2537 begin
2538 // just in case of overflow
2544 {$IFDEF GRID_USE_ORTHO_ACCEL}
2545 // if this is strict horizontal/vertical trace, use optimized codepath
2547 begin
2548 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2549 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2550 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2551 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2553 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2554 {$IF DEFINED(D2F_DEBUG)}
2556 {$ENDIF}
2558 // one of those will never change
2562 begin
2563 {$IF DEFINED(D2F_DEBUG)}
2564 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2565 {$ENDIF}
2566 // new tile?
2568 begin
2571 // convert coords to map (to avoid ajdusting coords inside the loop)
2574 begin
2577 begin
2582 // constant coord should be inside
2585 begin
2587 // inside the proxy?
2590 begin
2591 // setup prev[xy]
2593 begin
2595 begin
2600 exit;
2602 end
2603 else
2604 begin
2606 {$IF DEFINED(D2F_DEBUG)}
2607 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]);
2608 {$ENDIF}
2610 begin
2615 exit;
2618 continue;
2620 // remember this hitpoint if it is nearer than an old one
2621 // setup prev[xy]
2623 begin
2624 // horizontal trace
2628 begin
2629 // going left
2633 end
2634 else
2635 begin
2636 // going right
2641 end
2642 else
2643 begin
2644 // vertical trace
2648 begin
2649 // going up
2653 end
2654 else
2655 begin
2656 // going down
2663 begin
2665 begin
2670 exit;
2672 end
2673 else
2674 begin
2676 {$IF DEFINED(D2F_DEBUG)}
2677 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]);
2678 {$ENDIF}
2680 begin
2690 // next cell
2694 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2696 // skip to next tile
2698 begin
2700 begin
2701 // to the right
2703 {$IF DEFINED(D2F_DEBUG)}
2705 {$ENDIF}
2709 end
2710 else
2711 begin
2712 // to the left
2714 {$IF DEFINED(D2F_DEBUG)}
2716 {$ENDIF}
2721 end
2722 else
2723 begin
2725 begin
2726 // to the down
2728 {$IF DEFINED(D2F_DEBUG)}
2730 {$ENDIF}
2734 end
2735 else
2736 begin
2737 // to the up
2739 {$IF DEFINED(D2F_DEBUG)}
2741 {$ENDIF}
2749 // we can travel less than one cell
2752 exit;
2754 {$ENDIF}
2756 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2757 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2758 {$ENDIF}
2760 //e_LogWritefln('*********************', []);
2762 // can omit checks
2764 begin
2765 // check cell(s)
2766 {$IF DEFINED(D2F_DEBUG)}
2767 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2768 {$ENDIF}
2769 // new tile?
2771 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2772 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);
2773 {$ENDIF}
2775 begin
2776 // yes
2777 {$IF DEFINED(D2F_DEBUG)}
2778 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2779 {$ENDIF}
2781 begin
2782 // signal cell completion
2784 begin
2785 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2786 end
2788 begin
2791 exit;
2797 // has something to process in this tile?
2799 begin
2800 // process cell
2802 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2803 // convert coords to map (to avoid ajdusting coords inside the loop)
2806 // process cell list
2808 begin
2811 begin
2816 begin
2817 // can we process this proxy?
2819 begin
2822 begin
2824 begin
2829 exit;
2831 end
2832 else
2833 begin
2834 // remember this hitpoint if it is nearer than an old one
2836 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2837 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);
2838 {$ENDIF}
2840 begin
2848 end
2849 else
2850 begin
2851 // this is possibly interesting proxy, set "has more to check" flag
2856 // next cell
2859 // still has something interesting in this cell?
2861 begin
2862 // nope, don't process this cell anymore; signal cell completion
2865 begin
2867 end
2869 begin
2872 exit;
2877 begin
2878 // move to cell edge, as we have nothing to trace here anymore
2881 //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]);
2883 begin
2884 // step
2887 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2890 //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]);
2893 //putPixel(xptr^, yptr^);
2894 // move coords
2900 // we can travel less than one cell
2902 begin
2904 end
2905 else
2906 begin