Among other optimizations that need to be made, collision detection was one of the ones at the top of the list.  Doing it the brute force way is very crude.  The brute force way being take the list of objects on the screen, and compare it to every other object on the screen to see which ones collide.  This creates a rapidly escalating number of comparisons the program has to execute every cycle, which rises by the power of the square (n^2).

Last night I implemented the QuadTree algorithm to sort out objects and reduce the number of objects that have to be compared by determining which objects are close enough that they might intersect.  Things on opposite sides of the screen, for instance, can’t possibly intersect, so we can skip computing their collision.  It reduced the time it took for a cycle of the collision thread to complete from ~20-30ms for 200 creatures, down to an average of 4ms with 300 creatures.

Then I came into work this morning, where I had left a previous version of the program running over night to see how it handled extended running.  This version was using a ExecutorService and thread pool to help compute collisions in a brute force manner.  I’m still not entirely sure what happened, but this was the result when I came in this morning.  Note the execution timers in the top left.  The collision thread is now taking over 1,000,000ms to complete!  (that’s 16 minutes!)


Tags: , , , , ,