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 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
331 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
333 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
336 // ////////////////////////////////////////////////////////////////////////// //
338 begin
343 begin
344 // clip rectange
354 begin
360 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
362 var
364 begin
367 //writeln('stx=', stx, '; sty=', sty);
369 // ortho?
371 begin
372 // only xd
375 begin
376 // xd: to left edge
379 exit;
380 end
381 else
382 begin
383 // xd: to right edge
386 exit;
392 // not ortho
395 //FIXME: do some math to avoid single-stepping
397 begin
398 // xd: to left edge
402 end
403 else
404 begin
405 // xd: to right edge
411 //writeln('xd=', xd, '; yd=', yd, '; ex=', ex, '; ey=', ey, '; term=', term, '; wklen=', wklen);
414 begin
415 // do step
425 // NOT TESTED!
427 begin
428 //writeln('e=', e, '; dx2=', dx2, '; dy2=', dy2);
430 begin
433 end
434 else
435 begin
441 function TLineWalker.x (): Integer; inline; begin if xyswapped then result := yd else result := xd; end;
442 function TLineWalker.y (): Integer; inline; begin if xyswapped then result := xd else result := yd; end;
443 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;
445 function TLineWalker.dx (): Integer; inline; begin if xyswapped then result := stx else result := sty; end;
446 function TLineWalker.dy (): Integer; inline; begin if xyswapped then result := sty else result := stx; end;
449 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
450 var
455 begin
459 // horizontal setup
461 begin
462 // from left to right
465 end
466 else
467 begin
468 // from right to left
478 // vertical setup
480 begin
481 // from top to bottom
484 end
485 else
486 begin
487 // from bottom to top
501 begin
503 //xptr := @yd;
504 //yptr := @xd;
511 end
512 else
513 begin
514 //xptr := @xd;
515 //yptr := @yd;
527 begin
528 // clip at top
534 begin
543 begin
544 // clip at left
555 begin
556 // clip at bottom
566 //if (term = xd) then exit; // this is the only point, get out of here
576 // ////////////////////////////////////////////////////////////////////////// //
577 // you are not supposed to understand this
578 // returns `true` if there is an intersection, and enter coords
579 // enter coords will be equal to (x0, y0) if starting point is inside the box
580 // if result is `false`, `inx` and `iny` are undefined
581 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
582 var
590 //!term: Integer;
594 begin
596 // why not
602 begin
603 // check this point
605 exit;
608 // check if staring point is inside the box
609 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
611 // clip rectange
617 // horizontal setup
619 begin
620 // from left to right
623 end
624 else
625 begin
626 // from right to left
636 // vertical setup
638 begin
639 // from top to bottom
642 end
643 else
644 begin
645 // from bottom to top
659 begin
668 end
669 else
670 begin
680 //!term := x1;
684 begin
685 // clip at top
691 begin
700 begin
701 // clip at left
711 (*
712 if (y1 > wy1) then
713 begin
714 // clip at bottom
715 temp := dx2*(wy1-y0)+dsx;
716 term := x0+temp div dy2;
717 rem := temp mod dy2;
718 if (rem = 0) then Dec(term);
719 end;
721 if (term > wx1) then term := wx1; // clip at right
723 Inc(term); // draw last point
724 //if (term = xd) then exit; // this is the only point, get out of here
725 *)
729 //!dx2 -= dy2;
737 // ////////////////////////////////////////////////////////////////////////// //
738 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
740 var
744 var
746 begin
750 begin
754 end
756 begin
763 begin
766 end
768 begin
776 var
779 begin
792 // check if they are overlapping right now (SAT)
793 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
797 // treat b as stationary, so invert v to get relative velocity
811 begin
817 // ////////////////////////////////////////////////////////////////////////// //
818 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
819 begin
832 begin
837 begin
842 begin
847 begin
852 begin
857 begin
862 // ////////////////////////////////////////////////////////////////////////// //
863 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
864 begin
873 begin
875 begin
877 begin
881 exit;
891 begin
896 // ////////////////////////////////////////////////////////////////////////// //
897 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
898 var
900 begin
902 {$IF DEFINED(D2F_DEBUG)}
904 {$ENDIF}
905 {
906 if aTileSize < 1 then aTileSize := 1;
907 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
908 mTileSize := aTileSize;
909 }
920 // init free list
922 begin
928 // init grid
930 // init proxies
938 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
943 begin
951 // ////////////////////////////////////////////////////////////////////////// //
953 var
955 begin
958 begin
962 begin
968 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);
973 var
976 begin
979 begin
982 begin
985 begin
987 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
989 // next cell
997 var
1000 begin
1008 begin
1011 begin
1013 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
1015 // next cell
1021 // ////////////////////////////////////////////////////////////////////////// //
1022 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
1023 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
1027 begin
1028 // fix coords
1036 begin
1038 begin
1041 end
1042 else
1043 begin
1052 begin
1054 begin
1057 end
1058 else
1059 begin
1067 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
1068 begin
1070 begin
1073 end
1074 else
1075 begin
1086 // ////////////////////////////////////////////////////////////////////////// //
1088 begin
1089 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1094 begin
1096 begin
1098 begin
1100 end
1101 else
1102 begin
1110 begin
1115 // ////////////////////////////////////////////////////////////////////////// //
1117 var
1120 begin
1122 begin
1123 // no free cells, want more
1127 begin
1139 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1144 begin
1146 begin
1148 begin
1159 // ////////////////////////////////////////////////////////////////////////// //
1160 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1161 var
1164 begin
1166 begin
1167 // no free proxies, resize list
1174 // get one from list
1179 // add to used list
1181 // statistics
1187 begin
1189 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1190 // add to free list
1198 // ////////////////////////////////////////////////////////////////////////// //
1199 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1200 const
1202 var
1205 begin
1208 // fix coords
1211 // go on
1215 //tsize := mTileSize;
1218 begin
1222 begin
1232 // ////////////////////////////////////////////////////////////////////////// //
1234 var
1239 begin
1241 // add body to the given grid cell
1244 begin
1245 {$IF DEFINED(D2F_DEBUG)}
1248 begin
1251 begin
1253 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1257 {$ENDIF}
1260 begin
1262 // check "has room" flag
1264 begin
1265 // can add here
1267 begin
1269 begin
1272 exit;
1277 // no room, go to next cell in list (if there is any)
1280 // no room in cells, add new cell to list
1282 // either no room, or no cell at all
1292 var
1294 begin
1301 // assume that we cannot have one object added to bucket twice
1303 var
1307 begin
1309 // find and remove cell
1313 begin
1316 begin
1318 begin
1319 // i found her!
1321 begin
1322 // this cell contains no elements, remove it
1325 exit;
1327 // remove element from bucket
1329 begin
1334 exit;
1343 var
1345 begin
1352 // ////////////////////////////////////////////////////////////////////////// //
1353 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1354 begin
1362 begin
1369 // ////////////////////////////////////////////////////////////////////////// //
1371 var
1374 begin
1381 {$IF DEFINED(D2F_DEBUG_MOVER)}
1382 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);
1383 {$ENDIF}
1385 // map -> grid
1390 // did any corner crossed tile boundary?
1395 begin
1402 end
1403 else
1404 begin
1412 //TODO: optimize for horizontal/vertical moves
1414 var
1422 begin
1424 // check if tile coords was changed
1429 // map -> grid
1434 // check for heavy work
1445 {$IF DEFINED(D2F_DEBUG_MOVER)}
1446 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);
1447 {$ENDIF}
1449 begin
1450 // crossed tile boundary, do heavy work
1453 // cycle with old rect, remove body where it is necessary
1454 // optimized for horizontal moves
1455 {$IF DEFINED(D2F_DEBUG_MOVER)}
1456 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);
1457 {$ENDIF}
1458 // remove stale marks
1461 begin
1466 {$IF DEFINED(D2F_DEBUG_MOVER)}
1468 {$ENDIF}
1470 begin
1472 begin
1473 // this column is completely outside of new rect
1475 begin
1476 {$IF DEFINED(D2F_DEBUG_MOVER)}
1478 {$ENDIF}
1481 end
1482 else
1483 begin
1484 // heavy checks
1486 begin
1488 begin
1489 {$IF DEFINED(D2F_DEBUG_MOVER)}
1491 {$ENDIF}
1498 // cycle with new rect, add body where it is necessary
1501 begin
1506 {$IF DEFINED(D2F_DEBUG_MOVER)}
1508 {$ENDIF}
1510 begin
1512 begin
1513 // this column is completely outside of old rect
1515 begin
1516 {$IF DEFINED(D2F_DEBUG_MOVER)}
1518 {$ENDIF}
1521 end
1522 else
1523 begin
1524 // heavy checks
1526 begin
1528 begin
1529 {$IF DEFINED(D2F_DEBUG_MOVER)}
1531 {$ENDIF}
1538 // done
1539 end
1540 else
1541 begin
1542 {$IF DEFINED(D2F_DEBUG_MOVER)}
1543 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);
1544 {$ENDIF}
1546 // update coordinates
1552 var
1555 begin
1557 // check if tile coords was changed
1563 {$IF DEFINED(D2F_DEBUG_MOVER)}
1564 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);
1565 {$ENDIF}
1568 begin
1569 // crossed tile boundary, do heavy work
1574 end
1575 else
1576 begin
1577 // nothing to do with the grid, just fix size
1584 // ////////////////////////////////////////////////////////////////////////// //
1586 var
1588 begin
1591 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1596 // ////////////////////////////////////////////////////////////////////////// //
1597 // no callback: return `true` on the first hit
1598 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1599 var
1606 begin
1612 {$IF DEFINED(D2F_DEBUG_XXQ)}
1614 {$ENDIF}
1616 // make coords (0,0)-based
1623 {$IF DEFINED(D2F_DEBUG_XXQ)}
1624 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);
1625 {$ENDIF}
1627 // restore coords
1631 // increase query counter
1634 begin
1635 // just in case of overflow
1641 {$IF DEFINED(D2F_DEBUG_XXQ)}
1642 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1643 {$ENDIF}
1646 begin
1647 {$IF DEFINED(D2F_DEBUG_XXQ)}
1649 {$ENDIF}
1652 begin
1655 {$IF DEFINED(D2F_DEBUG_XXQ)}
1656 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);
1657 {$ENDIF}
1658 // shit. has to do it this way, so i can change tag in callback
1660 begin
1665 begin
1667 begin
1669 begin
1672 exit;
1674 end
1675 else
1676 begin
1679 exit;
1689 // ////////////////////////////////////////////////////////////////////////// //
1690 // no callback: return `true` on the first hit
1691 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1692 const
1694 var
1705 begin
1714 // fix coords
1719 //tsize := mTileSize;
1727 // increase query counter
1730 begin
1731 // just in case of overflow
1735 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1738 // go on
1740 begin
1744 begin
1747 // process cells
1750 begin
1753 begin
1756 // shit. has to do it this way, so i can change tag in callback
1765 begin
1767 end
1768 else
1769 begin
1772 exit;
1784 // ////////////////////////////////////////////////////////////////////////// //
1785 // no callback: return `true` on the nearest hit
1786 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1787 var
1789 begin
1794 // no callback: return `true` on the nearest hit
1795 // you are not supposed to understand this
1796 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1797 const
1799 var
1825 //swapped: Boolean = false; // true: xd is yd, and vice versa
1826 // horizontal walker
1827 {$IFDEF GRID_USE_ORTHO_ACCEL}
1829 //wksign: Integer;
1831 {$ENDIF}
1832 // skipper
1834 begin
1843 begin
1846 begin
1849 exit;
1861 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1862 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);
1863 {$ENDIF}
1870 // offset query coords to (0,0)-based
1876 // clip rectange
1882 // horizontal setup
1884 begin
1885 // from left to right
1888 end
1889 else
1890 begin
1891 // from right to left
1901 // vertical setup
1903 begin
1904 // from top to bottom
1907 end
1908 else
1909 begin
1910 // from bottom to top
1924 begin
1925 //swapped := true;
1934 end
1935 else
1936 begin
1950 begin
1951 // clip at top
1957 begin
1966 begin
1967 // clip at left
1978 begin
1979 // clip at bottom
1989 //if (term = xd) then exit; // this is the only point, get out of here
1995 // first move, to skip starting point
1996 // DON'T DO THIS! loop will take care of that
1998 begin
1999 //FIXME!
2002 begin
2004 begin
2006 begin
2009 end
2010 else
2011 begin
2014 end
2015 else
2016 begin
2021 exit;
2026 (*
2027 // move coords
2028 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2029 xd += stx;
2030 // done?
2031 if (xd = term) then exit;
2032 *)
2034 {$IF DEFINED(D2F_DEBUG)}
2035 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2036 {$ENDIF}
2037 // DON'T DO THIS! loop will take care of that
2038 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2039 //ccidx := mGrid[lastGA];
2041 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2042 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2043 {$ENDIF}
2045 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2050 // increase query counter
2053 begin
2054 // just in case of overflow
2060 {$IFDEF GRID_USE_ORTHO_ACCEL}
2061 // if this is strict horizontal/vertical trace, use optimized codepath
2063 begin
2064 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2065 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2066 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2067 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2069 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2070 {$IF DEFINED(D2F_DEBUG)}
2072 {$ENDIF}
2074 // one of those will never change
2078 begin
2079 {$IF DEFINED(D2F_DEBUG)}
2080 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2081 {$ENDIF}
2082 // new tile?
2084 begin
2087 // convert coords to map (to avoid ajdusting coords inside the loop)
2090 begin
2093 begin
2098 // constant coord should be inside
2101 begin
2103 // inside the proxy?
2106 begin
2107 // setup prev[xy]
2109 begin
2111 begin
2116 exit;
2118 end
2119 else
2120 begin
2122 {$IF DEFINED(D2F_DEBUG)}
2123 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]);
2124 {$ENDIF}
2126 begin
2131 exit;
2134 continue;
2136 // remember this hitpoint if it is nearer than an old one
2137 // setup prev[xy]
2139 begin
2140 // horizontal trace
2144 begin
2145 // going left
2149 end
2150 else
2151 begin
2152 // going right
2157 end
2158 else
2159 begin
2160 // vertical trace
2164 begin
2165 // going up
2169 end
2170 else
2171 begin
2172 // going down
2179 begin
2181 begin
2186 exit;
2188 end
2189 else
2190 begin
2192 {$IF DEFINED(D2F_DEBUG)}
2193 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]);
2194 {$ENDIF}
2196 begin
2206 // next cell
2210 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2212 // skip to next tile
2214 begin
2216 begin
2217 // to the right
2219 {$IF DEFINED(D2F_DEBUG)}
2221 {$ENDIF}
2225 end
2226 else
2227 begin
2228 // to the left
2230 {$IF DEFINED(D2F_DEBUG)}
2232 {$ENDIF}
2237 end
2238 else
2239 begin
2241 begin
2242 // to the down
2244 {$IF DEFINED(D2F_DEBUG)}
2246 {$ENDIF}
2250 end
2251 else
2252 begin
2253 // to the up
2255 {$IF DEFINED(D2F_DEBUG)}
2257 {$ENDIF}
2265 // we can travel less than one cell
2268 exit;
2270 {$ENDIF}
2272 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2273 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2274 {$ENDIF}
2276 //e_LogWritefln('*********************', []);
2278 // can omit checks
2280 begin
2281 // check cell(s)
2282 {$IF DEFINED(D2F_DEBUG)}
2283 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2284 {$ENDIF}
2285 // new tile?
2287 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2288 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);
2289 {$ENDIF}
2291 begin
2292 // yes
2293 {$IF DEFINED(D2F_DEBUG)}
2294 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2295 {$ENDIF}
2297 begin
2298 // signal cell completion
2300 begin
2301 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2302 end
2304 begin
2307 exit;
2313 // has something to process in this tile?
2315 begin
2316 // process cell
2318 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2319 // convert coords to map (to avoid ajdusting coords inside the loop)
2322 // process cell list
2324 begin
2327 begin
2332 begin
2333 // can we process this proxy?
2335 begin
2338 begin
2340 begin
2345 exit;
2347 end
2348 else
2349 begin
2350 // remember this hitpoint if it is nearer than an old one
2352 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2353 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);
2354 {$ENDIF}
2356 begin
2364 end
2365 else
2366 begin
2367 // this is possibly interesting proxy, set "has more to check" flag
2372 // next cell
2375 // still has something interesting in this cell?
2377 begin
2378 // nope, don't process this cell anymore; signal cell completion
2381 begin
2383 end
2385 begin
2388 exit;
2393 begin
2394 // move to cell edge, as we have nothing to trace here anymore
2397 //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]);
2399 begin
2400 // step
2403 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2406 //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]);
2409 //putPixel(xptr^, yptr^);
2410 // move coords
2416 // we can travel less than one cell
2418 begin
2420 end
2421 else
2422 begin
2431 // ////////////////////////////////////////////////////////////////////////// //
2432 //FIXME! optimize this with real tile walking
2433 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2434 const
2436 var
2457 //swapped: Boolean = false; // true: xd is yd, and vice versa
2458 // horizontal walker
2459 {$IFDEF GRID_USE_ORTHO_ACCEL}
2461 //wksign: Integer;
2463 {$ENDIF}
2464 // skipper
2466 begin
2473 begin
2475 exit;
2490 // offset query coords to (0,0)-based
2496 // clip rectange
2502 // horizontal setup
2504 begin
2505 // from left to right
2508 end
2509 else
2510 begin
2511 // from right to left
2521 // vertical setup
2523 begin
2524 // from top to bottom
2527 end
2528 else
2529 begin
2530 // from bottom to top
2544 begin
2545 //swapped := true;
2554 end
2555 else
2556 begin
2570 begin
2571 // clip at top
2577 begin
2586 begin
2587 // clip at left
2598 begin
2599 // clip at bottom
2609 //if (term = xd) then exit; // this is the only point, get out of here
2615 // first move, to skip starting point
2616 // DON'T DO THIS! loop will take care of that
2618 begin
2620 exit;
2623 (*
2624 // move coords
2625 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2626 xd += stx;
2627 // done?
2628 if (xd = term) then exit;
2629 *)
2631 {$IF DEFINED(D2F_DEBUG)}
2632 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2633 {$ENDIF}
2634 // DON'T DO THIS! loop will take care of that
2635 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2636 //ccidx := mGrid[lastGA];
2641 // increase query counter
2644 begin
2645 // just in case of overflow
2651 {$IFDEF GRID_USE_ORTHO_ACCEL}
2652 // if this is strict horizontal/vertical trace, use optimized codepath
2654 begin
2655 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2656 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2657 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2658 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2660 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2661 {$IF DEFINED(D2F_DEBUG)}
2663 {$ENDIF}
2666 begin
2667 {$IF DEFINED(D2F_DEBUG)}
2668 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2669 {$ENDIF}
2670 // new tile?
2672 begin
2675 // convert coords to map (to avoid ajdusting coords inside the loop)
2677 begin
2680 begin
2685 begin
2688 begin
2690 end
2691 else
2692 begin
2695 exit;
2699 // next cell
2703 // skip to next tile
2705 begin
2707 begin
2708 // to the right
2710 {$IF DEFINED(D2F_DEBUG)}
2712 {$ENDIF}
2716 end
2717 else
2718 begin
2719 // to the left
2721 {$IF DEFINED(D2F_DEBUG)}
2723 {$ENDIF}
2728 end
2729 else
2730 begin
2732 begin
2733 // to the down
2735 {$IF DEFINED(D2F_DEBUG)}
2737 {$ENDIF}
2741 end
2742 else
2743 begin
2744 // to the up
2746 {$IF DEFINED(D2F_DEBUG)}
2748 {$ENDIF}
2757 exit;
2759 {$ENDIF}
2761 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2762 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2763 {$ENDIF}
2766 // can omit checks
2768 begin
2769 // check cell(s)
2770 {$IF DEFINED(D2F_DEBUG)}
2771 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2772 {$ENDIF}
2773 // new tile?
2775 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2776 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);
2777 {$ENDIF}
2779 begin
2780 // yes
2781 {$IF DEFINED(D2F_DEBUG)}
2782 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2783 {$ENDIF}
2787 // has something to process in this tile?
2789 begin
2790 // process cell
2792 // process cell list
2794 begin
2797 begin
2802 begin
2805 begin
2807 end
2808 else
2809 begin
2812 exit;
2816 // next cell
2819 // nothing more interesting in this cell
2822 // move to cell edge, as we have nothing to trace here anymore
2825 //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]);
2827 begin
2828 // step
2831 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2834 //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]);
2836 //putPixel(xptr^, yptr^);
2837 // move coords
2846 // ////////////////////////////////////////////////////////////////////////// //
2847 // trace box with the given velocity; return object hit (if any)
2848 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
2849 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2850 var
2861 begin
2878 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
2884 // just in case
2887 // increase query counter
2890 begin
2891 // just in case of overflow
2898 begin
2900 begin
2903 begin
2906 begin
2911 begin
2914 begin
2917 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
2919 begin
2924 begin
2928 exit;
2933 // next cell
2940 begin
2943 // just in case, compensate for floating point inexactness
2944 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
2945 begin
2955 // ////////////////////////////////////////////////////////////////////////// //
2956 {.$DEFINE D2F_DEBUG_OTR}
2957 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
2958 var
2969 {$IF DEFINED(D2F_DEBUG_OTR)}
2971 {$ENDIF}
2972 begin
2986 // offset query coords to (0,0)-based
2993 begin
2995 // vertical
2997 begin
2998 // down
3000 //if (ay0 < 0) then ay0 := 0;
3004 end
3005 else
3006 begin
3007 // up
3009 //if (ay1 < 0) then ay1 := 0;
3014 // check tile
3016 begin
3022 begin
3025 begin
3031 begin
3032 // bound c0 and c1 to cell
3035 // fill the thing
3036 {$IF DEFINED(D2F_DEBUG_OTR)}
3037 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)]);
3038 {$ENDIF}
3039 //assert(c0 <= c1);
3043 // next cell
3046 {$IF DEFINED(D2F_DEBUG_OTR)}
3047 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
3051 {$ENDIF}
3052 // now go till we hit cell boundary or empty space
3054 begin
3055 // up
3057 begin
3058 {$IF DEFINED(D2F_DEBUG_OTR)}
3059 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
3060 {$ENDIF}
3064 {$IF DEFINED(D2F_DEBUG_OTR)}
3065 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
3066 {$ENDIF}
3068 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
3069 end
3070 else
3071 begin
3072 // down
3078 end
3079 else
3080 begin
3081 // horizontal
3087 // ////////////////////////////////////////////////////////////////////////// //
3088 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
3089 var
3091 begin
3096 // no callback: return `true` on the nearest hit
3097 // you are not supposed to understand this
3098 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
3099 var
3111 begin
3121 // make query coords to (0,0)-based
3137 // increase query counter
3140 begin
3141 // just in case of overflow
3148 repeat
3150 // check tile
3152 // process cells
3155 begin
3158 begin
3163 begin
3166 begin
3169 // get adjusted proxy coords
3174 // inside?
3176 begin
3177 // oops
3182 exit;
3184 // do line-vs-aabb test
3187 begin
3188 // hit detected
3192 begin
3197 // if this is not a first cell, get outta here
3204 // next cell
3207 // done processing cells; exit if we registered a hit
3208 // next cells can't have better candidates, obviously
3211 // move to next tile