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
35 {$IFDEF grid_use_buckets}
37 {$ENDIF}
39 private
40 type
43 private
50 private
56 {$IFDEF grid_use_buckets}
58 {$ELSE}
60 {$ENDIF}
66 private
84 private
99 public
100 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
103 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
110 //WARNING: can't do recursive queries
113 //WARNING: can't do recursive queries
116 //WARNING: can't do recursive queries
117 // cb with `(nil)` will be called before processing new tile
118 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean; overload;
124 implementation
126 uses
130 // ////////////////////////////////////////////////////////////////////////// //
131 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
132 begin
144 // ////////////////////////////////////////////////////////////////////////// //
145 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer; aTileSize: Integer=GridDefaultTileSize);
146 var
148 begin
162 // init free list
164 begin
165 {$IFDEF grid_use_buckets}
167 {$ELSE}
169 {$ENDIF}
173 // init grid
175 // init proxies
186 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
191 begin
200 var
202 begin
205 begin
209 begin
215 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);
220 var
222 begin
224 begin
225 // no free cells, want more
229 begin
230 {$IFDEF grid_use_buckets}
232 {$ELSE}
234 {$ENDIF}
242 {$IFDEF grid_use_buckets}
244 {$ELSE}
246 {$ENDIF}
248 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
253 begin
255 begin
256 //if mCells[idx].body = -1 then exit; // the thing that should not be
257 {$IFDEF grid_use_buckets}
259 {$ELSE}
261 {$ENDIF}
269 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
270 var
273 begin
275 begin
276 // no free proxies, resize list
283 // get one from list
288 // add to used list
290 // statistics
296 begin
298 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
299 // add to free list
308 var
311 begin
314 // fix coords
317 // go on
324 begin
328 begin
339 var
342 {$IFDEF grid_use_buckets}
345 {$ENDIF}
346 begin
348 // add body to the given grid cell
350 {$IFDEF grid_use_buckets}
352 begin
356 begin
358 begin
359 // can add here
362 exit;
366 // either no room, or no cell at all
372 {$ELSE}
374 //e_WriteLog(Format(' 01: allocated cell for grid coords (%d,%d), body coords:(%d,%d): #%d', [gx, gy, dx, dy, cidx]), MSG_NOTIFY);
378 {$ENDIF}
383 var
385 begin
394 var
395 {$IFDEF grid_use_buckets}
397 {$ENDIF}
399 {$IFDEF grid_use_buckets}
401 {$ENDIF}
402 begin
404 // find and remove cell
408 begin
410 {$IFDEF grid_use_buckets}
414 begin
416 begin
417 // i found her!
419 begin
420 // this cell contains no elements, remove it
424 end
425 else
426 begin
427 // remove element from bucket
430 begin
441 {$ELSE}
443 begin
448 {$ENDIF}
455 // absolutely not tested
457 var
459 begin
467 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=0): TBodyProxyId;
468 begin
475 begin
483 var
485 begin
498 begin
503 begin
508 // ////////////////////////////////////////////////////////////////////////// //
509 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
510 var
511 {$IFDEF grid_use_buckets}
513 {$ENDIF}
518 begin
522 // make coords (0,0)-based
528 // restore coords
532 // increase query counter
535 begin
536 // just in case of overflow
543 begin
545 {$IFDEF grid_use_buckets}
547 begin
551 begin
553 begin
560 {$ELSE}
562 begin
565 begin
567 begin
574 {$ENDIF}
580 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1): Boolean;
581 var
585 {$IFDEF grid_use_buckets}
587 {$ENDIF}
593 begin
600 // fix coords
610 // increase query counter
613 begin
614 // just in case of overflow
618 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
621 // go on
623 begin
627 begin
630 // process cells
633 begin
635 {$IFDEF grid_use_buckets}
637 begin
641 begin
649 {$ELSE}
651 begin
654 begin
655 if (x0 >= px.mX+px.mWidth) or (y0 >= px.mY+px.mHeight) or (x0+w <= px.mX) or (y0+h <= px.mY) then
656 begin
657 // no intersection
658 end
659 else
660 begin
667 {$ENDIF}
675 // ////////////////////////////////////////////////////////////////////////// //
676 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): Boolean;
677 var
699 begin
704 // make coords (0,0)-based
726 // increase query counter
729 begin
730 // just in case of overflow
743 begin
750 begin
753 begin
754 // new cell
757 {
758 if (ccidx <> -1) then
759 begin
760 result := cb(nil, 0, x+minx, y+miny, prevX, prevY);
761 if result then exit;
762 end;
763 }
765 end
766 else
767 begin
769 begin
777 begin
783 begin
785 {$IFDEF grid_use_buckets}
787 begin
791 begin
793 begin
797 end
798 else
799 begin
804 {$ELSE}
806 begin
809 begin
811 begin
815 end
816 else
817 begin
822 {$ENDIF}
826 begin
827 // don't process this cell anymore