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 const
35 type
39 public
40 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
41 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
47 private
48 const
51 public
52 type
55 private
62 private
74 public
89 private
90 type
99 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
101 private
102 //mTileSize: Integer;
106 public
109 type
111 private
115 public
122 private
136 public
138 {$IF DEFINED(D2F_DEBUG)}
140 {$ENDIF}
142 private
162 public
163 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
166 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
175 // `false` if `body` is surely invalid
180 //WARNING: don't modify grid while any query is in progress (no checks are made!)
181 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
182 // no callback: return `true` on the first hit
183 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
185 //WARNING: don't modify grid while any query is in progress (no checks are made!)
186 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
187 // no callback: return object on the first hit or nil
188 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
192 //WARNING: don't modify grid while any query is in progress (no checks are made!)
193 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
194 // cb with `(nil)` will be called before processing new tile
195 // no callback: return object of the nearest hit or nil
196 // if `inverted` is true, trace will register bodies *exluding* tagmask
197 //WARNING: don't change tags in callbacks here!
198 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
199 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
201 //WARNING: don't modify grid while any query is in progress (no checks are made!)
202 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
203 // cb with `(nil)` will be called before processing new tile
204 // no callback: return object of the nearest hit or nil
205 // if `inverted` is true, trace will register bodies *exluding* tagmask
206 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
207 //WARNING: don't change tags in callbacks here!
208 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
209 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
211 // return `false` if we're still inside at the end
212 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
213 // `true`: endpoint will point at the last "inside" pixel
214 // `false`: endpoint will be (ax1, ay1)
215 //WARNING: don't change tags in callbacks here!
216 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
218 //WARNING: don't modify grid while any query is in progress (no checks are made!)
219 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
220 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
221 //WARNING: don't change tags in callbacks here!
222 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
224 // trace box with the given velocity; return object hit (if any)
225 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
226 //WARNING: don't change tags in callbacks here!
227 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
229 // debug
234 public
235 //WARNING! no sanity checks!
247 type
248 // common structure for all line tracers
250 public
253 private
261 public
262 // call `setyp` after this
267 // this will use `w[xy][01]` to clip coords
268 // return `false` if the whole line was clipped away
269 // on `true`, you should process first point, and go on
272 // call this *after* doing a step
273 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
276 // as you will prolly call `done()` after doing a step anyway, this will do it for you
277 // move to next point, return `true` when the line is complete (i.e. you should stop)
280 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
285 public
286 // current coords
293 //function minInt (a, b: Integer): Integer; inline;
294 //function maxInt (a, b: Integer): Integer; inline;
297 implementation
299 uses
303 // ////////////////////////////////////////////////////////////////////////// //
304 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
305 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
306 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
307 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
310 // ////////////////////////////////////////////////////////////////////////// //
312 begin
317 begin
318 // clip rectange
326 var
328 begin
329 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
333 begin
335 end
336 else
337 begin
346 // check for ortho lines
348 begin
349 // horizontal
356 end
358 begin
359 // vertical
366 end
367 else
368 begin
369 // diagonal
371 begin
372 // horizontal
376 end
377 else
378 begin
379 // vertical
395 // true: done
397 begin
399 begin
403 end
404 else
405 begin
414 // true: done
416 var
420 begin
425 // strictly horizontal?
427 begin
428 // only xd
430 begin
431 // xd: to left edge
434 end
435 else
436 begin
437 // xd: to right edge
443 exit;
446 // strictly vertical?
448 begin
449 // only xd
451 begin
452 // yd: to top edge
455 end
456 else
457 begin
458 // yd: to bottom edge
464 exit;
467 // diagonal
469 // calculate xwalk
471 begin
474 end
475 else
476 begin
481 // calculate ywalk
483 begin
486 end
487 else
488 begin
493 {
494 while (xd <> ex) and (yd <> ey) do
495 begin
496 if horiz then
497 begin
498 xd += stx;
499 err += errinc;
500 if (err >= 0) then begin err -= errmax; yd += sty; end;
501 end
502 else
503 begin
504 yd += sty;
505 err += errinc;
506 if (err >= 0) then begin err -= errmax; xd += stx; end;
507 end;
508 Dec(stleft);
509 if (stleft < 1) then begin result := true; exit; end;
510 end;
511 }
515 begin
516 // in which dir we want to walk?
520 begin
523 begin
527 end
528 else
529 begin
532 begin
537 // check for walk completion
546 // ////////////////////////////////////////////////////////////////////////// //
547 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
548 begin
561 begin
566 begin
571 begin
576 begin
581 begin
586 begin
591 // ////////////////////////////////////////////////////////////////////////// //
592 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
593 begin
602 begin
604 begin
606 begin
610 exit;
620 begin
625 // ////////////////////////////////////////////////////////////////////////// //
626 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
627 var
629 begin
631 {$IF DEFINED(D2F_DEBUG)}
633 {$ENDIF}
634 {
635 if aTileSize < 1 then aTileSize := 1;
636 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
637 mTileSize := aTileSize;
638 }
649 // init free list
651 begin
657 // init grid
659 // init proxies
667 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
672 begin
680 // ////////////////////////////////////////////////////////////////////////// //
682 var
684 begin
687 begin
691 begin
697 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);
702 var
705 begin
708 begin
711 begin
714 begin
716 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
718 // next cell
726 var
729 begin
737 begin
740 begin
742 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
744 // next cell
750 // ////////////////////////////////////////////////////////////////////////// //
751 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
752 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
756 begin
757 // fix coords
765 begin
767 begin
770 end
771 else
772 begin
781 begin
783 begin
786 end
787 else
788 begin
796 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
797 begin
799 begin
802 end
803 else
804 begin
815 // ////////////////////////////////////////////////////////////////////////// //
817 begin
818 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
823 begin
825 begin
827 begin
829 end
830 else
831 begin
839 begin
844 // ////////////////////////////////////////////////////////////////////////// //
846 var
849 begin
851 begin
852 // no free cells, want more
856 begin
868 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
873 begin
875 begin
877 begin
888 // ////////////////////////////////////////////////////////////////////////// //
889 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
890 var
893 begin
895 begin
896 // no free proxies, resize list
903 // get one from list
908 // add to used list
910 // statistics
916 begin
918 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
919 // add to free list
927 // ////////////////////////////////////////////////////////////////////////// //
928 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
929 var
933 begin
936 // fix coords
939 // go on
948 // clip rect
954 // do the work
956 begin
958 begin
966 // ////////////////////////////////////////////////////////////////////////// //
968 var
973 begin
975 // add body to the given grid cell
978 begin
979 {$IF DEFINED(D2F_DEBUG)}
982 begin
985 begin
987 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
991 {$ENDIF}
994 begin
996 // check "has room" flag
998 begin
999 // can add here
1001 begin
1003 begin
1006 exit;
1011 // no room, go to next cell in list (if there is any)
1014 // no room in cells, add new cell to list
1016 // either no room, or no cell at all
1026 // assume that we cannot have one object added to bucket twice
1028 var
1032 begin
1034 // find and remove cell
1038 begin
1041 begin
1043 begin
1044 // i found her!
1046 begin
1047 // this cell contains no elements, remove it
1050 exit;
1052 // remove element from bucket
1054 begin
1059 exit;
1068 // ////////////////////////////////////////////////////////////////////////// //
1069 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1070 begin
1073 //insertInternal(result);
1079 var
1081 begin
1084 //removeInternal(body);
1090 // ////////////////////////////////////////////////////////////////////////// //
1092 var
1095 begin
1102 {$IF DEFINED(D2F_DEBUG_MOVER)}
1103 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);
1104 {$ENDIF}
1106 // map -> grid
1111 // did any corner crossed tile boundary?
1116 begin
1117 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1118 //removeInternal(body);
1124 //insertInternal(body);
1126 end
1127 else
1128 begin
1137 //TODO: optimize for horizontal/vertical moves
1139 var
1147 begin
1149 // check if tile coords was changed
1154 // map -> grid
1159 // check for heavy work
1170 {$IF DEFINED(D2F_DEBUG_MOVER)}
1171 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);
1172 {$ENDIF}
1174 begin
1175 // crossed tile boundary, do heavy work
1178 // cycle with old rect, remove body where it is necessary
1179 // optimized for horizontal moves
1180 {$IF DEFINED(D2F_DEBUG_MOVER)}
1181 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);
1182 {$ENDIF}
1183 // remove stale marks
1186 begin
1191 {$IF DEFINED(D2F_DEBUG_MOVER)}
1193 {$ENDIF}
1195 begin
1197 begin
1198 // this column is completely outside of new rect
1200 begin
1201 {$IF DEFINED(D2F_DEBUG_MOVER)}
1203 {$ENDIF}
1206 end
1207 else
1208 begin
1209 // heavy checks
1211 begin
1213 begin
1214 {$IF DEFINED(D2F_DEBUG_MOVER)}
1216 {$ENDIF}
1223 // cycle with new rect, add body where it is necessary
1226 begin
1231 {$IF DEFINED(D2F_DEBUG_MOVER)}
1233 {$ENDIF}
1235 begin
1237 begin
1238 // this column is completely outside of old rect
1240 begin
1241 {$IF DEFINED(D2F_DEBUG_MOVER)}
1243 {$ENDIF}
1246 end
1247 else
1248 begin
1249 // heavy checks
1251 begin
1253 begin
1254 {$IF DEFINED(D2F_DEBUG_MOVER)}
1256 {$ENDIF}
1263 // done
1264 end
1265 else
1266 begin
1267 {$IF DEFINED(D2F_DEBUG_MOVER)}
1268 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);
1269 {$ENDIF}
1271 // update coordinates
1278 var
1281 begin
1283 // check if tile coords was changed
1289 {$IF DEFINED(D2F_DEBUG_MOVER)}
1290 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);
1291 {$ENDIF}
1294 begin
1295 // crossed tile boundary, do heavy work
1296 //removeInternal(body);
1300 //insertInternal(body);
1302 end
1303 else
1304 begin
1305 // nothing to do with the grid, just fix size
1312 // ////////////////////////////////////////////////////////////////////////// //
1314 var
1316 begin
1319 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1324 // ////////////////////////////////////////////////////////////////////////// //
1325 // no callback: return `true` on the first hit
1326 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1327 var
1334 begin
1340 {$IF DEFINED(D2F_DEBUG_XXQ)}
1342 {$ENDIF}
1344 // make coords (0,0)-based
1351 {$IF DEFINED(D2F_DEBUG_XXQ)}
1352 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);
1353 {$ENDIF}
1355 // restore coords
1359 // increase query counter
1362 begin
1363 // just in case of overflow
1369 {$IF DEFINED(D2F_DEBUG_XXQ)}
1370 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1371 {$ENDIF}
1374 begin
1375 {$IF DEFINED(D2F_DEBUG_XXQ)}
1377 {$ENDIF}
1380 begin
1383 {$IF DEFINED(D2F_DEBUG_XXQ)}
1384 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);
1385 {$ENDIF}
1386 // shit. has to do it this way, so i can change tag in callback
1388 begin
1393 begin
1395 begin
1397 begin
1400 exit;
1402 end
1403 else
1404 begin
1407 exit;
1417 // ////////////////////////////////////////////////////////////////////////// //
1418 // no callback: return `true` on the first hit
1419 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1420 var
1432 begin
1441 // fix coords
1456 // clip rect
1463 // has something to do
1467 // increase query counter
1470 begin
1471 // just in case of overflow
1475 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1478 // go on
1480 begin
1482 begin
1483 // process cells
1486 begin
1489 begin
1492 // shit! has to do it this way, so i can change tag in callback
1501 begin
1503 end
1504 else
1505 begin
1508 exit;
1520 // ////////////////////////////////////////////////////////////////////////// //
1521 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1522 var
1533 //px0, py0, px1, py1: Integer;
1534 begin
1545 // make query coords (0,0)-based
1557 // increase query counter
1560 begin
1561 // just in case of overflow
1567 repeat
1569 // check tile
1571 // process cells
1573 begin
1576 begin
1581 begin
1584 begin
1587 exit;
1591 // next cell
1594 // done processing cells, move to next tile
1601 // ////////////////////////////////////////////////////////////////////////// //
1602 // trace box with the given velocity; return object hit (if any)
1603 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1604 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1605 var
1616 begin
1630 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1636 // just in case
1642 // increase query counter
1645 begin
1646 // just in case of overflow
1653 begin
1655 begin
1658 begin
1661 begin
1666 begin
1669 begin
1672 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1674 begin
1679 begin
1683 exit;
1688 // next cell
1695 begin
1698 // just in case, compensate for floating point inexactness
1699 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1700 begin
1710 // ////////////////////////////////////////////////////////////////////////// //
1711 {.$DEFINE D2F_DEBUG_OTR}
1712 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1713 var
1724 {$IF DEFINED(D2F_DEBUG_OTR)}
1726 {$ENDIF}
1727 begin
1741 // offset query coords to (0,0)-based
1748 begin
1750 // vertical
1752 begin
1753 // down
1755 //if (ay0 < 0) then ay0 := 0;
1759 end
1760 else
1761 begin
1762 // up
1764 //if (ay1 < 0) then ay1 := 0;
1769 // check tile
1771 begin
1777 begin
1780 begin
1786 begin
1787 // bound c0 and c1 to cell
1790 // fill the thing
1791 {$IF DEFINED(D2F_DEBUG_OTR)}
1792 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)]);
1793 {$ENDIF}
1794 //assert(c0 <= c1);
1798 // next cell
1801 {$IF DEFINED(D2F_DEBUG_OTR)}
1802 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1806 {$ENDIF}
1807 // now go till we hit cell boundary or empty space
1809 begin
1810 // up
1812 begin
1813 {$IF DEFINED(D2F_DEBUG_OTR)}
1814 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1815 {$ENDIF}
1819 {$IF DEFINED(D2F_DEBUG_OTR)}
1820 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1821 {$ENDIF}
1823 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1824 end
1825 else
1826 begin
1827 // down
1833 end
1834 else
1835 begin
1836 // horizontal
1842 // ////////////////////////////////////////////////////////////////////////// //
1843 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1844 var
1846 begin
1851 // no callback: return `true` on the nearest hit
1852 // you are not supposed to understand this
1853 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1854 var
1869 begin
1879 // make query coords (0,0)-based
1890 {$IF DEFINED(D2F_DEBUG)}
1891 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1892 {$ENDIF}
1897 // increase query counter
1900 begin
1901 // just in case of overflow
1907 repeat
1909 {$IF DEFINED(D2F_DEBUG)}
1911 {$ENDIF}
1912 // check tile
1914 // process cells
1917 begin
1920 begin
1925 begin
1928 begin
1931 // get adjusted proxy coords
1936 {$IF DEFINED(D2F_DEBUG)}
1937 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1938 {$ENDIF}
1939 // inside?
1941 begin
1942 // oops
1947 {$IF DEFINED(D2F_DEBUG)}
1949 {$ENDIF}
1950 exit;
1952 // do line-vs-aabb test
1954 begin
1955 // hit detected
1957 {$IF DEFINED(D2F_DEBUG)}
1958 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1959 {$ENDIF}
1961 begin
1971 // next cell
1974 // done processing cells; exit if we registered a hit
1975 // next cells can't have better candidates, obviously
1978 // move to next tile
1985 // ////////////////////////////////////////////////////////////////////////// //
1986 // no callback: return `true` on the nearest hit
1987 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1988 var
1990 begin
1995 // no callback: return `true` on the nearest hit
1996 // you are not supposed to understand this
1997 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1998 var
2024 //swapped: Boolean = false; // true: xd is yd, and vice versa
2025 // horizontal walker
2026 {$IFDEF GRID_USE_ORTHO_ACCEL}
2028 //wksign: Integer;
2030 {$ENDIF}
2031 // skipper
2033 begin
2042 begin
2045 begin
2048 exit;
2060 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2061 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);
2062 {$ENDIF}
2069 // offset query coords to (0,0)-based
2075 // clip rectange
2081 // horizontal setup
2083 begin
2084 // from left to right
2087 end
2088 else
2089 begin
2090 // from right to left
2100 // vertical setup
2102 begin
2103 // from top to bottom
2106 end
2107 else
2108 begin
2109 // from bottom to top
2123 begin
2124 //swapped := true;
2133 end
2134 else
2135 begin
2149 begin
2150 // clip at top
2156 begin
2159 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2166 begin
2167 // clip at left
2178 begin
2179 // clip at bottom
2189 //if (term = xd) then exit; // this is the only point, get out of here
2195 // first move, to skip starting point
2196 // DON'T DO THIS! loop will take care of that
2198 begin
2199 //FIXME!
2202 begin
2204 begin
2206 begin
2209 end
2210 else
2211 begin
2214 end
2215 else
2216 begin
2221 exit;
2226 (*
2227 // move coords
2228 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2229 xd += stx;
2230 // done?
2231 if (xd = term) then exit;
2232 *)
2234 {$IF DEFINED(D2F_DEBUG)}
2235 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2236 {$ENDIF}
2237 // DON'T DO THIS! loop will take care of that
2238 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2239 //ccidx := mGrid[lastGA];
2241 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2242 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2243 {$ENDIF}
2245 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2250 // increase query counter
2253 begin
2254 // just in case of overflow
2260 {$IFDEF GRID_USE_ORTHO_ACCEL}
2261 // if this is strict horizontal/vertical trace, use optimized codepath
2263 begin
2264 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2265 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2266 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2267 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2269 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2270 {$IF DEFINED(D2F_DEBUG)}
2272 {$ENDIF}
2274 // one of those will never change
2278 begin
2279 {$IF DEFINED(D2F_DEBUG)}
2280 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2281 {$ENDIF}
2282 // new tile?
2284 begin
2287 // convert coords to map (to avoid ajdusting coords inside the loop)
2290 begin
2293 begin
2298 // constant coord should be inside
2301 begin
2303 // inside the proxy?
2306 begin
2307 // setup prev[xy]
2309 begin
2311 begin
2316 exit;
2318 end
2319 else
2320 begin
2322 {$IF DEFINED(D2F_DEBUG)}
2323 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]);
2324 {$ENDIF}
2326 begin
2331 exit;
2334 continue;
2336 // remember this hitpoint if it is nearer than an old one
2337 // setup prev[xy]
2339 begin
2340 // horizontal trace
2344 begin
2345 // going left
2349 end
2350 else
2351 begin
2352 // going right
2357 end
2358 else
2359 begin
2360 // vertical trace
2364 begin
2365 // going up
2369 end
2370 else
2371 begin
2372 // going down
2379 begin
2381 begin
2386 exit;
2388 end
2389 else
2390 begin
2392 {$IF DEFINED(D2F_DEBUG)}
2393 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]);
2394 {$ENDIF}
2396 begin
2406 // next cell
2410 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2412 // skip to next tile
2414 begin
2416 begin
2417 // to the right
2419 {$IF DEFINED(D2F_DEBUG)}
2421 {$ENDIF}
2425 end
2426 else
2427 begin
2428 // to the left
2430 {$IF DEFINED(D2F_DEBUG)}
2432 {$ENDIF}
2437 end
2438 else
2439 begin
2441 begin
2442 // to the down
2444 {$IF DEFINED(D2F_DEBUG)}
2446 {$ENDIF}
2450 end
2451 else
2452 begin
2453 // to the up
2455 {$IF DEFINED(D2F_DEBUG)}
2457 {$ENDIF}
2465 // we can travel less than one cell
2468 exit;
2470 {$ENDIF}
2472 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2473 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2474 {$ENDIF}
2476 //e_LogWritefln('*********************', []);
2478 // can omit checks
2480 begin
2481 // check cell(s)
2482 {$IF DEFINED(D2F_DEBUG)}
2483 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2484 {$ENDIF}
2485 // new tile?
2487 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2488 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);
2489 {$ENDIF}
2491 begin
2492 // yes
2493 {$IF DEFINED(D2F_DEBUG)}
2494 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2495 {$ENDIF}
2497 begin
2498 // signal cell completion
2500 begin
2501 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2502 end
2504 begin
2507 exit;
2513 // has something to process in this tile?
2515 begin
2516 // process cell
2518 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2519 // convert coords to map (to avoid ajdusting coords inside the loop)
2522 // process cell list
2524 begin
2527 begin
2532 begin
2533 // can we process this proxy?
2535 begin
2538 begin
2540 begin
2545 exit;
2547 end
2548 else
2549 begin
2550 // remember this hitpoint if it is nearer than an old one
2552 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2553 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);
2554 {$ENDIF}
2556 begin
2564 end
2565 else
2566 begin
2567 // this is possibly interesting proxy, set "has more to check" flag
2572 // next cell
2575 // still has something interesting in this cell?
2577 begin
2578 // nope, don't process this cell anymore; signal cell completion
2581 begin
2583 end
2585 begin
2588 exit;
2593 begin
2594 // move to cell edge, as we have nothing to trace here anymore
2597 //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]);
2599 begin
2600 // step
2603 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2606 //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]);
2609 //putPixel(xptr^, yptr^);
2610 // move coords
2616 // we can travel less than one cell
2618 begin
2620 end
2621 else
2622 begin