From 6eab64d006f1081bc5096507bb634928cadd6d66 Mon Sep 17 00:00:00 2001 From: Ketmar Dark Date: Mon, 21 Aug 2017 22:28:08 +0300 Subject: [PATCH] new tree-based weapon hitscan tracer (sometimes it is faster than the old one, sometimes it is slower...) --- src/game/g_console.pas | 1 + src/game/g_game.pas | 11 ++ src/game/g_map.pas | 67 +++++++++ src/game/g_monsters.pas | 46 +++++- src/game/g_weapons.pas | 313 ++++++++++++++++++++++++++++++++++++++-- src/game/z_aabbtree.pas | 153 ++++++++++++++++++-- 6 files changed, 561 insertions(+), 30 deletions(-) diff --git a/src/game/g_console.pas b/src/game/g_console.pas index 8abfa6c..3c2e7aa 100644 --- a/src/game/g_console.pas +++ b/src/game/g_console.pas @@ -415,6 +415,7 @@ begin AddCommand('sq_use_tree', ProfilerCommands, 'use tree for map coldet acceleration'); AddCommand('mon_sq_enabled', ProfilerCommands, 'use accelerated spatial queries for monsters'); + AddCommand('wtrace_sq_enabled', ProfilerCommands, 'use accelerated weapon hitscan trace'); AddCommand('p1_name', GameCVars); AddCommand('p2_name', GameCVars); diff --git a/src/game/g_game.pas b/src/game/g_game.pas index 9edbcf0..fb5d978 100644 --- a/src/game/g_game.pas +++ b/src/game/g_game.pas @@ -5006,6 +5006,17 @@ begin if gmon_debug_use_sqaccel then g_Console_Add('accelerated monster coldet: tan') else g_Console_Add('accelerated monster coldet: ona'); exit; end; + + if (cmd = 'wtrace_sq_enabled') then + begin + case getBool(1) of + -1: begin end; + 0: gwep_debug_fast_trace := false; + 1: gwep_debug_fast_trace := true; + end; + if gwep_debug_fast_trace then g_Console_Add('accelerated weapon hitscan: tan') else g_Console_Add('accelerated weapon hitscan: ona'); + exit; + end; end; procedure DebugCommands(P: SArray); diff --git a/src/game/g_map.pas b/src/game/g_map.pas index 52713fd..36ac907 100644 --- a/src/game/g_map.pas +++ b/src/game/g_map.pas @@ -172,6 +172,9 @@ var function panelTypeToTag (panelType: Word): Integer; // returns GridTagXXX +function g_Map_traceToNearestWall (x0, y0, x1, y1: Integer; hitx: PInteger=nil; hity: PInteger=nil): Integer; + + implementation uses @@ -281,6 +284,70 @@ begin end; +// wall index in `gWalls` or -1 +function g_Map_traceToNearestWall (x0, y0, x1, y1: Integer; hitx: PInteger=nil; hity: PInteger=nil): Integer; + + function sqchecker (pan: TPanel; var ray: Ray2D): Single; + var + aabb: AABB2D; + tmin: Single; + begin + result := -666.0; // invalid + if not pan.Enabled then exit; + aabb := AABB2D.CreateWH(pan.X, pan.Y, pan.Width, pan.Height); + if not aabb.valid then exit; + if aabb.intersects(ray, @tmin) then + begin + if (tmin >= 0.0) then + begin + //e_WriteLog(Format('sqchecker(%d,%d,%d,%d): panel #%d (%d,%d)-(%d,%d); tmin=%f', [x0, y0, x1, y1, pan.arrIdx, pan.X, pan.Y, pan.Width, pan.Height, tmin]), MSG_NOTIFY); + //if (tmin < 0.0) then tmin := 0.0; + result := tmin; + end; + end; + end; + +var + qr: TDynAABBTreeMap.TSegmentQueryResult; + ray: Ray2D; + hxf, hyf: Single; + hx, hy: Integer; +begin + result := -1; + if (mapTree = nil) then exit; + if mapTree.segmentQuery(qr, x0, y0, x1, y1, sqchecker, (GridTagWall or GridTagDoor)) then + begin + if (qr.flesh <> nil) then + begin + result := qr.flesh.arrIdx; + if (hitx <> nil) or (hity <> nil) then + begin + ray := Ray2D.Create(x0, y0, x1, y1); + hxf := ray.origX+ray.dirX*qr.time; + hyf := ray.origY+ray.dirY*qr.time; + while true do + begin + hx := trunc(hxf); + hy := trunc(hyf); + if (hx >= qr.flesh.X) and (hy >= qr.flesh.Y) and (hx < qr.flesh.X+qr.flesh.Width) and (hy < qr.flesh.Y+qr.flesh.Height) then + begin + // go back a little + hxf -= ray.dirX; + hyf -= ray.dirY; + end + else + begin + break; + end; + end; + if (hitx <> nil) then hitx^ := hx; + if (hity <> nil) then hity^ := hy; + end; + end; + end; +end; + + function g_Map_IsSpecialTexture(Texture: String): Boolean; begin Result := (Texture = TEXTURE_NAME_WATER) or diff --git a/src/game/g_monsters.pas b/src/game/g_monsters.pas index ca7ec00..229748d 100644 --- a/src/game/g_monsters.pas +++ b/src/game/g_monsters.pas @@ -204,6 +204,12 @@ function g_Mons_ForEachAliveAt (x, y: Integer; width, height: Integer; cb: TEach function g_Mons_getNewTrapFrameId (): DWord; +type + TMonsAlongLineCB = function (mon: TMonster; dist: Single): Boolean is nested; + +function g_Mons_alongLine (x0, y0, x1, y1: Integer; cb: TMonsAlongLineCB): TMonster; + + var gmon_debug_use_sqaccel: Boolean = true; @@ -252,18 +258,48 @@ var monsTree: TDynAABBTreeMons = nil; +function g_Mons_alongLine (x0, y0, x1, y1: Integer; cb: TMonsAlongLineCB): TMonster; + + 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; +end; + + //WARNING! call this after monster position was changed, or coldet will not work right! procedure TMonster.positionChanged (); var x, y: Integer; begin - {$IF DEFINED(D2F_DEBUG)} + {$IF DEFINED(D2F_DEBUG_MONS_MOVE)} //e_WriteLog(Format('monster #%d(%u): pos=(%d,%d); rpos=(%d,%d)', [arrIdx, UID, FObj.X, FObj.Y, FObj.Rect.X, FObj.Rect.Y]), MSG_NOTIFY); {$ENDIF} if (treeNode = -1) then begin treeNode := monsTree.insertObject(self, 0); - {$IF DEFINED(D2F_DEBUG)} + {$IF DEFINED(D2F_DEBUG_MONS_MOVE)} monsTree.getNodeXY(treeNode, x, y); e_WriteLog(Format('monster #%d(%u): inserted into the tree; nodeid=%d; x=%d; y=%d', [arrIdx, UID, treeNode, x, y]), MSG_NOTIFY); {$ENDIF} @@ -272,7 +308,7 @@ begin begin monsTree.getNodeXY(treeNode, x, y); if (FObj.X+FObj.Rect.X = x) and (FObj.Y+FObj.Rect.Y = y) then exit; // nothing to do - {$IF DEFINED(D2F_DEBUG)}e_WriteLog(Format('monster #%d(%u): updating tree; nodeid=%d; x=%d; y=%d', [arrIdx, UID, treeNode, x, y]), MSG_NOTIFY);{$ENDIF} + {$IF DEFINED(D2F_DEBUG_MONS_MOVE)}e_WriteLog(Format('monster #%d(%u): updating tree; nodeid=%d; x=%d; y=%d', [arrIdx, UID, treeNode, x, y]), MSG_NOTIFY);{$ENDIF} {$IFDEF TRUE} monsTree.updateObject(treeNode); @@ -281,7 +317,7 @@ begin treeNode := monsTree.insertObject(self); {$ENDIF} - {$IF DEFINED(D2F_DEBUG)} + {$IF DEFINED(D2F_DEBUG_MONS_MOVE)} monsTree.getNodeXY(treeNode, x, y); e_WriteLog(Format('monster #%d(%u): updated tree; nodeid=%d; x=%d; y=%d', [arrIdx, UID, treeNode, x, y]), MSG_NOTIFY); {$ENDIF} @@ -1946,7 +1982,7 @@ begin begin if monsTree.isValidId(treeNode) then begin - {$IF DEFINED(D2F_DEBUG)} + {$IF DEFINED(D2F_DEBUG_MONS_MOVE)} e_WriteLog(Format('monster #%d(%u): removed from tree; nodeid=%d', [arrIdx, UID, treeNode]), MSG_NOTIFY); {$ENDIF} monsTree.removeObject(treeNode); diff --git a/src/game/g_weapons.pas b/src/game/g_weapons.pas index 18f777a..c55931b 100644 --- a/src/game/g_weapons.pas +++ b/src/game/g_weapons.pas @@ -14,12 +14,13 @@ * along with this program. If not, see . *) {$INCLUDE ../shared/a_modes.inc} +{.$DEFINE GWEP_HITSCAN_TRACE_BITMAP_CHECKER} unit g_weapons; interface uses - g_textures, g_basic, e_graphics, g_phys, BinEditor; + g_textures, g_basic, e_graphics, g_phys, BinEditor, xprofiler; const HIT_SOME = 0; @@ -116,6 +117,11 @@ const WP_FIRST = WEAPON_KASTET; WP_LAST = WEAPON_FLAMETHROWER; + +var + gwep_debug_fast_trace: Boolean = true; + + implementation uses @@ -1254,10 +1260,13 @@ var s, c: Extended; //vx, vy: Integer; xx, yy, d: Integer; - i: Integer; t1, _collide: Boolean; w, h: Word; + {$IF DEFINED(D2F_DEBUG)} + stt: UInt64; + showTime: Boolean = true; + {$ENDIF} begin a := GetAngle(x, y, xd, yd)+180; @@ -1293,6 +1302,10 @@ begin //vx := (dx*10 div d)*xi; //vy := (dy*10 div d)*yi; + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro(); + {$ENDIF} + xx := x; yy := y; @@ -1320,27 +1333,41 @@ begin if ByteBool(gCollideMap[yy, xx] and MARK_BLOCKED) then begin _collide := True; + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro()-stt; + e_WriteLog(Format('*** old trace time: %u microseconds', [LongWord(stt)]), MSG_NOTIFY); + showTime := false; + {$ENDIF} g_GFX_Spark(xx-xi, yy-yi, 2+Random(2), 180+a, 0, 0); if g_Game_IsServer and g_Game_IsNet then MH_SEND_Effect(xx-xi, yy-yi, 180+a, NET_GFX_SPARK); end; if not _collide then + begin _collide := GunHit(xx, yy, xi*v, yi*v, dmg, SpawnerUID, v <> 0) <> 0; + end; + + if _collide then Break; + end; - if _collide then - Break; + {$IF DEFINED(D2F_DEBUG)} + if showTime then + begin + stt := curTimeMicro()-stt; + e_WriteLog(Format('*** old trace time: %u microseconds', [LongWord(stt)]), MSG_NOTIFY); end; + {$ENDIF} if CheckTrigger and g_Game_IsServer then g_Triggers_PressL(X, Y, xx-xi, yy-yi, SpawnerUID, ACTIVATE_SHOT); end; -procedure g_Weapon_gun (const x, y, xd, yd, v, dmg: Integer; SpawnerUID: Word; CheckTrigger: Boolean); +(* +procedure g_Weapon_gunComplicated (const x, y, xd, yd, v, dmg: Integer; SpawnerUID: Word; CheckTrigger: Boolean); const HHGridSize = 64; - Nothing = -666666; var hitray: Ray2D; @@ -1353,6 +1380,9 @@ var if (gPlayers[idx] = nil) or not gPlayers[idx].Live then exit; result := HitPlayer(gPlayers[idx], dmg, (xi*v)*10, (yi*v)*10-3, SpawnerUID, HIT_SOME); if result and (v <> 0) then gPlayers[idx].Push((xi*v), (yi*v)); + {$IF DEFINED(D2F_DEBUG)} + //if result then e_WriteLog(Format(' PLAYER #%d HIT', [idx]), MSG_NOTIFY); + {$ENDIF} end; function doMonsterHit (mon: TMonster): Boolean; @@ -1361,6 +1391,9 @@ var if (mon = nil) then exit; result := HitMonster(mon, dmg, (xi*v)*10, (yi*v)*10-3, SpawnerUID, HIT_SOME); if result and (v <> 0) then mon.Push((xi*v), (yi*v)); + {$IF DEFINED(D2F_DEBUG)} + //if result then e_WriteLog(Format(' MONSTER #%u HIT', [LongWord(mon.UID)]), MSG_NOTIFY); + {$ENDIF} end; // get nearest player along hitray @@ -1435,15 +1468,30 @@ var xe, ye: Integer; s, c: Extended; xx, yy, d: Integer; + prevX, prevY: Integer; leftToNextMonsterQuery: Integer = 0; i: Integer; t1: Boolean; + {$IF DEFINED(GWEP_HITSCAN_TRACE_BITMAP_CHECKER)} w, h: Word; + {$ENDIF} wallWasHit: Boolean = false; wallHitX: Integer = 0; wallHitY: Integer = 0; didHit: Boolean = false; + mptWX: Integer = 0; + mptWY: Integer = 0; + mptHit: Integer = -1; + {$IF DEFINED(D2F_DEBUG)} + stt: UInt64; + {$ENDIF} begin + if not gwep_debug_fast_trace then + begin + g_Weapon_gunOld(x, y, xd, yd, v, dmg, SpawnerUID, CheckTrigger); + exit; + end; + wgunMonHash.reset(); //FIXME: clear hash on level change wgunHitHeap.clear(); wgunHitTimeUsed := 0; @@ -1460,9 +1508,13 @@ begin hitray := Ray2D.Create(x, y, x2, y2); + e_WriteLog(Format('GUN TRACE: (%d,%d) to (%d,%d)', [x, y, x2, y2]), MSG_NOTIFY); + + {$IF DEFINED(GWEP_HITSCAN_TRACE_BITMAP_CHECKER)} t1 := (gWalls <> nil); w := gMapInfo.Width; h := gMapInfo.Height; + {$ENDIF} dx := x2-x; dy := y2-y; @@ -1490,14 +1542,33 @@ begin //vx := (dx*10 div d)*xi; //vy := (dy*10 div d)*yi; + {$IF DEFINED(D2F_DEBUG)} + mptHit := g_Map_traceToNearestWall(x, y, x2, y2, @mptWX, @mptWY); + e_WriteLog(Format('tree trace: (%d,%d)', [mptWX, mptWY]), MSG_NOTIFY); + {$ENDIF} + + {$IF not DEFINED(GWEP_HITSCAN_TRACE_BITMAP_CHECKER)} + wallWasHit := (mptHit >= 0); + wallHitX := mptWX; + wallHitY := mptWY; + t1 := false; + {$ENDIF} + + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro(); + {$ENDIF} // find wall, collect monsters begin xe := 0; ye := 0; xx := x; yy := y; + prevX := xx; + prevY := yy; for i := 1 to d do begin + prevX := xx; + prevY := yy; xe += dx; ye += dy; if (xe > d) then begin xe -= d; xx += xi; end; @@ -1507,15 +1578,19 @@ begin //if (yy > h) or (yy < 0) then break; //if (xx > w) or (xx < 0) then break; + {$IF DEFINED(GWEP_HITSCAN_TRACE_BITMAP_CHECKER)} if t1 and (xx >= 0) and (yy >= 0) and (xx < w) and (yy < h) then begin if ByteBool(gCollideMap[yy, xx] and MARK_BLOCKED) then begin wallWasHit := true; - wallHitX := xx-xi; - wallHitY := yy-xi; + wallHitX := prevX; + wallHitY := prevY; end; end; + {$ELSE} + if (abs(prevX-wallHitX) < 2) and (abs(prevY-wallHitY) < 2) then t1 := true; + {$ENDIF} if (leftToNextMonsterQuery <> 0) and not wallWasHit then begin @@ -1526,14 +1601,18 @@ begin // check monsters g_Mons_ForEachAliveAt(xx-HHGridSize div 2, yy-HHGridSize div 2, HHGridSize+HHGridSize div 2, HHGridSize+HHGridSize div 2, monsPossibleHit); leftToNextMonsterQuery := HHGridSize; // again + {$IF DEFINED(GWEP_HITSCAN_TRACE_BITMAP_CHECKER)} if wallWasHit then break; + {$ELSE} + if t1 then break; + {$ENDIF} end; end; if not wallWasHit then begin - wallHitX := xx; - wallHitY := yy; + wallHitX := prevX; + wallHitY := prevY; end; end; @@ -1570,8 +1649,222 @@ begin // need sparks? if wallWasHit then begin + {$IF DEFINED(GWEP_HITSCAN_TRACE_BITMAP_CHECKER)} + if (mptHit < 0) then + begin + e_WriteLog('OOPS: tree trace failed, but pixel trace found the wall!', MSG_WARNING); + raise Exception.Create('map tree trace fucked'); + end + else + begin + {$IF DEFINED(D2F_DEBUG)} + //e_WriteLog(Format(' trace: (%d,%d)', [wallHitX, wallHitY]), MSG_NOTIFY); + {$ENDIF} + wallHitX := mptWX; + wallHitY := mptWY; + end; + {$ENDIF} + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro()-stt; + e_WriteLog(Format('*** new trace time: %u microseconds', [LongWord(stt)]), MSG_NOTIFY); + {$ENDIF} g_GFX_Spark(wallHitX, wallHitY, 2+Random(2), 180+a, 0, 0); if g_Game_IsServer and g_Game_IsNet then MH_SEND_Effect(wallHitX, wallHitY, 180+a, NET_GFX_SPARK); + end + else + begin + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro()-stt; + e_WriteLog(Format('*** new trace time: %u microseconds', [LongWord(stt)]), MSG_NOTIFY); + {$ENDIF} + end; + + if CheckTrigger and g_Game_IsServer then g_Triggers_PressL(X, Y, wallHitX, wallHitY, SpawnerUID, ACTIVATE_SHOT); +end; +*) + + +procedure g_Weapon_gun (const x, y, xd, yd, v, dmg: Integer; SpawnerUID: Word; CheckTrigger: Boolean); +var + hitray: Ray2D; + xi, yi: Integer; + wallDistSq: Single = 1.0e100; + + function doPlayerHit (idx: Integer): Boolean; + begin + result := false; + if (idx < 0) or (idx > High(gPlayers)) then exit; + if (gPlayers[idx] = nil) or not gPlayers[idx].Live then exit; + result := HitPlayer(gPlayers[idx], dmg, (xi*v)*10, (yi*v)*10-3, SpawnerUID, HIT_SOME); + if result and (v <> 0) then gPlayers[idx].Push((xi*v), (yi*v)); + {$IF DEFINED(D2F_DEBUG)} + //if result then e_WriteLog(Format(' PLAYER #%d HIT', [idx]), MSG_NOTIFY); + {$ENDIF} + end; + + function doMonsterHit (mon: TMonster): Boolean; + begin + result := false; + if (mon = nil) then exit; + result := HitMonster(mon, dmg, (xi*v)*10, (yi*v)*10-3, SpawnerUID, HIT_SOME); + if result and (v <> 0) then mon.Push((xi*v), (yi*v)); + {$IF DEFINED(D2F_DEBUG)} + //if result then e_WriteLog(Format(' MONSTER #%u HIT', [LongWord(mon.UID)]), MSG_NOTIFY); + {$ENDIF} + end; + + // collect players along hitray + // return `true` if instant hit was detected + function playerPossibleHit (): Boolean; + var + i: Integer; + aabb: AABB2D; + tmin: Single; + begin + result := false; + for i := 0 to High(gPlayers) do + begin + if (gPlayers[i] <> nil) and gPlayers[i].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 + begin + // intersect + if (tmin <= 0.0) then + begin + if doPlayerHit(i) then begin result := true; exit; end; + end + else + begin + if (tmin*tmin < wallDistSq) then appendHitTimePlr(tmin, i); + end; + end; + end; + end; + end; + + function sqchecker (mon: TMonster; dist: Single): Boolean; + begin + result := false; // don't stop + if (dist*dist < wallDistSq) then appendHitTimeMon(dist, mon); + end; + +var + a: Integer; + x2, y2: Integer; + dx, dy: Integer; + xe, ye: Integer; + s, c: Extended; + i: Integer; + wallHitIdx: Integer = -1; + wallHitX: Integer = 0; + wallHitY: Integer = 0; + didHit: Boolean = false; + {$IF DEFINED(D2F_DEBUG)} + stt: UInt64; + {$ENDIF} +begin + if not gwep_debug_fast_trace then + begin + g_Weapon_gunOld(x, y, xd, yd, v, dmg, SpawnerUID, CheckTrigger); + exit; + end; + + wgunMonHash.reset(); //FIXME: clear hash on level change + wgunHitHeap.clear(); + wgunHitTimeUsed := 0; + + a := GetAngle(x, y, xd, yd)+180; + + SinCos(DegToRad(-a), s, c); + + if Abs(s) < 0.01 then s := 0; + if Abs(c) < 0.01 then c := 0; + + x2 := x+Round(c*gMapInfo.Width); + y2 := y+Round(s*gMapInfo.Width); + + dx := x2-x; + dy := y2-y; + + if (xd = 0) and (yd = 0) then exit; + + if dx > 0 then xi := 1 else if dx < 0 then xi := -1 else xi := 0; + if dy > 0 then yi := 1 else if dy < 0 then yi := -1 else yi := 0; + + {$IF DEFINED(D2F_DEBUG)} + e_WriteLog(Format('GUN TRACE: (%d,%d) to (%d,%d)', [x, y, x2, y2]), MSG_NOTIFY); + stt := curTimeMicro(); + {$ENDIF} + + wallHitIdx := g_Map_traceToNearestWall(x, y, x2, y2, @wallHitX, @wallHitY); + if (wallHitIdx >= 0) then + begin + x2 := wallHitX; + y2 := wallHitY; + wallDistSq := (wallHitX-x)*(wallHitX-x)+(wallHitY-y)*(wallHitY-y); + end + else + begin + wallHitX := x2; + wallHitY := y2; + end; + + hitray := Ray2D.Create(x, y, x2, y2); + + if playerPossibleHit() then exit; // instant hit + + // collect monsters + g_Mons_alongLine(x, y, x2, y2, sqchecker); + + // here, we collected all monsters and players in `wgunHitHeap` and `wgunHitTime` + // also, if `wallWasHit` >= 0, then `wallHitX` and `wallHitY` contains spark coords + while (wgunHitHeap.count > 0) do + begin + // has some entities to check, do it + i := wgunHitHeap.front; + wgunHitHeap.popFront(); + hitray.atTime(wgunHitTime[i].time, xe, ye); + // check if it is not behind the wall + if (wgunHitTime[i].mon <> nil) then + begin + didHit := doMonsterHit(wgunHitTime[i].mon); + end + else + begin + didHit := doPlayerHit(wgunHitTime[i].plridx); + end; + if didHit then + begin + // need new coords for trigger + wallHitX := xe; + wallHitY := ye; + wallHitIdx := -1; // no sparks + break; + end; + end; + + // need sparks? + if (wallHitIdx >= 0) then + begin + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro()-stt; + e_WriteLog(Format('*** new trace time: %u microseconds', [LongWord(stt)]), MSG_NOTIFY); + {$ENDIF} + g_GFX_Spark(wallHitX, wallHitY, 2+Random(2), 180+a, 0, 0); + if g_Game_IsServer and g_Game_IsNet then MH_SEND_Effect(wallHitX, wallHitY, 180+a, NET_GFX_SPARK); + end + else + begin + {$IF DEFINED(D2F_DEBUG)} + stt := curTimeMicro()-stt; + e_WriteLog(Format('*** new trace time: %u microseconds', [LongWord(stt)]), MSG_NOTIFY); + {$ENDIF} end; if CheckTrigger and g_Game_IsServer then g_Triggers_PressL(X, Y, wallHitX, wallHitY, SpawnerUID, ACTIVATE_SHOT); diff --git a/src/game/z_aabbtree.pas b/src/game/z_aabbtree.pas index c16719a..86e0568 100644 --- a/src/game/z_aabbtree.pas +++ b/src/game/z_aabbtree.pas @@ -37,6 +37,9 @@ type origX, origY: Single; dirX, dirY: Single; + function getOrigN (idx: Integer): Single; inline; + function getDirN (idx: Integer): Single; inline; + public constructor Create (ax, ay: Single; aangle: Single); overload; constructor Create (ax0, ay0, ax1, ay1: Single); overload; @@ -50,6 +53,9 @@ type procedure setX0Y0X1Y1 (ax0, ay0, ax1, ay1: Single); inline; procedure atTime (time: Single; out rx, ry: Integer); inline; + + property orig[idx: Integer]: Single read getOrigN; + property dir[idx: Integer]: Single read getDirN; end; // ////////////////////////////////////////////////////////////////////////// // @@ -64,6 +70,8 @@ type function getcenterY (): TreeNumber; inline; function getextentX (): TreeNumber; inline; function getextentY (): TreeNumber; inline; + function getMinN (idx: Integer): TreeNumber; inline; + function getMaxN (idx: Integer): TreeNumber; inline; public constructor Create (x0, y0, x1, y1: TreeNumber); overload; @@ -91,13 +99,17 @@ type // ray direction must be normalized function intersects (constref ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload; - function intersects (ax, ay, bx, by: Single): Boolean; inline; overload; + function intersects (ax, ay, bx, by: Single; tmino: PSingle=nil): Boolean; inline; overload; + function intersects (constref ray: Ray2D; maxtime: Single; tmino: PSingle=nil): Boolean; inline; overload; property valid: Boolean read getvalid; property centerX: TreeNumber read getcenterX; property centerY: TreeNumber read getcenterY; property extentX: TreeNumber read getextentX; property extentY: TreeNumber read getextentY; + + property min[idx: Integer]: TreeNumber read getMinN; + property max[idx: Integer]: TreeNumber read getMaxN; end; @@ -197,11 +209,11 @@ type // called when a overlapping node has been found during the call to forEachAABBOverlap() // return `true` to stop type TQueryOverlapCB = function (abody: TTreeFlesh; atag: Integer): Boolean is nested; - type TSegQueryCallback = function (abody: TTreeFlesh; ax, ay, bx, by: Single): Single is nested; // return dist from (ax,ay) to abody + type TSegQueryCallback = function (abody: TTreeFlesh; var ray: Ray2D): Single is nested; // return hit time PSegmentQueryResult = ^TSegmentQueryResult; TSegmentQueryResult = record - dist: Single; // <0: nothing was hit + time: Single; // <0: nothing was hit flesh: TTreeFlesh; constructor Create (fuckyoufpc: Boolean); @@ -227,6 +239,7 @@ type curax, curay: Single; curbx, curby: Single; dirx, diry: Single; + traceRay: Ray2D; sqcb: TSegQueryCallback; vstack: array of Integer; // for `visit()` vstused: Integer; // to support recursive queries @@ -329,6 +342,9 @@ function dtMaxI (a, b: Integer): Integer; inline; function dtMinF (a, b: TreeNumber): TreeNumber; inline; function dtMaxF (a, b: TreeNumber): TreeNumber; inline; +function minSingle (a, b: Single): Single; inline; +function maxSingle (a, b: Single): Single; inline; + implementation @@ -343,6 +359,9 @@ function dtMaxI (a, b: Integer): Integer; inline; begin if (a > b) then result : function dtMinF (a, b: TreeNumber): TreeNumber; inline; begin if (a < b) then result := a else result := b; end; function dtMaxF (a, b: TreeNumber): TreeNumber; inline; begin if (a > b) then result := a else result := b; end; +function minSingle (a, b: Single): Single; inline; begin if (a < b) then result := a else result := b; end; +function maxSingle (a, b: Single): Single; inline; begin if (a > b) then result := a else result := b; end; + // ////////////////////////////////////////////////////////////////////////// // constructor Ray2D.Create (ax, ay: Single; aangle: Single); begin setXYAngle(ax, ay, aangle); end; @@ -350,6 +369,10 @@ constructor Ray2D.Create (ax0, ay0, ax1, ay1: Single); begin setX0Y0X1Y1(ax0, ay constructor Ray2D.Create (constref aray: Ray2D); overload; begin copyFrom(aray); end; +function Ray2D.getOrigN (idx: Integer): Single; inline; begin if (idx = 0) then result := origX else if (idx = 1) then result := origY else result := 0; end; +function Ray2D.getDirN (idx: Integer): Single; inline; begin if (idx = 0) then result := dirX else if (idx = 1) then result := dirY else result := 0; end; + + procedure Ray2D.copyFrom (constref aray: Ray2D); inline; begin origX := aray.origX; @@ -428,6 +451,9 @@ function AABB2D.getcenterY (): TreeNumber; inline; begin result := (minY+maxY) d function AABB2D.getextentX (): TreeNumber; inline; begin result := maxX-minX+1; end; function AABB2D.getextentY (): TreeNumber; inline; begin result := maxY-minY+1; end; +function AABB2D.getMinN (idx: Integer): TreeNumber; inline; begin if (idx = 0) then result := minX else if (idx = 1) then result := minY else result := 0; end; +function AABB2D.getMaxN (idx: Integer): TreeNumber; inline; begin if (idx = 0) then result := maxX else if (idx = 1) then result := maxY else result := 0; end; + procedure AABB2D.copyFrom (constref aabb: AABB2D); inline; begin minX := aabb.minX; @@ -515,6 +541,7 @@ end; // something to consider here is that 0 * inf =nan which occurs when the ray starts exactly on the edge of a box // https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/ +{ function AABB2D.intersects (constref ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload; var dinv, t1, t2, tmp: Single; @@ -559,30 +586,86 @@ begin result := false; end; end; +} + -function AABB2D.intersects (ax, ay, bx, by: Single): Boolean; inline; overload; +function AABB2D.intersects (constref ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload; +var + tmin, tmax, t1, t2, invd: Single; + i: Integer; +begin + tmin := -1.0e100; + tmax := 1.0e100; + for i := 0 to 1 do + begin + if (ray.dir[i] <> 0.0) then + begin + //t1 := (self.min[i]-ray.orig[i])/ray.dir[i]; + //t2 := (self.max[i]-ray.orig[i])/ray.dir[i]; + invd := 1.0/ray.dir[i]; + t1 := (self.min[i]-ray.orig[i])*invd; + t2 := (self.max[i]-ray.orig[i])*invd; + tmin := maxSingle(tmin, minSingle(t1, t2)); + tmax := minSingle(tmax, maxSingle(t1, t2)); + end + else if (ray.orig[i] <= self.min[i]) or (ray.orig[i] >= self.max[i]) then + begin + result := false; + exit; + end; + end; + + result := (tmax > tmin) and (tmax > 0.0); + if result then + begin + if (tmino <> nil) then tmino^ := tmin; + if (tmaxo <> nil) then tmaxo^ := tmin; + end; +end; + + +function AABB2D.intersects (ax, ay, bx, by: Single; tmino: PSingle=nil): Boolean; inline; overload; var tmin: Single; ray: Ray2D; begin result := true; + if (tmino <> nil) then tmino^ := 0.0; // it may be faster to first check if start or end point is inside AABB (this is sometimes enough for dyntree) if (ax >= minX) and (ay >= minY) and (ax <= maxX) and (ay <= maxY) then exit; // a if (bx >= minX) and (by >= minY) and (bx <= maxX) and (by <= maxY) then exit; // b // nope, do it hard way ray := Ray2D.Create(ax, ay, bx, by); - if not intersects(ray, @tmin) then begin result := false; exit; end; + if not intersects(ray, @tmin) then begin if (tmino <> nil) then tmino^ := tmin; result := false; exit; end; + if (tmino <> nil) then tmino^ := tmin; if (tmin < 0) then exit; // inside, just in case - bx := bx-ax; - by := by-ay; + bx -= ax; + by -= ay; result := (tmin*tmin <= bx*bx+by*by); end; +function AABB2D.intersects (constref ray: Ray2D; maxtime: Single; tmino: PSingle=nil): Boolean; inline; overload; +var + tmin: Single; +begin + result := true; + if (ray.origX >= minX) and (ray.origY >= minY) and (ray.origX <= maxX) and (ray.origY <= maxY) then + begin + if (tmino <> nil) then tmino^ := 0.0; + exit; + end; + if not intersects(ray, @tmin) then begin if (tmino <> nil) then tmino^ := -1.0; result := false; exit; end; + if (tmin < 0) then tmin := 0; // inside + if (tmino <> nil) then tmino^ := tmin; + result := (tmin <= maxtime); +end; + + // ////////////////////////////////////////////////////////////////////////// // -constructor TDynAABBTreeBase.TSegmentQueryResult.Create (fuckyoufpc: Boolean); begin dist := -1; flesh := Default(ITP); end; -procedure TDynAABBTreeBase.TSegmentQueryResult.reset (); inline; begin dist := -1; flesh := Default(ITP); end; -function TDynAABBTreeBase.TSegmentQueryResult.valid (): Boolean; inline; begin result := (dist >= 0) and (flesh <> Default(ITP)); end; +constructor TDynAABBTreeBase.TSegmentQueryResult.Create (fuckyoufpc: Boolean); begin time := -1; flesh := Default(ITP); end; +procedure TDynAABBTreeBase.TSegmentQueryResult.reset (); inline; begin time := -1; flesh := Default(ITP); end; +function TDynAABBTreeBase.TSegmentQueryResult.valid (): Boolean; inline; begin result := (time >= 0) and (flesh <> Default(ITP)); end; // ////////////////////////////////////////////////////////////////////////// // @@ -1597,19 +1680,51 @@ end; function TDynAABBTreeBase.checkerRay (node: PTreeNode): Boolean; +var + tmin: Single = 0; begin - result := node.aabb.intersects(curax, curay, curbx, curby); + {$IF FALSE} + result := node.aabb.intersects(curax, curay, curbx, curby, @tmin); + e_WriteLog(Format('intersect: (%f,%f)-(%f,%f) (%d,%d)-(%d,%d) tmin=%f res=%d', [ + minSingle(curax, curbx), + minSingle(curay, curby), + maxSingle(curax, curbx), + maxSingle(curay, curby), + node.aabb.minX, node.aabb.minY, + node.aabb.maxX, node.aabb.maxY, + tmin, + Integer(result), + ]), MSG_NOTIFY); + {$ELSE} + result := node.aabb.intersects(traceRay, maxFraction, @tmin); + { + e_WriteLog(Format('intersect: (%f,%f)-(%f,%f) (%d,%d)-(%d,%d) tmin=%f res=%d frac=%f', [ + curax, curay, curbx, curby, + node.aabb.minX, node.aabb.minY, + node.aabb.maxX, node.aabb.maxY, + tmin, + Integer(result), + maxFraction + ]), MSG_NOTIFY); + } + {$ENDIF} end; + function TDynAABBTreeBase.visitorRay (flesh: TTreeFlesh; tag: Integer): Boolean; var hitFraction: Single; + ray: Ray2D; begin - hitFraction := sqcb(flesh, curax, curay, curbx, curby); + ray.origX := curax; + ray.origY := curay; + ray.dirX := dirx; + ray.dirY := diry; + hitFraction := sqcb(flesh, ray); // if the user returned a hitFraction of zero, it means that the raycasting should stop here if (hitFraction = 0.0) then begin - qSRes.dist := 0; + qSRes.time := 0; qSRes.flesh := flesh; result := true; exit; @@ -1621,7 +1736,7 @@ begin if (hitFraction < maxFraction) then begin maxFraction := hitFraction; - qSRes.dist := hitFraction; + qSRes.time := hitFraction; qSRes.flesh := flesh; // fix curb here //curb := cura+dir*hitFraction; @@ -1643,10 +1758,11 @@ var invlen: Single; osres: PSegmentQueryResult; osqcb: TSegQueryCallback; + oldray: Ray2D; begin qr := TSegmentQueryResult.Create(false); - if (ax >= bx) or (ay >= by) then begin result := false; exit; end; + if (ax = bx) and (ay = by) then begin result := false; exit; end; oldmaxFraction := maxFraction; oldcurax := curax; @@ -1655,6 +1771,7 @@ begin oldcurby := curby; olddirx := dirx; olddiry := diry; + oldray := traceRay; maxFraction := 1.0e100; // infinity curax := ax; @@ -1669,6 +1786,11 @@ begin dirx *= invlen; diry *= invlen; + traceRay.origX := curax; + traceRay.origY := curay; + traceRay.dirX := dirx; + traceRay.dirY := diry; + //chkAABB := AABB2D.Create(0, 0, 1, 1); osres := qSRes; qSRes := @qr; @@ -1685,6 +1807,7 @@ begin dirx := olddirx; diry := olddiry; maxFraction := oldmaxFraction; + traceRay := oldray; result := qr.valid; end; -- 2.29.2