0c9da2dbd51d2e03d7e689026499a53812b4d43b
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 uses
30 mempool;
32 const
35 type
39 public
40 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
41 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
47 private
48 const
51 public
52 type
55 private
62 private
74 public
89 private
90 type
99 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
101 private
102 //mTileSize: Integer;
106 public
109 type
111 private
115 public
122 private
136 public
138 {$IF DEFINED(D2F_DEBUG)}
140 {$ENDIF}
142 private
162 public
163 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
166 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
175 // `false` if `body` is surely invalid
180 //WARNING: don't modify grid while any query is in progress (no checks are made!)
181 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
182 // no callback: return `true` on the first hit
183 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
185 //WARNING: don't modify grid while any query is in progress (no checks are made!)
186 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
187 // no callback: return object on the first hit or nil
188 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
192 //WARNING: don't modify grid while any query is in progress (no checks are made!)
193 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
194 // cb with `(nil)` will be called before processing new tile
195 // no callback: return object of the nearest hit or nil
196 // if `inverted` is true, trace will register bodies *exluding* tagmask
197 //WARNING: don't change tags in callbacks here!
198 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
199 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
201 //WARNING: don't modify grid while any query is in progress (no checks are made!)
202 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
203 // cb with `(nil)` will be called before processing new tile
204 // no callback: return object of the nearest hit or nil
205 // if `inverted` is true, trace will register bodies *exluding* tagmask
206 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
207 //WARNING: don't change tags in callbacks here!
208 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
209 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
211 // return `false` if we're still inside at the end
212 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
213 // `true`: endpoint will point at the last "inside" pixel
214 // `false`: endpoint will be (ax1, ay1)
215 //WARNING: don't change tags in callbacks here!
216 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
218 //WARNING: don't modify grid while any query is in progress (no checks are made!)
219 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
220 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
221 //WARNING: don't change tags in callbacks here!
222 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
224 // trace box with the given velocity; return object hit (if any)
225 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
226 //WARNING: don't change tags in callbacks here!
227 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
229 // debug
234 public
235 //WARNING! no sanity checks!
247 type
248 // common structure for all line tracers
250 public
253 private
261 public
262 // call `setyp` after this
267 // this will use `w[xy][01]` to clip coords
268 // return `false` if the whole line was clipped away
269 // on `true`, you should process first point, and go on
272 // call this *after* doing a step
273 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
276 // as you will prolly call `done()` after doing a step anyway, this will do it for you
277 // move to next point, return `true` when the line is complete (i.e. you should stop)
280 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
285 public
286 // current coords
292 // you are not supposed to understand this
293 // returns `true` if there is an intersection, and enter coords
294 // enter coords will be equal to (x0, y0) if starting point is inside the box
295 // if result is `false`, `inx` and `iny` are undefined
296 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
298 // sweep two AABB's to see if and when they are overlapping
299 // returns `true` if collision was detected (but boxes doesn't overlap)
300 // u1 and u1 has no sense if no collision was detected
301 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
302 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
303 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
304 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
305 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
311 //function minInt (a, b: Integer): Integer; inline;
312 //function maxInt (a, b: Integer): Integer; inline;
315 implementation
317 uses
321 // ////////////////////////////////////////////////////////////////////////// //
322 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
323 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
324 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
325 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
327 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
330 // ////////////////////////////////////////////////////////////////////////// //
332 const
340 begin
346 var
350 begin
355 begin
361 begin
364 end
366 begin
369 end
371 begin
374 end
376 begin
381 begin
385 end
386 else
387 begin
396 // returns `true` if there is an intersection, and enter coords
397 // enter coords will be equal to (x0, y0) if starting point is inside the box
398 // if result is `false`, `inx` and `iny` are undefined
399 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
400 var
402 begin
407 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
412 begin
415 // hack!
418 end
419 else
420 begin
427 // ////////////////////////////////////////////////////////////////////////// //
429 begin
434 begin
435 // clip rectange
443 var
445 begin
446 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
450 begin
452 end
453 else
454 begin
463 // check for ortho lines
465 begin
466 // horizontal
473 end
475 begin
476 // vertical
483 end
484 else
485 begin
486 // diagonal
488 begin
489 // horizontal
493 end
494 else
495 begin
496 // vertical
512 // true: done
514 begin
516 begin
520 end
521 else
522 begin
531 // true: done
533 var
537 begin
542 // strictly horizontal?
544 begin
545 // only xd
547 begin
548 // xd: to left edge
551 end
552 else
553 begin
554 // xd: to right edge
560 exit;
563 // strictly vertical?
565 begin
566 // only xd
568 begin
569 // yd: to top edge
572 end
573 else
574 begin
575 // yd: to bottom edge
581 exit;
584 // diagonal
586 // calculate xwalk
588 begin
591 end
592 else
593 begin
598 // calculate ywalk
600 begin
603 end
604 else
605 begin
610 {
611 while (xd <> ex) and (yd <> ey) do
612 begin
613 if horiz then
614 begin
615 xd += stx;
616 err += errinc;
617 if (err >= 0) then begin err -= errmax; yd += sty; end;
618 end
619 else
620 begin
621 yd += sty;
622 err += errinc;
623 if (err >= 0) then begin err -= errmax; xd += stx; end;
624 end;
625 Dec(stleft);
626 if (stleft < 1) then begin result := true; exit; end;
627 end;
628 }
632 begin
633 // in which dir we want to walk?
637 begin
640 begin
644 end
645 else
646 begin
649 begin
654 // check for walk completion
663 // ////////////////////////////////////////////////////////////////////////// //
664 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
666 var
670 var
672 begin
676 begin
680 end
682 begin
689 begin
692 end
694 begin
702 var
705 begin
718 // check if they are overlapping right now (SAT)
719 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
723 // treat b as stationary, so invert v to get relative velocity
737 begin
743 // ////////////////////////////////////////////////////////////////////////// //
744 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
745 begin
758 begin
763 begin
768 begin
773 begin
778 begin
783 begin
788 // ////////////////////////////////////////////////////////////////////////// //
789 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
790 begin
799 begin
801 begin
803 begin
807 exit;
817 begin
822 // ////////////////////////////////////////////////////////////////////////// //
823 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
824 var
826 begin
828 {$IF DEFINED(D2F_DEBUG)}
830 {$ENDIF}
831 {
832 if aTileSize < 1 then aTileSize := 1;
833 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
834 mTileSize := aTileSize;
835 }
846 // init free list
848 begin
854 // init grid
856 // init proxies
864 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
869 begin
877 // ////////////////////////////////////////////////////////////////////////// //
879 var
881 begin
884 begin
888 begin
894 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);
899 var
902 begin
905 begin
908 begin
911 begin
913 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
915 // next cell
923 var
926 begin
934 begin
937 begin
939 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
941 // next cell
947 // ////////////////////////////////////////////////////////////////////////// //
948 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
949 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
953 begin
954 // fix coords
962 begin
964 begin
967 end
968 else
969 begin
978 begin
980 begin
983 end
984 else
985 begin
993 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
994 begin
996 begin
999 end
1000 else
1001 begin
1012 // ////////////////////////////////////////////////////////////////////////// //
1014 begin
1015 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1020 begin
1022 begin
1024 begin
1026 end
1027 else
1028 begin
1036 begin
1041 // ////////////////////////////////////////////////////////////////////////// //
1043 var
1046 begin
1048 begin
1049 // no free cells, want more
1053 begin
1065 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1070 begin
1072 begin
1074 begin
1085 // ////////////////////////////////////////////////////////////////////////// //
1086 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1087 var
1090 begin
1092 begin
1093 // no free proxies, resize list
1100 // get one from list
1105 // add to used list
1107 // statistics
1113 begin
1115 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1116 // add to free list
1124 // ////////////////////////////////////////////////////////////////////////// //
1125 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1126 var
1130 begin
1133 // fix coords
1136 // go on
1145 // clip rect
1151 // do the work
1153 begin
1155 begin
1163 // ////////////////////////////////////////////////////////////////////////// //
1165 var
1170 begin
1172 // add body to the given grid cell
1175 begin
1176 {$IF DEFINED(D2F_DEBUG)}
1179 begin
1182 begin
1184 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1188 {$ENDIF}
1191 begin
1193 // check "has room" flag
1195 begin
1196 // can add here
1198 begin
1200 begin
1203 exit;
1208 // no room, go to next cell in list (if there is any)
1211 // no room in cells, add new cell to list
1213 // either no room, or no cell at all
1223 // assume that we cannot have one object added to bucket twice
1225 var
1229 begin
1231 // find and remove cell
1235 begin
1238 begin
1240 begin
1241 // i found her!
1243 begin
1244 // this cell contains no elements, remove it
1247 exit;
1249 // remove element from bucket
1251 begin
1256 exit;
1265 // ////////////////////////////////////////////////////////////////////////// //
1266 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1267 begin
1270 //insertInternal(result);
1276 var
1278 begin
1281 //removeInternal(body);
1287 // ////////////////////////////////////////////////////////////////////////// //
1289 var
1292 begin
1299 {$IF DEFINED(D2F_DEBUG_MOVER)}
1300 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);
1301 {$ENDIF}
1303 // map -> grid
1308 // did any corner crossed tile boundary?
1313 begin
1314 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1315 //removeInternal(body);
1321 //insertInternal(body);
1323 end
1324 else
1325 begin
1334 //TODO: optimize for horizontal/vertical moves
1336 var
1344 begin
1346 // check if tile coords was changed
1351 // map -> grid
1356 // check for heavy work
1367 {$IF DEFINED(D2F_DEBUG_MOVER)}
1368 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);
1369 {$ENDIF}
1371 begin
1372 // crossed tile boundary, do heavy work
1375 // cycle with old rect, remove body where it is necessary
1376 // optimized for horizontal moves
1377 {$IF DEFINED(D2F_DEBUG_MOVER)}
1378 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);
1379 {$ENDIF}
1380 // remove stale marks
1383 begin
1388 {$IF DEFINED(D2F_DEBUG_MOVER)}
1390 {$ENDIF}
1392 begin
1394 begin
1395 // this column is completely outside of new rect
1397 begin
1398 {$IF DEFINED(D2F_DEBUG_MOVER)}
1400 {$ENDIF}
1403 end
1404 else
1405 begin
1406 // heavy checks
1408 begin
1410 begin
1411 {$IF DEFINED(D2F_DEBUG_MOVER)}
1413 {$ENDIF}
1420 // cycle with new rect, add body where it is necessary
1423 begin
1428 {$IF DEFINED(D2F_DEBUG_MOVER)}
1430 {$ENDIF}
1432 begin
1434 begin
1435 // this column is completely outside of old rect
1437 begin
1438 {$IF DEFINED(D2F_DEBUG_MOVER)}
1440 {$ENDIF}
1443 end
1444 else
1445 begin
1446 // heavy checks
1448 begin
1450 begin
1451 {$IF DEFINED(D2F_DEBUG_MOVER)}
1453 {$ENDIF}
1460 // done
1461 end
1462 else
1463 begin
1464 {$IF DEFINED(D2F_DEBUG_MOVER)}
1465 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);
1466 {$ENDIF}
1468 // update coordinates
1475 var
1478 begin
1480 // check if tile coords was changed
1486 {$IF DEFINED(D2F_DEBUG_MOVER)}
1487 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);
1488 {$ENDIF}
1491 begin
1492 // crossed tile boundary, do heavy work
1493 //removeInternal(body);
1497 //insertInternal(body);
1499 end
1500 else
1501 begin
1502 // nothing to do with the grid, just fix size
1509 // ////////////////////////////////////////////////////////////////////////// //
1511 var
1513 begin
1516 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1521 // ////////////////////////////////////////////////////////////////////////// //
1522 // no callback: return `true` on the first hit
1523 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1524 var
1531 begin
1537 {$IF DEFINED(D2F_DEBUG_XXQ)}
1539 {$ENDIF}
1541 // make coords (0,0)-based
1548 {$IF DEFINED(D2F_DEBUG_XXQ)}
1549 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);
1550 {$ENDIF}
1552 // restore coords
1556 // increase query counter
1559 begin
1560 // just in case of overflow
1566 {$IF DEFINED(D2F_DEBUG_XXQ)}
1567 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1568 {$ENDIF}
1571 begin
1572 {$IF DEFINED(D2F_DEBUG_XXQ)}
1574 {$ENDIF}
1577 begin
1580 {$IF DEFINED(D2F_DEBUG_XXQ)}
1581 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);
1582 {$ENDIF}
1583 // shit. has to do it this way, so i can change tag in callback
1585 begin
1590 begin
1592 begin
1594 begin
1597 exit;
1599 end
1600 else
1601 begin
1604 exit;
1614 // ////////////////////////////////////////////////////////////////////////// //
1615 // no callback: return `true` on the first hit
1616 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1617 var
1629 begin
1638 // fix coords
1653 // clip rect
1660 // has something to do
1664 // increase query counter
1667 begin
1668 // just in case of overflow
1672 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1675 // go on
1677 begin
1679 begin
1680 // process cells
1683 begin
1686 begin
1689 // shit! has to do it this way, so i can change tag in callback
1698 begin
1700 end
1701 else
1702 begin
1705 exit;
1717 // ////////////////////////////////////////////////////////////////////////// //
1718 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1719 var
1730 //px0, py0, px1, py1: Integer;
1731 begin
1742 // make query coords (0,0)-based
1754 // increase query counter
1757 begin
1758 // just in case of overflow
1764 repeat
1766 // check tile
1768 // process cells
1770 begin
1773 begin
1778 begin
1781 begin
1784 exit;
1788 // next cell
1791 // done processing cells, move to next tile
1798 // ////////////////////////////////////////////////////////////////////////// //
1799 // trace box with the given velocity; return object hit (if any)
1800 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1801 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1802 var
1813 begin
1827 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1833 // just in case
1839 // increase query counter
1842 begin
1843 // just in case of overflow
1850 begin
1852 begin
1855 begin
1858 begin
1863 begin
1866 begin
1869 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1871 begin
1876 begin
1880 exit;
1885 // next cell
1892 begin
1895 // just in case, compensate for floating point inexactness
1896 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1897 begin
1907 // ////////////////////////////////////////////////////////////////////////// //
1908 {.$DEFINE D2F_DEBUG_OTR}
1909 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1910 var
1921 {$IF DEFINED(D2F_DEBUG_OTR)}
1923 {$ENDIF}
1924 begin
1938 // offset query coords to (0,0)-based
1945 begin
1947 // vertical
1949 begin
1950 // down
1952 //if (ay0 < 0) then ay0 := 0;
1956 end
1957 else
1958 begin
1959 // up
1961 //if (ay1 < 0) then ay1 := 0;
1966 // check tile
1968 begin
1974 begin
1977 begin
1983 begin
1984 // bound c0 and c1 to cell
1987 // fill the thing
1988 {$IF DEFINED(D2F_DEBUG_OTR)}
1989 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)]);
1990 {$ENDIF}
1991 //assert(c0 <= c1);
1995 // next cell
1998 {$IF DEFINED(D2F_DEBUG_OTR)}
1999 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2003 {$ENDIF}
2004 // now go till we hit cell boundary or empty space
2006 begin
2007 // up
2009 begin
2010 {$IF DEFINED(D2F_DEBUG_OTR)}
2011 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2012 {$ENDIF}
2016 {$IF DEFINED(D2F_DEBUG_OTR)}
2017 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2018 {$ENDIF}
2020 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2021 end
2022 else
2023 begin
2024 // down
2030 end
2031 else
2032 begin
2033 // horizontal
2039 // ////////////////////////////////////////////////////////////////////////// //
2040 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2041 var
2043 begin
2048 // no callback: return `true` on the nearest hit
2049 // you are not supposed to understand this
2050 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2051 var
2066 begin
2076 // make query coords (0,0)-based
2087 {$IF DEFINED(D2F_DEBUG)}
2088 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
2089 {$ENDIF}
2094 // increase query counter
2097 begin
2098 // just in case of overflow
2104 repeat
2106 {$IF DEFINED(D2F_DEBUG)}
2108 {$ENDIF}
2109 // check tile
2111 // process cells
2114 begin
2117 begin
2122 begin
2125 begin
2128 // get adjusted proxy coords
2133 {$IF DEFINED(D2F_DEBUG)}
2134 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
2135 {$ENDIF}
2136 // inside?
2138 begin
2139 // oops
2144 {$IF DEFINED(D2F_DEBUG)}
2146 {$ENDIF}
2147 exit;
2149 // do line-vs-aabb test
2151 begin
2152 // hit detected
2154 {$IF DEFINED(D2F_DEBUG)}
2155 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
2156 {$ENDIF}
2158 begin
2168 // next cell
2171 // done processing cells; exit if we registered a hit
2172 // next cells can't have better candidates, obviously
2175 // move to next tile
2182 // ////////////////////////////////////////////////////////////////////////// //
2183 // no callback: return `true` on the nearest hit
2184 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2185 var
2187 begin
2192 // no callback: return `true` on the nearest hit
2193 // you are not supposed to understand this
2194 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2195 var
2221 //swapped: Boolean = false; // true: xd is yd, and vice versa
2222 // horizontal walker
2223 {$IFDEF GRID_USE_ORTHO_ACCEL}
2225 //wksign: Integer;
2227 {$ENDIF}
2228 // skipper
2230 begin
2239 begin
2242 begin
2245 exit;
2257 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2258 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);
2259 {$ENDIF}
2266 // offset query coords to (0,0)-based
2272 // clip rectange
2278 // horizontal setup
2280 begin
2281 // from left to right
2284 end
2285 else
2286 begin
2287 // from right to left
2297 // vertical setup
2299 begin
2300 // from top to bottom
2303 end
2304 else
2305 begin
2306 // from bottom to top
2320 begin
2321 //swapped := true;
2330 end
2331 else
2332 begin
2346 begin
2347 // clip at top
2353 begin
2356 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2363 begin
2364 // clip at left
2375 begin
2376 // clip at bottom
2386 //if (term = xd) then exit; // this is the only point, get out of here
2392 // first move, to skip starting point
2393 // DON'T DO THIS! loop will take care of that
2395 begin
2396 //FIXME!
2399 begin
2401 begin
2403 begin
2406 end
2407 else
2408 begin
2411 end
2412 else
2413 begin
2418 exit;
2423 (*
2424 // move coords
2425 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2426 xd += stx;
2427 // done?
2428 if (xd = term) then exit;
2429 *)
2431 {$IF DEFINED(D2F_DEBUG)}
2432 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2433 {$ENDIF}
2434 // DON'T DO THIS! loop will take care of that
2435 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2436 //ccidx := mGrid[lastGA];
2438 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2439 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2440 {$ENDIF}
2442 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2447 // increase query counter
2450 begin
2451 // just in case of overflow
2457 {$IFDEF GRID_USE_ORTHO_ACCEL}
2458 // if this is strict horizontal/vertical trace, use optimized codepath
2460 begin
2461 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2462 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2463 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2464 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2466 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2467 {$IF DEFINED(D2F_DEBUG)}
2469 {$ENDIF}
2471 // one of those will never change
2475 begin
2476 {$IF DEFINED(D2F_DEBUG)}
2477 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2478 {$ENDIF}
2479 // new tile?
2481 begin
2484 // convert coords to map (to avoid ajdusting coords inside the loop)
2487 begin
2490 begin
2495 // constant coord should be inside
2498 begin
2500 // inside the proxy?
2503 begin
2504 // setup prev[xy]
2506 begin
2508 begin
2513 exit;
2515 end
2516 else
2517 begin
2519 {$IF DEFINED(D2F_DEBUG)}
2520 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]);
2521 {$ENDIF}
2523 begin
2528 exit;
2531 continue;
2533 // remember this hitpoint if it is nearer than an old one
2534 // setup prev[xy]
2536 begin
2537 // horizontal trace
2541 begin
2542 // going left
2546 end
2547 else
2548 begin
2549 // going right
2554 end
2555 else
2556 begin
2557 // vertical trace
2561 begin
2562 // going up
2566 end
2567 else
2568 begin
2569 // going down
2576 begin
2578 begin
2583 exit;
2585 end
2586 else
2587 begin
2589 {$IF DEFINED(D2F_DEBUG)}
2590 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]);
2591 {$ENDIF}
2593 begin
2603 // next cell
2607 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2609 // skip to next tile
2611 begin
2613 begin
2614 // to the right
2616 {$IF DEFINED(D2F_DEBUG)}
2618 {$ENDIF}
2622 end
2623 else
2624 begin
2625 // to the left
2627 {$IF DEFINED(D2F_DEBUG)}
2629 {$ENDIF}
2634 end
2635 else
2636 begin
2638 begin
2639 // to the down
2641 {$IF DEFINED(D2F_DEBUG)}
2643 {$ENDIF}
2647 end
2648 else
2649 begin
2650 // to the up
2652 {$IF DEFINED(D2F_DEBUG)}
2654 {$ENDIF}
2662 // we can travel less than one cell
2665 exit;
2667 {$ENDIF}
2669 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2670 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2671 {$ENDIF}
2673 //e_LogWritefln('*********************', []);
2675 // can omit checks
2677 begin
2678 // check cell(s)
2679 {$IF DEFINED(D2F_DEBUG)}
2680 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2681 {$ENDIF}
2682 // new tile?
2684 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2685 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);
2686 {$ENDIF}
2688 begin
2689 // yes
2690 {$IF DEFINED(D2F_DEBUG)}
2691 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2692 {$ENDIF}
2694 begin
2695 // signal cell completion
2697 begin
2698 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2699 end
2701 begin
2704 exit;
2710 // has something to process in this tile?
2712 begin
2713 // process cell
2715 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2716 // convert coords to map (to avoid ajdusting coords inside the loop)
2719 // process cell list
2721 begin
2724 begin
2729 begin
2730 // can we process this proxy?
2732 begin
2735 begin
2737 begin
2742 exit;
2744 end
2745 else
2746 begin
2747 // remember this hitpoint if it is nearer than an old one
2749 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2750 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);
2751 {$ENDIF}
2753 begin
2761 end
2762 else
2763 begin
2764 // this is possibly interesting proxy, set "has more to check" flag
2769 // next cell
2772 // still has something interesting in this cell?
2774 begin
2775 // nope, don't process this cell anymore; signal cell completion
2778 begin
2780 end
2782 begin
2785 exit;
2790 begin
2791 // move to cell edge, as we have nothing to trace here anymore
2794 //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]);
2796 begin
2797 // step
2800 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2803 //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]);
2806 //putPixel(xptr^, yptr^);
2807 // move coords
2813 // we can travel less than one cell
2815 begin
2817 end
2818 else
2819 begin