Is this efficient collision code?

[Qcode]

So I've been working on a platformer for quite a while now (It's still my first real game) and I've been trying quite a lot of different collision code. I'm one of those stubborn people that don't like using libs, and I don't really need that much power in my collision system, so I thought I would just make my own. I've come around a solution that works quite well, but I'm still worried that I may run into problems later. Here's my physics code (found in physics.lua)

Code: Select all

local function findIntersect(l1p1x,l1p1y, l1p2x,l1p2y, l2p1x,l2p1y, l2p2x,l2p2y, seg1, seg2)
    local a1,b1,a2,b2 = l1p2y-l1p1y, l1p1x-l1p2x, l2p2y-l2p1y, l2p1x-l2p2x
    local c1,c2 = a1*l1p1x+b1*l1p1y, a2*l2p1x+b2*l2p1y
    local det,x,y = a1*b2 - a2*b1
    if det==0 then
    	return false
    end
    x,y = (b2*c1-b1*c2)/det, (a1*c2-a2*c1)/det
    if seg1 or seg2 then
        local min,max = math.min, math.max
        if seg1 and not (min(l1p1x,l1p2x) <= x and x <= max(l1p1x,l1p2x) and min(l1p1y,l1p2y) <= y and y <= max(l1p1y,l1p2y)) or
           seg2 and not (min(l2p1x,l2p2x) <= x and x <= max(l2p1x,l2p2x) and min(l2p1y,l2p2y) <= y and y <= max(l2p1y,l2p2y)) then
            return false, "The lines don't intersect."
        end
    end
    return x,y
end --Taken off of https://love2d.org/wiki/Additional_math Probably not meant for collision, but oh well, it works

local function collisionCheck(v1, v2, v1name, v2name, dt)
	local should = true
	if v1.shouldcollide then --Checks a bunch of lines and stuff.
		down = findIntersect(v1.x + v1.width, v1.y, v1.x, v1.y+v1.height, v2.x + v2.width, v2.y, v2.x, v2.y, true, true)
		down2 = findIntersect(v1.x, v1.y, v1.x + v1.width, v1.y+v1.height, v2.x, v2.y, v2.x + v2.width, v2.y, true, true)
		right = findIntersect(v1.x + v1.width, v1.y, v1.x, v1.y + v1.height - 5, v2.x, v2.y, v2.x, v2.y + v2.height, true, true)
		right2 = findIntersect(v1.x, v1.y, v1.x + v1.width, v1.y + v1.height - 5, v2.x, v2.y, v2.x, v2.y + v2.height, true, true)
		left = findIntersect(v1.x + v1.width, v1.y, v1.x, v1.y + v1.height - 5, v2.x + v2.width, v2.y, v2.x + v2.width , v2.y + v2.height, true, true)
		left2 = findIntersect(v1.x, v1.y, v1.x + v1.width, v1.y + v1.height - 5, v2.x + v2.width, v2.y, v2.x + v2.width, v2.y + v2.height, true, true)
		up = findIntersect(v1.x + v1.width, v1.y, v1.x, v1.y, v2.x + v2.width, v2.y + v2.height, v2.x, v2.y + v2.height, true, true)
		up2 = findIntersect(v1.x, v1.y, v1.x + v1.width, v1.y, v2.x, v2.y + v2.height, v2.x + v2.width, v2.y + v2.height, true, true)
	end
	if down or down2 or up or up2 then --Dissection into horizontal and vertical
		vertical = true
	end
	if right or right2 or left or left2 then
		horizontal = true
	end
	if down or down2 then
		if v1.x + v1.width >= v2.x and v1.x + v1.width <= v2.x + 2 and v1.inAir and name == "Bighead" or v1.x - 2 >= v2.x + v2.width and v1.x <= v2.x + v2.width and not v1.inAir and name == "Bighead" then
			if math.abs(v1.ySpeed-gravity*dt) < math.abs(v1.xSpeed) then --A small part where dt is used -_-
				horizontal = true
				vertical = false
			else
				vertical = true
				horizontal = false
			end
		end
	end
	if v1.x + 20 > v2.x and v1.x < v2.x + v2.width - 10 and v1.y + v1.height >= v2.y and v1.y <= v2.y + v2.height and v1name == "Bighead" and not horizontal then
		vertical = true
	end
	if v1name == "Bighead" and v2name == "block" and down or down2 or right or rigth2 then --Ice and fallthrough stuf.
		if v2.fallthrough then
			if v1.ySpeed > 500*dt then
				vertical, horizontal = false, false
				local x, y = math.min(v2.x/(32*scale)), math.min(v2.y/(32*scale))
				if not editormode then
					map[x][y] = 0
				end
				v2.kill = true
			end
		end
		if v2.ice then
			v1.friction = 1
		else
			v1.friction = 5
		end
	end
	if horizontal then
		if v1.xSpeed > 0 then --Moving right
			v1.x = v2.x - v1.width - 2 --Move back
			if v1.rightcollide then 
				v1:rightcollide(v2, v2name)
			end
		elseif v1.xSpeed < 0 then
			v1.x = v2.x + v2.width + 2 --Where do you think you're going?
			if v1.leftcollide then
				v1:leftcollide(v2, v2name)
			end
		end
		v1.xSpeed = 0 --HOLD UP
	end
	if vertical then
		should = false
		if v1.ySpeed == 0 then
			v1.y = v1.oldy
		elseif v1.ySpeed < 0 then
			if v1.upcollide then
				v1:upcollide(v2, v2name)
			end
			v1.y = v2.y + v2.height + 2
		elseif v1.ySpeed >=0 then
			v1.y = v2.y - v1.height
			if v1.downcollide then
				v1:downcollide(v2, v2name)
			end
		end
		v1.ySpeed = 0 --HOLD UP
	end
	--GET RID OF ALL THE EVIDENCE.
	down, down2, right, right2, up, up2, left, left2, horizontal, vertical = nil, nil, nil, nil, nil, nil, nil, nil, nil, nil
	return should
