search

Darthfett / A-Priori-Physics-System

A side-scroller game based upon Mega Man X, with a priori collision detection, and objects being represented as a sequence of connected points.
3 stars 0 forks source link

Collision Detection algorithm slow #18

Closed Darthfett closed 12 years ago

Darthfett commented 12 years ago

The collision detection algorithm can be very slow when using a very large amount of lines. For example, when using 30 lines in a circle as a representation for the player.

Profiling using python's cProfile:

         5674765 function calls in 22.837 seconds

   Ordered by: internal time
   List reduced from 141 to 10 due to restriction <10>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     3494    3.077    0.001    3.077    0.001 {built-in method delay}
  1913935    2.908    0.000    2.908    0.000 vector.py:132(__getitem__)
   341169    2.205    0.000    3.726    0.000 vector.py:57(__add__)
   361979    1.742    0.000    2.793    0.000 vector.py:32(cross)
   988945    1.431    0.000    1.562    0.000 vector.py:136(__init__)
   184218    1.189    0.000    1.992    0.000 vector.py:60(__sub__)
    48000    1.164    0.000   10.600    0.000 physics.py:115(ParabolaLineCollision)
    42130    1.088    0.000    5.311    0.000 physics.py:141(<listcomp>)
   234280    1.034    0.000    1.341    0.000 vector.py:63(__mul__)
    12000    0.753    0.000   14.132    0.001 physics.py:145(find_intersections)

The items to note are probably the physics' ParabolaLineCollision and find_intersections functions. find_intersections calls ParabolaLineCollision.

Darthfett commented 12 years ago

A few things to note:

  1. While 30 lines to represent a single object is much more than necessary, a total of 40 lines shouldn't be nearly as slow as it is.
  2. Slowness is experienced upon collision, when all pairs between the 30-line-object and 10-line-object must be recalculated.
  3. Intersection.handle is causing this to recalculate both objects' intersections with all other objects (currently only the other object). In addition, Level.regenerate_ground causes another recalculation. This is twice the minimum amount of calculation upon impact, and given a very small amount of time between the ground generation and new collision time, as much as three times the minimum amount of calculation for the same duration of time.
  4. After the first demo, space partitioning will be implemented, which will add some overhead, but should speed things up overall.

The combination of the design to only need collision calculation upon invalidation, and space partitioning should ease up some of these issues. However, there will be still be some limitations with a large number of pairs of lines.

Pairs of Lines between the two existing objects (ground, player): 300 Number of collisions being calculated upon collision: 600 Number of collisions being calculated upon ground generation: 300

Darthfett commented 12 years ago

This issue is not in the milestone Demo 1, as:

  1. I've done nearly as much optimization as I can for this particular algorithm
  2. Space partitioning is not scheduled for this milestone.
Darthfett commented 12 years ago

With #30, I have reduced the number of calls to ParabolaLineCollision. With #31, I have found that parallelizing does not seem to be friendly with Windows (large overhead, terrible crashing, etc). It seems to be responsive for objects that are represented by a reasonable set of points. With space partitioning, this should not be too much of an issue, as space partitioning algorithms will be very fast, and avoid many unnecessary collision detections.

It's fair to say that the algorithm is not slow, and so I will close this.