View Single Post
Old 13 August 2019, 11:32   #62
Registered User

Join Date: Jun 2016
Location: UK
Posts: 338
Originally Posted by roondar View Post
In order for the grid system to work, every object needs to know where in the grid it is. Setting aside the obvious problem of objects potentially falling into multiple grid coordinates (and yes, that even happens if the grid is huge and can cause issues if not accounted for), you still need to calculate which grid coordinate each object belongs too. This is not needed for bounding box collisions.

That cost is missing in your comparison.

Furthermore, most properly coded bounding box algorithms will exit as soon as possible. The version Northway shows is one of the exceptions here. Using a simple set of comparisons and exiting on the first 'fail' tends to have most objects leave the comparisons on the first or second test.
"Calculating" the grid coordinate is trivial. Simply discard the lowest 3 or 4 bits of the X and Y coordinates (depending on your grid size) and combine into a single word. There is some overhead but it only needs to be done once per object, not once per collision.

On an A1200 it's free because the limiting factor is memory bandwidth.

Obviously I was looking at worst case, not including early exit. Even with early exit it's still a lot worse than the grid system.
zero is offline  
Page generated in 0.05012 seconds with 11 queries