X-Git-Url: http://deadsoftware.ru/gitweb?a=blobdiff_plain;ds=sidebyside;f=src%2Fgame%2Fg_grid.pas;h=6017ad4b492dfbc436da477ccd41a685a3bca7b1;hb=b4a2614636a9cc12ce9766ec1e2bf04cd5bec0ea;hp=2e7105e7729190fbe6e1062c834034beaa43de47;hpb=5599208111f3a6c4f303cb719a26e8e405e82a69;p=d2df-sdl.git diff --git a/src/game/g_grid.pas b/src/game/g_grid.pas index 2e7105e..6017ad4 100644 --- a/src/game/g_grid.pas +++ b/src/game/g_grid.pas @@ -17,7 +17,10 @@ {$INCLUDE ../shared/a_modes.inc} {$IF DEFINED(D2F_DEBUG)} {.$DEFINE D2F_DEBUG_RAYTRACE} + {.$DEFINE D2F_DEBUG_XXQ} + {.$DEFINE D2F_DEBUG_MOVER} {$ENDIF} +{.$DEFINE GRID_USE_ORTHO_ACCEL} unit g_grid; interface @@ -127,6 +130,8 @@ type // `false` if `body` is surely invalid function getBodyXY (body: TBodyProxyId; out rx, ry: Integer): Boolean; inline; + function getBodyWH (body: TBodyProxyId; out rw, rh: Integer): Boolean; inline; + function getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline; //WARNING: don't modify grid while any query is in progress (no checks are made!) // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it) @@ -135,19 +140,25 @@ type //WARNING: don't modify grid while any query is in progress (no checks are made!) // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it) - // no callback: return `true` on the first hit - function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; + // no callback: return object on the first hit or nil + function forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP; //WARNING: don't modify grid while any query is in progress (no checks are made!) // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it) // cb with `(nil)` will be called before processing new tile - // no callback: return `true` on the nearest hit + // no callback: return object of the nearest hit or nil + // if `inverted` is true, trace will register bodies *exluding* tagmask + //WARNING: don't change tags in callbacks here! function traceRay (const x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload; function traceRay (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; + //function traceOrthoRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload; + //function traceOrthoRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP; + //WARNING: don't modify grid while any query is in progress (no checks are made!) // you can set enabled/disabled flag, tho (but iterator can still return objects disabled inside it) // trace line along the grid, calling `cb` for all objects in passed cells, in no particular order + //WARNING: don't change tags in callbacks here! function forEachAlongLine (const x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1; log: Boolean=false): ITP; // debug @@ -395,6 +406,7 @@ begin for idx := 0 to High(mCells) do begin mCells[idx].bodies[0] := -1; + mCells[idx].bodies[GridCellBucketSize-1] := -1; // "has free room" flag mCells[idx].next := idx+1; end; mCells[High(mCells)].next := -1; // last cell @@ -446,7 +458,6 @@ procedure TBodyGridBase.forEachBodyCell (body: TBodyProxyId; cb: TCellQueryCB); var g, f, cidx: Integer; cc: PGridCell; - //px: PBodyProxyRec; begin if (body < 0) or (body > High(mProxies)) or not assigned(cb) then exit; for g := 0 to High(mGrid) do @@ -455,11 +466,10 @@ begin while (cidx <> -1) do begin cc := @mCells[cidx]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (cc.bodies[f] = -1) then break; if (cc.bodies[f] = body) then cb((g mod mWidth)*mTileSize+mMinX, (g div mWidth)*mTileSize+mMinY); - //px := @mProxies[cc.bodies[f]]; end; // next cell cidx := cc.next; @@ -482,7 +492,7 @@ begin while (cidx <> -1) do begin cc := @mCells[cidx]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (cc.bodies[f] = -1) then break; if cb(mProxies[cc.bodies[f]].mObj, mProxies[cc.bodies[f]].mTag) then begin result := mProxies[cc.bodies[f]].mObj; exit; end; @@ -523,6 +533,41 @@ begin end; +function TBodyGridBase.getBodyWH (body: TBodyProxyId; out rw, rh: Integer): Boolean; inline; +begin + if (body >= 0) and (body < Length(mProxies)) then + begin + with mProxies[body] do begin rw := mWidth; rh := mHeight; end; + result := true; + end + else + begin + rw := 0; + rh := 0; + result := false; + end; +end; + + +function TBodyGridBase.getBodyDims (body: TBodyProxyId; out rx, ry, rw, rh: Integer): Boolean; inline; +begin + if (body >= 0) and (body < Length(mProxies)) then + begin + with mProxies[body] do begin rx := mX; ry := mY; rw := mWidth; rh := mHeight; end; + result := true; + end + else + begin + rx := 0; + ry := 0; + rw := 0; + rh := 0; + result := false; + end; +end; + + + // ////////////////////////////////////////////////////////////////////////// // function TBodyGridBase.getProxyEnabled (pid: TBodyProxyId): Boolean; inline; begin @@ -560,7 +605,7 @@ begin for idx := mFreeCell to High(mCells) do begin mCells[idx].bodies[0] := -1; - mCells[idx].bodies[High(TGridCell.bodies)] := -1; // 'has free room' flag + mCells[idx].bodies[GridCellBucketSize-1] := -1; // 'has free room' flag mCells[idx].next := idx+1; end; mCells[High(mCells)].next := -1; // last cell @@ -569,7 +614,6 @@ begin pc := @mCells[result]; mFreeCell := pc.next; pc.next := -1; - //pc.bodies[0] := -1; Inc(mUsedCells); //e_WriteLog(Format('grid: allocated new cell #%d (total: %d)', [result, mUsedCells]), MSG_NOTIFY); end; @@ -582,7 +626,7 @@ begin with mCells[idx] do begin bodies[0] := -1; - bodies[High(TGridCell.bodies)] := -1; // 'has free room' flag + bodies[GridCellBucketSize-1] := -1; // 'has free room' flag next := mFreeCell; end; mFreeCell := idx; @@ -677,21 +721,42 @@ begin pc := mGrid[grida]; if (pc <> -1) then begin - pi := @mCells[pc]; - if (pi.bodies[High(TGridCell.bodies)] = -1) then + {$IF DEFINED(D2F_DEBUG)} + cidx := pc; + while (cidx <> -1) do + begin + pi := @mCells[cidx]; + for f := 0 to GridCellBucketSize-1 do + begin + if (pi.bodies[f] = -1) then break; + if (pi.bodies[f] = bodyId) then raise Exception.Create('trying to insert already inserted proxy'); + end; + cidx := pi.next; + end; + {$ENDIF} + cidx := pc; + while (cidx <> -1) do begin - // can add here - for f := 0 to High(TGridCell.bodies) do + pi := @mCells[cidx]; + // check "has room" flag + if (pi.bodies[GridCellBucketSize-1] = -1) then begin - if (pi.bodies[f] = -1) then + // can add here + for f := 0 to GridCellBucketSize-1 do begin - pi.bodies[f] := bodyId; - if (f+1 < Length(TGridCell.bodies)) then pi.bodies[f+1] := -1; - exit; + if (pi.bodies[f] = -1) then + begin + pi.bodies[f] := bodyId; + if (f+1 < GridCellBucketSize) then pi.bodies[f+1] := -1; + exit; + end; end; + raise Exception.Create('internal error in grid inserter'); end; - raise Exception.Create('internal error in grid inserter'); + // no room, go to next cell in list (if there is any) + cidx := pi.next; end; + // no room in cells, add new cell to list end; // either no room, or no cell at all cidx := allocCell(); @@ -726,7 +791,7 @@ begin while (cidx <> -1) do begin pc := @mCells[cidx]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (pc.bodies[f] = bodyId) then begin @@ -739,12 +804,12 @@ begin exit; end; // remove element from bucket - for c := f to High(TGridCell.bodies)-1 do + for c := f to GridCellBucketSize-2 do begin pc.bodies[c] := pc.bodies[c+1]; if (pc.bodies[c] = -1) then break; end; - pc.bodies[High(TGridCell.bodies)] := -1; // "has free room" flag + pc.bodies[GridCellBucketSize-1] := -1; // "has free room" flag exit; end; end; @@ -753,7 +818,6 @@ begin end; end; -// absolutely not tested procedure TBodyGridBase.removeInternal (body: TBodyProxyId); var px: PBodyProxyRec; @@ -793,7 +857,15 @@ begin y0 := px.mY; w := px.mWidth; h := px.mHeight; + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format('proxy #%d: MOVERESIZE: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d;nw=%d;nh=%d', [body, x0-mMinX, y0-mMinY, w, h, nx-mMinX, ny-mMinY, nw, nh]), MSG_NOTIFY); + {$ENDIF} if (nx = x0) and (ny = y0) and (nw = w) and (nh = h) then exit; + // map -> grid + Dec(x0, mMinX); + Dec(y0, mMinY); + Dec(nx, mMinX); + Dec(ny, mMinY); // did any corner crossed tile boundary? if (x0 div mTileSize <> nx div mTileSize) or (y0 div mTileSize <> ny div mTileSize) or @@ -801,16 +873,16 @@ begin ((y0+h) div mTileSize <> (ny+nh) div mTileSize) then begin removeInternal(body); - px.mX := nx; - px.mY := ny; + px.mX := nx+mMinX; + px.mY := ny+mMinY; px.mWidth := nw; px.mHeight := nh; insertInternal(body); end else begin - px.mX := nx; - px.mY := ny; + px.mX := nx+mMinX; + px.mY := ny+mMinY; px.mWidth := nw; px.mHeight := nh; end; @@ -835,9 +907,9 @@ begin if (nx = x0) and (ny = y0) then exit; // map -> grid Dec(x0, mMinX); - Dec(y0, mMinX); + Dec(y0, mMinY); Dec(nx, mMinX); - Dec(ny, mMinX); + Dec(ny, mMinY); // check for heavy work pw := px.mWidth; ph := px.mHeight; @@ -849,6 +921,9 @@ begin ogy1 := (y0+ph-1) div mTileSize; ngx1 := (nx+pw-1) div mTileSize; ngy1 := (ny+ph-1) div mTileSize; + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format('proxy #%d: checkmove: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [body, x0, y0, pw, ph, nx, ny, ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY); + {$ENDIF} if (ogx0 <> ngx0) or (ogy0 <> ngy0) or (ogx1 <> ngx1) or (ogy1 <> ngy1) then begin // crossed tile boundary, do heavy work @@ -856,7 +931,9 @@ begin gh := mHeight; // cycle with old rect, remove body where it is necessary // optimized for horizontal moves - //e_WriteLog(Format('og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format('proxy #%d: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [body, x0, y0, pw, ph, nx, ny, ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY); + {$ENDIF} // remove stale marks if not ((ogy0 >= gh) or (ogy1 < 0)) and not ((ogx0 >= gw) or (ogx1 < 0)) then @@ -865,7 +942,9 @@ begin if (ogy0 < 0) then ogy0 := 0; if (ogx1 > gw-1) then ogx1 := gw-1; if (ogy1 > gh-1) then ogy1 := gh-1; - //e_WriteLog(Format(' norm og:(%d,%d)-(%d,%d)', [ogx0, ogy0, ogx1, ogy1]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format(' norm og:(%d,%d)-(%d,%d)', [ogx0, ogy0, ogx1, ogy1]), MSG_NOTIFY); + {$ENDIF} for gx := ogx0 to ogx1 do begin if (gx < ngx0) or (gx > ngx1) then @@ -873,7 +952,9 @@ begin // this column is completely outside of new rect for gy := ogy0 to ogy1 do begin - //e_WriteLog(Format(' remove:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format(' remove0:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$ENDIF} remover(gy*gw+gx, body); end; end @@ -884,7 +965,9 @@ begin begin if (gy < ngy0) or (gy > ngy1) then begin - //e_WriteLog(Format(' remove:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format(' remove1:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$ENDIF} remover(gy*gw+gx, body); end; end; @@ -899,7 +982,9 @@ begin if (ngy0 < 0) then ngy0 := 0; if (ngx1 > gw-1) then ngx1 := gw-1; if (ngy1 > gh-1) then ngy1 := gh-1; - //e_WriteLog(Format(' norm ng:(%d,%d)-(%d,%d)', [ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format(' norm ng:(%d,%d)-(%d,%d)', [ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY); + {$ENDIF} for gx := ngx0 to ngx1 do begin if (gx < ogx0) or (gx > ogx1) then @@ -907,7 +992,9 @@ begin // this column is completely outside of old rect for gy := ngy0 to ngy1 do begin - //e_WriteLog(Format(' insert:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format(' insert0:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$ENDIF} inserter(gy*gw+gx, body); end; end @@ -918,7 +1005,9 @@ begin begin if (gy < ogy0) or (gy > ogy1) then begin - //e_WriteLog(Format(' insert:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format(' insert1:(%d,%d)', [gx, gy]), MSG_NOTIFY); + {$ENDIF} inserter(gy*gw+gx, body); end; end; @@ -926,6 +1015,12 @@ begin end; end; // done + end + else + begin + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format('proxy #%d: GRID OK: xg=%d;yg=%d;w=%d;h=%d;nx=%d;ny=%d og:(%d,%d)-(%d,%d); ng:(%d,%d)-(%d,%d)', [body, x0, y0, pw, ph, nx, ny, ogx0, ogy0, ogx1, ogy1, ngx0, ngy0, ngx1, ngy1]), MSG_NOTIFY); + {$ENDIF} end; // update coordinates px.mX := nx+mMinX; @@ -940,10 +1035,13 @@ begin if (body < 0) or (body > High(mProxies)) then exit; // just in case // check if tile coords was changed px := @mProxies[body]; - x0 := px.mX; - y0 := px.mY; + x0 := px.mX-mMinX; + y0 := px.mY-mMinY; w := px.mWidth; h := px.mHeight; + {$IF DEFINED(D2F_DEBUG_MOVER)} + e_WriteLog(Format('proxy #%d: RESIZE: xg=%d;yg=%d;w=%d;h=%d;nw=%d;nh=%d', [body, x0, y0, w, h, nw, nh]), MSG_NOTIFY); + {$ENDIF} if ((x0+w) div mTileSize <> (x0+nw) div mTileSize) or ((y0+h) div mTileSize <> (y0+nh) div mTileSize) then begin @@ -964,7 +1062,7 @@ end; // ////////////////////////////////////////////////////////////////////////// // // no callback: return `true` on the first hit -function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1): ITP; +function TBodyGridBase.forEachAtPoint (x, y: Integer; cb: TGridQueryCB; tagmask: Integer=-1; exittag: PInteger=nil): ITP; var f: Integer; idx, curci: Integer; @@ -974,15 +1072,25 @@ var ptag: Integer; begin result := Default(ITP); + if (exittag <> nil) then exittag^ := 0; tagmask := tagmask and TagFullMask; if (tagmask = 0) then exit; + {$IF DEFINED(D2F_DEBUG_XXQ)} + if (assigned(cb)) then e_WriteLog(Format('0: grid pointquery: (%d,%d)', [x, y]), MSG_NOTIFY); + {$ENDIF} + // make coords (0,0)-based Dec(x, mMinX); Dec(y, mMinY); if (x < 0) or (y < 0) or (x >= mWidth*mTileSize) or (y >= mHeight*mTileSize) then exit; curci := mGrid[(y div mTileSize)*mWidth+(x div mTileSize)]; + + {$IF DEFINED(D2F_DEBUG_XXQ)} + if (assigned(cb)) then e_WriteLog(Format('1: grid pointquery: (%d,%d) (%d,%d) %d', [x, y, (x div mTileSize), (y div mTileSize), curci]), MSG_NOTIFY); + {$ENDIF} + // restore coords Inc(x, mMinX); Inc(y, mMinY); @@ -997,26 +1105,44 @@ begin end; lq := mLastQuery; + {$IF DEFINED(D2F_DEBUG_XXQ)} + if (assigned(cb)) then e_WriteLog(Format('2: grid pointquery: (%d,%d); lq=%u', [x, y, lq]), MSG_NOTIFY); + {$ENDIF} + while (curci <> -1) do begin + {$IF DEFINED(D2F_DEBUG_XXQ)} + if (assigned(cb)) then e_WriteLog(Format(' cell #%d', [curci]), MSG_NOTIFY); + {$ENDIF} cc := @mCells[curci]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (cc.bodies[f] = -1) then break; px := @mProxies[cc.bodies[f]]; - ptag := px.mTag; - if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then + {$IF DEFINED(D2F_DEBUG_XXQ)} + if (assigned(cb)) then e_WriteLog(Format(' proxy #%d; qm:%u; tag:%08x; tagflag:%d %u', [cc.bodies[f], px.mQueryMark, px.mTag, (px.mTag and tagmask), LongWord(px.mObj)]), MSG_NOTIFY); + {$ENDIF} + // shit. has to do it this way, so i can change tag in callback + if (px.mQueryMark <> lq) then begin - if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then + px.mQueryMark := lq; + ptag := px.mTag; + if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and + (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then begin - px.mQueryMark := lq; if assigned(cb) then begin - if cb(px.mObj, ptag) then begin result := px.mObj; exit; end; + if cb(px.mObj, ptag) then + begin + result := px.mObj; + if (exittag <> nil) then exittag^ := ptag; + exit; + end; end else begin result := px.mObj; + if (exittag <> nil) then exittag^ := ptag; exit; end; end; @@ -1087,28 +1213,26 @@ begin while (curci <> -1) do begin cc := @mCells[curci]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (cc.bodies[f] = -1) then break; px := @mProxies[cc.bodies[f]]; + // shit. has to do it this way, so i can change tag in callback + if (px.mQueryMark = lq) then continue; + px.mQueryMark := lq; ptag := px.mTag; if (not allowDisabled) and ((ptag and TagDisabled) <> 0) then continue; - if ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then - //if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then - //if ( ((ptag and TagDisabled) = 0) = ignoreDisabled) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) then + if ((ptag and tagmask) = 0) then continue; + if (x0 >= px.mX+px.mWidth) or (y0 >= px.mY+px.mHeight) then continue; + if (x0+w <= px.mX) or (y0+h <= px.mY) then continue; + if assigned(cb) then begin - if (x0 >= px.mX+px.mWidth) or (y0 >= px.mY+px.mHeight) then continue; - if (x0+w <= px.mX) or (y0+h <= px.mY) then continue; - px.mQueryMark := lq; - if assigned(cb) then - begin - if cb(px.mObj, ptag) then begin result := px.mObj; exit; end; - end - else - begin - result := px.mObj; - exit; - end; + if cb(px.mObj, ptag) then begin result := px.mObj; exit; end; + end + else + begin + result := px.mObj; + exit; end; end; curci := cc.next; @@ -1159,6 +1283,11 @@ var lq: LongWord; f, ptag, distSq: Integer; x0, y0, x1, y1: Integer; + // horizontal walker + {$IFDEF GRID_USE_ORTHO_ACCEL} + wklen, wkstep: Integer; + hopt: Boolean; + {$ENDIF} begin result := Default(ITP); lastObj := Default(ITP); @@ -1167,7 +1296,15 @@ begin ey := ay1; // why not? if (tagmask = 0) then exit; - if (ax0 = ax1) and (ay0 = ay1) then exit; // as the first point is ignored, just get outta here + if (ax0 = ax1) and (ay0 = ay1) then + begin + result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag); + if (result <> nil) then + begin + if assigned(cb) and not cb(result, ptag, ax0, ay0, ax0, ay0) then result := Default(ITP); + end; + exit; + end; lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1; @@ -1312,29 +1449,54 @@ begin dx2 -= dy2; // first move, to skip starting point - if (xd = term) then exit; + // DON'T DO THIS! loop will take care of that + if (xd = term) then + begin + result := forEachAtPoint(ax0, ay0, nil, tagmask, @ptag); + if (result <> nil) then + begin + if assigned(cb) then + begin + if cb(result, ptag, ax0, ay0, ax0, ay0) then + begin + ex := ax0; + ey := ay0; + end + else + begin + result := nil; + end; + end + else + begin + ex := ax0; + ey := ay0; + end; + end; + exit; + end; + prevx := xptr^+minx; prevy := yptr^+miny; + (* // move coords if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2; xd += stx; // done? if (xd = term) then exit; + *) {$IF DEFINED(D2F_DEBUG)} if (xptr^ < 0) or (yptr^ < 0) or (xptr^ >= gw*tsize) and (yptr^ >= gh*tsize) then raise Exception.Create('raycaster internal error (0)'); {$ENDIF} - lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize); - ccidx := mGrid[lastGA]; + // DON'T DO THIS! loop will take care of that + //lastGA := (yptr^ div tsize)*gw+(xptr^ div tsize); + //ccidx := mGrid[lastGA]; {$IF DEFINED(D2F_DEBUG_RAYTRACE)} //if assigned(dbgRayTraceTileHitCB) then e_WriteLog('1:TRACING!', MSG_NOTIFY); {$ENDIF} - {$IF DEFINED(D2F_DEBUG_RAYTRACE)} - if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny); - {$ENDIF} - //if (dbgShowTraceLog) then e_WriteLog(Format('raycast start: (%d,%d)-(%d,%d); xptr^=%d; yptr^=%d', [ax0, ay0, ax1, ay1, xptr^, yptr^]), MSG_NOTIFY); // increase query counter @@ -1347,8 +1509,230 @@ begin end; lq := mLastQuery; + {$IFDEF GRID_USE_ORTHO_ACCEL} + // if this is strict horizontal trace, use optimized codepath + if (ax0 = ax1) or (ay0 = ay1) then + begin + // horizontal trace: walk the whole tiles, calculating mindist once for each proxy in cell + // stx < 0: going left, otherwise `stx` is > 0, and we're going right + // vertical trace: walk the whole tiles, calculating mindist once for each proxy in cell + // stx < 0: going up, otherwise `stx` is > 0, and we're going down + hopt := (ay0 = ay1); // horizontal? + if (stx < 0) then wklen := -(term-xd) else wklen := term-xd; + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln('optimized htrace; wklen=%d', [wklen]); + {$ENDIF} + ga := (yptr^ div tsize)*gw+(xptr^ div tsize); + // one of those will never change + x := xptr^+minx; + y := yptr^+miny; + {$IF DEFINED(D2F_DEBUG)} + if hopt then + begin + if (y <> ay0) then raise Exception.Create('htrace fatal internal error'); + end + else + begin + if (x <> ax0) then raise Exception.Create('vtrace fatal internal error'); + end; + {$ENDIF} + while (wklen > 0) do + begin + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' htrace; ga=%d; x=%d, y=%d; y=%d; y=%d', [ga, xptr^+minx, yptr^+miny, y, ay0]); + {$ENDIF} + // new tile? + if (ga <> lastGA) then + begin + lastGA := ga; + ccidx := mGrid[lastGA]; + // convert coords to map (to avoid ajdusting coords inside the loop) + if hopt then x := xptr^+minx else y := yptr^+miny; + while (ccidx <> -1) do + begin + cc := @mCells[ccidx]; + for f := 0 to GridCellBucketSize-1 do + begin + if (cc.bodies[f] = -1) then break; + px := @mProxies[cc.bodies[f]]; + ptag := px.mTag; + if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and + // constant coord should be inside + ((hopt and (y >= px.mY) and (y < px.mY+px.mHeight)) or + ((not hopt) and (x >= px.mX) and (x < px.mX+px.mWidth))) then + begin + px.mQueryMark := lq; // mark as processed + // inside the proxy? + if (hopt and (x > px.mX) and (x < px.mX+px.mWidth-1)) or + ((not hopt) and (y > px.mY) and (y < px.mY+px.mHeight-1)) then + begin + if assigned(cb) then + begin + if cb(px.mObj, ptag, x, y, x, y) then + begin + result := lastObj; + ex := prevx; + ey := prevy; + exit; + end; + x := xptr^+minx; + end + else + begin + distSq := distanceSq(ax0, ay0, x, y); + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' EMBEDDED hhit(%d): a=(%d,%d), h=(%d,%d), distsq=%d; lastsq=%d', [cc.bodies[f], ax0, ay0, x, y, distSq, lastDistSq]); + {$ENDIF} + if (distSq < lastDistSq) then + begin + ex := x; + ey := y; + result := px.mObj; + exit; + end; + end; + continue; + end; + // remember this hitpoint if it is nearer than an old one + if hopt then + begin + prevy := y; + if (stx < 0) then + begin + // going left + if (x < px.mX) then continue; + prevx := px.mX+px.mWidth; + end + else + begin + // going right + if (x > px.mX{+px.mWidth}) then continue; + prevx := px.mX-1; + end; + end + else + begin + prevx := x; + if (stx < 0) then + begin + // going up + if (y < px.mY) then continue; + prevy := px.mY+px.mHeight; + end + else + begin + // going down + if (y > px.mY{+px.mHeight}) then continue; + prevy := px.mY-1; + end; + end; + if assigned(cb) then + begin + if (stx < 0) then + begin + if hopt then x := prevx-1 else y := prevy-1; + end + else + begin + if hopt then x := prevx+1 else y := prevy+1; + end; + if cb(px.mObj, ptag, x, y, prevx, prevy) then + begin + result := lastObj; + ex := prevx; + ey := prevy; + exit; + end; + x := xptr^+minx; + y := yptr^+miny; + end + else + begin + distSq := distanceSq(ax0, ay0, prevx, prevy); + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' hhit(%d): a=(%d,%d), h=(%d,%d), p=(%d,%d), distsq=%d; lastsq=%d', [cc.bodies[f], ax0, ay0, x, y, prevx, prevy, distSq, lastDistSq]); + {$ENDIF} + if (distSq < lastDistSq) then + begin + wasHit := true; + lastDistSq := distSq; + ex := prevx; + ey := prevy; + lastObj := px.mObj; + end; + end; + end; + end; + // next cell + ccidx := cc.next; + end; + if wasHit and not assigned(cb) then begin result := lastObj; exit; end; + end; + // skip to next tile + if hopt then + begin + if (stx > 0) then + begin + // to the right + wkstep := ((xptr^ or (mTileSize-1))+1)-xptr^; + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' right step: wklen=%d; wkstep=%d', [wklen, wkstep]); + {$ENDIF} + if (wkstep >= wklen) then break; + Inc(xptr^, wkstep); + Inc(ga); + end + else + begin + // to the left + wkstep := xptr^-((xptr^ and (not (mTileSize-1)))-1); + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' left step: wklen=%d; wkstep=%d', [wklen, wkstep]); + {$ENDIF} + if (wkstep >= wklen) then break; + Dec(xptr^, wkstep); + Dec(ga); + end; + end + else + begin + if (stx > 0) then + begin + // to the down + wkstep := ((yptr^ or (mTileSize-1))+1)-yptr^; + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' down step: wklen=%d; wkstep=%d', [wklen, wkstep]); + {$ENDIF} + if (wkstep >= wklen) then break; + Inc(yptr^, wkstep); + Inc(ga, mHeight); + end + else + begin + // to the up + wkstep := yptr^-((yptr^ and (not (mTileSize-1)))-1); + {$IF DEFINED(D2F_DEBUG)} + if dbgShowTraceLog then e_LogWritefln(' up step: wklen=%d; wkstep=%d', [wklen, wkstep]); + {$ENDIF} + if (wkstep >= wklen) then break; + Dec(yptr^, wkstep); + Dec(ga, mHeight); + end; + end; + Dec(wklen, wkstep); + end; + // we can travel less than one cell + if wasHit and not assigned(cb) then result := lastObj else begin ex := ax1; ey := ay1; end; + exit; + end; + {$ENDIF} + + {$IF DEFINED(D2F_DEBUG_RAYTRACE)} + if assigned(dbgRayTraceTileHitCB) then dbgRayTraceTileHitCB((xptr^ div tsize*tsize)+minx, (yptr^ div tsize*tsize)+miny); + {$ENDIF} + ccidx := -1; - // draw it; can omit checks + // can omit checks while (xd <> term) do begin // check cell(s) @@ -1357,6 +1741,9 @@ begin {$ENDIF} // new tile? ga := (yptr^ div tsize)*gw+(xptr^ div tsize); + {$IF DEFINED(D2F_DEBUG_RAYTRACE)} + if assigned(dbgRayTraceTileHitCB) then e_WriteLog(Format(' xd=%d; term=%d; gx=%d; gy=%d; ga=%d; lastga=%d', [xd, term, xptr^, yptr^, ga, lastGA]), MSG_NOTIFY); + {$ENDIF} if (ga <> lastGA) then begin // yes @@ -1392,7 +1779,7 @@ begin while (curci <> -1) do begin cc := @mCells[curci]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (cc.bodies[f] = -1) then break; px := @mProxies[cc.bodies[f]]; @@ -1477,6 +1864,16 @@ begin if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2; xd += stx; end; + // we can travel less than one cell + if wasHit and not assigned(cb) then + begin + result := lastObj; + end + else + begin + ex := ax1; // why not? + ey := ay1; // why not? + end; end; @@ -1672,7 +2069,7 @@ begin while (curci <> -1) do begin cc := @mCells[curci]; - for f := 0 to High(TGridCell.bodies) do + for f := 0 to GridCellBucketSize-1 do begin if (cc.bodies[f] = -1) then break; px := @mProxies[cc.bodies[f]];