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 {$IFDEF USE_MEMPOOL}
30 uses
31 mempool;
32 {$ENDIF}
34 const
37 type
41 public
42 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
43 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
49 private
50 const
53 public
54 type
57 private
64 private
76 public
91 private
92 type
101 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
103 private
104 //mTileSize: Integer;
108 public
111 type
113 private
117 public
124 private
138 public
140 {$IF DEFINED(D2F_DEBUG)}
142 {$ENDIF}
144 private
164 public
165 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
168 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
177 // `false` if `body` is surely invalid
182 //WARNING: don't modify grid while any query is in progress (no checks are made!)
183 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
184 // no callback: return `true` on the first hit
185 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
187 //WARNING: don't modify grid while any query is in progress (no checks are made!)
188 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
189 // no callback: return object on the first hit or nil
190 function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
194 //WARNING: don't modify grid while any query is in progress (no checks are made!)
195 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
196 // cb with `(nil)` will be called before processing new tile
197 // no callback: return object of the nearest hit or nil
198 // if `inverted` is true, trace will register bodies *exluding* tagmask
199 //WARNING: don't change tags in callbacks here!
200 function traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
201 function traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
203 //WARNING: don't modify grid while any query is in progress (no checks are made!)
204 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
205 // cb with `(nil)` will be called before processing new tile
206 // no callback: return object of the nearest hit or nil
207 // if `inverted` is true, trace will register bodies *exluding* tagmask
208 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
209 //WARNING: don't change tags in callbacks here!
210 function traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; overload;
211 function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
213 // return `false` if we're still inside at the end
214 // line should be either strict horizontal, or strict vertical, otherwise an exception will be thrown
215 // `true`: endpoint will point at the last "inside" pixel
216 // `false`: endpoint will be (ax1, ay1)
217 //WARNING: don't change tags in callbacks here!
218 function traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
220 //WARNING: don't modify grid while any query is in progress (no checks are made!)
221 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
222 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
223 //WARNING: don't change tags in callbacks here!
224 function forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
226 // trace box with the given velocity; return object hit (if any)
227 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
228 //WARNING: don't change tags in callbacks here!
229 function traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
231 // debug
236 public
237 //WARNING! no sanity checks!
249 type
250 // common structure for all line tracers
252 public
255 private
263 public
264 // call `setyp` after this
269 // this will use `w[xy][01]` to clip coords
270 // return `false` if the whole line was clipped away
271 // on `true`, you should process first point, and go on
274 // call this *after* doing a step
275 // WARNING! if you will do a step when this returns `true`, you will fall into limbo
278 // as you will prolly call `done()` after doing a step anyway, this will do it for you
279 // move to next point, return `true` when the line is complete (i.e. you should stop)
282 // move to next tile; return `true` if the line is complete (and walker state is undefined then)
287 public
288 // current coords
295 //function minInt (a, b: Integer): Integer; inline;
296 //function maxInt (a, b: Integer): Integer; inline;
299 implementation
301 uses
305 // ////////////////////////////////////////////////////////////////////////// //
306 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
307 //procedure swapInt (var a: Integer; var b: Integer); inline; begin a := a xor b; b := b xor a; a := a xor b; end;
308 //function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
309 //function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
312 // ////////////////////////////////////////////////////////////////////////// //
314 begin
319 begin
320 // clip rectange
328 var
330 begin
331 if (wx1 < wx0) or (wy1 < wy0) then begin stleft := 0; xd := x0; yd := y0; result := false; exit; end;
335 begin
337 end
338 else
339 begin
348 // check for ortho lines
350 begin
351 // horizontal
358 end
360 begin
361 // vertical
368 end
369 else
370 begin
371 // diagonal
373 begin
374 // horizontal
378 end
379 else
380 begin
381 // vertical
397 // true: done
399 begin
401 begin
405 end
406 else
407 begin
416 // true: done
418 var
422 begin
427 // strictly horizontal?
429 begin
430 // only xd
432 begin
433 // xd: to left edge
436 end
437 else
438 begin
439 // xd: to right edge
445 exit;
448 // strictly vertical?
450 begin
451 // only xd
453 begin
454 // yd: to top edge
457 end
458 else
459 begin
460 // yd: to bottom edge
466 exit;
469 // diagonal
471 // calculate xwalk
473 begin
476 end
477 else
478 begin
483 // calculate ywalk
485 begin
488 end
489 else
490 begin
495 {
496 while (xd <> ex) and (yd <> ey) do
497 begin
498 if horiz then
499 begin
500 xd += stx;
501 err += errinc;
502 if (err >= 0) then begin err -= errmax; yd += sty; end;
503 end
504 else
505 begin
506 yd += sty;
507 err += errinc;
508 if (err >= 0) then begin err -= errmax; xd += stx; end;
509 end;
510 Dec(stleft);
511 if (stleft < 1) then begin result := true; exit; end;
512 end;
513 }
517 begin
518 // in which dir we want to walk?
522 begin
525 begin
529 end
530 else
531 begin
534 begin
539 // check for walk completion
548 // ////////////////////////////////////////////////////////////////////////// //
549 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
550 begin
563 begin
568 begin
573 begin
578 begin
583 begin
588 begin
593 // ////////////////////////////////////////////////////////////////////////// //
594 constructor TBodyGridBase.TAtPointEnumerator.Create (acells: TCellArray; aidx: Integer; agetpx: TGetProxyFn);
595 begin
604 begin
606 begin
608 begin
612 exit;
622 begin
627 // ////////////////////////////////////////////////////////////////////////// //
628 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
629 var
631 begin
633 {$IF DEFINED(D2F_DEBUG)}
635 {$ENDIF}
636 {
637 if aTileSize < 1 then aTileSize := 1;
638 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
639 mTileSize := aTileSize;
640 }
651 // init free list
653 begin
659 // init grid
661 // init proxies
669 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), TMsgType.Notify);
674 begin
682 // ////////////////////////////////////////////////////////////////////////// //
684 var
686 begin
689 begin
693 begin
699 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);
704 var
707 begin
710 begin
713 begin
716 begin
718 if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY);
720 // next cell
728 var
731 begin
739 begin
742 begin
744 if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end;
746 // next cell
752 // ////////////////////////////////////////////////////////////////////////// //
753 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
754 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
758 begin
759 // fix coords
767 begin
769 begin
772 end
773 else
774 begin
783 begin
785 begin
788 end
789 else
790 begin
798 function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline;
799 begin
801 begin
804 end
805 else
806 begin
817 // ////////////////////////////////////////////////////////////////////////// //
819 begin
820 if (pid >= 0) and (pid < Length(mProxies)) then result := ((mProxies[pid].mTag and TagDisabled) = 0) else result := false;
825 begin
827 begin
829 begin
831 end
832 else
833 begin
841 begin
846 // ////////////////////////////////////////////////////////////////////////// //
848 var
851 begin
853 begin
854 // no free cells, want more
858 begin
870 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
875 begin
877 begin
879 begin
890 // ////////////////////////////////////////////////////////////////////////// //
891 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
892 var
895 begin
897 begin
898 // no free proxies, resize list
905 // get one from list
910 // add to used list
912 // statistics
918 begin
920 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
921 // add to free list
929 // ////////////////////////////////////////////////////////////////////////// //
930 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
931 var
935 begin
938 // fix coords
941 // go on
950 // clip rect
956 // do the work
958 begin
960 begin
968 // ////////////////////////////////////////////////////////////////////////// //
970 var
975 begin
977 // add body to the given grid cell
980 begin
981 {$IF DEFINED(D2F_DEBUG)}
984 begin
987 begin
989 if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy');
993 {$ENDIF}
996 begin
998 // check "has room" flag
1000 begin
1001 // can add here
1003 begin
1005 begin
1008 exit;
1013 // no room, go to next cell in list (if there is any)
1016 // no room in cells, add new cell to list
1018 // either no room, or no cell at all
1028 // assume that we cannot have one object added to bucket twice
1030 var
1034 begin
1036 // find and remove cell
1040 begin
1043 begin
1045 begin
1046 // i found her!
1048 begin
1049 // this cell contains no elements, remove it
1052 exit;
1054 // remove element from bucket
1056 begin
1061 exit;
1070 // ////////////////////////////////////////////////////////////////////////// //
1071 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
1072 begin
1075 //insertInternal(result);
1081 var
1083 begin
1086 //removeInternal(body);
1092 // ////////////////////////////////////////////////////////////////////////// //
1094 var
1097 begin
1104 {$IF DEFINED(D2F_DEBUG_MOVER)}
1105 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);
1106 {$ENDIF}
1108 // map -> grid
1113 // did any corner crossed tile boundary?
1118 begin
1119 //writeln('moveResizeBody: cell occupation changed! old=(', x0, ',', y0, ')-(', x0+w-1, ',', y0+h-1, '); new=(', nx, ',', ny, ')-(', nx+nw-1, ',', ny+nh-1, ')');
1120 //removeInternal(body);
1126 //insertInternal(body);
1128 end
1129 else
1130 begin
1139 //TODO: optimize for horizontal/vertical moves
1141 var
1149 begin
1151 // check if tile coords was changed
1156 // map -> grid
1161 // check for heavy work
1172 {$IF DEFINED(D2F_DEBUG_MOVER)}
1173 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);
1174 {$ENDIF}
1176 begin
1177 // crossed tile boundary, do heavy work
1180 // cycle with old rect, remove body where it is necessary
1181 // optimized for horizontal moves
1182 {$IF DEFINED(D2F_DEBUG_MOVER)}
1183 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);
1184 {$ENDIF}
1185 // remove stale marks
1188 begin
1193 {$IF DEFINED(D2F_DEBUG_MOVER)}
1195 {$ENDIF}
1197 begin
1199 begin
1200 // this column is completely outside of new rect
1202 begin
1203 {$IF DEFINED(D2F_DEBUG_MOVER)}
1205 {$ENDIF}
1208 end
1209 else
1210 begin
1211 // heavy checks
1213 begin
1215 begin
1216 {$IF DEFINED(D2F_DEBUG_MOVER)}
1218 {$ENDIF}
1225 // cycle with new rect, add body where it is necessary
1228 begin
1233 {$IF DEFINED(D2F_DEBUG_MOVER)}
1235 {$ENDIF}
1237 begin
1239 begin
1240 // this column is completely outside of old rect
1242 begin
1243 {$IF DEFINED(D2F_DEBUG_MOVER)}
1245 {$ENDIF}
1248 end
1249 else
1250 begin
1251 // heavy checks
1253 begin
1255 begin
1256 {$IF DEFINED(D2F_DEBUG_MOVER)}
1258 {$ENDIF}
1265 // done
1266 end
1267 else
1268 begin
1269 {$IF DEFINED(D2F_DEBUG_MOVER)}
1270 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);
1271 {$ENDIF}
1273 // update coordinates
1280 var
1283 begin
1285 // check if tile coords was changed
1291 {$IF DEFINED(D2F_DEBUG_MOVER)}
1292 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);
1293 {$ENDIF}
1296 begin
1297 // crossed tile boundary, do heavy work
1298 //removeInternal(body);
1302 //insertInternal(body);
1304 end
1305 else
1306 begin
1307 // nothing to do with the grid, just fix size
1314 // ////////////////////////////////////////////////////////////////////////// //
1316 var
1318 begin
1321 if (x >= 0) and (y >= 0) and (x < mWidth*mTileSize) and (y < mHeight*mTileSize) then ccidx := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)];
1326 // ////////////////////////////////////////////////////////////////////////// //
1327 // no callback: return `true` on the first hit
1328 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP;
1329 var
1336 begin
1342 {$IF DEFINED(D2F_DEBUG_XXQ)}
1344 {$ENDIF}
1346 // make coords (0,0)-based
1353 {$IF DEFINED(D2F_DEBUG_XXQ)}
1354 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);
1355 {$ENDIF}
1357 // restore coords
1361 // increase query counter
1364 begin
1365 // just in case of overflow
1371 {$IF DEFINED(D2F_DEBUG_XXQ)}
1372 if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY);
1373 {$ENDIF}
1376 begin
1377 {$IF DEFINED(D2F_DEBUG_XXQ)}
1379 {$ENDIF}
1382 begin
1385 {$IF DEFINED(D2F_DEBUG_XXQ)}
1386 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);
1387 {$ENDIF}
1388 // shit. has to do it this way, so i can change tag in callback
1390 begin
1395 begin
1397 begin
1399 begin
1402 exit;
1404 end
1405 else
1406 begin
1409 exit;
1419 // ////////////////////////////////////////////////////////////////////////// //
1420 // no callback: return `true` on the first hit
1421 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
1422 var
1434 begin
1443 // fix coords
1458 // clip rect
1465 // has something to do
1469 // increase query counter
1472 begin
1473 // just in case of overflow
1477 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
1480 // go on
1482 begin
1484 begin
1485 // process cells
1488 begin
1491 begin
1494 // shit! has to do it this way, so i can change tag in callback
1503 begin
1505 end
1506 else
1507 begin
1510 exit;
1522 // ////////////////////////////////////////////////////////////////////////// //
1523 function TBodyGridBase.forEachAlongLine (ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1524 var
1535 //px0, py0, px1, py1: Integer;
1536 begin
1547 // make query coords (0,0)-based
1559 // increase query counter
1562 begin
1563 // just in case of overflow
1569 repeat
1571 // check tile
1573 // process cells
1575 begin
1578 begin
1583 begin
1586 begin
1589 exit;
1593 // next cell
1596 // done processing cells, move to next tile
1603 // ////////////////////////////////////////////////////////////////////////// //
1604 // trace box with the given velocity; return object hit (if any)
1605 // `cb` is used unconvetionally here: if it returns `false`, tracer will ignore the object
1606 function TBodyGridBase.traceBox (out ex, ey: Integer; const ax0, ay0, aw, ah: Integer; const dx, dy: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1607 var
1618 begin
1632 if (cx1 < 0) or (cy1 < 0) or (cx0 >= mWidth*mTileSize) or (cy0 >= mHeight*mTileSize) then exit;
1638 // just in case
1644 // increase query counter
1647 begin
1648 // just in case of overflow
1655 begin
1657 begin
1660 begin
1663 begin
1668 begin
1671 begin
1674 if not sweepAABB(ax0, ay0, aw, ah, dx, dy, px.mX, px.mY, px.mWidth, px.mHeight, @u0) then continue;
1676 begin
1681 begin
1685 exit;
1690 // next cell
1697 begin
1700 // just in case, compensate for floating point inexactness
1701 if (ex >= hitpx.mX) and (ey >= hitpx.mY) and (ex < hitpx.mX+hitpx.mWidth) and (ey < hitpx.mY+hitpx.mHeight) then
1702 begin
1712 // ////////////////////////////////////////////////////////////////////////// //
1713 {.$DEFINE D2F_DEBUG_OTR}
1714 function TBodyGridBase.traceOrthoRayWhileIn (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): Boolean;
1715 var
1726 {$IF DEFINED(D2F_DEBUG_OTR)}
1728 {$ENDIF}
1729 begin
1743 // offset query coords to (0,0)-based
1750 begin
1752 // vertical
1754 begin
1755 // down
1757 //if (ay0 < 0) then ay0 := 0;
1761 end
1762 else
1763 begin
1764 // up
1766 //if (ay1 < 0) then ay1 := 0;
1771 // check tile
1773 begin
1779 begin
1782 begin
1788 begin
1789 // bound c0 and c1 to cell
1792 // fill the thing
1793 {$IF DEFINED(D2F_DEBUG_OTR)}
1794 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)]);
1795 {$ENDIF}
1796 //assert(c0 <= c1);
1800 // next cell
1803 {$IF DEFINED(D2F_DEBUG_OTR)}
1804 s := formatstrf(' x=%s; ay0=%s; ay1=%s; y0=%s; celly0=%s; celly1=%s; dy=%s; [', [ax0, ay0, ay1, y0, celly0, celly1, dy]);
1808 {$ENDIF}
1809 // now go till we hit cell boundary or empty space
1811 begin
1812 // up
1814 begin
1815 {$IF DEFINED(D2F_DEBUG_OTR)}
1816 e_LogWritefln(' filled: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1817 {$ENDIF}
1821 {$IF DEFINED(D2F_DEBUG_OTR)}
1822 e_LogWritefln(' span done: cdy=%s; y0=%s; celly0=%s; ay0=%s; ay1=%s', [y0-celly0, y0, celly0, ay0, ay1]);
1823 {$ENDIF}
1825 if (y0 >= celly0) then begin ey := ay0+1; {assert(forEachAtPoint(ex, ey, nil, tagmask) <> nil);} result := true; exit; end;
1826 end
1827 else
1828 begin
1829 // down
1835 end
1836 else
1837 begin
1838 // horizontal
1844 // ////////////////////////////////////////////////////////////////////////// //
1845 function TBodyGridBase.traceRay (const x0, y0, x1, y1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1846 var
1848 begin
1853 // no callback: return `true` on the nearest hit
1854 // you are not supposed to understand this
1855 function TBodyGridBase.traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
1856 var
1871 begin
1881 // make query coords (0,0)-based
1892 {$IF DEFINED(D2F_DEBUG)}
1893 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln('*** traceRay: (%s,%s)-(%s,%s)', [x0, y0, x1, y1]);
1894 {$ENDIF}
1899 // increase query counter
1902 begin
1903 // just in case of overflow
1909 repeat
1911 {$IF DEFINED(D2F_DEBUG)}
1913 {$ENDIF}
1914 // check tile
1916 // process cells
1919 begin
1922 begin
1927 begin
1930 begin
1933 // get adjusted proxy coords
1938 {$IF DEFINED(D2F_DEBUG)}
1939 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' cxy=(%s,%s); pan=(%s,%s)-(%s,%s)', [cx, cy, px0, py0, px1, py1]);
1940 {$ENDIF}
1941 // inside?
1943 begin
1944 // oops
1949 {$IF DEFINED(D2F_DEBUG)}
1951 {$ENDIF}
1952 exit;
1954 // do line-vs-aabb test
1956 begin
1957 // hit detected
1959 {$IF DEFINED(D2F_DEBUG)}
1960 //if assigned(dbgRayTraceTileHitCB) then e_LogWritefln(' hit=(%s,%s); distSq=%s; lastDistSq=%s', [hx, hy, distSq, lastDistSq]);
1961 {$ENDIF}
1963 begin
1973 // next cell
1976 // done processing cells; exit if we registered a hit
1977 // next cells can't have better candidates, obviously
1980 // move to next tile
1987 // ////////////////////////////////////////////////////////////////////////// //
1988 // no callback: return `true` on the nearest hit
1989 function TBodyGridBase.traceRayOld (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
1990 var
1992 begin
1997 // no callback: return `true` on the nearest hit
1998 // you are not supposed to understand this
1999 function TBodyGridBase.traceRayOld (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
2000 var
2026 //swapped: Boolean = false; // true: xd is yd, and vice versa
2027 // horizontal walker
2028 {$IFDEF GRID_USE_ORTHO_ACCEL}
2030 //wksign: Integer;
2032 {$ENDIF}
2033 // skipper
2035 begin
2044 begin
2047 begin
2050 exit;
2062 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2063 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);
2064 {$ENDIF}
2071 // offset query coords to (0,0)-based
2077 // clip rectange
2083 // horizontal setup
2085 begin
2086 // from left to right
2089 end
2090 else
2091 begin
2092 // from right to left
2102 // vertical setup
2104 begin
2105 // from top to bottom
2108 end
2109 else
2110 begin
2111 // from bottom to top
2125 begin
2126 //swapped := true;
2135 end
2136 else
2137 begin
2151 begin
2152 // clip at top
2158 begin
2161 //if (rem > 0) then begin Inc(xd); e += dy2; end; //BUGGY
2168 begin
2169 // clip at left
2180 begin
2181 // clip at bottom
2191 //if (term = xd) then exit; // this is the only point, get out of here
2197 // first move, to skip starting point
2198 // DON'T DO THIS! loop will take care of that
2200 begin
2201 //FIXME!
2204 begin
2206 begin
2208 begin
2211 end
2212 else
2213 begin
2216 end
2217 else
2218 begin
2223 exit;
2228 (*
2229 // move coords
2230 if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2;
2231 xd += stx;
2232 // done?
2233 if (xd = term) then exit;
2234 *)
2236 {$IF DEFINED(D2F_DEBUG)}
2237 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2238 {$ENDIF}
2239 // DON'T DO THIS! loop will take care of that
2240 //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize);
2241 //ccidx := mGrid[lastGA];
2243 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2244 //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY);
2245 {$ENDIF}
2247 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
2252 // increase query counter
2255 begin
2256 // just in case of overflow
2262 {$IFDEF GRID_USE_ORTHO_ACCEL}
2263 // if this is strict horizontal/vertical trace, use optimized codepath
2265 begin
2266 // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell
2267 // stx < 0: going left, otherwise `stx` is > 0, and we're going right
2268 // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell
2269 // stx < 0: going up, otherwise `stx` is > 0, and we're going down
2271 if (stx < 0) then begin {wksign := -1;} wklen := -(term-xd); end else begin {wksign := 1;} wklen := term-xd; end;
2272 {$IF DEFINED(D2F_DEBUG)}
2274 {$ENDIF}
2276 // one of those will never change
2280 begin
2281 {$IF DEFINED(D2F_DEBUG)}
2282 if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]);
2283 {$ENDIF}
2284 // new tile?
2286 begin
2289 // convert coords to map (to avoid ajdusting coords inside the loop)
2292 begin
2295 begin
2300 // constant coord should be inside
2303 begin
2305 // inside the proxy?
2308 begin
2309 // setup prev[xy]
2311 begin
2313 begin
2318 exit;
2320 end
2321 else
2322 begin
2324 {$IF DEFINED(D2F_DEBUG)}
2325 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]);
2326 {$ENDIF}
2328 begin
2333 exit;
2336 continue;
2338 // remember this hitpoint if it is nearer than an old one
2339 // setup prev[xy]
2341 begin
2342 // horizontal trace
2346 begin
2347 // going left
2351 end
2352 else
2353 begin
2354 // going right
2359 end
2360 else
2361 begin
2362 // vertical trace
2366 begin
2367 // going up
2371 end
2372 else
2373 begin
2374 // going down
2381 begin
2383 begin
2388 exit;
2390 end
2391 else
2392 begin
2394 {$IF DEFINED(D2F_DEBUG)}
2395 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]);
2396 {$ENDIF}
2398 begin
2408 // next cell
2412 if assigned(cb) and cb(nil, 0, x, y, x, y) then begin result := lastObj; mInQuery := false; exit; end;
2414 // skip to next tile
2416 begin
2418 begin
2419 // to the right
2421 {$IF DEFINED(D2F_DEBUG)}
2423 {$ENDIF}
2427 end
2428 else
2429 begin
2430 // to the left
2432 {$IF DEFINED(D2F_DEBUG)}
2434 {$ENDIF}
2439 end
2440 else
2441 begin
2443 begin
2444 // to the down
2446 {$IF DEFINED(D2F_DEBUG)}
2448 {$ENDIF}
2452 end
2453 else
2454 begin
2455 // to the up
2457 {$IF DEFINED(D2F_DEBUG)}
2459 {$ENDIF}
2467 // we can travel less than one cell
2470 exit;
2472 {$ENDIF}
2474 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2475 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2476 {$ENDIF}
2478 //e_LogWritefln('*********************', []);
2480 // can omit checks
2482 begin
2483 // check cell(s)
2484 {$IF DEFINED(D2F_DEBUG)}
2485 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*mTileSize) and (yptr^ >= gh*mTileSize) then raise Exception.Create('raycaster internal error (0)');
2486 {$ENDIF}
2487 // new tile?
2489 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2490 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);
2491 {$ENDIF}
2493 begin
2494 // yes
2495 {$IF DEFINED(D2F_DEBUG)}
2496 if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div mTileSize*mTileSize)+minx, (yptr^ div mTileSize*mTileSize)+miny);
2497 {$ENDIF}
2499 begin
2500 // signal cell completion
2502 begin
2503 if cb(nil, 0, xptr^+minx, yptr^+miny, prevx, prevy) then begin result := lastObj; mInQuery := false; exit; end;
2504 end
2506 begin
2509 exit;
2515 // has something to process in this tile?
2517 begin
2518 // process cell
2520 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
2521 // convert coords to map (to avoid ajdusting coords inside the loop)
2524 // process cell list
2526 begin
2529 begin
2534 begin
2535 // can we process this proxy?
2537 begin
2540 begin
2542 begin
2547 exit;
2549 end
2550 else
2551 begin
2552 // remember this hitpoint if it is nearer than an old one
2554 {$IF DEFINED(D2F_DEBUG_RAYTRACE)}
2555 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);
2556 {$ENDIF}
2558 begin
2566 end
2567 else
2568 begin
2569 // this is possibly interesting proxy, set "has more to check" flag
2574 // next cell
2577 // still has something interesting in this cell?
2579 begin
2580 // nope, don't process this cell anymore; signal cell completion
2583 begin
2585 end
2587 begin
2590 exit;
2595 begin
2596 // move to cell edge, as we have nothing to trace here anymore
2599 //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]);
2601 begin
2602 // step
2605 //e_LogWritefln(' xd=%d; yd=%d', [xd, yd]);
2608 //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]);
2611 //putPixel(xptr^, yptr^);
2612 // move coords
2618 // we can travel less than one cell
2620 begin
2622 end
2623 else
2624 begin