TraceLine acting like a box

[RonanZero]

i made a traceline function, it detects things fine but it detects them like a box, if i go within the bounds of the start x/y and end x/y then it detects it, it doesn't work like an actual line. this is the detection code:

Code: Select all

for _x = startpos.x, endpos.x do
		for _y = startpos.y, endpos.y do
            for _, v in pairs(ents.GetAll()) do
                local sbx, sby, ebx, eby = v:GetBounds();
                if (_x >= sbx and _x <= ebx and _y >= sby and _y <= eby) then
                    --hit
                end
            end
		end
end

[0x72]

Take a look into bump.lua from kikito - It's written in a simple and clean manner (better then anything i could produce), I recommend reading the whole thing - very interesting

You can borrow this function from there:

Code: Select all

-- This is a generalized implementation of the liang-barsky algorithm, which also returns
-- the normals of the sides where the segment intersects.
-- Returns nil if the segment never touches the rect
-- Notice that normals are only guaranteed to be accurate when initially ti1, ti2 == -math.huge, math.huge
local function rect_getSegmentIntersectionIndices(x,y,w,h, x1,y1,x2,y2, ti1,ti2)
  ti1, ti2 = ti1 or 0, ti2 or 1
  local dx, dy = x2-x1, y2-y1
  local nx, ny
  local nx1, ny1, nx2, ny2 = 0,0,0,0
  local p, q, r

  for side = 1,4 do
    if     side == 1 then nx,ny,p,q = -1,  0, -dx, x1 - x     -- left
    elseif side == 2 then nx,ny,p,q =  1,  0,  dx, x + w - x1 -- right
    elseif side == 3 then nx,ny,p,q =  0, -1, -dy, y1 - y     -- top
    else                  nx,ny,p,q =  0,  1,  dy, y + h - y1 -- bottom
    end

    if p == 0 then
      if q <= 0 then return nil end
    else
      r = q / p
      if p < 0 then
        if     r > ti2 then return nil
        elseif r > ti1 then ti1,nx1,ny1 = r,nx,ny
        end
      else -- p > 0
        if     r < ti1 then return nil
        elseif r < ti2 then ti2,nx2,ny2 = r,nx,ny
        end
      end
    end
  end

  return ti1,ti2, nx1,ny1, nx2,ny2
end

and then

Code: Select all

  local ti1, ti2 = rect_getSegmentIntersectionIndices(x, y, w, h, ax, ay, bx, by, -math.huge, math.huge)
  local is_intersecting = ti1 and ((0 < ti1 and ti1 < 1) or (0 < ti2 and ti2 < 1))

(of course you might want to make this easier to call for your scenario)

--- edit ---
Actually your question was different, but you can still use the solution above.

Anyway:

You have 3 nested loops - the outer two will check every single point in box described with the two points that was supposed to be two points of a segment, so e.g. if you have line from (10,50) to(200,300) it actually checks 47500 * num_of_entities times. and the mentioned box would be something like {x=10, y=50, w=190, h=250}.

If you want to iterate point by point then you'll need to calculate slope of the segment, then with just one loop (instead of those two) increment x and y by slope.x and slope.y in each iteration (or something like that).

You won't get anywhere near good performance that way nor it'll check the whole segment (only by discrete units) but it'll be probably a bit better if you make the innermost loop (the one about entities) the outermost one.