A line trace that can hit non-blockmap actors

[Sir Robin]

I needed a line trace that could hit actor that were not on the block map. I don't know if this is useful to anyone else, but since I took the time to get it to work I'm posting it here, if anyone else needs it.

What's it good for? First thing is debugging. If you type INFO at the console it tells you about what you're looking at. Except that it can't tell you about any actors that are not on the block map because it uses a line trace to find the actor and the line trace function doesn't find actors not on the block map.

Second thing is if you wanted to build a hitscan weapon that can shoot down projectiles, a regular hitscan can't do that because projectiles are not on the block map. But you could use my function for that.

Thing thing, well I can't think of a third thing right now, but I'm sure there are more things out there.

Anyway, to the code:

Code: Select all

//a class for tracking hits on an actor
class HitList
{
    private array<actor> HitA;
    
    //can't have an array of vector3 so have to do it like this
    private array<float> HitX;
    private array<float> HitY;
    private array<float> HitZ;

    //tells how many hits on the list
    uint Size() {return HitZ.Size();}

    //clears everything
    void clear()
    {
        HitA.clear();
        HitX.clear();
        HitY.clear();
        HitZ.clear();
    }

    //adds a hit to the list
    uint Push3Floats(actor HitActor, float HitLocationX, float HitLocationY, float HitLocationZ)
    {
        if (!HitActor) return -1;
        
        HitA.Push(HitActor);
        HitX.Push(HitLocationX);
        HitY.Push(HitLocationY);
	HitZ.Push(HitLocationZ);
	return HitX.Size() - 1;
    }
    
    //adds a hit to the list
    uint PushVector3(actor HitActor, vector3 HitLocation)
    {
        return Push3Floats(HitActor, HitLocation.x, HitLocation.y, HitLocation.z);
    }
    
    //gets a specific hit
    actor, vector3 Get(uint IndexNumber)
    {
        return HitA[IndexNumber], (HitX[IndexNumber], HitY[IndexNumber], HitZ[IndexNumber]);
    }
    
    //sorts the hits by their distance to a point
    void SortByDistanceTo(vector3 ReferencePos)
    {
        if (Size() <= 1) {return;}
    
        array<double> ValueList;
        array<int> IndexList;
        
        for (int i = 0; i < size(); i++)
        {
            vector3 diff = (HitX[i], HitY[i], HitZ[i]) - ReferencePos;
            //TODO: is "dot" faster than "length()"? Need to test this
            //ALT: ValueList.push( diff.length() );
            ValueList.push( diff dot diff );
            IndexList.push(i);
        }
        
        ArraySort.SortDouble(ValueList, IndexList);
        
        array<actor> newHitA;
        array<float> newHitX;
        array<float> newHitY;
        array<float> newHitZ;
        
        for (int i = 0; i < IndexList.size(); i++)
        {
            newHitA.push(HitA[IndexList[i]]);
            newHitX.push(HitX[IndexList[i]]);
            newHitY.push(HitY[IndexList[i]]);
            newHitZ.push(HitZ[IndexList[i]]);
        }
        
        HitA.move(newHitA);
        HitX.move(newHitX);
        HitY.move(newHitY);
        HitZ.move(newHitZ);
    }

    void print()
    {
        for (int i = 0; i < HitZ.size(); i++)
        {
            console.printf("HitList: (%8.2f,%8.2f,%8.2f) %s", HitX[i], HitY[i], HitZ[i], HitA[i].GetCharacterName());
        }
    }
}



