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}
24 {$DEFINE LINEAABB2}
27 interface
29 uses
30 mempool;
32 (*
33 * In order to make this usable for kind-of-recursive calls,
34 * we'll use "frame memory pool" to return results. That is,
35 * we will allocate a memory pool that will be cleared on
36 * frame start, and then used as a simple "no-free" allocator.
37 * Grid will put results into this pool, and will never bother
38 * to free it. Caller should call "release" on result, and
39 * the pool will throw away everything.
40 * No more callbacks, of course.
41 *)
43 const
46 type
50 public
51 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
52 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
58 private
59 const
62 public
63 type
66 private
73 private
85 public
100 private
101 type
110 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
112 private
113 //mTileSize: Integer;
117 public
120 type
122 private
126 public
133 private
147 public
149 {$IF DEFINED(D2F_DEBUG)}
151 {$ENDIF}
153 private
173 public
174 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
177 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
186 // `false` if `body` is surely invalid
191 //WARNING: don't modify grid while any query is in progress (no checks are made!)
192 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
193 // no callback: return `true` on the first hit
194 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
196 //WARNING: don't modify grid while any query is in progress (no checks are made!)
197 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
198 // no callback: return object on the first hit or nil
199 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
203 //WARNING: don't modify grid while any query is in progress (no checks are made!)
204 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
205 // cb with `(nil)` will be called before processing new tile
206 // no callback: return object of the nearest hit or nil
207 // if `inverted` is true, trace will register bodies *exluding* tagmask
208 //WARNING: don't change tags in callbacks here!
209 {
210 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
211 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
212 }
214 //WARNING: don't modify grid while any query is in progress (no checks are made!)
215 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
216 // cb with `(nil)` will be called before processing new tile
217 // no callback: return object of the nearest hit or nil
218 // if `inverted` is true, trace will register bodies *exluding* tagmask
219 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
220 //WARNING: don't change tags in callbacks here!
221 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
222 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
224 // return `false` if we're still inside at the end
225 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
226 // `true`: endpoint will point at the last "inside" pixel
227 // `false`: endpoint will be (ax1, ay1)
228 //WARNING: don't change tags in callbacks here!
229 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
231 //WARNING: don't modify grid while any query is in progress (no checks are made!)
232 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
233 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
234 //WARNING: don't change tags in callbacks here!
235 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
237 // trace box with the given velocity; return object hit (if any)
238 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
239 //WARNING: don't change tags in callbacks here!
240 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
242 // debug
247 public
248 //WARNING! no sanity checks!
260 type
261 // common structure for all line tracers
263 public
266 private
274 public
275 // call `setyp` after this
280 // this will use `w[xy][01]` to clip coords
281 // return `false` if the whole line was clipped away
282 // on `true`, you should process first point, and go on
285 // call this *after* doing a step
286 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
289 // as you will prolly call `done()` after doing a step anyway, this will do it for you
290 // move to next point, return `true` when the line is complete (i.e. you should stop)
293 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
298 public
299 // current coords
306 //function minInt (a, b: Integer): Integer; inline;
307 //function maxInt (a, b: Integer): Integer; inline;
310 implementation
312 uses
316 // ////////////////////////////////////////////////////////////////////////// //
317 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
318 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
319 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
320 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
323 // ////////////////////////////////////////////////////////////////////////// //
325 begin
330 begin
331 // clip rectange
339 var
341 begin
342 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
346 begin
348 end
349 else
350 begin
359 // check for ortho lines
361 begin
362 // horizontal
369 end
371 begin
372 // vertical
379 end
380 else
381 begin
382 // diagonal
384 begin
385 // horizontal
389 end
390 else
391 begin
392 // vertical
408 // true: done
410 begin
412 begin
416 end
417 else
418 begin
427 // true: done
429 var
433 begin
438 // strictly horizontal?
440 begin
441 // only xd
443 begin
444 // xd: to left edge
447 end
448 else
449 begin
450 // xd: to right edge
456 exit;
459 // strictly vertical?
461 begin
462 // only xd
464 begin
465 // yd: to top edge
468 end
469 else
470 begin
471 // yd: to bottom edge
477 exit;
480 // diagonal
482 // calculate xwalk
484 begin
487 end
488 else
489 begin
494 // calculate ywalk
496 begin
499 end
500 else
501 begin
506 {
507 while (xd <> ex) and (yd <> ey) do
508 begin
509 if horiz then
510 begin
511 xd += stx;
512 err += errinc;
513 if (err >= 0) then begin err -= errmax; yd += sty; end;
514 end
515 else
516 begin
517 yd += sty;
518 err += errinc;
519 if (err >= 0) then begin err -= errmax; xd += stx; end;
520 end;
521 Dec(stleft);
522 if (stleft < 1) then begin result := true; exit; end;
523 end;
524 }
528 begin
529 // in which dir we want to walk?
533 begin
536 begin
540 end
541 else
542 begin
545 begin
550 // check for walk completion
559 // ////////////////////////////////////////////////////////////////////////// //
560 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
561 begin
574 begin
579 begin
584 begin
589 begin
594 begin
599 begin
604 // ////////////////////////////////////////////////////////////////////////// //
605 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
606 begin
615 begin
617 begin
619 begin
623 exit;
633 begin
638 // ////////////////////////////////////////////////////////////////////////// //
639 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
640 var
642 begin
644 {$IF DEFINED(D2F_DEBUG)}
646 {$ENDIF}
647 {
648 if aTileSize < 1 then aTileSize := 1;
649 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
650 mTileSize := aTileSize;
651 }
662 // init free list
664 begin
670 // init grid
672 // init proxies
680 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
685 begin
693 // ////////////////////////////////////////////////////////////////////////// //
695 var
697 begin
700 begin
704 begin
710 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]), TMsgType.Notify);
715 var
718 begin
721 begin
724 begin
727 begin
729 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
731 // next cell
739 var
742 begin
750 begin
753 begin
755 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
757 // next cell
763 // ////////////////////////////////////////////////////////////////////////// //
764 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
765 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
769 begin
770 // fix coords
778 begin
780 begin
783 end
784 else
785 begin
794 begin
796 begin
799 end
800 else
801 begin
809 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
810 begin
812 begin
815 end
816 else
817 begin
828 // ////////////////////////////////////////////////////////////////////////// //
830 begin
831 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
836 begin
838 begin
840 begin
842 end
843 else
844 begin
852 begin
857 // ////////////////////////////////////////////////////////////////////////// //
859 var
862 begin
864 begin
865 // no free cells, want more
869 begin
881 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
886 begin
888 begin
890 begin
901 // ////////////////////////////////////////////////////////////////////////// //
902 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
903 var
906 begin
908 begin
909 // no free proxies, resize list
916 // get one from list
921 // add to used list
923 // statistics
929 begin
931 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
932 // add to free list
940 // ////////////////////////////////////////////////////////////////////////// //
941 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
942 var
946 begin
949 // fix coords
952 // go on
961 // clip rect
967 // do the work
969 begin
971 begin
979 // ////////////////////////////////////////////////////////////////////////// //
981 var
986 begin
988 // add body to the given grid cell
991 begin
992 {$IF DEFINED(D2F_DEBUG)}
995 begin
998 begin
1000 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1004 {$ENDIF}
1007 begin
1009 // check "has room" flag
1011 begin
1012 // can add here
1014 begin
1016 begin
1019 exit;
1024 // no room, go to next cell in list (if there is any)
1027 // no room in cells, add new cell to list
1029 // either no room, or no cell at all
1039 // assume that we cannot have one object added to bucket twice
1041 var
1045 begin
1047 // find and remove cell
1051 begin
1054 begin
1056 begin
1057 // i found her!
1059 begin
1060 // this cell contains no elements, remove it
1063 exit;
1065 // remove element from bucket
1067 begin
1072 exit;
1081 // ////////////////////////////////////////////////////////////////////////// //
1082 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1083 begin
1086 //insertInternal(result);
1092 var
1094 begin
1097 //removeInternal(body);
1103 // ////////////////////////////////////////////////////////////////////////// //
1105 var
1108 begin
1115 {$IF DEFINED(D2F_DEBUG_MOVER)}
1116 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);
1117 {$ENDIF}
1119 // map -> grid
1124 // did any corner crossed tile boundary?
1129 begin
1130 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1131 //removeInternal(body);
1137 //insertInternal(body);
1139 end
1140 else
1141 begin
1150 //TODO: optimize for horizontal/vertical moves
1152 var
1160 begin
1162 // check if tile coords was changed
1167 // map -> grid
1172 // check for heavy work
1183 {$IF DEFINED(D2F_DEBUG_MOVER)}
1184 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);
1185 {$ENDIF}
1187 begin
1188 // crossed tile boundary, do heavy work
1191 // cycle with old rect, remove body where it is necessary
1192 // optimized for horizontal moves
1193 {$IF DEFINED(D2F_DEBUG_MOVER)}
1194 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);
1195 {$ENDIF}
1196 // remove stale marks
1199 begin
1204 {$IF DEFINED(D2F_DEBUG_MOVER)}
1206 {$ENDIF}
1208 begin
1210 begin
1211 // this column is completely outside of new rect
1213 begin
1214 {$IF DEFINED(D2F_DEBUG_MOVER)}
1216 {$ENDIF}
1219 end
1220 else
1221 begin
1222 // heavy checks
1224 begin
1226 begin
1227 {$IF DEFINED(D2F_DEBUG_MOVER)}
1229 {$ENDIF}
1236 // cycle with new rect, add body where it is necessary
1239 begin
1244 {$IF DEFINED(D2F_DEBUG_MOVER)}
1246 {$ENDIF}
1248 begin
1250 begin
1251 // this column is completely outside of old rect
1253 begin
1254 {$IF DEFINED(D2F_DEBUG_MOVER)}
1256 {$ENDIF}
1259 end
1260 else
1261 begin
1262 // heavy checks
1264 begin
1266 begin
1267 {$IF DEFINED(D2F_DEBUG_MOVER)}
1269 {$ENDIF}
1276 // done
1277 end
1278 else
1279 begin
1280 {$IF DEFINED(D2F_DEBUG_MOVER)}
1281 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);
1282 {$ENDIF}
1284 // update coordinates
1291 var
1294 begin
1296 // check if tile coords was changed
1302 {$IF DEFINED(D2F_DEBUG_MOVER)}
1303 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);
1304 {$ENDIF}
1307 begin
1308 // crossed tile boundary, do heavy work
1309 //removeInternal(body);
1313 //insertInternal(body);
1315 end
1316 else
1317 begin
1318 // nothing to do with the grid, just fix size
1325 // ////////////////////////////////////////////////////////////////////////// //
1327 var
1329 begin
1332 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1337 // ////////////////////////////////////////////////////////////////////////// //
1338 // no callback: return `true` on the first hit
1339 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1340 var
1347 begin
1353 {$IF DEFINED(D2F_DEBUG_XXQ)}
1355 {$ENDIF}
1357 // make coords (0,0)-based
1364 {$IF DEFINED(D2F_DEBUG_XXQ)}
1365 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);
1366 {$ENDIF}
1368 // restore coords
1372 // increase query counter
1375 begin
1376 // just in case of overflow
1382 {$IF DEFINED(D2F_DEBUG_XXQ)}
1383 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1384 {$ENDIF}
1387 begin
1388 {$IF DEFINED(D2F_DEBUG_XXQ)}
1390 {$ENDIF}
1393 begin
1396 {$IF DEFINED(D2F_DEBUG_XXQ)}
1397 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);
1398 {$ENDIF}
1399 // shit. has to do it this way, so i can change tag in callback
1401 begin
1406 begin
1408 begin
1410 begin
1413 exit;
1415 end
1416 else
1417 begin
1420 exit;
1430 // ////////////////////////////////////////////////////////////////////////// //
1431 // no callback: return `true` on the first hit
1432 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1433 var
1445 begin
1454 // fix coords
1469 // clip rect
1476 // has something to do
1480 // increase query counter
1483 begin
1484 // just in case of overflow
1488 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1491 // go on
1493 begin
1495 begin
1496 // process cells
1499 begin
1502 begin
1505 // shit! has to do it this way, so i can change tag in callback
1514 begin
1516 end
1517 else
1518 begin
1521 exit;
1533 // ////////////////////////////////////////////////////////////////////////// //
1534 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1535 var
1546 //px0, py0, px1, py1: Integer;
1547 begin
1558 // make query coords (0,0)-based
1570 // increase query counter
1573 begin
1574 // just in case of overflow
1580 repeat
1582 // check tile
1584 // process cells
1586 begin
1589 begin
1594 begin
1597 begin
1600 exit;
1604 // next cell
1607 // done processing cells, move to next tile
1614 // ////////////////////////////////////////////////////////////////////////// //
1615 // trace box with the given velocity; return object hit (if any)
1616 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1617 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1618 var
1629 begin
1643 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1649 // just in case
1655 // increase query counter
1658 begin
1659 // just in case of overflow
1666 begin
1668 begin
1671 begin
1674 begin
1679 begin
1682 begin
1685 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1687 begin
1692 begin
1696 exit;
1701 // next cell
1708 begin
1711 // just in case, compensate for floating point inexactness
1712 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1713 begin
1723 // ////////////////////////////////////////////////////////////////////////// //
1724 {.$DEFINE D2F_DEBUG_OTR}
1725 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1726 var
1737 {$IF DEFINED(D2F_DEBUG_OTR)}
1739 {$ENDIF}
1740 begin
1754 // offset query coords to (0,0)-based
1761 begin
1763 // vertical
1765 begin
1766 // down
1768 //if (ay0 < 0) then ay0 := 0;
1772 end
1773 else
1774 begin
1775 // up
1777 //if (ay1 < 0) then ay1 := 0;
1782 // check tile
1784 begin
1790 begin
1793 begin
1799 begin
1800 // bound c0 and c1 to cell
1803 // fill the thing
1804 {$IF DEFINED(D2F_DEBUG_OTR)}
1805 e_LogWritefln('**px.y0=%s; px.y1=%s; c0=%s; c1=%s; celly0=%s; celly1=%s; [%s..%s]', [px.y0-miny, px.y1-miny, c0, c1, celly0, celly1, c0-celly0, (c0-celly0)+(c1-c0)]);
1806 {$ENDIF}
1807 //assert(c0 <= c1);
1811 // next cell
1814 {$IF DEFINED(D2F_DEBUG_OTR)}
1815 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1819 {$ENDIF}
1820 // now go till we hit cell boundary or empty space
1822 begin
1823 // up
1825 begin
1826 {$IF DEFINED(D2F_DEBUG_OTR)}
1827 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1828 {$ENDIF}
1832 {$IF DEFINED(D2F_DEBUG_OTR)}
1833 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1834 {$ENDIF}
1836 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1837 end
1838 else
1839 begin
1840 // down
1846 end
1847 else
1848 begin
1849 // horizontal
1855 // ////////////////////////////////////////////////////////////////////////// //
1856 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1857 var
1859 begin
1864 // no callback: return `true` on the nearest hit
1865 // you are not supposed to understand this
1866 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1867 var
1882 begin
1892 // make query coords (0,0)-based
1903 {$IF DEFINED(D2F_DEBUG)}
1904 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1905 {$ENDIF}
1910 // increase query counter
1913 begin
1914 // just in case of overflow
1920 repeat
1922 {$IF DEFINED(D2F_DEBUG)}
1924 {$ENDIF}
1925 // check tile
1927 // process cells
1930 begin
1933 begin
1938 begin
1941 begin
1944 // get adjusted proxy coords
1949 {$IF DEFINED(D2F_DEBUG)}
1950 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1951 {$ENDIF}
1952 // inside?
1954 begin
1955 // oops
1960 {$IF DEFINED(D2F_DEBUG)}
1962 {$ENDIF}
1963 exit;
1965 // do line-vs-aabb test
1967 begin
1968 // hit detected
1970 {$IF DEFINED(D2F_DEBUG)}
1971 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1972 {$ENDIF}
1974 begin
1984 // next cell
1987 // done processing cells; exit if we registered a hit
1988 // next cells can't have better candidates, obviously
1991 // move to next tile
1998 // ////////////////////////////////////////////////////////////////////////// //
1999 // no callback: return `true` on the nearest hit
2000 (*
2001 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2002 var
2003 ex, ey: Integer;
2004 begin
2005 result := traceRayOld(ex, ey, x0, y0, x1, y1, cb, tagmask);
2006 end;
2009 // no callback: return `true` on the nearest hit
2010 // you are not supposed to understand this
2011 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2012 var
2013 wx0, wy0, wx1, wy1: Integer; // window coordinates
2014 stx, sty: Integer; // "steps" for x and y axes
2015 dsx, dsy: Integer; // "lengthes" for x and y axes
2016 dx2, dy2: Integer; // "double lengthes" for x and y axes
2017 xd, yd: Integer; // current coord
2018 e: Integer; // "error" (as in bresenham algo)
2019 rem: Integer;
2020 term: Integer;
2021 xptr, yptr: PInteger;
2022 xfixed: Boolean;
2023 temp: Integer;
2024 prevx, prevy: Integer;
2025 lastDistSq: Integer;
2026 ccidx, curci: Integer;
2027 hasUntried: Boolean;
2028 lastGA: Integer = -1;
2029 ga, x, y: Integer;
2030 lastObj: ITP;
2031 wasHit: Boolean = false;
2032 gw, gh, minx, miny, maxx, maxy: Integer;
2033 cc: PGridCell;
2034 px: PBodyProxyRec;
2035 lq: LongWord;
2036 f, ptag, distSq: Integer;
2037 x0, y0, x1, y1: Integer;
2038 //swapped: Boolean = false; // true: xd is yd, and vice versa
2039 // horizontal walker
2040 {$IFDEF GRID_USE_ORTHO_ACCEL}
2041 wklen, wkstep: Integer;
2042 //wksign: Integer;
2043 hopt: Boolean;
2044 {$ENDIF}
2045 // skipper
2046 xdist, ydist: Integer;
2047 begin
2048 result := Default(ITP);
2049 lastObj := Default(ITP);
2050 tagmask := tagmask and TagFullMask;
2051 ex := ax1; // why not?
2052 ey := ay1; // why not?
2053 if (tagmask = 0) then exit;
2055 if (ax0 = ax1) and (ay0 = ay1) then
2056 begin
2057 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2058 if (result <> nil) then
2059 begin
2060 if assigned(cb) and not cb(result, ptag, ax0, ay0, ax0, ay0) then result := Default(ITP);
2061 end;
2062 exit;
2063 end;
2065 lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1;
2067 gw := mWidth;
2068 gh := mHeight;
2069 minx := mMinX;
2070 miny := mMinY;
2071 maxx := gw*mTileSize-1;
2072 maxy := gh*mTileSize-1;
2074 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2075 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);
2076 {$ENDIF}
2078 x0 := ax0;
2079 y0 := ay0;
2080 x1 := ax1;
2081 y1 := ay1;
2083 // offset query coords to (0,0)-based
2084 Dec(x0, minx);
2085 Dec(y0, miny);
2086 Dec(x1, minx);
2087 Dec(y1, miny);
2089 // clip rectange
2090 wx0 := 0;
2091 wy0 := 0;
2092 wx1 := maxx;
2093 wy1 := maxy;
2095 // horizontal setup
2096 if (x0 < x1) then
2097 begin
2098 // from left to right
2099 if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
2100 stx := 1; // going right
2101 end
2102 else
2103 begin
2104 // from right to left
2105 if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
2106 stx := -1; // going left
2107 x0 := -x0;
2108 x1 := -x1;
2109 wx0 := -wx0;
2110 wx1 := -wx1;
2111 swapInt(wx0, wx1);
2112 end;
2114 // vertical setup
2115 if (y0 < y1) then
2116 begin
2117 // from top to bottom
2118 if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
2119 sty := 1; // going down
2120 end
2121 else
2122 begin
2123 // from bottom to top
2124 if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
2125 sty := -1; // going up
2126 y0 := -y0;
2127 y1 := -y1;
2128 wy0 := -wy0;
2129 wy1 := -wy1;
2130 swapInt(wy0, wy1);
2131 end;
2133 dsx := x1-x0;
2134 dsy := y1-y0;
2136 if (dsx < dsy) then
2137 begin
2138 //swapped := true;
2139 xptr := @yd;
2140 yptr := @xd;
2141 swapInt(x0, y0);
2142 swapInt(x1, y1);
2143 swapInt(dsx, dsy);
2144 swapInt(wx0, wy0);
2145 swapInt(wx1, wy1);
2146 swapInt(stx, sty);
2147 end
2148 else
2149 begin
2150 xptr := @xd;
2151 yptr := @yd;
2152 end;
2154 dx2 := 2*dsx;
2155 dy2 := 2*dsy;
2156 xd := x0;
2157 yd := y0;
2158 e := 2*dsy-dsx;
2159 term := x1;
2161 xfixed := false;
2162 if (y0 < wy0) then
2163 begin
2164 // clip at top
2165 temp := dx2*(wy0-y0)-dsx;
2166 xd += temp div dy2;
2167 rem := temp mod dy2;
2168 if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
2169 if (xd+1 >= wx0) then
2170 begin
2171 yd := wy0;
2172 e -= rem+dsx;
2173 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2174 if (xd < wx0) then begin xd += 1; e += dy2; end; //???
2175 xfixed := true;
2176 end;
2177 end;
2179 if (not xfixed) and (x0 < wx0) then
2180 begin
2181 // clip at left
2182 temp := dy2*(wx0-x0);
2183 yd += temp div dx2;
2184 rem := temp mod dx2;
2185 if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
2186 xd := wx0;
2187 e += rem;
2188 if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
2189 end;
2191 if (y1 > wy1) then
2192 begin
2193 // clip at bottom
2194 temp := dx2*(wy1-y0)+dsx;
2195 term := x0+temp div dy2;
2196 rem := temp mod dy2;
2197 if (rem = 0) then Dec(term);
2198 end;
2200 if (term > wx1) then term := wx1; // clip at right
2202 Inc(term); // draw last point
2203 //if (term = xd) then exit; // this is the only point, get out of here
2205 if (sty = -1) then yd := -yd;
2206 if (stx = -1) then begin xd := -xd; term := -term; end;
2207 dx2 -= dy2;
2209 // first move, to skip starting point
2210 // DON'T DO THIS! loop will take care of that
2211 if (xd = term) then
2212 begin
2213 //FIXME!
2214 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2215 if (result <> nil) then
2216 begin
2217 if assigned(cb) then
2218 begin
2219 if cb(result, ptag, ax0, ay0, ax0, ay0) then
2220 begin
2221 ex := ax0;
2222 ey := ay0;
2223 end
2224 else
2225 begin
2226 result := nil;
2227 end;
2228 end
2229 else
2230 begin
2231 ex := ax0;
2232 ey := ay0;
2233 end;
2234 end;
2235 exit;
2236 end;
2238 prevx := xptr^+minx;
2239 prevy := yptr^+miny;
2240 ( *
2241 // move coords
2242 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2243 xd += stx;
2244 // done?
2245 if (xd = term) then exit;
2246 * )
2248 {$IF DEFINED(D2F_DEBUG)}
2249 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2250 {$ENDIF}
2251 // DON'T DO THIS! loop will take care of that
2252 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2253 //ccidx := mGrid[lastGA];
2255 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2256 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2257 {$ENDIF}
2259 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2261 if mInQuery then raise Exception.Create('recursive queries aren''t supported');
2262 mInQuery := true;
2264 // increase query counter
2265 Inc(mLastQuery);
2266 if (mLastQuery = 0) then
2267 begin
2268 // just in case of overflow
2269 mLastQuery := 1;
2270 for f := 0 to High(mProxies) do mProxies[f].mQueryMark := 0;
2271 end;
2272 lq := mLastQuery;
2274 {$IFDEF GRID_USE_ORTHO_ACCEL}
2275 // if this is strict horizontal/vertical trace, use optimized codepath
2276 if (ax0 = ax1) or (ay0 = ay1) then
2277 begin
2278 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2279 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2280 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2281 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2282 hopt := (ay0 = ay1); // horizontal?
2283 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2284 {$IF DEFINED(D2F_DEBUG)}
2285 if dbgShowTraceLog then e_LogWritefln('optimized htrace; wklen=%d', [wklen]);
2286 {$ENDIF}
2287 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2288 // one of those will never change
2289 x := xptr^+minx;
2290 y := yptr^+miny;
2291 while (wklen > 0) do
2292 begin
2293 {$IF DEFINED(D2F_DEBUG)}
2294 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2295 {$ENDIF}
2296 // new tile?
2297 if (ga <> lastGA) then
2298 begin
2299 lastGA := ga;
2300 ccidx := mGrid[lastGA];
2301 // convert coords to map (to avoid ajdusting coords inside the loop)
2302 if hopt then x := xptr^+minx else y := yptr^+miny;
2303 while (ccidx <> -1) do
2304 begin
2305 cc := @mCells[ccidx];
2306 for f := 0 to GridCellBucketSize-1 do
2307 begin
2308 if (cc.bodies[f] = -1) then break;
2309 px := @mProxies[cc.bodies[f]];
2310 ptag := px.mTag;
2311 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and
2312 // constant coord should be inside
2313 ((hopt and (y >= px.y0) and (y <= px.y1)) or
2314 ((not hopt) and (x >= px.x0) and (x <= px.x1))) then
2315 begin
2316 px.mQueryMark := lq; // mark as processed
2317 // inside the proxy?
2318 if (hopt and (x > px.x0) and (x < px.x1)) or
2319 ((not hopt) and (y > px.y0) and (y < px.y1)) then
2320 begin
2321 // setup prev[xy]
2322 if assigned(cb) then
2323 begin
2324 if cb(px.mObj, ptag, x, y, x, y) then
2325 begin
2326 result := px.mObj;
2327 ex := x;
2328 ey := y;
2329 mInQuery := false;
2330 exit;
2331 end;
2332 end
2333 else
2334 begin
2335 distSq := distanceSq(ax0, ay0, x, y);
2336 {$IF DEFINED(D2F_DEBUG)}
2337 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]);
2338 {$ENDIF}
2339 if (distSq < lastDistSq) then
2340 begin
2341 ex := x;
2342 ey := y;
2343 result := px.mObj;
2344 mInQuery := false;
2345 exit;
2346 end;
2347 end;
2348 continue;
2349 end;
2350 // remember this hitpoint if it is nearer than an old one
2351 // setup prev[xy]
2352 if hopt then
2353 begin
2354 // horizontal trace
2355 prevy := y;
2356 y := yptr^+miny;
2357 if (stx < 0) then
2358 begin
2359 // going left
2360 if (x < px.x1) then continue; // not on the right edge
2361 x := px.x1;
2362 prevx := x+1;
2363 end
2364 else
2365 begin
2366 // going right
2367 if (x > px.x0) then continue; // not on the left edge
2368 x := px.x0;
2369 prevx := x-1;
2370 end;
2371 end
2372 else
2373 begin
2374 // vertical trace
2375 prevx := x;
2376 x := xptr^+minx;
2377 if (stx < 0) then
2378 begin
2379 // going up
2380 if (y < px.y1) then continue; // not on the bottom edge
2381 y := px.y1;
2382 prevy := x+1;
2383 end
2384 else
2385 begin
2386 // going down
2387 if (y > px.y0) then continue; // not on the top edge
2388 y := px.y0;
2389 prevy := y-1;
2390 end;
2391 end;
2392 if assigned(cb) then
2393 begin
2394 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2395 begin
2396 result := px.mObj;
2397 ex := prevx;
2398 ey := prevy;
2399 mInQuery := false;
2400 exit;
2401 end;
2402 end
2403 else
2404 begin
2405 distSq := distanceSq(ax0, ay0, prevx, prevy);
2406 {$IF DEFINED(D2F_DEBUG)}
2407 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]);
2408 {$ENDIF}
2409 if (distSq < lastDistSq) then
2410 begin
2411 wasHit := true;
2412 lastDistSq := distSq;
2413 ex := prevx;
2414 ey := prevy;
2415 lastObj := px.mObj;
2416 end;
2417 end;
2418 end;
2419 end;
2420 // next cell
2421 ccidx := cc.next;
2422 end;
2423 if wasHit and not assigned(cb) then begin result := lastObj; mInQuery := false; exit; end;
2424 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2425 end;
2426 // skip to next tile
2427 if hopt then
2428 begin
2429 if (stx > 0) then
2430 begin
2431 // to the right
2432 wkstep := ((xptr^ or (mTileSize-1))+1)-xptr^;
2433 {$IF DEFINED(D2F_DEBUG)}
2434 if dbgShowTraceLog then e_LogWritefln(' right step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2435 {$ENDIF}
2436 if (wkstep >= wklen) then break;
2437 Inc(xptr^, wkstep);
2438 Inc(ga);
2439 end
2440 else
2441 begin
2442 // to the left
2443 wkstep := xptr^-((xptr^ and (not (mTileSize-1)))-1);
2444 {$IF DEFINED(D2F_DEBUG)}
2445 if dbgShowTraceLog then e_LogWritefln(' left step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2446 {$ENDIF}
2447 if (wkstep >= wklen) then break;
2448 Dec(xptr^, wkstep);
2449 Dec(ga);
2450 end;
2451 end
2452 else
2453 begin
2454 if (stx > 0) then
2455 begin
2456 // to the down
2457 wkstep := ((yptr^ or (mTileSize-1))+1)-yptr^;
2458 {$IF DEFINED(D2F_DEBUG)}
2459 if dbgShowTraceLog then e_LogWritefln(' down step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2460 {$ENDIF}
2461 if (wkstep >= wklen) then break;
2462 Inc(yptr^, wkstep);
2463 Inc(ga, mWidth);
2464 end
2465 else
2466 begin
2467 // to the up
2468 wkstep := yptr^-((yptr^ and (not (mTileSize-1)))-1);
2469 {$IF DEFINED(D2F_DEBUG)}
2470 if dbgShowTraceLog then e_LogWritefln(' up step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2471 {$ENDIF}
2472 if (wkstep >= wklen) then break;
2473 Dec(yptr^, wkstep);
2474 Dec(ga, mWidth);
2475 end;
2476 end;
2477 Dec(wklen, wkstep);
2478 end;
2479 // we can travel less than one cell
2480 if wasHit and not assigned(cb) then result := lastObj else begin ex := ax1; ey := ay1; end;
2481 mInQuery := false;
2482 exit;
2483 end;
2484 {$ENDIF}
2486 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2487 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2488 {$ENDIF}
2490 //e_LogWritefln('*********************', []);
2491 ccidx := -1;
2492 // can omit checks
2493 while (xd <> term) do
2494 begin
2495 // check cell(s)
2496 {$IF DEFINED(D2F_DEBUG)}
2497 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2498 {$ENDIF}
2499 // new tile?
2500 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2501 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2502 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);
2503 {$ENDIF}
2504 if (ga <> lastGA) then
2505 begin
2506 // yes
2507 {$IF DEFINED(D2F_DEBUG)}
2508 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2509 {$ENDIF}
2510 if (ccidx <> -1) then
2511 begin
2512 // signal cell completion
2513 if assigned(cb) then
2514 begin
2515 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2516 end
2517 else if wasHit then
2518 begin
2519 result := lastObj;
2520 mInQuery := false;
2521 exit;
2522 end;
2523 end;
2524 lastGA := ga;
2525 ccidx := mGrid[lastGA];
2526 end;
2527 // has something to process in this tile?
2528 if (ccidx <> -1) then
2529 begin
2530 // process cell
2531 curci := ccidx;
2532 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2533 // convert coords to map (to avoid ajdusting coords inside the loop)
2534 x := xptr^+minx;
2535 y := yptr^+miny;
2536 // process cell list
2537 while (curci <> -1) do
2538 begin
2539 cc := @mCells[curci];
2540 for f := 0 to GridCellBucketSize-1 do
2541 begin
2542 if (cc.bodies[f] = -1) then break;
2543 px := @mProxies[cc.bodies[f]];
2544 ptag := px.mTag;
2545 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
2546 begin
2547 // can we process this proxy?
2548 if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
2549 begin
2550 px.mQueryMark := lq; // mark as processed
2551 if assigned(cb) then
2552 begin
2553 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2554 begin
2555 result := px.mObj;
2556 ex := prevx;
2557 ey := prevy;
2558 mInQuery := false;
2559 exit;
2560 end;
2561 end
2562 else
2563 begin
2564 // remember this hitpoint if it is nearer than an old one
2565 distSq := distanceSq(ax0, ay0, prevx, prevy);
2566 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2567 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);
2568 {$ENDIF}
2569 if (distSq < lastDistSq) then
2570 begin
2571 wasHit := true;
2572 lastDistSq := distSq;
2573 ex := prevx;
2574 ey := prevy;
2575 lastObj := px.mObj;
2576 end;
2577 end;
2578 end
2579 else
2580 begin
2581 // this is possibly interesting proxy, set "has more to check" flag
2582 hasUntried := true;
2583 end;
2584 end;
2585 end;
2586 // next cell
2587 curci := cc.next;
2588 end;
2589 // still has something interesting in this cell?
2590 if not hasUntried then
2591 begin
2592 // nope, don't process this cell anymore; signal cell completion
2593 ccidx := -1;
2594 if assigned(cb) then
2595 begin
2596 if cb(nil, 0, x, y, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2597 end
2598 else if wasHit then
2599 begin
2600 result := lastObj;
2601 mInQuery := false;
2602 exit;
2603 end;
2604 end;
2605 end;
2606 if (ccidx = -1) then
2607 begin
2608 // move to cell edge, as we have nothing to trace here anymore
2609 if (stx < 0) then xdist := xd and (not (mTileSize-1)) else xdist := xd or (mTileSize-1);
2610 if (sty < 0) then ydist := yd and (not (mTileSize-1)) else ydist := yd or (mTileSize-1);
2611 //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]);
2612 while (xd <> xdist) and (yd <> ydist) do
2613 begin
2614 // step
2615 xd += stx;
2616 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2617 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2618 if (xd = term) then break;
2619 end;
2620 //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]);
2621 if (xd = term) then break;
2622 end;
2623 //putPixel(xptr^, yptr^);
2624 // move coords
2625 prevx := xptr^+minx;
2626 prevy := yptr^+miny;
2627 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2628 xd += stx;
2629 end;
2630 // we can travel less than one cell
2631 if wasHit and not assigned(cb) then
2632 begin
2633 result := lastObj;
2634 end
2635 else
2636 begin
2637 ex := ax1; // why not?
2638 ey := ay1; // why not?
2639 end;
2641 mInQuery := false;
2642 end;
2643 *)