Collision response libraries

[vrld]

And something I've never seen explained well on the Internet.

That's because it is a very, very hard problem. People write whole PhD theses around that topic.

[ivan]

I'd love to use Box2D if it wasn't for that physics bodies limit.

Box2D can simulate quite a high number of proxies.
The max number limit(which can be adjusted if you re-build the lib yourself) makes sure that the simulation can run in realtime.
There's no point in simulating thousands of shapes and rigid bodies if the result is going to be a slideshow.

[AaronWizard]

And something I've never seen explained well on the Internet.

That's because it is a very, very hard problem. People write whole PhD theses around that topic.

And yet every game seems to do this.

I'm thinking what I should really do is come up with a way of merging all my wall tiles into a smaller number of bigger rectangles. That should allow me to use Box2D without going over the physics bodies limit.

For reference, this is what my game looks like.

shootron.png (36.02 KiB) Viewed 1627 times

[MarekkPie]

http://vrld.github.com/HardonCollider/r ... mergedWith

HardonCollider seems to do this (I would think Box2D would do this as well).

The issue you would need to look out for if you decide to make one yourself is that SAT collisions require convex polygons, so if you merge an L shaped corner, the outside edge would work correctly, but the inside edge would not. This can "easily" be alleviated by grouping into two shapes the vertical side and the horizontal side, but doing so programmatically is not a simple task (do a Google search for convex decomposition).

A much simpler (in my opinion) solution would be to use spatial hashing, which I believe Box2D does automatically when you create a "world" (this is totally pulled out of my ass; I haven't used love.physics yet), and HardonCollider provides:

http://vrld.github.com/HardonCollider/r ... patialhash

Or...[cough] https://github.com/mkosler/LoveHash [/cough]

EDIT: Also, I bet it's safe to say that VERY, VERY few games (with games including scientific simulations) try to calculate collisions between more than two objects. It's a trick of the mind and the speed of the process that fakes these seemingly instantaneous collisions. Think about how often, truly, three objects collide with each other at the exact same time...Keep thinking...having trouble, right? How often, in a game, does it truly matter?

[tentus]

Remember all those times (well, that handful of times) that you were playing a triple A game and found yourself oddly stuck in a corner? This happened a lot in the previous console gen, less so in this one. That's because of this very problem.

If everything in your game is gonna be grid-align rectangles, you can still go with my underpowered method using HardonCollider. Give this code a whirl:

Code: Select all

function love.load()
	collider = require("hardoncollider")(128, on_collide)
	shapes = {
		collider:addCircle(100, 100, 25),   -- the player shape
		collider:addRectangle(200, 200, 100, 100),
		collider:addRectangle(300, 300, 100, 100),
	}
end
function love.update(dt)
	local speed = 200 * dt
	local x, y = 0, 0
	if love.keyboard.isDown("left") then
		x = -1
	elseif love.keyboard.isDown("right") then
		x = 1
	end
	if love.keyboard.isDown("up") then
		y = -1
	elseif love.keyboard.isDown("down") then
		y = 1
	end
	shapes[1]:move(x * speed, y * speed)
	collider:update(dt)
end
function love.draw()
	for i=1, #shapes do 
		shapes[i]:draw("line")
	end
end
function on_collide(dt, a, b, x,y)
	a:move(x,y)
end

Use arrow keys to move.

[vrld]

And something I've never seen explained well on the Internet.

That's because it is a very, very hard problem. People write whole PhD theses around that topic.

And yet every game seems to do this.

That doesn't mean it's easy. If you want to read up on it, search for "rigid body simulation".

This can "easily" be alleviated by grouping into two shapes the vertical side and the horizontal side, but doing so programmatically is not a simple task (do a Google search for convex decomposition).

HC does it, but not perfectly. In essence, that's the reason for Polygon:mergedWith().

Also, I bet it's safe to say that VERY, VERY few games (with games including scientific simulations) try to calculate collisions between more than two objects.

It actually happens quite often, as you can see here:

doublecollider.png (5.28 KiB) Viewed 1590 times

[MarekkPie]

But that is still calculating collisions between object A and B, and object A and C. Each collision is within it's own environment, and does not directly affect another. That's what I am getting at.

[AaronWizard]

The issue you would need to look out for if you decide to make one yourself is that SAT collisions require convex polygons, so if you merge an L shaped corner, the outside edge would work correctly, but the inside edge would not. This can "easily" be alleviated by grouping into two shapes the vertical side and the horizontal side, but doing so programmatically is not a simple task (do a Google search for convex decomposition).

I wasn't thinking of merging all wall tiles into one big blob (or several blobs). I was strictly thinking of rectangles; i.e. convex. So, if there's a long row of wall tiles, they'd be covered by one long rectangle. I'm still not sure how I'd do that though.

And remember, this would be an optimization step so that the terrain puts a light enough load on Box2D so that it can handle all the monsters and bullets.

Also, I bet it's safe to say that VERY, VERY few games (with games including scientific simulations) try to calculate collisions between more than two objects.

It actually happens quite often, as you can see here:

Also, terrain collision is easy compared to handling collisions between mobiles.

bad_craziness.png (10.37 KiB) Viewed 1579 times

In what direction does each circle get pushed to fix the collision?

And how do we prevent new collisions from being created when we resolve existing ones?

bad_craziness_2.png (12.19 KiB) Viewed 1579 times