From b4c47ccb9cb4d0773bd7da3f9614b6395c65db5a Mon Sep 17 00:00:00 2001 From: Ketmar Dark Date: Tue, 22 Aug 2017 20:45:18 +0300 Subject: [PATCH 1/1] no more tree traces (i hope); still not working right --- src/game/g_grid.pas | 162 ++++++++++++++++++++++++++++++++++++++++ src/game/g_monsters.pas | 46 +++--------- src/game/g_weapons.pas | 109 +++++++++++++++------------ src/shared/a_modes.inc | 1 + 4 files changed, 234 insertions(+), 84 deletions(-) diff --git a/src/game/g_grid.pas b/src/game/g_grid.pas index f5667d3..73341c0 100644 --- a/src/game/g_grid.pas +++ b/src/game/g_grid.pas @@ -27,6 +27,7 @@ type public type TGridQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop type TGridRayQueryCB = function (obj: ITP; tag: Integer; x, y, prevx, prevy: Integer): Boolean is nested; // return `true` to stop + type TGridAlongQueryCB = function (obj: ITP; tag: Integer): Boolean is nested; // return `true` to stop const TagDisabled = $40000000; const TagFullMask = $3fffffff; @@ -130,6 +131,11 @@ type function traceRay (x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; tagmask: Integer=-1): ITP; overload; function traceRay (out ex, ey: Integer; x0, y0, x1, y1: Integer; cb: TGridRayQueryCB; 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 + function forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP; + procedure dumpStats (); //WARNING! no sanity checks! @@ -142,7 +148,15 @@ type end; +// you are not supposed to understand this +// returns `true` if there is an intersection, and enter coords +// enter coords will be equal to (x0, y0) if starting point is inside the box +// if result is `false`, `inx` and `iny` are undefined +function lineAABBIntersects (x0, y0, x1, y1: Integer; bx, by, bw, bh: Integer; out inx, iny: Integer): Boolean; + + procedure swapInt (var a: Integer; var b: Integer); inline; +function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; implementation @@ -154,6 +168,8 @@ uses // ////////////////////////////////////////////////////////////////////////// // procedure swapInt (var a: Integer; var b: Integer); inline; var t: Integer; begin t := a; a := b; b := t; end; +function distanceSq (x0, y0, x1, y1: Integer): Integer; inline; begin result := (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0); end; + // ////////////////////////////////////////////////////////////////////////// // // you are not supposed to understand this @@ -1169,4 +1185,150 @@ begin end; +// ////////////////////////////////////////////////////////////////////////// // +function TBodyGridBase.forEachAlongLine (x0, y0, x1, y1: Integer; cb: TGridAlongQueryCB; tagmask: Integer=-1): ITP; +const + tsize = mTileSize; +var + i: Integer; + dx, dy, d: Integer; + xerr, yerr: Integer; + incx, incy: Integer; + stepx, stepy: Integer; + x, y: Integer; + maxx, maxy: Integer; + gw, gh: Integer; + ccidx: Integer; + curci: Integer; + cc: PGridCell; + px: PBodyProxyRec; + lq: LongWord; + minx, miny: Integer; + ptag: Integer; + lastWasInGrid: Boolean; + tbcross: Boolean; + f: Integer; +begin + result := Default(ITP); + tagmask := tagmask and TagFullMask; + if (tagmask = 0) then exit; + + minx := mMinX; + miny := mMinY; + + dx := x1-x0; + dy := y1-y0; + + if (dx > 0) then incx := 1 else if (dx < 0) then incx := -1 else incx := 0; + if (dy > 0) then incy := 1 else if (dy < 0) then incy := -1 else incy := 0; + + dx := abs(dx); + dy := abs(dy); + + if (dx > dy) then d := dx else d := dy; + + // `x` and `y` will be in grid coords + x := x0-minx; + y := y0-miny; + + // increase query counter + Inc(mLastQuery); + if (mLastQuery = 0) then + begin + // just in case of overflow + mLastQuery := 1; + for i := 0 to High(mProxies) do mProxies[i].mQueryMark := 0; + end; + lq := mLastQuery; + + // cache various things + //tsize := mTileSize; + gw := mWidth; + gh := mHeight; + maxx := gw*tsize-1; + maxy := gh*tsize-1; + + // setup distance and flags + lastWasInGrid := (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy); + + // setup starting tile ('cause we'll adjust tile vars only on tile edge crossing) + if lastWasInGrid then ccidx := mGrid[(y div tsize)*gw+(x div tsize)] else ccidx := -1; + + // it is slightly faster this way + xerr := -d; + yerr := -d; + + // now trace + for i := 1 to d do + begin + // do one step + xerr += dx; + yerr += dy; + // invariant: one of those always changed + if (xerr < 0) and (yerr < 0) then raise Exception.Create('internal bug in grid raycaster (0)'); + if (xerr >= 0) then begin xerr -= d; x += incx; stepx := incx; end else stepx := 0; + if (yerr >= 0) then begin yerr -= d; y += incy; stepy := incy; end else stepy := 0; + // invariant: we always doing a step + if ((stepx or stepy) = 0) then raise Exception.Create('internal bug in grid raycaster (1)'); + begin + // check for crossing tile/grid boundary + if (x >= 0) and (y >= 0) and (x <= maxx) and (y <= maxy) then + begin + // we're still in grid + lastWasInGrid := true; + // check for tile edge crossing + if (stepx < 0) and ((x mod tsize) = tsize-1) then tbcross := true + else if (stepx > 0) and ((x mod tsize) = 0) then tbcross := true + else if (stepy < 0) and ((y mod tsize) = tsize-1) then tbcross := true + else if (stepy > 0) and ((y mod tsize) = 0) then tbcross := true + else tbcross := false; + // crossed tile edge? + if tbcross then + begin + // setup new cell index + ccidx := mGrid[(y div tsize)*gw+(x div tsize)]; + end; + end + else + begin + // out of grid + if lastWasInGrid then exit; // oops, stepped out of the grid -- there is no way to return + end; + end; + + // has something to process in the current cell? + if (ccidx <> -1) then + begin + // process cell + curci := ccidx; + // convert coords to map (to avoid ajdusting coords inside the loop) + Inc(x, minx); + Inc(y, miny); + // process cell list + while (curci <> -1) do + begin + cc := @mCells[curci]; + for f := 0 to High(TGridCell.bodies) 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 + begin + px.mQueryMark := lq; // mark as processed + if cb(px.mObj, ptag) then begin result := px.mObj; exit; end; + end; + end; + // next cell + curci := cc.next; + end; + ccidx := -1; // don't process this anymore + // convert coords to grid + Dec(x, minx); + Dec(y, miny); + end; + end; +end; + + end. diff --git a/src/game/g_monsters.pas b/src/game/g_monsters.pas index 25b2555..dcb8dc0 100644 --- a/src/game/g_monsters.pas +++ b/src/game/g_monsters.pas @@ -206,7 +206,7 @@ function g_Mons_getNewTrapFrameId (): DWord; type - TMonsAlongLineCB = function (mon: TMonster; distSq: Integer): Boolean is nested; + TMonsAlongLineCB = function (mon: TMonster; tag: Integer): Boolean is nested; function g_Mons_alongLine (x0, y0, x1, y1: Integer; cb: TMonsAlongLineCB): TMonster; @@ -286,36 +286,9 @@ var function g_Mons_alongLine (x0, y0, x1, y1: Integer; cb: TMonsAlongLineCB): TMonster; -//!!!FIXME!!! -{ - function sqchecker (mon: TMonster; var ray: Ray2D): Single; - var - aabb: AABB2D; - tmin: Single; - begin - result := -666.0; // invalid - aabb := mon.mapAABB; - if not aabb.valid then exit; - if aabb.intersects(ray, @tmin) then - begin - if (tmin <= 0.0) then tmin := 0.0; - result := tmin; - if cb(mon, tmin) then result := 0.0; // instant stop - end; - end; - -var - qr: TDynAABBTreeMons.TSegmentQueryResult; -} begin - result := nil; -{ - if not assigned(cb) then exit; - if monsTree.segmentQuery(qr, x0, y0, x1, y1, sqchecker) then - begin - if (qr.flesh <> nil) then result := qr.flesh; - end; -} + if not assigned(cb) then begin result := nil; exit; end; + result := monsGrid.forEachAlongLine(x0, y0, x1, y1, cb); end; @@ -2019,14 +1992,17 @@ begin if (proxyId <> -1) then begin - monsGrid.removeBody(proxyId); - {$IF DEFINED(D2F_DEBUG_MONS_MOVE)} - e_WriteLog(Format('monster #%d(%u): removed from tree; proxyid=%d', [arrIdx, UID, proxyId]), MSG_NOTIFY); - {$ENDIF} + if (monsGrid <> nil) then + begin + monsGrid.removeBody(proxyId); + {$IF DEFINED(D2F_DEBUG_MONS_MOVE)} + e_WriteLog(Format('monster #%d(%u): removed from tree; proxyid=%d', [arrIdx, UID, proxyId]), MSG_NOTIFY); + {$ENDIF} + end; proxyId := -1; end; - if (arrIdx <> -1) then gMonsters[arrIdx] := nil; + if (arrIdx <> -1) and (arrIdx < Length(gMonsters)) then gMonsters[arrIdx] := nil; arrIdx := -1; uidMap[FUID] := nil; diff --git a/src/game/g_weapons.pas b/src/game/g_weapons.pas index 7f8f99d..fc9db75 100644 --- a/src/game/g_weapons.pas +++ b/src/game/g_weapons.pas @@ -128,7 +128,7 @@ uses Math, g_map, g_player, g_gfx, g_sound, g_main, g_panel, g_console, SysUtils, g_options, g_game, g_triggers, MAPDEF, e_log, g_monsters, g_saveload, - g_language, g_netmsg, + g_language, g_netmsg, g_grid, binheap, hashtable; type @@ -162,9 +162,10 @@ const type PHitTime = ^THitTime; THitTime = record - time: Single; + distSq: Integer; mon: TMonster; plridx: Integer; // if mon=nil + x, y: Integer; end; // indicies in `wgunHitTime` array @@ -172,7 +173,7 @@ type var WaterMap: array of array of DWORD = nil; - wgunMonHash: THashIntInt = nil; + //wgunMonHash: THashIntInt = nil; wgunHitHeap: TBinaryHeapHitTimes = nil; wgunHitTime: array of THitTime = nil; wgunHitTimeUsed: Integer = 0; @@ -180,8 +181,8 @@ var function hitTimeCompare (a, b: Integer): Boolean; begin - if (wgunHitTime[a].time < wgunHitTime[b].time) then begin result := true; exit; end; - if (wgunHitTime[a].time > wgunHitTime[b].time) then begin result := false; exit; end; + if (wgunHitTime[a].distSq < wgunHitTime[b].distSq) then begin result := true; exit; end; + if (wgunHitTime[a].distSq > wgunHitTime[b].distSq) then begin result := false; exit; end; if (wgunHitTime[a].mon <> nil) then begin // a is monster @@ -197,23 +198,33 @@ begin end; -procedure appendHitTimeMon (time: Single; mon: TMonster); +procedure appendHitTimeMon (adistSq: Integer; amon: TMonster; ax, ay: Integer); begin if (wgunHitTimeUsed = Length(wgunHitTime)) then SetLength(wgunHitTime, wgunHitTimeUsed+128); - wgunHitTime[wgunHitTimeUsed].time := time; - wgunHitTime[wgunHitTimeUsed].mon := mon; - wgunHitTime[wgunHitTimeUsed].plridx := -1; + with wgunHitTime[wgunHitTimeUsed] do + begin + distSq := adistSq; + mon := amon; + plridx := -1; + x := ax; + y := ay; + end; wgunHitHeap.insert(wgunHitTimeUsed); Inc(wgunHitTimeUsed); end; -procedure appendHitTimePlr (time: Single; plridx: Integer); +procedure appendHitTimePlr (adistSq: Integer; aplridx: Integer; ax, ay: Integer); begin if (wgunHitTimeUsed = Length(wgunHitTime)) then SetLength(wgunHitTime, wgunHitTimeUsed+128); - wgunHitTime[wgunHitTimeUsed].time := time; - wgunHitTime[wgunHitTimeUsed].mon := nil; - wgunHitTime[wgunHitTimeUsed].plridx := plridx; + with wgunHitTime[wgunHitTimeUsed] do + begin + distSq := adistSq; + mon := nil; + plridx := aplridx; + x := ax; + y := ay; + end; wgunHitHeap.insert(wgunHitTimeUsed); Inc(wgunHitTimeUsed); end; @@ -1151,7 +1162,7 @@ begin g_Texture_CreateWADEx('TEXTURE_SHELL_BULLET', GameWAD+':TEXTURES\EBULLET'); g_Texture_CreateWADEx('TEXTURE_SHELL_SHELL', GameWAD+':TEXTURES\ESHELL'); - wgunMonHash := hashNewIntInt(); + //wgunMonHash := hashNewIntInt(); wgunHitHeap := TBinaryHeapHitTimes.Create(hitTimeCompare); end; @@ -1369,13 +1380,12 @@ end; //!!!FIXME!!! procedure g_Weapon_gun (const x, y, xd, yd, v, dmg: Integer; SpawnerUID: Word; CheckTrigger: Boolean); -(* var - hitray: Ray2D; + x2, y2: Integer; xi, yi: Integer; - wallDistSq: Single = 1.0e100; + wallDistSq: Integer = $3fffffff; - function doPlayerHit (idx: Integer): Boolean; + function doPlayerHit (idx: Integer; hx, hy: Integer): Boolean; begin result := false; if (idx < 0) or (idx > High(gPlayers)) then exit; @@ -1387,7 +1397,7 @@ var {$ENDIF} end; - function doMonsterHit (mon: TMonster): Boolean; + function doMonsterHit (mon: TMonster; hx, hy: Integer): Boolean; begin result := false; if (mon = nil) then exit; @@ -1403,47 +1413,52 @@ var function playerPossibleHit (): Boolean; var i: Integer; - aabb: AABB2D; - tmin: Single; + px, py, pw, ph: Integer; + inx, iny: Integer; + distSq: Integer; + plr: TPlayer; begin result := false; for i := 0 to High(gPlayers) do begin - if (gPlayers[i] <> nil) and gPlayers[i].Live then + plr := gPlayers[i]; + if (plr <> nil) and plr.Live then begin - aabb := gPlayers[i].mapAABB; - // inside? - if aabb.contains(x, y) then - begin - if doPlayerHit(i) then begin result := true; exit; end; - end - else if (aabb.intersects(hitray, @tmin)) then + plr.getMapBox(px, py, pw, ph); + if lineAABBIntersects(x, y, x2, y2, px, py, pw, ph, inx, iny) then begin - // intersect - if (tmin <= 0.0) then + distSq := distanceSq(x, y, inx, iny); + if (distSq = 0) then begin - if doPlayerHit(i) then begin result := true; exit; end; + // contains + if doPlayerHit(i, x, y) then begin result := true; exit; end; end - else + else if (distSq < wallDistSq) then begin - if (tmin*tmin < wallDistSq) then appendHitTimePlr(tmin, i); + appendHitTimePlr(distSq, i, inx, iny); end; end; end; end; end; - function sqchecker (mon: TMonster; dist: Single): Boolean; + function sqchecker (mon: TMonster; tag: Integer): Boolean; + var + mx, my, mw, mh: Integer; + inx, iny: Integer; + distSq: Integer; begin result := false; // don't stop - if (dist*dist < wallDistSq) then appendHitTimeMon(dist, mon); + mon.getMapBox(mx, my, mw, mh); + if lineAABBIntersects(x, y, x2, y2, mx, my, mw, mh, inx, iny) then + begin + distSq := distanceSq(x, y, inx, iny); + if (distSq < wallDistSq) then appendHitTimeMon(distanceSq(x, y, inx, iny), mon, inx, iny); + end; end; -*) -(* var a: Integer; - x2, y2: Integer; dx, dy: Integer; xe, ye: Integer; s, c: Extended; @@ -1455,7 +1470,6 @@ var {$IF DEFINED(D2F_DEBUG)} stt: UInt64; {$ENDIF} -*) begin (* if not gwep_debug_fast_trace then @@ -1465,8 +1479,7 @@ begin end; *) -(* - wgunMonHash.reset(); //FIXME: clear hash on level change + //wgunMonHash.reset(); //FIXME: clear hash on level change wgunHitHeap.clear(); wgunHitTimeUsed := 0; @@ -1498,7 +1511,7 @@ begin begin x2 := wallHitX; y2 := wallHitY; - wallDistSq := (wallHitX-x)*(wallHitX-x)+(wallHitY-y)*(wallHitY-y); + wallDistSq := distanceSq(x, y, wallHitX, wallHitY); end else begin @@ -1506,8 +1519,6 @@ begin wallHitY := y2; end; - hitray := Ray2D.Create(x, y, x2, y2); - if playerPossibleHit() then exit; // instant hit // collect monsters @@ -1520,15 +1531,16 @@ begin // has some entities to check, do it i := wgunHitHeap.front; wgunHitHeap.popFront(); - hitray.atTime(wgunHitTime[i].time, xe, ye); + xe := wgunHitTime[i].x; + ye := wgunHitTime[i].y; // check if it is not behind the wall if (wgunHitTime[i].mon <> nil) then begin - didHit := doMonsterHit(wgunHitTime[i].mon); + didHit := doMonsterHit(wgunHitTime[i].mon, xe, ye); end else begin - didHit := doPlayerHit(wgunHitTime[i].plridx); + didHit := doPlayerHit(wgunHitTime[i].plridx, xe, ye); end; if didHit then begin @@ -1559,7 +1571,6 @@ begin end; if CheckTrigger and g_Game_IsServer then g_Triggers_PressL(X, Y, wallHitX, wallHitY, SpawnerUID, ACTIVATE_SHOT); -*) end; diff --git a/src/shared/a_modes.inc b/src/shared/a_modes.inc index 4853063..ee78b4f 100644 --- a/src/shared/a_modes.inc +++ b/src/shared/a_modes.inc @@ -61,6 +61,7 @@ {$STACKFRAMES OFF} {$ENDIF} {$WARNINGS ON} +{$NOTES ON} {$IFDEF MSWINDOWS} -- 2.29.2