41f03adea7bcf5fbd0bd7f3f6b402e840c4b955d
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
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;
207 //WARNING: don't modify grid while any query is in progress (no checks are made!)
208 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
209 // cb with `(nil)` will be called before processing new tile
210 // no callback: return object of the nearest hit or nil
211 // if `inverted` is true, trace will register bodies *exluding* tagmask
212 //WARNING: don't change tags in callbacks here!
213 {
214 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
215 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
216 }
218 //WARNING: don't modify grid while any query is in progress (no checks are made!)
219 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
220 // cb with `(nil)` will be called before processing new tile
221 // no callback: return object of the nearest hit or nil
222 // if `inverted` is true, trace will register bodies *exluding* tagmask
223 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
224 //WARNING: don't change tags in callbacks here!
225 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
226 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
228 // return `false` if we're still inside at the end
229 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
230 // `true`: endpoint will point at the last "inside" pixel
231 // `false`: endpoint will be (ax1, ay1)
232 //WARNING: don't change tags in callbacks here!
233 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
235 //WARNING: don't modify grid while any query is in progress (no checks are made!)
236 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
237 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
238 //WARNING: don't change tags in callbacks here!
239 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
241 // trace box with the given velocity; return object hit (if any)
242 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
243 //WARNING: don't change tags in callbacks here!
244 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
246 // debug
251 public
252 //WARNING! no sanity checks!
264 type
265 // common structure for all line tracers
267 public
270 private
278 public
279 // call `setyp` after this
284 // this will use `w[xy][01]` to clip coords
285 // return `false` if the whole line was clipped away
286 // on `true`, you should process first point, and go on
289 // call this *after* doing a step
290 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
293 // as you will prolly call `done()` after doing a step anyway, this will do it for you
294 // move to next point, return `true` when the line is complete (i.e. you should stop)
297 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
302 public
303 // current coords
310 //function minInt (a, b: Integer): Integer; inline;
311 //function maxInt (a, b: Integer): Integer; inline;
314 implementation
316 uses
320 // ////////////////////////////////////////////////////////////////////////// //
321 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
322 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
323 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
324 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
327 // ////////////////////////////////////////////////////////////////////////// //
329 begin
334 begin
335 // clip rectange
343 var
345 begin
346 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
350 begin
352 end
353 else
354 begin
363 // check for ortho lines
365 begin
366 // horizontal
373 end
375 begin
376 // vertical
383 end
384 else
385 begin
386 // diagonal
388 begin
389 // horizontal
393 end
394 else
395 begin
396 // vertical
412 // true: done
414 begin
416 begin
420 end
421 else
422 begin
431 // true: done
433 var
437 begin
442 // strictly horizontal?
444 begin
445 // only xd
447 begin
448 // xd: to left edge
451 end
452 else
453 begin
454 // xd: to right edge
460 exit;
463 // strictly vertical?
465 begin
466 // only xd
468 begin
469 // yd: to top edge
472 end
473 else
474 begin
475 // yd: to bottom edge
481 exit;
484 // diagonal
486 // calculate xwalk
488 begin
491 end
492 else
493 begin
498 // calculate ywalk
500 begin
503 end
504 else
505 begin
510 {
511 while (xd <> ex) and (yd <> ey) do
512 begin
513 if horiz then
514 begin
515 xd += stx;
516 err += errinc;
517 if (err >= 0) then begin err -= errmax; yd += sty; end;
518 end
519 else
520 begin
521 yd += sty;
522 err += errinc;
523 if (err >= 0) then begin err -= errmax; xd += stx; end;
524 end;
525 Dec(stleft);
526 if (stleft < 1) then begin result := true; exit; end;
527 end;
528 }
532 begin
533 // in which dir we want to walk?
537 begin
540 begin
544 end
545 else
546 begin
549 begin
554 // check for walk completion
563 // ////////////////////////////////////////////////////////////////////////// //
564 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
565 begin
578 begin
583 begin
588 begin
593 begin
598 begin
603 begin
608 // ////////////////////////////////////////////////////////////////////////// //
609 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
610 begin
619 begin
621 begin
623 begin
627 exit;
637 begin
642 // ////////////////////////////////////////////////////////////////////////// //
643 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
644 var
646 begin
648 {$IF DEFINED(D2F_DEBUG)}
650 {$ENDIF}
651 {
652 if aTileSize < 1 then aTileSize := 1;
653 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
654 mTileSize := aTileSize;
655 }
666 // init free list
668 begin
674 // init grid
676 // init proxies
684 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
689 begin
697 // ////////////////////////////////////////////////////////////////////////// //
699 var
701 begin
704 begin
708 begin
714 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);
719 var
722 begin
725 begin
728 begin
731 begin
733 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
735 // next cell
743 var
746 begin
754 begin
757 begin
759 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
761 // next cell
767 // ////////////////////////////////////////////////////////////////////////// //
768 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
769 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
773 begin
774 // fix coords
782 begin
784 begin
787 end
788 else
789 begin
798 begin
800 begin
803 end
804 else
805 begin
813 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
814 begin
816 begin
819 end
820 else
821 begin
832 // ////////////////////////////////////////////////////////////////////////// //
834 begin
835 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
840 begin
842 begin
844 begin
846 end
847 else
848 begin
856 begin
861 // ////////////////////////////////////////////////////////////////////////// //
863 var
866 begin
868 begin
869 // no free cells, want more
873 begin
885 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
890 begin
892 begin
894 begin
905 // ////////////////////////////////////////////////////////////////////////// //
906 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
907 var
910 begin
912 begin
913 // no free proxies, resize list
920 // get one from list
925 // add to used list
927 // statistics
933 begin
935 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
936 // add to free list
944 // ////////////////////////////////////////////////////////////////////////// //
945 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
946 var
950 begin
953 // fix coords
956 // go on
965 // clip rect
971 // do the work
973 begin
975 begin
983 // ////////////////////////////////////////////////////////////////////////// //
985 var
990 begin
992 // add body to the given grid cell
995 begin
996 {$IF DEFINED(D2F_DEBUG)}
999 begin
1002 begin
1004 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1008 {$ENDIF}
1011 begin
1013 // check "has room" flag
1015 begin
1016 // can add here
1018 begin
1020 begin
1023 exit;
1028 // no room, go to next cell in list (if there is any)
1031 // no room in cells, add new cell to list
1033 // either no room, or no cell at all
1043 // assume that we cannot have one object added to bucket twice
1045 var
1049 begin
1051 // find and remove cell
1055 begin
1058 begin
1060 begin
1061 // i found her!
1063 begin
1064 // this cell contains no elements, remove it
1067 exit;
1069 // remove element from bucket
1071 begin
1076 exit;
1085 // ////////////////////////////////////////////////////////////////////////// //
1086 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1087 begin
1090 //insertInternal(result);
1096 var
1098 begin
1101 //removeInternal(body);
1107 // ////////////////////////////////////////////////////////////////////////// //
1109 var
1112 begin
1119 {$IF DEFINED(D2F_DEBUG_MOVER)}
1120 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);
1121 {$ENDIF}
1123 // map -> grid
1128 // did any corner crossed tile boundary?
1133 begin
1134 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1135 //removeInternal(body);
1141 //insertInternal(body);
1143 end
1144 else
1145 begin
1154 //TODO: optimize for horizontal/vertical moves
1156 var
1164 begin
1166 // check if tile coords was changed
1171 // map -> grid
1176 // check for heavy work
1187 {$IF DEFINED(D2F_DEBUG_MOVER)}
1188 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);
1189 {$ENDIF}
1191 begin
1192 // crossed tile boundary, do heavy work
1195 // cycle with old rect, remove body where it is necessary
1196 // optimized for horizontal moves
1197 {$IF DEFINED(D2F_DEBUG_MOVER)}
1198 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);
1199 {$ENDIF}
1200 // remove stale marks
1203 begin
1208 {$IF DEFINED(D2F_DEBUG_MOVER)}
1210 {$ENDIF}
1212 begin
1214 begin
1215 // this column is completely outside of new rect
1217 begin
1218 {$IF DEFINED(D2F_DEBUG_MOVER)}
1220 {$ENDIF}
1223 end
1224 else
1225 begin
1226 // heavy checks
1228 begin
1230 begin
1231 {$IF DEFINED(D2F_DEBUG_MOVER)}
1233 {$ENDIF}
1240 // cycle with new rect, add body where it is necessary
1243 begin
1248 {$IF DEFINED(D2F_DEBUG_MOVER)}
1250 {$ENDIF}
1252 begin
1254 begin
1255 // this column is completely outside of old rect
1257 begin
1258 {$IF DEFINED(D2F_DEBUG_MOVER)}
1260 {$ENDIF}
1263 end
1264 else
1265 begin
1266 // heavy checks
1268 begin
1270 begin
1271 {$IF DEFINED(D2F_DEBUG_MOVER)}
1273 {$ENDIF}
1280 // done
1281 end
1282 else
1283 begin
1284 {$IF DEFINED(D2F_DEBUG_MOVER)}
1285 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);
1286 {$ENDIF}
1288 // update coordinates
1295 var
1298 begin
1300 // check if tile coords was changed
1306 {$IF DEFINED(D2F_DEBUG_MOVER)}
1307 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);
1308 {$ENDIF}
1311 begin
1312 // crossed tile boundary, do heavy work
1313 //removeInternal(body);
1317 //insertInternal(body);
1319 end
1320 else
1321 begin
1322 // nothing to do with the grid, just fix size
1329 // ////////////////////////////////////////////////////////////////////////// //
1331 var
1333 begin
1336 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1341 // ////////////////////////////////////////////////////////////////////////// //
1342 // no callback: return `true` on the first hit
1343 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1344 var
1351 begin
1357 {$IF DEFINED(D2F_DEBUG_XXQ)}
1359 {$ENDIF}
1361 // make coords (0,0)-based
1368 {$IF DEFINED(D2F_DEBUG_XXQ)}
1369 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);
1370 {$ENDIF}
1372 // restore coords
1376 // increase query counter
1379 begin
1380 // just in case of overflow
1386 {$IF DEFINED(D2F_DEBUG_XXQ)}
1387 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1388 {$ENDIF}
1391 begin
1392 {$IF DEFINED(D2F_DEBUG_XXQ)}
1394 {$ENDIF}
1397 begin
1400 {$IF DEFINED(D2F_DEBUG_XXQ)}
1401 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);
1402 {$ENDIF}
1403 // shit. has to do it this way, so i can change tag in callback
1405 begin
1410 begin
1412 begin
1414 begin
1417 exit;
1419 end
1420 else
1421 begin
1424 exit;
1434 // ////////////////////////////////////////////////////////////////////////// //
1435 // no callback: return `true` on the first hit
1436 // return number of ITP thingys put into frame pool
1437 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1438 var
1451 begin
1460 // fix coords
1475 // clip rect
1482 // has something to do
1486 // increase query counter
1489 begin
1490 // just in case of overflow
1494 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1497 // go on
1499 begin
1501 begin
1502 // process cells
1505 begin
1508 begin
1511 // shit! has to do it this way, so i can change tag in callback
1523 (*
1524 if assigned(cb) then
1525 begin
1526 if cb(px.mObj, ptag) then begin result := px.mObj; mInQuery := false; exit; end;
1527 end
1528 else
1529 begin
1530 result := px.mObj;
1531 mInQuery := false;
1532 exit;
1533 end;
1534 *)
1545 // ////////////////////////////////////////////////////////////////////////// //
1546 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1547 var
1558 //px0, py0, px1, py1: Integer;
1559 begin
1570 // make query coords (0,0)-based
1582 // increase query counter
1585 begin
1586 // just in case of overflow
1592 repeat
1594 // check tile
1596 // process cells
1598 begin
1601 begin
1606 begin
1609 begin
1612 exit;
1616 // next cell
1619 // done processing cells, move to next tile
1626 // ////////////////////////////////////////////////////////////////////////// //
1627 // trace box with the given velocity; return object hit (if any)
1628 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1629 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1630 var
1641 begin
1655 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1661 // just in case
1667 // increase query counter
1670 begin
1671 // just in case of overflow
1678 begin
1680 begin
1683 begin
1686 begin
1691 begin
1694 begin
1697 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1699 begin
1704 begin
1708 exit;
1713 // next cell
1720 begin
1723 // just in case, compensate for floating point inexactness
1724 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1725 begin
1735 // ////////////////////////////////////////////////////////////////////////// //
1736 {.$DEFINE D2F_DEBUG_OTR}
1737 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1738 var
1749 {$IF DEFINED(D2F_DEBUG_OTR)}
1751 {$ENDIF}
1752 begin
1766 // offset query coords to (0,0)-based
1773 begin
1775 // vertical
1777 begin
1778 // down
1780 //if (ay0 < 0) then ay0 := 0;
1784 end
1785 else
1786 begin
1787 // up
1789 //if (ay1 < 0) then ay1 := 0;
1794 // check tile
1796 begin
1802 begin
1805 begin
1811 begin
1812 // bound c0 and c1 to cell
1815 // fill the thing
1816 {$IF DEFINED(D2F_DEBUG_OTR)}
1817 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)]);
1818 {$ENDIF}
1819 //assert(c0 <= c1);
1823 // next cell
1826 {$IF DEFINED(D2F_DEBUG_OTR)}
1827 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1831 {$ENDIF}
1832 // now go till we hit cell boundary or empty space
1834 begin
1835 // up
1837 begin
1838 {$IF DEFINED(D2F_DEBUG_OTR)}
1839 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1840 {$ENDIF}
1844 {$IF DEFINED(D2F_DEBUG_OTR)}
1845 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1846 {$ENDIF}
1848 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1849 end
1850 else
1851 begin
1852 // down
1858 end
1859 else
1860 begin
1861 // horizontal
1867 // ////////////////////////////////////////////////////////////////////////// //
1868 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1869 var
1871 begin
1876 // no callback: return `true` on the nearest hit
1877 // you are not supposed to understand this
1878 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1879 var
1894 begin
1904 // make query coords (0,0)-based
1915 {$IF DEFINED(D2F_DEBUG)}
1916 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1917 {$ENDIF}
1922 // increase query counter
1925 begin
1926 // just in case of overflow
1932 repeat
1934 {$IF DEFINED(D2F_DEBUG)}
1936 {$ENDIF}
1937 // check tile
1939 // process cells
1942 begin
1945 begin
1950 begin
1953 begin
1956 // get adjusted proxy coords
1961 {$IF DEFINED(D2F_DEBUG)}
1962 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1963 {$ENDIF}
1964 // inside?
1966 begin
1967 // oops
1972 {$IF DEFINED(D2F_DEBUG)}
1974 {$ENDIF}
1975 exit;
1977 // do line-vs-aabb test
1979 begin
1980 // hit detected
1982 {$IF DEFINED(D2F_DEBUG)}
1983 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1984 {$ENDIF}
1986 begin
1996 // next cell
1999 // done processing cells; exit if we registered a hit
2000 // next cells can't have better candidates, obviously
2003 // move to next tile
2010 // ////////////////////////////////////////////////////////////////////////// //
2011 // no callback: return `true` on the nearest hit
2012 (*
2013 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2014 var
2015 ex, ey: Integer;
2016 begin
2017 result := traceRayOld(ex, ey, x0, y0, x1, y1, cb, tagmask);
2018 end;
2021 // no callback: return `true` on the nearest hit
2022 // you are not supposed to understand this
2023 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2024 var
2025 wx0, wy0, wx1, wy1: Integer; // window coordinates
2026 stx, sty: Integer; // "steps" for x and y axes
2027 dsx, dsy: Integer; // "lengthes" for x and y axes
2028 dx2, dy2: Integer; // "double lengthes" for x and y axes
2029 xd, yd: Integer; // current coord
2030 e: Integer; // "error" (as in bresenham algo)
2031 rem: Integer;
2032 term: Integer;
2033 xptr, yptr: PInteger;
2034 xfixed: Boolean;
2035 temp: Integer;
2036 prevx, prevy: Integer;
2037 lastDistSq: Integer;
2038 ccidx, curci: Integer;
2039 hasUntried: Boolean;
2040 lastGA: Integer = -1;
2041 ga, x, y: Integer;
2042 lastObj: ITP;
2043 wasHit: Boolean = false;
2044 gw, gh, minx, miny, maxx, maxy: Integer;
2045 cc: PGridCell;
2046 px: PBodyProxyRec;
2047 lq: LongWord;
2048 f, ptag, distSq: Integer;
2049 x0, y0, x1, y1: Integer;
2050 //swapped: Boolean = false; // true: xd is yd, and vice versa
2051 // horizontal walker
2052 {$IFDEF GRID_USE_ORTHO_ACCEL}
2053 wklen, wkstep: Integer;
2054 //wksign: Integer;
2055 hopt: Boolean;
2056 {$ENDIF}
2057 // skipper
2058 xdist, ydist: Integer;
2059 begin
2060 result := Default(ITP);
2061 lastObj := Default(ITP);
2062 tagmask := tagmask and TagFullMask;
2063 ex := ax1; // why not?
2064 ey := ay1; // why not?
2065 if (tagmask = 0) then exit;
2067 if (ax0 = ax1) and (ay0 = ay1) then
2068 begin
2069 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2070 if (result <> nil) then
2071 begin
2072 if assigned(cb) and not cb(result, ptag, ax0, ay0, ax0, ay0) then result := Default(ITP);
2073 end;
2074 exit;
2075 end;
2077 lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1;
2079 gw := mWidth;
2080 gh := mHeight;
2081 minx := mMinX;
2082 miny := mMinY;
2083 maxx := gw*mTileSize-1;
2084 maxy := gh*mTileSize-1;
2086 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2087 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);
2088 {$ENDIF}
2090 x0 := ax0;
2091 y0 := ay0;
2092 x1 := ax1;
2093 y1 := ay1;
2095 // offset query coords to (0,0)-based
2096 Dec(x0, minx);
2097 Dec(y0, miny);
2098 Dec(x1, minx);
2099 Dec(y1, miny);
2101 // clip rectange
2102 wx0 := 0;
2103 wy0 := 0;
2104 wx1 := maxx;
2105 wy1 := maxy;
2107 // horizontal setup
2108 if (x0 < x1) then
2109 begin
2110 // from left to right
2111 if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
2112 stx := 1; // going right
2113 end
2114 else
2115 begin
2116 // from right to left
2117 if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
2118 stx := -1; // going left
2119 x0 := -x0;
2120 x1 := -x1;
2121 wx0 := -wx0;
2122 wx1 := -wx1;
2123 swapInt(wx0, wx1);
2124 end;
2126 // vertical setup
2127 if (y0 < y1) then
2128 begin
2129 // from top to bottom
2130 if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
2131 sty := 1; // going down
2132 end
2133 else
2134 begin
2135 // from bottom to top
2136 if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
2137 sty := -1; // going up
2138 y0 := -y0;
2139 y1 := -y1;
2140 wy0 := -wy0;
2141 wy1 := -wy1;
2142 swapInt(wy0, wy1);
2143 end;
2145 dsx := x1-x0;
2146 dsy := y1-y0;
2148 if (dsx < dsy) then
2149 begin
2150 //swapped := true;
2151 xptr := @yd;
2152 yptr := @xd;
2153 swapInt(x0, y0);
2154 swapInt(x1, y1);
2155 swapInt(dsx, dsy);
2156 swapInt(wx0, wy0);
2157 swapInt(wx1, wy1);
2158 swapInt(stx, sty);
2159 end
2160 else
2161 begin
2162 xptr := @xd;
2163 yptr := @yd;
2164 end;
2166 dx2 := 2*dsx;
2167 dy2 := 2*dsy;
2168 xd := x0;
2169 yd := y0;
2170 e := 2*dsy-dsx;
2171 term := x1;
2173 xfixed := false;
2174 if (y0 < wy0) then
2175 begin
2176 // clip at top
2177 temp := dx2*(wy0-y0)-dsx;
2178 xd += temp div dy2;
2179 rem := temp mod dy2;
2180 if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
2181 if (xd+1 >= wx0) then
2182 begin
2183 yd := wy0;
2184 e -= rem+dsx;
2185 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2186 if (xd < wx0) then begin xd += 1; e += dy2; end; //???
2187 xfixed := true;
2188 end;
2189 end;
2191 if (not xfixed) and (x0 < wx0) then
2192 begin
2193 // clip at left
2194 temp := dy2*(wx0-x0);
2195 yd += temp div dx2;
2196 rem := temp mod dx2;
2197 if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
2198 xd := wx0;
2199 e += rem;
2200 if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
2201 end;
2203 if (y1 > wy1) then
2204 begin
2205 // clip at bottom
2206 temp := dx2*(wy1-y0)+dsx;
2207 term := x0+temp div dy2;
2208 rem := temp mod dy2;
2209 if (rem = 0) then Dec(term);
2210 end;
2212 if (term > wx1) then term := wx1; // clip at right
2214 Inc(term); // draw last point
2215 //if (term = xd) then exit; // this is the only point, get out of here
2217 if (sty = -1) then yd := -yd;
2218 if (stx = -1) then begin xd := -xd; term := -term; end;
2219 dx2 -= dy2;
2221 // first move, to skip starting point
2222 // DON'T DO THIS! loop will take care of that
2223 if (xd = term) then
2224 begin
2225 //FIXME!
2226 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2227 if (result <> nil) then
2228 begin
2229 if assigned(cb) then
2230 begin
2231 if cb(result, ptag, ax0, ay0, ax0, ay0) then
2232 begin
2233 ex := ax0;
2234 ey := ay0;
2235 end
2236 else
2237 begin
2238 result := nil;
2239 end;
2240 end
2241 else
2242 begin
2243 ex := ax0;
2244 ey := ay0;
2245 end;
2246 end;
2247 exit;
2248 end;
2250 prevx := xptr^+minx;
2251 prevy := yptr^+miny;
2252 ( *
2253 // move coords
2254 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2255 xd += stx;
2256 // done?
2257 if (xd = term) then exit;
2258 * )
2260 {$IF DEFINED(D2F_DEBUG)}
2261 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2262 {$ENDIF}
2263 // DON'T DO THIS! loop will take care of that
2264 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2265 //ccidx := mGrid[lastGA];
2267 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2268 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2269 {$ENDIF}
2271 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2273 if mInQuery then raise Exception.Create('recursive queries aren''t supported');
2274 mInQuery := true;
2276 // increase query counter
2277 Inc(mLastQuery);
2278 if (mLastQuery = 0) then
2279 begin
2280 // just in case of overflow
2281 mLastQuery := 1;
2282 for f := 0 to High(mProxies) do mProxies[f].mQueryMark := 0;
2283 end;
2284 lq := mLastQuery;
2286 {$IFDEF GRID_USE_ORTHO_ACCEL}
2287 // if this is strict horizontal/vertical trace, use optimized codepath
2288 if (ax0 = ax1) or (ay0 = ay1) then
2289 begin
2290 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2291 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2292 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2293 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2294 hopt := (ay0 = ay1); // horizontal?
2295 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2296 {$IF DEFINED(D2F_DEBUG)}
2297 if dbgShowTraceLog then e_LogWritefln('optimized htrace; wklen=%d', [wklen]);
2298 {$ENDIF}
2299 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2300 // one of those will never change
2301 x := xptr^+minx;
2302 y := yptr^+miny;
2303 while (wklen > 0) do
2304 begin
2305 {$IF DEFINED(D2F_DEBUG)}
2306 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2307 {$ENDIF}
2308 // new tile?
2309 if (ga <> lastGA) then
2310 begin
2311 lastGA := ga;
2312 ccidx := mGrid[lastGA];
2313 // convert coords to map (to avoid ajdusting coords inside the loop)
2314 if hopt then x := xptr^+minx else y := yptr^+miny;
2315 while (ccidx <> -1) do
2316 begin
2317 cc := @mCells[ccidx];
2318 for f := 0 to GridCellBucketSize-1 do
2319 begin
2320 if (cc.bodies[f] = -1) then break;
2321 px := @mProxies[cc.bodies[f]];
2322 ptag := px.mTag;
2323 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and
2324 // constant coord should be inside
2325 ((hopt and (y >= px.y0) and (y <= px.y1)) or
2326 ((not hopt) and (x >= px.x0) and (x <= px.x1))) then
2327 begin
2328 px.mQueryMark := lq; // mark as processed
2329 // inside the proxy?
2330 if (hopt and (x > px.x0) and (x < px.x1)) or
2331 ((not hopt) and (y > px.y0) and (y < px.y1)) then
2332 begin
2333 // setup prev[xy]
2334 if assigned(cb) then
2335 begin
2336 if cb(px.mObj, ptag, x, y, x, y) then
2337 begin
2338 result := px.mObj;
2339 ex := x;
2340 ey := y;
2341 mInQuery := false;
2342 exit;
2343 end;
2344 end
2345 else
2346 begin
2347 distSq := distanceSq(ax0, ay0, x, y);
2348 {$IF DEFINED(D2F_DEBUG)}
2349 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]);
2350 {$ENDIF}
2351 if (distSq < lastDistSq) then
2352 begin
2353 ex := x;
2354 ey := y;
2355 result := px.mObj;
2356 mInQuery := false;
2357 exit;
2358 end;
2359 end;
2360 continue;
2361 end;
2362 // remember this hitpoint if it is nearer than an old one
2363 // setup prev[xy]
2364 if hopt then
2365 begin
2366 // horizontal trace
2367 prevy := y;
2368 y := yptr^+miny;
2369 if (stx < 0) then
2370 begin
2371 // going left
2372 if (x < px.x1) then continue; // not on the right edge
2373 x := px.x1;
2374 prevx := x+1;
2375 end
2376 else
2377 begin
2378 // going right
2379 if (x > px.x0) then continue; // not on the left edge
2380 x := px.x0;
2381 prevx := x-1;
2382 end;
2383 end
2384 else
2385 begin
2386 // vertical trace
2387 prevx := x;
2388 x := xptr^+minx;
2389 if (stx < 0) then
2390 begin
2391 // going up
2392 if (y < px.y1) then continue; // not on the bottom edge
2393 y := px.y1;
2394 prevy := x+1;
2395 end
2396 else
2397 begin
2398 // going down
2399 if (y > px.y0) then continue; // not on the top edge
2400 y := px.y0;
2401 prevy := y-1;
2402 end;
2403 end;
2404 if assigned(cb) then
2405 begin
2406 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2407 begin
2408 result := px.mObj;
2409 ex := prevx;
2410 ey := prevy;
2411 mInQuery := false;
2412 exit;
2413 end;
2414 end
2415 else
2416 begin
2417 distSq := distanceSq(ax0, ay0, prevx, prevy);
2418 {$IF DEFINED(D2F_DEBUG)}
2419 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]);
2420 {$ENDIF}
2421 if (distSq < lastDistSq) then
2422 begin
2423 wasHit := true;
2424 lastDistSq := distSq;
2425 ex := prevx;
2426 ey := prevy;
2427 lastObj := px.mObj;
2428 end;
2429 end;
2430 end;
2431 end;
2432 // next cell
2433 ccidx := cc.next;
2434 end;
2435 if wasHit and not assigned(cb) then begin result := lastObj; mInQuery := false; exit; end;
2436 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2437 end;
2438 // skip to next tile
2439 if hopt then
2440 begin
2441 if (stx > 0) then
2442 begin
2443 // to the right
2444 wkstep := ((xptr^ or (mTileSize-1))+1)-xptr^;
2445 {$IF DEFINED(D2F_DEBUG)}
2446 if dbgShowTraceLog then e_LogWritefln(' right step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2447 {$ENDIF}
2448 if (wkstep >= wklen) then break;
2449 Inc(xptr^, wkstep);
2450 Inc(ga);
2451 end
2452 else
2453 begin
2454 // to the left
2455 wkstep := xptr^-((xptr^ and (not (mTileSize-1)))-1);
2456 {$IF DEFINED(D2F_DEBUG)}
2457 if dbgShowTraceLog then e_LogWritefln(' left step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2458 {$ENDIF}
2459 if (wkstep >= wklen) then break;
2460 Dec(xptr^, wkstep);
2461 Dec(ga);
2462 end;
2463 end
2464 else
2465 begin
2466 if (stx > 0) then
2467 begin
2468 // to the down
2469 wkstep := ((yptr^ or (mTileSize-1))+1)-yptr^;
2470 {$IF DEFINED(D2F_DEBUG)}
2471 if dbgShowTraceLog then e_LogWritefln(' down step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2472 {$ENDIF}
2473 if (wkstep >= wklen) then break;
2474 Inc(yptr^, wkstep);
2475 Inc(ga, mWidth);
2476 end
2477 else
2478 begin
2479 // to the up
2480 wkstep := yptr^-((yptr^ and (not (mTileSize-1)))-1);
2481 {$IF DEFINED(D2F_DEBUG)}
2482 if dbgShowTraceLog then e_LogWritefln(' up step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2483 {$ENDIF}
2484 if (wkstep >= wklen) then break;
2485 Dec(yptr^, wkstep);
2486 Dec(ga, mWidth);
2487 end;
2488 end;
2489 Dec(wklen, wkstep);
2490 end;
2491 // we can travel less than one cell
2492 if wasHit and not assigned(cb) then result := lastObj else begin ex := ax1; ey := ay1; end;
2493 mInQuery := false;
2494 exit;
2495 end;
2496 {$ENDIF}
2498 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2499 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2500 {$ENDIF}
2502 //e_LogWritefln('*********************', []);
2503 ccidx := -1;
2504 // can omit checks
2505 while (xd <> term) do
2506 begin
2507 // check cell(s)
2508 {$IF DEFINED(D2F_DEBUG)}
2509 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2510 {$ENDIF}
2511 // new tile?
2512 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2513 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2514 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);
2515 {$ENDIF}
2516 if (ga <> lastGA) then
2517 begin
2518 // yes
2519 {$IF DEFINED(D2F_DEBUG)}
2520 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2521 {$ENDIF}
2522 if (ccidx <> -1) then
2523 begin
2524 // signal cell completion
2525 if assigned(cb) then
2526 begin
2527 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2528 end
2529 else if wasHit then
2530 begin
2531 result := lastObj;
2532 mInQuery := false;
2533 exit;
2534 end;
2535 end;
2536 lastGA := ga;
2537 ccidx := mGrid[lastGA];
2538 end;
2539 // has something to process in this tile?
2540 if (ccidx <> -1) then
2541 begin
2542 // process cell
2543 curci := ccidx;
2544 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2545 // convert coords to map (to avoid ajdusting coords inside the loop)
2546 x := xptr^+minx;
2547 y := yptr^+miny;
2548 // process cell list
2549 while (curci <> -1) do
2550 begin
2551 cc := @mCells[curci];
2552 for f := 0 to GridCellBucketSize-1 do
2553 begin
2554 if (cc.bodies[f] = -1) then break;
2555 px := @mProxies[cc.bodies[f]];
2556 ptag := px.mTag;
2557 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
2558 begin
2559 // can we process this proxy?
2560 if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
2561 begin
2562 px.mQueryMark := lq; // mark as processed
2563 if assigned(cb) then
2564 begin
2565 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2566 begin
2567 result := px.mObj;
2568 ex := prevx;
2569 ey := prevy;
2570 mInQuery := false;
2571 exit;
2572 end;
2573 end
2574 else
2575 begin
2576 // remember this hitpoint if it is nearer than an old one
2577 distSq := distanceSq(ax0, ay0, prevx, prevy);
2578 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2579 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);
2580 {$ENDIF}
2581 if (distSq < lastDistSq) then
2582 begin
2583 wasHit := true;
2584 lastDistSq := distSq;
2585 ex := prevx;
2586 ey := prevy;
2587 lastObj := px.mObj;
2588 end;
2589 end;
2590 end
2591 else
2592 begin
2593 // this is possibly interesting proxy, set "has more to check" flag
2594 hasUntried := true;
2595 end;
2596 end;
2597 end;
2598 // next cell
2599 curci := cc.next;
2600 end;
2601 // still has something interesting in this cell?
2602 if not hasUntried then
2603 begin
2604 // nope, don't process this cell anymore; signal cell completion
2605 ccidx := -1;
2606 if assigned(cb) then
2607 begin
2608 if cb(nil, 0, x, y, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2609 end
2610 else if wasHit then
2611 begin
2612 result := lastObj;
2613 mInQuery := false;
2614 exit;
2615 end;
2616 end;
2617 end;
2618 if (ccidx = -1) then
2619 begin
2620 // move to cell edge, as we have nothing to trace here anymore
2621 if (stx < 0) then xdist := xd and (not (mTileSize-1)) else xdist := xd or (mTileSize-1);
2622 if (sty < 0) then ydist := yd and (not (mTileSize-1)) else ydist := yd or (mTileSize-1);
2623 //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]);
2624 while (xd <> xdist) and (yd <> ydist) do
2625 begin
2626 // step
2627 xd += stx;
2628 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2629 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2630 if (xd = term) then break;
2631 end;
2632 //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]);
2633 if (xd = term) then break;
2634 end;
2635 //putPixel(xptr^, yptr^);
2636 // move coords
2637 prevx := xptr^+minx;
2638 prevy := yptr^+miny;
2639 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2640 xd += stx;
2641 end;
2642 // we can travel less than one cell
2643 if wasHit and not assigned(cb) then
2644 begin
2645 result := lastObj;
2646 end
2647 else
2648 begin
2649 ex := ax1; // why not?
2650 ey := ay1; // why not?
2651 end;
2653 mInQuery := false;
2654 end;
2655 *)