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 public
49 type
52 private
59 private
68 public
77 private
78 type
85 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
87 private
88 //mTileSize: Integer;
91 public
94 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 (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; 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;
1239 // increase query counter
1242 begin
1243 // just in case of overflow
1247 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1250 // go on
1252 begin
1256 begin
1259 // process cells
1262 begin
1265 begin
1268 // shit. has to do it this way, so i can change tag in callback
1277 begin
1279 end
1280 else
1281 begin
1283 exit;
1293 // ////////////////////////////////////////////////////////////////////////// //
1294 // no callback: return `true` on the nearest hit
1295 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1296 var
1298 begin
1303 // no callback: return `true` on the nearest hit
1304 // you are not supposed to understand this
1305 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1306 const
1308 var
1334 // horizontal walker
1335 {$IFDEF GRID_USE_ORTHO_ACCEL}
1337 //wksign: Integer;
1339 {$ENDIF}
1340 begin
1349 begin
1352 begin
1355 exit;
1367 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1368 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);
1369 {$ENDIF}
1376 // offset query coords to (0,0)-based
1382 // clip rectange
1388 // horizontal setup
1390 begin
1391 // from left to right
1394 end
1395 else
1396 begin
1397 // from right to left
1407 // vertical setup
1409 begin
1410 // from top to bottom
1413 end
1414 else
1415 begin
1416 // from bottom to top
1430 begin
1439 end
1440 else
1441 begin
1455 begin
1456 // clip at top
1462 begin
1471 begin
1472 // clip at left
1483 begin
1484 // clip at bottom
1494 //if (term = xd) then exit; // this is the only point, get out of here
1500 // first move, to skip starting point
1501 // DON'T DO THIS! loop will take care of that
1503 begin
1506 begin
1508 begin
1510 begin
1513 end
1514 else
1515 begin
1518 end
1519 else
1520 begin
1525 exit;
1530 (*
1531 // move coords
1532 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
1533 xd += stx;
1534 // done?
1535 if (xd = term) then exit;
1536 *)
1538 {$IF DEFINED(D2F_DEBUG)}
1539 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1540 {$ENDIF}
1541 // DON'T DO THIS! loop will take care of that
1542 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
1543 //ccidx := mGrid[lastGA];
1545 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1546 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
1547 {$ENDIF}
1549 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1551 // increase query counter
1554 begin
1555 // just in case of overflow
1561 {$IFDEF GRID_USE_ORTHO_ACCEL}
1562 // if this is strict horizontal/vertical trace, use optimized codepath
1564 begin
1565 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
1566 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
1567 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
1568 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
1570 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
1571 {$IF DEFINED(D2F_DEBUG)}
1573 {$ENDIF}
1575 // one of those will never change
1578 //prevx := x;
1579 //prevy := y;
1580 {$IF DEFINED(D2F_DEBUG)}
1582 begin
1584 end
1585 else
1586 begin
1589 {$ENDIF}
1591 begin
1592 {$IF DEFINED(D2F_DEBUG)}
1593 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
1594 {$ENDIF}
1595 // new tile?
1597 begin
1600 // convert coords to map (to avoid ajdusting coords inside the loop)
1603 begin
1606 begin
1611 // constant coord should be inside
1614 begin
1616 // inside the proxy?
1619 begin
1620 // setup prev[xy]
1622 begin
1624 begin
1628 exit;
1630 end
1631 else
1632 begin
1634 {$IF DEFINED(D2F_DEBUG)}
1635 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]);
1636 {$ENDIF}
1638 begin
1642 exit;
1645 continue;
1647 // remember this hitpoint if it is nearer than an old one
1648 // setup prev[xy]
1650 begin
1651 // horizontal trace
1655 begin
1656 // going left
1660 end
1661 else
1662 begin
1663 // going right
1668 end
1669 else
1670 begin
1671 // vertical trace
1675 begin
1676 // going up
1680 end
1681 else
1682 begin
1683 // going down
1690 begin
1692 begin
1696 exit;
1698 end
1699 else
1700 begin
1702 {$IF DEFINED(D2F_DEBUG)}
1703 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]);
1704 {$ENDIF}
1706 begin
1716 // next cell
1721 // skip to next tile
1723 begin
1725 begin
1726 // to the right
1728 {$IF DEFINED(D2F_DEBUG)}
1730 {$ENDIF}
1734 end
1735 else
1736 begin
1737 // to the left
1739 {$IF DEFINED(D2F_DEBUG)}
1741 {$ENDIF}
1746 end
1747 else
1748 begin
1750 begin
1751 // to the down
1753 {$IF DEFINED(D2F_DEBUG)}
1755 {$ENDIF}
1759 end
1760 else
1761 begin
1762 // to the up
1764 {$IF DEFINED(D2F_DEBUG)}
1766 {$ENDIF}
1774 // we can travel less than one cell
1776 exit;
1778 {$ENDIF}
1780 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1781 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1782 {$ENDIF}
1785 // can omit checks
1787 begin
1788 // check cell(s)
1789 {$IF DEFINED(D2F_DEBUG)}
1790 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)');
1791 {$ENDIF}
1792 // new tile?
1794 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1795 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);
1796 {$ENDIF}
1798 begin
1799 // yes
1800 {$IF DEFINED(D2F_DEBUG)}
1801 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny);
1802 {$ENDIF}
1804 begin
1805 // signal cell completion
1807 begin
1809 end
1811 begin
1813 exit;
1819 // has something to process in this tile?
1821 begin
1822 // process cell
1824 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1825 // convert coords to map (to avoid ajdusting coords inside the loop)
1828 // process cell list
1830 begin
1833 begin
1838 begin
1839 // can we process this proxy?
1841 begin
1844 begin
1846 begin
1850 exit;
1852 (*
1853 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1854 distSq := distanceSq(ax0, ay0, prevx, prevy);
1855 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);
1856 if (distSq < lastDistSq) then
1857 begin
1858 wasHit := true;
1859 lastDistSq := distSq;
1860 ex := prevx;
1861 ey := prevy;
1862 lastObj := px.mObj;
1863 end;
1864 {$ENDIF}
1865 *)
1866 end
1867 else
1868 begin
1869 // remember this hitpoint if it is nearer than an old one
1871 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
1872 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);
1873 {$ENDIF}
1875 begin
1883 end
1884 else
1885 begin
1886 // this is possibly interesting proxy, set "has more to check" flag
1891 // next cell
1894 // still has something interesting in this cell?
1896 begin
1897 // nope, don't process this cell anymore; signal cell completion
1900 begin
1902 end
1904 begin
1906 exit;
1910 //putPixel(xptr^, yptr^);
1911 // move coords
1917 // we can travel less than one cell
1919 begin
1921 end
1922 else
1923 begin
1930 // ////////////////////////////////////////////////////////////////////////// //
1931 //FIXME! optimize this with real tile walking
1932 function TBodyGridBase.forEachAlongLine (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1933 const
1935 var
1954 //tedist: Integer;
1955 begin
1977 // `x` and `y` will be in grid coords
1981 // increase query counter
1984 begin
1985 // just in case of overflow
1991 // cache various things
1992 //tsize := mTileSize;
1998 // setup distance and flags
2001 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
2004 // it is slightly faster this way
2008 if (log) then e_WriteLog(Format('tracing: (%d,%d)-(%d,%d)', [x, y, x1-minx, y1-miny]), MSG_NOTIFY);
2010 // now trace
2013 begin
2015 // do one step
2018 // invariant: one of those always changed
2019 {$IF DEFINED(D2F_DEBUG)}
2020 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
2021 {$ENDIF}
2024 // invariant: we always doing a step
2025 {$IF DEFINED(D2F_DEBUG)}
2027 {$ENDIF}
2028 begin
2029 // check for crossing tile/grid boundary
2031 begin
2032 // we're still in grid
2034 // check for tile edge crossing
2040 // crossed tile edge?
2042 begin
2043 // setup new cell index
2045 if (log) then e_WriteLog(Format(' stepped to new tile (%d,%d) -- (%d,%d)', [(x div tsize), (y div tsize), x, y]), MSG_NOTIFY);
2046 end
2047 else
2049 begin
2050 // we have nothing interesting here anymore, jump directly to tile edge
2051 (*
2052 if (incx = 0) then
2053 begin
2054 // vertical line
2055 if (incy < 0) then tedist := y-(y and (not tsize)) else tedist := (y or (tsize-1))-y;
2056 if (tedist > 1) then
2057 begin
2058 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);
2059 y += incy*tedist;
2060 Inc(i, tedist);
2061 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);
2062 end;
2063 end
2064 else if (incy = 0) then
2065 begin
2066 // horizontal line
2067 if (incx < 0) then tedist := x-(x and (not tsize)) else tedist := (x or (tsize-1))-x;
2068 if (tedist > 1) then
2069 begin
2070 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);
2071 x += incx*tedist;
2072 Inc(i, tedist);
2073 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);
2074 end;
2075 end;
2076 *)
2077 (*
2078 else if (
2079 // get minimal distance to tile edges
2080 if (incx < 0) then tedist := x-(x and (not tsize)) else if (incx > 0) then tedist := (x or (tsize+1))-x else tedist := 0;
2081 {$IF DEFINED(D2F_DEBUG)}
2082 if (tedist < 0) then raise Exception.Create('internal bug in grid raycaster (2.x)');
2083 {$ENDIF}
2084 if (incy < 0) then f := y-(y and (not tsize)) else if (incy > 0) then f := (y or (tsize+1))-y else f := 0;
2085 {$IF DEFINED(D2F_DEBUG)}
2086 if (f < 0) then raise Exception.Create('internal bug in grid raycaster (2.y)');
2087 {$ENDIF}
2088 if (tedist = 0) then tedist := f else if (f <> 0) then tedist := minInt(tedist, f);
2089 // do jump
2090 if (tedist > 1) then
2091 begin
2092 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);
2093 xerr += dx*tedist;
2094 yerr += dy*tedist;
2095 if (xerr >= 0) then begin x += incx*((xerr div d)+1); xerr := (xerr mod d)-d; end;
2096 if (yerr >= 0) then begin y += incy*((yerr div d)+1); yerr := (yerr mod d)-d; end;
2097 Inc(i, tedist);
2098 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);
2099 end;
2100 *)
2102 end
2103 else
2104 begin
2105 // out of grid
2110 // has something to process in the current cell?
2112 begin
2113 // process cell
2115 // convert coords to map (to avoid ajdusting coords inside the loop)
2116 //Inc(x, minx);
2117 //Inc(y, miny);
2118 // process cell list
2120 begin
2123 begin
2128 begin
2133 // next cell
2137 // convert coords to grid
2138 //Dec(x, minx);
2139 //Dec(y, miny);