30ed8ee0ae9dc062de5a3897a238de1a2e1c6d48
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
53 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
54 //type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
60 private
61 const
64 public
65 type
68 private
75 private
87 public
102 private
103 type
112 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
114 private
115 //mTileSize: Integer;
119 public
122 type
124 private
128 public
135 private
147 //mInQuery: Boolean;
149 public
151 {$IF DEFINED(D2F_DEBUG)}
153 {$ENDIF}
155 private
175 public
176 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
179 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
188 // `false` if `body` is surely invalid
193 //WARNING: don't modify grid while any query is in progress (no checks are made!)
194 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
195 // no callback: return `true` on the first hit
196 //function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
197 // return number of ITP thingys put into frame pool
198 function forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
200 //WARNING: don't modify grid while any query is in progress (no checks are made!)
201 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
202 // no callback: return object on the first hit or nil
203 //function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1{; exittag: PInteger=nil}): ITP;
204 function forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
208 //WARNING: don't modify grid while any query is in progress (no checks are made!)
209 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
210 // cb with `(nil)` will be called before processing new tile
211 // no callback: return object of the nearest hit or nil
212 // if `inverted` is true, trace will register bodies *exluding* tagmask
213 //WARNING: don't change tags in callbacks here!
214 {
215 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
216 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
217 }
219 //WARNING: don't modify grid while any query is in progress (no checks are made!)
220 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
221 // return object of the nearest hit or nil
222 // if `inverted` is true, trace will register bodies *exluding* tagmask
223 //WARNING: don't change tags in callbacks here!
225 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
227 // return `false` if we're still inside at the end
228 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
229 // `true`: endpoint will point at the last "inside" pixel
230 // `false`: endpoint will be (ax1, ay1)
231 //WARNING: don't change tags in callbacks here!
232 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
234 //WARNING: don't modify grid while any query is in progress (no checks are made!)
235 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
236 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
237 //WARNING: don't change tags in callbacks here!
238 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
240 // trace box with the given velocity; return object hit (if any)
241 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
242 //WARNING: don't change tags in callbacks here!
243 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; tagmask: Integer=-1): ITP;
245 // debug
250 public
251 //WARNING! no sanity checks!
263 type
264 // common structure for all line tracers
266 public
269 private
277 public
278 // call `setyp` after this
283 // this will use `w[xy][01]` to clip coords
284 // return `false` if the whole line was clipped away
285 // on `true`, you should process first point, and go on
288 // call this *after* doing a step
289 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
292 // as you will prolly call `done()` after doing a step anyway, this will do it for you
293 // move to next point, return `true` when the line is complete (i.e. you should stop)
296 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
301 public
302 // current coords
309 //function minInt (a, b: Integer): Integer; inline;
310 //function maxInt (a, b: Integer): Integer; inline;
313 implementation
315 uses
319 // ////////////////////////////////////////////////////////////////////////// //
320 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
321 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
322 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
323 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
326 // ////////////////////////////////////////////////////////////////////////// //
328 begin
333 begin
334 // clip rectange
342 var
344 begin
345 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
349 begin
351 end
352 else
353 begin
362 // check for ortho lines
364 begin
365 // horizontal
372 end
374 begin
375 // vertical
382 end
383 else
384 begin
385 // diagonal
387 begin
388 // horizontal
392 end
393 else
394 begin
395 // vertical
411 // true: done
413 begin
415 begin
419 end
420 else
421 begin
430 // true: done
432 var
436 begin
441 // strictly horizontal?
443 begin
444 // only xd
446 begin
447 // xd: to left edge
450 end
451 else
452 begin
453 // xd: to right edge
459 exit;
462 // strictly vertical?
464 begin
465 // only xd
467 begin
468 // yd: to top edge
471 end
472 else
473 begin
474 // yd: to bottom edge
480 exit;
483 // diagonal
485 // calculate xwalk
487 begin
490 end
491 else
492 begin
497 // calculate ywalk
499 begin
502 end
503 else
504 begin
509 {
510 while (xd <> ex) and (yd <> ey) do
511 begin
512 if horiz then
513 begin
514 xd += stx;
515 err += errinc;
516 if (err >= 0) then begin err -= errmax; yd += sty; end;
517 end
518 else
519 begin
520 yd += sty;
521 err += errinc;
522 if (err >= 0) then begin err -= errmax; xd += stx; end;
523 end;
524 Dec(stleft);
525 if (stleft < 1) then begin result := true; exit; end;
526 end;
527 }
531 begin
532 // in which dir we want to walk?
536 begin
539 begin
543 end
544 else
545 begin
548 begin
553 // check for walk completion
562 // ////////////////////////////////////////////////////////////////////////// //
563 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
564 begin
577 begin
582 begin
587 begin
592 begin
597 begin
602 begin
607 // ////////////////////////////////////////////////////////////////////////// //
608 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
609 begin
618 begin
620 begin
622 begin
626 exit;
636 begin
641 // ////////////////////////////////////////////////////////////////////////// //
642 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
643 var
645 begin
647 {$IF DEFINED(D2F_DEBUG)}
649 {$ENDIF}
650 {
651 if aTileSize < 1 then aTileSize := 1;
652 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
653 mTileSize := aTileSize;
654 }
665 // init free list
667 begin
673 // init grid
675 // init proxies
683 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
688 begin
696 // ////////////////////////////////////////////////////////////////////////// //
698 var
700 begin
703 begin
707 begin
713 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);
718 var
721 begin
724 begin
727 begin
730 begin
732 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
734 // next cell
742 var
745 begin
753 begin
756 begin
758 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
760 // next cell
766 // ////////////////////////////////////////////////////////////////////////// //
767 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
768 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
772 begin
773 // fix coords
781 begin
783 begin
786 end
787 else
788 begin
797 begin
799 begin
802 end
803 else
804 begin
812 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
813 begin
815 begin
818 end
819 else
820 begin
831 // ////////////////////////////////////////////////////////////////////////// //
833 begin
834 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
839 begin
841 begin
843 begin
845 end
846 else
847 begin
855 begin
860 // ////////////////////////////////////////////////////////////////////////// //
862 var
865 begin
867 begin
868 // no free cells, want more
872 begin
884 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
889 begin
891 begin
893 begin
904 // ////////////////////////////////////////////////////////////////////////// //
905 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
906 var
909 begin
911 begin
912 // no free proxies, resize list
919 // get one from list
924 // add to used list
926 // statistics
932 begin
934 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
935 // add to free list
943 // ////////////////////////////////////////////////////////////////////////// //
944 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
945 var
949 begin
952 // fix coords
955 // go on
964 // clip rect
970 // do the work
972 begin
974 begin
982 // ////////////////////////////////////////////////////////////////////////// //
984 var
989 begin
991 // add body to the given grid cell
994 begin
995 {$IF DEFINED(D2F_DEBUG)}
998 begin
1001 begin
1003 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1007 {$ENDIF}
1010 begin
1012 // check "has room" flag
1014 begin
1015 // can add here
1017 begin
1019 begin
1022 exit;
1027 // no room, go to next cell in list (if there is any)
1030 // no room in cells, add new cell to list
1032 // either no room, or no cell at all
1042 // assume that we cannot have one object added to bucket twice
1044 var
1048 begin
1050 // find and remove cell
1054 begin
1057 begin
1059 begin
1060 // i found her!
1062 begin
1063 // this cell contains no elements, remove it
1066 exit;
1068 // remove element from bucket
1070 begin
1075 exit;
1084 // ////////////////////////////////////////////////////////////////////////// //
1085 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1086 begin
1089 //insertInternal(result);
1095 var
1097 begin
1100 //removeInternal(body);
1106 // ////////////////////////////////////////////////////////////////////////// //
1108 var
1111 begin
1118 {$IF DEFINED(D2F_DEBUG_MOVER)}
1119 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);
1120 {$ENDIF}
1122 // map -> grid
1127 // did any corner crossed tile boundary?
1132 begin
1133 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1134 //removeInternal(body);
1140 //insertInternal(body);
1142 end
1143 else
1144 begin
1153 //TODO: optimize for horizontal/vertical moves
1155 var
1163 begin
1165 // check if tile coords was changed
1170 // map -> grid
1175 // check for heavy work
1186 {$IF DEFINED(D2F_DEBUG_MOVER)}
1187 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);
1188 {$ENDIF}
1190 begin
1191 // crossed tile boundary, do heavy work
1194 // cycle with old rect, remove body where it is necessary
1195 // optimized for horizontal moves
1196 {$IF DEFINED(D2F_DEBUG_MOVER)}
1197 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);
1198 {$ENDIF}
1199 // remove stale marks
1202 begin
1207 {$IF DEFINED(D2F_DEBUG_MOVER)}
1209 {$ENDIF}
1211 begin
1213 begin
1214 // this column is completely outside of new rect
1216 begin
1217 {$IF DEFINED(D2F_DEBUG_MOVER)}
1219 {$ENDIF}
1222 end
1223 else
1224 begin
1225 // heavy checks
1227 begin
1229 begin
1230 {$IF DEFINED(D2F_DEBUG_MOVER)}
1232 {$ENDIF}
1239 // cycle with new rect, add body where it is necessary
1242 begin
1247 {$IF DEFINED(D2F_DEBUG_MOVER)}
1249 {$ENDIF}
1251 begin
1253 begin
1254 // this column is completely outside of old rect
1256 begin
1257 {$IF DEFINED(D2F_DEBUG_MOVER)}
1259 {$ENDIF}
1262 end
1263 else
1264 begin
1265 // heavy checks
1267 begin
1269 begin
1270 {$IF DEFINED(D2F_DEBUG_MOVER)}
1272 {$ENDIF}
1279 // done
1280 end
1281 else
1282 begin
1283 {$IF DEFINED(D2F_DEBUG_MOVER)}
1284 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);
1285 {$ENDIF}
1287 // update coordinates
1294 var
1297 begin
1299 // check if tile coords was changed
1305 {$IF DEFINED(D2F_DEBUG_MOVER)}
1306 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);
1307 {$ENDIF}
1310 begin
1311 // crossed tile boundary, do heavy work
1312 //removeInternal(body);
1316 //insertInternal(body);
1318 end
1319 else
1320 begin
1321 // nothing to do with the grid, just fix size
1328 // ////////////////////////////////////////////////////////////////////////// //
1330 var
1332 begin
1335 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1340 // ////////////////////////////////////////////////////////////////////////// //
1341 // no callback: return `true` on the first hit
1342 function TBodyGridBase.forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1343 var
1351 begin
1356 {$IF DEFINED(D2F_DEBUG_XXQ)}
1358 {$ENDIF}
1360 // make coords (0,0)-based
1367 {$IF DEFINED(D2F_DEBUG_XXQ)}
1368 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);
1369 {$ENDIF}
1371 // restore coords
1375 // increase query counter
1378 begin
1379 // just in case of overflow
1385 {$IF DEFINED(D2F_DEBUG_XXQ)}
1386 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1387 {$ENDIF}
1390 begin
1391 {$IF DEFINED(D2F_DEBUG_XXQ)}
1392 //if (assigned(cb)) then e_WriteLog(Format(' cell #%d', [curci]), MSG_NOTIFY);
1393 {$ENDIF}
1396 begin
1399 {$IF DEFINED(D2F_DEBUG_XXQ)}
1400 //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);
1401 {$ENDIF}
1408 begin
1420 // ////////////////////////////////////////////////////////////////////////// //
1421 // no callback: return `true` on the first hit
1422 // return number of ITP thingys put into frame pool
1423 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1424 var
1437 begin
1442 begin
1444 exit;
1453 // fix coords
1468 // clip rect
1475 // has something to do
1476 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1477 //mInQuery := true;
1479 // increase query counter
1482 begin
1483 // just in case of overflow
1487 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1490 // go on
1492 begin
1494 begin
1495 // process cells
1498 begin
1501 begin
1504 // shit! has to do it this way, so i can change tag in callback
1516 (*
1517 if assigned(cb) then
1518 begin
1519 if cb(px.mObj, ptag) then begin result := px.mObj; mInQuery := false; exit; end;
1520 end
1521 else
1522 begin
1523 result := px.mObj;
1524 mInQuery := false;
1525 exit;
1526 end;
1527 *)
1534 //mInQuery := false;
1538 // ////////////////////////////////////////////////////////////////////////// //
1539 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1540 var
1551 //px0, py0, px1, py1: Integer;
1552 begin
1563 // make query coords (0,0)-based
1572 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1573 //mInQuery := true;
1575 // increase query counter
1578 begin
1579 // just in case of overflow
1585 repeat
1587 // check tile
1589 // process cells
1591 begin
1594 begin
1599 begin
1602 begin
1604 //mInQuery := false;
1605 exit;
1609 // next cell
1612 // done processing cells, move to next tile
1615 //mInQuery := false;
1619 // ////////////////////////////////////////////////////////////////////////// //
1620 // trace box with the given velocity; return object hit (if any)
1621 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1622 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; tagmask: Integer=-1): ITP;
1623 var
1634 begin
1648 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1654 // just in case
1657 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1658 //mInQuery := true;
1660 // increase query counter
1663 begin
1664 // just in case of overflow
1671 begin
1673 begin
1676 begin
1679 begin
1684 begin
1686 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1688 begin
1693 begin
1696 //mInQuery := false;
1697 exit;
1702 // next cell
1709 begin
1712 // just in case, compensate for floating point inexactness
1713 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1714 begin
1720 //mInQuery := false;
1724 // ////////////////////////////////////////////////////////////////////////// //
1725 {.$DEFINE D2F_DEBUG_OTR}
1726 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1727 var
1738 {$IF DEFINED(D2F_DEBUG_OTR)}
1740 {$ENDIF}
1742 begin
1758 // offset query coords to (0,0)-based
1765 begin
1767 // vertical
1769 begin
1770 // down
1772 //if (ay0 < 0) then ay0 := 0;
1776 end
1777 else
1778 begin
1779 // up
1781 //if (ay1 < 0) then ay1 := 0;
1786 // check tile
1788 begin
1794 begin
1797 begin
1803 begin
1804 // bound c0 and c1 to cell
1807 // fill the thing
1808 {$IF DEFINED(D2F_DEBUG_OTR)}
1809 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)]);
1810 {$ENDIF}
1811 //assert(c0 <= c1);
1815 // next cell
1818 {$IF DEFINED(D2F_DEBUG_OTR)}
1819 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1823 {$ENDIF}
1824 // now go till we hit cell boundary or empty space
1826 begin
1827 // up
1829 begin
1830 {$IF DEFINED(D2F_DEBUG_OTR)}
1831 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1832 {$ENDIF}
1836 {$IF DEFINED(D2F_DEBUG_OTR)}
1837 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1838 {$ENDIF}
1840 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1841 end
1842 else
1843 begin
1844 // down
1850 end
1851 else
1852 begin
1853 // horizontal
1859 // ////////////////////////////////////////////////////////////////////////// //
1861 var
1863 begin
1868 // no callback: return `true` on the nearest hit
1869 // you are not supposed to understand this
1870 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
1871 var
1886 begin
1896 // make query coords (0,0)-based
1907 {$IF DEFINED(D2F_DEBUG)}
1908 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1909 {$ENDIF}
1911 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1912 //mInQuery := true;
1914 // increase query counter
1917 begin
1918 // just in case of overflow
1924 repeat
1926 {$IF DEFINED(D2F_DEBUG)}
1928 {$ENDIF}
1929 // check tile
1931 // process cells
1934 begin
1937 begin
1942 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
1959 //mInQuery := false;
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
1994 //mInQuery := false;
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 *)