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}
20 interface
23 type
27 public
28 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
29 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
30 type TGridAlongQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
35 private
36 const
40 private
41 type
44 private
51 private
61 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
63 private
64 //mTileSize: Integer;
67 public
70 private
83 public
86 private
107 public
108 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
111 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
120 // `false` if `body` is surely invalid
123 //WARNING: don't modify grid while any query is in progress (no checks are made!)
124 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
125 // no callback: return `true` on the first hit
126 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
128 //WARNING: don't modify grid while any query is in progress (no checks are made!)
129 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
130 // no callback: return `true` on the first hit
133 //WARNING: don't modify grid while any query is in progress (no checks are made!)
134 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
135 // cb with `(nil)` will be called before processing new tile
136 // no callback: return `true` on the nearest hit
137 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
138 function traceRay (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
140 //WARNING: don't modify grid while any query is in progress (no checks are made!)
141 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
142 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
143 function forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
147 //WARNING! no sanity checks!
157 // you are not supposed to understand this
158 // returns `true` if there is an intersection, and enter coords
159 // enter coords will be equal to (x0, y0) if starting point is inside the box
160 // if result is `false`, `inx` and `iny` are undefined
161 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
170 implementation
172 uses
176 // ////////////////////////////////////////////////////////////////////////// //
177 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
178 function minInt (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
179 function maxInt (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
181 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
184 // ////////////////////////////////////////////////////////////////////////// //
185 // you are not supposed to understand this
186 // returns `true` if there is an intersection, and enter coords
187 // enter coords will be equal to (x0, y0) if starting point is inside the box
188 // if result is `false`, `inx` and `iny` are undefined
189 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
190 var
198 //!term: Integer;
202 begin
204 // why not
210 begin
211 // check this point
213 exit;
216 // check if staring point is inside the box
217 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
219 // clip rectange
225 // horizontal setup
227 begin
228 // from left to right
231 end
232 else
233 begin
234 // from right to left
244 // vertical setup
246 begin
247 // from top to bottom
250 end
251 else
252 begin
253 // from bottom to top
267 begin
276 end
277 else
278 begin
288 //!term := x1;
292 begin
293 // clip at top
299 begin
308 begin
309 // clip at left
319 (*
320 if (y1 > wy1) then
321 begin
322 // clip at bottom
323 temp := dx2*(wy1-y0)+dsx;
324 term := x0+temp div dy2;
325 rem := temp mod dy2;
326 if (rem = 0) then Dec(term);
327 end;
329 if (term > wx1) then term := wx1; // clip at right
331 Inc(term); // draw last point
332 //if (term = xd) then exit; // this is the only point, get out of here
333 *)
337 //!dx2 -= dy2;
345 // ////////////////////////////////////////////////////////////////////////// //
346 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
347 begin
359 // ////////////////////////////////////////////////////////////////////////// //
360 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
361 var
363 begin
365 {
366 if aTileSize < 1 then aTileSize := 1;
367 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
368 mTileSize := aTileSize;
369 }
380 // init free list
382 begin
387 // init grid
389 // init proxies
397 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
402 begin
410 // ////////////////////////////////////////////////////////////////////////// //
412 var
414 begin
417 begin
421 begin
427 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);
431 // ////////////////////////////////////////////////////////////////////////// //
432 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
433 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
437 begin
438 // fix coords
446 begin
448 begin
451 end
452 else
453 begin
461 // ////////////////////////////////////////////////////////////////////////// //
463 begin
469 begin
471 begin
473 begin
475 end
476 else
477 begin
484 // ////////////////////////////////////////////////////////////////////////// //
486 var
488 begin
490 begin
491 // no free cells, want more
495 begin
506 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
511 begin
513 begin
514 //if mCells[idx].body = -1 then exit; // the thing that should not be
523 // ////////////////////////////////////////////////////////////////////////// //
524 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
525 var
528 begin
530 begin
531 // no free proxies, resize list
538 // get one from list
543 // add to used list
545 // statistics
551 begin
553 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
554 // add to free list
562 // ////////////////////////////////////////////////////////////////////////// //
563 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
564 const
566 var
569 begin
572 // fix coords
575 // go on
579 //tsize := mTileSize;
582 begin
586 begin
596 // ////////////////////////////////////////////////////////////////////////// //
598 var
603 begin
605 // add body to the given grid cell
608 begin
612 begin
614 begin
615 // can add here
618 exit;
622 // either no room, or no cell at all
631 var
633 begin
640 // absolutely not tested
642 var
646 begin
648 // find and remove cell
652 begin
657 begin
659 begin
660 // i found her!
662 begin
663 // this cell contains no elements, remove it
667 end
668 else
669 begin
670 // remove element from bucket
673 begin
689 // absolutely not tested
691 var
693 begin
700 // ////////////////////////////////////////////////////////////////////////// //
701 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
702 begin
710 begin
717 // ////////////////////////////////////////////////////////////////////////// //
719 var
722 begin
730 // did any corner crossed tile boundary?
735 begin
742 end
743 else
744 begin
753 var
756 begin
758 // check if tile coords was changed
764 begin
765 // crossed tile boundary, do heavy work
770 end
771 else
772 begin
773 // nothing to do with the grid, just fix coordinates
780 var
783 begin
785 // check if tile coords was changed
793 begin
794 // crossed tile boundary, do heavy work
799 end
800 else
801 begin
802 // nothing to do with the grid, just fix size
809 // ////////////////////////////////////////////////////////////////////////// //
810 // no callback: return `true` on the first hit
811 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
812 var
819 begin
824 // make coords (0,0)-based
830 // restore coords
834 // increase query counter
837 begin
838 // just in case of overflow
845 begin
848 begin
853 begin
855 begin
858 begin
860 end
861 else
862 begin
864 exit;
874 // ////////////////////////////////////////////////////////////////////////// //
875 // no callback: return `true` on the first hit
876 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
877 const
879 var
890 begin
899 // fix coords
904 //tsize := mTileSize;
909 // increase query counter
912 begin
913 // just in case of overflow
917 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
920 // go on
922 begin
926 begin
929 // process cells
932 begin
935 begin
941 //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
942 //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
943 begin
948 begin
950 end
951 else
952 begin
954 exit;
965 // ////////////////////////////////////////////////////////////////////////// //
966 // no callback: return `true` on the nearest hit
967 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
968 var
970 begin
975 // no callback: return `true` on the nearest hit
976 // you are not supposed to understand this
977 function TBodyGridBase.traceRay (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
978 const
980 var
1006 begin
1014 if (ax0 = ax1) and (ay0 = ay1) then exit; // as the first point is ignored, just get outta here
1030 // offset query coords to (0,0)-based
1036 // clip rectange
1042 // horizontal setup
1044 begin
1045 // from left to right
1048 end
1049 else
1050 begin
1051 // from right to left
1061 // vertical setup
1063 begin
1064 // from top to bottom
1067 end
1068 else
1069 begin
1070 // from bottom to top
1084 begin
1093 end
1094 else
1095 begin
1109 begin
1110 // clip at top
1116 begin
1125 begin
1126 // clip at left
1137 begin
1138 // clip at bottom
1148 //if (term = xd) then exit; // this is the only point, get out of here
1154 // first move, to skip starting point
1158 // move coords
1161 // done?
1164 {$IF DEFINED(D2F_DEBUG)}
1165 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ > mHeight*tsize) then raise Exception.Create('raycaster internal error (0)');
1166 {$ENDIF}
1168 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1170 // restore query coords
1173 //Inc(ax1, minx);
1174 //Inc(ay1, miny);
1176 // increase query counter
1179 begin
1180 // just in case of overflow
1187 // draw it; can omit checks
1189 begin
1190 // check cell(s)
1191 {$IF DEFINED(D2F_DEBUG)}
1192 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ > mHeight*tsize) then raise Exception.Create('raycaster internal error (0)');
1193 {$ENDIF}
1194 // new tile?
1197 begin
1198 // yes
1200 begin
1201 // signal cell completion
1203 begin
1205 end
1207 begin
1209 exit;
1215 // has something to process in this tile?
1217 begin
1218 // process cell
1220 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1221 // convert coords to map (to avoid ajdusting coords inside the loop)
1224 // process cell list
1226 begin
1229 begin
1234 begin
1235 // can we process this proxy?
1237 begin
1240 begin
1242 begin
1246 exit;
1248 end
1249 else
1250 begin
1251 // remember this hitpoint if it is nearer than an old one
1254 begin
1262 end
1263 else
1264 begin
1265 // this is possibly interesting proxy, set "has more to check" flag
1270 // next cell
1273 // still has something interesting in this cell?
1275 begin
1276 // nope, don't process this cell anymore; signal cell completion
1279 begin
1281 end
1283 begin
1285 exit;
1289 //putPixel(xptr^, yptr^);
1290 // move coords
1299 // ////////////////////////////////////////////////////////////////////////// //
1300 //FIXME! optimize this with real tile walking
1301 function TBodyGridBase.forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP;
1302 const
1304 var
1323 //tedist: Integer;
1324 begin
1346 // `x` and `y` will be in grid coords
1350 // increase query counter
1353 begin
1354 // just in case of overflow
1360 // cache various things
1361 //tsize := mTileSize;
1367 // setup distance and flags
1370 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1373 // it is slightly faster this way
1377 if (log) then e_WriteLog(Format('tracing: (%d,%d)-(%d,%d)', [x, y, x1-minx, y1-miny]), MSG_NOTIFY);
1379 // now trace
1382 begin
1384 // do one step
1387 // invariant: one of those always changed
1388 {$IF DEFINED(D2F_DEBUG)}
1389 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1390 {$ENDIF}
1393 // invariant: we always doing a step
1394 {$IF DEFINED(D2F_DEBUG)}
1396 {$ENDIF}
1397 begin
1398 // check for crossing tile/grid boundary
1400 begin
1401 // we're still in grid
1403 // check for tile edge crossing
1409 // crossed tile edge?
1411 begin
1412 // setup new cell index
1414 if (log) then e_WriteLog(Format(' stepped to new tile (%d,%d) -- (%d,%d)', [(x div tsize), (y div tsize), x, y]), MSG_NOTIFY);
1415 end
1416 else
1418 begin
1419 // we have nothing interesting here anymore, jump directly to tile edge
1420 (*
1421 if (incx = 0) then
1422 begin
1423 // vertical line
1424 if (incy < 0) then tedist := y-(y and (not tsize)) else tedist := (y or (tsize-1))-y;
1425 if (tedist > 1) then
1426 begin
1427 if (log) then e_WriteLog(Format(' doing vertical jump from tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
1428 y += incy*tedist;
1429 Inc(i, tedist);
1430 if (log) then e_WriteLog(Format(' jumped to tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
1431 end;
1432 end
1433 else if (incy = 0) then
1434 begin
1435 // horizontal line
1436 if (incx < 0) then tedist := x-(x and (not tsize)) else tedist := (x or (tsize-1))-x;
1437 if (tedist > 1) then
1438 begin
1439 if (log) then e_WriteLog(Format(' doing horizontal jump from tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
1440 x += incx*tedist;
1441 Inc(i, tedist);
1442 if (log) then e_WriteLog(Format(' jumped to tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
1443 end;
1444 end;
1445 *)
1446 (*
1447 else if (
1448 // get minimal distance to tile edges
1449 if (incx < 0) then tedist := x-(x and (not tsize)) else if (incx > 0) then tedist := (x or (tsize+1))-x else tedist := 0;
1450 {$IF DEFINED(D2F_DEBUG)}
1451 if (tedist < 0) then raise Exception.Create('internal bug in grid raycaster (2.x)');
1452 {$ENDIF}
1453 if (incy < 0) then f := y-(y and (not tsize)) else if (incy > 0) then f := (y or (tsize+1))-y else f := 0;
1454 {$IF DEFINED(D2F_DEBUG)}
1455 if (f < 0) then raise Exception.Create('internal bug in grid raycaster (2.y)');
1456 {$ENDIF}
1457 if (tedist = 0) then tedist := f else if (f <> 0) then tedist := minInt(tedist, f);
1458 // do jump
1459 if (tedist > 1) then
1460 begin
1461 if (log) then e_WriteLog(Format(' doing jump from tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
1462 xerr += dx*tedist;
1463 yerr += dy*tedist;
1464 if (xerr >= 0) then begin x += incx*((xerr div d)+1); xerr := (xerr mod d)-d; end;
1465 if (yerr >= 0) then begin y += incy*((yerr div d)+1); yerr := (yerr mod d)-d; end;
1466 Inc(i, tedist);
1467 if (log) then e_WriteLog(Format(' jumped to tile (%d,%d) - (%d,%d) by %d steps', [(x div tsize), (y div tsize), x, y, tedist]), MSG_NOTIFY);
1468 end;
1469 *)
1471 end
1472 else
1473 begin
1474 // out of grid
1479 // has something to process in the current cell?
1481 begin
1482 // process cell
1484 // convert coords to map (to avoid ajdusting coords inside the loop)
1485 //Inc(x, minx);
1486 //Inc(y, miny);
1487 // process cell list
1489 begin
1492 begin
1497 begin
1502 // next cell
1506 // convert coords to grid
1507 //Dec(x, minx);
1508 //Dec(y, miny);