Collision Optimisation

[charlie_says]

I wrote a pretty nifty collision optimisation, which neatly gridded up the screen and then placed the (non-moving) shapes into a relevant array for lookup later.

I know need to do something very similar, again I'm using non-moving shapes, but unfortunately this time my collider isn't a point, it also is a shape.

Can anyone help me with a method for optimising shape to shape collisions... bearing in mind that the shapes are non uniform (some are circular, some square-ish, some triangles and some are long rectangles.)

Everything I've come up with so far is less optimal than just looping thru all the shapes.

[trogdor458]

Is the shape you're testing against the non-uniform shapes also non-uniform?
If it isn't, you could actually use something similar to your current collision optimization me thinks

If it is non-uniform, by how much? Is there only a couple of different states for it, or tons more?

I'm also interested a little in optimizing shape to shape collisions

EDIT: I kind of assumed you already had your math down for testing for collisions between shapes?
And you just wanted to know a way to speed up the process

[dandylion13]

Stefan Gottschalk's Separating Axis Theorem is the way to go if you want the best performance.

If you're up for a some math, his original paper is here (p. 67 is where SAT is introduced):

http://gamma.cs.unc.edu/theses/gottschalk/main.pdf

There's a more user-friendly explanation of the concepts here:

http://www.metanetsoftware.com/technique/tutorialA.html

The other option which works very well if performance is not a big concern is using hitTest and BitmapData. That allows you to easily check for collisions between irregular shapes. It's slow, but maybe that's not a concern?

http://www.anotherearlymorning.com/2...ctionscript-3/

[Freshmaker]

A second approach which may be used for detecting collisions between arbitrary convex polytopes is the GJK algorithm(s). From what I have heard, this algorithm is more difficult to implement than the SAT, but provides more flexibility in the long run. It does not seem difficult to understand to me, but I have not tried to implement it myself and I believe that may be where the difficulties lay.

Beyond that, a uniform grid is actually still a good approach for a spatial partitioning scheme for moving objects. For static detection, as you mentioned, other tree-like structures are often used--quadtree, kd-tree, bsp, etc.

[tonypa]

Is the problem in broad phase (which shapes to test) or narrow phase (shape vs shape collision)?

[charlie_says]

Thanks for all the responses.

I think Tony has cut to the chase (and basically highlighted part of the information I should have given in the initial question.)

What I'm looking for is the broad phase testing.

I looked at the Metanet tutorial (which is excellent) and although I didn't follow it my collision solution works very similarly.

The Separating Axis Theorem for Circles (Section 3) example highlights exactly the issue I'm trying to improve upon. I've got my circle and I calculate the distances to the corners of a block...

In my game if you imagine not one block but more like 15, I want to know which of the blocks I need to look at each of the four corner points for.

At the moment, I loop thru all blocks, and within that all points in that block. If the distance from the origin of the circle to a point is <r then I push it to an array and do some further checks specific to my game.

Every optimisation method I've thought or read about would seem to add complexity to the above... It's not optimising it if you have to add 30 lines of code and some really nasty algorithms.

@dandylion - I've just noticed this morning that your last link about the pixel perfect collision detection also has a link to broad phase testing - I'll read through the source and feedback here if it works

[tonypa]

Well, the good old grid is always an option. It works best when you got lots of small moving objects. Each object needs to check collision within 1-4 grids. However, when you have large objects that occupy several grids, it becomes more work.

For small number of objects (15 is not that much), I think trees and such are overkill. You could just do circle vs every box collision. You could reduce calculations perhaps by using bounding circles around the boxes. Lets say each box has center point, width and height. It will then fit into circle with radius equal to distance from any corner point to its center point. Now if the distance from circle to center of box is more then radius of circle plus radius of bounding circle, they cant collide. You dont need to find square roots for this. Only find distance between centers and compare with combined radius. Of course it works better for square boxes, for very thin boxes you get large number of false positives.

For not-so-squared boxes you could bound the circle inside square. The first check would now become comparing 2 boxes. Both of the boxes should have min and max value for x and y coordinate. The collision can not happen if boxes do not overlap:

if (a.maxx < b.minx || a.minx > b.maxx || a.maxy < b.miny || a.miny > b.maxy) return 0;

Each moving object has to update its min and max values on every step.

[charlie_says]

@tony

I had realised that doing with a grid and bounding boxes would probably work for me.

The unfortunate problem with the way I've done things (this time) is that some of my objects could occupy several grid cells (i.e. they're long and thin).

The only way I can think to avoid doing multiple checks on shapes that cross over cells s to push them to a new array, and to check that shapes aren't pushed more than once.

[charlie_says]

I thought there might be another way to do this, but then gave up about halfway through.

Tony's method of assigning each shape a radius is far and away easier than any other method - and it seems to afford some performance improvement (I don't drop frames, but I can see that CPU usage ramps up.)

If anyone is looking at this before they start a project - the way I would go about this next time is do not have shapes that can be positioned anywhere and be any shape/size - I would make it tile based simply as that cuts down on the other calculations you may need to make later on.

(Thanks Tony!)

[dandylion13]

For a small number of objects (15 is not that much), I think trees and such are overkill.

Yes, for broadphase to pay off you'd need to be doing collision tests between a few hundred objects per frame. This is because broadphase (like a grid) has itself a lot of overhead.

If you're testing less than 100 shapes, I wouldn't worry about it

[trogdor458]

I feel smart now, for having realized it was broad-phase optimization to begin with =)
I wouldn't mind expanding on this subject a bit, though

I myself have potentially thousands of possible colliders, and at that point even the calculations it costs to check bounding boxes could start adding up

Charlie: The radius method really takes less power for you than checking boundaries?
This surprises me
Don't forget that the box method can be split up into 4 different checks, allowing for many collision checks to stop short at a single comparision operator

1) minx1<maxx2
2) maxx1>minx2
3) miny1<maxy2
4) maxy1>miny2