dcsimg
A Flash Developer Resource Site

Results 1 to 11 of 11

Thread: Collision Optimisation

  1. #1
    Senior Member charlie_says's Avatar
    Join Date
    Feb 2003
    Location
    UK
    Posts
    508

    Collision Optimisation

    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.

  2. #2
    Please, Call Me Bob trogdor458's Avatar
    Join Date
    Aug 2006
    Location
    Pensacola, FL
    Posts
    915
    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
    Last edited by trogdor458; 01-19-2010 at 05:36 PM.

  3. #3
    Senior Member
    Join Date
    Oct 2009
    Posts
    118
    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/

  4. #4
    Junior Member
    Join Date
    Dec 2009
    Posts
    15
    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.

  5. #5
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,227
    Is the problem in broad phase (which shapes to test) or narrow phase (shape vs shape collision)?

  6. #6
    Senior Member charlie_says's Avatar
    Join Date
    Feb 2003
    Location
    UK
    Posts
    508
    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

  7. #7
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,227
    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.

  8. #8
    Senior Member charlie_says's Avatar
    Join Date
    Feb 2003
    Location
    UK
    Posts
    508
    @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.

  9. #9
    Senior Member charlie_says's Avatar
    Join Date
    Feb 2003
    Location
    UK
    Posts
    508
    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!)

  10. #10
    Senior Member
    Join Date
    Oct 2009
    Posts
    118
    Quote Originally Posted by tonypa View Post
    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

  11. #11
    Please, Call Me Bob trogdor458's Avatar
    Join Date
    Aug 2006
    Location
    Pensacola, FL
    Posts
    915
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center