3D FPS Shooting Is Hard...

Comments

• EvanDavis

  March 2017 Posts: 112

  Holy crap, great job!
• Kolosso

  March 2017 Posts: 160

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

  March 2017 Posts: 455

  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...
• Kolosso

  March 2017 Posts: 160

  @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!
• spacemonkey

  March 2017 Posts: 455

  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...
• Kolosso

  March 2017 Posts: 160

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

  March 2017 Posts: 2,020

  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.
• Kolosso

  March 2017 edited March 2017 Posts: 160

  @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.
• spacemonkey

  March 2017 Posts: 455

  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
• Kolosso

  March 2017 Posts: 160

  @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?
• spacemonkey

  March 2017 edited March 2017 Posts: 455

  @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.
• Kolosso

  March 2017 Posts: 160

  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
• XanDDemoX

  March 2017 edited April 2017 Posts: 175

  @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

  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)