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
34 private
35 const
39 private
40 type
43 private
50 private
60 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
62 private
63 //mTileSize: Integer;
66 private
79 private
100 public
101 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
104 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
113 // `false` if `body` is surely invalid
116 //WARNING: don't modify grid while any query is in progress (no checks are made!)
117 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
118 // no callback: return `true` on the first hit
119 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
121 //WARNING: don't modify grid while any query is in progress (no checks are made!)
122 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
123 // no callback: return `true` on the first hit
126 //WARNING: don't modify grid while any query is in progress (no checks are made!)
127 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
128 // cb with `(nil)` will be called before processing new tile
129 // no callback: return `true` on the nearest hit
130 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
131 function traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
135 //WARNING! no sanity checks!
148 implementation
150 uses
154 // ////////////////////////////////////////////////////////////////////////// //
155 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
158 // ////////////////////////////////////////////////////////////////////////// //
159 // you are not supposed to understand this
160 // returns `true` if there is an intersection, and enter coords
161 // enter coords will be equal to (x0, y0) if starting point is inside the box
162 // if result is `false`, `inx` and `iny` are undefined
163 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
164 var
176 begin
178 // why not
184 begin
185 // check this point
187 exit;
190 // check if staring point is inside the box
191 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
193 // clip rectange
199 // horizontal setup
201 begin
202 // from left to right
205 end
206 else
207 begin
208 // from right to left
218 // vertical setup
220 begin
221 // from top to bottom
224 end
225 else
226 begin
227 // from bottom to top
241 begin
250 end
251 else
252 begin
266 begin
267 // clip at top
273 begin
282 begin
283 // clip at left
294 begin
295 // clip at bottom
305 //if (term = xd) then exit; // this is the only point, get out of here
317 // ////////////////////////////////////////////////////////////////////////// //
318 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
319 begin
331 // ////////////////////////////////////////////////////////////////////////// //
332 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
333 var
335 begin
336 {
337 if aTileSize < 1 then aTileSize := 1;
338 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
339 mTileSize := aTileSize;
340 }
351 // init free list
353 begin
358 // init grid
360 // init proxies
368 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
373 begin
381 // ////////////////////////////////////////////////////////////////////////// //
383 var
385 begin
388 begin
392 begin
398 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);
402 // ////////////////////////////////////////////////////////////////////////// //
403 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
404 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
408 begin
409 // fix coords
417 begin
419 begin
422 end
423 else
424 begin
432 // ////////////////////////////////////////////////////////////////////////// //
434 begin
440 begin
442 begin
444 begin
446 end
447 else
448 begin
455 // ////////////////////////////////////////////////////////////////////////// //
457 var
459 begin
461 begin
462 // no free cells, want more
466 begin
477 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
482 begin
484 begin
485 //if mCells[idx].body = -1 then exit; // the thing that should not be
494 // ////////////////////////////////////////////////////////////////////////// //
495 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
496 var
499 begin
501 begin
502 // no free proxies, resize list
509 // get one from list
514 // add to used list
516 // statistics
522 begin
524 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
525 // add to free list
533 // ////////////////////////////////////////////////////////////////////////// //
534 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
535 const
537 var
540 begin
543 // fix coords
546 // go on
550 //tsize := mTileSize;
553 begin
557 begin
567 // ////////////////////////////////////////////////////////////////////////// //
569 var
574 begin
576 // add body to the given grid cell
579 begin
583 begin
585 begin
586 // can add here
589 exit;
593 // either no room, or no cell at all
602 var
604 begin
611 // absolutely not tested
613 var
617 begin
619 // find and remove cell
623 begin
628 begin
630 begin
631 // i found her!
633 begin
634 // this cell contains no elements, remove it
638 end
639 else
640 begin
641 // remove element from bucket
644 begin
660 // absolutely not tested
662 var
664 begin
671 // ////////////////////////////////////////////////////////////////////////// //
672 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
673 begin
681 begin
688 // ////////////////////////////////////////////////////////////////////////// //
690 var
693 begin
701 // did any corner crossed tile boundary?
706 begin
713 end
714 else
715 begin
724 var
727 begin
730 // check if tile coords was changed
735 begin
736 // crossed tile boundary, do heavy work
738 end
739 else
740 begin
741 // nothing to do with the grid, just fix coordinates
748 var
752 begin
755 // check if tile coords was changed
763 begin
764 // crossed tile boundary, do heavy work
766 end
767 else
768 begin
769 // nothing to do with the grid, just fix size
776 // ////////////////////////////////////////////////////////////////////////// //
777 // no callback: return `true` on the first hit
778 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
779 var
786 begin
791 // make coords (0,0)-based
797 // restore coords
801 // increase query counter
804 begin
805 // just in case of overflow
812 begin
815 begin
820 begin
822 begin
825 begin
827 end
828 else
829 begin
831 exit;
841 // ////////////////////////////////////////////////////////////////////////// //
842 // no callback: return `true` on the first hit
843 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
844 const
846 var
857 begin
866 // fix coords
871 //tsize := mTileSize;
876 // increase query counter
879 begin
880 // just in case of overflow
884 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
887 // go on
889 begin
893 begin
896 // process cells
899 begin
902 begin
908 //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
909 //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
910 begin
915 begin
917 end
918 else
919 begin
921 exit;
932 // ////////////////////////////////////////////////////////////////////////// //
933 // no callback: return `true` on the nearest hit
934 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
935 var
937 begin
942 // no callback: return `true` on the nearest hit
943 function TBodyGridBase.traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
944 const
946 var
970 begin
990 // `x` and `y` will be in grid coords
994 // increase query counter
997 begin
998 // just in case of overflow
1004 // cache various things
1005 //tsize := mTileSize;
1011 // setup distance and flags
1015 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1018 // it is slightly faster this way
1022 // now trace
1024 begin
1025 // prevs are always in map coords
1028 // do one step
1031 // invariant: one of those always changed
1032 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1035 // invariant: we always doing a step
1037 begin
1038 // check for crossing tile/grid boundary
1040 begin
1041 // we're still in grid
1043 // check for tile edge crossing
1049 // crossed tile edge?
1051 begin
1052 // had something in the cell we're leaving?
1054 begin
1055 // yes, signal cell completion
1057 begin
1059 end
1061 begin
1063 exit;
1066 // setup new cell index
1069 end
1070 else
1071 begin
1072 // out of grid, had something in the last processed cell?
1074 begin
1075 // yes, signal cell completion
1078 begin
1080 end
1082 begin
1084 exit;
1091 // has something to process in the current cell?
1093 begin
1094 // process cell
1096 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1097 // convert coords to map (to avoid ajdusting coords inside the loop)
1100 // process cell list
1102 begin
1105 begin
1110 begin
1111 // can we process this proxy?
1113 begin
1116 begin
1118 begin
1122 exit;
1124 end
1125 else
1126 begin
1127 // remember this hitpoint if it is nearer than an old one
1130 begin
1138 end
1139 else
1140 begin
1141 // this is possibly interesting proxy, set "has more to check" flag
1146 // next cell
1149 // still has something interesting in this cell?
1151 begin
1152 // nope, don't process this cell anymore; signal cell completion
1155 begin
1157 end
1159 begin
1161 exit;
1164 // convert coords to grid