1 (* Copyright (C) DooM 2D:Forever Developers
2 *
3 * This program is free software: you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation, either version 3 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 *)
16 // universal spatial grid
17 {$INCLUDE ../shared/a_modes.inc}
18 {$IF DEFINED(D2F_DEBUG)}
19 {.$DEFINE D2F_DEBUG_RAYTRACE}
20 {.$DEFINE D2F_DEBUG_XXQ}
21 {.$DEFINE D2F_DEBUG_MOVER}
22 {$ENDIF}
23 {.$DEFINE GRID_USE_ORTHO_ACCEL}
26 interface
29 type
33 public
34 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
35 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
36 type TGridAlongQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
43 private
44 const
48 private
49 type
52 private
59 private
69 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
71 private
72 //mTileSize: Integer;
75 public
78 private
91 public
93 {$IF DEFINED(D2F_DEBUG)}
95 {$ENDIF}
97 private
118 public
119 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
122 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
131 // `false` if `body` is surely invalid
136 //WARNING: don't modify grid while any query is in progress (no checks are made!)
137 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
138 // no callback: return `true` on the first hit
139 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
141 //WARNING: don't modify grid while any query is in progress (no checks are made!)
142 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
143 // no callback: return object on the first hit or nil
144 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
146 //WARNING: don't modify grid while any query is in progress (no checks are made!)
147 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
148 // cb with `(nil)` will be called before processing new tile
149 // no callback: return object of the nearest hit or nil
150 // if `inverted` is true, trace will register bodies *exluding* tagmask
151 //WARNING: don't change tags in callbacks here!
152 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
153 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
155 //function traceOrthoRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload;
156 //function traceOrthoRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
158 //WARNING: don't modify grid while any query is in progress (no checks are made!)
159 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
160 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
161 //WARNING: don't change tags in callbacks here!
162 function forEachAlongLine (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
164 // debug
169 //WARNING! no sanity checks!
179 // you are not supposed to understand this
180 // returns `true` if there is an intersection, and enter coords
181 // enter coords will be equal to (x0, y0) if starting point is inside the box
182 // if result is `false`, `inx` and `iny` are undefined
183 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
192 implementation
194 uses
198 // ////////////////////////////////////////////////////////////////////////// //
199 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
200 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
201 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
203 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
206 // ////////////////////////////////////////////////////////////////////////// //
207 // you are not supposed to understand this
208 // returns `true` if there is an intersection, and enter coords
209 // enter coords will be equal to (x0, y0) if starting point is inside the box
210 // if result is `false`, `inx` and `iny` are undefined
211 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
212 var
220 //!term: Integer;
224 begin
226 // why not
232 begin
233 // check this point
235 exit;
238 // check if staring point is inside the box
239 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
241 // clip rectange
247 // horizontal setup
249 begin
250 // from left to right
253 end
254 else
255 begin
256 // from right to left
266 // vertical setup
268 begin
269 // from top to bottom
272 end
273 else
274 begin
275 // from bottom to top
289 begin
298 end
299 else
300 begin
310 //!term := x1;
314 begin
315 // clip at top
321 begin
330 begin
331 // clip at left
341 (*
342 if (y1 > wy1) then
343 begin
344 // clip at bottom
345 temp := dx2*(wy1-y0)+dsx;
346 term := x0+temp div dy2;
347 rem := temp mod dy2;
348 if (rem = 0) then Dec(term);
349 end;
351 if (term > wx1) then term := wx1; // clip at right
353 Inc(term); // draw last point
354 //if (term = xd) then exit; // this is the only point, get out of here
355 *)
359 //!dx2 -= dy2;
367 // ////////////////////////////////////////////////////////////////////////// //
368 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
369 begin
381 // ////////////////////////////////////////////////////////////////////////// //
382 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
383 var
385 begin
387 {$IF DEFINED(D2F_DEBUG)}
389 {$ENDIF}
390 {
391 if aTileSize < 1 then aTileSize := 1;
392 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
393 mTileSize := aTileSize;
394 }
405 // init free list
407 begin
413 // init grid
415 // init proxies
423 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
428 begin
436 // ////////////////////////////////////////////////////////////////////////// //
438 var
440 begin
443 begin
447 begin
453 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);
458 var
461 begin
464 begin
467 begin
470 begin
472 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
474 // next cell
482 var
485 begin
493 begin
496 begin
498 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
500 // next cell
506 // ////////////////////////////////////////////////////////////////////////// //
507 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
508 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
512 begin
513 // fix coords
521 begin
523 begin
526 end
527 else
528 begin
537 begin
539 begin
542 end
543 else
544 begin
552 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
553 begin
555 begin
558 end
559 else
560 begin
571 // ////////////////////////////////////////////////////////////////////////// //
573 begin
579 begin
581 begin
583 begin
585 end
586 else
587 begin
594 // ////////////////////////////////////////////////////////////////////////// //
596 var
599 begin
601 begin
602 // no free cells, want more
606 begin
618 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
623 begin
625 begin
627 begin
638 // ////////////////////////////////////////////////////////////////////////// //
639 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
640 var
643 begin
645 begin
646 // no free proxies, resize list
653 // get one from list
658 // add to used list
660 // statistics
666 begin
668 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
669 // add to free list
677 // ////////////////////////////////////////////////////////////////////////// //
678 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
679 const
681 var
684 begin
687 // fix coords
690 // go on
694 //tsize := mTileSize;
697 begin
701 begin
711 // ////////////////////////////////////////////////////////////////////////// //
713 var
718 begin
720 // add body to the given grid cell
723 begin
724 {$IF DEFINED(D2F_DEBUG)}
727 begin
730 begin
732 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
736 {$ENDIF}
739 begin
741 // check "has room" flag
743 begin
744 // can add here
746 begin
748 begin
751 exit;
756 // no room, go to next cell in list (if there is any)
759 // no room in cells, add new cell to list
761 // either no room, or no cell at all
771 var
773 begin
780 // assume that we cannot have one object added to bucket twice
782 var
786 begin
788 // find and remove cell
792 begin
795 begin
797 begin
798 // i found her!
800 begin
801 // this cell contains no elements, remove it
804 exit;
806 // remove element from bucket
808 begin
813 exit;
822 var
824 begin
831 // ////////////////////////////////////////////////////////////////////////// //
832 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
833 begin
841 begin
848 // ////////////////////////////////////////////////////////////////////////// //
850 var
853 begin
860 {$IF DEFINED(D2F_DEBUG_MOVER)}
861 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);
862 {$ENDIF}
864 // map -> grid
869 // did any corner crossed tile boundary?
874 begin
881 end
882 else
883 begin
891 //TODO: optimize for horizontal/vertical moves
893 var
901 begin
903 // check if tile coords was changed
908 // map -> grid
913 // check for heavy work
924 {$IF DEFINED(D2F_DEBUG_MOVER)}
925 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);
926 {$ENDIF}
928 begin
929 // crossed tile boundary, do heavy work
932 // cycle with old rect, remove body where it is necessary
933 // optimized for horizontal moves
934 {$IF DEFINED(D2F_DEBUG_MOVER)}
935 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);
936 {$ENDIF}
937 // remove stale marks
940 begin
945 {$IF DEFINED(D2F_DEBUG_MOVER)}
947 {$ENDIF}
949 begin
951 begin
952 // this column is completely outside of new rect
954 begin
955 {$IF DEFINED(D2F_DEBUG_MOVER)}
957 {$ENDIF}
960 end
961 else
962 begin
963 // heavy checks
965 begin
967 begin
968 {$IF DEFINED(D2F_DEBUG_MOVER)}
970 {$ENDIF}
977 // cycle with new rect, add body where it is necessary
980 begin
985 {$IF DEFINED(D2F_DEBUG_MOVER)}
987 {$ENDIF}
989 begin
991 begin
992 // this column is completely outside of old rect
994 begin
995 {$IF DEFINED(D2F_DEBUG_MOVER)}
997 {$ENDIF}
1000 end
1001 else
1002 begin
1003 // heavy checks
1005 begin
1007 begin
1008 {$IF DEFINED(D2F_DEBUG_MOVER)}
1010 {$ENDIF}
1017 // done
1018 end
1019 else
1020 begin
1021 {$IF DEFINED(D2F_DEBUG_MOVER)}
1022 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);
1023 {$ENDIF}
1025 // update coordinates
1031 var
1034 begin
1036 // check if tile coords was changed
1042 {$IF DEFINED(D2F_DEBUG_MOVER)}
1043 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);
1044 {$ENDIF}
1047 begin
1048 // crossed tile boundary, do heavy work
1053 end
1054 else
1055 begin
1056 // nothing to do with the grid, just fix size
1063 // ////////////////////////////////////////////////////////////////////////// //
1064 // no callback: return `true` on the first hit
1065 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1066 var
1073 begin
1079 {$IF DEFINED(D2F_DEBUG_XXQ)}
1081 {$ENDIF}
1083 // make coords (0,0)-based
1090 {$IF DEFINED(D2F_DEBUG_XXQ)}
1091 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);
1092 {$ENDIF}
1094 // restore coords
1098 // increase query counter
1101 begin
1102 // just in case of overflow
1108 {$IF DEFINED(D2F_DEBUG_XXQ)}
1109 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1110 {$ENDIF}
1113 begin
1114 {$IF DEFINED(D2F_DEBUG_XXQ)}
1116 {$ENDIF}
1119 begin
1122 {$IF DEFINED(D2F_DEBUG_XXQ)}
1123 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);
1124 {$ENDIF}
1125 // shit. has to do it this way, so i can change tag in callback
1127 begin
1132 begin
1134 begin
1136 begin
1139 exit;
1141 end
1142 else
1143 begin
1146 exit;
1156 // ////////////////////////////////////////////////////////////////////////// //
1157 // no callback: return `true` on the first hit
1158 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1159 const
1161 var
1172 begin
1181 // fix coords
1186 //tsize := mTileSize;
1191 // increase query counter
1194 begin
1195 // just in case of overflow
1199 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1202 // go on
1204 begin
1208 begin
1211 // process cells
1214 begin
1217 begin
1220 // shit. has to do it this way, so i can change tag in callback
1229 begin
1231 end
1232 else
1233 begin
1235 exit;
1245 // ////////////////////////////////////////////////////////////////////////// //
1246 // no callback: return `true` on the nearest hit
1247 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1248 var
1250 begin
1255 // no callback: return `true` on the nearest hit
1256 // you are not supposed to understand this
1257 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1258 const
1260 var
1286 // horizontal walker
1287 {$IFDEF GRID_USE_ORTHO_ACCEL}
1290 {$ENDIF}
1291 begin
1300 begin
1303 begin
1306 exit;
1318 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1319 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);
1320 {$ENDIF}
1327 // offset query coords to (0,0)-based
1333 // clip rectange
1339 // horizontal setup
1341 begin
1342 // from left to right
1345 end
1346 else
1347 begin
1348 // from right to left
1358 // vertical setup
1360 begin
1361 // from top to bottom
1364 end
1365 else
1366 begin
1367 // from bottom to top
1381 begin
1390 end
1391 else
1392 begin
1406 begin
1407 // clip at top
1413 begin
1422 begin
1423 // clip at left
1434 begin
1435 // clip at bottom
1445 //if (term = xd) then exit; // this is the only point, get out of here
1451 // first move, to skip starting point
1452 // DON'T DO THIS! loop will take care of that
1454 begin
1457 begin
1459 begin
1461 begin
1464 end
1465 else
1466 begin
1469 end
1470 else
1471 begin
1476 exit;
1481 (*
1482 // move coords
1483 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1484 xd += stx;
1485 // done?
1486 if (xd = term) then exit;
1487 *)
1489 {$IF DEFINED(D2F_DEBUG)}
1490 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1491 {$ENDIF}
1492 // DON'T DO THIS! loop will take care of that
1493 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1494 //ccidx := mGrid[lastGA];
1496 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1497 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1498 {$ENDIF}
1500 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1502 // increase query counter
1505 begin
1506 // just in case of overflow
1512 {$IFDEF GRID_USE_ORTHO_ACCEL}
1513 // if this is strict horizontal trace, use optimized codepath
1515 begin
1516 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1517 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1518 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1519 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1522 {$IF DEFINED(D2F_DEBUG)}
1524 {$ENDIF}
1526 // one of those will never change
1529 {$IF DEFINED(D2F_DEBUG)}
1531 begin
1533 end
1534 else
1535 begin
1538 {$ENDIF}
1540 begin
1541 {$IF DEFINED(D2F_DEBUG)}
1542 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1543 {$ENDIF}
1544 // new tile?
1546 begin
1549 // convert coords to map (to avoid ajdusting coords inside the loop)
1552 begin
1555 begin
1560 // constant coord should be inside
1563 begin
1565 // inside the proxy?
1568 begin
1570 begin
1572 begin
1576 exit;
1579 end
1580 else
1581 begin
1583 {$IF DEFINED(D2F_DEBUG)}
1584 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]);
1585 {$ENDIF}
1587 begin
1591 exit;
1594 continue;
1596 // remember this hitpoint if it is nearer than an old one
1598 begin
1601 begin
1602 // going left
1605 end
1606 else
1607 begin
1608 // going right
1612 end
1613 else
1614 begin
1617 begin
1618 // going up
1621 end
1622 else
1623 begin
1624 // going down
1630 begin
1632 begin
1634 end
1635 else
1636 begin
1640 begin
1644 exit;
1648 end
1649 else
1650 begin
1652 {$IF DEFINED(D2F_DEBUG)}
1653 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]);
1654 {$ENDIF}
1656 begin
1666 // next cell
1671 // skip to next tile
1673 begin
1675 begin
1676 // to the right
1678 {$IF DEFINED(D2F_DEBUG)}
1680 {$ENDIF}
1684 end
1685 else
1686 begin
1687 // to the left
1689 {$IF DEFINED(D2F_DEBUG)}
1691 {$ENDIF}
1696 end
1697 else
1698 begin
1700 begin
1701 // to the down
1703 {$IF DEFINED(D2F_DEBUG)}
1705 {$ENDIF}
1709 end
1710 else
1711 begin
1712 // to the up
1714 {$IF DEFINED(D2F_DEBUG)}
1716 {$ENDIF}
1724 // we can travel less than one cell
1726 exit;
1728 {$ENDIF}
1730 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1731 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1732 {$ENDIF}
1735 // can omit checks
1737 begin
1738 // check cell(s)
1739 {$IF DEFINED(D2F_DEBUG)}
1740 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1741 {$ENDIF}
1742 // new tile?
1744 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1745 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);
1746 {$ENDIF}
1748 begin
1749 // yes
1750 {$IF DEFINED(D2F_DEBUG)}
1751 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1752 {$ENDIF}
1754 begin
1755 // signal cell completion
1757 begin
1759 end
1761 begin
1763 exit;
1769 // has something to process in this tile?
1771 begin
1772 // process cell
1774 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1775 // convert coords to map (to avoid ajdusting coords inside the loop)
1778 // process cell list
1780 begin
1783 begin
1788 begin
1789 // can we process this proxy?
1791 begin
1794 begin
1796 begin
1800 exit;
1802 (*
1803 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1804 distSq := distanceSq(ax0, ay0, prevx, prevy);
1805 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);
1806 if (distSq < lastDistSq) then
1807 begin
1808 wasHit := true;
1809 lastDistSq := distSq;
1810 ex := prevx;
1811 ey := prevy;
1812 lastObj := px.mObj;
1813 end;
1814 {$ENDIF}
1815 *)
1816 end
1817 else
1818 begin
1819 // remember this hitpoint if it is nearer than an old one
1821 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1822 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);
1823 {$ENDIF}
1825 begin
1833 end
1834 else
1835 begin
1836 // this is possibly interesting proxy, set "has more to check" flag
1841 // next cell
1844 // still has something interesting in this cell?
1846 begin
1847 // nope, don't process this cell anymore; signal cell completion
1850 begin
1852 end
1854 begin
1856 exit;
1860 //putPixel(xptr^, yptr^);
1861 // move coords
1867 // we can travel less than one cell
1869 begin
1871 end
1872 else
1873 begin
1880 // ////////////////////////////////////////////////////////////////////////// //
1881 //FIXME! optimize this with real tile walking
1882 function TBodyGridBase.forEachAlongLine (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1883 const
1885 var
1904 //tedist: Integer;
1905 begin
1927 // `x` and `y` will be in grid coords
1931 // increase query counter
1934 begin
1935 // just in case of overflow
1941 // cache various things
1942 //tsize := mTileSize;
1948 // setup distance and flags
1951 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1954 // it is slightly faster this way
1958 if (log) then e_WriteLog(Format('tracing: (%d,%d)-(%d,%d)', [x, y, x1-minx, y1-miny]), MSG_NOTIFY);
1960 // now trace
1963 begin
1965 // do one step
1968 // invariant: one of those always changed
1969 {$IF DEFINED(D2F_DEBUG)}
1970 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1971 {$ENDIF}
1974 // invariant: we always doing a step
1975 {$IF DEFINED(D2F_DEBUG)}
1977 {$ENDIF}
1978 begin
1979 // check for crossing tile/grid boundary
1981 begin
1982 // we're still in grid
1984 // check for tile edge crossing
1990 // crossed tile edge?
1992 begin
1993 // setup new cell index
1995 if (log) then e_WriteLog(Format(' stepped to new tile (%d,%d) -- (%d,%d)', [(x div tsize), (y div tsize), x, y]), MSG_NOTIFY);
1996 end
1997 else
1999 begin
2000 // we have nothing interesting here anymore, jump directly to tile edge
2001 (*
2002 if (incx = 0) then
2003 begin
2004 // vertical line
2005 if (incy < 0) then tedist := y-(y and (not tsize)) else tedist := (y or (tsize-1))-y;
2006 if (tedist > 1) then
2007 begin
2008 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);
2009 y += incy*tedist;
2010 Inc(i, tedist);
2011 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);
2012 end;
2013 end
2014 else if (incy = 0) then
2015 begin
2016 // horizontal line
2017 if (incx < 0) then tedist := x-(x and (not tsize)) else tedist := (x or (tsize-1))-x;
2018 if (tedist > 1) then
2019 begin
2020 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);
2021 x += incx*tedist;
2022 Inc(i, tedist);
2023 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);
2024 end;
2025 end;
2026 *)
2027 (*
2028 else if (
2029 // get minimal distance to tile edges
2030 if (incx < 0) then tedist := x-(x and (not tsize)) else if (incx > 0) then tedist := (x or (tsize+1))-x else tedist := 0;
2031 {$IF DEFINED(D2F_DEBUG)}
2032 if (tedist < 0) then raise Exception.Create('internal bug in grid raycaster (2.x)');
2033 {$ENDIF}
2034 if (incy < 0) then f := y-(y and (not tsize)) else if (incy > 0) then f := (y or (tsize+1))-y else f := 0;
2035 {$IF DEFINED(D2F_DEBUG)}
2036 if (f < 0) then raise Exception.Create('internal bug in grid raycaster (2.y)');
2037 {$ENDIF}
2038 if (tedist = 0) then tedist := f else if (f <> 0) then tedist := minInt(tedist, f);
2039 // do jump
2040 if (tedist > 1) then
2041 begin
2042 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);
2043 xerr += dx*tedist;
2044 yerr += dy*tedist;
2045 if (xerr >= 0) then begin x += incx*((xerr div d)+1); xerr := (xerr mod d)-d; end;
2046 if (yerr >= 0) then begin y += incy*((yerr div d)+1); yerr := (yerr mod d)-d; end;
2047 Inc(i, tedist);
2048 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);
2049 end;
2050 *)
2052 end
2053 else
2054 begin
2055 // out of grid
2060 // has something to process in the current cell?
2062 begin
2063 // process cell
2065 // convert coords to map (to avoid ajdusting coords inside the loop)
2066 //Inc(x, minx);
2067 //Inc(y, miny);
2068 // process cell list
2070 begin
2073 begin
2078 begin
2083 // next cell
2087 // convert coords to grid
2088 //Dec(x, minx);
2089 //Dec(y, miny);