Help with my sweep collision test

Game Mechanics
#1

Hey all,

I’ve got a sweep collision test happening between two AABBs and I missed some key part of it because it doesn’t work perfectly. Don’t worry about how unoptimized it is - I am leaving it like this until I get it all working.

Here is the detection algorithm. It performs a sweep test on each axis, and given a last position and a current position returns the moment in time (the fraction between the last pos and current pos) where collision happened. This doesn’t seem to work totally correctly, plus stationary objects can overlap in each other, because pos - lastPos = 0. I’m thinking what’s wrong is that I’m dealing with the size of the object incorrectly.


/**
	 * Performs a sweep test against the other SpatialObject to determine
	 * whether collision exists anywhere along the movement path.
	 * @param o	The object to test collision against.
	 * @return	The first intersection time. If negative, no collision occurred.
	 */
	public float intersects(SpatialObject o)
	{
		float minXA = position.x < lastPosition.x ? position.x : lastPosition.x;
		float maxXA = (position.x > lastPosition.x ? position.x : lastPosition.x) + size.x;
		float minYA = position.y < lastPosition.y ? position.y : lastPosition.y;
		float maxYA = (position.y > lastPosition.y ? position.y : lastPosition.y) + size.y;
		
		float minXB = o.position.x < o.lastPosition.x ? o.position.x : o.lastPosition.x;
		float maxXB = (o.position.x > o.lastPosition.x ? o.position.x : o.lastPosition.x) + o.size.x;
		float minYB = o.position.y < o.lastPosition.y ? o.position.y : o.lastPosition.y;
		float maxYB = (o.position.y > o.lastPosition.y ? o.position.y : o.lastPosition.y) + o.size.y;
		
		//Do a quick bounding box check - if neither lie within these bounds, there is no collision.
		if ( minXA > maxXB || maxXA < minXB || minYA > maxYB || maxYA < minYB )
		{
			return -1.0f;
		}
		
		//We know they lie within each others' bounds of movement. Now see if the time periods match for each axis.
		float periodXMin = minXA < minXB ? (minXB - minXA) / (maxXA - minXA) : (minXA - minXB) / (maxXB - minXB);
		float periodXMax = maxXA > maxXB ? (maxXB - minXA) / (maxXA - minXA) : (maxXA - minXB) / (maxXB - minXB);
		float periodYMin = minYA < minYB ? (minYB - minYA) / (maxYA - minYA) : (minYA - minYB) / (maxYB - minYB);
		float periodYMax = maxYA > maxYB ? (maxYB - minYA) / (maxYA - minYA) : (maxYA - minYB) / (maxYB - minYB);
		
		//If the ranges don't lie within each other, there is no collision.
		if (periodXMin > periodYMax || periodXMax < periodYMin)
		{
			return -1.0f;
		}
		
		//Finally, we know we had collision. Return the initial intersection time.
		return (periodXMin < periodYMin ? periodYMin : periodXMin);
	}

And if there’s collision then moveBack() will be called to place them at the moment of collision. I already see what’s wrong with this for stationary objects (as mentioned above). I tried some different combinations using the size but they don’t work.


position.x = (position.x + size.x - lastPosition.x) * percent + lastPosition.x;
position.y = (position.y + size.y - lastPosition.y) * percent + lastPosition.y;

Any pointers before I waste more time on this? Thanks.

#2

http://kaioa.com/jws/jnlp_na/Collision.jnlp

Click/drag with left mouse button… then the same with the right one.

It uses a very outdated version of LWJGL. It might not work.

The source of this module (BSD 0-clause):

http://kaioa.com/k/AABB.java
http://kaioa.com/k/Collision.java

Wrote it about 4 years ago. I don’t remember any details, but the source itself should be good enough, I guess.

#3

No good? Thought the demo was pretty cool. I mean it even shows where the AABBs will collide (if they collide) and there is even an animation to show that it will indeed happen at the calculated position.

#4

Well I liked it at least.
Sounds like Demonpants is under a lot of deadline pressure at the moment though.

@Demonpants: Is this problem sorted now? What was the problem you were having? False positives? Negatives?

#5

Have to agree, very neat little demo!

Though not sure it needs LWJGL to draw a few rectangles & lines :wink:

#6

Well, I made it with my scripting framework. Back then I used a 500mhz CPU. As you can imagine the turn-over rates weren’t that nice out-of-the-box. Took over half a minute - even longer if there were any resources to load. With that framework I was able to cut it down to less than a second (if all resources were already cached).

I just swapped the Janino loader with the Java loader, compiled it, and put it online.

#7

Yes, it’s good, thanks, I’m just quite busy. I’ve decided that what I have is good enough for now, I’ll figure out how to make it perfect later.