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; 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; 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
1688 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1690 begin
1695 begin
1698 //mInQuery := false;
1699 exit;
1704 // next cell
1711 begin
1714 // just in case, compensate for floating point inexactness
1715 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1716 begin
1722 //mInQuery := false;
1726 // ////////////////////////////////////////////////////////////////////////// //
1727 {.$DEFINE D2F_DEBUG_OTR}
1728 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1729 var
1740 {$IF DEFINED(D2F_DEBUG_OTR)}
1742 {$ENDIF}
1744 begin
1760 // offset query coords to (0,0)-based
1767 begin
1769 // vertical
1771 begin
1772 // down
1774 //if (ay0 < 0) then ay0 := 0;
1778 end
1779 else
1780 begin
1781 // up
1783 //if (ay1 < 0) then ay1 := 0;
1788 // check tile
1790 begin
1796 begin
1799 begin
1805 begin
1806 // bound c0 and c1 to cell
1809 // fill the thing
1810 {$IF DEFINED(D2F_DEBUG_OTR)}
1811 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)]);
1812 {$ENDIF}
1813 //assert(c0 <= c1);
1817 // next cell
1820 {$IF DEFINED(D2F_DEBUG_OTR)}
1821 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1825 {$ENDIF}
1826 // now go till we hit cell boundary or empty space
1828 begin
1829 // up
1831 begin
1832 {$IF DEFINED(D2F_DEBUG_OTR)}
1833 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1834 {$ENDIF}
1838 {$IF DEFINED(D2F_DEBUG_OTR)}
1839 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1840 {$ENDIF}
1842 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1843 end
1844 else
1845 begin
1846 // down
1852 end
1853 else
1854 begin
1855 // horizontal
1861 // ////////////////////////////////////////////////////////////////////////// //
1862 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1863 var
1865 begin
1870 // no callback: return `true` on the nearest hit
1871 // you are not supposed to understand this
1872 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1873 var
1888 begin
1898 // make query coords (0,0)-based
1909 {$IF DEFINED(D2F_DEBUG)}
1910 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1911 {$ENDIF}
1913 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1914 //mInQuery := true;
1916 // increase query counter
1919 begin
1920 // just in case of overflow
1926 repeat
1928 {$IF DEFINED(D2F_DEBUG)}
1930 {$ENDIF}
1931 // check tile
1933 // process cells
1936 begin
1939 begin
1944 begin
1947 begin
1950 // get adjusted proxy coords
1955 {$IF DEFINED(D2F_DEBUG)}
1956 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1957 {$ENDIF}
1958 // inside?
1960 begin
1961 // oops
1965 //mInQuery := false;
1966 {$IF DEFINED(D2F_DEBUG)}
1968 {$ENDIF}
1969 exit;
1971 // do line-vs-aabb test
1973 begin
1974 // hit detected
1976 {$IF DEFINED(D2F_DEBUG)}
1977 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1978 {$ENDIF}
1980 begin
1990 // next cell
1993 // done processing cells; exit if we registered a hit
1994 // next cells can't have better candidates, obviously
1997 // move to next tile
2000 //mInQuery := false;
2004 // ////////////////////////////////////////////////////////////////////////// //
2005 // no callback: return `true` on the nearest hit
2006 (*
2007 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2008 var
2009 ex, ey: Integer;
2010 begin
2011 result := traceRayOld(ex, ey, x0, y0, x1, y1, cb, tagmask);
2012 end;
2015 // no callback: return `true` on the nearest hit
2016 // you are not supposed to understand this
2017 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2018 var
2019 wx0, wy0, wx1, wy1: Integer; // window coordinates
2020 stx, sty: Integer; // "steps" for x and y axes
2021 dsx, dsy: Integer; // "lengthes" for x and y axes
2022 dx2, dy2: Integer; // "double lengthes" for x and y axes
2023 xd, yd: Integer; // current coord
2024 e: Integer; // "error" (as in bresenham algo)
2025 rem: Integer;
2026 term: Integer;
2027 xptr, yptr: PInteger;
2028 xfixed: Boolean;
2029 temp: Integer;
2030 prevx, prevy: Integer;
2031 lastDistSq: Integer;
2032 ccidx, curci: Integer;
2033 hasUntried: Boolean;
2034 lastGA: Integer = -1;
2035 ga, x, y: Integer;
2036 lastObj: ITP;
2037 wasHit: Boolean = false;
2038 gw, gh, minx, miny, maxx, maxy: Integer;
2039 cc: PGridCell;
2040 px: PBodyProxyRec;
2041 lq: LongWord;
2042 f, ptag, distSq: Integer;
2043 x0, y0, x1, y1: Integer;
2044 //swapped: Boolean = false; // true: xd is yd, and vice versa
2045 // horizontal walker
2046 {$IFDEF GRID_USE_ORTHO_ACCEL}
2047 wklen, wkstep: Integer;
2048 //wksign: Integer;
2049 hopt: Boolean;
2050 {$ENDIF}
2051 // skipper
2052 xdist, ydist: Integer;
2053 begin
2054 result := Default(ITP);
2055 lastObj := Default(ITP);
2056 tagmask := tagmask and TagFullMask;
2057 ex := ax1; // why not?
2058 ey := ay1; // why not?
2059 if (tagmask = 0) then exit;
2061 if (ax0 = ax1) and (ay0 = ay1) then
2062 begin
2063 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2064 if (result <> nil) then
2065 begin
2066 if assigned(cb) and not cb(result, ptag, ax0, ay0, ax0, ay0) then result := Default(ITP);
2067 end;
2068 exit;
2069 end;
2071 lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1;
2073 gw := mWidth;
2074 gh := mHeight;
2075 minx := mMinX;
2076 miny := mMinY;
2077 maxx := gw*mTileSize-1;
2078 maxy := gh*mTileSize-1;
2080 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2081 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);
2082 {$ENDIF}
2084 x0 := ax0;
2085 y0 := ay0;
2086 x1 := ax1;
2087 y1 := ay1;
2089 // offset query coords to (0,0)-based
2090 Dec(x0, minx);
2091 Dec(y0, miny);
2092 Dec(x1, minx);
2093 Dec(y1, miny);
2095 // clip rectange
2096 wx0 := 0;
2097 wy0 := 0;
2098 wx1 := maxx;
2099 wy1 := maxy;
2101 // horizontal setup
2102 if (x0 < x1) then
2103 begin
2104 // from left to right
2105 if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
2106 stx := 1; // going right
2107 end
2108 else
2109 begin
2110 // from right to left
2111 if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
2112 stx := -1; // going left
2113 x0 := -x0;
2114 x1 := -x1;
2115 wx0 := -wx0;
2116 wx1 := -wx1;
2117 swapInt(wx0, wx1);
2118 end;
2120 // vertical setup
2121 if (y0 < y1) then
2122 begin
2123 // from top to bottom
2124 if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
2125 sty := 1; // going down
2126 end
2127 else
2128 begin
2129 // from bottom to top
2130 if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
2131 sty := -1; // going up
2132 y0 := -y0;
2133 y1 := -y1;
2134 wy0 := -wy0;
2135 wy1 := -wy1;
2136 swapInt(wy0, wy1);
2137 end;
2139 dsx := x1-x0;
2140 dsy := y1-y0;
2142 if (dsx < dsy) then
2143 begin
2144 //swapped := true;
2145 xptr := @yd;
2146 yptr := @xd;
2147 swapInt(x0, y0);
2148 swapInt(x1, y1);
2149 swapInt(dsx, dsy);
2150 swapInt(wx0, wy0);
2151 swapInt(wx1, wy1);
2152 swapInt(stx, sty);
2153 end
2154 else
2155 begin
2156 xptr := @xd;
2157 yptr := @yd;
2158 end;
2160 dx2 := 2*dsx;
2161 dy2 := 2*dsy;
2162 xd := x0;
2163 yd := y0;
2164 e := 2*dsy-dsx;
2165 term := x1;
2167 xfixed := false;
2168 if (y0 < wy0) then
2169 begin
2170 // clip at top
2171 temp := dx2*(wy0-y0)-dsx;
2172 xd += temp div dy2;
2173 rem := temp mod dy2;
2174 if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
2175 if (xd+1 >= wx0) then
2176 begin
2177 yd := wy0;
2178 e -= rem+dsx;
2179 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2180 if (xd < wx0) then begin xd += 1; e += dy2; end; //???
2181 xfixed := true;
2182 end;
2183 end;
2185 if (not xfixed) and (x0 < wx0) then
2186 begin
2187 // clip at left
2188 temp := dy2*(wx0-x0);
2189 yd += temp div dx2;
2190 rem := temp mod dx2;
2191 if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
2192 xd := wx0;
2193 e += rem;
2194 if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
2195 end;
2197 if (y1 > wy1) then
2198 begin
2199 // clip at bottom
2200 temp := dx2*(wy1-y0)+dsx;
2201 term := x0+temp div dy2;
2202 rem := temp mod dy2;
2203 if (rem = 0) then Dec(term);
2204 end;
2206 if (term > wx1) then term := wx1; // clip at right
2208 Inc(term); // draw last point
2209 //if (term = xd) then exit; // this is the only point, get out of here
2211 if (sty = -1) then yd := -yd;
2212 if (stx = -1) then begin xd := -xd; term := -term; end;
2213 dx2 -= dy2;
2215 // first move, to skip starting point
2216 // DON'T DO THIS! loop will take care of that
2217 if (xd = term) then
2218 begin
2219 //FIXME!
2220 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2221 if (result <> nil) then
2222 begin
2223 if assigned(cb) then
2224 begin
2225 if cb(result, ptag, ax0, ay0, ax0, ay0) then
2226 begin
2227 ex := ax0;
2228 ey := ay0;
2229 end
2230 else
2231 begin
2232 result := nil;
2233 end;
2234 end
2235 else
2236 begin
2237 ex := ax0;
2238 ey := ay0;
2239 end;
2240 end;
2241 exit;
2242 end;
2244 prevx := xptr^+minx;
2245 prevy := yptr^+miny;
2246 ( *
2247 // move coords
2248 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2249 xd += stx;
2250 // done?
2251 if (xd = term) then exit;
2252 * )
2254 {$IF DEFINED(D2F_DEBUG)}
2255 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2256 {$ENDIF}
2257 // DON'T DO THIS! loop will take care of that
2258 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2259 //ccidx := mGrid[lastGA];
2261 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2262 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2263 {$ENDIF}
2265 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2267 if mInQuery then raise Exception.Create('recursive queries aren''t supported');
2268 mInQuery := true;
2270 // increase query counter
2271 Inc(mLastQuery);
2272 if (mLastQuery = 0) then
2273 begin
2274 // just in case of overflow
2275 mLastQuery := 1;
2276 for f := 0 to High(mProxies) do mProxies[f].mQueryMark := 0;
2277 end;
2278 lq := mLastQuery;
2280 {$IFDEF GRID_USE_ORTHO_ACCEL}
2281 // if this is strict horizontal/vertical trace, use optimized codepath
2282 if (ax0 = ax1) or (ay0 = ay1) then
2283 begin
2284 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2285 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2286 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2287 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2288 hopt := (ay0 = ay1); // horizontal?
2289 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2290 {$IF DEFINED(D2F_DEBUG)}
2291 if dbgShowTraceLog then e_LogWritefln('optimized htrace; wklen=%d', [wklen]);
2292 {$ENDIF}
2293 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2294 // one of those will never change
2295 x := xptr^+minx;
2296 y := yptr^+miny;
2297 while (wklen > 0) do
2298 begin
2299 {$IF DEFINED(D2F_DEBUG)}
2300 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2301 {$ENDIF}
2302 // new tile?
2303 if (ga <> lastGA) then
2304 begin
2305 lastGA := ga;
2306 ccidx := mGrid[lastGA];
2307 // convert coords to map (to avoid ajdusting coords inside the loop)
2308 if hopt then x := xptr^+minx else y := yptr^+miny;
2309 while (ccidx <> -1) do
2310 begin
2311 cc := @mCells[ccidx];
2312 for f := 0 to GridCellBucketSize-1 do
2313 begin
2314 if (cc.bodies[f] = -1) then break;
2315 px := @mProxies[cc.bodies[f]];
2316 ptag := px.mTag;
2317 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and
2318 // constant coord should be inside
2319 ((hopt and (y >= px.y0) and (y <= px.y1)) or
2320 ((not hopt) and (x >= px.x0) and (x <= px.x1))) then
2321 begin
2322 px.mQueryMark := lq; // mark as processed
2323 // inside the proxy?
2324 if (hopt and (x > px.x0) and (x < px.x1)) or
2325 ((not hopt) and (y > px.y0) and (y < px.y1)) then
2326 begin
2327 // setup prev[xy]
2328 if assigned(cb) then
2329 begin
2330 if cb(px.mObj, ptag, x, y, x, y) then
2331 begin
2332 result := px.mObj;
2333 ex := x;
2334 ey := y;
2335 mInQuery := false;
2336 exit;
2337 end;
2338 end
2339 else
2340 begin
2341 distSq := distanceSq(ax0, ay0, x, y);
2342 {$IF DEFINED(D2F_DEBUG)}
2343 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]);
2344 {$ENDIF}
2345 if (distSq < lastDistSq) then
2346 begin
2347 ex := x;
2348 ey := y;
2349 result := px.mObj;
2350 mInQuery := false;
2351 exit;
2352 end;
2353 end;
2354 continue;
2355 end;
2356 // remember this hitpoint if it is nearer than an old one
2357 // setup prev[xy]
2358 if hopt then
2359 begin
2360 // horizontal trace
2361 prevy := y;
2362 y := yptr^+miny;
2363 if (stx < 0) then
2364 begin
2365 // going left
2366 if (x < px.x1) then continue; // not on the right edge
2367 x := px.x1;
2368 prevx := x+1;
2369 end
2370 else
2371 begin
2372 // going right
2373 if (x > px.x0) then continue; // not on the left edge
2374 x := px.x0;
2375 prevx := x-1;
2376 end;
2377 end
2378 else
2379 begin
2380 // vertical trace
2381 prevx := x;
2382 x := xptr^+minx;
2383 if (stx < 0) then
2384 begin
2385 // going up
2386 if (y < px.y1) then continue; // not on the bottom edge
2387 y := px.y1;
2388 prevy := x+1;
2389 end
2390 else
2391 begin
2392 // going down
2393 if (y > px.y0) then continue; // not on the top edge
2394 y := px.y0;
2395 prevy := y-1;
2396 end;
2397 end;
2398 if assigned(cb) then
2399 begin
2400 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2401 begin
2402 result := px.mObj;
2403 ex := prevx;
2404 ey := prevy;
2405 mInQuery := false;
2406 exit;
2407 end;
2408 end
2409 else
2410 begin
2411 distSq := distanceSq(ax0, ay0, prevx, prevy);
2412 {$IF DEFINED(D2F_DEBUG)}
2413 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]);
2414 {$ENDIF}
2415 if (distSq < lastDistSq) then
2416 begin
2417 wasHit := true;
2418 lastDistSq := distSq;
2419 ex := prevx;
2420 ey := prevy;
2421 lastObj := px.mObj;
2422 end;
2423 end;
2424 end;
2425 end;
2426 // next cell
2427 ccidx := cc.next;
2428 end;
2429 if wasHit and not assigned(cb) then begin result := lastObj; mInQuery := false; exit; end;
2430 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2431 end;
2432 // skip to next tile
2433 if hopt then
2434 begin
2435 if (stx > 0) then
2436 begin
2437 // to the right
2438 wkstep := ((xptr^ or (mTileSize-1))+1)-xptr^;
2439 {$IF DEFINED(D2F_DEBUG)}
2440 if dbgShowTraceLog then e_LogWritefln(' right step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2441 {$ENDIF}
2442 if (wkstep >= wklen) then break;
2443 Inc(xptr^, wkstep);
2444 Inc(ga);
2445 end
2446 else
2447 begin
2448 // to the left
2449 wkstep := xptr^-((xptr^ and (not (mTileSize-1)))-1);
2450 {$IF DEFINED(D2F_DEBUG)}
2451 if dbgShowTraceLog then e_LogWritefln(' left step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2452 {$ENDIF}
2453 if (wkstep >= wklen) then break;
2454 Dec(xptr^, wkstep);
2455 Dec(ga);
2456 end;
2457 end
2458 else
2459 begin
2460 if (stx > 0) then
2461 begin
2462 // to the down
2463 wkstep := ((yptr^ or (mTileSize-1))+1)-yptr^;
2464 {$IF DEFINED(D2F_DEBUG)}
2465 if dbgShowTraceLog then e_LogWritefln(' down step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2466 {$ENDIF}
2467 if (wkstep >= wklen) then break;
2468 Inc(yptr^, wkstep);
2469 Inc(ga, mWidth);
2470 end
2471 else
2472 begin
2473 // to the up
2474 wkstep := yptr^-((yptr^ and (not (mTileSize-1)))-1);
2475 {$IF DEFINED(D2F_DEBUG)}
2476 if dbgShowTraceLog then e_LogWritefln(' up step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2477 {$ENDIF}
2478 if (wkstep >= wklen) then break;
2479 Dec(yptr^, wkstep);
2480 Dec(ga, mWidth);
2481 end;
2482 end;
2483 Dec(wklen, wkstep);
2484 end;
2485 // we can travel less than one cell
2486 if wasHit and not assigned(cb) then result := lastObj else begin ex := ax1; ey := ay1; end;
2487 mInQuery := false;
2488 exit;
2489 end;
2490 {$ENDIF}
2492 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2493 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2494 {$ENDIF}
2496 //e_LogWritefln('*********************', []);
2497 ccidx := -1;
2498 // can omit checks
2499 while (xd <> term) do
2500 begin
2501 // check cell(s)
2502 {$IF DEFINED(D2F_DEBUG)}
2503 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2504 {$ENDIF}
2505 // new tile?
2506 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2507 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2508 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);
2509 {$ENDIF}
2510 if (ga <> lastGA) then
2511 begin
2512 // yes
2513 {$IF DEFINED(D2F_DEBUG)}
2514 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2515 {$ENDIF}
2516 if (ccidx <> -1) then
2517 begin
2518 // signal cell completion
2519 if assigned(cb) then
2520 begin
2521 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2522 end
2523 else if wasHit then
2524 begin
2525 result := lastObj;
2526 mInQuery := false;
2527 exit;
2528 end;
2529 end;
2530 lastGA := ga;
2531 ccidx := mGrid[lastGA];
2532 end;
2533 // has something to process in this tile?
2534 if (ccidx <> -1) then
2535 begin
2536 // process cell
2537 curci := ccidx;
2538 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2539 // convert coords to map (to avoid ajdusting coords inside the loop)
2540 x := xptr^+minx;
2541 y := yptr^+miny;
2542 // process cell list
2543 while (curci <> -1) do
2544 begin
2545 cc := @mCells[curci];
2546 for f := 0 to GridCellBucketSize-1 do
2547 begin
2548 if (cc.bodies[f] = -1) then break;
2549 px := @mProxies[cc.bodies[f]];
2550 ptag := px.mTag;
2551 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
2552 begin
2553 // can we process this proxy?
2554 if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
2555 begin
2556 px.mQueryMark := lq; // mark as processed
2557 if assigned(cb) then
2558 begin
2559 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2560 begin
2561 result := px.mObj;
2562 ex := prevx;
2563 ey := prevy;
2564 mInQuery := false;
2565 exit;
2566 end;
2567 end
2568 else
2569 begin
2570 // remember this hitpoint if it is nearer than an old one
2571 distSq := distanceSq(ax0, ay0, prevx, prevy);
2572 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2573 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);
2574 {$ENDIF}
2575 if (distSq < lastDistSq) then
2576 begin
2577 wasHit := true;
2578 lastDistSq := distSq;
2579 ex := prevx;
2580 ey := prevy;
2581 lastObj := px.mObj;
2582 end;
2583 end;
2584 end
2585 else
2586 begin
2587 // this is possibly interesting proxy, set "has more to check" flag
2588 hasUntried := true;
2589 end;
2590 end;
2591 end;
2592 // next cell
2593 curci := cc.next;
2594 end;
2595 // still has something interesting in this cell?
2596 if not hasUntried then
2597 begin
2598 // nope, don't process this cell anymore; signal cell completion
2599 ccidx := -1;
2600 if assigned(cb) then
2601 begin
2602 if cb(nil, 0, x, y, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2603 end
2604 else if wasHit then
2605 begin
2606 result := lastObj;
2607 mInQuery := false;
2608 exit;
2609 end;
2610 end;
2611 end;
2612 if (ccidx = -1) then
2613 begin
2614 // move to cell edge, as we have nothing to trace here anymore
2615 if (stx < 0) then xdist := xd and (not (mTileSize-1)) else xdist := xd or (mTileSize-1);
2616 if (sty < 0) then ydist := yd and (not (mTileSize-1)) else ydist := yd or (mTileSize-1);
2617 //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]);
2618 while (xd <> xdist) and (yd <> ydist) do
2619 begin
2620 // step
2621 xd += stx;
2622 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2623 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2624 if (xd = term) then break;
2625 end;
2626 //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]);
2627 if (xd = term) then break;
2628 end;
2629 //putPixel(xptr^, yptr^);
2630 // move coords
2631 prevx := xptr^+minx;
2632 prevy := yptr^+miny;
2633 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2634 xd += stx;
2635 end;
2636 // we can travel less than one cell
2637 if wasHit and not assigned(cb) then
2638 begin
2639 result := lastObj;
2640 end
2641 else
2642 begin
2643 ex := ax1; // why not?
2644 ey := ay1; // why not?
2645 end;
2647 mInQuery := false;
2648 end;
2649 *)