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 {$DEFINE grid_use_buckets}
21 interface
24 type
28 public
29 type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
30 type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop
32 private
33 const
37 private
38 type
41 private
48 private
54 {$IFDEF grid_use_buckets}
56 {$ELSE}
58 {$ENDIF}
64 private
82 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=0): TBodyProxyId;
108 //WARNING: can't do recursive queries
111 //WARNING: can't do recursive queries
114 //WARNING: can't do recursive queries
115 // cb with `(nil)` will be called before processing new tile
116 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean; overload;
122 implementation
124 uses
128 // ////////////////////////////////////////////////////////////////////////// //
129 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
130 begin
142 // ////////////////////////////////////////////////////////////////////////// //
143 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
144 var
146 begin
160 // init free list
162 begin
163 {$IFDEF grid_use_buckets}
165 {$ELSE}
167 {$ENDIF}
171 // init grid
173 // init proxies
184 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
189 begin
198 var
200 begin
203 begin
207 begin
213 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);
218 var
220 begin
222 begin
223 // no free cells, want more
227 begin
228 {$IFDEF grid_use_buckets}
230 {$ELSE}
232 {$ENDIF}
241 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
246 begin
248 begin
249 //if mCells[idx].body = -1 then exit; // the thing that should not be
250 //mCells[idx].body := -1;
258 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
259 var
262 begin
264 begin
265 // no free proxies, resize list
272 // get one from list
277 // add to used list
279 // statistics
285 begin
287 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
288 // add to free list
297 var
299 begin
302 // fix coords
305 // go on
309 begin
313 begin
323 // ////////////////////////////////////////////////////////////////////////// //
324 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
325 var
331 begin
344 // increase query counter
347 begin
348 // just in case of overflow
355 begin
358 begin
362 begin
364 begin
376 // ////////////////////////////////////////////////////////////////////////// //
377 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean;
378 var
398 begin
403 // make coords (0,0)-based
427 // increase query counter
430 begin
431 // just in case of overflow
444 begin
451 begin
454 begin
455 // new cell
459 begin
464 end
465 else
466 begin
471 begin
475 begin
478 begin
482 begin
483 if (x+minx >= px.mX) and (y+miny >= px.mY) and (x+minx < px.mX+px.mWidth) and (y+miny < px.mY+px.mHeight) then
484 begin
488 end
489 else
490 begin
504 var
507 {$IFDEF grid_use_buckets}
510 {$ENDIF}
511 begin
513 // add body to the given grid cell
515 {$IFDEF grid_use_buckets}
517 begin
521 begin
523 begin
524 // can add here
527 exit;
531 // either no room, or no cell at all
537 {$ELSE}
539 //e_WriteLog(Format(' 01: allocated cell for grid coords (%d,%d), body coords:(%d,%d): #%d', [gx, gy, dx, dy, cidx]), MSG_NOTIFY);
543 {$ENDIF}
548 var
550 begin
559 var
562 begin
564 // find and remove cell
568 begin
570 {$IFDEF grid_use_buckets}
574 begin
576 begin
577 // i found her!
579 begin
580 // this cell contains no elements, remove it
584 end
585 else
586 begin
587 // remove element from bucket
590 begin
601 {$ELSE}
603 begin
608 {$ENDIF}
615 // absolutely not tested
617 var
619 begin
627 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
628 begin
635 begin
643 var
645 begin
658 begin
663 begin
668 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
669 var
679 begin
686 // fix coords
696 // increase query counter
699 begin
700 // just in case of overflow
704 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
707 // go on
709 begin
713 begin
716 // process cells
719 begin
722 begin
726 begin