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
30 type TGridAlongQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop
35 private
36 const
40 private
41 type
44 private
51 private
61 TGridInternalCB = function (grida: Integer; bodyId: TBodyProxyId): Boolean of object; // return `true` to stop
63 private
64 //mTileSize: Integer;
67 private
80 public
83 private
104 public
105 constructor Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
108 function insertBody (aObj: ITP; ax, ay, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
117 // `false` if `body` is surely invalid
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 // no callback: return `true` on the first hit
123 function forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
125 //WARNING: don't modify grid while any query is in progress (no checks are made!)
126 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
127 // no callback: return `true` on the first hit
130 //WARNING: don't modify grid while any query is in progress (no checks are made!)
131 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
132 // cb with `(nil)` will be called before processing new tile
133 // no callback: return `true` on the nearest hit
134 function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload;
135 function traceRay (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
137 //WARNING: don't modify grid while any query is in progress (no checks are made!)
138 // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it)
139 // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order
140 function forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
144 //WARNING! no sanity checks!
154 // you are not supposed to understand this
155 // returns `true` if there is an intersection, and enter coords
156 // enter coords will be equal to (x0, y0) if starting point is inside the box
157 // if result is `false`, `inx` and `iny` are undefined
158 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer; log: Boolean=false): Boolean;
165 implementation
167 uses
171 // ////////////////////////////////////////////////////////////////////////// //
172 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
174 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
177 // ////////////////////////////////////////////////////////////////////////// //
178 // you are not supposed to understand this
179 // returns `true` if there is an intersection, and enter coords
180 // enter coords will be equal to (x0, y0) if starting point is inside the box
181 // if result is `false`, `inx` and `iny` are undefined
182 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer; log: Boolean=false): Boolean;
183 var
195 begin
197 // why not
203 begin
204 // check this point
206 exit;
209 // check if staring point is inside the box
210 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
212 // clip rectange
219 // horizontal setup
221 begin
222 // from left to right
225 end
226 else
227 begin
228 // from right to left
239 // vertical setup
241 begin
242 // from top to bottom
245 end
246 else
247 begin
248 // from bottom to top
262 begin
271 end
272 else
273 begin
288 begin
289 // clip at top
295 begin
305 begin
306 // clip at left
318 begin
319 // clip at bottom
329 //if (term = xd) then exit; // this is the only point, get out of here
342 // ////////////////////////////////////////////////////////////////////////// //
343 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
344 begin
356 // ////////////////////////////////////////////////////////////////////////// //
357 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
358 var
360 begin
362 {
363 if aTileSize < 1 then aTileSize := 1;
364 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
365 mTileSize := aTileSize;
366 }
377 // init free list
379 begin
384 // init grid
386 // init proxies
394 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
399 begin
407 // ////////////////////////////////////////////////////////////////////////// //
409 var
411 begin
414 begin
418 begin
424 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);
428 // ////////////////////////////////////////////////////////////////////////// //
429 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
430 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
434 begin
435 // fix coords
443 begin
445 begin
448 end
449 else
450 begin
458 // ////////////////////////////////////////////////////////////////////////// //
460 begin
466 begin
468 begin
470 begin
472 end
473 else
474 begin
481 // ////////////////////////////////////////////////////////////////////////// //
483 var
485 begin
487 begin
488 // no free cells, want more
492 begin
503 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
508 begin
510 begin
511 //if mCells[idx].body = -1 then exit; // the thing that should not be
520 // ////////////////////////////////////////////////////////////////////////// //
521 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
522 var
525 begin
527 begin
528 // no free proxies, resize list
535 // get one from list
540 // add to used list
542 // statistics
548 begin
550 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
551 // add to free list
559 // ////////////////////////////////////////////////////////////////////////// //
560 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
561 const
563 var
566 begin
569 // fix coords
572 // go on
576 //tsize := mTileSize;
579 begin
583 begin
593 // ////////////////////////////////////////////////////////////////////////// //
595 var
600 begin
602 // add body to the given grid cell
605 begin
609 begin
611 begin
612 // can add here
615 exit;
619 // either no room, or no cell at all
628 var
630 begin
637 // absolutely not tested
639 var
643 begin
645 // find and remove cell
649 begin
654 begin
656 begin
657 // i found her!
659 begin
660 // this cell contains no elements, remove it
664 end
665 else
666 begin
667 // remove element from bucket
670 begin
686 // absolutely not tested
688 var
690 begin
697 // ////////////////////////////////////////////////////////////////////////// //
698 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
699 begin
707 begin
714 // ////////////////////////////////////////////////////////////////////////// //
716 var
719 begin
727 // did any corner crossed tile boundary?
732 begin
739 end
740 else
741 begin
750 var
753 begin
756 // check if tile coords was changed
761 begin
762 // crossed tile boundary, do heavy work
764 end
765 else
766 begin
767 // nothing to do with the grid, just fix coordinates
774 var
778 begin
781 // check if tile coords was changed
789 begin
790 // crossed tile boundary, do heavy work
792 end
793 else
794 begin
795 // nothing to do with the grid, just fix size
802 // ////////////////////////////////////////////////////////////////////////// //
803 // no callback: return `true` on the first hit
804 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
805 var
812 begin
817 // make coords (0,0)-based
823 // restore coords
827 // increase query counter
830 begin
831 // just in case of overflow
838 begin
841 begin
846 begin
848 begin
851 begin
853 end
854 else
855 begin
857 exit;
867 // ////////////////////////////////////////////////////////////////////////// //
868 // no callback: return `true` on the first hit
869 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
870 const
872 var
883 begin
892 // fix coords
897 //tsize := mTileSize;
902 // increase query counter
905 begin
906 // just in case of overflow
910 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
913 // go on
915 begin
919 begin
922 // process cells
925 begin
928 begin
934 //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
935 //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
936 begin
941 begin
943 end
944 else
945 begin
947 exit;
958 // ////////////////////////////////////////////////////////////////////////// //
959 // no callback: return `true` on the nearest hit
960 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
961 var
963 begin
968 // no callback: return `true` on the nearest hit
969 // you are not supposed to understand this
970 function TBodyGridBase.traceRay (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
971 const
973 var
999 begin
1007 if (ax0 = ax1) and (ay0 = ay1) then exit; // as the first point is ignored, just get outta here
1023 // offset query coords to (0,0)-based
1029 // clip rectange
1035 // horizontal setup
1037 begin
1038 // from left to right
1041 end
1042 else
1043 begin
1044 // from right to left
1054 // vertical setup
1056 begin
1057 // from top to bottom
1060 end
1061 else
1062 begin
1063 // from bottom to top
1077 begin
1086 end
1087 else
1088 begin
1102 begin
1103 // clip at top
1109 begin
1118 begin
1119 // clip at left
1130 begin
1131 // clip at bottom
1141 //if (term = xd) then exit; // this is the only point, get out of here
1147 // first move, to skip starting point
1151 // move coords
1154 // done?
1157 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ > mHeight*tsize) then raise Exception.Create('raycaster internal error (0)');
1159 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1161 // restore query coords
1164 //Inc(ax1, minx);
1165 //Inc(ay1, miny);
1167 // increase query counter
1170 begin
1171 // just in case of overflow
1178 // draw it; can omit checks
1180 begin
1181 // check cell(s)
1182 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ > mHeight*tsize) then raise Exception.Create('raycaster internal error (0)');
1183 // new tile?
1186 begin
1187 // yes
1189 begin
1190 // signal cell completion
1192 begin
1194 end
1196 begin
1198 exit;
1204 // has something to process in this tile?
1206 begin
1207 // process cell
1209 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1210 // convert coords to map (to avoid ajdusting coords inside the loop)
1213 // process cell list
1215 begin
1218 begin
1223 begin
1224 // can we process this proxy?
1226 begin
1229 begin
1231 begin
1235 exit;
1237 end
1238 else
1239 begin
1240 // remember this hitpoint if it is nearer than an old one
1243 begin
1251 end
1252 else
1253 begin
1254 // this is possibly interesting proxy, set "has more to check" flag
1259 // next cell
1262 // still has something interesting in this cell?
1264 begin
1265 // nope, don't process this cell anymore; signal cell completion
1268 begin
1270 end
1272 begin
1274 exit;
1278 //putPixel(xptr^, yptr^);
1279 // move coords
1288 // ////////////////////////////////////////////////////////////////////////// //
1289 //FIXME! optimize this with real tile walking
1290 function TBodyGridBase.forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
1291 const
1293 var
1312 begin
1331 // `x` and `y` will be in grid coords
1335 // increase query counter
1338 begin
1339 // just in case of overflow
1345 // cache various things
1346 //tsize := mTileSize;
1352 // setup distance and flags
1355 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1358 // it is slightly faster this way
1362 // now trace
1364 begin
1365 // do one step
1368 // invariant: one of those always changed
1369 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1372 // invariant: we always doing a step
1374 begin
1375 // check for crossing tile/grid boundary
1377 begin
1378 // we're still in grid
1380 // check for tile edge crossing
1386 // crossed tile edge?
1388 begin
1389 // setup new cell index
1392 end
1393 else
1394 begin
1395 // out of grid
1400 // has something to process in the current cell?
1402 begin
1403 // process cell
1405 // convert coords to map (to avoid ajdusting coords inside the loop)
1408 // process cell list
1410 begin
1413 begin
1418 begin
1423 // next cell
1427 // convert coords to grid