struct LineSegCollide play
{
    static
    bool CheckLineSegHitsActor(vector3 LineStart, vector3 LineStop, actor CheckTarget, out HitList Hits)
    {
        double aLeft = CheckTarget.pos.x - CheckTarget.radius;
        double aRight = CheckTarget.pos.x + CheckTarget.radius;
        double aFront = CheckTarget.pos.y - CheckTarget.radius;
        double aBack = CheckTarget.pos.y + CheckTarget.radius;
        double aBottom = CheckTarget.pos.z;
        double aTop = CheckTarget.pos.z + CheckTarget.height;

        //check for easy misses
        if (LineStart.x < aLeft && LineStop.x < aLeft) return false;
        if (LineStart.x > aRight && LineStop.x > aRight) return false;
        if (LineStart.y < aFront && LineStop.y < aFront) return false;
        if (LineStart.y > aBack && LineStop.y > aBack) return false;
        if (LineStart.z < aBottom && LineStop.z < aBottom) return false;
        if (LineStart.z > aTop && LineStop.z > aTop) return false;
        
        vector3 LineDirection = LineStop - LineStart;

        if (!Hits) Hits = new("HitList");
        int NumHits = 0;
    
        //check left
        if (LineDirection.x != 0)
        {
            double t = (aLeft - LineStart.x) / LineDirection.x;
            if (0 <= t && t <= 1)
            {
                double y = LineStart.y + LineDirection.y * t;
                double z = LineStart.z + LineDirection.z * t;
                if (aFront <= y && y <= aBack && aBottom <= z && z <= aTop)
                {
                    Hits.Push3Floats(CheckTarget, aLeft, y, z);
                    NumHits++;
                }
            }
        }

        //check right
        if (LineDirection.x != 0)
        {
            double t = (aRight - LineStart.x) / LineDirection.x;
            if (0 <= t && t <= 1)
            {
                double y = LineStart.y + LineDirection.y * t;
                double z = LineStart.z + LineDirection.z * t;
                if (aFront <= y && y <= aBack && aBottom <= z && z <= aTop)
                {
                    Hits.Push3Floats(CheckTarget, aRight, y, z);
                    NumHits++;
                }
            }
        }
        
        //check front
        if (LineDirection.y != 0)
        {
            double t = (aFront - LineStart.y) / LineDirection.y;
            if (0 <= t && t <= 1)
            {
                double x = LineStart.x + LineDirection.x * t;
                double z = LineStart.z + LineDirection.z * t;
                if (aLeft <= x && x <= aRight && aBottom <= z && z <= aTop)
                {
                    Hits.Push3Floats(CheckTarget, x, aFront, z);
                    NumHits++;
                }
            }
        }

        //check back
        if (LineDirection.y != 0)
        {
            double t = (aBack - LineStart.y) / LineDirection.y;
            if (0 <= t && t <= 1)
            {
                double x = LineStart.x + LineDirection.x * t;
                double z = LineStart.z + LineDirection.z * t;
                if (aLeft <= x && x <= aRight && aBottom <= z && z <= aTop)
                {
                    Hits.Push3Floats(CheckTarget, x, aBack, z);
                    NumHits++;
                }
            }
        }

        //check bottom
        if (LineDirection.z != 0)
        {
            double t = (aBottom - LineStart.z) / LineDirection.z;
            if (0 <= t && t <= 1)
            {
                double x = LineStart.x + LineDirection.x * t;
                double y = LineStart.y + LineDirection.y * t;
                if (aLeft <= x && x <= aRight && aFront <= y && y <= aBack)
                {
                    Hits.Push3Floats(CheckTarget, x, y, aBottom);
                    NumHits++;
                }
            }
        }

        //check top
        if (LineDirection.z != 0)
        {
            double t = (aTop - LineStart.z) / LineDirection.z;
            if (0 <= t && t <= 1)
            {
                double x = LineStart.x + LineDirection.x * t;
                double y = LineStart.y + LineDirection.y * t;
                if (aLeft <= x && x <= aRight && aFront <= y && y <= aBack)
                {
                    Hits.Push3Floats(CheckTarget, x, y, aTop);
                    NumHits++;
                }
            }
        }
        
        return NumHits > 0;
    }
    
    static
    bool CheckLineSegHitsActors(vector3 LineStart, vector3 LineStop, array<actor> CheckTargetList, out HitList Hits)
    {
        if (!Hits) Hits = new("HitList");
    
        bool ret = false;
    
        for (int i = 0; i < CheckTargetList.size(); i++)
        {
            if (!CheckTargetList[i]) continue;
            
            if (CheckLineSegHitsActor(LineStart, LineStop, CheckTargetList[i], Hits)) {ret = true;}
        }
        
        return ret;
    }
    
