1

Let there be o objects, and p projectiles.

When testing for collision between any projectile and any object, is the fastest algorithm going to be order of n-squared?

Here's my pseudocode: (I'm actually writing this in C++, not a Python-like language)

for projectile p in projectiles:
    for object o in objects:
        if /* check distance between p and o */:
            if /* collision */:
                foo()

I know that when checking for collision in one set of objects, I can reduce the algorithm from T(n^2) to T((n^2)/2) by not "rechecking" objects, or checking the same two objects against each other twice. However, in this case, there are two sets of objects. I have never written algorithms for two sets of objects before. Is it "okay" for my algorithm in this situation to be O(n^2)? Is there a fundamentally better way to go about this?

Notice

This question is NOT a duplicate of Collision detection of huge number of circles because that is talking about one set of objects. This question is entirely different.

If you do find a question involving two sets of objects --- not one set of objects --- please link to that question and then vote to close this question.

Why

Testing collision between two sets of objects is different than testing collision between one set of objects because:

When testing collision between one set of (sorted) objects, I can make the algorithm T((n^2)/2).

for(i = 0; i < length; ++i)
{
    for(j = i + 1; j < length; ++j)
    {
        /* test collision between i and j */
    }
}

Here's an example using indexes 1 through 5:

list: 1 2 3 4 5
1 - 2
1 - 3
1 - 4
1 - 5
2 - 3 /* notice this is NOT 2 - 1 */
2 - 4
2 - 5
3 - 4 /* again, this is NOT 3 - 1 or 3 - 2 */
3 - 5
4 - 5 /* finally, this is not 4 -1 or 4 - 2 or 4 - 3 */

This will take literally half the time that my algorithm for collision between two sets of objects takes. I know it doesn't change the big-O, but still, I think halving execution time is substantial. Here is my algorithm for collision between two sets of objects. It is T(n^2). I will explain.

for(i = 0; i < length; ++i)
{
    for(j = 0; j < length; ++j)
    {
        /* test collision between i and j */
    }
}

I believe you have to check every object against every other object. Because any projectile could be hitting any object, and we go through every projectile every time we go through one object. This algorithm could not be cut in half because we aren't testing projectiles against projectiles, or objects against objects.

