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 private
80 private
101 public
102 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
105 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
114 // `false` if `body` is surely invalid
117 //WARNING: don't modify grid while any query is in progress (no checks are made!)
118 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
119 // no callback: return `true` on the first hit
120 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
122 //WARNING: don't modify grid while any query is in progress (no checks are made!)
123 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
124 // no callback: return `true` on the first hit
127 //WARNING: don't modify grid while any query is in progress (no checks are made!)
128 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
129 // cb with `(nil)` will be called before processing new tile
130 // no callback: return `true` on the nearest hit
131 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
132 function traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
134 //WARNING: don't modify grid while any query is in progress (no checks are made!)
135 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
136 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
137 function forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
141 //WARNING! no sanity checks!
151 // you are not supposed to understand this
152 // returns `true` if there is an intersection, and enter coords
153 // enter coords will be equal to (x0, y0) if starting point is inside the box
154 // if result is `false`, `inx` and `iny` are undefined
155 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
162 implementation
164 uses
168 // ////////////////////////////////////////////////////////////////////////// //
169 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
171 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
174 // ////////////////////////////////////////////////////////////////////////// //
175 // you are not supposed to understand this
176 // returns `true` if there is an intersection, and enter coords
177 // enter coords will be equal to (x0, y0) if starting point is inside the box
178 // if result is `false`, `inx` and `iny` are undefined
179 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
180 var
192 begin
194 // why not
200 begin
201 // check this point
203 exit;
206 // check if staring point is inside the box
207 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
209 // clip rectange
215 // horizontal setup
217 begin
218 // from left to right
221 end
222 else
223 begin
224 // from right to left
234 // vertical setup
236 begin
237 // from top to bottom
240 end
241 else
242 begin
243 // from bottom to top
257 begin
266 end
267 else
268 begin
282 begin
283 // clip at top
289 begin
298 begin
299 // clip at left
310 begin
311 // clip at bottom
321 //if (term = xd) then exit; // this is the only point, get out of here
333 // ////////////////////////////////////////////////////////////////////////// //
334 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
335 begin
347 // ////////////////////////////////////////////////////////////////////////// //
348 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
349 var
351 begin
352 {
353 if aTileSize < 1 then aTileSize := 1;
354 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
355 mTileSize := aTileSize;
356 }
367 // init free list
369 begin
374 // init grid
376 // init proxies
384 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
389 begin
397 // ////////////////////////////////////////////////////////////////////////// //
399 var
401 begin
404 begin
408 begin
414 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);
418 // ////////////////////////////////////////////////////////////////////////// //
419 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
420 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
424 begin
425 // fix coords
433 begin
435 begin
438 end
439 else
440 begin
448 // ////////////////////////////////////////////////////////////////////////// //
450 begin
456 begin
458 begin
460 begin
462 end
463 else
464 begin
471 // ////////////////////////////////////////////////////////////////////////// //
473 var
475 begin
477 begin
478 // no free cells, want more
482 begin
493 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
498 begin
500 begin
501 //if mCells[idx].body = -1 then exit; // the thing that should not be
510 // ////////////////////////////////////////////////////////////////////////// //
511 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
512 var
515 begin
517 begin
518 // no free proxies, resize list
525 // get one from list
530 // add to used list
532 // statistics
538 begin
540 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
541 // add to free list
549 // ////////////////////////////////////////////////////////////////////////// //
550 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
551 const
553 var
556 begin
559 // fix coords
562 // go on
566 //tsize := mTileSize;
569 begin
573 begin
583 // ////////////////////////////////////////////////////////////////////////// //
585 var
590 begin
592 // add body to the given grid cell
595 begin
599 begin
601 begin
602 // can add here
605 exit;
609 // either no room, or no cell at all
618 var
620 begin
627 // absolutely not tested
629 var
633 begin
635 // find and remove cell
639 begin
644 begin
646 begin
647 // i found her!
649 begin
650 // this cell contains no elements, remove it
654 end
655 else
656 begin
657 // remove element from bucket
660 begin
676 // absolutely not tested
678 var
680 begin
687 // ////////////////////////////////////////////////////////////////////////// //
688 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
689 begin
697 begin
704 // ////////////////////////////////////////////////////////////////////////// //
706 var
709 begin
717 // did any corner crossed tile boundary?
722 begin
729 end
730 else
731 begin
740 var
743 begin
746 // check if tile coords was changed
751 begin
752 // crossed tile boundary, do heavy work
754 end
755 else
756 begin
757 // nothing to do with the grid, just fix coordinates
764 var
768 begin
771 // check if tile coords was changed
779 begin
780 // crossed tile boundary, do heavy work
782 end
783 else
784 begin
785 // nothing to do with the grid, just fix size
792 // ////////////////////////////////////////////////////////////////////////// //
793 // no callback: return `true` on the first hit
794 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
795 var
802 begin
807 // make coords (0,0)-based
813 // restore coords
817 // increase query counter
820 begin
821 // just in case of overflow
828 begin
831 begin
836 begin
838 begin
841 begin
843 end
844 else
845 begin
847 exit;
857 // ////////////////////////////////////////////////////////////////////////// //
858 // no callback: return `true` on the first hit
859 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
860 const
862 var
873 begin
882 // fix coords
887 //tsize := mTileSize;
892 // increase query counter
895 begin
896 // just in case of overflow
900 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
903 // go on
905 begin
909 begin
912 // process cells
915 begin
918 begin
924 //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
925 //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
926 begin
931 begin
933 end
934 else
935 begin
937 exit;
948 // ////////////////////////////////////////////////////////////////////////// //
949 // no callback: return `true` on the nearest hit
950 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
951 var
953 begin
958 // no callback: return `true` on the nearest hit
959 function TBodyGridBase.traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
960 const
962 var
986 begin
1006 // `x` and `y` will be in grid coords
1010 // increase query counter
1013 begin
1014 // just in case of overflow
1020 // cache various things
1021 //tsize := mTileSize;
1027 // setup distance and flags
1031 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1034 // it is slightly faster this way
1038 // now trace
1040 begin
1041 // prevs are always in map coords
1044 // do one step
1047 // invariant: one of those always changed
1048 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1051 // invariant: we always doing a step
1053 begin
1054 // check for crossing tile/grid boundary
1056 begin
1057 // we're still in grid
1059 // check for tile edge crossing
1065 // crossed tile edge?
1067 begin
1068 // had something in the cell we're leaving?
1070 begin
1071 // yes, signal cell completion
1073 begin
1075 end
1077 begin
1079 exit;
1082 // setup new cell index
1085 end
1086 else
1087 begin
1088 // out of grid, had something in the last processed cell?
1090 begin
1091 // yes, signal cell completion
1094 begin
1096 end
1098 begin
1100 exit;
1107 // has something to process in the current cell?
1109 begin
1110 // process cell
1112 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1113 // convert coords to map (to avoid ajdusting coords inside the loop)
1116 // process cell list
1118 begin
1121 begin
1126 begin
1127 // can we process this proxy?
1129 begin
1132 begin
1134 begin
1138 exit;
1140 end
1141 else
1142 begin
1143 // remember this hitpoint if it is nearer than an old one
1146 begin
1154 end
1155 else
1156 begin
1157 // this is possibly interesting proxy, set "has more to check" flag
1162 // next cell
1165 // still has something interesting in this cell?
1167 begin
1168 // nope, don't process this cell anymore; signal cell completion
1171 begin
1173 end
1175 begin
1177 exit;
1180 // convert coords to grid
1188 // ////////////////////////////////////////////////////////////////////////// //
1189 function TBodyGridBase.forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
1190 const
1192 var
1211 begin
1230 // `x` and `y` will be in grid coords
1234 // increase query counter
1237 begin
1238 // just in case of overflow
1244 // cache various things
1245 //tsize := mTileSize;
1251 // setup distance and flags
1254 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1257 // it is slightly faster this way
1261 // now trace
1263 begin
1264 // do one step
1267 // invariant: one of those always changed
1268 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1271 // invariant: we always doing a step
1273 begin
1274 // check for crossing tile/grid boundary
1276 begin
1277 // we're still in grid
1279 // check for tile edge crossing
1285 // crossed tile edge?
1287 begin
1288 // setup new cell index
1291 end
1292 else
1293 begin
1294 // out of grid
1299 // has something to process in the current cell?
1301 begin
1302 // process cell
1304 // convert coords to map (to avoid ajdusting coords inside the loop)
1307 // process cell list
1309 begin
1312 begin
1317 begin
1322 // next cell
1326 // convert coords to grid