38ee53b79abbe55c6f70e70852689050e10b73a0
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
158 public
159 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
162 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
171 // `false` if `body` is surely invalid
176 //WARNING: don't modify grid while any query is in progress (no checks are made!)
177 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
178 // no callback: return `true` on the first hit
179 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
181 //WARNING: don't modify grid while any query is in progress (no checks are made!)
182 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
183 // no callback: return object on the first hit or nil
184 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
188 //WARNING: don't modify grid while any query is in progress (no checks are made!)
189 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
190 // cb with `(nil)` will be called before processing new tile
191 // no callback: return object of the nearest hit or nil
192 // if `inverted` is true, trace will register bodies *exluding* tagmask
193 //WARNING: don't change tags in callbacks here!
194 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
195 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
197 //WARNING: don't modify grid while any query is in progress (no checks are made!)
198 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
199 // cb with `(nil)` will be called before processing new tile
200 // no callback: return object of the nearest hit or nil
201 // if `inverted` is true, trace will register bodies *exluding* tagmask
202 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
203 //WARNING: don't change tags in callbacks here!
204 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
205 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
207 // return `false` if we're still inside at the end
208 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
209 // `true`: endpoint will point at the last "inside" pixel
210 // `false`: endpoint will be (ax1, ay1)
211 //WARNING: don't change tags in callbacks here!
212 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
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 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
217 //WARNING: don't change tags in callbacks here!
218 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
220 // trace box with the given velocity; return object hit (if any)
221 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
222 //WARNING: don't change tags in callbacks here!
223 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
225 // debug
230 public
231 //WARNING! no sanity checks!
243 type
244 // common structure for all line tracers
246 public
249 private
256 //xptr, yptr: PInteger;
259 public
260 // call `setyp` after this
265 // this will use `w[xy][01]` to clip coords
266 // return `false` if the whole line was clipped away
267 // on `true`, you should process first point, and go on
270 // call this *after* doing a step
271 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
274 // as you will prolly call `done()` after doing a step anyway, this will do it for you
275 // move to next point, return `true` when the line is complete (i.e. you should stop)
278 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
281 // hack for line-vs-aabb; NOT PROPERLY TESTED!
284 // current coords
290 // move directions; always [-1..1] (can be zero!)
296 // you are not supposed to understand this
297 // returns `true` if there is an intersection, and enter coords
298 // enter coords will be equal to (x0, y0) if starting point is inside the box
299 // if result is `false`, `inx` and `iny` are undefined
300 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
302 // sweep two AABB's to see if and when they are overlapping
303 // returns `true` if collision was detected (but boxes doesn't overlap)
304 // u1 and u1 has no sense if no collision was detected
305 // u0 = normalized time of first collision (i.e. collision starts at myMove*u0)
306 // u1 = normalized time of second collision (i.e. collision stops after myMove*u1)
307 // hitedge for `it`: 0: top; 1: right; 2: bottom; 3: left
308 // enter/exit coords will form non-intersecting configuration (i.e. will be before/after the actual collision)
309 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
315 //function minInt (a, b: Integer): Integer; inline;
316 //function maxInt (a, b: Integer): Integer; inline;
319 implementation
321 uses
325 // ////////////////////////////////////////////////////////////////////////// //
326 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
327 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
328 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
329 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
331 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
334 // ////////////////////////////////////////////////////////////////////////// //
336 begin
341 begin
342 // clip rectange
352 begin
359 var
366 begin
374 // ortho?
376 begin
377 // only xd
378 //assert(lsty <> 0);
380 begin
381 // xd: to left edge
384 exit;
385 end
386 else
387 begin
388 // xd: to right edge
391 exit;
395 // not ortho
396 //assert(lstx <> 0); // invariant
403 // calculate xwalk
405 begin
408 end
409 else
410 begin
415 // calculate ywalk
417 begin
420 end
421 else
422 begin
428 begin
429 // in which dir we want to walk?
431 // walk x
433 begin
436 end
437 else
438 begin
442 // walk y
448 //assert((xd div TileSize <> lxd div TileSize) or (yd div TileSize <> lyd div TileSize));
454 // NOT TESTED!
456 begin
457 //writeln('e=', e, '; dx2=', dx2, '; dy2=', dy2);
459 begin
462 end
463 else
464 begin
470 function TLineWalker.x (): Integer; inline; begin if xyswapped then result := yd else result := xd; end;
471 function TLineWalker.y (): Integer; inline; begin if xyswapped then result := xd else result := yd; end;
472 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;
474 function TLineWalker.dx (): Integer; inline; begin if xyswapped then result := stx else result := sty; end;
475 function TLineWalker.dy (): Integer; inline; begin if xyswapped then result := sty else result := stx; end;
478 procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
479 var
484 begin
488 // horizontal setup
490 begin
491 // from left to right
494 end
495 else
496 begin
497 // from right to left
507 // vertical setup
509 begin
510 // from top to bottom
513 end
514 else
515 begin
516 // from bottom to top
530 begin
532 //xptr := @yd;
533 //yptr := @xd;
540 end
541 else
542 begin
543 //xptr := @xd;
544 //yptr := @yd;
556 begin
557 // clip at top
563 begin
566 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
573 begin
574 // clip at left
585 begin
586 // clip at bottom
596 //if (term = xd) then exit; // this is the only point, get out of here
606 // ////////////////////////////////////////////////////////////////////////// //
607 // true: has something to draw
608 // based on paper by S.R.Kodituwakku, K.R.Wijeweera, M.A.P.Chamikara
610 var
612 begin
613 // non vertical lines
615 begin
616 // non vertical and non horizontal lines
618 begin
630 end
631 else
632 begin
633 // horizontal lines
639 end
640 else
641 begin
642 // vertical lines
643 // initial line is just a point
645 begin
647 end
649 begin
650 // completely outside
652 end
653 else
654 begin
662 // you are not supposed to understand this
663 // returns `true` if there is an intersection, and enter coords
664 // enter coords will be equal to (x0, y0) if starting point is inside the box
665 // if result is `false`, `inx` and `iny` are undefined
666 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
667 var
669 begin
671 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin inx := x0; iny := y0; result := true; exit; end;
675 if result then begin inx := trunc(sx0); iny := trunc(sy0); end else begin inx := x1; iny := y1; end;
679 // ////////////////////////////////////////////////////////////////////////// //
680 function sweepAABB (mex0, mey0, mew, meh: Integer; medx, medy: Integer; itx0, ity0, itw, ith: Integer;
682 var
686 var
688 begin
692 begin
696 end
698 begin
705 begin
708 end
710 begin
718 var
721 begin
734 // check if they are overlapping right now (SAT)
735 //if (mex1 >= itx0) and (mex0 <= itx1) and (mey1 >= ity0) and (mey0 <= ity1) then begin result := true; exit; end;
739 // treat b as stationary, so invert v to get relative velocity
753 begin
759 // ////////////////////////////////////////////////////////////////////////// //
760 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
761 begin
774 begin
779 begin
784 begin
789 begin
794 begin
799 begin
804 // ////////////////////////////////////////////////////////////////////////// //
805 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
806 begin
815 begin
817 begin
819 begin
823 exit;
833 begin
838 // ////////////////////////////////////////////////////////////////////////// //
839 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
840 var
842 begin
844 {$IF DEFINED(D2F_DEBUG)}
846 {$ENDIF}
847 {
848 if aTileSize < 1 then aTileSize := 1;
849 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
850 mTileSize := aTileSize;
851 }
862 // init free list
864 begin
870 // init grid
872 // init proxies
880 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
885 begin
893 // ////////////////////////////////////////////////////////////////////////// //
895 var
897 begin
900 begin
904 begin
910 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);
915 var
918 begin
921 begin
924 begin
927 begin
929 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
931 // next cell
939 var
942 begin
950 begin
953 begin
955 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
957 // next cell
963 // ////////////////////////////////////////////////////////////////////////// //
964 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
965 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
969 begin
970 // fix coords
978 begin
980 begin
983 end
984 else
985 begin
994 begin
996 begin
999 end
1000 else
1001 begin
1009 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
1010 begin
1012 begin
1015 end
1016 else
1017 begin
1028 // ////////////////////////////////////////////////////////////////////////// //
1030 begin
1031 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
1036 begin
1038 begin
1040 begin
1042 end
1043 else
1044 begin
1052 begin
1057 // ////////////////////////////////////////////////////////////////////////// //
1059 var
1062 begin
1064 begin
1065 // no free cells, want more
1069 begin
1081 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
1086 begin
1088 begin
1090 begin
1101 // ////////////////////////////////////////////////////////////////////////// //
1102 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
1103 var
1106 begin
1108 begin
1109 // no free proxies, resize list
1116 // get one from list
1121 // add to used list
1123 // statistics
1129 begin
1131 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
1132 // add to free list
1140 // ////////////////////////////////////////////////////////////////////////// //
1141 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
1142 var
1146 begin
1149 // fix coords
1152 // go on
1161 // clip rect
1167 // do the work
1169 begin
1171 begin
1179 // ////////////////////////////////////////////////////////////////////////// //
1181 var
1186 begin
1188 // add body to the given grid cell
1191 begin
1192 {$IF DEFINED(D2F_DEBUG)}
1195 begin
1198 begin
1200 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
1204 {$ENDIF}
1207 begin
1209 // check "has room" flag
1211 begin
1212 // can add here
1214 begin
1216 begin
1219 exit;
1224 // no room, go to next cell in list (if there is any)
1227 // no room in cells, add new cell to list
1229 // either no room, or no cell at all
1239 // assume that we cannot have one object added to bucket twice
1241 var
1245 begin
1247 // find and remove cell
1251 begin
1254 begin
1256 begin
1257 // i found her!
1259 begin
1260 // this cell contains no elements, remove it
1263 exit;
1265 // remove element from bucket
1267 begin
1272 exit;
1281 // ////////////////////////////////////////////////////////////////////////// //
1282 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1283 begin
1286 //insertInternal(result);
1292 var
1294 begin
1297 //removeInternal(body);
1303 // ////////////////////////////////////////////////////////////////////////// //
1305 var
1308 begin
1315 {$IF DEFINED(D2F_DEBUG_MOVER)}
1316 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);
1317 {$ENDIF}
1319 // map -> grid
1324 // did any corner crossed tile boundary?
1329 begin
1330 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1331 //removeInternal(body);
1337 //insertInternal(body);
1339 end
1340 else
1341 begin
1350 //TODO: optimize for horizontal/vertical moves
1352 var
1360 begin
1362 // check if tile coords was changed
1367 // map -> grid
1372 // check for heavy work
1383 {$IF DEFINED(D2F_DEBUG_MOVER)}
1384 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);
1385 {$ENDIF}
1387 begin
1388 // crossed tile boundary, do heavy work
1391 // cycle with old rect, remove body where it is necessary
1392 // optimized for horizontal moves
1393 {$IF DEFINED(D2F_DEBUG_MOVER)}
1394 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);
1395 {$ENDIF}
1396 // remove stale marks
1399 begin
1404 {$IF DEFINED(D2F_DEBUG_MOVER)}
1406 {$ENDIF}
1408 begin
1410 begin
1411 // this column is completely outside of new rect
1413 begin
1414 {$IF DEFINED(D2F_DEBUG_MOVER)}
1416 {$ENDIF}
1419 end
1420 else
1421 begin
1422 // heavy checks
1424 begin
1426 begin
1427 {$IF DEFINED(D2F_DEBUG_MOVER)}
1429 {$ENDIF}
1436 // cycle with new rect, add body where it is necessary
1439 begin
1444 {$IF DEFINED(D2F_DEBUG_MOVER)}
1446 {$ENDIF}
1448 begin
1450 begin
1451 // this column is completely outside of old rect
1453 begin
1454 {$IF DEFINED(D2F_DEBUG_MOVER)}
1456 {$ENDIF}
1459 end
1460 else
1461 begin
1462 // heavy checks
1464 begin
1466 begin
1467 {$IF DEFINED(D2F_DEBUG_MOVER)}
1469 {$ENDIF}
1476 // done
1477 end
1478 else
1479 begin
1480 {$IF DEFINED(D2F_DEBUG_MOVER)}
1481 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);
1482 {$ENDIF}
1484 // update coordinates
1491 var
1494 begin
1496 // check if tile coords was changed
1502 {$IF DEFINED(D2F_DEBUG_MOVER)}
1503 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);
1504 {$ENDIF}
1507 begin
1508 // crossed tile boundary, do heavy work
1509 //removeInternal(body);
1513 //insertInternal(body);
1515 end
1516 else
1517 begin
1518 // nothing to do with the grid, just fix size
1525 // ////////////////////////////////////////////////////////////////////////// //
1527 var
1529 begin
1532 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1537 // ////////////////////////////////////////////////////////////////////////// //
1538 // no callback: return `true` on the first hit
1539 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1540 var
1547 begin
1553 {$IF DEFINED(D2F_DEBUG_XXQ)}
1555 {$ENDIF}
1557 // make coords (0,0)-based
1564 {$IF DEFINED(D2F_DEBUG_XXQ)}
1565 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);
1566 {$ENDIF}
1568 // restore coords
1572 // increase query counter
1575 begin
1576 // just in case of overflow
1582 {$IF DEFINED(D2F_DEBUG_XXQ)}
1583 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1584 {$ENDIF}
1587 begin
1588 {$IF DEFINED(D2F_DEBUG_XXQ)}
1590 {$ENDIF}
1593 begin
1596 {$IF DEFINED(D2F_DEBUG_XXQ)}
1597 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);
1598 {$ENDIF}
1599 // shit. has to do it this way, so i can change tag in callback
1601 begin
1606 begin
1608 begin
1610 begin
1613 exit;
1615 end
1616 else
1617 begin
1620 exit;
1630 // ////////////////////////////////////////////////////////////////////////// //
1631 // no callback: return `true` on the first hit
1632 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1633 var
1645 begin
1654 // fix coords
1669 // clip rect
1676 // has something to do
1680 // increase query counter
1683 begin
1684 // just in case of overflow
1688 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1691 // go on
1693 begin
1695 begin
1696 // process cells
1699 begin
1702 begin
1705 // shit! has to do it this way, so i can change tag in callback
1714 begin
1716 end
1717 else
1718 begin
1721 exit;
1733 // ////////////////////////////////////////////////////////////////////////// //
1734 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1735 var
1746 //px0, py0, px1, py1: Integer;
1747 begin
1758 // make query coords (0,0)-based
1770 // increase query counter
1773 begin
1774 // just in case of overflow
1780 repeat
1782 // check tile
1784 // process cells
1786 begin
1789 begin
1794 begin
1797 begin
1800 exit;
1804 // next cell
1807 // done processing cells, move to next tile
1814 // ////////////////////////////////////////////////////////////////////////// //
1815 // trace box with the given velocity; return object hit (if any)
1816 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1817 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1818 var
1829 begin
1843 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1849 // just in case
1855 // increase query counter
1858 begin
1859 // just in case of overflow
1866 begin
1868 begin
1871 begin
1874 begin
1879 begin
1882 begin
1885 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1887 begin
1892 begin
1896 exit;
1901 // next cell
1908 begin
1911 // just in case, compensate for floating point inexactness
1912 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1913 begin
1923 // ////////////////////////////////////////////////////////////////////////// //
1924 {.$DEFINE D2F_DEBUG_OTR}
1925 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1926 var
1937 {$IF DEFINED(D2F_DEBUG_OTR)}
1939 {$ENDIF}
1940 begin
1954 // offset query coords to (0,0)-based
1961 begin
1963 // vertical
1965 begin
1966 // down
1968 //if (ay0 < 0) then ay0 := 0;
1972 end
1973 else
1974 begin
1975 // up
1977 //if (ay1 < 0) then ay1 := 0;
1982 // check tile
1984 begin
1990 begin
1993 begin
1999 begin
2000 // bound c0 and c1 to cell
2003 // fill the thing
2004 {$IF DEFINED(D2F_DEBUG_OTR)}
2005 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)]);
2006 {$ENDIF}
2007 //assert(c0 <= c1);
2011 // next cell
2014 {$IF DEFINED(D2F_DEBUG_OTR)}
2015 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
2019 {$ENDIF}
2020 // now go till we hit cell boundary or empty space
2022 begin
2023 // up
2025 begin
2026 {$IF DEFINED(D2F_DEBUG_OTR)}
2027 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2028 {$ENDIF}
2032 {$IF DEFINED(D2F_DEBUG_OTR)}
2033 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
2034 {$ENDIF}
2036 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
2037 end
2038 else
2039 begin
2040 // down
2046 end
2047 else
2048 begin
2049 // horizontal
2055 // ////////////////////////////////////////////////////////////////////////// //
2056 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2057 var
2059 begin
2064 // no callback: return `true` on the nearest hit
2065 // you are not supposed to understand this
2066 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
2067 var
2082 begin
2092 // make query coords (0,0)-based
2108 // increase query counter
2111 begin
2112 // just in case of overflow
2118 repeat
2120 // check tile
2122 // process cells
2125 begin
2128 begin
2133 begin
2136 begin
2139 // get adjusted proxy coords
2144 // inside?
2146 begin
2147 // oops
2152 exit;
2154 // do line-vs-aabb test
2157 begin
2158 // hit detected
2162 begin
2167 // if this is not a first cell, get outta here
2174 // next cell
2177 // done processing cells; exit if we registered a hit
2178 // next cells can't have better candidates, obviously
2181 // move to next tile
2188 // ////////////////////////////////////////////////////////////////////////// //
2189 // no callback: return `true` on the nearest hit
2190 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2191 var
2193 begin
2198 // no callback: return `true` on the nearest hit
2199 // you are not supposed to understand this
2200 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2201 var
2227 //swapped: Boolean = false; // true: xd is yd, and vice versa
2228 // horizontal walker
2229 {$IFDEF GRID_USE_ORTHO_ACCEL}
2231 //wksign: Integer;
2233 {$ENDIF}
2234 // skipper
2236 begin
2245 begin
2248 begin
2251 exit;
2263 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2264 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);
2265 {$ENDIF}
2272 // offset query coords to (0,0)-based
2278 // clip rectange
2284 // horizontal setup
2286 begin
2287 // from left to right
2290 end
2291 else
2292 begin
2293 // from right to left
2303 // vertical setup
2305 begin
2306 // from top to bottom
2309 end
2310 else
2311 begin
2312 // from bottom to top
2326 begin
2327 //swapped := true;
2336 end
2337 else
2338 begin
2352 begin
2353 // clip at top
2359 begin
2362 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2369 begin
2370 // clip at left
2381 begin
2382 // clip at bottom
2392 //if (term = xd) then exit; // this is the only point, get out of here
2398 // first move, to skip starting point
2399 // DON'T DO THIS! loop will take care of that
2401 begin
2402 //FIXME!
2405 begin
2407 begin
2409 begin
2412 end
2413 else
2414 begin
2417 end
2418 else
2419 begin
2424 exit;
2429 (*
2430 // move coords
2431 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2432 xd += stx;
2433 // done?
2434 if (xd = term) then exit;
2435 *)
2437 {$IF DEFINED(D2F_DEBUG)}
2438 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2439 {$ENDIF}
2440 // DON'T DO THIS! loop will take care of that
2441 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2442 //ccidx := mGrid[lastGA];
2444 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2445 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2446 {$ENDIF}
2448 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2453 // increase query counter
2456 begin
2457 // just in case of overflow
2463 {$IFDEF GRID_USE_ORTHO_ACCEL}
2464 // if this is strict horizontal/vertical trace, use optimized codepath
2466 begin
2467 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2468 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2469 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2470 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2472 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2473 {$IF DEFINED(D2F_DEBUG)}
2475 {$ENDIF}
2477 // one of those will never change
2481 begin
2482 {$IF DEFINED(D2F_DEBUG)}
2483 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2484 {$ENDIF}
2485 // new tile?
2487 begin
2490 // convert coords to map (to avoid ajdusting coords inside the loop)
2493 begin
2496 begin
2501 // constant coord should be inside
2504 begin
2506 // inside the proxy?
2509 begin
2510 // setup prev[xy]
2512 begin
2514 begin
2519 exit;
2521 end
2522 else
2523 begin
2525 {$IF DEFINED(D2F_DEBUG)}
2526 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]);
2527 {$ENDIF}
2529 begin
2534 exit;
2537 continue;
2539 // remember this hitpoint if it is nearer than an old one
2540 // setup prev[xy]
2542 begin
2543 // horizontal trace
2547 begin
2548 // going left
2552 end
2553 else
2554 begin
2555 // going right
2560 end
2561 else
2562 begin
2563 // vertical trace
2567 begin
2568 // going up
2572 end
2573 else
2574 begin
2575 // going down
2582 begin
2584 begin
2589 exit;
2591 end
2592 else
2593 begin
2595 {$IF DEFINED(D2F_DEBUG)}
2596 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]);
2597 {$ENDIF}
2599 begin
2609 // next cell
2613 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2615 // skip to next tile
2617 begin
2619 begin
2620 // to the right
2622 {$IF DEFINED(D2F_DEBUG)}
2624 {$ENDIF}
2628 end
2629 else
2630 begin
2631 // to the left
2633 {$IF DEFINED(D2F_DEBUG)}
2635 {$ENDIF}
2640 end
2641 else
2642 begin
2644 begin
2645 // to the down
2647 {$IF DEFINED(D2F_DEBUG)}
2649 {$ENDIF}
2653 end
2654 else
2655 begin
2656 // to the up
2658 {$IF DEFINED(D2F_DEBUG)}
2660 {$ENDIF}
2668 // we can travel less than one cell
2671 exit;
2673 {$ENDIF}
2675 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2676 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2677 {$ENDIF}
2679 //e_LogWritefln('*********************', []);
2681 // can omit checks
2683 begin
2684 // check cell(s)
2685 {$IF DEFINED(D2F_DEBUG)}
2686 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2687 {$ENDIF}
2688 // new tile?
2690 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2691 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);
2692 {$ENDIF}
2694 begin
2695 // yes
2696 {$IF DEFINED(D2F_DEBUG)}
2697 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2698 {$ENDIF}
2700 begin
2701 // signal cell completion
2703 begin
2704 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2705 end
2707 begin
2710 exit;
2716 // has something to process in this tile?
2718 begin
2719 // process cell
2721 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2722 // convert coords to map (to avoid ajdusting coords inside the loop)
2725 // process cell list
2727 begin
2730 begin
2735 begin
2736 // can we process this proxy?
2738 begin
2741 begin
2743 begin
2748 exit;
2750 end
2751 else
2752 begin
2753 // remember this hitpoint if it is nearer than an old one
2755 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2756 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);
2757 {$ENDIF}
2759 begin
2767 end
2768 else
2769 begin
2770 // this is possibly interesting proxy, set "has more to check" flag
2775 // next cell
2778 // still has something interesting in this cell?
2780 begin
2781 // nope, don't process this cell anymore; signal cell completion
2784 begin
2786 end
2788 begin
2791 exit;
2796 begin
2797 // move to cell edge, as we have nothing to trace here anymore
2800 //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]);
2802 begin
2803 // step
2806 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2809 //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]);
2812 //putPixel(xptr^, yptr^);
2813 // move coords
2819 // we can travel less than one cell
2821 begin
2823 end
2824 else
2825 begin