3D FPS Shooting Is Hard...

Questions
1

Hey, everyone! :slight_smile:
I am currently working on a 3D FPS, and I’m making progress. The game includes houses, collisions, enemies, shooting, and even an intro. But there’s a problem I want to fix before continuing: The player can shoot through walls. My code works like this: “If shoot button pressed then iterate over each guard and check if the player is aiming at one”, but I don’t know how to change it so the player cant shoot through a wall before hitting a guard. I’ve been trying to figure this problem out for a while now, but this is all I could think of:

Right now, my code uses math to find out if a guard is hit. Instead, I could take a screenshot of the screen but color code everything and then check the pixels in the middle of the screen to see if they match the right color code.

The problem is that I fear that that process might be too slow. I would really like some help from you guys! :slight_smile: The code is located in the gist below. The shooting detection code is located at around line 262.
https://gist.github.com/Kolosso7/ebb9a85f0683b9ea8c9da5fb70d4bd0a

Thank-you so much in advance! :smiley:

2

Holy crap, great job!

3

@EvanDavis Thanks! :blush:
I worked hard on it, and I’m proud of my progress.
'Hope everyone has a good day :slight_smile:

4

Doing it with math and hitboxes is the “right” way, but doing a coloured render (enemy’s colour coded per enemy (or even coloured to body part), everything else rendered say black) and then render to a image with setcontext is simpler.

When doing that you could use the clip(x,y,width,height) function to restrict the drawing to just the area the bullet is going, this may reduce the drawing overhead as the fragment shaders shouldn’t have to process all the pixels in the screen…

5

@spacemonkey I think I’ll try the method you described for now, but if it’s too slow for the finished game, I might need to figure out how to do the math.
Thanks for helping! :smiley:

6

you can always optimize it a bit by doing a simple bounding box on the hit test pass to only pick up enemies and walls broadly within the pass, so the render only has to render the meshes for those items even with the clipping…

7

@spacemonkey Umm. I don’t mean to sound stupid, but I don’t know what a bounding box is… :sweat_smile:
Do you mean I can optimize it by only drawing meshes that are in the middle of the screen?

8

I’ve not looked at your code, but what collision detection do you have currently? What stops the player being able to walk through walls, and could that be adapted to the firing routine?

Are the walls aligned with any of the axes (eg, vertically aligned with the “up” axis)? If so, the walls can effectively be treated as lines, and maths should be a quite straightforward, “do these 2 lines cross” algorithm.

9

@yojimbo2000 This is the code that handles the gravity and collisions of the player. It’s located in Player.draw so it’s running 60 times a second (s is a local variable used in the code that equals Player which is a table that holds all the player data):

s.onGround = false
local oldx,oldy,oldz = s.x,s.y,s.z -- Store x,y,z positions for collision sensing
s.vel = math.max(s.vel - 0.77,-55) -- fastest falling speed is -55.
s.y = s.y + s.vel -- Simulate gravity
            
if s.y < 0 then -- if below ground level then
    s.vel = 0 -- set velocity to 0
    s.y = 0 -- and teleport to ground level
    s.onGround = true -- Set onGround to true for the jump button
