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 // cb with `(nil)` will be called before processing new tile
222 // no callback: return object of the nearest hit or nil
223 // if `inverted` is true, trace will register bodies *exluding* tagmask
224 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
225 //WARNING: don't change tags in callbacks here!
226 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
227 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
229 // return `false` if we're still inside at the end
230 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
231 // `true`: endpoint will point at the last "inside" pixel
232 // `false`: endpoint will be (ax1, ay1)
233 //WARNING: don't change tags in callbacks here!
234 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
236 //WARNING: don't modify grid while any query is in progress (no checks are made!)
237 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
238 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
239 //WARNING: don't change tags in callbacks here!
240 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
242 // trace box with the given velocity; return object hit (if any)
243 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
244 //WARNING: don't change tags in callbacks here!
245 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
247 // debug
252 public
253 //WARNING! no sanity checks!
265 type
266 // common structure for all line tracers
268 public
271 private
279 public
280 // call `setyp` after this
285 // this will use `w[xy][01]` to clip coords
286 // return `false` if the whole line was clipped away
287 // on `true`, you should process first point, and go on
290 // call this *after* doing a step
291 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
294 // as you will prolly call `done()` after doing a step anyway, this will do it for you
295 // move to next point, return `true` when the line is complete (i.e. you should stop)
298 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
303 public
304 // current coords
311 //function minInt (a, b: Integer): Integer; inline;
312 //function maxInt (a, b: Integer): Integer; inline;
315 implementation
317 uses
321 // ////////////////////////////////////////////////////////////////////////// //
322 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
323 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
324 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
325 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
328 // ////////////////////////////////////////////////////////////////////////// //
330 begin
335 begin
336 // clip rectange
344 var
346 begin
347 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
351 begin
353 end
354 else
355 begin
364 // check for ortho lines
366 begin
367 // horizontal
374 end
376 begin
377 // vertical
384 end
385 else
386 begin
387 // diagonal
389 begin
390 // horizontal
394 end
395 else
396 begin
397 // vertical
413 // true: done
415 begin
417 begin
421 end
422 else
423 begin
432 // true: done
434 var
438 begin
443 // strictly horizontal?
445 begin
446 // only xd
448 begin
449 // xd: to left edge
452 end
453 else
454 begin
455 // xd: to right edge
461 exit;
464 // strictly vertical?
466 begin
467 // only xd
469 begin
470 // yd: to top edge
473 end
474 else
475 begin
476 // yd: to bottom edge
482 exit;
485 // diagonal
487 // calculate xwalk
489 begin
492 end
493 else
494 begin
499 // calculate ywalk
501 begin
504 end
505 else
506 begin
511 {
512 while (xd <> ex) and (yd <> ey) do
513 begin
514 if horiz then
515 begin
516 xd += stx;
517 err += errinc;
518 if (err >= 0) then begin err -= errmax; yd += sty; end;
519 end
520 else
521 begin
522 yd += sty;
523 err += errinc;
524 if (err >= 0) then begin err -= errmax; xd += stx; end;
525 end;
526 Dec(stleft);
527 if (stleft < 1) then begin result := true; exit; end;
528 end;
529 }
533 begin
534 // in which dir we want to walk?
538 begin
541 begin
545 end
546 else
547 begin
550 begin
555 // check for walk completion
564 // ////////////////////////////////////////////////////////////////////////// //
565 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
566 begin
579 begin
584 begin
589 begin
594 begin
599 begin
604 begin
609 // ////////////////////////////////////////////////////////////////////////// //
610 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
611 begin
620 begin
622 begin
624 begin
628 exit;
638 begin
643 // ////////////////////////////////////////////////////////////////////////// //
644 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
645 var
647 begin
649 {$IF DEFINED(D2F_DEBUG)}
651 {$ENDIF}
652 {
653 if aTileSize < 1 then aTileSize := 1;
654 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
655 mTileSize := aTileSize;
656 }
667 // init free list
669 begin
675 // init grid
677 // init proxies
685 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
690 begin
698 // ////////////////////////////////////////////////////////////////////////// //
700 var
702 begin
705 begin
709 begin
715 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);
720 var
723 begin
726 begin
729 begin
732 begin
734 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
736 // next cell
744 var
747 begin
755 begin
758 begin
760 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
762 // next cell
768 // ////////////////////////////////////////////////////////////////////////// //
769 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
770 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
774 begin
775 // fix coords
783 begin
785 begin
788 end
789 else
790 begin
799 begin
801 begin
804 end
805 else
806 begin
814 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
815 begin
817 begin
820 end
821 else
822 begin
833 // ////////////////////////////////////////////////////////////////////////// //
835 begin
836 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
841 begin
843 begin
845 begin
847 end
848 else
849 begin
857 begin
862 // ////////////////////////////////////////////////////////////////////////// //
864 var
867 begin
869 begin
870 // no free cells, want more
874 begin
886 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
891 begin
893 begin
895 begin
906 // ////////////////////////////////////////////////////////////////////////// //
907 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
908 var
911 begin
913 begin
914 // no free proxies, resize list
921 // get one from list
926 // add to used list
928 // statistics
934 begin
936 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
937 // add to free list
945 // ////////////////////////////////////////////////////////////////////////// //
946 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
947 var
951 begin
954 // fix coords
957 // go on
966 // clip rect
972 // do the work
974 begin
976 begin
984 // ////////////////////////////////////////////////////////////////////////// //
986 var
991 begin
993 // add body to the given grid cell
996 begin
997 {$IF DEFINED(D2F_DEBUG)}
1000 begin
1003 begin
1005 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1009 {$ENDIF}
1012 begin
1014 // check "has room" flag
1016 begin
1017 // can add here
1019 begin
1021 begin
1024 exit;
1029 // no room, go to next cell in list (if there is any)
1032 // no room in cells, add new cell to list
1034 // either no room, or no cell at all
1044 // assume that we cannot have one object added to bucket twice
1046 var
1050 begin
1052 // find and remove cell
1056 begin
1059 begin
1061 begin
1062 // i found her!
1064 begin
1065 // this cell contains no elements, remove it
1068 exit;
1070 // remove element from bucket
1072 begin
1077 exit;
1086 // ////////////////////////////////////////////////////////////////////////// //
1087 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1088 begin
1091 //insertInternal(result);
1097 var
1099 begin
1102 //removeInternal(body);
1108 // ////////////////////////////////////////////////////////////////////////// //
1110 var
1113 begin
1120 {$IF DEFINED(D2F_DEBUG_MOVER)}
1121 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);
1122 {$ENDIF}
1124 // map -> grid
1129 // did any corner crossed tile boundary?
1134 begin
1135 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1136 //removeInternal(body);
1142 //insertInternal(body);
1144 end
1145 else
1146 begin
1155 //TODO: optimize for horizontal/vertical moves
1157 var
1165 begin
1167 // check if tile coords was changed
1172 // map -> grid
1177 // check for heavy work
1188 {$IF DEFINED(D2F_DEBUG_MOVER)}
1189 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);
1190 {$ENDIF}
1192 begin
1193 // crossed tile boundary, do heavy work
1196 // cycle with old rect, remove body where it is necessary
1197 // optimized for horizontal moves
1198 {$IF DEFINED(D2F_DEBUG_MOVER)}
1199 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);
1200 {$ENDIF}
1201 // remove stale marks
1204 begin
1209 {$IF DEFINED(D2F_DEBUG_MOVER)}
1211 {$ENDIF}
1213 begin
1215 begin
1216 // this column is completely outside of new rect
1218 begin
1219 {$IF DEFINED(D2F_DEBUG_MOVER)}
1221 {$ENDIF}
1224 end
1225 else
1226 begin
1227 // heavy checks
1229 begin
1231 begin
1232 {$IF DEFINED(D2F_DEBUG_MOVER)}
1234 {$ENDIF}
1241 // cycle with new rect, add body where it is necessary
1244 begin
1249 {$IF DEFINED(D2F_DEBUG_MOVER)}
1251 {$ENDIF}
1253 begin
1255 begin
1256 // this column is completely outside of old rect
1258 begin
1259 {$IF DEFINED(D2F_DEBUG_MOVER)}
1261 {$ENDIF}
1264 end
1265 else
1266 begin
1267 // heavy checks
1269 begin
1271 begin
1272 {$IF DEFINED(D2F_DEBUG_MOVER)}
1274 {$ENDIF}
1281 // done
1282 end
1283 else
1284 begin
1285 {$IF DEFINED(D2F_DEBUG_MOVER)}
1286 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);
1287 {$ENDIF}
1289 // update coordinates
1296 var
1299 begin
1301 // check if tile coords was changed
1307 {$IF DEFINED(D2F_DEBUG_MOVER)}
1308 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);
1309 {$ENDIF}
1312 begin
1313 // crossed tile boundary, do heavy work
1314 //removeInternal(body);
1318 //insertInternal(body);
1320 end
1321 else
1322 begin
1323 // nothing to do with the grid, just fix size
1330 // ////////////////////////////////////////////////////////////////////////// //
1332 var
1334 begin
1337 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1342 // ////////////////////////////////////////////////////////////////////////// //
1343 // no callback: return `true` on the first hit
1344 function TBodyGridBase.forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1345 var
1353 begin
1358 {$IF DEFINED(D2F_DEBUG_XXQ)}
1360 {$ENDIF}
1362 // make coords (0,0)-based
1369 {$IF DEFINED(D2F_DEBUG_XXQ)}
1370 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);
1371 {$ENDIF}
1373 // restore coords
1377 // increase query counter
1380 begin
1381 // just in case of overflow
1387 {$IF DEFINED(D2F_DEBUG_XXQ)}
1388 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1389 {$ENDIF}
1392 begin
1393 {$IF DEFINED(D2F_DEBUG_XXQ)}
1394 //if (assigned(cb)) then e_WriteLog(Format(' cell #%d', [curci]), MSG_NOTIFY);
1395 {$ENDIF}
1398 begin
1401 {$IF DEFINED(D2F_DEBUG_XXQ)}
1402 //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);
1403 {$ENDIF}
1410 begin
1422 // ////////////////////////////////////////////////////////////////////////// //
1423 // no callback: return `true` on the first hit
1424 // return number of ITP thingys put into frame pool
1425 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1426 var
1439 begin
1444 begin
1446 exit;
1455 // fix coords
1470 // clip rect
1477 // has something to do
1478 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1479 //mInQuery := true;
1481 // increase query counter
1484 begin
1485 // just in case of overflow
1489 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1492 // go on
1494 begin
1496 begin
1497 // process cells
1500 begin
1503 begin
1506 // shit! has to do it this way, so i can change tag in callback
1518 (*
1519 if assigned(cb) then
1520 begin
1521 if cb(px.mObj, ptag) then begin result := px.mObj; mInQuery := false; exit; end;
1522 end
1523 else
1524 begin
1525 result := px.mObj;
1526 mInQuery := false;
1527 exit;
1528 end;
1529 *)
1536 //mInQuery := false;
1540 // ////////////////////////////////////////////////////////////////////////// //
1541 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1542 var
1553 //px0, py0, px1, py1: Integer;
1554 begin
1565 // make query coords (0,0)-based
1574 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1575 //mInQuery := true;
1577 // increase query counter
1580 begin
1581 // just in case of overflow
1587 repeat
1589 // check tile
1591 // process cells
1593 begin
1596 begin
1601 begin
1604 begin
1606 //mInQuery := false;
1607 exit;
1611 // next cell
1614 // done processing cells, move to next tile
1617 //mInQuery := false;
1621 // ////////////////////////////////////////////////////////////////////////// //
1622 // trace box with the given velocity; return object hit (if any)
1623 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1624 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1625 var
1636 begin
1650 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1656 // just in case
1659 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1660 //mInQuery := true;
1662 // increase query counter
1665 begin
1666 // just in case of overflow
1673 begin
1675 begin
1678 begin
1681 begin
1686 begin
1689 begin
1692 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1694 begin
1699 begin
1702 //mInQuery := false;
1703 exit;
1708 // next cell
1715 begin
1718 // just in case, compensate for floating point inexactness
1719 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1720 begin
1726 //mInQuery := false;
1730 // ////////////////////////////////////////////////////////////////////////// //
1731 {.$DEFINE D2F_DEBUG_OTR}
1732 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1733 var
1744 {$IF DEFINED(D2F_DEBUG_OTR)}
1746 {$ENDIF}
1748 begin
1764 // offset query coords to (0,0)-based
1771 begin
1773 // vertical
1775 begin
1776 // down
1778 //if (ay0 < 0) then ay0 := 0;
1782 end
1783 else
1784 begin
1785 // up
1787 //if (ay1 < 0) then ay1 := 0;
1792 // check tile
1794 begin
1800 begin
1803 begin
1809 begin
1810 // bound c0 and c1 to cell
1813 // fill the thing
1814 {$IF DEFINED(D2F_DEBUG_OTR)}
1815 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)]);
1816 {$ENDIF}
1817 //assert(c0 <= c1);
1821 // next cell
1824 {$IF DEFINED(D2F_DEBUG_OTR)}
1825 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1829 {$ENDIF}
1830 // now go till we hit cell boundary or empty space
1832 begin
1833 // up
1835 begin
1836 {$IF DEFINED(D2F_DEBUG_OTR)}
1837 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1838 {$ENDIF}
1842 {$IF DEFINED(D2F_DEBUG_OTR)}
1843 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1844 {$ENDIF}
1846 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1847 end
1848 else
1849 begin
1850 // down
1856 end
1857 else
1858 begin
1859 // horizontal
1865 // ////////////////////////////////////////////////////////////////////////// //
1866 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1867 var
1869 begin
1874 // no callback: return `true` on the nearest hit
1875 // you are not supposed to understand this
1876 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1877 var
1892 begin
1902 // make query coords (0,0)-based
1913 {$IF DEFINED(D2F_DEBUG)}
1914 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1915 {$ENDIF}
1917 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1918 //mInQuery := true;
1920 // increase query counter
1923 begin
1924 // just in case of overflow
1930 repeat
1932 {$IF DEFINED(D2F_DEBUG)}
1934 {$ENDIF}
1935 // check tile
1937 // process cells
1940 begin
1943 begin
1948 begin
1951 begin
1954 // get adjusted proxy coords
1959 {$IF DEFINED(D2F_DEBUG)}
1960 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1961 {$ENDIF}
1962 // inside?
1964 begin
1965 // oops
1969 //mInQuery := false;
1970 {$IF DEFINED(D2F_DEBUG)}
1972 {$ENDIF}
1973 exit;
1975 // do line-vs-aabb test
1977 begin
1978 // hit detected
1980 {$IF DEFINED(D2F_DEBUG)}
1981 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1982 {$ENDIF}
1984 begin
1994 // next cell
1997 // done processing cells; exit if we registered a hit
1998 // next cells can't have better candidates, obviously
2001 // move to next tile
2004 //mInQuery := false;
2008 // ////////////////////////////////////////////////////////////////////////// //
2009 // no callback: return `true` on the nearest hit
2010 (*
2011 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2012 var
2013 ex, ey: Integer;
2014 begin
2015 result := traceRayOld(ex, ey, x0, y0, x1, y1, cb, tagmask);
2016 end;
2019 // no callback: return `true` on the nearest hit
2020 // you are not supposed to understand this
2021 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2022 var
2023 wx0, wy0, wx1, wy1: Integer; // window coordinates
2024 stx, sty: Integer; // "steps" for x and y axes
2025 dsx, dsy: Integer; // "lengthes" for x and y axes
2026 dx2, dy2: Integer; // "double lengthes" for x and y axes
2027 xd, yd: Integer; // current coord
2028 e: Integer; // "error" (as in bresenham algo)
2029 rem: Integer;
2030 term: Integer;
2031 xptr, yptr: PInteger;
2032 xfixed: Boolean;
2033 temp: Integer;
2034 prevx, prevy: Integer;
2035 lastDistSq: Integer;
2036 ccidx, curci: Integer;
2037 hasUntried: Boolean;
2038 lastGA: Integer = -1;
2039 ga, x, y: Integer;
2040 lastObj: ITP;
2041 wasHit: Boolean = false;
2042 gw, gh, minx, miny, maxx, maxy: Integer;
2043 cc: PGridCell;
2044 px: PBodyProxyRec;
2045 lq: LongWord;
2046 f, ptag, distSq: Integer;
2047 x0, y0, x1, y1: Integer;
2048 //swapped: Boolean = false; // true: xd is yd, and vice versa
2049 // horizontal walker
2050 {$IFDEF GRID_USE_ORTHO_ACCEL}
2051 wklen, wkstep: Integer;
2052 //wksign: Integer;
2053 hopt: Boolean;
2054 {$ENDIF}
2055 // skipper
2056 xdist, ydist: Integer;
2057 begin
2058 result := Default(ITP);
2059 lastObj := Default(ITP);
2060 tagmask := tagmask and TagFullMask;
2061 ex := ax1; // why not?
2062 ey := ay1; // why not?
2063 if (tagmask = 0) then exit;
2065 if (ax0 = ax1) and (ay0 = ay1) then
2066 begin
2067 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2068 if (result <> nil) then
2069 begin
2070 if assigned(cb) and not cb(result, ptag, ax0, ay0, ax0, ay0) then result := Default(ITP);
2071 end;
2072 exit;
2073 end;
2075 lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1;
2077 gw := mWidth;
2078 gh := mHeight;
2079 minx := mMinX;
2080 miny := mMinY;
2081 maxx := gw*mTileSize-1;
2082 maxy := gh*mTileSize-1;
2084 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2085 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);
2086 {$ENDIF}
2088 x0 := ax0;
2089 y0 := ay0;
2090 x1 := ax1;
2091 y1 := ay1;
2093 // offset query coords to (0,0)-based
2094 Dec(x0, minx);
2095 Dec(y0, miny);
2096 Dec(x1, minx);
2097 Dec(y1, miny);
2099 // clip rectange
2100 wx0 := 0;
2101 wy0 := 0;
2102 wx1 := maxx;
2103 wy1 := maxy;
2105 // horizontal setup
2106 if (x0 < x1) then
2107 begin
2108 // from left to right
2109 if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
2110 stx := 1; // going right
2111 end
2112 else
2113 begin
2114 // from right to left
2115 if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
2116 stx := -1; // going left
2117 x0 := -x0;
2118 x1 := -x1;
2119 wx0 := -wx0;
2120 wx1 := -wx1;
2121 swapInt(wx0, wx1);
2122 end;
2124 // vertical setup
2125 if (y0 < y1) then
2126 begin
2127 // from top to bottom
2128 if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
2129 sty := 1; // going down
2130 end
2131 else
2132 begin
2133 // from bottom to top
2134 if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
2135 sty := -1; // going up
2136 y0 := -y0;
2137 y1 := -y1;
2138 wy0 := -wy0;
2139 wy1 := -wy1;
2140 swapInt(wy0, wy1);
2141 end;
2143 dsx := x1-x0;
2144 dsy := y1-y0;
2146 if (dsx < dsy) then
2147 begin
2148 //swapped := true;
2149 xptr := @yd;
2150 yptr := @xd;
2151 swapInt(x0, y0);
2152 swapInt(x1, y1);
2153 swapInt(dsx, dsy);
2154 swapInt(wx0, wy0);
2155 swapInt(wx1, wy1);
2156 swapInt(stx, sty);
2157 end
2158 else
2159 begin
2160 xptr := @xd;
2161 yptr := @yd;
2162 end;
2164 dx2 := 2*dsx;
2165 dy2 := 2*dsy;
2166 xd := x0;
2167 yd := y0;
2168 e := 2*dsy-dsx;
2169 term := x1;
2171 xfixed := false;
2172 if (y0 < wy0) then
2173 begin
2174 // clip at top
2175 temp := dx2*(wy0-y0)-dsx;
2176 xd += temp div dy2;
2177 rem := temp mod dy2;
2178 if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
2179 if (xd+1 >= wx0) then
2180 begin
2181 yd := wy0;
2182 e -= rem+dsx;
2183 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2184 if (xd < wx0) then begin xd += 1; e += dy2; end; //???
2185 xfixed := true;
2186 end;
2187 end;
2189 if (not xfixed) and (x0 < wx0) then
2190 begin
2191 // clip at left
2192 temp := dy2*(wx0-x0);
2193 yd += temp div dx2;
2194 rem := temp mod dx2;
2195 if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
2196 xd := wx0;
2197 e += rem;
2198 if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
2199 end;
2201 if (y1 > wy1) then
2202 begin
2203 // clip at bottom
2204 temp := dx2*(wy1-y0)+dsx;
2205 term := x0+temp div dy2;
2206 rem := temp mod dy2;
2207 if (rem = 0) then Dec(term);
2208 end;
2210 if (term > wx1) then term := wx1; // clip at right
2212 Inc(term); // draw last point
2213 //if (term = xd) then exit; // this is the only point, get out of here
2215 if (sty = -1) then yd := -yd;
2216 if (stx = -1) then begin xd := -xd; term := -term; end;
2217 dx2 -= dy2;
2219 // first move, to skip starting point
2220 // DON'T DO THIS! loop will take care of that
2221 if (xd = term) then
2222 begin
2223 //FIXME!
2224 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2225 if (result <> nil) then
2226 begin
2227 if assigned(cb) then
2228 begin
2229 if cb(result, ptag, ax0, ay0, ax0, ay0) then
2230 begin
2231 ex := ax0;
2232 ey := ay0;
2233 end
2234 else
2235 begin
2236 result := nil;
2237 end;
2238 end
2239 else
2240 begin
2241 ex := ax0;
2242 ey := ay0;
2243 end;
2244 end;
2245 exit;
2246 end;
2248 prevx := xptr^+minx;
2249 prevy := yptr^+miny;
2250 ( *
2251 // move coords
2252 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2253 xd += stx;
2254 // done?
2255 if (xd = term) then exit;
2256 * )
2258 {$IF DEFINED(D2F_DEBUG)}
2259 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2260 {$ENDIF}
2261 // DON'T DO THIS! loop will take care of that
2262 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2263 //ccidx := mGrid[lastGA];
2265 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2266 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2267 {$ENDIF}
2269 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2271 if mInQuery then raise Exception.Create('recursive queries aren''t supported');
2272 mInQuery := true;
2274 // increase query counter
2275 Inc(mLastQuery);
2276 if (mLastQuery = 0) then
2277 begin
2278 // just in case of overflow
2279 mLastQuery := 1;
2280 for f := 0 to High(mProxies) do mProxies[f].mQueryMark := 0;
2281 end;
2282 lq := mLastQuery;
2284 {$IFDEF GRID_USE_ORTHO_ACCEL}
2285 // if this is strict horizontal/vertical trace, use optimized codepath
2286 if (ax0 = ax1) or (ay0 = ay1) then
2287 begin
2288 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2289 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2290 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2291 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2292 hopt := (ay0 = ay1); // horizontal?
2293 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2294 {$IF DEFINED(D2F_DEBUG)}
2295 if dbgShowTraceLog then e_LogWritefln('optimized htrace; wklen=%d', [wklen]);
2296 {$ENDIF}
2297 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2298 // one of those will never change
2299 x := xptr^+minx;
2300 y := yptr^+miny;
2301 while (wklen > 0) do
2302 begin
2303 {$IF DEFINED(D2F_DEBUG)}
2304 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2305 {$ENDIF}
2306 // new tile?
2307 if (ga <> lastGA) then
2308 begin
2309 lastGA := ga;
2310 ccidx := mGrid[lastGA];
2311 // convert coords to map (to avoid ajdusting coords inside the loop)
2312 if hopt then x := xptr^+minx else y := yptr^+miny;
2313 while (ccidx <> -1) do
2314 begin
2315 cc := @mCells[ccidx];
2316 for f := 0 to GridCellBucketSize-1 do
2317 begin
2318 if (cc.bodies[f] = -1) then break;
2319 px := @mProxies[cc.bodies[f]];
2320 ptag := px.mTag;
2321 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and
2322 // constant coord should be inside
2323 ((hopt and (y >= px.y0) and (y <= px.y1)) or
2324 ((not hopt) and (x >= px.x0) and (x <= px.x1))) then
2325 begin
2326 px.mQueryMark := lq; // mark as processed
2327 // inside the proxy?
2328 if (hopt and (x > px.x0) and (x < px.x1)) or
2329 ((not hopt) and (y > px.y0) and (y < px.y1)) then
2330 begin
2331 // setup prev[xy]
2332 if assigned(cb) then
2333 begin
2334 if cb(px.mObj, ptag, x, y, x, y) then
2335 begin
2336 result := px.mObj;
2337 ex := x;
2338 ey := y;
2339 mInQuery := false;
2340 exit;
2341 end;
2342 end
2343 else
2344 begin
2345 distSq := distanceSq(ax0, ay0, x, y);
2346 {$IF DEFINED(D2F_DEBUG)}
2347 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]);
2348 {$ENDIF}
2349 if (distSq < lastDistSq) then
2350 begin
2351 ex := x;
2352 ey := y;
2353 result := px.mObj;
2354 mInQuery := false;
2355 exit;
2356 end;
2357 end;
2358 continue;
2359 end;
2360 // remember this hitpoint if it is nearer than an old one
2361 // setup prev[xy]
2362 if hopt then
2363 begin
2364 // horizontal trace
2365 prevy := y;
2366 y := yptr^+miny;
2367 if (stx < 0) then
2368 begin
2369 // going left
2370 if (x < px.x1) then continue; // not on the right edge
2371 x := px.x1;
2372 prevx := x+1;
2373 end
2374 else
2375 begin
2376 // going right
2377 if (x > px.x0) then continue; // not on the left edge
2378 x := px.x0;
2379 prevx := x-1;
2380 end;
2381 end
2382 else
2383 begin
2384 // vertical trace
2385 prevx := x;
2386 x := xptr^+minx;
2387 if (stx < 0) then
2388 begin
2389 // going up
2390 if (y < px.y1) then continue; // not on the bottom edge
2391 y := px.y1;
2392 prevy := x+1;
2393 end
2394 else
2395 begin
2396 // going down
2397 if (y > px.y0) then continue; // not on the top edge
2398 y := px.y0;
2399 prevy := y-1;
2400 end;
2401 end;
2402 if assigned(cb) then
2403 begin
2404 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2405 begin
2406 result := px.mObj;
2407 ex := prevx;
2408 ey := prevy;
2409 mInQuery := false;
2410 exit;
2411 end;
2412 end
2413 else
2414 begin
2415 distSq := distanceSq(ax0, ay0, prevx, prevy);
2416 {$IF DEFINED(D2F_DEBUG)}
2417 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]);
2418 {$ENDIF}
2419 if (distSq < lastDistSq) then
2420 begin
2421 wasHit := true;
2422 lastDistSq := distSq;
2423 ex := prevx;
2424 ey := prevy;
2425 lastObj := px.mObj;
2426 end;
2427 end;
2428 end;
2429 end;
2430 // next cell
2431 ccidx := cc.next;
2432 end;
2433 if wasHit and not assigned(cb) then begin result := lastObj; mInQuery := false; exit; end;
2434 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2435 end;
2436 // skip to next tile
2437 if hopt then
2438 begin
2439 if (stx > 0) then
2440 begin
2441 // to the right
2442 wkstep := ((xptr^ or (mTileSize-1))+1)-xptr^;
2443 {$IF DEFINED(D2F_DEBUG)}
2444 if dbgShowTraceLog then e_LogWritefln(' right step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2445 {$ENDIF}
2446 if (wkstep >= wklen) then break;
2447 Inc(xptr^, wkstep);
2448 Inc(ga);
2449 end
2450 else
2451 begin
2452 // to the left
2453 wkstep := xptr^-((xptr^ and (not (mTileSize-1)))-1);
2454 {$IF DEFINED(D2F_DEBUG)}
2455 if dbgShowTraceLog then e_LogWritefln(' left step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2456 {$ENDIF}
2457 if (wkstep >= wklen) then break;
2458 Dec(xptr^, wkstep);
2459 Dec(ga);
2460 end;
2461 end
2462 else
2463 begin
2464 if (stx > 0) then
2465 begin
2466 // to the down
2467 wkstep := ((yptr^ or (mTileSize-1))+1)-yptr^;
2468 {$IF DEFINED(D2F_DEBUG)}
2469 if dbgShowTraceLog then e_LogWritefln(' down step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2470 {$ENDIF}
2471 if (wkstep >= wklen) then break;
2472 Inc(yptr^, wkstep);
2473 Inc(ga, mWidth);
2474 end
2475 else
2476 begin
2477 // to the up
2478 wkstep := yptr^-((yptr^ and (not (mTileSize-1)))-1);
2479 {$IF DEFINED(D2F_DEBUG)}
2480 if dbgShowTraceLog then e_LogWritefln(' up step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2481 {$ENDIF}
2482 if (wkstep >= wklen) then break;
2483 Dec(yptr^, wkstep);
2484 Dec(ga, mWidth);
2485 end;
2486 end;
2487 Dec(wklen, wkstep);
2488 end;
2489 // we can travel less than one cell
2490 if wasHit and not assigned(cb) then result := lastObj else begin ex := ax1; ey := ay1; end;
2491 mInQuery := false;
2492 exit;
2493 end;
2494 {$ENDIF}
2496 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2497 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2498 {$ENDIF}
2500 //e_LogWritefln('*********************', []);
2501 ccidx := -1;
2502 // can omit checks
2503 while (xd <> term) do
2504 begin
2505 // check cell(s)
2506 {$IF DEFINED(D2F_DEBUG)}
2507 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2508 {$ENDIF}
2509 // new tile?
2510 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2511 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2512 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);
2513 {$ENDIF}
2514 if (ga <> lastGA) then
2515 begin
2516 // yes
2517 {$IF DEFINED(D2F_DEBUG)}
2518 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2519 {$ENDIF}
2520 if (ccidx <> -1) then
2521 begin
2522 // signal cell completion
2523 if assigned(cb) then
2524 begin
2525 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2526 end
2527 else if wasHit then
2528 begin
2529 result := lastObj;
2530 mInQuery := false;
2531 exit;
2532 end;
2533 end;
2534 lastGA := ga;
2535 ccidx := mGrid[lastGA];
2536 end;
2537 // has something to process in this tile?
2538 if (ccidx <> -1) then
2539 begin
2540 // process cell
2541 curci := ccidx;
2542 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2543 // convert coords to map (to avoid ajdusting coords inside the loop)
2544 x := xptr^+minx;
2545 y := yptr^+miny;
2546 // process cell list
2547 while (curci <> -1) do
2548 begin
2549 cc := @mCells[curci];
2550 for f := 0 to GridCellBucketSize-1 do
2551 begin
2552 if (cc.bodies[f] = -1) then break;
2553 px := @mProxies[cc.bodies[f]];
2554 ptag := px.mTag;
2555 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
2556 begin
2557 // can we process this proxy?
2558 if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
2559 begin
2560 px.mQueryMark := lq; // mark as processed
2561 if assigned(cb) then
2562 begin
2563 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2564 begin
2565 result := px.mObj;
2566 ex := prevx;
2567 ey := prevy;
2568 mInQuery := false;
2569 exit;
2570 end;
2571 end
2572 else
2573 begin
2574 // remember this hitpoint if it is nearer than an old one
2575 distSq := distanceSq(ax0, ay0, prevx, prevy);
2576 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2577 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);
2578 {$ENDIF}
2579 if (distSq < lastDistSq) then
2580 begin
2581 wasHit := true;
2582 lastDistSq := distSq;
2583 ex := prevx;
2584 ey := prevy;
2585 lastObj := px.mObj;
2586 end;
2587 end;
2588 end
2589 else
2590 begin
2591 // this is possibly interesting proxy, set "has more to check" flag
2592 hasUntried := true;
2593 end;
2594 end;
2595 end;
2596 // next cell
2597 curci := cc.next;
2598 end;
2599 // still has something interesting in this cell?
2600 if not hasUntried then
2601 begin
2602 // nope, don't process this cell anymore; signal cell completion
2603 ccidx := -1;
2604 if assigned(cb) then
2605 begin
2606 if cb(nil, 0, x, y, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2607 end
2608 else if wasHit then
2609 begin
2610 result := lastObj;
2611 mInQuery := false;
2612 exit;
2613 end;
2614 end;
2615 end;
2616 if (ccidx = -1) then
2617 begin
2618 // move to cell edge, as we have nothing to trace here anymore
2619 if (stx < 0) then xdist := xd and (not (mTileSize-1)) else xdist := xd or (mTileSize-1);
2620 if (sty < 0) then ydist := yd and (not (mTileSize-1)) else ydist := yd or (mTileSize-1);
2621 //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]);
2622 while (xd <> xdist) and (yd <> ydist) do
2623 begin
2624 // step
2625 xd += stx;
2626 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2627 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2628 if (xd = term) then break;
2629 end;
2630 //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]);
2631 if (xd = term) then break;
2632 end;
2633 //putPixel(xptr^, yptr^);
2634 // move coords
2635 prevx := xptr^+minx;
2636 prevy := yptr^+miny;
2637 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2638 xd += stx;
2639 end;
2640 // we can travel less than one cell
2641 if wasHit and not assigned(cb) then
2642 begin
2643 result := lastObj;
2644 end
2645 else
2646 begin
2647 ex := ax1; // why not?
2648 ey := ay1; // why not?
2649 end;
2651 mInQuery := false;
2652 end;
2653 *)