X-Git-Url: http://deadsoftware.ru/gitweb?a=blobdiff_plain;f=src%2Fgame%2Fg_grid.pas;h=6017ad4b492dfbc436da477ccd41a685a3bca7b1;hb=b4a2614636a9cc12ce9766ec1e2bf04cd5bec0ea;hp=ed2406dce52482e18157b6738c0e089b782c565a;hpb=900057549a968ef66d21960f84283714e3c7eb5d;p=d2df-sdl.git diff --git a/src/game/g_grid.pas b/src/game/g_grid.pas index ed2406d..6017ad4 100644 --- a/src/game/g_grid.pas +++ b/src/game/g_grid.pas @@ -20,6 +20,7 @@ {.$DEFINE D2F_DEBUG_XXQ} {.$DEFINE D2F_DEBUG_MOVER} {$ENDIF} +{.$DEFINE GRID_USE_ORTHO_ACCEL} unit g_grid; interface @@ -87,10 +88,6 @@ type mProxyCount: Integer; // currently used mProxyMaxCount: Integer; - private - // optimized horizontal tracer - //function traceRayHOpt (out ex, ey: Integer; const ax0, ay0, ax1, ay1, x0, len, dx: Integer; cb: TGridRayQueryCB; tagmask: Integer): ITP; - public dbgShowTraceLog: Boolean; {$IF DEFINED(D2F_DEBUG)} @@ -155,8 +152,8 @@ type 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 traceRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload; - //function traceRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; 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) @@ -1287,7 +1284,10 @@ var f, ptag, distSq: Integer; x0, y0, x1, y1: Integer; // horizontal walker - wklen, wkstep, wkpos: Integer; + {$IFDEF GRID_USE_ORTHO_ACCEL} + wklen, wkstep: Integer; + hopt: Boolean; + {$ENDIF} begin result := Default(ITP); lastObj := Default(ITP); @@ -1509,29 +1509,37 @@ begin end; lq := mLastQuery; - // if this is strict horizontal/vertical trace, use optimized codepath - if (ay0 = ay1) then + {$IFDEF GRID_USE_ORTHO_ACCEL} + // if this is strict horizontal trace, use optimized codepath + if (ax0 = ax1) or (ay0 = ay1) then begin - //if dbgShowTraceLog then e_LogWritefln('!!!', []); - // horizontal trace - // for horizontal traces, we'll walk the whole tiles, calculating mindist once for each proxy in cell - // one step: - // while (xd <> term) do - // if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2; - // xd += stx; + // 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); - y := yptr^+miny; // it will never change + // one of those will never change + x := xptr^+minx; + y := yptr^+miny; {$IF DEFINED(D2F_DEBUG)} - if (y <> ay0) then raise Exception.Create('htrace fatal internal error'); + 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]); + 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 @@ -1539,7 +1547,7 @@ begin lastGA := ga; ccidx := mGrid[lastGA]; // convert coords to map (to avoid ajdusting coords inside the loop) - x := xptr^+minx; + if hopt then x := xptr^+minx else y := yptr^+miny; while (ccidx <> -1) do begin cc := @mCells[ccidx]; @@ -1549,13 +1557,15 @@ begin px := @mProxies[cc.bodies[f]]; ptag := px.mTag; if ((ptag and TagDisabled) = 0) and ((ptag and tagmask) <> 0) and (px.mQueryMark <> lq) and - (y >= px.mY) and (y < px.mY+px.mHeight) then // y should be inside + // 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; something that should not be - if (x > px.mX) and (x < px.mX+px.mWidth-1) then + // 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 - //raise Exception.Create('abosultely impossible embedding in htrace'); if assigned(cb) then begin if cb(px.mObj, ptag, x, y, x, y) then @@ -1565,6 +1575,7 @@ begin ey := prevy; exit; end; + x := xptr^+minx; end else begin @@ -1583,30 +1594,70 @@ begin continue; end; // remember this hitpoint if it is nearer than an old one - if (stx < 0) then wkpos := px.mX+px.mWidth else wkpos := px.mX-1; + 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 x := wkpos+1 else x := wkpos-1; - if cb(px.mObj, ptag, x, y, wkpos, y) then + 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, wkpos, y); + 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, wkpos, y, distSq, lastDistSq]); + 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 := wkpos; - ey := y; + ex := prevx; + ey := prevy; lastObj := px.mObj; end; end; @@ -1618,33 +1669,63 @@ begin if wasHit and not assigned(cb) then begin result := lastObj; exit; end; end; // skip to next tile - if (ax0 < ax1) then + if hopt 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); + 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 - // 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); + 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); @@ -2011,324 +2092,4 @@ begin end; -// ////////////////////////////////////////////////////////////////////////// // -(* -function TBodyGridBase.traceRayWhileIn (const x0, y0, x1, y1: Integer; tagmask: Integer=-1): ITP; overload; -var - ex, ey: Integer; -begin - result := traceRayWhileIn(ex, ey, x0, y0, x1, y1, tagmask); -end; - - -// FUCKIN' PASTA! -function TBodyGridBase.traceRayWhileIn (out ex, ey: Integer; const ax0, ay0, ax1, ay1: Integer; tagmask: Integer=-1): ITP; -const - tsize = mTileSize; -var - wx0, wy0, wx1, wy1: Integer; // window coordinates - stx, sty: Integer; // "steps" for x and y axes - dsx, dsy: Integer; // "lengthes" for x and y axes - dx2, dy2: Integer; // "double lengthes" for x and y axes - xd, yd: Integer; // current coord - e: Integer; // "error" (as in bresenham algo) - rem: Integer; - term: Integer; - xptr, yptr: PInteger; - xfixed: Boolean; - temp: Integer; - prevx, prevy: Integer; - lastDistSq: Integer; - ccidx, curci: Integer; - hasUntried: Boolean; - lastGA: Integer = -1; - ga, x, y: Integer; - lastObj: ITP; - wasHit: Boolean = false; - gw, gh, minx, miny, maxx, maxy: Integer; - cc: PGridCell; - px: PBodyProxyRec; - lq: LongWord; - f, ptag, distSq: Integer; - x0, y0, x1, y1: Integer; - inx, iny: Integer; -begin - result := Default(ITP); - lastObj := Default(ITP); - tagmask := tagmask and TagFullMask; - ex := ax1; // why not? - ey := ay1; // why not? - if (tagmask = 0) then exit; - - if (ax0 = ax1) and (ay0 = ay1) then exit; // doesn't matter - - // we should start inside - if (forEachAtPoint(ax0, ay0, nil, tagmask, @ptag) = nil) then - begin - ex := ax0; // why not? - ey := ay0; // why not? - exit; - end; - - lastDistSq := distanceSq(ax0, ay0, ax1, ay1)+1; - - gw := mWidth; - gh := mHeight; - minx := mMinX; - miny := mMinY; - maxx := gw*tsize-1; - maxy := gh*tsize-1; - - x0 := ax0; - y0 := ay0; - x1 := ax1; - y1 := ay1; - - // offset query coords to (0,0)-based - Dec(x0, minx); - Dec(y0, miny); - Dec(x1, minx); - Dec(y1, miny); - - // clip rectange - wx0 := 0; - wy0 := 0; - wx1 := maxx; - wy1 := maxy; - - // horizontal setup - if (x0 < x1) then - begin - // from left to right - if (x0 > wx1) or (x1 < wx0) then exit; // out of screen - stx := 1; // going right - end - else - begin - // from right to left - if (x1 > wx1) or (x0 < wx0) then exit; // out of screen - stx := -1; // going left - x0 := -x0; - x1 := -x1; - wx0 := -wx0; - wx1 := -wx1; - swapInt(wx0, wx1); - end; - - // vertical setup - if (y0 < y1) then - begin - // from top to bottom - if (y0 > wy1) or (y1 < wy0) then exit; // out of screen - sty := 1; // going down - end - else - begin - // from bottom to top - if (y1 > wy1) or (y0 < wy0) then exit; // out of screen - sty := -1; // going up - y0 := -y0; - y1 := -y1; - wy0 := -wy0; - wy1 := -wy1; - swapInt(wy0, wy1); - end; - - dsx := x1-x0; - dsy := y1-y0; - - if (dsx < dsy) then - begin - xptr := @yd; - yptr := @xd; - swapInt(x0, y0); - swapInt(x1, y1); - swapInt(dsx, dsy); - swapInt(wx0, wy0); - swapInt(wx1, wy1); - swapInt(stx, sty); - end - else - begin - xptr := @xd; - yptr := @yd; - end; - - dx2 := 2*dsx; - dy2 := 2*dsy; - xd := x0; - yd := y0; - e := 2*dsy-dsx; - term := x1; - - xfixed := false; - if (y0 < wy0) then - begin - // clip at top - temp := dx2*(wy0-y0)-dsx; - xd += temp div dy2; - rem := temp mod dy2; - if (xd > wx1) then exit; // x is moved out of clipping rect, nothing to do - if (xd+1 >= wx0) then - begin - yd := wy0; - e -= rem+dsx; - if (rem > 0) then begin Inc(xd); e += dy2; end; - xfixed := true; - end; - end; - - if (not xfixed) and (x0 < wx0) then - begin - // clip at left - temp := dy2*(wx0-x0); - yd += temp div dx2; - rem := temp mod dx2; - if (yd > wy1) or (yd = wy1) and (rem >= dsx) then exit; - xd := wx0; - e += rem; - if (rem >= dsx) then begin Inc(yd); e -= dx2; end; - end; - - if (y1 > wy1) then - begin - // clip at bottom - temp := dx2*(wy1-y0)+dsx; - term := x0+temp div dy2; - rem := temp mod dy2; - if (rem = 0) then Dec(term); - end; - - if (term > wx1) then term := wx1; // clip at right - - Inc(term); // draw last point - //if (term = xd) then exit; // this is the only point, get out of here - - if (sty = -1) then yd := -yd; - if (stx = -1) then begin xd := -xd; term := -term; end; - dx2 -= dy2; - - // first move, to skip starting point - // 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) and ((ptag and tagmask) <> 0) then result := nil; - exit; - end; - - prevx := xptr^+minx; - prevy := yptr^+miny; - - // increase query counter - Inc(mLastQuery); - if (mLastQuery = 0) then - begin - // just in case of overflow - mLastQuery := 1; - for f := 0 to High(mProxies) do mProxies[f].mQueryMark := 0; - end; - lq := mLastQuery; - - ccidx := -1; - // draw it; can omit checks - while (xd <> term) do - begin - // check cell(s) - // new tile? - ga := (yptr^ div tsize)*gw+(xptr^ div tsize); - if (ga <> lastGA) then - begin - // yes - lastGA := ga; - ccidx := mGrid[lastGA]; - // no objects in cell == exit - if (ccidx = -1) then exit; - end; - // has something to process in this tile? - if (ccidx <> -1) then - begin - // process cell - curci := ccidx; - // convert coords to map (to avoid ajdusting coords inside the loop) - x := xptr^+minx; - y := yptr^+miny; - wasHit := false; - // process cell list - while (curci <> -1) do - begin - cc := @mCells[curci]; - 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 (px.mQueryMark <> lq) then - begin -function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean; - // can we process this proxy? - if (x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight) then - begin - px.mQueryMark := lq; // mark as processed - if ((ptag and tagmask) = 0) then - begin - result := px.mObj; - ex := x; - ey := y; - exit; - end; - // march out of the panel/cell - while (xd <> term) do - begin - if (e >= 0) then begin yd += sty; e -= dx2; end else e += dy2; - xd += stx; - // new cell? - ga := (yptr^ div tsize)*gw+(xptr^ div tsize); - if (ga <> lastGA) then break; - // out of panel? - if not ((x >= px.mX) and (y >= px.mY) and (x < px.mX+px.mWidth) and (y < px.mY+px.mHeight)) then break; - end; - end; - end; - end; - // next cell - curci := cc.next; - end; - // still has something interesting in this cell? - if not hasUntried then - begin - // nope, don't process this cell anymore; signal cell completion - ccidx := -1; - if assigned(cb) then - begin - if cb(nil, 0, x, y, prevx, prevy) then begin result := lastObj; exit; end; - end - else if wasHit then - begin - result := lastObj; - exit; - end; - end; - end; - //putPixel(xptr^, yptr^); - // move coords - prevx := xptr^+minx; - prevy := yptr^+miny; - 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; -*) - - end.