end
if World == Worlds.town then
    local x,y,z = s.x,s.y,s.z
    local moving = World.jx ~= 0 or World.jy ~= 0 -- jx and jy are the x,y positions of the joystick. If jx and jy are both 0, moving is false. Otherwise it's true.

    if moving then
        local new = vec2(World.jy/6,World.jx/6):rotate(s.rotation.x) -- vec2 of next step of player
        x,z = x+new.x,z+new.y -- add the step to current position (and assign it to the local variables)
        s.x,s.z = x,z -- set the position of the player to the local variables x and z
    end

    -- Collisions with houses
    for i,v in ipairs(World.houses) do -- iterate over houses for collision checking
        local oldY = (((oldx < v.x + 30 and oldx > v.x - 30) and 400) or ((oldx > v.x and 400 - math.abs(v.x - oldx-30)/2) or 400 - math.abs(oldx - v.x-30)/2)) -- formula for the y position whilst on the roof depending on the x position of the last frame.
        local Y = (((x < v.x + 30 and x > v.x - 30) and 400) or ((x > v.x and 400 - math.abs(x - v.x-30)/2) or 400 - math.abs(v.x - x-30)/2)) -- formula for the y position whilst on the roof depending on the x position of the current frame.

        if x < v.x + 230 and x > v.x - 230 and z > v.z - 230 and z < v.z + 230 then -- if x,z are within the walls then
            if oldy >= oldY and y < Y then -- if the old y position is higher than the roof and current y is below the roof then
                s.vel = math.max(s.vel, 0)
                s.y = Y -- Set y to where the roof y would be
                s.onGround = true -- allow the jump button to be pressed
                break
            elseif moving then
                if oldy < oldY and oldx > v.x - 230 and oldx < v.x + 230 then -- if old y was below old roof y and also within the walls of -x and +x then
                    Player.z = v.z + (oldz > v.z and 230 or -230) -- set z to outside +z and -z walls
                    break
                elseif oldy < 300 and oldz > v.z - 230 and oldz < v.z + 230 then
                    Player.x = v.x + (oldx > v.x and 230 or -230)
                    break
                end
            end
        end
    end
end

When I wrote this code I was trying not to use any complicated math. Here’s how it works, starting at the line that says -- Collisions with houses:

