Simple, lightweight, general purpose collision detection

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by vrld »

Double post again to bump this topic (may the gods have mercy on my soul)

HardonCollider changes behavior:
As of the most recent update, HC will report collisions as soon as it detects them. Previously this was a two step process: In the first step, all collisions were collected and in the second, all collision were reported.

This led to complicated collision resolution when a shape x collided with two other shapes y and z at the same time and the resolution of x and y would also (partly) resolve the collision of x and z.

To give you (completely random :roll: ) example, consider a tile-based platformer. If the player managed to stand on two adjacent tiles, and the callback would simply push the player out of the tile he collided with, the player would be pushed up too far:
Some stunts had the be pulled to resolve this situation correctly.
Faulty collision resolution.
Faulty collision resolution.
collision_resolution.png (15.45 KiB) Viewed 2396 times
With the newly change, the second resolution (with tile b) will not be invoked, since after the collision with tile a is resolved, there is no longer a collision with tile b. Additionally, situations where a callback partly resolves a collision will also be handled correctly:
Step wise resolution.
Step wise resolution.
collision_resolution_step.png (22.26 KiB) Viewed 2396 times
Also, when you remove a shape in a collision callback, that shape will not be participating in any following on-collide callbacks (stop-collide will still be called, as it should be).

Get the new version here or as weirdly named zip here. Please let me know if you run into any issues using the new code.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by kikito »

Are collisions sorted out in any way? In other words, will TileB come always before TileA, or in some occasions will TileA come in first, depending on a random pairs() invokation?

That's one of the toughest problems I had in bump.lua . Right now it sorts by "surface colliding" (the tile covering most surface on the 'currently evaluated object' is collided first. This means lots of collisions are calculated and discarded. But well, AABBs are fast). It is not a silver bullet - sometimes it does the "non-intuitive" thing. I would be happy to get more brains working on the problem of "what colliding object should be dealt with first".
When I write def I mean function.
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by Ragzouken »

Is this supposed to support polygons with negative coordinates? I thought I was having some trouble creating a centered rectangle - something to do with it ending up with NAN and INF arguments for the dot product in the support routine. I don't really have a minimal test program at the moment, and the problem was non-deterministic, so I thought I'd just ask if I was trying to do something undefined?

Code: Select all

shapes.newPolygonShape(x-w, y-h,
                       x-w, y,
                         x, y,
                         x, y-h)
Last edited by Ragzouken on Mon Oct 08, 2012 5:23 pm, edited 1 time in total.
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by vrld »

Bartbes just asked how HC handles the situation that a collision callback moves a shape back into a shape from a previous callback, i.e. this situation (when only C is movable):
clusterfuck.png
clusterfuck.png (16.62 KiB) Viewed 2382 times
The answer is: it doesn't (and didn't before), so watch out for that.
kikito wrote:Are collisions sorted out in any way? In other words, will TileB come always before TileA, or in some occasions will TileA come in first, depending on a random pairs() invokation?
No. But there is no way of knowing in advance - for bump or HC anyways - which collision should be resolved first. :( However, most of the time it shouldn't matter (in the step example you will get the same end result regardless if you collide with TileA or TileB first).
kikito wrote:I would be happy to get more brains working on the problem of "what colliding object should be dealt with first".
The only way I see to really solve this problem would be to let the user assign priorities to which collisions should be reported first.
Ragzouken wrote:Is this supposed to support polygons with negative coordinates?
Yes.
Ragzouken wrote:something to do with it ending up with NAN and INF arguments for the dot product in the support routine.
Odd. Are you sure your coordinates are neither NaN nor very (and I mean VERY) big (or small)?
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by Ragzouken »

Actually, come to think of it, I'm getting really wacky results all round - and I can't replicate the same crash I used to get with that. For some reason I didn't get the problem if created the same rectangle with shape = collider:addRectangleShape(same coords) and then collider:remove(shape) - is there any reason that would be the case?

I'd investigate further, but it's code from a game jam, and complete spaghetti - probably I am just doing numerous stupid things that are interacting badly :/
User avatar
Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by Robin »

Great update!


I still need to include the following before resolving, though, to avoid "stumbling":

Code: Select all

    if bottom1 - 3 <= top2 then
    	mtv_x = 0
    end
Otherwise, when the player walks from the one tile to the next, it stops and you have to jump over the seam, even though it is pixelperfectly right.
Help us help you: attach a .love.
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by kikito »

kikito wrote:Are collisions sorted out in any way? In other words, will TileB come always before TileA, or in some occasions will TileA come in first, depending on a random pairs() invokation?
No. But there is no way of knowing in advance - for bump or HC anyways - which collision should be resolved first. :(

Probably you didn't mean both HC and bump on that phrase. It took me long time to get that feature working as I wanted on bump. But now TileB always comes first, if it covers more surface.
When I write def I mean function.
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by Ragzouken »

vrld wrote:Bartbes just asked how HC handles the situation that a collision callback moves a shape back into a shape from a previous callback, i.e. this situation (when only C is movable):
The attachment clusterfuck.png is no longer available
The answer is: it doesn't (and didn't before), so watch out for that.
What happens in this situation? Is it always / ever the case that the callbacks are called in an infinite loop due to the flip flopping?

I'm also experiencing a problem where a concave polygon colliding with a circle is giving a minimum translation vector where the y component is nil. My understanding is that the mtv should be valid for everything but points, and at the very least be non-nil for everything, so this is a bug?
Attachments
hardonbug.love
This demonstrates where my shape causes the failure.
(34.8 KiB) Downloaded 74 times
User avatar
Ragzouken
Citizen
Posts: 84
Joined: Fri Aug 10, 2012 7:59 am
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by Ragzouken »

The problem seems to be in lines 172-174 in shapes.lua (CircleShape:collidesWith) - for non-polygon non-circle shapes (convex polygons being "compound" type) the code only expects and returns one separation value, which doesn't seem consistent with anything else. I'm using the fix of just "return other:collidesWith(self)", but I'm not sure if that has other implications.

Code: Select all

-- else: let the other shape decide
local collide, sep = other:collidesWith(self)
return collide, sep and -sep

Code: Select all

-- else: let the other shape decide
return other:collidesWidth(self)
I have *tried* to submit a patch/whatever on github, but I have next to no idea what I'm doing, so apologies if I have done something stupid there.
User avatar
bartbes
Sex machine
Posts: 4946
Joined: Fri Aug 29, 2008 10:35 am
Location: The Netherlands
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by bartbes »

Ragzouken wrote: What happens in this situation? Is it always / ever the case that the callbacks are called in an infinite loop due to the flip flopping?
No, the callbacks are only called once.
Post Reply

Who is online

Users browsing this forum: No registered users and 5 guests