Quote:
Originally Posted by Shatterhand
If all enemies can be at any X or Y without actually have one side of the screen more used than the other, I have the feeling that the time you will take sorting it will not compensate for what you may gain with a binary search.
|
I dunno... You would avoid having to check every bullet against every enemy. Let's assume you maintain a list L sorted on x position containing enemies...
Pseudo code :
Code:
For each bullet b do
Enemy e = BinarySearch(L, bullet.x)
If e != null then
CheckBounds(e, bullet)
End if
Next
Let's assume your BinarySearch function returns a valid enemy pointer from list L if the x is within some distance of the enemy's x. If that is valid then do a bounds check. That way you're not comparing everything with everything else. The code complexity then approaches O(n) which is a vast improvement. You would probably need to also repeat this until no more enemies are found for that X.
Assuming blitz's list sort function is something sensible, it's quick to sort an already sorted (or mostly sorted) set.