Iterate over a table of tables that each store the x and z position of a house (no houses will be floating or underground, so I don't need to store a y position).

Determine the y position of the roof (The roof is shaped like "^", so the y is dependent on the x) using the x position (The roofs will always be facing towards the z direction in my game), of the last frame and store it for later.

Determine the y position of the roof using the x position, of the current frame.

if (the x & z of the player are within the walls of the house) then
    if (player's y of the last frame is below the y of the roof of the last frame) then
        Set the player's y velocity to 0.
        Set the player's y position to the roof's y.
        Set Player.onGround to true, to allow the player to press the jump button.
        Break the loop because no two houses would be close enough to each other to both intersect with the player simultaneously.

        elseif (the player is moving) then
        if (the player's y of the last frame was below the roof y of the last frame and the player's x was between the house's x + 230 and the house's x - 230) then
            Determine which side of the house the player was on, then set the player's z to that side of the house.
            Break the loop.

            elseif (the player's y is below 300 and the player's x is between the house's z + 230 and the house's z - 230) then
            Determine which side of the house the player was on, then set the player's x to either the +x or -x side of the house.
            Break the loop.
        end
    end
end

The walls are vertical, but I wanted to allow the player to jump high and stand on top of the roofs of the houses at some point in the game (maybe at the end in a sandbox mode or something). But, now as I think about it, I find it kind of a lame idea. Maybe I should remove the roof collisions, never let the player be able to jump that high and use the technique you described.

10

Bounding boxes are a simplified math for do you hit something, but not specific enough. Let’s say you have a monster mesh that has a shape to it, it’s all blobby. You could accurately detect a hit on it by somehow methematically describing it’s overall shape and testing it. BUT this is expensive and complex. So what you do with a bounding box is put a cube or sphere around the object (logically not visually) where the object is fully within the bounding box. Then you can do a quick first test of does my shot or whatever hit the bounding box (for which the math is simple), and only if the bounding box is hit, then you worry about the object in detail.

So in drawing this can be good for culling all the meshes out of range, I did something similar in some landscape and things I did in the past, effectively for each quad in my landscape I defined a sphere fully encompassing that quad, then I can quickly test whether the quad is in the visual space (in front of camera), if it is I draw the mesh, if it’s not I don’t, so the graphics processor only considers things that are likely to at least be partially in view. This meant I could have an immense landscape, but the draw speed is still good.

https://codea.io/talk/discussion/5786/heightfield-terrain-very-large-with-good-performance#latest

11

@spacemonkey Okay. So, you’re saying I can have a line (not visually) pointing outwards from the camera (and following the camera’s rotation), and if it touches one of these bounding boxes, the mesh of that bounding box gets drawn? Do you mean it should do this every frame? Wouldn’t that be expensive? Or should it do this only when the shoot button is pressed? Also, how do I detect if a 3D line intersects a cube?

12

@Kolosso with the normal maths for these sorts of things, just like in your current shoot you use maths to see whether there is an enemy in front of you. But you use the bounding box to determine whether the mesh is worth trying to draw. The theory is that the maths to determine whether the bounding box is in frame is cheaper than the GPU work to throw all the meshes at the screen and see what appears. Also the maths on a bounding box of a simple cube or sphere is much better than a more accurate collision with the mesh if it’s not a nice simple shape.

If you have lots of complex meshes, then it can make a big difference if the world is big as you can only see a small portion of it.

This article I based part of the terrain thing on kind of describes it
https://www.gamedev.net/resources/_/technical/graphics-programming-and-theory/quadtrees-r1303
In figure 1 you can see it’s a big terrain, but the camera is in one corner facing away, so you can effectively trim out all the other bits from processing. Then because it’s a “flat” area, it describes a way of structuring the terrain in a quad tree structure for the non moving elements. This means if my terrain is say 64x64 rectangles I’d have to test bounding boxes for 4096 squares which might not be fun. By making them a quadtree type structure I can first test my terrain on a 2x2 grid (4 checks), then discard the big squares outside, and only test in more detail for the 4 squares in each big square I want and on down recursively. I guess it’s analogous to using an index in SQL or something, so I can get to the in camera items by maybe doing 100 checks instead of 4096.

So in my terrain example, I have 16,385 possible quads in the tree, but while running it’ll only have to check 100-120 of them, and it’ll only draw 30-40 of them. → result = performance. There’s some other weirdness I do there so that if it’s far away I draw it at a lower complexity to also reduce the number of mesh renders…

To be honest, a lot of the math on this stuff is a bit beyond me, I just try to understand the concepts and then steal code off the web.

13

I now understand what quadTrees are, but I don’t know how to check if the view frustum (the triangle in Figure 1) is intersecting with a cell (a house in my case). Do you know how to do this? Sorry if I’m becoming annoying. I don’t mean to :frowning:

14

@Kolosso As you are working in 3D you should use an octree. The principal is basically the same except they are split into eight nodes instead of four to cope with the extra dimension.

Check out these links for some reference material. (The code examples aren’t lua)
http://www.flipcode.com/archives/Introduction_To_Octrees.shtml
http://www.gamasutra.com/view/feature/131625/octree_partitioning_techniques.php
https://github.com/Nition/UnityOctree/

Getting the frustrum in Codea is a little tricky to understand but doesn’t require too much typing because it can extracted directly from Codea’s transform matrices using the OpenGL plane extraction technique described in the links below.

http://www.lighthouse3d.com/tutorials/view-frustum-culling/clip-space-approach-extracting-the-planes/

http://www.lighthouse3d.com/tutorials/view-frustum-culling/clip-space-approach-implementation-details/

To be honest it was a bit of a pain to port so I’ll save you the trouble :slight_smile:

Note: It also implements the radar method from the same tutorial so it actually has two independent representations of the frustrum.

Edit: Whoops I missed off a couple of extra links.

Extracting frustrum planes
http://www.txutxi.com/?p=444

AABB intersect algorithm
http://www.txutxi.com/?p=584
http://old.cescg.org/CESCG-2002/DSykoraJJelinek/

Frustrum = class()
Frustrum.planes = {"near","left","right","bottom","top","far"}
function Frustrum:init()
    self.camPos = vec3(0,0,0)
    self.planes = {}
    for i, name in ipairs(Frustrum.planes) do
        self.planes[name] = {abc=vec3(0,0,0),d=0}
    end
end

function Frustrum:setPerspective(angle,ratio,near,far)
    self.ratio = ratio
    self.near = near
    self.far = far
    angle = math.rad(angle)
    self.tang = math.tan(angle * 0.5)
    self.height = near * self.tang 
    self.width = self.height * ratio
    self.sphereY = 1.0/math.cos(angle)
    self.sphereX = 1.0/math.cos(math.atan(self.tang * ratio))
end

function Frustrum:setCamera(p,l,u)
    self.z = (l - p):normalize()
    self.x = self.z:cross(u):normalize()
    self.y = self.x:cross(self.z)
    self.camPos = p
    self:setPlanes()
end

local function setPlane(p,m,a,b,c,d,s)
    p.abc.x =(m[a]*s) + m[4]
    p.abc.y = (m[b]*s) + m[8]
    p.abc.z = (m[c]*s) + m[12]
    p.d = (m[d]*s) + m[16]
    p.di = -p.d
end

function Frustrum:setPlanes(vMatrix,pMatrix)
    vMatrix = vMatrix or viewMatrix()
    pMatrix = pMatrix or projectionMatrix()
    
    local m = vMatrix * pMatrix
    setPlane(self.planes.left,m,1,5,9,13,1)
    setPlane(self.planes.right,m,1,5,9,13,-1)
    setPlane(self.planes.bottom,m,2,6,10,14,1)
    setPlane(self.planes.top,m,2,6,10,14,-1)
    setPlane(self.planes.near,m,3,7,11,15,1)
    setPlane(self.planes.far,m,3,7,11,15,-1)
end

function Frustrum:radarTestPoint(p)
    local v = p - self.camPos
    local pcz = v:dot(self.z)
    
    local near, far = self.near,self.far
    
    if pcz > far or pcz < near then
        return false
    end
    
    local pcy = v:dot(self.y)
    local aux = pcz * self.tang
    
    if pcy > aux or pcy < -aux then
        return false
    end
    
    local pcx = v:dot(self.x)
    aux = aux * self.ratio
    
    if pcx > aux or pcx < -aux then
        return false
    end

    return true
end

function Frustrum:radarTestSphere(p,r)
    local result = true
    local v = p - self.camPos
    
    local pcz = v:dot(self.z)
    local near, far = self.near,self.far
    
    if pcz > far + r or pcz < near - r then
        return false
    elseif pcz > far - r or pcz < near + r then
        -- intersect
    end
    
    local pcy = v:dot(self.y)
    local d = self.sphereY * r
    
    local aux = pcz * self.tang
    if pcy > aux+d or pcy < -aux-d then
        return false
    elseif pcy > aux-d or pcy < -aux+d then
        -- intersect
    end
    
    local pcx = v:dot(self.x)
    d = self.sphereX * r
    aux = aux * self.ratio
    
    if pcx > aux+d or pcx < -aux-d then
        return false
    elseif pcx > aux-d or pcx < -aux+d then
        -- intersect
    end
    
    return result
end

function Frustrum:planeTestBounds(min,max)
    for i,name in ipairs(Frustrum.planes) do
        local plane = self.planes[name]
        local p = vec3(
            plane.abc.x > 0 and max.x or min.x,
            plane.abc.y > 0 and max.y or min.y,
            plane.abc.z > 0 and max.z or min.z
        )
        if p:dot(plane.abc) < plane.di then
            return false
        end
    end
    return true
end

function Frustrum:planeTestPoint(vec)
    for i,name in ipairs(Frustrum.planes) do
        local plane = self.planes[name]
        if v:dot(plane.abc) < plane.di then
            return false
        end
    end
    return true
end

Usage example


frustrum = Frustrum()

-- set up frustrum with values from perspective and camera.
perspective(angle,ratio,near,far)
frustrum:setPerspective(angle,ratio,near,far)

camera(eye.x,eye.y,eye.z,centre.x,centre.y,centre.z,up.x,up.y,up.z)
frustrum:setCamera(eye,centre,up)



-- tests whether an AABB intersects / is inside frustrum using the extents
frustrum:planeTestBounds(bounds.min,bounds.max)

-- tests whether a Point is inside the frustrum
frustrum:planeTestPoint(vec)