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
76 private
77 type
84 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
86 private
87 //mTileSize: Integer;
90 public
93 private
107 public
109 {$IF DEFINED(D2F_DEBUG)}
111 {$ENDIF}
113 private
136 public
137 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
140 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
149 // `false` if `body` is surely invalid
154 //WARNING: don't modify grid while any query is in progress (no checks are made!)
155 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
156 // no callback: return `true` on the first hit
157 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
159 //WARNING: don't modify grid while any query is in progress (no checks are made!)
160 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
161 // no callback: return object on the first hit or nil
162 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
164 //WARNING: don't modify grid while any query is in progress (no checks are made!)
165 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
166 // cb with `(nil)` will be called before processing new tile
167 // no callback: return object of the nearest hit or nil
168 // if `inverted` is true, trace will register bodies *exluding* tagmask
169 //WARNING: don't change tags in callbacks here!
170 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
171 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
173 //function traceOrthoRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload;
174 //function traceOrthoRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): 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 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
179 //WARNING: don't change tags in callbacks here!
180 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
182 // debug
187 public
188 //WARNING! no sanity checks!
200 // you are not supposed to understand this
201 // returns `true` if there is an intersection, and enter coords
202 // enter coords will be equal to (x0, y0) if starting point is inside the box
203 // if result is `false`, `inx` and `iny` are undefined
204 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
213 implementation
215 uses
219 // ////////////////////////////////////////////////////////////////////////// //
220 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
221 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
222 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
224 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
227 // ////////////////////////////////////////////////////////////////////////// //
228 // you are not supposed to understand this
229 // returns `true` if there is an intersection, and enter coords
230 // enter coords will be equal to (x0, y0) if starting point is inside the box
231 // if result is `false`, `inx` and `iny` are undefined
232 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
233 var
241 //!term: Integer;
245 begin
247 // why not
253 begin
254 // check this point
256 exit;
259 // check if staring point is inside the box
260 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
262 // clip rectange
268 // horizontal setup
270 begin
271 // from left to right
274 end
275 else
276 begin
277 // from right to left
287 // vertical setup
289 begin
290 // from top to bottom
293 end
294 else
295 begin
296 // from bottom to top
310 begin
319 end
320 else
321 begin
331 //!term := x1;
335 begin
336 // clip at top
342 begin
351 begin
352 // clip at left
362 (*
363 if (y1 > wy1) then
364 begin
365 // clip at bottom
366 temp := dx2*(wy1-y0)+dsx;
367 term := x0+temp div dy2;
368 rem := temp mod dy2;
369 if (rem = 0) then Dec(term);
370 end;
372 if (term > wx1) then term := wx1; // clip at right
374 Inc(term); // draw last point
375 //if (term = xd) then exit; // this is the only point, get out of here
376 *)
380 //!dx2 -= dy2;
388 // ////////////////////////////////////////////////////////////////////////// //
389 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
390 begin
403 begin
408 begin
413 begin
418 begin
423 // ////////////////////////////////////////////////////////////////////////// //
424 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
425 var
427 begin
429 {$IF DEFINED(D2F_DEBUG)}
431 {$ENDIF}
432 {
433 if aTileSize < 1 then aTileSize := 1;
434 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
435 mTileSize := aTileSize;
436 }
447 // init free list
449 begin
455 // init grid
457 // init proxies
465 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
470 begin
478 // ////////////////////////////////////////////////////////////////////////// //
480 var
482 begin
485 begin
489 begin
495 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);
500 var
503 begin
506 begin
509 begin
512 begin
514 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
516 // next cell
524 var
527 begin
535 begin
538 begin
540 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
542 // next cell
548 // ////////////////////////////////////////////////////////////////////////// //
549 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
550 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
554 begin
555 // fix coords
563 begin
565 begin
568 end
569 else
570 begin
579 begin
581 begin
584 end
585 else
586 begin
594 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
595 begin
597 begin
600 end
601 else
602 begin
613 // ////////////////////////////////////////////////////////////////////////// //
615 begin
621 begin
623 begin
625 begin
627 end
628 else
629 begin
637 begin
642 // ////////////////////////////////////////////////////////////////////////// //
644 var
647 begin
649 begin
650 // no free cells, want more
654 begin
666 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
671 begin
673 begin
675 begin
686 // ////////////////////////////////////////////////////////////////////////// //
687 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
688 var
691 begin
693 begin
694 // no free proxies, resize list
701 // get one from list
706 // add to used list
708 // statistics
714 begin
716 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
717 // add to free list
725 // ////////////////////////////////////////////////////////////////////////// //
726 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
727 const
729 var
732 begin
735 // fix coords
738 // go on
742 //tsize := mTileSize;
745 begin
749 begin
759 // ////////////////////////////////////////////////////////////////////////// //
761 var
766 begin
768 // add body to the given grid cell
771 begin
772 {$IF DEFINED(D2F_DEBUG)}
775 begin
778 begin
780 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
784 {$ENDIF}
787 begin
789 // check "has room" flag
791 begin
792 // can add here
794 begin
796 begin
799 exit;
804 // no room, go to next cell in list (if there is any)
807 // no room in cells, add new cell to list
809 // either no room, or no cell at all
819 var
821 begin
828 // assume that we cannot have one object added to bucket twice
830 var
834 begin
836 // find and remove cell
840 begin
843 begin
845 begin
846 // i found her!
848 begin
849 // this cell contains no elements, remove it
852 exit;
854 // remove element from bucket
856 begin
861 exit;
870 var
872 begin
879 // ////////////////////////////////////////////////////////////////////////// //
880 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
881 begin
889 begin
896 // ////////////////////////////////////////////////////////////////////////// //
898 var
901 begin
908 {$IF DEFINED(D2F_DEBUG_MOVER)}
909 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);
910 {$ENDIF}
912 // map -> grid
917 // did any corner crossed tile boundary?
922 begin
929 end
930 else
931 begin
939 //TODO: optimize for horizontal/vertical moves
941 var
949 begin
951 // check if tile coords was changed
956 // map -> grid
961 // check for heavy work
972 {$IF DEFINED(D2F_DEBUG_MOVER)}
973 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);
974 {$ENDIF}
976 begin
977 // crossed tile boundary, do heavy work
980 // cycle with old rect, remove body where it is necessary
981 // optimized for horizontal moves
982 {$IF DEFINED(D2F_DEBUG_MOVER)}
983 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);
984 {$ENDIF}
985 // remove stale marks
988 begin
993 {$IF DEFINED(D2F_DEBUG_MOVER)}
995 {$ENDIF}
997 begin
999 begin
1000 // this column is completely outside of new rect
1002 begin
1003 {$IF DEFINED(D2F_DEBUG_MOVER)}
1005 {$ENDIF}
1008 end
1009 else
1010 begin
1011 // heavy checks
1013 begin
1015 begin
1016 {$IF DEFINED(D2F_DEBUG_MOVER)}
1018 {$ENDIF}
1025 // cycle with new rect, add body where it is necessary
1028 begin
1033 {$IF DEFINED(D2F_DEBUG_MOVER)}
1035 {$ENDIF}
1037 begin
1039 begin
1040 // this column is completely outside of old rect
1042 begin
1043 {$IF DEFINED(D2F_DEBUG_MOVER)}
1045 {$ENDIF}
1048 end
1049 else
1050 begin
1051 // heavy checks
1053 begin
1055 begin
1056 {$IF DEFINED(D2F_DEBUG_MOVER)}
1058 {$ENDIF}
1065 // done
1066 end
1067 else
1068 begin
1069 {$IF DEFINED(D2F_DEBUG_MOVER)}
1070 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);
1071 {$ENDIF}
1073 // update coordinates
1079 var
1082 begin
1084 // check if tile coords was changed
1090 {$IF DEFINED(D2F_DEBUG_MOVER)}
1091 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);
1092 {$ENDIF}
1095 begin
1096 // crossed tile boundary, do heavy work
1101 end
1102 else
1103 begin
1104 // nothing to do with the grid, just fix size
1111 // ////////////////////////////////////////////////////////////////////////// //
1112 // no callback: return `true` on the first hit
1113 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1114 var
1121 begin
1127 {$IF DEFINED(D2F_DEBUG_XXQ)}
1129 {$ENDIF}
1131 // make coords (0,0)-based
1138 {$IF DEFINED(D2F_DEBUG_XXQ)}
1139 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);
1140 {$ENDIF}
1142 // restore coords
1146 // increase query counter
1149 begin
1150 // just in case of overflow
1156 {$IF DEFINED(D2F_DEBUG_XXQ)}
1157 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1158 {$ENDIF}
1161 begin
1162 {$IF DEFINED(D2F_DEBUG_XXQ)}
1164 {$ENDIF}
1167 begin
1170 {$IF DEFINED(D2F_DEBUG_XXQ)}
1171 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);
1172 {$ENDIF}
1173 // shit. has to do it this way, so i can change tag in callback
1175 begin
1180 begin
1182 begin
1184 begin
1187 exit;
1189 end
1190 else
1191 begin
1194 exit;
1204 // ////////////////////////////////////////////////////////////////////////// //
1205 // no callback: return `true` on the first hit
1206 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1207 const
1209 var
1220 begin
1229 // fix coords
1234 //tsize := mTileSize;
1242 // increase query counter
1245 begin
1246 // just in case of overflow
1250 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1253 // go on
1255 begin
1259 begin
1262 // process cells
1265 begin
1268 begin
1271 // shit. has to do it this way, so i can change tag in callback
1280 begin
1282 end
1283 else
1284 begin
1287 exit;
1299 // ////////////////////////////////////////////////////////////////////////// //
1300 // no callback: return `true` on the nearest hit
1301 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1302 var
1304 begin
1309 // no callback: return `true` on the nearest hit
1310 // you are not supposed to understand this
1311 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1312 const
1314 var
1340 //swapped: Boolean = false; // true: xd is yd, and vice versa
1341 // horizontal walker
1342 {$IFDEF GRID_USE_ORTHO_ACCEL}
1344 //wksign: Integer;
1346 {$ENDIF}
1347 // skipper
1349 begin
1358 begin
1361 begin
1364 exit;
1376 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1377 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);
1378 {$ENDIF}
1385 // offset query coords to (0,0)-based
1391 // clip rectange
1397 // horizontal setup
1399 begin
1400 // from left to right
1403 end
1404 else
1405 begin
1406 // from right to left
1416 // vertical setup
1418 begin
1419 // from top to bottom
1422 end
1423 else
1424 begin
1425 // from bottom to top
1439 begin
1440 //swapped := true;
1449 end
1450 else
1451 begin
1465 begin
1466 // clip at top
1472 begin
1481 begin
1482 // clip at left
1493 begin
1494 // clip at bottom
1504 //if (term = xd) then exit; // this is the only point, get out of here
1510 // first move, to skip starting point
1511 // DON'T DO THIS! loop will take care of that
1513 begin
1514 //FIXME!
1517 begin
1519 begin
1521 begin
1524 end
1525 else
1526 begin
1529 end
1530 else
1531 begin
1536 exit;
1541 (*
1542 // move coords
1543 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1544 xd += stx;
1545 // done?
1546 if (xd = term) then exit;
1547 *)
1549 {$IF DEFINED(D2F_DEBUG)}
1550 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1551 {$ENDIF}
1552 // DON'T DO THIS! loop will take care of that
1553 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1554 //ccidx := mGrid[lastGA];
1556 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1557 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1558 {$ENDIF}
1560 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1565 // increase query counter
1568 begin
1569 // just in case of overflow
1575 {$IFDEF GRID_USE_ORTHO_ACCEL}
1576 // if this is strict horizontal/vertical trace, use optimized codepath
1578 begin
1579 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1580 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1581 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1582 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1584 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1585 {$IF DEFINED(D2F_DEBUG)}
1587 {$ENDIF}
1589 // one of those will never change
1592 //prevx := x;
1593 //prevy := y;
1594 {$IF DEFINED(D2F_DEBUG)}
1596 begin
1598 end
1599 else
1600 begin
1603 {$ENDIF}
1605 begin
1606 {$IF DEFINED(D2F_DEBUG)}
1607 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1608 {$ENDIF}
1609 // new tile?
1611 begin
1614 // convert coords to map (to avoid ajdusting coords inside the loop)
1617 begin
1620 begin
1625 // constant coord should be inside
1628 begin
1630 // inside the proxy?
1633 begin
1634 // setup prev[xy]
1636 begin
1638 begin
1643 exit;
1645 end
1646 else
1647 begin
1649 {$IF DEFINED(D2F_DEBUG)}
1650 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]);
1651 {$ENDIF}
1653 begin
1658 exit;
1661 continue;
1663 // remember this hitpoint if it is nearer than an old one
1664 // setup prev[xy]
1666 begin
1667 // horizontal trace
1671 begin
1672 // going left
1676 end
1677 else
1678 begin
1679 // going right
1684 end
1685 else
1686 begin
1687 // vertical trace
1691 begin
1692 // going up
1696 end
1697 else
1698 begin
1699 // going down
1706 begin
1708 begin
1713 exit;
1715 end
1716 else
1717 begin
1719 {$IF DEFINED(D2F_DEBUG)}
1720 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]);
1721 {$ENDIF}
1723 begin
1733 // next cell
1737 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
1739 // skip to next tile
1741 begin
1743 begin
1744 // to the right
1746 {$IF DEFINED(D2F_DEBUG)}
1748 {$ENDIF}
1752 end
1753 else
1754 begin
1755 // to the left
1757 {$IF DEFINED(D2F_DEBUG)}
1759 {$ENDIF}
1764 end
1765 else
1766 begin
1768 begin
1769 // to the down
1771 {$IF DEFINED(D2F_DEBUG)}
1773 {$ENDIF}
1777 end
1778 else
1779 begin
1780 // to the up
1782 {$IF DEFINED(D2F_DEBUG)}
1784 {$ENDIF}
1792 // we can travel less than one cell
1795 exit;
1797 {$ENDIF}
1799 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1800 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1801 {$ENDIF}
1803 //e_LogWritefln('*********************', []);
1805 // can omit checks
1807 begin
1808 // check cell(s)
1809 {$IF DEFINED(D2F_DEBUG)}
1810 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1811 {$ENDIF}
1812 // new tile?
1814 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1815 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);
1816 {$ENDIF}
1818 begin
1819 // yes
1820 {$IF DEFINED(D2F_DEBUG)}
1821 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1822 {$ENDIF}
1824 begin
1825 // signal cell completion
1827 begin
1828 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
1829 end
1831 begin
1834 exit;
1840 // has something to process in this tile?
1842 begin
1843 // process cell
1845 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1846 // convert coords to map (to avoid ajdusting coords inside the loop)
1849 // process cell list
1851 begin
1854 begin
1859 begin
1860 // can we process this proxy?
1862 begin
1865 begin
1867 begin
1872 exit;
1874 end
1875 else
1876 begin
1877 // remember this hitpoint if it is nearer than an old one
1879 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1880 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);
1881 {$ENDIF}
1883 begin
1891 end
1892 else
1893 begin
1894 // this is possibly interesting proxy, set "has more to check" flag
1899 // next cell
1902 // still has something interesting in this cell?
1904 begin
1905 // nope, don't process this cell anymore; signal cell completion
1908 begin
1910 end
1912 begin
1915 exit;
1920 begin
1921 // move to cell edge, as we have nothing to trace here anymore
1924 //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]);
1926 begin
1927 // step
1930 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
1933 //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]);
1936 //putPixel(xptr^, yptr^);
1937 // move coords
1943 // we can travel less than one cell
1945 begin
1947 end
1948 else
1949 begin
1958 // ////////////////////////////////////////////////////////////////////////// //
1959 //FIXME! optimize this with real tile walking
1960 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1961 const
1963 var
1984 //swapped: Boolean = false; // true: xd is yd, and vice versa
1985 // horizontal walker
1986 {$IFDEF GRID_USE_ORTHO_ACCEL}
1988 //wksign: Integer;
1990 {$ENDIF}
1991 // skipper
1993 begin
2000 begin
2002 exit;
2017 // offset query coords to (0,0)-based
2023 // clip rectange
2029 // horizontal setup
2031 begin
2032 // from left to right
2035 end
2036 else
2037 begin
2038 // from right to left
2048 // vertical setup
2050 begin
2051 // from top to bottom
2054 end
2055 else
2056 begin
2057 // from bottom to top
2071 begin
2072 //swapped := true;
2081 end
2082 else
2083 begin
2097 begin
2098 // clip at top
2104 begin
2113 begin
2114 // clip at left
2125 begin
2126 // clip at bottom
2136 //if (term = xd) then exit; // this is the only point, get out of here
2142 // first move, to skip starting point
2143 // DON'T DO THIS! loop will take care of that
2145 begin
2147 exit;
2150 (*
2151 // move coords
2152 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2153 xd += stx;
2154 // done?
2155 if (xd = term) then exit;
2156 *)
2158 {$IF DEFINED(D2F_DEBUG)}
2159 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2160 {$ENDIF}
2161 // DON'T DO THIS! loop will take care of that
2162 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2163 //ccidx := mGrid[lastGA];
2168 // increase query counter
2171 begin
2172 // just in case of overflow
2178 {$IFDEF GRID_USE_ORTHO_ACCEL}
2179 // if this is strict horizontal/vertical trace, use optimized codepath
2181 begin
2182 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2183 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2184 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2185 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2187 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2188 {$IF DEFINED(D2F_DEBUG)}
2190 {$ENDIF}
2192 // one of those will never change
2195 {$IF DEFINED(D2F_DEBUG)}
2197 begin
2199 end
2200 else
2201 begin
2204 {$ENDIF}
2206 begin
2207 {$IF DEFINED(D2F_DEBUG)}
2208 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2209 {$ENDIF}
2210 // new tile?
2212 begin
2215 // convert coords to map (to avoid ajdusting coords inside the loop)
2218 begin
2221 begin
2226 begin
2229 begin
2231 end
2232 else
2233 begin
2236 exit;
2240 // next cell
2244 // skip to next tile
2246 begin
2248 begin
2249 // to the right
2251 {$IF DEFINED(D2F_DEBUG)}
2253 {$ENDIF}
2257 end
2258 else
2259 begin
2260 // to the left
2262 {$IF DEFINED(D2F_DEBUG)}
2264 {$ENDIF}
2269 end
2270 else
2271 begin
2273 begin
2274 // to the down
2276 {$IF DEFINED(D2F_DEBUG)}
2278 {$ENDIF}
2282 end
2283 else
2284 begin
2285 // to the up
2287 {$IF DEFINED(D2F_DEBUG)}
2289 {$ENDIF}
2298 exit;
2300 {$ENDIF}
2302 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2303 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2304 {$ENDIF}
2307 // can omit checks
2309 begin
2310 // check cell(s)
2311 {$IF DEFINED(D2F_DEBUG)}
2312 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
2313 {$ENDIF}
2314 // new tile?
2316 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2317 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);
2318 {$ENDIF}
2320 begin
2321 // yes
2322 {$IF DEFINED(D2F_DEBUG)}
2323 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
2324 {$ENDIF}
2328 // has something to process in this tile?
2330 begin
2331 // process cell
2333 // convert coords to map (to avoid ajdusting coords inside the loop)
2336 // process cell list
2338 begin
2341 begin
2346 begin
2349 begin
2351 end
2352 else
2353 begin
2356 exit;
2360 // next cell
2363 // nothing more interesting in this cell
2366 // move to cell edge, as we have nothing to trace here anymore
2369 //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]);
2371 begin
2372 // step
2375 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2378 //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]);
2380 //putPixel(xptr^, yptr^);
2381 // move coords