e45fede6f34b818d9a9f41191fc0d0c8bef8e32b
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
97 public
98 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
101 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
110 //WARNING: don't modify grid while any query is in progress (no checks are made!)
111 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
112 // no callback: return `true` on the first hit
113 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
115 //WARNING: don't modify grid while any query is in progress (no checks are made!)
116 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
117 // no callback: return `true` on the first hit
120 //WARNING: don't modify grid while any query is in progress (no checks are made!)
121 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
122 // cb with `(nil)` will be called before processing new tile
123 // no callback: return `true` on the nearest hit
124 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
125 function traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
129 //WARNING! no sanity checks!
134 implementation
136 uses
140 // ////////////////////////////////////////////////////////////////////////// //
141 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
142 begin
154 // ////////////////////////////////////////////////////////////////////////// //
155 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
156 var
158 begin
159 {
160 if aTileSize < 1 then aTileSize := 1;
161 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
162 mTileSize := aTileSize;
163 }
174 // init free list
176 begin
181 // init grid
183 // init proxies
191 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
196 begin
205 var
207 begin
210 begin
214 begin
220 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);
225 begin
226 // fix coords
234 begin
240 begin
242 begin
244 begin
246 end
247 else
248 begin
256 var
258 begin
260 begin
261 // no free cells, want more
265 begin
276 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
281 begin
283 begin
284 //if mCells[idx].body = -1 then exit; // the thing that should not be
293 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
294 var
297 begin
299 begin
300 // no free proxies, resize list
307 // get one from list
312 // add to used list
314 // statistics
320 begin
322 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
323 // add to free list
331 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
332 const
334 var
337 begin
340 // fix coords
343 // go on
347 //tsize := mTileSize;
350 begin
354 begin
365 var
370 begin
372 // add body to the given grid cell
375 begin
379 begin
381 begin
382 // can add here
385 exit;
389 // either no room, or no cell at all
398 var
400 begin
407 // absolutely not tested
409 var
413 begin
415 // find and remove cell
419 begin
424 begin
426 begin
427 // i found her!
429 begin
430 // this cell contains no elements, remove it
434 end
435 else
436 begin
437 // remove element from bucket
440 begin
456 // absolutely not tested
458 var
460 begin
467 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
468 begin
476 begin
484 var
486 begin
499 begin
504 begin
509 // ////////////////////////////////////////////////////////////////////////// //
510 // no callback: return `true` on the first hit
511 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
512 var
519 begin
524 // make coords (0,0)-based
530 // restore coords
534 // increase query counter
537 begin
538 // just in case of overflow
545 begin
548 begin
553 begin
555 begin
558 begin
560 end
561 else
562 begin
564 exit;
574 // no callback: return `true` on the first hit
575 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
576 const
578 var
589 begin
598 // fix coords
603 //tsize := mTileSize;
608 // increase query counter
611 begin
612 // just in case of overflow
616 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
619 // go on
621 begin
625 begin
628 // process cells
631 begin
634 begin
640 //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
641 //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
642 begin
647 begin
649 end
650 else
651 begin
653 exit;
664 // ////////////////////////////////////////////////////////////////////////// //
665 // no callback: return `true` on the nearest hit
666 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
667 var
669 begin
674 // no callback: return `true` on the nearest hit
675 function TBodyGridBase.traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
676 const
678 var
702 begin
722 // `x` and `y` will be in grid coords
726 // increase query counter
729 begin
730 // just in case of overflow
736 // cache various things
737 //tsize := mTileSize;
743 // setup distance and flags
747 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
750 // it is slightly faster this way
754 // now trace
756 begin
757 // prevs are always in map coords
760 // do one step
763 // invariant: one of those always changed
767 // invariant: we always doing a step
769 begin
770 // check for crossing tile/grid boundary
772 begin
773 // we're still in grid
775 // check for tile edge crossing
781 // crossed tile edge?
783 begin
784 // had something in the cell we're leaving?
786 begin
787 // yes, signal cell completion
789 begin
791 end
793 begin
795 exit;
798 // setup new cell index
801 end
802 else
803 begin
804 // out of grid, had something in the last processed cell?
806 begin
807 // yes, signal cell completion
810 begin
812 end
814 begin
816 exit;
823 // has something to process in the current cell?
825 begin
826 // process cell
828 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
829 // convert coords to map (to avoid ajdusting coords inside the loop)
832 // process cell list
834 begin
837 begin
842 begin
843 // can we process this proxy?
845 begin
848 begin
850 begin
854 exit;
856 end
857 else
858 begin
859 // remember this hitpoint if it is nearer than an old one
862 begin
870 end
871 else
872 begin
873 // this is possibly interesting proxy, set "has more to check" flag
878 // next cell
881 // still has something interesting in this cell?
883 begin
884 // nope, don't process this cell anymore; signal cell completion
887 begin
889 end
891 begin
893 exit;
896 // convert coords to grid