    static
    bool CheckPlayerLineOfSightHitList(int PlayNum, array<actor> CheckTarget, out HitList Hits, double LookRange = 4096, int TRF_Flags = 0, out FLineTraceData ltd = null)
    {
        PlayerPawn pp = players[PlayNum].mo;
        if (!pp) return false;
        
        pp.LineTrace(pp.Angle, LookRange, pp.Pitch, TRF_flags, pp.player.viewheight, data: ltd);
        vector3 LineStart = pp.pos;
        LineStart.z += pp.player.viewheight;
        vector3 LineStop = ltd.HitLocation;
        
        bool ret = CheckLineSegHitsActors(LineStart, LineStop, CheckTarget, Hits);
        Hits.SortByDistanceTo(LineStart);

        return ret;
    }
    
    static
    actor, vector3 CheckPlayerLineOfSightHitActor(int PlayNum, array<actor> CheckTarget, double LookRange = 4096, int TRF_flags = 0)
    {
        PlayerPawn pp = players[PlayNum].mo;
        if (!pp) return null, (0,0,0);
        
        actor retAct = null;
        vector3 retPos = pp.pos + (0,0,pp.player.ViewHeight);
        fLineTraceData ltd;
        HitList Hits = new("HitList");
        if (CheckPlayerLineOfSightHitList(PlayNum, CheckTarget, Hits, LookRange, TRF_Flags, ltd))
        {
            Hits.SortByDistanceTo(retPos);
        }
        if (0 < Hits.size())
        {
            [retAct, retPos] = Hits.Get(0);
        }
        else if (ltd.HitType == TRACE_HitActor)
        {
            retAct = ltd.HitActor;
            retPos = ltd.HitLocation;
        }
        else
        {
            retPos = ltd.HitLocation;
        }
        
        return retAct, retPos;
    }
}

How it works: It takes a line segment and checks to see if it collides with an actor's hitbox. It does this over a list of actors and keeps a list of which ones get hit, if any, and where. It then sorts this list by distance to the origin, so the first one on the list is the first hit. That reminds me it also needs my ArraySort to function.
Where does it get the list of actors to check? You'll have to provide that. Where does it get the line segment? From a line trace. All you have to tell it is the player number and it can get everything it needs from there.

The function call looks like this:
[HitActor, HitLocation] = LineSegCollide.LineSegCollide.CheckPlayerLineOfSightHitActor(consoleplayer, CheckTargets);
If HitActor is not null then the line hit an actor. It could be one of the actors in CheckTargets or it could have missed all of those and hit another actor. HitLocation tells where the hit happened.

And here is a handler to demonstrate it with:

Code: Select all

class LSC_Handler : EventHandler
{
    //a list of classes not to hit
    static const string ExcludeFromChecks[]={"MapMarker","WireCube3d"};
    array<class> ExcludeList;
    
    override void OnRegister()
    {
        //should only need to do this once
        BuildExcludeList();
    }
    
    //builds a list of classes to exclude with building a target checking list
    void BuildExcludeList()
    {
        ExcludeList.clear();
        for (int i = 0; i < ExcludeFromChecks.size(); i++)
        {
            class ExcludeClass = ExcludeFromChecks[i];
            if (ExcludeClass) ExcludeList.push(ExcludeClass);
        }
    }
    
    //builds a list of non-blockmap actors, exclusing classes in ExcludeList
    void BuildCheckList(int PlayerNum, array<actor> CheckList, array<class> ExcludeList)
    {
        PlayerPawn pp = (0 <= PlayerNum && PlayerNum < players.size()) ? players[PlayerNum].mo : null;
        
        ThinkerIterator it = ThinkerIterator.Create("Actor");
        Actor mo;
        while (mo = Actor(it.Next()))
        {
            bool ShouldSkip = (mo == pp);
            ShouldSkip |= !mo.bNoBlockMap;
            for (int i = 0; i < ExcludeList.size() && !ShouldSkip; i++)
            {
                ShouldSkip = mo is ExcludeList[i];
            }
            if (ShouldSkip) continue;
            CheckList.push(mo);
        }
    }

