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}
26 interface
28 const
31 type
35 public
36 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
37 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
43 private
44 const
47 public
48 type
51 private
58 private
70 public
85 private
86 type
95 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
97 private
98 //mTileSize: Integer;
102 public
105 type
107 private
111 public
118 private
132 public
134 {$IF DEFINED(D2F_DEBUG)}
136 {$ENDIF}
138 private
161 public
162 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
165 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
174 // `false` if `body` is surely invalid
179 //WARNING: don't modify grid while any query is in progress (no checks are made!)
180 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
181 // no callback: return `true` on the first hit
182 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
184 //WARNING: don't modify grid while any query is in progress (no checks are made!)
185 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
186 // no callback: return object on the first hit or nil
187 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
191 //WARNING: don't modify grid while any query is in progress (no checks are made!)
192 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
193 // cb with `(nil)` will be called before processing new tile
194 // no callback: return object of the nearest hit or nil
195 // if `inverted` is true, trace will register bodies *exluding* tagmask
196 //WARNING: don't change tags in callbacks here!
197 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
198 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
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 // cb with `(nil)` will be called before processing new tile
203 // no callback: return object of the nearest hit or nil
204 // if `inverted` is true, trace will register bodies *exluding* tagmask
205 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
206 //WARNING: don't change tags in callbacks here!
207 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
208 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
210 // return `false` if we're still inside at the end
211 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
212 // `true`: endpoint will point at the last "inside" pixel
213 // `false`: endpoint will be (ax1, ay1)
214 //WARNING: don't change tags in callbacks here!
215 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
217 //WARNING: don't modify grid while any query is in progress (no checks are made!)
218 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
219 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
220 //WARNING: don't change tags in callbacks here!
221 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
223 // trace box with the given velocity; return object hit (if any)
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 traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
228 // debug
233 public
234 //WARNING! no sanity checks!
246 type
247 // common structure for all line tracers
249 public
252 private
259 //xptr, yptr: PInteger;
262 public
263 // call `setyp` after this
268 // this will use `w[xy][01]` to clip coords
269 // return `false` if the whole line was clipped away
270 // on `true`, you should process first point, and go on
273 // call this *after* doing a step
274 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
277 // as you will prolly call `done()` after doing a step anyway, this will do it for you
278 // move to next point, return `true` when the line is complete (i.e. you should stop)
281 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
284 // hack for line-vs-aabb; NOT PROPERLY TESTED!
287 // current coords
293 // move directions; always [-1..1] (can be zero!)
299 // you are not supposed to understand this
300 // returns `true` if there is an intersection, and enter coords
301 // enter coords will be equal to (x0, y0) if starting point is inside the box
302 // if result is `false`, `inx` and `iny` are undefined
303 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
305 // sweep two AABB's to see if and when they are overlapping
306 // returns `true` if collision was detected (but boxes doesn't overlap)
307 // u1 and u1 has no sense if no collision was detected
308 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
309 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
310 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
311 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
312 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
318 //function minInt (a, b: Integer): Integer; inline;
319 //function maxInt (a, b: Integer): Integer; inline;
322 implementation
324 uses
328 // ////////////////////////////////////////////////////////////////////////// //
329 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
330 procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
331 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
332 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
334 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
337 // ////////////////////////////////////////////////////////////////////////// //
339 begin
344 begin
345 // clip rectange
355 begin
361 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
363 var
365 begin
368 //writeln('stx=', stx, '; sty=', sty);
370 // ortho?
372 begin
373 // only xd
376 begin
377 // xd: to left edge
380 exit;
381 end
382 else
383 begin
384 // xd: to right edge
387 exit;
393 // not ortho
396 //FIXME: do some math to avoid single-stepping
398 begin
399 // xd: to left edge
403 end
404 else
405 begin
406 // xd: to right edge
412 //writeln('xd=', xd, '; yd=', yd, '; ex=', ex, '; ey=', ey, '; term=', term, '; wklen=', wklen);
415 begin
416 // do step
426 // NOT TESTED!
428 begin
429 //writeln('e=', e, '; dx2=', dx2, '; dy2=', dy2);
431 begin
434 end
435 else
436 begin
442 function TLineWalker.x (): Integer; inline; begin if xyswapped then result := yd else result := xd; end;
443 function TLineWalker.y (): Integer; inline; begin if xyswapped then result := xd else result := yd; end;
444 procedure TLineWalker.getXY (out ox, oy: Integer); inline; begin if xyswapped then begin ox := yd; oy := xd; end else begin ox := xd; oy := yd; end; end;
446 function TLineWalker.dx (): Integer; inline; begin if xyswapped then result := stx else result := sty; end;
447 function TLineWalker.dy (): Integer; inline; begin if xyswapped then result := sty else result := stx; end;
450 procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
451 var
456 begin
460 // horizontal setup
462 begin
463 // from left to right
466 end
467 else
468 begin
469 // from right to left
479 // vertical setup
481 begin
482 // from top to bottom
485 end
486 else
487 begin
488 // from bottom to top
502 begin
504 //xptr := @yd;
505 //yptr := @xd;
512 end
513 else
514 begin
515 //xptr := @xd;
516 //yptr := @yd;
528 begin
529 // clip at top
535 begin
538 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
545 begin
546 // clip at left
557 begin
558 // clip at bottom
568 //if (term = xd) then exit; // this is the only point, get out of here
578 // ////////////////////////////////////////////////////////////////////////// //
579 // you are not supposed to understand this
580 // returns `true` if there is an intersection, and enter coords
581 // enter coords will be equal to (x0, y0) if starting point is inside the box
582 // if result is `false`, `inx` and `iny` are undefined
583 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
584 var
592 //!term: Integer;
596 begin
598 // why not
604 begin
605 // check this point
607 exit;
610 // check if staring point is inside the box
611 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
613 // clip rectange
619 // horizontal setup
621 begin
622 // from left to right
625 end
626 else
627 begin
628 // from right to left
638 // vertical setup
640 begin
641 // from top to bottom
644 end
645 else
646 begin
647 // from bottom to top
661 begin
670 end
671 else
672 begin
682 //!term := x1;
686 begin
687 // clip at top
693 begin
696 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
703 begin
704 // clip at left
714 (*
715 if (y1 > wy1) then
716 begin
717 // clip at bottom
718 temp := dx2*(wy1-y0)+dsx;
719 term := x0+temp div dy2;
720 rem := temp mod dy2;
721 if (rem = 0) then Dec(term);
722 end;
724 if (term > wx1) then term := wx1; // clip at right
726 Inc(term); // draw last point
727 //if (term = xd) then exit; // this is the only point, get out of here
728 *)
732 //!dx2 -= dy2;
740 // ////////////////////////////////////////////////////////////////////////// //
741 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
743 var
747 var
749 begin
753 begin
757 end
759 begin
766 begin
769 end
771 begin
779 var
782 begin
795 // check if they are overlapping right now (SAT)
796 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
800 // treat b as stationary, so invert v to get relative velocity
814 begin
820 // ////////////////////////////////////////////////////////////////////////// //
821 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
822 begin
835 begin
840 begin
845 begin
850 begin
855 begin
860 begin
865 // ////////////////////////////////////////////////////////////////////////// //
866 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
867 begin
876 begin
878 begin
880 begin
884 exit;
894 begin
899 // ////////////////////////////////////////////////////////////////////////// //
900 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
901 var
903 begin
905 {$IF DEFINED(D2F_DEBUG)}
907 {$ENDIF}
908 {
909 if aTileSize < 1 then aTileSize := 1;
910 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
911 mTileSize := aTileSize;
912 }
923 // init free list
925 begin
931 // init grid
933 // init proxies
941 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
946 begin
954 // ////////////////////////////////////////////////////////////////////////// //
956 var
958 begin
961 begin
965 begin
971 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]), MSG_NOTIFY);
976 var
979 begin
982 begin
985 begin
988 begin
990 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
992 // next cell
1000 var
1003 begin
1011 begin
1014 begin
1016 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
1018 // next cell
1024 // ////////////////////////////////////////////////////////////////////////// //
1025 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
1026 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
1030 begin
1031 // fix coords
1039 begin
1041 begin
1044 end
1045 else
1046 begin
1055 begin
1057 begin
1060 end
1061 else
1062 begin
1070 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
1071 begin
1073 begin
1076 end
1077 else
1078 begin
1089 // ////////////////////////////////////////////////////////////////////////// //
1091 begin
1092 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1097 begin
1099 begin
1101 begin
1103 end
1104 else
1105 begin
1113 begin
1118 // ////////////////////////////////////////////////////////////////////////// //
1120 var
1123 begin
1125 begin
1126 // no free cells, want more
1130 begin
1142 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1147 begin
1149 begin
1151 begin
1162 // ////////////////////////////////////////////////////////////////////////// //
1163 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1164 var
1167 begin
1169 begin
1170 // no free proxies, resize list
1177 // get one from list
1182 // add to used list
1184 // statistics
1190 begin
1192 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1193 // add to free list
1201 // ////////////////////////////////////////////////////////////////////////// //
1202 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1203 var
1206 begin
1209 // fix coords
1212 // go on
1216 //tsize := mTileSize;
1219 begin
1223 begin
1233 // ////////////////////////////////////////////////////////////////////////// //
1235 var
1240 begin
1242 // add body to the given grid cell
1245 begin
1246 {$IF DEFINED(D2F_DEBUG)}
1249 begin
1252 begin
1254 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1258 {$ENDIF}
1261 begin
1263 // check "has room" flag
1265 begin
1266 // can add here
1268 begin
1270 begin
1273 exit;
1278 // no room, go to next cell in list (if there is any)
1281 // no room in cells, add new cell to list
1283 // either no room, or no cell at all
1293 var
1295 begin
1302 // assume that we cannot have one object added to bucket twice
1304 var
1308 begin
1310 // find and remove cell
1314 begin
1317 begin
1319 begin
1320 // i found her!
1322 begin
1323 // this cell contains no elements, remove it
1326 exit;
1328 // remove element from bucket
1330 begin
1335 exit;
1344 var
1346 begin
1353 // ////////////////////////////////////////////////////////////////////////// //
1354 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1355 begin
1363 begin
1370 // ////////////////////////////////////////////////////////////////////////// //
1372 var
1375 begin
1382 {$IF DEFINED(D2F_DEBUG_MOVER)}
1383 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);
1384 {$ENDIF}
1386 // map -> grid
1391 // did any corner crossed tile boundary?
1396 begin
1403 end
1404 else
1405 begin
1413 //TODO: optimize for horizontal/vertical moves
1415 var
1423 begin
1425 // check if tile coords was changed
1430 // map -> grid
1435 // check for heavy work
1446 {$IF DEFINED(D2F_DEBUG_MOVER)}
1447 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);
1448 {$ENDIF}
1450 begin
1451 // crossed tile boundary, do heavy work
1454 // cycle with old rect, remove body where it is necessary
1455 // optimized for horizontal moves
1456 {$IF DEFINED(D2F_DEBUG_MOVER)}
1457 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);
1458 {$ENDIF}
1459 // remove stale marks
1462 begin
1467 {$IF DEFINED(D2F_DEBUG_MOVER)}
1469 {$ENDIF}
1471 begin
1473 begin
1474 // this column is completely outside of new rect
1476 begin
1477 {$IF DEFINED(D2F_DEBUG_MOVER)}
1479 {$ENDIF}
1482 end
1483 else
1484 begin
1485 // heavy checks
1487 begin
1489 begin
1490 {$IF DEFINED(D2F_DEBUG_MOVER)}
1492 {$ENDIF}
1499 // cycle with new rect, add body where it is necessary
1502 begin
1507 {$IF DEFINED(D2F_DEBUG_MOVER)}
1509 {$ENDIF}
1511 begin
1513 begin
1514 // this column is completely outside of old rect
1516 begin
1517 {$IF DEFINED(D2F_DEBUG_MOVER)}
1519 {$ENDIF}
1522 end
1523 else
1524 begin
1525 // heavy checks
1527 begin
1529 begin
1530 {$IF DEFINED(D2F_DEBUG_MOVER)}
1532 {$ENDIF}
1539 // done
1540 end
1541 else
1542 begin
1543 {$IF DEFINED(D2F_DEBUG_MOVER)}
1544 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);
1545 {$ENDIF}
1547 // update coordinates
1553 var
1556 begin
1558 // check if tile coords was changed
1564 {$IF DEFINED(D2F_DEBUG_MOVER)}
1565 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);
1566 {$ENDIF}
1569 begin
1570 // crossed tile boundary, do heavy work
1575 end
1576 else
1577 begin
1578 // nothing to do with the grid, just fix size
1585 // ////////////////////////////////////////////////////////////////////////// //
1587 var
1589 begin
1592 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1597 // ////////////////////////////////////////////////////////////////////////// //
1598 // no callback: return `true` on the first hit
1599 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1600 var
1607 begin
1613 {$IF DEFINED(D2F_DEBUG_XXQ)}
1615 {$ENDIF}
1617 // make coords (0,0)-based
1624 {$IF DEFINED(D2F_DEBUG_XXQ)}
1625 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);
1626 {$ENDIF}
1628 // restore coords
1632 // increase query counter
1635 begin
1636 // just in case of overflow
1642 {$IF DEFINED(D2F_DEBUG_XXQ)}
1643 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1644 {$ENDIF}
1647 begin
1648 {$IF DEFINED(D2F_DEBUG_XXQ)}
1650 {$ENDIF}
1653 begin
1656 {$IF DEFINED(D2F_DEBUG_XXQ)}
1657 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);
1658 {$ENDIF}
1659 // shit. has to do it this way, so i can change tag in callback
1661 begin
1666 begin
1668 begin
1670 begin
1673 exit;
1675 end
1676 else
1677 begin
1680 exit;
1690 // ////////////////////////////////////////////////////////////////////////// //
1691 // no callback: return `true` on the first hit
1692 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1693 var
1704 begin
1713 // fix coords
1718 //tsize := mTileSize;
1726 // increase query counter
1729 begin
1730 // just in case of overflow
1734 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1737 // go on
1739 begin
1743 begin
1746 // process cells
1749 begin
1752 begin
1755 // shit. has to do it this way, so i can change tag in callback
1764 begin
1766 end
1767 else
1768 begin
1771 exit;
1783 // ////////////////////////////////////////////////////////////////////////// //
1784 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1785 var
1796 //px0, py0, px1, py1: Integer;
1797 begin
1808 // make query coords (0,0)-based
1820 // increase query counter
1823 begin
1824 // just in case of overflow
1830 repeat
1832 // check tile
1834 // process cells
1836 begin
1839 begin
1844 begin
1847 begin
1850 exit;
1854 // next cell
1857 // done processing cells, move to next tile
1864 // ////////////////////////////////////////////////////////////////////////// //
1865 // trace box with the given velocity; return object hit (if any)
1866 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1867 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1868 var
1879 begin
1893 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1899 // just in case
1905 // increase query counter
1908 begin
1909 // just in case of overflow
1916 begin
1918 begin
1921 begin
1924 begin
1929 begin
1932 begin
1935 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1937 begin
1942 begin
1946 exit;
1951 // next cell
1958 begin
1961 // just in case, compensate for floating point inexactness
1962 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1963 begin
1973 // ////////////////////////////////////////////////////////////////////////// //
1974 {.$DEFINE D2F_DEBUG_OTR}
1975 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1976 var
1987 {$IF DEFINED(D2F_DEBUG_OTR)}
1989 {$ENDIF}
1990 begin
2004 // offset query coords to (0,0)-based
2011 begin
2013 // vertical
2015 begin
2016 // down
2018 //if (ay0 < 0) then ay0 := 0;
2022 end
2023 else
2024 begin
2025 // up
2027 //if (ay1 < 0) then ay1 := 0;
2032 // check tile
2034 begin
2040 begin
2043 begin
2049 begin
2050 // bound c0 and c1 to cell
2053 // fill the thing
2054 {$IF DEFINED(D2F_DEBUG_OTR)}
2055 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)]);
2056 {$ENDIF}
2057 //assert(c0 <= c1);
2061 // next cell
2064 {$IF DEFINED(D2F_DEBUG_OTR)}
2065 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2069 {$ENDIF}
2070 // now go till we hit cell boundary or empty space
2072 begin
2073 // up
2075 begin
2076 {$IF DEFINED(D2F_DEBUG_OTR)}
2077 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2078 {$ENDIF}
2082 {$IF DEFINED(D2F_DEBUG_OTR)}
2083 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2084 {$ENDIF}
2086 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2087 end
2088 else
2089 begin
2090 // down
2096 end
2097 else
2098 begin
2099 // horizontal
2105 // ////////////////////////////////////////////////////////////////////////// //
2106 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2107 var
2109 begin
2114 // no callback: return `true` on the nearest hit
2115 // you are not supposed to understand this
2116 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2117 var
2132 begin
2142 // make query coords (0,0)-based
2158 // increase query counter
2161 begin
2162 // just in case of overflow
2168 repeat
2170 // check tile
2172 // process cells
2175 begin
2178 begin
2183 begin
2186 begin
2189 // get adjusted proxy coords
2194 // inside?
2196 begin
2197 // oops
2202 exit;
2204 // do line-vs-aabb test
2207 begin
2208 // hit detected
2212 begin
2217 // if this is not a first cell, get outta here
2224 // next cell
2227 // done processing cells; exit if we registered a hit
2228 // next cells can't have better candidates, obviously
2231 // move to next tile
2238 // ////////////////////////////////////////////////////////////////////////// //
2239 // no callback: return `true` on the nearest hit
2240 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2241 var
2243 begin
2248 // no callback: return `true` on the nearest hit
2249 // you are not supposed to understand this
2250 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2251 var
2277 //swapped: Boolean = false; // true: xd is yd, and vice versa
2278 // horizontal walker
2279 {$IFDEF GRID_USE_ORTHO_ACCEL}
2281 //wksign: Integer;
2283 {$ENDIF}
2284 // skipper
2286 begin
2295 begin
2298 begin
2301 exit;
2313 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2314 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);
2315 {$ENDIF}
2322 // offset query coords to (0,0)-based
2328 // clip rectange
2334 // horizontal setup
2336 begin
2337 // from left to right
2340 end
2341 else
2342 begin
2343 // from right to left
2353 // vertical setup
2355 begin
2356 // from top to bottom
2359 end
2360 else
2361 begin
2362 // from bottom to top
2376 begin
2377 //swapped := true;
2386 end
2387 else
2388 begin
2402 begin
2403 // clip at top
2409 begin
2412 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2419 begin
2420 // clip at left
2431 begin
2432 // clip at bottom
2442 //if (term = xd) then exit; // this is the only point, get out of here
2448 // first move, to skip starting point
2449 // DON'T DO THIS! loop will take care of that
2451 begin
2452 //FIXME!
2455 begin
2457 begin
2459 begin
2462 end
2463 else
2464 begin
2467 end
2468 else
2469 begin
2474 exit;
2479 (*
2480 // move coords
2481 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2482 xd += stx;
2483 // done?
2484 if (xd = term) then exit;
2485 *)
2487 {$IF DEFINED(D2F_DEBUG)}
2488 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2489 {$ENDIF}
2490 // DON'T DO THIS! loop will take care of that
2491 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2492 //ccidx := mGrid[lastGA];
2494 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2495 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2496 {$ENDIF}
2498 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2503 // increase query counter
2506 begin
2507 // just in case of overflow
2513 {$IFDEF GRID_USE_ORTHO_ACCEL}
2514 // if this is strict horizontal/vertical trace, use optimized codepath
2516 begin
2517 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2518 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2519 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2520 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2522 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2523 {$IF DEFINED(D2F_DEBUG)}
2525 {$ENDIF}
2527 // one of those will never change
2531 begin
2532 {$IF DEFINED(D2F_DEBUG)}
2533 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2534 {$ENDIF}
2535 // new tile?
2537 begin
2540 // convert coords to map (to avoid ajdusting coords inside the loop)
2543 begin
2546 begin
2551 // constant coord should be inside
2554 begin
2556 // inside the proxy?
2559 begin
2560 // setup prev[xy]
2562 begin
2564 begin
2569 exit;
2571 end
2572 else
2573 begin
2575 {$IF DEFINED(D2F_DEBUG)}
2576 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]);
2577 {$ENDIF}
2579 begin
2584 exit;
2587 continue;
2589 // remember this hitpoint if it is nearer than an old one
2590 // setup prev[xy]
2592 begin
2593 // horizontal trace
2597 begin
2598 // going left
2602 end
2603 else
2604 begin
2605 // going right
2610 end
2611 else
2612 begin
2613 // vertical trace
2617 begin
2618 // going up
2622 end
2623 else
2624 begin
2625 // going down
2632 begin
2634 begin
2639 exit;
2641 end
2642 else
2643 begin
2645 {$IF DEFINED(D2F_DEBUG)}
2646 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]);
2647 {$ENDIF}
2649 begin
2659 // next cell
2663 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2665 // skip to next tile
2667 begin
2669 begin
2670 // to the right
2672 {$IF DEFINED(D2F_DEBUG)}
2674 {$ENDIF}
2678 end
2679 else
2680 begin
2681 // to the left
2683 {$IF DEFINED(D2F_DEBUG)}
2685 {$ENDIF}
2690 end
2691 else
2692 begin
2694 begin
2695 // to the down
2697 {$IF DEFINED(D2F_DEBUG)}
2699 {$ENDIF}
2703 end
2704 else
2705 begin
2706 // to the up
2708 {$IF DEFINED(D2F_DEBUG)}
2710 {$ENDIF}
2718 // we can travel less than one cell
2721 exit;
2723 {$ENDIF}
2725 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2726 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2727 {$ENDIF}
2729 //e_LogWritefln('*********************', []);
2731 // can omit checks
2733 begin
2734 // check cell(s)
2735 {$IF DEFINED(D2F_DEBUG)}
2736 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2737 {$ENDIF}
2738 // new tile?
2740 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2741 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);
2742 {$ENDIF}
2744 begin
2745 // yes
2746 {$IF DEFINED(D2F_DEBUG)}
2747 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2748 {$ENDIF}
2750 begin
2751 // signal cell completion
2753 begin
2754 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2755 end
2757 begin
2760 exit;
2766 // has something to process in this tile?
2768 begin
2769 // process cell
2771 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2772 // convert coords to map (to avoid ajdusting coords inside the loop)
2775 // process cell list
2777 begin
2780 begin
2785 begin
2786 // can we process this proxy?
2788 begin
2791 begin
2793 begin
2798 exit;
2800 end
2801 else
2802 begin
2803 // remember this hitpoint if it is nearer than an old one
2805 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2806 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);
2807 {$ENDIF}
2809 begin
2817 end
2818 else
2819 begin
2820 // this is possibly interesting proxy, set "has more to check" flag
2825 // next cell
2828 // still has something interesting in this cell?
2830 begin
2831 // nope, don't process this cell anymore; signal cell completion
2834 begin
2836 end
2838 begin
2841 exit;
2846 begin
2847 // move to cell edge, as we have nothing to trace here anymore
2850 //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]);
2852 begin
2853 // step
2856 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2859 //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]);
2862 //putPixel(xptr^, yptr^);
2863 // move coords
2869 // we can travel less than one cell
2871 begin
2873 end
2874 else
2875 begin