HaxeFlixel/flixel — pull request #1267 by danim1130 (2014-08-13 02:36:55+00:00)
Title: Fixing the "Multiple overlap between two objects" issue

This pull request is supposed to fix the multiple overlap issue. Before going into the technical details, a quick summary:

* What does it do:
* When using the overlap() function, because of the way the FlxQuadTree works, two of the same object usually overlapped in more than one quadrant. Because of this, the callback function(s) were called multiple times, possibly causing bugs (player getting hit multiple times, etc.) This pull request is supposed to fix this.
* What will it break:
* I've wrote the code so that almost no one should be affected should this commit ever get into the master branch. The default value of SingleOverlap is false, so it won't change anything with older projects. The only thing that could possibly cause some issue is if someone also uses the built-in IDs of FlxBasics. If this is a problem, I could add another ID, specifically used for sorting to the FlxBasics.
* What about performance:
* During testing, I haven't really seen any difference. Naturally, singleOverlap uses extra memory, but besides that, it gives the same performance as the regular overlap in all normal cases (in extreme cases (>2000 object colliding on Release) the original overlap did better)

Technical Details:
==============

If SingleOverlap is used, instead of watching for overlaps in execute(), it will start checking the overlaps when an object to the A_LIST is added. For this to work properly, we first have to load in the B_LIST. After this, we add the first object to the A_LIST of one of the quadrants. When this happens, it will check the overlap with every object from B_LIST, and while doing so, adds every checked object to the _checked SearchArray. When it finished the quadrant, and goes recursively deeper, it will check with the SearchArray every time an object is being checked for overlap. If an object has been found in the array, it will get ignored, if not, it adds to the array, then checks for the overlap. After the recursive functions have finished, we reset the SearchArray, and add the next object from the group to the A_LIST.
The method is the same if _useBothList == false.

The SearchArray uses a binary search algorithm. It uses the ID of the FlxObjects, which I made to be a unique number for every FlxObject.