    override void NetworkProcess(ConsoleEvent e)
    {
        if (e.Name ~== "LSC_Call")
        {
            CheckPlayerLOS(e.player);
        }
    }
    
    //Checks the given player line of sight and prints info on any actor hit
    void CheckPlayerLOS(int PlayerNum)
    {
        if (PlayerNum < 0 || PlayerNum >= players.size()) return;

        array<actor> CheckList;
        BuildCheckList(PlayerNum, CheckList, ExcludeList);
        
        actor HitActor;
        vector3 HitPos;
        [HitActor, HitPos] = LineSegCollide.CheckPlayerLineOfSightHitActor(PlayerNum, CheckList, 4096, TRF_AllActors | TRF_ThruHitScan);

        console.printf("Hit (%.2f,%.2f,%.2f) %s", HitPos.x, HitPos.y, HitPos.z, HitActor ? HitActor.GetClassName() : "[No actor]");//DEBUG
    }
}
 

Just bind something to call that "LSC_Call" and you're set

Limitations:

• Doesn't work through portals, mirrors, etc
• There's a bit of weird code internally, because ZScript doesn't allow vector3 types in dynamic arrays or by reference function parameters
• Is not aware of any infinitely tall actors mode, uses the exact actor height & radius to calculate the hitbox
• If you really want a gun to shot down a projectile, probably should double the height down as Doom only puts a hitbox on the upper half

UPDATE: 2023/10/22
Fixed code not running on newer (~4.10) versions of GZDOOM, according to this post

[Caligari87]

If you really want a gun to shot down a projectile, probably should double the height down as Doom only puts a hitbox on the upper half[/list]

Pedantic and not really related to the topic, but this isn't a (GZ)Doom problem. It's a "people don't set their sprite offsets correctly" problem, and should be handled on a case-by-case basis, not considered a universal constant.

That said, cool concept. I need to bookmark this for later use.

How's performance compared to say, actual line-traces?

[Sir Robin]

How's performance compared to say, actual line-traces?

Definitely slower, but I haven't done any performance testing on it. It uses an actual line trace as the base to find the line segment to test, so it's always going to be linetrace time + it's own time. The functions are compartmentalized, so if you have a better way to determine your line segment without using a line trace, you can use my code on top of that instead.
That said, the math for the check itself it pretty simple: A handful of arithmetic, no trig or square roots, etc. Even the distance sort, I'm using square distance instead of square root distance, so it should be decently fast. But feel free to tell me if there is any part I can still optimize.
In the example handler I posted it generates the list of check actors every time it's called. That's probably slower than it needs to be. In the code I wrote this for, there are only a few specific actors I'm interested in so I track that list myself and don't have to regenerate it every call.
All said, I don't know how to time-test it. If someone wants to do that and tell me the results, or better yet show me how to do it then I could do it myself.

About the projectiles, Yeah I haven't tested that out. It wasn't what I wrote this to do but I was throwing that out as an idea. In testing MAP01 I noticed that I can hit the doomimpball projectiles but their hitbox is at the top half of the sprite. I don't know how many other projectiles are coded that way. If you need to modify the hitbox on a per-actor basis, just change the code in CheckLineSegHitsActor:

Code: Select all

        double aLeft = CheckTarget.pos.x - CheckTarget.radius;
        double aRight = CheckTarget.pos.x + CheckTarget.radius;
        double aFront = CheckTarget.pos.y - CheckTarget.radius;
        double aBack = CheckTarget.pos.y + CheckTarget.radius;
        double aBottom = CheckTarget.pos.z;
        double aTop = CheckTarget.pos.z + CheckTarget.height;
 

You can check CheckTarget and adjust the values as needed.

Another idea is that if you want a railgun or laser or other piecing weapon, instead of calling CheckPlayerLineOfSightHitActor call CheckPlayerLineOfSightHitList and all actors hit will be on that hit list object, with both entry and exit wounds listed. But if you're only doing that for blockmap actors, you could probably do that better with a sub-classed line-trace.

[Sir Robin]

Updated code to work on newer builds of GZDOOM (~4.10) according to this post