CODEWITHSUNDEEP
algorithmcollision-detectionparticles
vincemathic
vincemathic

Reputation: 19

Runtime for a collision-detection algorithm

I've come up with an algorithm for predicting the collision between two particles. Given a rectangular environment (width w, height h), and two particles with known starting positions and velocities, it can determine

in a finite number of steps, so to say O(1). By extension, it can do this for n particles in O(n^2). Is there anything novel in this approach?

I'm assuming that the particles move in a linearly and at a constant velocity, and occupy points (so a collision would be when two particles occupy the same point).

Thank you for helping.

Upvotes: 1

Views: 655

Answers (2)

cobarzan
cobarzan

Reputation: 682

Here is a straight-forward solution assuming a rasterized setup and that collisions (inter-particle or particle-wall) do not modify the direction and speed of particles. The main idea is to "paint" the trajectories of the particles into a raster of size w x h.

allocate a raster of size w*h, each pixel being able to keep a list of (time,particle_id) tuples
for each particle pa
    for each pixel pi on the direction of pa
        store the tuple (time_of_pa_at_pi, pa_id) in the list of pi
for each pixel pi in the raster
    check for collisions inside the list of pi by ordering the tuples by time

The worst case scenario is pretty hard to describe, but an upper bound on the performance is O(n*max(w,h)) + O(wh) + max(w,h)*O(n*logn). The worst case scenario(s) probably occurs when all particles (or a large percentage of them) are traveling the same direction. This is extremely unlikely assuming a distribution uniformly at random of all the input params. Assuming that, in the average case scenario, the performance should be a lot better.

Additionally (but this is probably the important part of this answer), you can obtain a speed up if you first allocate a smaller raster (e.g. of size w/c x h/c) and you run a probable-collision check in the same manner as above. The pixels in this raster are larger, so the probable-collision step takes less. At the end of this step you get a feeling of what can happen in each macroscopic pixel and then continue your investigation locally (in a recursive way or using some other technique). The c above could be a constant or some function of w, h and n (e.g. c=sqrt(max(w,h))).

Of course, all the above are useless if w and/or h are inconveniently large.

Upvotes: 0

Nick Johnson
Nick Johnson

Reputation: 101149

It's very easy to do this in O(n^2) time for n particles simply by comparing all pairs of particles, and extrapolating a line segment for each to see where they collide.

More efficient algorithms exist, often based around the idea of indexing your objects in memory using something such as a quadtree; the Wikipedia article on collision detection has a good overview of another possible approach.

Upvotes: 2

Related Questions