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}
25 interface
28 type
32 public
33 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
34 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
35 type TGridAlongQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
42 private
43 const
47 private
48 type
51 private
58 private
68 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
70 private
71 //mTileSize: Integer;
74 public
77 private
90 public
92 {$IF DEFINED(D2F_DEBUG)}
94 {$ENDIF}
96 private
117 public
118 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
121 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
130 // `false` if `body` is surely invalid
135 //WARNING: don't modify grid while any query is in progress (no checks are made!)
136 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
137 // no callback: return `true` on the first hit
138 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
140 //WARNING: don't modify grid while any query is in progress (no checks are made!)
141 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
142 // no callback: return object on the first hit or nil
143 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
145 //WARNING: don't modify grid while any query is in progress (no checks are made!)
146 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
147 // cb with `(nil)` will be called before processing new tile
148 // no callback: return object of the nearest hit or nil
149 // if `inverted` is true, trace will register bodies *exluding* tagmask
150 //WARNING: don't change tags in callbacks here!
151 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
152 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
154 //function traceOrthoRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload;
155 //function traceOrthoRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
157 //WARNING: don't modify grid while any query is in progress (no checks are made!)
158 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
159 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
160 //WARNING: don't change tags in callbacks here!
161 function forEachAlongLine (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
163 // debug
168 //WARNING! no sanity checks!
178 // you are not supposed to understand this
179 // returns `true` if there is an intersection, and enter coords
180 // enter coords will be equal to (x0, y0) if starting point is inside the box
181 // if result is `false`, `inx` and `iny` are undefined
182 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
191 implementation
193 uses
197 // ////////////////////////////////////////////////////////////////////////// //
198 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
199 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
200 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
202 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
205 // ////////////////////////////////////////////////////////////////////////// //
206 // you are not supposed to understand this
207 // returns `true` if there is an intersection, and enter coords
208 // enter coords will be equal to (x0, y0) if starting point is inside the box
209 // if result is `false`, `inx` and `iny` are undefined
210 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
211 var
219 //!term: Integer;
223 begin
225 // why not
231 begin
232 // check this point
234 exit;
237 // check if staring point is inside the box
238 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
240 // clip rectange
246 // horizontal setup
248 begin
249 // from left to right
252 end
253 else
254 begin
255 // from right to left
265 // vertical setup
267 begin
268 // from top to bottom
271 end
272 else
273 begin
274 // from bottom to top
288 begin
297 end
298 else
299 begin
309 //!term := x1;
313 begin
314 // clip at top
320 begin
329 begin
330 // clip at left
340 (*
341 if (y1 > wy1) then
342 begin
343 // clip at bottom
344 temp := dx2*(wy1-y0)+dsx;
345 term := x0+temp div dy2;
346 rem := temp mod dy2;
347 if (rem = 0) then Dec(term);
348 end;
350 if (term > wx1) then term := wx1; // clip at right
352 Inc(term); // draw last point
353 //if (term = xd) then exit; // this is the only point, get out of here
354 *)
358 //!dx2 -= dy2;
366 // ////////////////////////////////////////////////////////////////////////// //
367 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
368 begin
380 // ////////////////////////////////////////////////////////////////////////// //
381 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
382 var
384 begin
386 {$IF DEFINED(D2F_DEBUG)}
388 {$ENDIF}
389 {
390 if aTileSize < 1 then aTileSize := 1;
391 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
392 mTileSize := aTileSize;
393 }
404 // init free list
406 begin
412 // init grid
414 // init proxies
422 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
427 begin
435 // ////////////////////////////////////////////////////////////////////////// //
437 var
439 begin
442 begin
446 begin
452 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);
457 var
460 begin
463 begin
466 begin
469 begin
471 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
473 // next cell
481 var
484 begin
492 begin
495 begin
497 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
499 // next cell
505 // ////////////////////////////////////////////////////////////////////////// //
506 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
507 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
511 begin
512 // fix coords
520 begin
522 begin
525 end
526 else
527 begin
536 begin
538 begin
541 end
542 else
543 begin
551 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
552 begin
554 begin
557 end
558 else
559 begin
570 // ////////////////////////////////////////////////////////////////////////// //
572 begin
578 begin
580 begin
582 begin
584 end
585 else
586 begin
593 // ////////////////////////////////////////////////////////////////////////// //
595 var
598 begin
600 begin
601 // no free cells, want more
605 begin
617 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
622 begin
624 begin
626 begin
637 // ////////////////////////////////////////////////////////////////////////// //
638 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
639 var
642 begin
644 begin
645 // no free proxies, resize list
652 // get one from list
657 // add to used list
659 // statistics
665 begin
667 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
668 // add to free list
676 // ////////////////////////////////////////////////////////////////////////// //
677 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
678 const
680 var
683 begin
686 // fix coords
689 // go on
693 //tsize := mTileSize;
696 begin
700 begin
710 // ////////////////////////////////////////////////////////////////////////// //
712 var
717 begin
719 // add body to the given grid cell
722 begin
723 {$IF DEFINED(D2F_DEBUG)}
726 begin
729 begin
731 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
735 {$ENDIF}
738 begin
740 // check "has room" flag
742 begin
743 // can add here
745 begin
747 begin
750 exit;
755 // no room, go to next cell in list (if there is any)
758 // no room in cells, add new cell to list
760 // either no room, or no cell at all
770 var
772 begin
779 // assume that we cannot have one object added to bucket twice
781 var
785 begin
787 // find and remove cell
791 begin
794 begin
796 begin
797 // i found her!
799 begin
800 // this cell contains no elements, remove it
803 exit;
805 // remove element from bucket
807 begin
812 exit;
821 var
823 begin
830 // ////////////////////////////////////////////////////////////////////////// //
831 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
832 begin
840 begin
847 // ////////////////////////////////////////////////////////////////////////// //
849 var
852 begin
859 {$IF DEFINED(D2F_DEBUG_MOVER)}
860 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);
861 {$ENDIF}
863 // map -> grid
868 // did any corner crossed tile boundary?
873 begin
880 end
881 else
882 begin
890 //TODO: optimize for horizontal/vertical moves
892 var
900 begin
902 // check if tile coords was changed
907 // map -> grid
912 // check for heavy work
923 {$IF DEFINED(D2F_DEBUG_MOVER)}
924 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);
925 {$ENDIF}
927 begin
928 // crossed tile boundary, do heavy work
931 // cycle with old rect, remove body where it is necessary
932 // optimized for horizontal moves
933 {$IF DEFINED(D2F_DEBUG_MOVER)}
934 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);
935 {$ENDIF}
936 // remove stale marks
939 begin
944 {$IF DEFINED(D2F_DEBUG_MOVER)}
946 {$ENDIF}
948 begin
950 begin
951 // this column is completely outside of new rect
953 begin
954 {$IF DEFINED(D2F_DEBUG_MOVER)}
956 {$ENDIF}
959 end
960 else
961 begin
962 // heavy checks
964 begin
966 begin
967 {$IF DEFINED(D2F_DEBUG_MOVER)}
969 {$ENDIF}
976 // cycle with new rect, add body where it is necessary
979 begin
984 {$IF DEFINED(D2F_DEBUG_MOVER)}
986 {$ENDIF}
988 begin
990 begin
991 // this column is completely outside of old rect
993 begin
994 {$IF DEFINED(D2F_DEBUG_MOVER)}
996 {$ENDIF}
999 end
1000 else
1001 begin
1002 // heavy checks
1004 begin
1006 begin
1007 {$IF DEFINED(D2F_DEBUG_MOVER)}
1009 {$ENDIF}
1016 // done
1017 end
1018 else
1019 begin
1020 {$IF DEFINED(D2F_DEBUG_MOVER)}
1021 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);
1022 {$ENDIF}
1024 // update coordinates
1030 var
1033 begin
1035 // check if tile coords was changed
1041 {$IF DEFINED(D2F_DEBUG_MOVER)}
1042 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);
1043 {$ENDIF}
1046 begin
1047 // crossed tile boundary, do heavy work
1052 end
1053 else
1054 begin
1055 // nothing to do with the grid, just fix size
1062 // ////////////////////////////////////////////////////////////////////////// //
1063 // no callback: return `true` on the first hit
1064 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1065 var
1072 begin
1078 {$IF DEFINED(D2F_DEBUG_XXQ)}
1080 {$ENDIF}
1082 // make coords (0,0)-based
1089 {$IF DEFINED(D2F_DEBUG_XXQ)}
1090 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);
1091 {$ENDIF}
1093 // restore coords
1097 // increase query counter
1100 begin
1101 // just in case of overflow
1107 {$IF DEFINED(D2F_DEBUG_XXQ)}
1108 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1109 {$ENDIF}
1112 begin
1113 {$IF DEFINED(D2F_DEBUG_XXQ)}
1115 {$ENDIF}
1118 begin
1121 {$IF DEFINED(D2F_DEBUG_XXQ)}
1122 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);
1123 {$ENDIF}
1124 // shit. has to do it this way, so i can change tag in callback
1126 begin
1131 begin
1133 begin
1135 begin
1138 exit;
1140 end
1141 else
1142 begin
1145 exit;
1155 // ////////////////////////////////////////////////////////////////////////// //
1156 // no callback: return `true` on the first hit
1157 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1158 const
1160 var
1171 begin
1180 // fix coords
1185 //tsize := mTileSize;
1190 // increase query counter
1193 begin
1194 // just in case of overflow
1198 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1201 // go on
1203 begin
1207 begin
1210 // process cells
1213 begin
1216 begin
1219 // shit. has to do it this way, so i can change tag in callback
1228 begin
1230 end
1231 else
1232 begin
1234 exit;
1244 // ////////////////////////////////////////////////////////////////////////// //
1245 // no callback: return `true` on the nearest hit
1246 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1247 var
1249 begin
1254 // no callback: return `true` on the nearest hit
1255 // you are not supposed to understand this
1256 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1257 const
1259 var
1285 // horizontal walker
1288 begin
1297 begin
1300 begin
1303 exit;
1315 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1316 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);
1317 {$ENDIF}
1324 // offset query coords to (0,0)-based
1330 // clip rectange
1336 // horizontal setup
1338 begin
1339 // from left to right
1342 end
1343 else
1344 begin
1345 // from right to left
1355 // vertical setup
1357 begin
1358 // from top to bottom
1361 end
1362 else
1363 begin
1364 // from bottom to top
1378 begin
1387 end
1388 else
1389 begin
1403 begin
1404 // clip at top
1410 begin
1419 begin
1420 // clip at left
1431 begin
1432 // clip at bottom
1442 //if (term = xd) then exit; // this is the only point, get out of here
1448 // first move, to skip starting point
1449 // DON'T DO THIS! loop will take care of that
1451 begin
1454 begin
1456 begin
1458 begin
1461 end
1462 else
1463 begin
1466 end
1467 else
1468 begin
1473 exit;
1478 (*
1479 // move coords
1480 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1481 xd += stx;
1482 // done?
1483 if (xd = term) then exit;
1484 *)
1486 {$IF DEFINED(D2F_DEBUG)}
1487 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1488 {$ENDIF}
1489 // DON'T DO THIS! loop will take care of that
1490 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1491 //ccidx := mGrid[lastGA];
1493 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1494 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1495 {$ENDIF}
1497 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1499 // increase query counter
1502 begin
1503 // just in case of overflow
1509 // if this is strict horizontal trace, use optimized codepath
1511 begin
1512 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1513 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1514 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1515 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1518 {$IF DEFINED(D2F_DEBUG)}
1520 {$ENDIF}
1522 // one of those will never change
1525 {$IF DEFINED(D2F_DEBUG)}
1527 begin
1529 end
1530 else
1531 begin
1534 {$ENDIF}
1536 begin
1537 {$IF DEFINED(D2F_DEBUG)}
1538 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1539 {$ENDIF}
1540 // new tile?
1542 begin
1545 // convert coords to map (to avoid ajdusting coords inside the loop)
1548 begin
1551 begin
1556 // constant coord should be inside
1559 begin
1561 // inside the proxy?
1564 begin
1566 begin
1568 begin
1572 exit;
1575 end
1576 else
1577 begin
1579 {$IF DEFINED(D2F_DEBUG)}
1580 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]);
1581 {$ENDIF}
1583 begin
1587 exit;
1590 continue;
1592 // remember this hitpoint if it is nearer than an old one
1594 begin
1597 begin
1598 // going left
1601 end
1602 else
1603 begin
1604 // going right
1608 end
1609 else
1610 begin
1613 begin
1614 // going up
1617 end
1618 else
1619 begin
1620 // going down
1626 begin
1628 begin
1630 end
1631 else
1632 begin
1636 begin
1640 exit;
1644 end
1645 else
1646 begin
1648 {$IF DEFINED(D2F_DEBUG)}
1649 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]);
1650 {$ENDIF}
1652 begin
1662 // next cell
1667 // skip to next tile
1669 begin
1671 begin
1672 // to the right
1674 {$IF DEFINED(D2F_DEBUG)}
1676 {$ENDIF}
1680 end
1681 else
1682 begin
1683 // to the left
1685 {$IF DEFINED(D2F_DEBUG)}
1687 {$ENDIF}
1692 end
1693 else
1694 begin
1696 begin
1697 // to the down
1699 {$IF DEFINED(D2F_DEBUG)}
1701 {$ENDIF}
1705 end
1706 else
1707 begin
1708 // to the up
1710 {$IF DEFINED(D2F_DEBUG)}
1712 {$ENDIF}
1720 // we can travel less than one cell
1722 exit;
1725 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1726 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1727 {$ENDIF}
1730 // can omit checks
1732 begin
1733 // check cell(s)
1734 {$IF DEFINED(D2F_DEBUG)}
1735 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1736 {$ENDIF}
1737 // new tile?
1739 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1740 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);
1741 {$ENDIF}
1743 begin
1744 // yes
1745 {$IF DEFINED(D2F_DEBUG)}
1746 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1747 {$ENDIF}
1749 begin
1750 // signal cell completion
1752 begin
1754 end
1756 begin
1758 exit;
1764 // has something to process in this tile?
1766 begin
1767 // process cell
1769 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1770 // convert coords to map (to avoid ajdusting coords inside the loop)
1773 // process cell list
1775 begin
1778 begin
1783 begin
1784 // can we process this proxy?
1786 begin
1789 begin
1791 begin
1795 exit;
1797 (*
1798 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1799 distSq := distanceSq(ax0, ay0, prevx, prevy);
1800 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);
1801 if (distSq < lastDistSq) then
1802 begin
1803 wasHit := true;
1804 lastDistSq := distSq;
1805 ex := prevx;
1806 ey := prevy;
1807 lastObj := px.mObj;
1808 end;
1809 {$ENDIF}
1810 *)
1811 end
1812 else
1813 begin
1814 // remember this hitpoint if it is nearer than an old one
1816 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1817 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);
1818 {$ENDIF}
1820 begin
1828 end
1829 else
1830 begin
1831 // this is possibly interesting proxy, set "has more to check" flag
1836 // next cell
1839 // still has something interesting in this cell?
1841 begin
1842 // nope, don't process this cell anymore; signal cell completion
1845 begin
1847 end
1849 begin
1851 exit;
1855 //putPixel(xptr^, yptr^);
1856 // move coords
1862 // we can travel less than one cell
1864 begin
1866 end
1867 else
1868 begin
1875 // ////////////////////////////////////////////////////////////////////////// //
1876 //FIXME! optimize this with real tile walking
1877 function TBodyGridBase.forEachAlongLine (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1878 const
1880 var
1899 //tedist: Integer;
1900 begin
1922 // `x` and `y` will be in grid coords
1926 // increase query counter
1929 begin
1930 // just in case of overflow
1936 // cache various things
1937 //tsize := mTileSize;
1943 // setup distance and flags
1946 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1949 // it is slightly faster this way
1953 if (log) then e_WriteLog(Format('tracing: (%d,%d)-(%d,%d)', [x, y, x1-minx, y1-miny]), MSG_NOTIFY);
1955 // now trace
1958 begin
1960 // do one step
1963 // invariant: one of those always changed
1964 {$IF DEFINED(D2F_DEBUG)}
1965 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1966 {$ENDIF}
1969 // invariant: we always doing a step
1970 {$IF DEFINED(D2F_DEBUG)}
1972 {$ENDIF}
1973 begin
1974 // check for crossing tile/grid boundary
1976 begin
1977 // we're still in grid
1979 // check for tile edge crossing
1985 // crossed tile edge?
1987 begin
1988 // setup new cell index
1990 if (log) then e_WriteLog(Format(' stepped to new tile (%d,%d) -- (%d,%d)', [(x div tsize), (y div tsize), x, y]), MSG_NOTIFY);
1991 end
1992 else
1994 begin
1995 // we have nothing interesting here anymore, jump directly to tile edge
1996 (*
1997 if (incx = 0) then
1998 begin
1999 // vertical line
2000 if (incy < 0) then tedist := y-(y and (not tsize)) else tedist := (y or (tsize-1))-y;
2001 if (tedist > 1) then
2002 begin
2003 if (log) then e_WriteLog(Format(' doing vertical jump from tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
2004 y += incy*tedist;
2005 Inc(i, tedist);
2006 if (log) then e_WriteLog(Format(' jumped to tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
2007 end;
2008 end
2009 else if (incy = 0) then
2010 begin
2011 // horizontal line
2012 if (incx < 0) then tedist := x-(x and (not tsize)) else tedist := (x or (tsize-1))-x;
2013 if (tedist > 1) then
2014 begin
2015 if (log) then e_WriteLog(Format(' doing horizontal jump from tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
2016 x += incx*tedist;
2017 Inc(i, tedist);
2018 if (log) then e_WriteLog(Format(' jumped to tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
2019 end;
2020 end;
2021 *)
2022 (*
2023 else if (
2024 // get minimal distance to tile edges
2025 if (incx < 0) then tedist := x-(x and (not tsize)) else if (incx > 0) then tedist := (x or (tsize+1))-x else tedist := 0;
2026 {$IF DEFINED(D2F_DEBUG)}
2027 if (tedist < 0) then raise Exception.Create('internal bug in grid raycaster (2.x)');
2028 {$ENDIF}
2029 if (incy < 0) then f := y-(y and (not tsize)) else if (incy > 0) then f := (y or (tsize+1))-y else f := 0;
2030 {$IF DEFINED(D2F_DEBUG)}
2031 if (f < 0) then raise Exception.Create('internal bug in grid raycaster (2.y)');
2032 {$ENDIF}
2033 if (tedist = 0) then tedist := f else if (f <> 0) then tedist := minInt(tedist, f);
2034 // do jump
2035 if (tedist > 1) then
2036 begin
2037 if (log) then e_WriteLog(Format(' doing jump from tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
2038 xerr += dx*tedist;
2039 yerr += dy*tedist;
2040 if (xerr >= 0) then begin x += incx*((xerr div d)+1); xerr := (xerr mod d)-d; end;
2041 if (yerr >= 0) then begin y += incy*((yerr div d)+1); yerr := (yerr mod d)-d; end;
2042 Inc(i, tedist);
2043 if (log) then e_WriteLog(Format(' jumped to tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
2044 end;
2045 *)
2047 end
2048 else
2049 begin
2050 // out of grid
2055 // has something to process in the current cell?
2057 begin
2058 // process cell
2060 // convert coords to map (to avoid ajdusting coords inside the loop)
2061 //Inc(x, minx);
2062 //Inc(y, miny);
2063 // process cell list
2065 begin
2068 begin
2073 begin
2078 // next cell
2082 // convert coords to grid
2083 //Dec(x, minx);
2084 //Dec(y, miny);