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
31 private
32 const
36 private
37 type
40 private
47 private
53 {$IFDEF grid_use_buckets}
55 {$ELSE}
57 {$ENDIF}
63 private
81 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;
114 implementation
116 uses
120 // ////////////////////////////////////////////////////////////////////////// //
121 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
122 begin
134 // ////////////////////////////////////////////////////////////////////////// //
135 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
136 var
138 begin
152 // init free list
154 begin
155 {$IFDEF grid_use_buckets}
157 {$ELSE}
159 {$ENDIF}
163 // init grid
165 // init proxies
176 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
181 begin
190 var
192 begin
195 begin
199 begin
205 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);
210 var
212 begin
214 begin
215 // no free cells, want more
219 begin
220 {$IFDEF grid_use_buckets}
222 {$ELSE}
224 {$ENDIF}
233 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
238 begin
240 begin
241 //if mCells[idx].body = -1 then exit; // the thing that should not be
242 //mCells[idx].body := -1;
250 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
251 var
254 begin
256 begin
257 // no free proxies, resize list
264 // get one from list
269 // add to used list
271 // statistics
277 begin
279 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
280 // add to free list
289 var
291 begin
294 // fix coords
297 // go on
301 begin
305 begin
315 var
318 {$IFDEF grid_use_buckets}
321 {$ENDIF}
322 begin
324 // add body to the given grid cell
326 {$IFDEF grid_use_buckets}
328 begin
332 begin
334 begin
335 // can add here
338 exit;
342 // either no room, or no cell at all
348 {$ELSE}
350 //e_WriteLog(Format(' 01: allocated cell for grid coords (%d,%d), body coords:(%d,%d): #%d', [gx, gy, dx, dy, cidx]), MSG_NOTIFY);
354 {$ENDIF}
359 var
362 begin
373 var
376 begin
378 // find and remove cell
382 begin
384 {$IFDEF grid_use_buckets}
388 begin
390 begin
391 // i found her!
393 begin
394 // this cell contains no elements, remove it
398 end
399 else
400 begin
401 // remove element from bucket
404 begin
415 {$ELSE}
417 begin
422 {$ENDIF}
429 // absolutely not tested
431 var
434 begin
444 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
445 begin
452 begin
460 var
462 begin
475 begin
480 begin
486 var
489 {$IFDEF grid_use_buckets}
492 {$ENDIF}
493 begin
497 begin
498 {$IFDEF grid_use_buckets}
501 begin
505 begin
506 //e_WriteLog(Format(' query #%d body hit: (%d,%d)-(%dx%d) tag:%d', [mLastQuery, mCells[idx].body.mX, mCells[idx].body.mY, mCells[idx].body.mWidth, mCells[idx].body.mHeight, mCells[idx].body.mTag]), MSG_NOTIFY);
512 {$ELSE}
514 begin
517 begin
518 //e_WriteLog(Format(' query #%d body hit: (%d,%d)-(%dx%d) tag:%d', [mLastQuery, mCells[idx].body.mX, mCells[idx].body.mY, mCells[idx].body.mWidth, mCells[idx].body.mHeight, mCells[idx].body.mTag]), MSG_NOTIFY);
524 {$ENDIF}
528 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
529 var
533 begin
537 // increase query counter
540 begin
541 // just in case of overflow
545 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);