HOME | DD

Description
So this was initiated by who recently asked me about algorithm I would recommend for collision detection broad phase and in particular mentioned sweep+prune [link]

This initiated series of tests and thinking on my part as I found this algorithm to be interesting. So result was that I tested different algorithms of sorting/finding/inserting items in arrays in flash [link] and came to a conclusion that Array.sort and Array.indexOf work so fast that probably should win over even faster algorithms of collision detection if I manage to make algorithm based on those core procedures.

Also I digged out my previous algorithm which turned out to be something like QuadTree algorithm(found out that recently ) and exchanged it to my realization of sweep+prune.

Usage and performance information/comparison
Usage. Well there is one bull under your cursor which you control and you can input ball count in box in Left-Bottom corner.

MoveAndRemove - step at which algorithm runs trough all balls and moves them and check if it is needed to remove those which flew beyond the screen.

SortAxis - there are separate array for each axis in which balls are contained. On this step those arrays are resorted.

checkSortedForColission - on this step sorted axis arrays are checked for object bondings intersections in pretty fast way. From what I can say a very fast way. Problem is then to find same pairs that intersected on both axis X and Y. And this so far is biggest slow down in this step. Need to think some more on it.

finalPairCheckAndResolve - on this step pairs that intersected on both axis are checked for collision more precisely and if determined to collide then collision is resolved.

Memory: Determines how much memory program currently uses.

Update
After some thinking and performance testings made changes to the algorithm. In short I changed how checkSortedForColission works and combined second part of checkSortedForColission with finalPairCheckAndResolve. As a result I got some 50% of performance boost Check journal to see results.

And extended explanation. Well Sweep+Prune sorts objects in separate arrays according to one of the axis of space. In those arrays those those objects are represented as one dimensional intervals which are easy to check for intersection. So in the end we have groups of intersections on each axis. Then we need to combine our results so that object pairs that intersect on all axis are pushed further to more precise/resource intensive checking and others are filtered out. Most resource taking part here is finding pairs that are contained in all axis arrays. Well before I was using Object for this. Turned out that I can use integers instead of strings as keys which makes it much faster but in the end made an algorithm based on Array and custom hashing function. So now bottleneck is sorting which is ridiculously fast Though I may try some more ideas on how to speed up this part.

Also before I was creating final pair list and looping trough it in separate loop but now understood that that was not necessary and merged it with last axis loop.

Description
So this was initiated by who recently asked me about algorithm I would recommend for collision detection broad phase and in particular mentioned sweep+prune [link]

This initiated series of tests and thinking on my part as I found this algorithm to be interesting. So result was that I tested different algorithms of sorting/finding/inserting items in arrays in flash [link] and came to a conclusion that Array.sort and Array.indexOf work so fast that probably should win over even faster algorithms of collision detection if I manage to make algorithm based on those core procedures.

Also I digged out my previous algorithm which turned out to be something like QuadTree algorithm(found out that recently ) and exchanged it to my realization of sweep+prune.

Usage and performance information/comparison
Usage. Well there is one bull under your cursor which you control and you can input ball count in box in Left-Bottom corner.

MoveAndRemove - step at which algorithm runs trough all balls and moves them and check if it is needed to remove those which flew beyond the screen.

SortAxis - there are separate array for each axis in which balls are contained. On this step those arrays are resorted.

checkSortedForColission - on this step sorted axis arrays are checked for object bondings intersections in pretty fast way. From what I can say a very fast way. Problem is then to find same pairs that intersected on both axis X and Y. And this so far is biggest slow down in this step. Need to think some more on it.

finalPairCheckAndResolve - on this step pairs that intersected on both axis are checked for collision more precisely and if determined to collide then collision is resolved.

Memory: Determines how much memory program currently uses.

Update
After some thinking and performance testings made changes to the algorithm. In short I changed how checkSortedForColission works and combined second part of checkSortedForColission with finalPairCheckAndResolve. As a result I got some 50% of performance boost Check journal to see results.

And extended explanation. Well Sweep+Prune sorts objects in separate arrays according to one of the axis of space. In those arrays those those objects are represented as one dimensional intervals which are easy to check for intersection. So in the end we have groups of intersections on each axis. Then we need to combine our results so that object pairs that intersect on all axis are pushed further to more precise/resource intensive checking and others are filtered out. Most resource taking part here is finding pairs that are contained in all axis arrays. Well before I was using Object for this. Turned out that I can use integers instead of strings as keys which makes it much faster but in the end made an algorithm based on Array and custom hashing function. So now bottleneck is sorting which is ridiculously fast Though I may try some more ideas on how to speed up this part.

Also before I was creating final pair list and looping trough it in separate loop but now understood that that was not necessary and merged it with last axis loop.