Community
  • 1
  • 1
  • 4
    One big optimisation you can make is not to take square roots of distances between objects - so rather than check if objects are less than 10 units apart, check if their un-square-rooted distances apart are less than 100 units. – Mark Setchell Aug 11 '14 at 17:24
  • 3
    It all boils down to space partitioning. For example, if you had your objects and projectiles in an octree, you'd only have to do an O(n^2) search within each single cell. Additionally, you could keep a flag for each cell indicating whether anything moved in it since the last frame (generally not the case, so this provides a nice optimization). Another neat trick is to maintain a sorted list of your objects for each dimension of their positions -- then you only have to check for collisions between items that are adjacent/overlapping in each list (and updating the lists is quite fast). – Cameron Aug 11 '14 at 17:26
  • @dohashi please read my question before voting to close it. In my question I acknowledged the similar problem of collision in one set of objects. My post poses a question involving two sets of objects. These are fundamentally different questions and should be treated as such. –  Aug 11 '14 at 17:34
  • @MarkSetchell That is called the "Manhattan distance" – Moby Disk Aug 11 '14 at 17:37
  • Quadtree is what you are looking for : https://en.wikipedia.org/wiki/Quadtree – Davidbrcz Aug 11 '14 at 17:38
  • 1
    @MobyDisk: Manhattan distance is x+y, he's talking about x^2+y^2, which is simply distances squared. – Mooing Duck Aug 11 '14 at 17:41
  • 1
    @gragas: I can't think of a solution for a single set of objects that doesn't work perfectly for two sets, so this _is_ a duplicate in my opinion, until someone provides more evidence that the answers on that page cannot apply to two sets. – Mooing Duck Aug 11 '14 at 17:42
  • 2
    @gragas The answers for the linked question boil down to iteratively taking _one candidate circle_ and seeing if it collides with _any other circles_. How is that different from taking _one candidate projectile_ and seeing if it collides with _any object_? The algorithm should be essentially identical. – Useless Aug 11 '14 at 17:43
  • I think http://stackoverflow.com/questions/2544431/collision-detection-of-huge-number-of-circles is no duplicate, but very related! –  Aug 11 '14 at 17:46
  • @Useless while what you propose works, you might be able to do specific optimizations for testing multiple objects at once for collision. Not sure if it's worth in this case though. – JarkkoL Aug 11 '14 at 17:48
  • @MobyDisk No, I am saying that if you want to tell if 2 objects are less than 10m apart, you can calculate a^2 + b^2 and not bother doing the square root and then check if that value is less than 100. The Manhattan Distance is simply `a` + `b`, not `a^2` + `b^2`. – Mark Setchell Aug 11 '14 at 17:50
  • @MooingDuck Yes, exactly. I didn't see your comment. – Mark Setchell Aug 11 '14 at 17:52
  • @gragas: When comparing if objects in a set collide with each other, you compare each of the `N` objects, and compare them against each of the `N` other objects (sans half already compared), giving you `O(N*N)`. With your code, you need to compare `P` projectiles against `T` targets, giving you `O(P*T)` You can't do the optimization of ignoring already compared, but other than that, _the algorithms are going to be nearly identical_. – Mooing Duck Aug 11 '14 at 18:04
  • The fact that you don't understand that the answers apply to your problem does not mean that this is not a duplicate. We read and understand the question. You do not understand our answer. – Mooing Duck Aug 11 '14 at 18:06
  • @MooingDuck As I said in my post, though both have the same big-O, one takes **half** the time the other takes. This is substantial when you are calling the algorithm every frame. –  Aug 11 '14 at 18:06
  • @MooingDuck It is ridiculously hypocritical to say "You don't understand our answers. We understand your question." We both think that about each other, and we could both say it and believe it the same amount. I could say "You don't understand my question. I understand your answers." and that would be a null point. –  Aug 11 '14 at 18:10
  • 1
    @gragas: And yet, it does not change the fact that both are the same algorithm with the same big-O. You asked for an algorithm, we closed as a dupe asking for the same algorithm(s). If you want _optimizations for a specific algorithm given your two sets_, that is an altogether different question, for which you are encouraged to create a new question. (You would of course have to give more details about the code you're using for us to find optimizations) – Mooing Duck Aug 11 '14 at 18:11
  • @MooingDuck Two questions are not the same simply because their big-O values are the same. I am asking a different question that may happen to have the same big-O as a similar problem. Notice in my question I am talking about `T()` values, as well, which implies *optimizations for a specific algorithm given my two sets*. –  Aug 11 '14 at 18:14
  • @gragas: It appears that you're simply looping over all of the projectiles, and comparing the distance to each of the targets. For a nearly-identical question that has answers to this conundrum, see here: http://stackoverflow.com/questions/2544431/collision-detection-of-huge-number-of-circles Only trivial adjustments are necessary for your data. – Mooing Duck Aug 11 '14 at 18:26
  • @MooingDuck That is not true. I can make the algorithm `T((n^2)/2)` for that question, but for this question I can only get my algorithm down to `T(n^2)`. –  Aug 11 '14 at 18:56
  • @gragas: The top answer on the other page shows three optimizations and one of them is how to get it down to an _average_ of O(1). All of his optimizations also apply to your problem. – Mooing Duck Aug 11 '14 at 19:08
  • @MooingDuck Where does it talk about an O(1) solution? –  Aug 11 '14 at 22:24
  • @gragas: "Solution 1" of the first answer, is technically `O(N*M/)` rather than O(1) like I had believed, but the second answer suggests a quad-tree, which is O(1) (ish). Neither answer says O(1) directly, because that's not _quite_ right. They tend to perform as if they were O(1) for most projects though. – Mooing Duck Aug 11 '14 at 22:38

1 Answers1

3

It is ok to have an O(n^2) algorithm for small values of n. Somtimes if the algorithm is simple, it may even be faster than something running with a better O().

If you have many objects, I would recomend to put them in a q-tree (or some other spatial partitioning scheme) then your collision detection algorithm may run in O(n*log(n)), or even O(log(n)) if you only recheck when objects move.

youdontneedtothankme
  • 656
  • 4
  • 6