end

local function docollision(dt) --Handles loops for physics. Lot less complicated than it seems.
	for j, w in pairs(objects) do --
		if j ~= "block" then --Blocks don't need to collide with blocks. Cuz they dont move.
			for i, v in pairs(w) do -- Select first objects table
				for name, lol in pairs(objects) do --Go through all objects names again
					for __, value in pairs(lol) do -- Goes through second objetcs table.
						if (j~=name) then -- They dont need to collide with themselves.
							local properx = gamescroll
							if v.x >= properx and v.x < properx + love.graphics.getWidth() and value.x >= properx and value.x < properx + love.graphics.getWidth() then
								if collisionCheck(v, value, j, name, dt) then --LETS DO SOME COLLISION.
									v.inAir = true
								else
									v.inAir = false
								end
							end
						end
					end		 
				end
			end
		end
	end
end

function loadphysics(dt) --Deltatime	Put in game, will load all the physics
	docollision(dt) --Yay collision system that does physics for me
end

It works quite well, and I haven't been having any trouble with performance yet, but I was wondering if some of you could test this out for me. Have I made any glaringly obvious mistakes? And does anybody know of a solution to that problem where I have to make a right and right2 etc.?
Thanks for telling me, heres a .love. (BTW the gui is mouse based)

[verilog]

Hey man!
Sadly, I get the following error while attempting to open your proyect:

"Could not open file settings.txt. Does not exist"

[Qcode]

Oh, that was a fail on my part. I've updated the first post with the bug fixed.

[ivan]

Hi qcode.
If you want to test an axis-aligned rectangle vs another axis-aligned rectangle, then there's a much simpler way to do that.
You are using line vs line tests which is not the most efficient approach and in fact it wont work in cases where one rectangle is INSIDE another - where none of their edges would intersect.
There is a simpler way to test axis-aligned rectangles:

Code: Select all

local function collisionCheck(v1, v2, v1name, v2name, dt)
  if v1.x + v1.width < v2.x or v1.x > v2.x + v2.width then
    return false
  end
  if v1.y + v1.height < v2.y or v1.y > v2.y + v2.height the
    return false
  end
  return true
end

[Qcode]

