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
23 const
27 type
28 TGridQueryCB = function (obj: TObject; objx, objy, objw, objh: Integer; tag: Integer): Boolean is nested; // return `true` to stop
30 type
37 private
41 //mGrid: TBodyGrid;
45 private
48 public
49 //constructor Create (aGrid: TBodyGrid; aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer);
50 //destructor Destroy (); override;
58 //property grid: TBodyGrid read mGrid;
63 {$IFDEF grid_use_buckets}
65 {$ELSE}
67 {$ENDIF}
74 private
88 private
92 function allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer): TBodyProxy;
100 public
101 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
104 function insertBody (aObj: TObject; ax, ay, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxy;
113 //function getProxyForBody (aObj: TObject; x, y, w, h: Integer): TBodyProxy;
119 implementation
121 uses
125 // ////////////////////////////////////////////////////////////////////////// //
127 begin
139 // ////////////////////////////////////////////////////////////////////////// //
140 constructor TBodyGrid.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
141 var
143 begin
157 // init free list
159 begin
160 {$IFDEF grid_use_buckets}
162 {$ELSE}
164 {$ENDIF}
168 // init grid
170 // init proxies
178 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
183 begin
192 var
194 begin
197 begin
201 begin
207 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);
212 var
214 begin
216 begin
217 // no free cells, want more
221 begin
222 {$IFDEF grid_use_buckets}
224 {$ELSE}
226 {$ENDIF}
235 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
240 begin
242 begin
243 //if mCells[idx].body = -1 then exit; // the thing that should not be
244 //mCells[idx].body := -1;
252 function TBodyGrid.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: TObject; aTag: Integer): TBodyProxy;
253 var
256 begin
258 begin
259 // no free proxies, resize list
266 // get one from list
271 // add to used list
273 // statistics
279 begin
281 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
282 // add to free list
291 var
293 begin
296 // fix coords
299 // go on
303 begin
307 begin
319 var
322 {$IFDEF grid_use_buckets}
325 {$ENDIF}
326 begin
328 // add body to the given grid cell
330 {$IFDEF grid_use_buckets}
332 begin
336 begin
338 begin
339 // can add here
342 exit;
346 // either no room, or no cell at all
352 {$ELSE}
354 //e_WriteLog(Format(' 01: allocated cell for grid coords (%d,%d), body coords:(%d,%d): #%d', [gx, gy, dx, dy, cidx]), MSG_NOTIFY);
358 {$ENDIF}
361 var
363 begin
370 // absolutely not tested
373 (*
374 function remover (grida: Integer): Boolean;
375 var
376 pidx, idx, tmp: Integer;
377 begin
378 result := false; // never stop
379 // find and remove cell
380 pidx := -1;
381 idx := mGrid[grida];
382 while idx >= 0 do
383 begin
384 tmp := mCells[idx].next;
385 if (mCells[idx].body = body) then
386 begin
387 if (pidx = -1) then mGrid[grida] := tmp else mCells[pidx].next := tmp;
388 freeCell(idx);
389 break; // assume that we cannot have one object added to bucket twice
390 end
391 else
392 begin
393 pidx := idx;
394 end;
395 idx := tmp;
396 end;
397 end;
399 var
400 px: PBodyProxyRec;
401 *)
402 begin
403 (*
404 if (body < 0) or (body > High(mProxies)) then exit; // just in case
405 px := @mProxies[body];
406 forGridRect(px.mX, px.mY, px.mWidth, px.mHeight, remover);
407 *)
412 function TBodyGrid.insertBody (aObj: TObject; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxy;
413 begin
420 begin
428 var
430 begin
443 begin
448 begin
453 function TBodyGrid.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
455 var
458 {$IFDEF grid_use_buckets}
461 {$ENDIF}
462 begin
466 begin
467 {$IFDEF grid_use_buckets}
470 begin
474 begin
475 //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);
477 if (cb(px.mObj, px.mX, px.mY, px.mWidth, px.mHeight, px.mTag)) then begin result := true; exit; end;
481 {$ELSE}
483 begin
486 begin
487 //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);
489 if (cb(px.mObj, px.mX, px.mY, px.mWidth, px.mHeight, px.mTag)) then begin result := true; exit; end;
493 {$ENDIF}
497 var
499 begin
503 // increase query counter
506 begin
507 // just in case of overflow
511 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
517 (*
518 function TBodyGrid.getProxyForBody (aObj: TObject; x, y, w, h: Integer): TBodyProxy;
519 var
520 res: TBodyProxy = -1;
522 function iterator (grida: Integer): Boolean;
523 var
524 idx: Integer;
525 begin
526 result := false;
527 idx := mGrid[grida];
528 while idx >= 0 do
529 begin
530 if (mCells[idx].body <> -1) and (mProxies[mCells[idx].body].mObj = aObj) then
531 begin
532 result := true;
533 res := mCells[idx].body;
534 exit;
535 end;
536 idx := mCells[idx].next;
537 end;
538 end;
540 begin
541 result := -1;
542 if (aObj = nil) then exit;
543 forGridRect(x, y, w, h, iterator);
544 result := res;
545 end;
546 *)