1cb2534f9d8fdaaef113598cb828b047c8d5e4d4
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}
24 {$DEFINE LINEAABB2}
27 interface
29 const
32 type
36 public
37 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
38 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
44 private
45 const
48 public
49 type
52 private
59 private
71 public
86 private
87 type
96 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
98 private
99 //mTileSize: Integer;
103 public
106 type
108 private
112 public
119 private
133 public
135 {$IF DEFINED(D2F_DEBUG)}
137 {$ENDIF}
139 private
159 public
160 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
163 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
172 // `false` if `body` is surely invalid
177 //WARNING: don't modify grid while any query is in progress (no checks are made!)
178 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
179 // no callback: return `true` on the first hit
180 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
182 //WARNING: don't modify grid while any query is in progress (no checks are made!)
183 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
184 // no callback: return object on the first hit or nil
185 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
189 //WARNING: don't modify grid while any query is in progress (no checks are made!)
190 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
191 // cb with `(nil)` will be called before processing new tile
192 // no callback: return object of the nearest hit or nil
193 // if `inverted` is true, trace will register bodies *exluding* tagmask
194 //WARNING: don't change tags in callbacks here!
195 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
196 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
198 //WARNING: don't modify grid while any query is in progress (no checks are made!)
199 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
200 // cb with `(nil)` will be called before processing new tile
201 // no callback: return object of the nearest hit or nil
202 // if `inverted` is true, trace will register bodies *exluding* tagmask
203 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
204 //WARNING: don't change tags in callbacks here!
205 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
206 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
208 // return `false` if we're still inside at the end
209 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
210 // `true`: endpoint will point at the last "inside" pixel
211 // `false`: endpoint will be (ax1, ay1)
212 //WARNING: don't change tags in callbacks here!
213 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
215 //WARNING: don't modify grid while any query is in progress (no checks are made!)
216 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
217 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
218 //WARNING: don't change tags in callbacks here!
219 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
221 // trace box with the given velocity; return object hit (if any)
222 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
223 //WARNING: don't change tags in callbacks here!
224 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
226 // debug
231 public
232 //WARNING! no sanity checks!
244 type
245 // common structure for all line tracers
247 public
250 private
258 public
259 // call `setyp` after this
264 // this will use `w[xy][01]` to clip coords
265 // return `false` if the whole line was clipped away
266 // on `true`, you should process first point, and go on
269 // call this *after* doing a step
270 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
273 // as you will prolly call `done()` after doing a step anyway, this will do it for you
274 // move to next point, return `true` when the line is complete (i.e. you should stop)
277 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
282 public
283 // current coords
289 // you are not supposed to understand this
290 // returns `true` if there is an intersection, and enter coords
291 // enter coords will be equal to (x0, y0) if starting point is inside the box
292 // if result is `false`, `inx` and `iny` are undefined
293 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
295 // sweep two AABB's to see if and when they are overlapping
296 // returns `true` if collision was detected (but boxes doesn't overlap)
297 // u1 and u1 has no sense if no collision was detected
298 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
299 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
300 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
301 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
302 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
308 //function minInt (a, b: Integer): Integer; inline;
309 //function maxInt (a, b: Integer): Integer; inline;
312 implementation
314 uses
318 // ////////////////////////////////////////////////////////////////////////// //
319 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
320 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
321 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
322 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
324 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
327 // ////////////////////////////////////////////////////////////////////////// //
329 const
337 begin
343 var
347 begin
352 begin
358 begin
361 end
363 begin
366 end
368 begin
371 end
373 begin
378 begin
382 end
383 else
384 begin
393 // returns `true` if there is an intersection, and enter coords
394 // enter coords will be equal to (x0, y0) if starting point is inside the box
395 // if result is `false`, `inx` and `iny` are undefined
396 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
397 var
399 begin
404 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
409 begin
412 // hack!
415 end
416 else
417 begin
424 // ////////////////////////////////////////////////////////////////////////// //
426 begin
431 begin
432 // clip rectange
440 var
442 begin
443 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
447 begin
449 end
450 else
451 begin
460 // check for ortho lines
462 begin
463 // horizontal
470 end
472 begin
473 // vertical
480 end
481 else
482 begin
483 // diagonal
485 begin
486 // horizontal
490 end
491 else
492 begin
493 // vertical
509 // true: done
511 begin
513 begin
517 end
518 else
519 begin
528 // true: done
530 var
534 begin
539 // strictly horizontal?
541 begin
542 // only xd
544 begin
545 // xd: to left edge
548 end
549 else
550 begin
551 // xd: to right edge
557 exit;
560 // strictly vertical?
562 begin
563 // only xd
565 begin
566 // yd: to top edge
569 end
570 else
571 begin
572 // yd: to bottom edge
578 exit;
581 // diagonal
583 // calculate xwalk
585 begin
588 end
589 else
590 begin
595 // calculate ywalk
597 begin
600 end
601 else
602 begin
607 {
608 while (xd <> ex) and (yd <> ey) do
609 begin
610 if horiz then
611 begin
612 xd += stx;
613 err += errinc;
614 if (err >= 0) then begin err -= errmax; yd += sty; end;
615 end
616 else
617 begin
618 yd += sty;
619 err += errinc;
620 if (err >= 0) then begin err -= errmax; xd += stx; end;
621 end;
622 Dec(stleft);
623 if (stleft < 1) then begin result := true; exit; end;
624 end;
625 }
629 begin
630 // in which dir we want to walk?
634 begin
637 begin
641 end
642 else
643 begin
646 begin
651 // check for walk completion
660 // ////////////////////////////////////////////////////////////////////////// //
661 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
663 var
667 var
669 begin
673 begin
677 end
679 begin
686 begin
689 end
691 begin
699 var
702 begin
715 // check if they are overlapping right now (SAT)
716 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
720 // treat b as stationary, so invert v to get relative velocity
734 begin
740 // ////////////////////////////////////////////////////////////////////////// //
741 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
742 begin
755 begin
760 begin
765 begin
770 begin
775 begin
780 begin
785 // ////////////////////////////////////////////////////////////////////////// //
786 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
787 begin
796 begin
798 begin
800 begin
804 exit;
814 begin
819 // ////////////////////////////////////////////////////////////////////////// //
820 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
821 var
823 begin
825 {$IF DEFINED(D2F_DEBUG)}
827 {$ENDIF}
828 {
829 if aTileSize < 1 then aTileSize := 1;
830 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
831 mTileSize := aTileSize;
832 }
843 // init free list
845 begin
851 // init grid
853 // init proxies
861 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
866 begin
874 // ////////////////////////////////////////////////////////////////////////// //
876 var
878 begin
881 begin
885 begin
891 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);
896 var
899 begin
902 begin
905 begin
908 begin
910 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
912 // next cell
920 var
923 begin
931 begin
934 begin
936 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
938 // next cell
944 // ////////////////////////////////////////////////////////////////////////// //
945 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
946 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
950 begin
951 // fix coords
959 begin
961 begin
964 end
965 else
966 begin
975 begin
977 begin
980 end
981 else
982 begin
990 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
991 begin
993 begin
996 end
997 else
998 begin
1009 // ////////////////////////////////////////////////////////////////////////// //
1011 begin
1012 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1017 begin
1019 begin
1021 begin
1023 end
1024 else
1025 begin
1033 begin
1038 // ////////////////////////////////////////////////////////////////////////// //
1040 var
1043 begin
1045 begin
1046 // no free cells, want more
1050 begin
1062 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1067 begin
1069 begin
1071 begin
1082 // ////////////////////////////////////////////////////////////////////////// //
1083 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1084 var
1087 begin
1089 begin
1090 // no free proxies, resize list
1097 // get one from list
1102 // add to used list
1104 // statistics
1110 begin
1112 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1113 // add to free list
1121 // ////////////////////////////////////////////////////////////////////////// //
1122 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1123 var
1127 begin
1130 // fix coords
1133 // go on
1142 // clip rect
1148 // do the work
1150 begin
1152 begin
1160 // ////////////////////////////////////////////////////////////////////////// //
1162 var
1167 begin
1169 // add body to the given grid cell
1172 begin
1173 {$IF DEFINED(D2F_DEBUG)}
1176 begin
1179 begin
1181 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1185 {$ENDIF}
1188 begin
1190 // check "has room" flag
1192 begin
1193 // can add here
1195 begin
1197 begin
1200 exit;
1205 // no room, go to next cell in list (if there is any)
1208 // no room in cells, add new cell to list
1210 // either no room, or no cell at all
1220 // assume that we cannot have one object added to bucket twice
1222 var
1226 begin
1228 // find and remove cell
1232 begin
1235 begin
1237 begin
1238 // i found her!
1240 begin
1241 // this cell contains no elements, remove it
1244 exit;
1246 // remove element from bucket
1248 begin
1253 exit;
1262 // ////////////////////////////////////////////////////////////////////////// //
1263 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1264 begin
1267 //insertInternal(result);
1273 var
1275 begin
1278 //removeInternal(body);
1284 // ////////////////////////////////////////////////////////////////////////// //
1286 var
1289 begin
1296 {$IF DEFINED(D2F_DEBUG_MOVER)}
1297 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);
1298 {$ENDIF}
1300 // map -> grid
1305 // did any corner crossed tile boundary?
1310 begin
1311 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1312 //removeInternal(body);
1318 //insertInternal(body);
1320 end
1321 else
1322 begin
1331 //TODO: optimize for horizontal/vertical moves
1333 var
1341 begin
1343 // check if tile coords was changed
1348 // map -> grid
1353 // check for heavy work
1364 {$IF DEFINED(D2F_DEBUG_MOVER)}
1365 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);
1366 {$ENDIF}
1368 begin
1369 // crossed tile boundary, do heavy work
1372 // cycle with old rect, remove body where it is necessary
1373 // optimized for horizontal moves
1374 {$IF DEFINED(D2F_DEBUG_MOVER)}
1375 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);
1376 {$ENDIF}
1377 // remove stale marks
1380 begin
1385 {$IF DEFINED(D2F_DEBUG_MOVER)}
1387 {$ENDIF}
1389 begin
1391 begin
1392 // this column is completely outside of new rect
1394 begin
1395 {$IF DEFINED(D2F_DEBUG_MOVER)}
1397 {$ENDIF}
1400 end
1401 else
1402 begin
1403 // heavy checks
1405 begin
1407 begin
1408 {$IF DEFINED(D2F_DEBUG_MOVER)}
1410 {$ENDIF}
1417 // cycle with new rect, add body where it is necessary
1420 begin
1425 {$IF DEFINED(D2F_DEBUG_MOVER)}
1427 {$ENDIF}
1429 begin
1431 begin
1432 // this column is completely outside of old rect
1434 begin
1435 {$IF DEFINED(D2F_DEBUG_MOVER)}
1437 {$ENDIF}
1440 end
1441 else
1442 begin
1443 // heavy checks
1445 begin
1447 begin
1448 {$IF DEFINED(D2F_DEBUG_MOVER)}
1450 {$ENDIF}
1457 // done
1458 end
1459 else
1460 begin
1461 {$IF DEFINED(D2F_DEBUG_MOVER)}
1462 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);
1463 {$ENDIF}
1465 // update coordinates
1472 var
1475 begin
1477 // check if tile coords was changed
1483 {$IF DEFINED(D2F_DEBUG_MOVER)}
1484 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);
1485 {$ENDIF}
1488 begin
1489 // crossed tile boundary, do heavy work
1490 //removeInternal(body);
1494 //insertInternal(body);
1496 end
1497 else
1498 begin
1499 // nothing to do with the grid, just fix size
1506 // ////////////////////////////////////////////////////////////////////////// //
1508 var
1510 begin
1513 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1518 // ////////////////////////////////////////////////////////////////////////// //
1519 // no callback: return `true` on the first hit
1520 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1521 var
1528 begin
1534 {$IF DEFINED(D2F_DEBUG_XXQ)}
1536 {$ENDIF}
1538 // make coords (0,0)-based
1545 {$IF DEFINED(D2F_DEBUG_XXQ)}
1546 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);
1547 {$ENDIF}
1549 // restore coords
1553 // increase query counter
1556 begin
1557 // just in case of overflow
1563 {$IF DEFINED(D2F_DEBUG_XXQ)}
1564 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1565 {$ENDIF}
1568 begin
1569 {$IF DEFINED(D2F_DEBUG_XXQ)}
1571 {$ENDIF}
1574 begin
1577 {$IF DEFINED(D2F_DEBUG_XXQ)}
1578 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);
1579 {$ENDIF}
1580 // shit. has to do it this way, so i can change tag in callback
1582 begin
1587 begin
1589 begin
1591 begin
1594 exit;
1596 end
1597 else
1598 begin
1601 exit;
1611 // ////////////////////////////////////////////////////////////////////////// //
1612 // no callback: return `true` on the first hit
1613 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1614 var
1626 begin
1635 // fix coords
1650 // clip rect
1657 // has something to do
1661 // increase query counter
1664 begin
1665 // just in case of overflow
1669 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1672 // go on
1674 begin
1676 begin
1677 // process cells
1680 begin
1683 begin
1686 // shit! has to do it this way, so i can change tag in callback
1695 begin
1697 end
1698 else
1699 begin
1702 exit;
1714 // ////////////////////////////////////////////////////////////////////////// //
1715 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1716 var
1727 //px0, py0, px1, py1: Integer;
1728 begin
1739 // make query coords (0,0)-based
1751 // increase query counter
1754 begin
1755 // just in case of overflow
1761 repeat
1763 // check tile
1765 // process cells
1767 begin
1770 begin
1775 begin
1778 begin
1781 exit;
1785 // next cell
1788 // done processing cells, move to next tile
1795 // ////////////////////////////////////////////////////////////////////////// //
1796 // trace box with the given velocity; return object hit (if any)
1797 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1798 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1799 var
1810 begin
1824 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1830 // just in case
1836 // increase query counter
1839 begin
1840 // just in case of overflow
1847 begin
1849 begin
1852 begin
1855 begin
1860 begin
1863 begin
1866 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1868 begin
1873 begin
1877 exit;
1882 // next cell
1889 begin
1892 // just in case, compensate for floating point inexactness
1893 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1894 begin
1904 // ////////////////////////////////////////////////////////////////////////// //
1905 {.$DEFINE D2F_DEBUG_OTR}
1906 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1907 var
1918 {$IF DEFINED(D2F_DEBUG_OTR)}
1920 {$ENDIF}
1921 begin
1935 // offset query coords to (0,0)-based
1942 begin
1944 // vertical
1946 begin
1947 // down
1949 //if (ay0 < 0) then ay0 := 0;
1953 end
1954 else
1955 begin
1956 // up
1958 //if (ay1 < 0) then ay1 := 0;
1963 // check tile
1965 begin
1971 begin
1974 begin
1980 begin
1981 // bound c0 and c1 to cell
1984 // fill the thing
1985 {$IF DEFINED(D2F_DEBUG_OTR)}
1986 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)]);
1987 {$ENDIF}
1988 //assert(c0 <= c1);
1992 // next cell
1995 {$IF DEFINED(D2F_DEBUG_OTR)}
1996 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2000 {$ENDIF}
2001 // now go till we hit cell boundary or empty space
2003 begin
2004 // up
2006 begin
2007 {$IF DEFINED(D2F_DEBUG_OTR)}
2008 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2009 {$ENDIF}
2013 {$IF DEFINED(D2F_DEBUG_OTR)}
2014 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2015 {$ENDIF}
2017 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2018 end
2019 else
2020 begin
2021 // down
2027 end
2028 else
2029 begin
2030 // horizontal
2036 // ////////////////////////////////////////////////////////////////////////// //
2037 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2038 var
2040 begin
2045 // no callback: return `true` on the nearest hit
2046 // you are not supposed to understand this
2047 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2048 var
2063 begin
2073 // make query coords (0,0)-based
2084 {$IF DEFINED(D2F_DEBUG)}
2085 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
2086 {$ENDIF}
2091 // increase query counter
2094 begin
2095 // just in case of overflow
2101 repeat
2103 {$IF DEFINED(D2F_DEBUG)}
2105 {$ENDIF}
2106 // check tile
2108 // process cells
2111 begin
2114 begin
2119 begin
2122 begin
2125 // get adjusted proxy coords
2130 {$IF DEFINED(D2F_DEBUG)}
2131 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
2132 {$ENDIF}
2133 // inside?
2135 begin
2136 // oops
2141 {$IF DEFINED(D2F_DEBUG)}
2143 {$ENDIF}
2144 exit;
2146 // do line-vs-aabb test
2148 begin
2149 // hit detected
2151 {$IF DEFINED(D2F_DEBUG)}
2152 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
2153 {$ENDIF}
2155 begin
2165 // next cell
2168 // done processing cells; exit if we registered a hit
2169 // next cells can't have better candidates, obviously
2172 // move to next tile
2179 // ////////////////////////////////////////////////////////////////////////// //
2180 // no callback: return `true` on the nearest hit
2181 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2182 var
2184 begin
2189 // no callback: return `true` on the nearest hit
2190 // you are not supposed to understand this
2191 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2192 var
2218 //swapped: Boolean = false; // true: xd is yd, and vice versa
2219 // horizontal walker
2220 {$IFDEF GRID_USE_ORTHO_ACCEL}
2222 //wksign: Integer;
2224 {$ENDIF}
2225 // skipper
2227 begin
2236 begin
2239 begin
2242 exit;
2254 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2255 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);
2256 {$ENDIF}
2263 // offset query coords to (0,0)-based
2269 // clip rectange
2275 // horizontal setup
2277 begin
2278 // from left to right
2281 end
2282 else
2283 begin
2284 // from right to left
2294 // vertical setup
2296 begin
2297 // from top to bottom
2300 end
2301 else
2302 begin
2303 // from bottom to top
2317 begin
2318 //swapped := true;
2327 end
2328 else
2329 begin
2343 begin
2344 // clip at top
2350 begin
2353 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2360 begin
2361 // clip at left
2372 begin
2373 // clip at bottom
2383 //if (term = xd) then exit; // this is the only point, get out of here
2389 // first move, to skip starting point
2390 // DON'T DO THIS! loop will take care of that
2392 begin
2393 //FIXME!
2396 begin
2398 begin
2400 begin
2403 end
2404 else
2405 begin
2408 end
2409 else
2410 begin
2415 exit;
2420 (*
2421 // move coords
2422 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2423 xd += stx;
2424 // done?
2425 if (xd = term) then exit;
2426 *)
2428 {$IF DEFINED(D2F_DEBUG)}
2429 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2430 {$ENDIF}
2431 // DON'T DO THIS! loop will take care of that
2432 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2433 //ccidx := mGrid[lastGA];
2435 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2436 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2437 {$ENDIF}
2439 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2444 // increase query counter
2447 begin
2448 // just in case of overflow
2454 {$IFDEF GRID_USE_ORTHO_ACCEL}
2455 // if this is strict horizontal/vertical trace, use optimized codepath
2457 begin
2458 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2459 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2460 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2461 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2463 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2464 {$IF DEFINED(D2F_DEBUG)}
2466 {$ENDIF}
2468 // one of those will never change
2472 begin
2473 {$IF DEFINED(D2F_DEBUG)}
2474 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2475 {$ENDIF}
2476 // new tile?
2478 begin
2481 // convert coords to map (to avoid ajdusting coords inside the loop)
2484 begin
2487 begin
2492 // constant coord should be inside
2495 begin
2497 // inside the proxy?
2500 begin
2501 // setup prev[xy]
2503 begin
2505 begin
2510 exit;
2512 end
2513 else
2514 begin
2516 {$IF DEFINED(D2F_DEBUG)}
2517 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]);
2518 {$ENDIF}
2520 begin
2525 exit;
2528 continue;
2530 // remember this hitpoint if it is nearer than an old one
2531 // setup prev[xy]
2533 begin
2534 // horizontal trace
2538 begin
2539 // going left
2543 end
2544 else
2545 begin
2546 // going right
2551 end
2552 else
2553 begin
2554 // vertical trace
2558 begin
2559 // going up
2563 end
2564 else
2565 begin
2566 // going down
2573 begin
2575 begin
2580 exit;
2582 end
2583 else
2584 begin
2586 {$IF DEFINED(D2F_DEBUG)}
2587 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]);
2588 {$ENDIF}
2590 begin
2600 // next cell
2604 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2606 // skip to next tile
2608 begin
2610 begin
2611 // to the right
2613 {$IF DEFINED(D2F_DEBUG)}
2615 {$ENDIF}
2619 end
2620 else
2621 begin
2622 // to the left
2624 {$IF DEFINED(D2F_DEBUG)}
2626 {$ENDIF}
2631 end
2632 else
2633 begin
2635 begin
2636 // to the down
2638 {$IF DEFINED(D2F_DEBUG)}
2640 {$ENDIF}
2644 end
2645 else
2646 begin
2647 // to the up
2649 {$IF DEFINED(D2F_DEBUG)}
2651 {$ENDIF}
2659 // we can travel less than one cell
2662 exit;
2664 {$ENDIF}
2666 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2667 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2668 {$ENDIF}
2670 //e_LogWritefln('*********************', []);
2672 // can omit checks
2674 begin
2675 // check cell(s)
2676 {$IF DEFINED(D2F_DEBUG)}
2677 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2678 {$ENDIF}
2679 // new tile?
2681 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2682 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);
2683 {$ENDIF}
2685 begin
2686 // yes
2687 {$IF DEFINED(D2F_DEBUG)}
2688 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2689 {$ENDIF}
2691 begin
2692 // signal cell completion
2694 begin
2695 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2696 end
2698 begin
2701 exit;
2707 // has something to process in this tile?
2709 begin
2710 // process cell
2712 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2713 // convert coords to map (to avoid ajdusting coords inside the loop)
2716 // process cell list
2718 begin
2721 begin
2726 begin
2727 // can we process this proxy?
2729 begin
2732 begin
2734 begin
2739 exit;
2741 end
2742 else
2743 begin
2744 // remember this hitpoint if it is nearer than an old one
2746 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2747 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);
2748 {$ENDIF}
2750 begin
2758 end
2759 else
2760 begin
2761 // this is possibly interesting proxy, set "has more to check" flag
2766 // next cell
2769 // still has something interesting in this cell?
2771 begin
2772 // nope, don't process this cell anymore; signal cell completion
2775 begin
2777 end
2779 begin
2782 exit;
2787 begin
2788 // move to cell edge, as we have nothing to trace here anymore
2791 //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]);
2793 begin
2794 // step
2797 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2800 //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]);
2803 //putPixel(xptr^, yptr^);
2804 // move coords
2810 // we can travel less than one cell
2812 begin
2814 end
2815 else
2816 begin