I've tried stuff like that, but then what i had trouble with was determining which way the collision was coming from. I tried comparing the xSpeed and ySpeed, and if the ySpeed was greater than the xSpeed then it would be a vertical collision, and vice versa. But then came the problem where if he moved horizontally on the ground then it would automatically class it as a vertical collision and shove him off the edge of the blocks.

[Inny]

Just as a quick primer on collision detection: the type you're talking about is called Narrow Phase Collision Detection, where you directly compare two objects to see if they're meeting the definition of a collision. The Axis-Aligned Bounding Box for this tends to be adequate, or even bounding circle overlaps (which is really just checking if the distance between two objects is smaller than their radii. For most games, if you've got like a dozen onscreen objects, then this is all you need, because you'll only do under a hundred checks on each phase.

However, if you're going to have more onscreen objects than that, like a hundred asteroids banging around in space, then you need to perform something called Broad-Phase Collision Detection, which involved grouping near objects together and only performing collision detection on those objects, and not even wasting time seeing if far away objects are colliding. You're doing none of that. However, you also don't need it. With less than a dozen onscreen objects, the overhead of doing broad-phase collision would be inefficient. If however, you do need it, check the love.physics wiki page.

So basically, instead of asking "Is this efficient", ask "is this correct?"

[ivan]

A while ago a wrote a small platformer lib called FizzX (a revamp of Fizz by taehl).
Here's the collision code for rectangle vs rectangle:

Code: Select all

function testRectRect(a, b)
  -- distance between the shapes
  local dx, dy = a.x - b.x, a.y - b.y
  local adx = abs(dx)
  local ady = abs(dy)
  -- sum of the half-widths
  local shw, shh = a.hw + b.hw, a.hh + b.hh
  if adx > shw or ady > shh then
    return
  end
  -- shortest separation
  local sx, sy = shw - adx, shh - ady
  if sx < sy then
    sy = 0
  else
    sx = 0
  end
  if dx < 0 then
    sx = -sx
  end
  if dy < 0 then
    sy = -sy
  end
  -- penertation depth
  local pen = sqrt(sx*sx + sy*sy)
  if pen > 0 then
    return sx/pen, sy/pen, pen
  end
end

Notice that this function represents rects as center positions (.x/.y) with half width/height (.hw/.hh).
Basically it returns nil if there is NO collision.
If there IS a collision it returns the collision normal vector and the penetration depth.
Using this info, all you have to do is move one of the rects by the shortest separation vector (normal*depth) to resolve the collision:

Code: Select all

  local nx, ny, pen = testRectRect(b.shape, a.shape)
  if nx and ny and pen then
    -- collision?
    local sx, sy = nx*pen, ny*pen -- separation vector

There are some other minor issues that might come up, but this approach is quite effective IMO.
Collision resolution is also a bit more complicated (especially if you want friction/bounce) but you can see examples of that in the FizzX repository (link above).
Good luck.

[vrld]

The tricky part in general is not the actual detection code, but selecting collision candidates.

If you have 100 objects in the scene and you check for collisions between every pair of objects you end up doing 9900 checks. On the other hand, if you can -given an object - quickly decide which other objects are near it, you end up with only a fraction of the checks. E.g. if every object has an average of 10 neighbors you end up with just about 1000 checks. In reality this number is probably smaller.

Now if you do 9900 "efficient" checks, the result will still be slower than doing 1000 "inefficient" ones.

Edit: But as inny wrote, In your case it doesn't really matter

[kikito]

You might think that I'm giving you a tangential answer, but I find it kindof important.

This piece of code should raise an alarm:

Code: Select all

                        end
                     end
                  end
               end       
            end
         end
      end
   end
end

First reason is because code containing stairs like that is incredibly difficult to maintain. On a smaller note, this piece of code also hints at ineficiencies - it'll likely contain unnecessary loops.

As a rule of thumb, in a language as expressive as Lua, a function starts being suspicious when it has 3 indentation levels. 4 is a good indicator that the function is doing too many things, and should be split.

[Qcode]

Thanks for all the help guys. I'd karma you all, but it seems I can't. I'll keep woking on this.