6ff288c5de2d2549fc98e0dd4a8be0e7e67bd2cf
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): Boolean;
164 implementation
166 uses
170 // ////////////////////////////////////////////////////////////////////////// //
171 procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end;
173 function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end;
176 // ////////////////////////////////////////////////////////////////////////// //
177 // you are not supposed to understand this
178 // returns `true` if there is an intersection, and enter coords
179 // enter coords will be equal to (x0, y0) if starting point is inside the box
180 // if result is `false`, `inx` and `iny` are undefined
181 function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean;
182 var
190 //!term: Integer;
194 begin
196 // why not
202 begin
203 // check this point
205 exit;
208 // check if staring point is inside the box
209 if (x0 >= bx) and (y0 >= by) and (x0 < bx+bw) and (y0 < by+bh) then begin result := true; exit; end;
211 // clip rectange
217 // horizontal setup
219 begin
220 // from left to right
223 end
224 else
225 begin
226 // from right to left
236 // vertical setup
238 begin
239 // from top to bottom
242 end
243 else
244 begin
245 // from bottom to top
259 begin
268 end
269 else
270 begin
280 //!term := x1;
284 begin
285 // clip at top
291 begin
300 begin
301 // clip at left
311 (*
312 if (y1 > wy1) then
313 begin
314 // clip at bottom
315 temp := dx2*(wy1-y0)+dsx;
316 term := x0+temp div dy2;
317 rem := temp mod dy2;
318 if (rem = 0) then Dec(term);
319 end;
321 if (term > wx1) then term := wx1; // clip at right
323 Inc(term); // draw last point
324 //if (term = xd) then exit; // this is the only point, get out of here
325 *)
329 //!dx2 -= dy2;
337 // ////////////////////////////////////////////////////////////////////////// //
338 procedure TBodyGridBase.TBodyProxyRec.setup (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer);
339 begin
351 // ////////////////////////////////////////////////////////////////////////// //
352 constructor TBodyGridBase.Create (aMinPixX, aMinPixY, aPixWidth, aPixHeight: Integer{; aTileSize: Integer=GridDefaultTileSize});
353 var
355 begin
357 {
358 if aTileSize < 1 then aTileSize := 1;
359 if aTileSize > 8192 then aTileSize := 8192; // arbitrary limit
360 mTileSize := aTileSize;
361 }
372 // init free list
374 begin
379 // init grid
381 // init proxies
389 e_WriteLog(Format('created grid with size: %dx%d (tile size: %d); pix: %dx%d', [mWidth, mHeight, mTileSize, mWidth*mTileSize, mHeight*mTileSize]), MSG_NOTIFY);
394 begin
402 // ////////////////////////////////////////////////////////////////////////// //
404 var
406 begin
409 begin
413 begin
419 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);
423 // ////////////////////////////////////////////////////////////////////////// //
424 function TBodyGridBase.getGridWidthPx (): Integer; inline; begin result := mWidth*mTileSize; end;
425 function TBodyGridBase.getGridHeightPx (): Integer; inline; begin result := mHeight*mTileSize; end;
429 begin
430 // fix coords
438 begin
440 begin
443 end
444 else
445 begin
453 // ////////////////////////////////////////////////////////////////////////// //
455 begin
461 begin
463 begin
465 begin
467 end
468 else
469 begin
476 // ////////////////////////////////////////////////////////////////////////// //
478 var
480 begin
482 begin
483 // no free cells, want more
487 begin
498 //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY);
503 begin
505 begin
506 //if mCells[idx].body = -1 then exit; // the thing that should not be
515 // ////////////////////////////////////////////////////////////////////////// //
516 function TBodyGridBase.allocProxy (aX, aY, aWidth, aHeight: Integer; aObj: ITP; aTag: Integer): TBodyProxyId;
517 var
520 begin
522 begin
523 // no free proxies, resize list
530 // get one from list
535 // add to used list
537 // statistics
543 begin
545 if (mProxyCount = 0) then raise Exception.Create('wutafuuuuu in grid (no allocated proxies, what i should free now?)');
546 // add to free list
554 // ////////////////////////////////////////////////////////////////////////// //
555 function TBodyGridBase.forGridRect (x, y, w, h: Integer; cb: TGridInternalCB; bodyId: TBodyProxyId): Boolean;
556 const
558 var
561 begin
564 // fix coords
567 // go on
571 //tsize := mTileSize;
574 begin
578 begin
588 // ////////////////////////////////////////////////////////////////////////// //
590 var
595 begin
597 // add body to the given grid cell
600 begin
604 begin
606 begin
607 // can add here
610 exit;
614 // either no room, or no cell at all
623 var
625 begin
632 // absolutely not tested
634 var
638 begin
640 // find and remove cell
644 begin
649 begin
651 begin
652 // i found her!
654 begin
655 // this cell contains no elements, remove it
659 end
660 else
661 begin
662 // remove element from bucket
665 begin
681 // absolutely not tested
683 var
685 begin
692 // ////////////////////////////////////////////////////////////////////////// //
693 function TBodyGridBase.insertBody (aObj: ITP; aX, aY, aWidth, aHeight: Integer; aTag: Integer=-1): TBodyProxyId;
694 begin
702 begin
709 // ////////////////////////////////////////////////////////////////////////// //
711 var
714 begin
722 // did any corner crossed tile boundary?
727 begin
734 end
735 else
736 begin
745 var
748 begin
750 // check if tile coords was changed
756 begin
757 // crossed tile boundary, do heavy work
762 end
763 else
764 begin
765 // nothing to do with the grid, just fix coordinates
772 var
775 begin
777 // check if tile coords was changed
785 begin
786 // crossed tile boundary, do heavy work
791 end
792 else
793 begin
794 // nothing to do with the grid, just fix size
801 // ////////////////////////////////////////////////////////////////////////// //
802 // no callback: return `true` on the first hit
803 function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP;
804 var
811 begin
816 // make coords (0,0)-based
822 // restore coords
826 // increase query counter
829 begin
830 // just in case of overflow
837 begin
840 begin
845 begin
847 begin
850 begin
852 end
853 else
854 begin
856 exit;
866 // ////////////////////////////////////////////////////////////////////////// //
867 // no callback: return `true` on the first hit
868 function TBodyGridBase.forEachInAABB (x, y, w, h: Integer; cb: TGridQueryCB; tagmask: Integer=-1; allowDisabled: Boolean=false): ITP;
869 const
871 var
882 begin
891 // fix coords
896 //tsize := mTileSize;
901 // increase query counter
904 begin
905 // just in case of overflow
909 //e_WriteLog(Format('grid: query #%d: (%d,%d)-(%dx%d)', [mLastQuery, minx, miny, maxx, maxy]), MSG_NOTIFY);
912 // go on
914 begin
918 begin
921 // process cells
924 begin
927 begin
933 //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
934 //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then
935 begin
940 begin
942 end
943 else
944 begin
946 exit;
957 // ////////////////////////////////////////////////////////////////////////// //
958 // no callback: return `true` on the nearest hit
959 function TBodyGridBase.traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
960 var
962 begin
967 // no callback: return `true` on the nearest hit
968 // you are not supposed to understand this
969 function TBodyGridBase.traceRay (out ex, ey: Integer; ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP;
970 const
972 var
998 begin
1006 if (ax0 = ax1) and (ay0 = ay1) then exit; // as the first point is ignored, just get outta here
1022 // offset query coords to (0,0)-based
1028 // clip rectange
1034 // horizontal setup
1036 begin
1037 // from left to right
1040 end
1041 else
1042 begin
1043 // from right to left
1053 // vertical setup
1055 begin
1056 // from top to bottom
1059 end
1060 else
1061 begin
1062 // from bottom to top
1076 begin
1085 end
1086 else
1087 begin
1101 begin
1102 // clip at top
1108 begin
1117 begin
1118 // clip at left
1129 begin
1130 // clip at bottom
1140 //if (term = xd) then exit; // this is the only point, get out of here
1146 // first move, to skip starting point
1150 // move coords
1153 // done?
1156 {$IF DEFINED(D2F_DEBUG)}
1157 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ > mHeight*tsize) then raise Exception.Create('raycaster internal error (0)');
1158 {$ENDIF}
1160 //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY);
1162 // restore query coords
1165 //Inc(ax1, minx);
1166 //Inc(ay1, miny);
1168 // increase query counter
1171 begin
1172 // just in case of overflow
1179 // draw it; can omit checks
1181 begin
1182 // check cell(s)
1183 {$IF DEFINED(D2F_DEBUG)}
1184 if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ > mHeight*tsize) then raise Exception.Create('raycaster internal error (0)');
1185 {$ENDIF}
1186 // new tile?
1189 begin
1190 // yes
1192 begin
1193 // signal cell completion
1195 begin
1197 end
1199 begin
1201 exit;
1207 // has something to process in this tile?
1209 begin
1210 // process cell
1212 hasUntried := false; // this will be set to `true` if we have some proxies we still want to process at the next step
1213 // convert coords to map (to avoid ajdusting coords inside the loop)
1216 // process cell list
1218 begin
1221 begin
1226 begin
1227 // can we process this proxy?
1229 begin
1232 begin
1234 begin
1238 exit;
1240 end
1241 else
1242 begin
1243 // remember this hitpoint if it is nearer than an old one
1246 begin
1254 end
1255 else
1256 begin
1257 // this is possibly interesting proxy, set "has more to check" flag
1262 // next cell
1265 // still has something interesting in this cell?
1267 begin
1268 // nope, don't process this cell anymore; signal cell completion
1271 begin
1273 end
1275 begin
1277 exit;
1281 //putPixel(xptr^, yptr^);
1282 // move coords
1291 // ////////////////////////////////////////////////////////////////////////// //
1292 //FIXME! optimize this with real tile walking
1293 function TBodyGridBase.forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP;
1294 const
1296 var
1315 begin
1334 // `x` and `y` will be in grid coords
1338 // increase query counter
1341 begin
1342 // just in case of overflow
1348 // cache various things
1349 //tsize := mTileSize;
1355 // setup distance and flags
1358 // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing)
1361 // it is slightly faster this way
1365 // now trace
1367 begin
1368 // do one step
1371 // invariant: one of those always changed
1372 {$IF DEFINED(D2F_DEBUG)}
1373 if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)');
1374 {$ENDIF}
1377 // invariant: we always doing a step
1378 {$IF DEFINED(D2F_DEBUG)}
1380 {$ENDIF}
1381 begin
1382 // check for crossing tile/grid boundary
1384 begin
1385 // we're still in grid
1387 // check for tile edge crossing
1393 // crossed tile edge?
1395 begin
1396 // setup new cell index
1399 end
1400 else
1401 begin
1402 // out of grid
1407 // has something to process in the current cell?
1409 begin
1410 // process cell
1412 // convert coords to map (to avoid ajdusting coords inside the loop)
1415 // process cell list
1417 begin
1420 begin
1425 begin
1430 // next cell
1434 // convert coords to grid