a41349315a469391e90a1c268d56c01b81f9f294
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
52 type
56 public
59 //type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
60 //type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
66 private
67 const
70 public
71 type
74 private
81 private
93 public
108 private
109 type
118 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
120 private
121 //mTileSize: Integer;
125 public
128 type
130 private
134 public
141 private
153 //mInQuery: Boolean;
155 public
157 {$IF DEFINED(D2F_DEBUG)}
159 {$ENDIF}
161 private
181 public
182 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
185 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
194 // `false` if `body` is surely invalid
199 //WARNING: don't modify grid while any query is in progress (no checks are made!)
200 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
201 // no callback: return `true` on the first hit
202 //function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
203 // return number of ITP thingys put into frame pool
204 function forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
206 //WARNING: don't modify grid while any query is in progress (no checks are made!)
207 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
208 // no callback: return object on the first hit or nil
209 //function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1{; exittag: PInteger=nil}): ITP;
210 function forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
214 //WARNING: don't modify grid while any query is in progress (no checks are made!)
215 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
216 // cb with `(nil)` will be called before processing new tile
217 // no callback: return object of the nearest hit or nil
218 // if `inverted` is true, trace will register bodies *exluding* tagmask
219 //WARNING: don't change tags in callbacks here!
220 {
221 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
222 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
223 }
225 //WARNING: don't modify grid while any query is in progress (no checks are made!)
226 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
227 // return object of the nearest hit or nil
228 // if `inverted` is true, trace will register bodies *exluding* tagmask
229 //WARNING: don't change tags in callbacks here!
231 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
233 // return `false` if we're still inside at the end
234 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
235 // `true`: endpoint will point at the last "inside" pixel
236 // `false`: endpoint will be (ax1, ay1)
237 //WARNING: don't change tags in callbacks here!
238 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
240 //WARNING: don't modify grid while any query is in progress (no checks are made!)
241 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
242 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
243 //WARNING: don't change tags in callbacks here!
244 //function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
245 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1; log: Boolean=false): Integer;
247 // trace box with the given velocity; return object hit (if any)
248 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
249 //WARNING: don't change tags in callbacks here!
250 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; tagmask: Integer=-1): ITP;
252 // debug
253 function forEachBodyCell (body: TBodyProxyId): Integer; // this puts `TGridCellCoord` into frame pool for each cell
257 public
258 //WARNING! no sanity checks!
270 type
271 // common structure for all line tracers
273 public
276 private
284 public
285 // call `setyp` after this
290 // this will use `w[xy][01]` to clip coords
291 // return `false` if the whole line was clipped away
292 // on `true`, you should process first point, and go on
295 // call this *after* doing a step
296 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
299 // as you will prolly call `done()` after doing a step anyway, this will do it for you
300 // move to next point, return `true` when the line is complete (i.e. you should stop)
303 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
308 public
309 // current coords
316 //function minInt (a, b: Integer): Integer; inline;
317 //function maxInt (a, b: Integer): Integer; inline;
320 implementation
322 uses
326 // ////////////////////////////////////////////////////////////////////////// //
327 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
328 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
329 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
330 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
333 // ////////////////////////////////////////////////////////////////////////// //
335 begin
340 begin
341 // clip rectange
349 var
351 begin
352 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
356 begin
358 end
359 else
360 begin
369 // check for ortho lines
371 begin
372 // horizontal
379 end
381 begin
382 // vertical
389 end
390 else
391 begin
392 // diagonal
394 begin
395 // horizontal
399 end
400 else
401 begin
402 // vertical
418 // true: done
420 begin
422 begin
426 end
427 else
428 begin
437 // true: done
439 var
443 begin
448 // strictly horizontal?
450 begin
451 // only xd
453 begin
454 // xd: to left edge
457 end
458 else
459 begin
460 // xd: to right edge
466 exit;
469 // strictly vertical?
471 begin
472 // only xd
474 begin
475 // yd: to top edge
478 end
479 else
480 begin
481 // yd: to bottom edge
487 exit;
490 // diagonal
492 // calculate xwalk
494 begin
497 end
498 else
499 begin
504 // calculate ywalk
506 begin
509 end
510 else
511 begin
516 {
517 while (xd <> ex) and (yd <> ey) do
518 begin
519 if horiz then
520 begin
521 xd += stx;
522 err += errinc;
523 if (err >= 0) then begin err -= errmax; yd += sty; end;
524 end
525 else
526 begin
527 yd += sty;
528 err += errinc;
529 if (err >= 0) then begin err -= errmax; xd += stx; end;
530 end;
531 Dec(stleft);
532 if (stleft < 1) then begin result := true; exit; end;
533 end;
534 }
538 begin
539 // in which dir we want to walk?
543 begin
546 begin
550 end
551 else
552 begin
555 begin
560 // check for walk completion
569 // ////////////////////////////////////////////////////////////////////////// //
570 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
571 begin
584 begin
589 begin
594 begin
599 begin
604 begin
609 begin
614 // ////////////////////////////////////////////////////////////////////////// //
615 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
616 begin
625 begin
627 begin
629 begin
633 exit;
643 begin
648 // ////////////////////////////////////////////////////////////////////////// //
649 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
650 var
652 begin
654 {$IF DEFINED(D2F_DEBUG)}
656 {$ENDIF}
657 {
658 if aTileSize < 1 then aTileSize := 1;
659 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
660 mTileSize := aTileSize;
661 }
672 // init free list
674 begin
680 // init grid
682 // init proxies
690 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
695 begin
703 // ////////////////////////////////////////////////////////////////////////// //
705 var
707 begin
710 begin
714 begin
720 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);
725 var
729 begin
733 begin
736 begin
739 begin
742 begin
747 //cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
750 // next cell
758 var
762 begin
769 begin
772 begin
774 //if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
776 //presobj^ := mProxies[cc.bodies[f]].mObj;
780 // next cell
786 // ////////////////////////////////////////////////////////////////////////// //
787 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
788 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
792 begin
793 // fix coords
801 begin
803 begin
806 end
807 else
808 begin
817 begin
819 begin
822 end
823 else
824 begin
832 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
833 begin
835 begin
838 end
839 else
840 begin
851 // ////////////////////////////////////////////////////////////////////////// //
853 begin
854 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
859 begin
861 begin
863 begin
865 end
866 else
867 begin
875 begin
880 // ////////////////////////////////////////////////////////////////////////// //
882 var
885 begin
887 begin
888 // no free cells, want more
892 begin
904 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
909 begin
911 begin
913 begin
924 // ////////////////////////////////////////////////////////////////////////// //
925 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
926 var
929 begin
931 begin
932 // no free proxies, resize list
939 // get one from list
944 // add to used list
946 // statistics
952 begin
954 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
955 // add to free list
963 // ////////////////////////////////////////////////////////////////////////// //
964 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
965 var
969 begin
972 // fix coords
975 // go on
984 // clip rect
990 // do the work
992 begin
994 begin
1002 // ////////////////////////////////////////////////////////////////////////// //
1004 var
1009 begin
1011 // add body to the given grid cell
1014 begin
1015 {$IF DEFINED(D2F_DEBUG)}
1018 begin
1021 begin
1023 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1027 {$ENDIF}
1030 begin
1032 // check "has room" flag
1034 begin
1035 // can add here
1037 begin
1039 begin
1042 exit;
1047 // no room, go to next cell in list (if there is any)
1050 // no room in cells, add new cell to list
1052 // either no room, or no cell at all
1062 // assume that we cannot have one object added to bucket twice
1064 var
1068 begin
1070 // find and remove cell
1074 begin
1077 begin
1079 begin
1080 // i found her!
1082 begin
1083 // this cell contains no elements, remove it
1086 exit;
1088 // remove element from bucket
1090 begin
1095 exit;
1104 // ////////////////////////////////////////////////////////////////////////// //
1105 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1106 begin
1109 //insertInternal(result);
1115 var
1117 begin
1120 //removeInternal(body);
1126 // ////////////////////////////////////////////////////////////////////////// //
1128 var
1131 begin
1138 {$IF DEFINED(D2F_DEBUG_MOVER)}
1139 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);
1140 {$ENDIF}
1142 // map -> grid
1147 // did any corner crossed tile boundary?
1152 begin
1153 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1154 //removeInternal(body);
1160 //insertInternal(body);
1162 end
1163 else
1164 begin
1173 //TODO: optimize for horizontal/vertical moves
1175 var
1183 begin
1185 // check if tile coords was changed
1190 // map -> grid
1195 // check for heavy work
1206 {$IF DEFINED(D2F_DEBUG_MOVER)}
1207 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);
1208 {$ENDIF}
1210 begin
1211 // crossed tile boundary, do heavy work
1214 // cycle with old rect, remove body where it is necessary
1215 // optimized for horizontal moves
1216 {$IF DEFINED(D2F_DEBUG_MOVER)}
1217 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);
1218 {$ENDIF}
1219 // remove stale marks
1222 begin
1227 {$IF DEFINED(D2F_DEBUG_MOVER)}
1229 {$ENDIF}
1231 begin
1233 begin
1234 // this column is completely outside of new rect
1236 begin
1237 {$IF DEFINED(D2F_DEBUG_MOVER)}
1239 {$ENDIF}
1242 end
1243 else
1244 begin
1245 // heavy checks
1247 begin
1249 begin
1250 {$IF DEFINED(D2F_DEBUG_MOVER)}
1252 {$ENDIF}
1259 // cycle with new rect, add body where it is necessary
1262 begin
1267 {$IF DEFINED(D2F_DEBUG_MOVER)}
1269 {$ENDIF}
1271 begin
1273 begin
1274 // this column is completely outside of old rect
1276 begin
1277 {$IF DEFINED(D2F_DEBUG_MOVER)}
1279 {$ENDIF}
1282 end
1283 else
1284 begin
1285 // heavy checks
1287 begin
1289 begin
1290 {$IF DEFINED(D2F_DEBUG_MOVER)}
1292 {$ENDIF}
1299 // done
1300 end
1301 else
1302 begin
1303 {$IF DEFINED(D2F_DEBUG_MOVER)}
1304 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);
1305 {$ENDIF}
1307 // update coordinates
1314 var
1317 begin
1319 // check if tile coords was changed
1325 {$IF DEFINED(D2F_DEBUG_MOVER)}
1326 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);
1327 {$ENDIF}
1330 begin
1331 // crossed tile boundary, do heavy work
1332 //removeInternal(body);
1336 //insertInternal(body);
1338 end
1339 else
1340 begin
1341 // nothing to do with the grid, just fix size
1348 // ////////////////////////////////////////////////////////////////////////// //
1350 var
1352 begin
1355 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1360 // ////////////////////////////////////////////////////////////////////////// //
1361 // no callback: return `true` on the first hit
1362 function TBodyGridBase.forEachAtPoint (x, y: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1363 var
1371 begin
1376 {$IF DEFINED(D2F_DEBUG_XXQ)}
1378 {$ENDIF}
1380 // make coords (0,0)-based
1387 {$IF DEFINED(D2F_DEBUG_XXQ)}
1388 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);
1389 {$ENDIF}
1391 // restore coords
1395 // increase query counter
1398 begin
1399 // just in case of overflow
1405 {$IF DEFINED(D2F_DEBUG_XXQ)}
1406 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1407 {$ENDIF}
1410 begin
1411 {$IF DEFINED(D2F_DEBUG_XXQ)}
1412 //if (assigned(cb)) then e_WriteLog(Format(' cell #%d', [curci]), MSG_NOTIFY);
1413 {$ENDIF}
1416 begin
1419 {$IF DEFINED(D2F_DEBUG_XXQ)}
1420 //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);
1421 {$ENDIF}
1428 begin
1440 // ////////////////////////////////////////////////////////////////////////// //
1441 // no callback: return `true` on the first hit
1442 // return number of ITP thingys put into frame pool
1443 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; tagmask: Integer=-1; allowDisabled: Boolean=false; firstHit: Boolean=false): Integer;
1444 var
1457 begin
1462 begin
1464 exit;
1473 // fix coords
1488 // clip rect
1495 // has something to do
1496 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1497 //mInQuery := true;
1499 // increase query counter
1502 begin
1503 // just in case of overflow
1507 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1510 // go on
1512 begin
1514 begin
1515 // process cells
1518 begin
1521 begin
1524 // shit! has to do it this way, so i can change tag in callback
1536 (*
1537 if assigned(cb) then
1538 begin
1539 if cb(px.mObj, ptag) then begin result := px.mObj; mInQuery := false; exit; end;
1540 end
1541 else
1542 begin
1543 result := px.mObj;
1544 mInQuery := false;
1545 exit;
1546 end;
1547 *)
1554 //mInQuery := false;
1558 // ////////////////////////////////////////////////////////////////////////// //
1559 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1; log: Boolean=false): Integer;
1560 var
1571 //px0, py0, px1, py1: Integer;
1573 begin
1584 // make query coords (0,0)-based
1593 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1594 //mInQuery := true;
1596 // increase query counter
1599 begin
1600 // just in case of overflow
1606 repeat
1608 // check tile
1610 // process cells
1612 begin
1615 begin
1620 begin
1625 {
1626 if cb(px.mObj, ptag) then
1627 begin
1628 result := px.mObj;
1629 //mInQuery := false;
1630 exit;
1631 end;
1632 }
1635 // next cell
1638 // done processing cells, move to next tile
1641 //mInQuery := false;
1645 // ////////////////////////////////////////////////////////////////////////// //
1646 // trace box with the given velocity; return object hit (if any)
1647 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1648 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; tagmask: Integer=-1): ITP;
1649 var
1660 begin
1674 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1680 // just in case
1683 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1684 //mInQuery := true;
1686 // increase query counter
1689 begin
1690 // just in case of overflow
1697 begin
1699 begin
1702 begin
1705 begin
1710 begin
1712 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1714 begin
1719 begin
1722 //mInQuery := false;
1723 exit;
1728 // next cell
1735 begin
1738 // just in case, compensate for floating point inexactness
1739 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1740 begin
1746 //mInQuery := false;
1750 // ////////////////////////////////////////////////////////////////////////// //
1751 {.$DEFINE D2F_DEBUG_OTR}
1752 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1753 var
1764 {$IF DEFINED(D2F_DEBUG_OTR)}
1766 {$ENDIF}
1768 begin
1784 // offset query coords to (0,0)-based
1791 begin
1793 // vertical
1795 begin
1796 // down
1798 //if (ay0 < 0) then ay0 := 0;
1802 end
1803 else
1804 begin
1805 // up
1807 //if (ay1 < 0) then ay1 := 0;
1812 // check tile
1814 begin
1820 begin
1823 begin
1829 begin
1830 // bound c0 and c1 to cell
1833 // fill the thing
1834 {$IF DEFINED(D2F_DEBUG_OTR)}
1835 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)]);
1836 {$ENDIF}
1837 //assert(c0 <= c1);
1841 // next cell
1844 {$IF DEFINED(D2F_DEBUG_OTR)}
1845 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1849 {$ENDIF}
1850 // now go till we hit cell boundary or empty space
1852 begin
1853 // up
1855 begin
1856 {$IF DEFINED(D2F_DEBUG_OTR)}
1857 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1858 {$ENDIF}
1862 {$IF DEFINED(D2F_DEBUG_OTR)}
1863 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1864 {$ENDIF}
1866 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1867 end
1868 else
1869 begin
1870 // down
1876 end
1877 else
1878 begin
1879 // horizontal
1885 // ////////////////////////////////////////////////////////////////////////// //
1887 var
1889 begin
1894 // no callback: return `true` on the nearest hit
1895 // you are not supposed to understand this
1896 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP;
1897 var
1912 begin
1922 // make query coords (0,0)-based
1933 {$IF DEFINED(D2F_DEBUG)}
1934 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1935 {$ENDIF}
1937 //if mInQuery then raise Exception.Create('recursive queries aren''t supported');
1938 //mInQuery := true;
1940 // increase query counter
1943 begin
1944 // just in case of overflow
1950 repeat
1952 {$IF DEFINED(D2F_DEBUG)}
1954 {$ENDIF}
1955 // check tile
1957 // process cells
1960 begin
1963 begin
1968 begin
1970 // get adjusted proxy coords
1975 {$IF DEFINED(D2F_DEBUG)}
1976 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1977 {$ENDIF}
1978 // inside?
1980 begin
1981 // oops
1985 //mInQuery := false;
1986 {$IF DEFINED(D2F_DEBUG)}
1988 {$ENDIF}
1989 exit;
1991 // do line-vs-aabb test
1993 begin
1994 // hit detected
1996 {$IF DEFINED(D2F_DEBUG)}
1997 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1998 {$ENDIF}
2000 begin
2010 // next cell
2013 // done processing cells; exit if we registered a hit
2014 // next cells can't have better candidates, obviously
2017 // move to next tile
2020 //mInQuery := false;
2024 // ////////////////////////////////////////////////////////////////////////// //
2025 // no callback: return `true` on the nearest hit
2026 (*
2027 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2028 var
2029 ex, ey: Integer;
2030 begin
2031 result := traceRayOld(ex, ey, x0, y0, x1, y1, cb, tagmask);
2032 end;
2035 // no callback: return `true` on the nearest hit
2036 // you are not supposed to understand this
2037 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2038 var
2039 wx0, wy0, wx1, wy1: Integer; // window coordinates
2040 stx, sty: Integer; // "steps" for x and y axes
2041 dsx, dsy: Integer; // "lengthes" for x and y axes
2042 dx2, dy2: Integer; // "double lengthes" for x and y axes
2043 xd, yd: Integer; // current coord
2044 e: Integer; // "error" (as in bresenham algo)
2045 rem: Integer;
2046 term: Integer;
2047 xptr, yptr: PInteger;
2048 xfixed: Boolean;
2049 temp: Integer;
2050 prevx, prevy: Integer;
2051 lastDistSq: Integer;
2052 ccidx, curci: Integer;
2053 hasUntried: Boolean;
2054 lastGA: Integer = -1;
2055 ga, x, y: Integer;
2056 lastObj: ITP;
2057 wasHit: Boolean = false;
2058 gw, gh, minx, miny, maxx, maxy: Integer;
2059 cc: PGridCell;
2060 px: PBodyProxyRec;
2061 lq: LongWord;
2062 f, ptag, distSq: Integer;
2063 x0, y0, x1, y1: Integer;
2064 //swapped: Boolean = false; // true: xd is yd, and vice versa
2065 // horizontal walker
2066 {$IFDEF GRID_USE_ORTHO_ACCEL}
2067 wklen, wkstep: Integer;
2068 //wksign: Integer;
2069 hopt: Boolean;
2070 {$ENDIF}
2071 // skipper
2072 xdist, ydist: Integer;
2073 begin
2074 result := Default(ITP);
2075 lastObj := Default(ITP);
2076 tagmask := tagmask and TagFullMask;
2077 ex := ax1; // why not?
2078 ey := ay1; // why not?
2079 if (tagmask = 0) then exit;
2081 if (ax0 = ax1) and (ay0 = ay1) then
2082 begin
2083 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2084 if (result <> nil) then
2085 begin
2086 if assigned(cb) and not cb(result, ptag, ax0, ay0, ax0, ay0) then result := Default(ITP);
2087 end;
2088 exit;
2089 end;
2091 lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1;
2093 gw := mWidth;
2094 gh := mHeight;
2095 minx := mMinX;
2096 miny := mMinY;
2097 maxx := gw*mTileSize-1;
2098 maxy := gh*mTileSize-1;
2100 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2101 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);
2102 {$ENDIF}
2104 x0 := ax0;
2105 y0 := ay0;
2106 x1 := ax1;
2107 y1 := ay1;
2109 // offset query coords to (0,0)-based
2110 Dec(x0, minx);
2111 Dec(y0, miny);
2112 Dec(x1, minx);
2113 Dec(y1, miny);
2115 // clip rectange
2116 wx0 := 0;
2117 wy0 := 0;
2118 wx1 := maxx;
2119 wy1 := maxy;
2121 // horizontal setup
2122 if (x0 < x1) then
2123 begin
2124 // from left to right
2125 if (x0 > wx1) or (x1 < wx0) then exit; // out of screen
2126 stx := 1; // going right
2127 end
2128 else
2129 begin
2130 // from right to left
2131 if (x1 > wx1) or (x0 < wx0) then exit; // out of screen
2132 stx := -1; // going left
2133 x0 := -x0;
2134 x1 := -x1;
2135 wx0 := -wx0;
2136 wx1 := -wx1;
2137 swapInt(wx0, wx1);
2138 end;
2140 // vertical setup
2141 if (y0 < y1) then
2142 begin
2143 // from top to bottom
2144 if (y0 > wy1) or (y1 < wy0) then exit; // out of screen
2145 sty := 1; // going down
2146 end
2147 else
2148 begin
2149 // from bottom to top
2150 if (y1 > wy1) or (y0 < wy0) then exit; // out of screen
2151 sty := -1; // going up
2152 y0 := -y0;
2153 y1 := -y1;
2154 wy0 := -wy0;
2155 wy1 := -wy1;
2156 swapInt(wy0, wy1);
2157 end;
2159 dsx := x1-x0;
2160 dsy := y1-y0;
2162 if (dsx < dsy) then
2163 begin
2164 //swapped := true;
2165 xptr := @yd;
2166 yptr := @xd;
2167 swapInt(x0, y0);
2168 swapInt(x1, y1);
2169 swapInt(dsx, dsy);
2170 swapInt(wx0, wy0);
2171 swapInt(wx1, wy1);
2172 swapInt(stx, sty);
2173 end
2174 else
2175 begin
2176 xptr := @xd;
2177 yptr := @yd;
2178 end;
2180 dx2 := 2*dsx;
2181 dy2 := 2*dsy;
2182 xd := x0;
2183 yd := y0;
2184 e := 2*dsy-dsx;
2185 term := x1;
2187 xfixed := false;
2188 if (y0 < wy0) then
2189 begin
2190 // clip at top
2191 temp := dx2*(wy0-y0)-dsx;
2192 xd += temp div dy2;
2193 rem := temp mod dy2;
2194 if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do
2195 if (xd+1 >= wx0) then
2196 begin
2197 yd := wy0;
2198 e -= rem+dsx;
2199 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2200 if (xd < wx0) then begin xd += 1; e += dy2; end; //???
2201 xfixed := true;
2202 end;
2203 end;
2205 if (not xfixed) and (x0 < wx0) then
2206 begin
2207 // clip at left
2208 temp := dy2*(wx0-x0);
2209 yd += temp div dx2;
2210 rem := temp mod dx2;
2211 if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit;
2212 xd := wx0;
2213 e += rem;
2214 if (rem >= dsx) then begin Inc(yd); e -= dx2; end;
2215 end;
2217 if (y1 > wy1) then
2218 begin
2219 // clip at bottom
2220 temp := dx2*(wy1-y0)+dsx;
2221 term := x0+temp div dy2;
2222 rem := temp mod dy2;
2223 if (rem = 0) then Dec(term);
2224 end;
2226 if (term > wx1) then term := wx1; // clip at right
2228 Inc(term); // draw last point
2229 //if (term = xd) then exit; // this is the only point, get out of here
2231 if (sty = -1) then yd := -yd;
2232 if (stx = -1) then begin xd := -xd; term := -term; end;
2233 dx2 -= dy2;
2235 // first move, to skip starting point
2236 // DON'T DO THIS! loop will take care of that
2237 if (xd = term) then
2238 begin
2239 //FIXME!
2240 result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag);
2241 if (result <> nil) then
2242 begin
2243 if assigned(cb) then
2244 begin
2245 if cb(result, ptag, ax0, ay0, ax0, ay0) then
2246 begin
2247 ex := ax0;
2248 ey := ay0;
2249 end
2250 else
2251 begin
2252 result := nil;
2253 end;
2254 end
2255 else
2256 begin
2257 ex := ax0;
2258 ey := ay0;
2259 end;
2260 end;
2261 exit;
2262 end;
2264 prevx := xptr^+minx;
2265 prevy := yptr^+miny;
2266 ( *
2267 // move coords
2268 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2269 xd += stx;
2270 // done?
2271 if (xd = term) then exit;
2272 * )
2274 {$IF DEFINED(D2F_DEBUG)}
2275 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2276 {$ENDIF}
2277 // DON'T DO THIS! loop will take care of that
2278 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2279 //ccidx := mGrid[lastGA];
2281 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2282 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2283 {$ENDIF}
2285 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2287 if mInQuery then raise Exception.Create('recursive queries aren''t supported');
2288 mInQuery := true;
2290 // increase query counter
2291 Inc(mLastQuery);
2292 if (mLastQuery = 0) then
2293 begin
2294 // just in case of overflow
2295 mLastQuery := 1;
2296 for f := 0 to High(mProxies) do mProxies[f].mQueryMark := 0;
2297 end;
2298 lq := mLastQuery;
2300 {$IFDEF GRID_USE_ORTHO_ACCEL}
2301 // if this is strict horizontal/vertical trace, use optimized codepath
2302 if (ax0 = ax1) or (ay0 = ay1) then
2303 begin
2304 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2305 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2306 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2307 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2308 hopt := (ay0 = ay1); // horizontal?
2309 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2310 {$IF DEFINED(D2F_DEBUG)}
2311 if dbgShowTraceLog then e_LogWritefln('optimized htrace; wklen=%d', [wklen]);
2312 {$ENDIF}
2313 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2314 // one of those will never change
2315 x := xptr^+minx;
2316 y := yptr^+miny;
2317 while (wklen > 0) do
2318 begin
2319 {$IF DEFINED(D2F_DEBUG)}
2320 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2321 {$ENDIF}
2322 // new tile?
2323 if (ga <> lastGA) then
2324 begin
2325 lastGA := ga;
2326 ccidx := mGrid[lastGA];
2327 // convert coords to map (to avoid ajdusting coords inside the loop)
2328 if hopt then x := xptr^+minx else y := yptr^+miny;
2329 while (ccidx <> -1) do
2330 begin
2331 cc := @mCells[ccidx];
2332 for f := 0 to GridCellBucketSize-1 do
2333 begin
2334 if (cc.bodies[f] = -1) then break;
2335 px := @mProxies[cc.bodies[f]];
2336 ptag := px.mTag;
2337 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and
2338 // constant coord should be inside
2339 ((hopt and (y >= px.y0) and (y <= px.y1)) or
2340 ((not hopt) and (x >= px.x0) and (x <= px.x1))) then
2341 begin
2342 px.mQueryMark := lq; // mark as processed
2343 // inside the proxy?
2344 if (hopt and (x > px.x0) and (x < px.x1)) or
2345 ((not hopt) and (y > px.y0) and (y < px.y1)) then
2346 begin
2347 // setup prev[xy]
2348 if assigned(cb) then
2349 begin
2350 if cb(px.mObj, ptag, x, y, x, y) then
2351 begin
2352 result := px.mObj;
2353 ex := x;
2354 ey := y;
2355 mInQuery := false;
2356 exit;
2357 end;
2358 end
2359 else
2360 begin
2361 distSq := distanceSq(ax0, ay0, x, y);
2362 {$IF DEFINED(D2F_DEBUG)}
2363 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]);
2364 {$ENDIF}
2365 if (distSq < lastDistSq) then
2366 begin
2367 ex := x;
2368 ey := y;
2369 result := px.mObj;
2370 mInQuery := false;
2371 exit;
2372 end;
2373 end;
2374 continue;
2375 end;
2376 // remember this hitpoint if it is nearer than an old one
2377 // setup prev[xy]
2378 if hopt then
2379 begin
2380 // horizontal trace
2381 prevy := y;
2382 y := yptr^+miny;
2383 if (stx < 0) then
2384 begin
2385 // going left
2386 if (x < px.x1) then continue; // not on the right edge
2387 x := px.x1;
2388 prevx := x+1;
2389 end
2390 else
2391 begin
2392 // going right
2393 if (x > px.x0) then continue; // not on the left edge
2394 x := px.x0;
2395 prevx := x-1;
2396 end;
2397 end
2398 else
2399 begin
2400 // vertical trace
2401 prevx := x;
2402 x := xptr^+minx;
2403 if (stx < 0) then
2404 begin
2405 // going up
2406 if (y < px.y1) then continue; // not on the bottom edge
2407 y := px.y1;
2408 prevy := x+1;
2409 end
2410 else
2411 begin
2412 // going down
2413 if (y > px.y0) then continue; // not on the top edge
2414 y := px.y0;
2415 prevy := y-1;
2416 end;
2417 end;
2418 if assigned(cb) then
2419 begin
2420 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2421 begin
2422 result := px.mObj;
2423 ex := prevx;
2424 ey := prevy;
2425 mInQuery := false;
2426 exit;
2427 end;
2428 end
2429 else
2430 begin
2431 distSq := distanceSq(ax0, ay0, prevx, prevy);
2432 {$IF DEFINED(D2F_DEBUG)}
2433 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]);
2434 {$ENDIF}
2435 if (distSq < lastDistSq) then
2436 begin
2437 wasHit := true;
2438 lastDistSq := distSq;
2439 ex := prevx;
2440 ey := prevy;
2441 lastObj := px.mObj;
2442 end;
2443 end;
2444 end;
2445 end;
2446 // next cell
2447 ccidx := cc.next;
2448 end;
2449 if wasHit and not assigned(cb) then begin result := lastObj; mInQuery := false; exit; end;
2450 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2451 end;
2452 // skip to next tile
2453 if hopt then
2454 begin
2455 if (stx > 0) then
2456 begin
2457 // to the right
2458 wkstep := ((xptr^ or (mTileSize-1))+1)-xptr^;
2459 {$IF DEFINED(D2F_DEBUG)}
2460 if dbgShowTraceLog then e_LogWritefln(' right step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2461 {$ENDIF}
2462 if (wkstep >= wklen) then break;
2463 Inc(xptr^, wkstep);
2464 Inc(ga);
2465 end
2466 else
2467 begin
2468 // to the left
2469 wkstep := xptr^-((xptr^ and (not (mTileSize-1)))-1);
2470 {$IF DEFINED(D2F_DEBUG)}
2471 if dbgShowTraceLog then e_LogWritefln(' left step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2472 {$ENDIF}
2473 if (wkstep >= wklen) then break;
2474 Dec(xptr^, wkstep);
2475 Dec(ga);
2476 end;
2477 end
2478 else
2479 begin
2480 if (stx > 0) then
2481 begin
2482 // to the down
2483 wkstep := ((yptr^ or (mTileSize-1))+1)-yptr^;
2484 {$IF DEFINED(D2F_DEBUG)}
2485 if dbgShowTraceLog then e_LogWritefln(' down step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2486 {$ENDIF}
2487 if (wkstep >= wklen) then break;
2488 Inc(yptr^, wkstep);
2489 Inc(ga, mWidth);
2490 end
2491 else
2492 begin
2493 // to the up
2494 wkstep := yptr^-((yptr^ and (not (mTileSize-1)))-1);
2495 {$IF DEFINED(D2F_DEBUG)}
2496 if dbgShowTraceLog then e_LogWritefln(' up step: wklen=%d; wkstep=%d', [wklen, wkstep]);
2497 {$ENDIF}
2498 if (wkstep >= wklen) then break;
2499 Dec(yptr^, wkstep);
2500 Dec(ga, mWidth);
2501 end;
2502 end;
2503 Dec(wklen, wkstep);
2504 end;
2505 // we can travel less than one cell
2506 if wasHit and not assigned(cb) then result := lastObj else begin ex := ax1; ey := ay1; end;
2507 mInQuery := false;
2508 exit;
2509 end;
2510 {$ENDIF}
2512 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2513 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2514 {$ENDIF}
2516 //e_LogWritefln('*********************', []);
2517 ccidx := -1;
2518 // can omit checks
2519 while (xd <> term) do
2520 begin
2521 // check cell(s)
2522 {$IF DEFINED(D2F_DEBUG)}
2523 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2524 {$ENDIF}
2525 // new tile?
2526 ga := (yptr^ div mTileSize)*gw+(xptr^ div mTileSize);
2527 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2528 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);
2529 {$ENDIF}
2530 if (ga <> lastGA) then
2531 begin
2532 // yes
2533 {$IF DEFINED(D2F_DEBUG)}
2534 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2535 {$ENDIF}
2536 if (ccidx <> -1) then
2537 begin
2538 // signal cell completion
2539 if assigned(cb) then
2540 begin
2541 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2542 end
2543 else if wasHit then
2544 begin
2545 result := lastObj;
2546 mInQuery := false;
2547 exit;
2548 end;
2549 end;
2550 lastGA := ga;
2551 ccidx := mGrid[lastGA];
2552 end;
2553 // has something to process in this tile?
2554 if (ccidx <> -1) then
2555 begin
2556 // process cell
2557 curci := ccidx;
2558 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2559 // convert coords to map (to avoid ajdusting coords inside the loop)
2560 x := xptr^+minx;
2561 y := yptr^+miny;
2562 // process cell list
2563 while (curci <> -1) do
2564 begin
2565 cc := @mCells[curci];
2566 for f := 0 to GridCellBucketSize-1 do
2567 begin
2568 if (cc.bodies[f] = -1) then break;
2569 px := @mProxies[cc.bodies[f]];
2570 ptag := px.mTag;
2571 if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
2572 begin
2573 // can we process this proxy?
2574 if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then
2575 begin
2576 px.mQueryMark := lq; // mark as processed
2577 if assigned(cb) then
2578 begin
2579 if cb(px.mObj, ptag, x, y, prevx, prevy) then
2580 begin
2581 result := px.mObj;
2582 ex := prevx;
2583 ey := prevy;
2584 mInQuery := false;
2585 exit;
2586 end;
2587 end
2588 else
2589 begin
2590 // remember this hitpoint if it is nearer than an old one
2591 distSq := distanceSq(ax0, ay0, prevx, prevy);
2592 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2593 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);
2594 {$ENDIF}
2595 if (distSq < lastDistSq) then
2596 begin
2597 wasHit := true;
2598 lastDistSq := distSq;
2599 ex := prevx;
2600 ey := prevy;
2601 lastObj := px.mObj;
2602 end;
2603 end;
2604 end
2605 else
2606 begin
2607 // this is possibly interesting proxy, set "has more to check" flag
2608 hasUntried := true;
2609 end;
2610 end;
2611 end;
2612 // next cell
2613 curci := cc.next;
2614 end;
2615 // still has something interesting in this cell?
2616 if not hasUntried then
2617 begin
2618 // nope, don't process this cell anymore; signal cell completion
2619 ccidx := -1;
2620 if assigned(cb) then
2621 begin
2622 if cb(nil, 0, x, y, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2623 end
2624 else if wasHit then
2625 begin
2626 result := lastObj;
2627 mInQuery := false;
2628 exit;
2629 end;
2630 end;
2631 end;
2632 if (ccidx = -1) then
2633 begin
2634 // move to cell edge, as we have nothing to trace here anymore
2635 if (stx < 0) then xdist := xd and (not (mTileSize-1)) else xdist := xd or (mTileSize-1);
2636 if (sty < 0) then ydist := yd and (not (mTileSize-1)) else ydist := yd or (mTileSize-1);
2637 //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]);
2638 while (xd <> xdist) and (yd <> ydist) do
2639 begin
2640 // step
2641 xd += stx;
2642 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2643 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2644 if (xd = term) then break;
2645 end;
2646 //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]);
2647 if (xd = term) then break;
2648 end;
2649 //putPixel(xptr^, yptr^);
2650 // move coords
2651 prevx := xptr^+minx;
2652 prevy := yptr^+miny;
2653 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2654 xd += stx;
2655 end;
2656 // we can travel less than one cell
2657 if wasHit and not assigned(cb) then
2658 begin
2659 result := lastObj;
2660 end
2661 else
2662 begin
2663 ex := ax1; // why not?
2664 ey := ay1; // why not?
2665 end;
2667 mInQuery := false;
2668 end;
2669 *)