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
42 private
43 const
47 public
48 type
51 private
58 private
67 public
77 private
78 type
87 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
89 private
90 //mTileSize: Integer;
94 public
97 type
99 private
103 public
110 private
124 public
126 {$IF DEFINED(D2F_DEBUG)}
128 {$ENDIF}
130 private
153 public
154 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
157 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
166 // `false` if `body` is surely invalid
171 //WARNING: don't modify grid while any query is in progress (no checks are made!)
172 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
173 // no callback: return `true` on the first hit
174 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
176 //WARNING: don't modify grid while any query is in progress (no checks are made!)
177 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
178 // no callback: return object on the first hit or nil
179 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
183 //WARNING: don't modify grid while any query is in progress (no checks are made!)
184 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
185 // cb with `(nil)` will be called before processing new tile
186 // no callback: return object of the nearest hit or nil
187 // if `inverted` is true, trace will register bodies *exluding* tagmask
188 //WARNING: don't change tags in callbacks here!
189 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
190 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
192 //function traceOrthoRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload;
193 //function traceOrthoRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
195 //WARNING: don't modify grid while any query is in progress (no checks are made!)
196 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
197 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
198 //WARNING: don't change tags in callbacks here!
199 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
201 // debug
206 public
207 //WARNING! no sanity checks!
219 // you are not supposed to understand this
220 // returns `true` if there is an intersection, and enter coords
221 // enter coords will be equal to (x0, y0) if starting point is inside the box
222 // if result is `false`, `inx` and `iny` are undefined
223 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
232 implementation
234 uses
238 // ////////////////////////////////////////////////////////////////////////// //
239 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
240 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
241 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
243 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
246 // ////////////////////////////////////////////////////////////////////////// //
247 // you are not supposed to understand this
248 // returns `true` if there is an intersection, and enter coords
249 // enter coords will be equal to (x0, y0) if starting point is inside the box
250 // if result is `false`, `inx` and `iny` are undefined
251 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
252 var
260 //!term: Integer;
264 begin
266 // why not
272 begin
273 // check this point
275 exit;
278 // check if staring point is inside the box
279 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
281 // clip rectange
287 // horizontal setup
289 begin
290 // from left to right
293 end
294 else
295 begin
296 // from right to left
306 // vertical setup
308 begin
309 // from top to bottom
312 end
313 else
314 begin
315 // from bottom to top
329 begin
338 end
339 else
340 begin
350 //!term := x1;
354 begin
355 // clip at top
361 begin
370 begin
371 // clip at left
381 (*
382 if (y1 > wy1) then
383 begin
384 // clip at bottom
385 temp := dx2*(wy1-y0)+dsx;
386 term := x0+temp div dy2;
387 rem := temp mod dy2;
388 if (rem = 0) then Dec(term);
389 end;
391 if (term > wx1) then term := wx1; // clip at right
393 Inc(term); // draw last point
394 //if (term = xd) then exit; // this is the only point, get out of here
395 *)
399 //!dx2 -= dy2;
407 // ////////////////////////////////////////////////////////////////////////// //
408 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
409 begin
422 begin
427 begin
432 begin
437 begin
442 // ////////////////////////////////////////////////////////////////////////// //
443 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
444 begin
453 begin
455 begin
457 begin
461 exit;
471 begin
476 // ////////////////////////////////////////////////////////////////////////// //
477 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
478 var
480 begin
482 {$IF DEFINED(D2F_DEBUG)}
484 {$ENDIF}
485 {
486 if aTileSize < 1 then aTileSize := 1;
487 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
488 mTileSize := aTileSize;
489 }
500 // init free list
502 begin
508 // init grid
510 // init proxies
518 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
523 begin
531 // ////////////////////////////////////////////////////////////////////////// //
533 var
535 begin
538 begin
542 begin
548 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);
553 var
556 begin
559 begin
562 begin
565 begin
567 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
569 // next cell
577 var
580 begin
588 begin
591 begin
593 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
595 // next cell
601 // ////////////////////////////////////////////////////////////////////////// //
602 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
603 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
607 begin
608 // fix coords
616 begin
618 begin
621 end
622 else
623 begin
632 begin
634 begin
637 end
638 else
639 begin
647 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
648 begin
650 begin
653 end
654 else
655 begin
666 // ////////////////////////////////////////////////////////////////////////// //
668 begin
674 begin
676 begin
678 begin
680 end
681 else
682 begin
690 begin
695 // ////////////////////////////////////////////////////////////////////////// //
697 var
700 begin
702 begin
703 // no free cells, want more
707 begin
719 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
724 begin
726 begin
728 begin
739 // ////////////////////////////////////////////////////////////////////////// //
740 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
741 var
744 begin
746 begin
747 // no free proxies, resize list
754 // get one from list
759 // add to used list
761 // statistics
767 begin
769 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
770 // add to free list
778 // ////////////////////////////////////////////////////////////////////////// //
779 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
780 const
782 var
785 begin
788 // fix coords
791 // go on
795 //tsize := mTileSize;
798 begin
802 begin
812 // ////////////////////////////////////////////////////////////////////////// //
814 var
819 begin
821 // add body to the given grid cell
824 begin
825 {$IF DEFINED(D2F_DEBUG)}
828 begin
831 begin
833 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
837 {$ENDIF}
840 begin
842 // check "has room" flag
844 begin
845 // can add here
847 begin
849 begin
852 exit;
857 // no room, go to next cell in list (if there is any)
860 // no room in cells, add new cell to list
862 // either no room, or no cell at all
872 var
874 begin
881 // assume that we cannot have one object added to bucket twice
883 var
887 begin
889 // find and remove cell
893 begin
896 begin
898 begin
899 // i found her!
901 begin
902 // this cell contains no elements, remove it
905 exit;
907 // remove element from bucket
909 begin
914 exit;
923 var
925 begin
932 // ////////////////////////////////////////////////////////////////////////// //
933 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
934 begin
942 begin
949 // ////////////////////////////////////////////////////////////////////////// //
951 var
954 begin
961 {$IF DEFINED(D2F_DEBUG_MOVER)}
962 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);
963 {$ENDIF}
965 // map -> grid
970 // did any corner crossed tile boundary?
975 begin
982 end
983 else
984 begin
992 //TODO: optimize for horizontal/vertical moves
994 var
1002 begin
1004 // check if tile coords was changed
1009 // map -> grid
1014 // check for heavy work
1025 {$IF DEFINED(D2F_DEBUG_MOVER)}
1026 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);
1027 {$ENDIF}
1029 begin
1030 // crossed tile boundary, do heavy work
1033 // cycle with old rect, remove body where it is necessary
1034 // optimized for horizontal moves
1035 {$IF DEFINED(D2F_DEBUG_MOVER)}
1036 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);
1037 {$ENDIF}
1038 // remove stale marks
1041 begin
1046 {$IF DEFINED(D2F_DEBUG_MOVER)}
1048 {$ENDIF}
1050 begin
1052 begin
1053 // this column is completely outside of new rect
1055 begin
1056 {$IF DEFINED(D2F_DEBUG_MOVER)}
1058 {$ENDIF}
1061 end
1062 else
1063 begin
1064 // heavy checks
1066 begin
1068 begin
1069 {$IF DEFINED(D2F_DEBUG_MOVER)}
1071 {$ENDIF}
1078 // cycle with new rect, add body where it is necessary
1081 begin
1086 {$IF DEFINED(D2F_DEBUG_MOVER)}
1088 {$ENDIF}
1090 begin
1092 begin
1093 // this column is completely outside of old rect
1095 begin
1096 {$IF DEFINED(D2F_DEBUG_MOVER)}
1098 {$ENDIF}
1101 end
1102 else
1103 begin
1104 // heavy checks
1106 begin
1108 begin
1109 {$IF DEFINED(D2F_DEBUG_MOVER)}
1111 {$ENDIF}
1118 // done
1119 end
1120 else
1121 begin
1122 {$IF DEFINED(D2F_DEBUG_MOVER)}
1123 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);
1124 {$ENDIF}
1126 // update coordinates
1132 var
1135 begin
1137 // check if tile coords was changed
1143 {$IF DEFINED(D2F_DEBUG_MOVER)}
1144 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);
1145 {$ENDIF}
1148 begin
1149 // crossed tile boundary, do heavy work
1154 end
1155 else
1156 begin
1157 // nothing to do with the grid, just fix size
1164 // ////////////////////////////////////////////////////////////////////////// //
1166 var
1168 begin
1171 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then cidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1176 // ////////////////////////////////////////////////////////////////////////// //
1177 // no callback: return `true` on the first hit
1178 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1179 var
1186 begin
1192 {$IF DEFINED(D2F_DEBUG_XXQ)}
1194 {$ENDIF}
1196 // make coords (0,0)-based
1203 {$IF DEFINED(D2F_DEBUG_XXQ)}
1204 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);
1205 {$ENDIF}
1207 // restore coords
1211 // increase query counter
1214 begin
1215 // just in case of overflow
1221 {$IF DEFINED(D2F_DEBUG_XXQ)}
1222 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1223 {$ENDIF}
1226 begin
1227 {$IF DEFINED(D2F_DEBUG_XXQ)}
1229 {$ENDIF}
1232 begin
1235 {$IF DEFINED(D2F_DEBUG_XXQ)}
1236 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);
1237 {$ENDIF}
1238 // shit. has to do it this way, so i can change tag in callback
1240 begin
1245 begin
1247 begin
1249 begin
1252 exit;
1254 end
1255 else
1256 begin
1259 exit;
1269 // ////////////////////////////////////////////////////////////////////////// //
1270 // no callback: return `true` on the first hit
1271 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1272 const
1274 var
1285 begin
1294 // fix coords
1299 //tsize := mTileSize;
1307 // increase query counter
1310 begin
1311 // just in case of overflow
1315 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1318 // go on
1320 begin
1324 begin
1327 // process cells
1330 begin
1333 begin
1336 // shit. has to do it this way, so i can change tag in callback
1345 begin
1347 end
1348 else
1349 begin
1352 exit;
1364 // ////////////////////////////////////////////////////////////////////////// //
1365 // no callback: return `true` on the nearest hit
1366 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1367 var
1369 begin
1374 // no callback: return `true` on the nearest hit
1375 // you are not supposed to understand this
1376 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1377 const
1379 var
1405 //swapped: Boolean = false; // true: xd is yd, and vice versa
1406 // horizontal walker
1407 {$IFDEF GRID_USE_ORTHO_ACCEL}
1409 //wksign: Integer;
1411 {$ENDIF}
1412 // skipper
1414 begin
1423 begin
1426 begin
1429 exit;
1441 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1442 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);
1443 {$ENDIF}
1450 // offset query coords to (0,0)-based
1456 // clip rectange
1462 // horizontal setup
1464 begin
1465 // from left to right
1468 end
1469 else
1470 begin
1471 // from right to left
1481 // vertical setup
1483 begin
1484 // from top to bottom
1487 end
1488 else
1489 begin
1490 // from bottom to top
1504 begin
1505 //swapped := true;
1514 end
1515 else
1516 begin
1530 begin
1531 // clip at top
1537 begin
1546 begin
1547 // clip at left
1558 begin
1559 // clip at bottom
1569 //if (term = xd) then exit; // this is the only point, get out of here
1575 // first move, to skip starting point
1576 // DON'T DO THIS! loop will take care of that
1578 begin
1579 //FIXME!
1582 begin
1584 begin
1586 begin
1589 end
1590 else
1591 begin
1594 end
1595 else
1596 begin
1601 exit;
1606 (*
1607 // move coords
1608 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1609 xd += stx;
1610 // done?
1611 if (xd = term) then exit;
1612 *)
1614 {$IF DEFINED(D2F_DEBUG)}
1615 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1616 {$ENDIF}
1617 // DON'T DO THIS! loop will take care of that
1618 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1619 //ccidx := mGrid[lastGA];
1621 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1622 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1623 {$ENDIF}
1625 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1630 // increase query counter
1633 begin
1634 // just in case of overflow
1640 {$IFDEF GRID_USE_ORTHO_ACCEL}
1641 // if this is strict horizontal/vertical trace, use optimized codepath
1643 begin
1644 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1645 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1646 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1647 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1649 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1650 {$IF DEFINED(D2F_DEBUG)}
1652 {$ENDIF}
1654 // one of those will never change
1657 //prevx := x;
1658 //prevy := y;
1659 {$IF DEFINED(D2F_DEBUG)}
1661 begin
1663 end
1664 else
1665 begin
1668 {$ENDIF}
1670 begin
1671 {$IF DEFINED(D2F_DEBUG)}
1672 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1673 {$ENDIF}
1674 // new tile?
1676 begin
1679 // convert coords to map (to avoid ajdusting coords inside the loop)
1682 begin
1685 begin
1690 // constant coord should be inside
1693 begin
1695 // inside the proxy?
1698 begin
1699 // setup prev[xy]
1701 begin
1703 begin
1708 exit;
1710 end
1711 else
1712 begin
1714 {$IF DEFINED(D2F_DEBUG)}
1715 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]);
1716 {$ENDIF}
1718 begin
1723 exit;
1726 continue;
1728 // remember this hitpoint if it is nearer than an old one
1729 // setup prev[xy]
1731 begin
1732 // horizontal trace
1736 begin
1737 // going left
1741 end
1742 else
1743 begin
1744 // going right
1749 end
1750 else
1751 begin
1752 // vertical trace
1756 begin
1757 // going up
1761 end
1762 else
1763 begin
1764 // going down
1771 begin
1773 begin
1778 exit;
1780 end
1781 else
1782 begin
1784 {$IF DEFINED(D2F_DEBUG)}
1785 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]);
1786 {$ENDIF}
1788 begin
1798 // next cell
1802 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1804 // skip to next tile
1806 begin
1808 begin
1809 // to the right
1811 {$IF DEFINED(D2F_DEBUG)}
1813 {$ENDIF}
1817 end
1818 else
1819 begin
1820 // to the left
1822 {$IF DEFINED(D2F_DEBUG)}
1824 {$ENDIF}
1829 end
1830 else
1831 begin
1833 begin
1834 // to the down
1836 {$IF DEFINED(D2F_DEBUG)}
1838 {$ENDIF}
1842 end
1843 else
1844 begin
1845 // to the up
1847 {$IF DEFINED(D2F_DEBUG)}
1849 {$ENDIF}
1857 // we can travel less than one cell
1860 exit;
1862 {$ENDIF}
1864 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1865 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1866 {$ENDIF}
1868 //e_LogWritefln('*********************', []);
1870 // can omit checks
1872 begin
1873 // check cell(s)
1874 {$IF DEFINED(D2F_DEBUG)}
1875 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1876 {$ENDIF}
1877 // new tile?
1879 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1880 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);
1881 {$ENDIF}
1883 begin
1884 // yes
1885 {$IF DEFINED(D2F_DEBUG)}
1886 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1887 {$ENDIF}
1889 begin
1890 // signal cell completion
1892 begin
1893 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1894 end
1896 begin
1899 exit;
1905 // has something to process in this tile?
1907 begin
1908 // process cell
1910 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1911 // convert coords to map (to avoid ajdusting coords inside the loop)
1914 // process cell list
1916 begin
1919 begin
1924 begin
1925 // can we process this proxy?
1927 begin
1930 begin
1932 begin
1937 exit;
1939 end
1940 else
1941 begin
1942 // remember this hitpoint if it is nearer than an old one
1944 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1945 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);
1946 {$ENDIF}
1948 begin
1956 end
1957 else
1958 begin
1959 // this is possibly interesting proxy, set "has more to check" flag
1964 // next cell
1967 // still has something interesting in this cell?
1969 begin
1970 // nope, don't process this cell anymore; signal cell completion
1973 begin
1975 end
1977 begin
1980 exit;
1985 begin
1986 // move to cell edge, as we have nothing to trace here anymore
1989 //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]);
1991 begin
1992 // step
1995 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
1998 //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]);
2001 //putPixel(xptr^, yptr^);
2002 // move coords
2008 // we can travel less than one cell
2010 begin
2012 end
2013 else
2014 begin
2023 // ////////////////////////////////////////////////////////////////////////// //
2024 //FIXME! optimize this with real tile walking
2025 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
2026 const
2028 var
2049 //swapped: Boolean = false; // true: xd is yd, and vice versa
2050 // horizontal walker
2051 {$IFDEF GRID_USE_ORTHO_ACCEL}
2053 //wksign: Integer;
2055 {$ENDIF}
2056 // skipper
2058 begin
2065 begin
2067 exit;
2082 // offset query coords to (0,0)-based
2088 // clip rectange
2094 // horizontal setup
2096 begin
2097 // from left to right
2100 end
2101 else
2102 begin
2103 // from right to left
2113 // vertical setup
2115 begin
2116 // from top to bottom
2119 end
2120 else
2121 begin
2122 // from bottom to top
2136 begin
2137 //swapped := true;
2146 end
2147 else
2148 begin
2162 begin
2163 // clip at top
2169 begin
2178 begin
2179 // clip at left
2190 begin
2191 // clip at bottom
2201 //if (term = xd) then exit; // this is the only point, get out of here
2207 // first move, to skip starting point
2208 // DON'T DO THIS! loop will take care of that
2210 begin
2212 exit;
2215 (*
2216 // move coords
2217 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2218 xd += stx;
2219 // done?
2220 if (xd = term) then exit;
2221 *)
2223 {$IF DEFINED(D2F_DEBUG)}
2224 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2225 {$ENDIF}
2226 // DON'T DO THIS! loop will take care of that
2227 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2228 //ccidx := mGrid[lastGA];
2233 // increase query counter
2236 begin
2237 // just in case of overflow
2243 {$IFDEF GRID_USE_ORTHO_ACCEL}
2244 // if this is strict horizontal/vertical trace, use optimized codepath
2246 begin
2247 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2248 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2249 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2250 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2252 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2253 {$IF DEFINED(D2F_DEBUG)}
2255 {$ENDIF}
2257 {$IF DEFINED(D2F_DEBUG)}
2259 begin
2261 end
2262 else
2263 begin
2266 {$ENDIF}
2268 begin
2269 {$IF DEFINED(D2F_DEBUG)}
2270 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; ay0=%d', [ga, xptr^+minx, yptr^+miny, ay0]);
2271 {$ENDIF}
2272 // new tile?
2274 begin
2277 // convert coords to map (to avoid ajdusting coords inside the loop)
2279 begin
2282 begin
2287 begin
2290 begin
2292 end
2293 else
2294 begin
2297 exit;
2301 // next cell
2305 // skip to next tile
2307 begin
2309 begin
2310 // to the right
2312 {$IF DEFINED(D2F_DEBUG)}
2314 {$ENDIF}
2318 end
2319 else
2320 begin
2321 // to the left
2323 {$IF DEFINED(D2F_DEBUG)}
2325 {$ENDIF}
2330 end
2331 else
2332 begin
2334 begin
2335 // to the down
2337 {$IF DEFINED(D2F_DEBUG)}
2339 {$ENDIF}
2343 end
2344 else
2345 begin
2346 // to the up
2348 {$IF DEFINED(D2F_DEBUG)}
2350 {$ENDIF}
2359 exit;
2361 {$ENDIF}
2363 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2364 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2365 {$ENDIF}
2368 // can omit checks
2370 begin
2371 // check cell(s)
2372 {$IF DEFINED(D2F_DEBUG)}
2373 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2374 {$ENDIF}
2375 // new tile?
2377 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2378 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);
2379 {$ENDIF}
2381 begin
2382 // yes
2383 {$IF DEFINED(D2F_DEBUG)}
2384 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2385 {$ENDIF}
2389 // has something to process in this tile?
2391 begin
2392 // process cell
2394 // process cell list
2396 begin
2399 begin
2404 begin
2407 begin
2409 end
2410 else
2411 begin
2414 exit;
2418 // next cell
2421 // nothing more interesting in this cell
2424 // move to cell edge, as we have nothing to trace here anymore
2427 //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]);
2429 begin
2430 // step
2433 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2436 //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]);
2438 //putPixel(xptr^, yptr^);
2439 // move coords